Bi-objective scheduling algorithms for optimizing makespan and reliability on heterogeneous systems

Jack J. Dongarra, Emmanuel Jeannot, Erik Saule, Zhiao Shi

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    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-off 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-off between makespan and reliability. Copyright 2007 ACM.
    Original languageEnglish
    Title of host publicationAnnual ACM Symposium on Parallelism in Algorithms and Architectures|Annu. ACM Symp. Parall. Algorithms Archit.
    PublisherAssociation for Computing Machinery
    Pages280-288
    Number of pages8
    ISBN (Print)159593667X, 9781595936677
    DOIs
    Publication statusPublished - 2007
    EventSPAA'07: 19th Annual Symposium on Parallelism in Algorithms and Architectures - San Diego, CA
    Duration: 1 Jul 2007 → …
    http://dblp.uni-trier.de/db/conf/spaa/spaa2007.html#DongarraJSS07http://dblp.uni-trier.de/rec/bibtex/conf/spaa/DongarraJSS07.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/spaa/DongarraJSS07

    Conference

    ConferenceSPAA'07: 19th Annual Symposium on Parallelism in Algorithms and Architectures
    CitySan Diego, CA
    Period1/07/07 → …
    Internet address

    Keywords

    • DAG
    • Pareto-curve
    • Reliability
    • Scheduling

    Fingerprint

    Dive into the research topics of 'Bi-objective scheduling algorithms for optimizing makespan and reliability on heterogeneous systems'. Together they form a unique fingerprint.

    Cite this