Skip to Main content Skip to Navigation
Journal articles

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

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.
Complete list of metadatas

Cited literature [46 references]  Display  Hide  Download

https://hal.inria.fr/hal-01412922
Contributor : Emmanuel Jeannot <>
Submitted on : Friday, December 16, 2016 - 12:52:27 PM
Last modification on : Friday, February 28, 2020 - 2:17:29 PM
Document(s) archivé(s) le : Tuesday, March 21, 2017 - 8:39:37 AM

File

hal.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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, Institute of Electrical and Electronics Engineers, 2016, 27 (11), pp.3158-3171. ⟨10.1109/TPDS.2016.2528983⟩. ⟨hal-01412922⟩

Share

Metrics

Record views

732

Files downloads

469