Scheduling Contract Algorithms on Multiple Processors

Daniel S. Bernstein, Theodore J. Perkins, Shlomo Zilberstein, and Lev Finkelstein. Scheduling Contract Algorithms on Multiple Processors. Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI), 702-706, Edmonton, Alberta, 2002.

Abstract

Anytime algorithms offer a tradeoff between computation time and the quality of the result returned. They can be divided into two classes: contract algorithms, for which the total run time must be specified in advance, and interruptible algorithms, which can be queried at any time for a solution. An interruptible algorithm can be constructed from a contract algorithm by repeatedly activating the contract algorithm with increasing run times. The acceleration ratio of a run-time schedule is a worst-case measure of how inefficient the constructed interruptible algorithm is compared to the contract algorithm. The smallest acceleration ratio achievable on a single processor is known. Using multiple processors, smaller acceleration ratios are possible. In this paper, we provide a schedule for m processors and prove that it is optimal for all m. Our results provide general guidelines for the use of parallel processors in the design of real-time systems.

Bibtex entry:

@inproceedings{BPZFaaai02,
  author	= {Daniel S. Bernstein and Theodore J. Perkins and Shlomo Zilberstein
                   and Lev Finkelstein},
  title		= {Scheduling Contract Algorithms on Multiple Processors},
  booktitle     = {Proceedings of the Eighteenth National Conference on Artificial
                   Intelligence},
  year		= {2002},
  pages		= {702-706},
  address       = {Edmonton, Alberta},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/BPZFaaai02.html}
}

shlomo@cs.umass.edu