Scheduling Contract Algorithms on Multiple Processors
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.
Cite
Text
Bernstein et al. "Scheduling Contract Algorithms on Multiple Processors." AAAI Conference on Artificial Intelligence, 2002. doi:10.5555/777092.777200Markdown
[Bernstein et al. "Scheduling Contract Algorithms on Multiple Processors." AAAI Conference on Artificial Intelligence, 2002.](https://mlanthology.org/aaai/2002/bernstein2002aaai-scheduling/) doi:10.5555/777092.777200BibTeX
@inproceedings{bernstein2002aaai-scheduling,
title = {{Scheduling Contract Algorithms on Multiple Processors}},
author = {Bernstein, Daniel S. and Perkins, Theodore J. and Zilberstein, Shlomo and Finkelstein, Lev},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2002},
pages = {702-706},
doi = {10.5555/777092.777200},
url = {https://mlanthology.org/aaai/2002/bernstein2002aaai-scheduling/}
}