Evaluating Data Redistribution in PaRSEC

Qinglei Cao; George Bosilca; Nuria Losada; Wei Wu; Dong Zhong; Jack Dongarra

doi:10.1109/TPDS.2021.3131657

Evaluating Data Redistribution in PaRSEC

Qinglei Cao, George Bosilca, Nuria Losada, Wei Wu, Dong Zhong, Jack Dongarra

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

Data redistribution aims to reshuffle data to optimize some objective for an algorithm. The objective can be multi-dimensional, such as improving computational load balance or decreasing communication volume or cost, with the ultimate goal of increasing the efficiency and therefore reducing the time-to-solution for the algorithm. The classic redistribution problem focuses on optimally scheduling communications when reshuffling data between two regular, usually block-cyclic, data distributions. Besides distribution, data size is also a performance-critical parameter because it affects the reshuffling algorithm in terms of cache, communication efficiency, and potential parallelism. In addition, task-based runtime systems have gained popularity recently as a potential candidate to address the programming complexity on the way to exascale. In this scenario, it becomes paramount to develop a flexible redistribution algorithm for task-based runtime systems, which could support all types of regular and irregular data distributions and take data size into account. In this article, we detail a flexible redistribution algorithm and implement an efficient approach in a task-based runtime system, PaRSEC. Performance results show great capability compared to the theoretical bound and ScaLAPACK, and applications highlight an increased efficiency with little overhead in terms of data distribution, data size, and data format.

Original language	English (US)
Pages (from-to)	1856-1872
Number of pages	17
Journal	IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
Volume	33
Issue number	8
DOIs	https://doi.org/10.1109/TPDS.2021.3131657
State	Published - Nov 30 2021
Externally published	Yes

Bibliographical note

KAUST Repository Item: Exported on 2022-05-26
Acknowledgements: This work was supported in part by the Exascale Computing Project under Grant 17-SC-20-SC, a collaborative effort of the U.S. Department of Energy Office of Science and the National Nuclear Security Administration. For computer time, this research used the Shaheen II supercomputer hosted at the Supercomputing Laboratory at KAUST.
The authors would like to thank Aurelien Bouteiller for multi-threaded supports in PaRSEC Cray Inc. and Intel in the context of the Cray Center of Excellence and Intel Parallel Computing Center awarded to the Extreme Computing Research Center at KAUST.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

Access to Document

10.1109/TPDS.2021.3131657

Cite this

@article{352b4ddd8d84415baaa3f029112f5de0,

title = "Evaluating Data Redistribution in PaRSEC",

abstract = "Data redistribution aims to reshuffle data to optimize some objective for an algorithm. The objective can be multi-dimensional, such as improving computational load balance or decreasing communication volume or cost, with the ultimate goal of increasing the efficiency and therefore reducing the time-to-solution for the algorithm. The classic redistribution problem focuses on optimally scheduling communications when reshuffling data between two regular, usually block-cyclic, data distributions. Besides distribution, data size is also a performance-critical parameter because it affects the reshuffling algorithm in terms of cache, communication efficiency, and potential parallelism. In addition, task-based runtime systems have gained popularity recently as a potential candidate to address the programming complexity on the way to exascale. In this scenario, it becomes paramount to develop a flexible redistribution algorithm for task-based runtime systems, which could support all types of regular and irregular data distributions and take data size into account. In this article, we detail a flexible redistribution algorithm and implement an efficient approach in a task-based runtime system, PaRSEC. Performance results show great capability compared to the theoretical bound and ScaLAPACK, and applications highlight an increased efficiency with little overhead in terms of data distribution, data size, and data format.",

author = "Qinglei Cao and George Bosilca and Nuria Losada and Wei Wu and Dong Zhong and Jack Dongarra",

note = "KAUST Repository Item: Exported on 2022-05-26 Acknowledgements: This work was supported in part by the Exascale Computing Project under Grant 17-SC-20-SC, a collaborative effort of the U.S. Department of Energy Office of Science and the National Nuclear Security Administration. For computer time, this research used the Shaheen II supercomputer hosted at the Supercomputing Laboratory at KAUST. The authors would like to thank Aurelien Bouteiller for multi-threaded supports in PaRSEC Cray Inc. and Intel in the context of the Cray Center of Excellence and Intel Parallel Computing Center awarded to the Extreme Computing Research Center at KAUST. This publication acknowledges KAUST support, but has no KAUST affiliated authors.",

year = "2021",

month = nov,

day = "30",

doi = "10.1109/TPDS.2021.3131657",

language = "English (US)",

volume = "33",

pages = "1856--1872",

journal = "IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS",

issn = "1558-2183",

publisher = "Institute of Electrical and Electronics Engineers",

number = "8",

}

TY - JOUR

T1 - Evaluating Data Redistribution in PaRSEC

AU - Cao, Qinglei

AU - Bosilca, George

AU - Losada, Nuria

AU - Wu, Wei

AU - Zhong, Dong

AU - Dongarra, Jack

N1 - KAUST Repository Item: Exported on 2022-05-26 Acknowledgements: This work was supported in part by the Exascale Computing Project under Grant 17-SC-20-SC, a collaborative effort of the U.S. Department of Energy Office of Science and the National Nuclear Security Administration. For computer time, this research used the Shaheen II supercomputer hosted at the Supercomputing Laboratory at KAUST. The authors would like to thank Aurelien Bouteiller for multi-threaded supports in PaRSEC Cray Inc. and Intel in the context of the Cray Center of Excellence and Intel Parallel Computing Center awarded to the Extreme Computing Research Center at KAUST. This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2021/11/30

Y1 - 2021/11/30

N2 - Data redistribution aims to reshuffle data to optimize some objective for an algorithm. The objective can be multi-dimensional, such as improving computational load balance or decreasing communication volume or cost, with the ultimate goal of increasing the efficiency and therefore reducing the time-to-solution for the algorithm. The classic redistribution problem focuses on optimally scheduling communications when reshuffling data between two regular, usually block-cyclic, data distributions. Besides distribution, data size is also a performance-critical parameter because it affects the reshuffling algorithm in terms of cache, communication efficiency, and potential parallelism. In addition, task-based runtime systems have gained popularity recently as a potential candidate to address the programming complexity on the way to exascale. In this scenario, it becomes paramount to develop a flexible redistribution algorithm for task-based runtime systems, which could support all types of regular and irregular data distributions and take data size into account. In this article, we detail a flexible redistribution algorithm and implement an efficient approach in a task-based runtime system, PaRSEC. Performance results show great capability compared to the theoretical bound and ScaLAPACK, and applications highlight an increased efficiency with little overhead in terms of data distribution, data size, and data format.

AB - Data redistribution aims to reshuffle data to optimize some objective for an algorithm. The objective can be multi-dimensional, such as improving computational load balance or decreasing communication volume or cost, with the ultimate goal of increasing the efficiency and therefore reducing the time-to-solution for the algorithm. The classic redistribution problem focuses on optimally scheduling communications when reshuffling data between two regular, usually block-cyclic, data distributions. Besides distribution, data size is also a performance-critical parameter because it affects the reshuffling algorithm in terms of cache, communication efficiency, and potential parallelism. In addition, task-based runtime systems have gained popularity recently as a potential candidate to address the programming complexity on the way to exascale. In this scenario, it becomes paramount to develop a flexible redistribution algorithm for task-based runtime systems, which could support all types of regular and irregular data distributions and take data size into account. In this article, we detail a flexible redistribution algorithm and implement an efficient approach in a task-based runtime system, PaRSEC. Performance results show great capability compared to the theoretical bound and ScaLAPACK, and applications highlight an increased efficiency with little overhead in terms of data distribution, data size, and data format.

UR - http://hdl.handle.net/10754/678245

UR - https://ieeexplore.ieee.org/document/9629320/

UR - http://www.scopus.com/inward/record.url?scp=85121846332&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2021.3131657

DO - 10.1109/TPDS.2021.3131657

M3 - Article

SN - 1558-2183

VL - 33

SP - 1856

EP - 1872

JO - IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS

JF - IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS

IS - 8

ER -

Evaluating Data Redistribution in PaRSEC

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this