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 schedule is a worst-case measure of how inefficient the constructed interruptible algorithm is compared to the contract algorithm. When the contracts are executed serially, i.e., on one processor, it is known how to choose contract lengths to minimize the acceleration ratio. We study the problem of scheduling contracts to run on processors in parallel. We derive an upper bound on the best possible acceleration ratio for processors, providing a simple exponential scheduling strategy that achieves this acceleration ratio. Further, we show that for the class of all round-robin schedules, no better acceleration ratio can be attained.