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

TLDR

Scheduling task graphs on heterogeneous machines with exponentially distributed processor failures is the problem addressed. The study aims to develop algorithms that jointly optimize makespan and reliability. The authors present an optimal algorithm for independent unitary tasks that maximizes reliability while minimizing makespan, an approximation algorithm for the bi‑criteria Pareto curve, and a conversion technique that adapts existing heterogeneous‑cluster scheduling heuristics to incorporate reliability. The results show that the product of a processor’s failure rate and unitary instruction execution time is key for distinguishing processors, enabling users to select a trade‑off between reliability and makespan in both independent and general task‑graph settings.

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}x {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.