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.
Type de document :
Article dans une revue
IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2016
Liste complète des métadonnées

Littérature citée [46 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01412922
Contributeur : Emmanuel Jeannot <>
Soumis le : vendredi 16 décembre 2016 - 12:52:27
Dernière modification le : jeudi 15 février 2018 - 08:48:08
Document(s) archivé(s) le : mardi 21 mars 2017 - 08:39:37

Fichier

hal.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01412922, version 1

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. 〈hal-01412922〉

Partager

Métriques

Consultations de la notice

377

Téléchargements de fichiers

50