Optimal Schedules for Parallelizing Anytime Algorithms

Lev Finkelstein, Shaul Markovitch and Ehud Rivlin. Optimal Schedules for Parallelizing Anytime Algorithms. In Proceedings of The AAAI Fall Symposium on Using Uncertainty within Computation, 49-56 North Carolina, 2001.

Abstract

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.

Keywords: Scheduling, Resource-Bounded Reasoning, Multi-Agent Systems

Secondary Keywords:

Online version:

Bibtex entry:

 @inproceedings{Finkelstein:2001:OSP,
  Author = {Lev Finkelstein and Shaul Markovitch and Ehud Rivlin},
  Title = {Optimal Schedules for Parallelizing Anytime Algorithms},
  Year = {2001},
  Booktitle = {Proceedings of The AAAI Fall Symposium on Using Uncertainty within Computation},
  Pages = {49--56},
  Address = {North Carolina},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Finkelstein-Markovitch-Rivlin-fss2001.pdf},
  Keywords = {Scheduling, Resource-Bounded Reasoning, Multi-Agent Systems},
  Secondary-keywords = {Anytime Algorithms, Portfolio, Las Vegas Algorithms, Parallelization},
  Abstract = {
    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.
  }

  }