TurboBŁYSK: Scheduling for improved data-driven task performance with fast dependency resolution
2014 (English)In: Using and Improving OpenMP for Devices, Tasks, and More: 10th International Workshop on OpenMP, IWOMP 2014, Salvador, Brazil, September 28-30, 2014. Proceedings, Springer, 2014, 45-57 p.Conference paper (Refereed)
Data-driven task-parallelism is attracting growing interest and has now been added to OpenMP (4.0). This paradigm simplifies the writing of parallel applications, extracting parallelism, and facilitates the use of distributed memory architectures. While the programming model itself is becoming mature, a problem with current run-time scheduler implementations is that they require a very large task granularity in order to scale. This limitation goes at odds with the idea of task-parallel programing where programmers should be able to concentrate on exposing parallelism with little regard to the task granularity. To mitigate this limitation, we have designed and implemented TurboBŁYSK, a highly efficient run-time scheduler of tasks with explicit data-dependence annotations. We propose a novel mechanism based on pattern-saving that allows the scheduler to re-use previously resolved dependency patterns, based on programmer annotations, enabling programs to use even the smallest of tasks and scale well. We experimentally show that our techniques in TurboBŁYSK enable achieving nearly twice the peak performance compared with other run-time schedulers. Our techniques are not OpenMP specific and can be implemented in other task-parallel frameworks.
Place, publisher, year, edition, pages
Springer, 2014. 45-57 p.
, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 8766
Application programming interfaces (API), Computer software reusability, Distributed memory architecture, Parallel application, Peak performance, Programming models, Scheduler implementation, Task granularity, Task parallelism, Task performance
IdentifiersURN: urn:nbn:se:kth:diva-161691DOI: 10.1007/978-3-319-11454-5_4ISI: 000360155400004ScopusID: 2-s2.0-84921513746ISBN: 978-3-319-11453-8ISBN: 978-3-319-11454-5OAI: oai:DiVA.org:kth-161691DiVA: diva2:798214
10th International Workshop on OpenMP, IWOMP 2014, Salvador, Brazil, September 28-30, 2014
QC 201503262015-03-262015-03-132016-01-27Bibliographically approved