Optimizing performance and reliability on heterogeneous parallel systems: Approximation algorithms and heuristics

摘要

We study the problem of scheduling tasks (with and without precedence constraints) on a set of related processors which have a probability of failure governed by an exponential law. The goal is to design approximation algorithms or heuristics that optimize both makespan and reliability. First, we show that both objectives are contradictory and that the number of points of the Pareto-front can be exponential. This means that this problem cannot be approximated by a single schedule. Second, for independent unitary tasks, we provide an optimal scheduling algorithm where the objective is to maximize the reliability subject to makespan minimization. For the bi-objective optimization, we provide a (1 + ∈, 1)-approximation algorithm of the Pareto-front. Next, for independent arbitrary tasks, we propose a (2, 1)-approximation algorithm (i.e. for any fixed value of the makespan, the obtained solution is optimal on the reliability and no more than twice the given makespan) that has a much lower complexity than the other existing algorithms. This solution is used to derive a (2 + ∈, l)-approximation of the Pareto-front of the problem. All these proposed solutions are discriminated by the value of the product {failure rate}×{unitary instruction execution time} of each processor, which appears to be a crucial parameter in the context of biobjective optimization. Based on this observation, we provide a general method for converting scheduling heuristics on heterogeneous clusters into heuristics that take into account the reliability when there are precedence constraints. The average behavior is studied by extensive simulations. Finally, we discuss the specific case of scheduling a chain of tasks which leads to optimal results.