More on scheduling block-cyclic array redistribution

Frédéric Desprez; Stéphane Domas; Jack Dongarra; Antoine Petitet; Cyril Randriamaro; Yves Robert

More on scheduling block-cyclic array redistribution

Frédéric Desprez, Stéphane Domas, Jack Dongarra, Antoine Petitet, Cyril Randriamaro, Yves Robert

Research output: Chapter in Book/Conference proceeding › Conference contribution

Abstract

This article is devoted to the run-time redistribution of one- dimensional arrays that are distributed in a block-cyclic fashion over a processor grid. In a previous paper, we have reported how to derive opti- mal schedules made up of successive communication-steps. In this paper we assume that successive steps may overlap. We show how to obtain an optimal scheduling for the most general case, namely, moving from a CYCLIC(r) distribution on a P-processor grid to a CYCLIC(s) distri- bution on a Q-processor grid, for arbitrary values of the redistribution parameters P, Q, r, and s. We use graph-theoretic algorithms, and mo- dular algebra techniques to derive these optimal schedulings. © Springer-Verlag Berlin Heidelberg 1998.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)\|Lect. Notes Comput. Sci.
Publisher	Springer Nature
Pages	275-287
Number of pages	12
Volume	1511
ISBN (Print)	3540651721, 9783540651727
Publication status	Published - 1998
Event	4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, LCR 1998 - Pittsburgh, PA Duration: 1 Jul 1998 → … http://dblp.uni-trier.de/db/conf/lcr/lcr98.html#DesprezDDPRR98http://dblp.uni-trier.de/rec/bibtex/conf/lcr/DesprezDDPRR98.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/lcr/DesprezDDPRR98

Publication series

Name	Lecture Notes in Computer Science

Conference

Conference	4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, LCR 1998
City	Pittsburgh, PA
Period	1/07/98 → …
Internet address	http://dblp.uni-trier.de/db/conf/lcr/lcr98.html#DesprezDDPRR98http://dblp.uni-trier.de/rec/bibtex/conf/lcr/DesprezDDPRR98.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/lcr/DesprezDDPRR98

Keywords

Asynchronous communications
Block-CYCLIC distribution
Distributed arrays
Hpf
Redistribution
Scheduling

Access to Document

Cite this

Desprez, F., Domas, S., Dongarra, J., Petitet, A., Randriamaro, C., & Robert, Y. (1998). More on scheduling block-cyclic array redistribution. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci. (Vol. 1511, pp. 275-287). (Lecture Notes in Computer Science). Springer Nature. http://dblp.uni-trier.de/db/conf/lcr/lcr98.html#DesprezDDPRR98

@inproceedings{0b97b67ebd704789820e31c5c69827f8,

title = "More on scheduling block-cyclic array redistribution",

abstract = "This article is devoted to the run-time redistribution of one- dimensional arrays that are distributed in a block-cyclic fashion over a processor grid. In a previous paper, we have reported how to derive opti- mal schedules made up of successive communication-steps. In this paper we assume that successive steps may overlap. We show how to obtain an optimal scheduling for the most general case, namely, moving from a CYCLIC(r) distribution on a P-processor grid to a CYCLIC(s) distri- bution on a Q-processor grid, for arbitrary values of the redistribution parameters P, Q, r, and s. We use graph-theoretic algorithms, and mo- dular algebra techniques to derive these optimal schedulings. {\textcopyright} Springer-Verlag Berlin Heidelberg 1998.",

keywords = "Asynchronous communications, Block-CYCLIC distribution, Distributed arrays, Hpf, Redistribution, Scheduling",

author = "Fr{\'e}d{\'e}ric Desprez and St{\'e}phane Domas and Jack Dongarra and Antoine Petitet and Cyril Randriamaro and Yves Robert",

year = "1998",

language = "English",

isbn = "3540651721",

volume = "1511",

series = "Lecture Notes in Computer Science",

publisher = "Springer Nature",

pages = "275--287",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.",

address = "United States",

note = "4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, LCR 1998 ; Conference date: 01-07-1998",

url = "http://dblp.uni-trier.de/db/conf/lcr/lcr98.html#DesprezDDPRR98http://dblp.uni-trier.de/rec/bibtex/conf/lcr/DesprezDDPRR98.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/lcr/DesprezDDPRR98",

}

Desprez, F, Domas, S, Dongarra, J, Petitet, A, Randriamaro, C & Robert, Y 1998, More on scheduling block-cyclic array redistribution. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.. vol. 1511, Lecture Notes in Computer Science, Springer Nature, pp. 275-287, 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, LCR 1998, Pittsburgh, PA, 1/07/98. <http://dblp.uni-trier.de/db/conf/lcr/lcr98.html#DesprezDDPRR98>

More on scheduling block-cyclic array redistribution. / Desprez, Frédéric; Domas, Stéphane; Dongarra, Jack et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.. Vol. 1511 Springer Nature, 1998. p. 275-287 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Conference proceeding › Conference contribution

TY - GEN

T1 - More on scheduling block-cyclic array redistribution

AU - Desprez, Frédéric

AU - Domas, Stéphane

AU - Dongarra, Jack

AU - Petitet, Antoine

AU - Randriamaro, Cyril

AU - Robert, Yves

PY - 1998

Y1 - 1998

N2 - This article is devoted to the run-time redistribution of one- dimensional arrays that are distributed in a block-cyclic fashion over a processor grid. In a previous paper, we have reported how to derive opti- mal schedules made up of successive communication-steps. In this paper we assume that successive steps may overlap. We show how to obtain an optimal scheduling for the most general case, namely, moving from a CYCLIC(r) distribution on a P-processor grid to a CYCLIC(s) distri- bution on a Q-processor grid, for arbitrary values of the redistribution parameters P, Q, r, and s. We use graph-theoretic algorithms, and mo- dular algebra techniques to derive these optimal schedulings. © Springer-Verlag Berlin Heidelberg 1998.

AB - This article is devoted to the run-time redistribution of one- dimensional arrays that are distributed in a block-cyclic fashion over a processor grid. In a previous paper, we have reported how to derive opti- mal schedules made up of successive communication-steps. In this paper we assume that successive steps may overlap. We show how to obtain an optimal scheduling for the most general case, namely, moving from a CYCLIC(r) distribution on a P-processor grid to a CYCLIC(s) distri- bution on a Q-processor grid, for arbitrary values of the redistribution parameters P, Q, r, and s. We use graph-theoretic algorithms, and mo- dular algebra techniques to derive these optimal schedulings. © Springer-Verlag Berlin Heidelberg 1998.

KW - Asynchronous communications

KW - Block-CYCLIC distribution

KW - Distributed arrays

KW - Hpf

KW - Redistribution

KW - Scheduling

M3 - Conference contribution

SN - 3540651721

SN - 9783540651727

VL - 1511

T3 - Lecture Notes in Computer Science

SP - 275

EP - 287

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.

PB - Springer Nature

T2 - 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, LCR 1998

Y2 - 1 July 1998

ER -

More on scheduling block-cyclic array redistribution

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this