A semi-greedy heuristic for the mapping of large task graphs

K.-E. Berger 1 F. Galea 2 B.L. Cun 1 R. Sirdey 2
1 PRISM - Parallélisme, Réseaux, Systèmes, Modélisation
2 DACLE-LIST - Département d'Architectures, Conception et Logiciels Embarqués-LIST
Abstract : In the context of the dataflow process network mapping problem, we propose a parallel solutionmethod based on a semi-greedy heuristic to improve the solution quality of a greedy regret-based mapping algorithm (RBA). In this method, several executions of a randomized version of RBA are performed in parallel togenerate different solutions. We exploit a correlation between solution quality and execution time to propose a methodologyto stop the method after only a small amount of solutions are obtained.
Keywords : Conformal mapping Mapping Dataflow process networks Greedy heuristics Mapping algorithms Parallel heuristics Process network mappings Runtime optimization Solution quality Task graph Distributed computer systems
Document type :
Conference papers
Complete list of metadatas
https://hal-cea.archives-ouvertes.fr/cea-01838136
Contributor : Léna Le Roy <>
Submitted on : Friday, July 13, 2018 - 10:28:40 AM
Last modification on : Wednesday, January 23, 2019 - 2:39:33 PM

Identifiers

Collections

CEA | CNRS | PRISM | UVSQ | CEA-UPSAY | DRT | LIST | UNIV-PARIS-SACLAY

Citation

K.-E. Berger, F. Galea, B.L. Cun, R. Sirdey. A semi-greedy heuristic for the mapping of large task graphs. 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), May 2016, Chicago, United States. pp.817-824, ⟨10.1109/IPDPSW.2016.179⟩. ⟨cea-01838136⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

54

Contact

Informations

CCSD