Task-graph scheduling extensions for efficient synchronization and communication

Seonmyeong Bak, Oscar Hernandez, Mark Gates, Piotr Luszczek, Vivek Sarkar

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

Task graphs have been studied for decades as a foundation for scheduling irregular parallel applications and incorporated in many programming models including OpenMP. While many high-performance parallel libraries are based on task graphs, they also have additional scheduling requirements, such as synchronization within inner levels of data parallelism and internal blocking communications. In this paper, we extend task-graph scheduling to support efficient synchronization and communication within tasks. Compared to past work, our scheduler avoids deadlock and oversubscription of worker threads, and refines victim selection to increase the overlap of sibling tasks. To the best of our knowledge, our approach is the first to combine gang-scheduling and work-stealing in a single runtime. Our approach has been evaluated on the SLATE high-performance linear algebra library. Relative to the LLVM OMP runtime, our runtime demonstrates performance improvements of up to 13.82%, 15.2%, and 36.94% for LU, QR, and Cholesky, respectively, evaluated across different configurations related to matrix size, number of nodes, and use of CPUs vs GPUs.

Original languageEnglish
Title of host publicationICS 2021 - Proceedings of the 2021 ACM International Conference on Supercomputing
PublisherAssociation for Computing Machinery
Pages88-101
Number of pages14
ISBN (Electronic)9781450383356
DOIs
StatePublished - Jun 3 2021
Event35th ACM International Conference on Supercomputing, ICS 2021 - Virtual, Online, United States
Duration: Jun 14 2021Jun 17 2021

Publication series

NameProceedings of the International Conference on Supercomputing

Conference

Conference35th ACM International Conference on Supercomputing, ICS 2021
Country/TerritoryUnited States
CityVirtual, Online
Period06/14/2106/17/21

Funding

This work was supported by the Exascale Computing Project (17-SC-20-SC), a collaborative effort of the U.S. Department of Energy Office of Science and the National Nuclear Security Administration. This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy.

FundersFunder number
U.S. Department of Energy
National Nuclear Security AdministrationDE-AC05-00OR22725

    Keywords

    • Gang scheduling
    • OpenMP
    • Runtime system
    • Task graph
    • Work stealing

    Fingerprint

    Dive into the research topics of 'Task-graph scheduling extensions for efficient synchronization and communication'. Together they form a unique fingerprint.

    Cite this