Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Shared Resources

Lev Finkelstein, Shaul Markovitch and Ehud Rivlin. Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Shared Resources. Journal of Artificial Intelligence Research, 19:73-138 2003.

Abstract

The performance of anytime algorithms can be improved by simultaneously solving several instances of algorithm-problem pairs. These pairs may include different instances of a problem (such as starting from a different initial state), different algorithms (if several alternatives exist), or several runs of the same algorithm (for non-deterministic algorithms). In this paper we present a methodology for designing an optimal scheduling policy based on the statistical characteristics of the algorithms involved. We formally analyze the case where the processes share resources (a single-processor model), and provide an algorithm for optimal scheduling. We analyze, theoretically and empirically, the behavior of our scheduling algorithm for various distribution types. Finally, we present empirical results of applying our scheduling algorithm to the Latin Square problem.

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

Secondary Keywords:

Online version:

Bibtex entry:

 @article{Finkelstein:2003:OSP,
  Author = {Lev Finkelstein and Shaul Markovitch and Ehud Rivlin},
  Title = {Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Shared Resources},
  Year = {2003},
  Journal = {Journal of Artificial Intelligence Research},
  Volume = {19},
  Pages = {73--138},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Finkelstein-Markovitch-Rivlin-jair2003.pdf},
  Keywords = {Scheduling, Resource-Bounded Reasoning, Multi-Agent Systems},
  Secondary-keywords = {Anytime Algorithms, Portfolio, Las Vegas Algorithms, Parallelization},
  Abstract = {
    The performance of anytime algorithms can be improved by
    simultaneously solving several instances of algorithm-problem
    pairs. These pairs may include different instances of a problem
    (such as starting from a different initial state), different
    algorithms (if several alternatives exist), or several runs of the
    same algorithm (for non-deterministic algorithms). In this paper
    we present a methodology for designing an optimal scheduling
    policy based on the statistical characteristics of the algorithms
    involved. We formally analyze the case where the processes share
    resources (a single-processor model), and provide an algorithm for
    optimal scheduling. We analyze, theoretically and empirically, the
    behavior of our scheduling algorithm for various distribution
    types. Finally, we present empirical results of applying our
    scheduling algorithm to the Latin Square problem.
  }

  }