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

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

2011-06-26

arxiv.org/abs/1106.5269v1

Journal Of Artificial Intelligence Research, Volume 19, pages 73-138, 2003

Computer Science

Artificial Intelligence

Scientific paper

10.1613/jair.1195

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.

Affiliated with

Also associated with

No associations

Rating

Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Shared Resources does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Shared Resources, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Schedules for Parallelizing Anytime Algorithms: The Case of Shared Resources will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-637773