Personal tools
You are here: Home Publications Bi-objective Scheduling Algorithms for Optimizing Makespan and Reliability on Heterogeneous Systems
Document Actions

Jack Dongarra, Emmanuel Jeannot, Erik Saule, and Zhiao Shi (2007)

Bi-objective Scheduling Algorithms for Optimizing Makespan and Reliability on Heterogeneous Systems

In: Proceedings of 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '07), ACM.

We tackle the problem of scheduling task graphs onto a heterogeneous set of machines, where each processor has a probability of failure governed by an exponential law. The goal is to design algorithms that optimize both makespan and reliability. First, we provide an optimal scheduling algorithm for independent unitary tasks where the objective is to maximize the reliability subject to makespan minimization. For the bi-criteria case, we provide an algorithm that approximates the Pareto-curve. Next, for independent non-unitary tasks, we show that the product failure rate× unitary instruction execution time is crucial to distinguish processors in this context. Based on these results we are able to let the user choose a trade-o between reliability maximization and makespan minimization. For general task graphs we provide a method for converting scheduling heuristics on heterogeneous cluster into heuristics that take reliability into account. Here again, we show how we can help the user to select a trade-o between makespan and reliability. publisher = "ACM",

by admin last modified 2008-04-30 12:20
« October 2010 »
Su Mo Tu We Th Fr Sa
12
3456789
10111213141516
17181920212223
24252627282930
31
 

VGrADS Collaborators include:

Rice University UCSD UH UCSB UTK ISI UTK

Powered by Plone