Correlation-Aware Heuristics for Evaluating the Distribution of the Longest Path Length of a DAG with Random Weights - Archive ouverte HAL Access content directly
Journal Articles IEEE Transactions on Parallel and Distributed Systems Year : 2016

Correlation-Aware Heuristics for Evaluating the Distribution of the Longest Path Length of a DAG with Random Weights

(1) , (2)
1
2

Abstract

Coping with uncertainties when scheduling task graphs on parallel machines requires to perform non-trivial evaluations. When considering that each computation and communication duration is a random variable, evaluating the distribution of the critical path length of such graphs involves computing maximums and sums of possibly de- pendent random variables. The discrete version of this evaluation problem is known to be #P- hard. Here, we propose two heuristics, CorLCA and Cordyn, to compute such lengths. They ap- proximate the input random variables and the intermediate ones as normal random variables, and they precisely take into account correlations with two distinct mechanisms: through lowest common ancestor queries for CorLCA and with a dynamic programming approach for Cordyn. Moreover, we empirically compare some classical methods from the literature and confront them to our solutions. Simulations on a large set of cases indicate that CorLCA and Cordyn consti- tute each a new relevant trade-off in terms of rapidity and precision.
Fichier principal
Vignette du fichier
hal.pdf (1.12 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01412922 , version 1 (16-12-2016)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

Louis-Claude Canon, Emmanuel Jeannot. Correlation-Aware Heuristics for Evaluating the Distribution of the Longest Path Length of a DAG with Random Weights. IEEE Transactions on Parallel and Distributed Systems, 2016, 27 (11), pp.3158-3171. ⟨10.1109/TPDS.2016.2528983⟩. ⟨hal-01412922⟩
446 View
249 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More