Improving parallel executions by increasing task granularity in task-based runtime systems using acyclic DAG clustering

Bérenger Bramas 1, 2 Alain Ketterlin 1, 2
2 CAMUS - Compilation pour les Architectures MUlti-coeurS
Inria Nancy - Grand Est, ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie
Abstract : The task-based approach is a parallelization paradigm in which an algorithm is transformed into a direct acyclic graph of tasks: the vertices are computational elements extracted from the original algorithm and the edges are dependencies between those. During the execution, the management of the dependencies adds an overhead that can become significant when the computational cost of the tasks is low. A possibility to reduce the makespan is to aggregate the tasks to make them heavier, while having fewer of them, with the objective of mitigating the importance of the overhead. In this paper, we study an existing clustering/partitioning strategy to speed up the parallel execution of a task-based application. We provide two additional heuristics to this algorithm and perform an in-depth study on a large graph set. In addition, we propose a new model to estimate the execution duration and use it to choose the proper granularity. We show that this strategy allows speeding up a real numerical application by a factor of 7 on a multi-core system.
Complete list of metadatas

Cited literature [37 references]  Display  Hide  Download

https://hal.inria.fr/hal-02436826
Contributor : Bérenger Bramas <>
Submitted on : Monday, January 13, 2020 - 1:59:37 PM
Last modification on : Tuesday, January 14, 2020 - 1:43:12 AM

File

peerj-cs-247.pdf
Files produced by the author(s)

Identifiers

Citation

Bérenger Bramas, Alain Ketterlin. Improving parallel executions by increasing task granularity in task-based runtime systems using acyclic DAG clustering. PeerJ Computer Science, PeerJ, 2020, ⟨10.7717/peerj-cs.247⟩. ⟨hal-02436826⟩

Share

Metrics

Record views

16

Files downloads

76