Paper Info
Title
Improving parallel executions by increasing task granularity in task-based runtime systems using acyclic DAG clustering.
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.
Year
DOI
Venue
2020
10.7717/peerj-cs.247
PEERJ COMPUTER SCIENCE
Keywords
Field
DocType
Task-based,Graph,DAG,Clustering,Partitioning
Paleontology,Graph,Direct acyclic graph,Job shop scheduling,Vertex (geometry),Biology,Theoretical computer science,Heuristics,Granularity,Cluster analysis,Speedup
Journal
Volume
ISSN
Citations 
6
2376-5992
1
PageRank 
References 
Authors
0.36
0
2
Name
Order
Citations
PageRank
Bérenger Bramas110.70
Alain Ketterlin210.36