.png){kind=icon}
返回
Optimizing performance and reliability on heterogeneous parallel systems: Approximation algorithms and heuristics
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2011.11.003.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 + epsilon, 1)-approximation algorithm of the Pareto-front. Next, for independent arbitrary tasks, we propose a ((2) over bar, 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 + epsilon, 1)-approximation of the Pareto-front of the problem. All these proposed solutions are discriminated by the value of the product {failure rate} x {unitary instruction execution time} of each processor, which appears to be a crucial parameter in the context of bi-objective 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. (C) 2011 Elsevier Inc. All rights reserved.
Keyword:
Scheduling
Pareto-front approximation
Reliability
Makespan
Precedence task graphs
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
机构
引用论文
分享收藏分享收藏Basic Helix-Loop-Helix Transcription Factor TCF21 Is a Downstream Target of the Male Sex Determining Gene SRY.png)
PLoS ONE
OAAI
PLoS ONEIF0
OAAI分享收藏Analysis on Error Rate of Wireless Optical Communication Using Subcarrier Modulation on Turbo Code
PREAI
分享收藏分享收藏
查看更多内容