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

K.-E. Berger; F. Galea; B.L. Cun; R. Sirdey

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

K.-E. Berger ¹ F. Galea ² B.L. Cun ¹ R. Sirdey ²

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

Domain :

Computer Science [cs]

Engineering Sciences [physics]

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

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

Identifiers

Collections

Citation

Export

Metrics

43

Contact

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

Identifiers

Collections

Citation

Export

Share

Metrics

43

Contact