Optimal Schedules for Parallelizing Anytime Algorithms

Lev Finkelstein, Shaul Markovitch, and Ehud Rivlin

The performance of anytime algorithms having a nondeterministic nature can be improved by solving simultaneously several instances of the algorithm-problem pairs. These pairs may include different instances of a problem (like starting from a different initial state), different algorithms (if several alternatives exist), or several instances of the same algorithm (for non-deterministic algorithms). A straightforward parallelization, however, usually results in only a linear speedup, while more effective parallelization schemes require knowledge about the problem space and/or the algorithm itself. In this paper we present a general framework for parallelization, which uses only minimal information on the algorithm (namely, its probabilistic behavior, described by a performance profile), and obtains a super-linear speedup by optimal scheduling of different instances of the algorithm-problem pairs. We show a mathematical model for this framework, present algorithms for optimal scheduling, and demonstrate the behavior of optimal schedules for different kinds of anytime algorithms.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.