Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Independent Processes

Lev Finkelstein, Shaul Markovitch and Ehud Rivlin. Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Independent Processes. In Proceedings of the Eighteenth National Conference on Artificial Intelligence, 719-724 Edmonton, Alberta, Canada, 2002.

Abstract

The performance of anytime algorithms having a non-deterministic 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). In this paper we present a general framework for optimal parallelization of independent processes. We show a mathematical model for this framework, present algorithms for optimal scheduling, and demonstrate its usefulness on a real problem.

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

Secondary Keywords:

Online version:

Bibtex entry:

 @inproceedings{Finkelstein:2002:OSP,
  Author = {Lev Finkelstein and Shaul Markovitch and Ehud Rivlin},
  Title = {Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Independent Processes},
  Year = {2002},
  Booktitle = {Proceedings of the Eighteenth National Conference on Artificial Intelligence},
  Pages = {719--724},
  Address = {Edmonton, Alberta, Canada},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Finkelstein-Markovitch-Rivlin-aaai2002.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 non-deterministic
    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). In this paper we present a general framework for
    optimal parallelization of independent processes. We show a
    mathematical model for this framework, present algorithms for
    optimal scheduling, and demonstrate its usefulness on a real
    problem.
  }

  }