Optimal schedules for parallelizing anytime algorithms: the case of independent processes
Lev Finkelstein, Shaul Markovitch, Ehud Rivlin · 2002
The performance of anytime algorithms having a non-deterministic nature can be improved by solving simultane-ously several instances of the algorithm-problem pairs. These pairs may include different instances of a problem (like start-ing from a different initial state), different algorithms (if sev-eral alternatives exist), or several instances of the same al-gorithm (for non-deterministic algorithms). A straightfor-ward parallelization, however, usually results in only a linear speedup, while more effective parallelization schemes require knowledge about the problem space and/or the algorithm it-self. In this paper we present a general framework for paralleliza-tion, which uses only minimal information on the algorithm (namely, its probabilistic behavior, described by a perfor-mance 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 any-time algorithms.