More on scheduling block-cyclic array redistribution

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

doi:10.1007/3-540-49530-4_20

More on scheduling block-cyclic array redistribution

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

Computer Science and Mathematics Div

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

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.

Original language	English
Title of host publication	Languages, Compilers, and Run-Time Systems for Scalable Computers - 4th International Workshop, LCR 1998, Selected Papers
Publisher	Springer Verlag
Pages	275-287
Number of pages	13
ISBN (Print)	3540651721, 9783540651727
DOIs	https://doi.org/10.1007/3-540-49530-4_20
State	Published - 1998
Event	4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, LCR 1998 - Pittsburgh, PA, United States Duration: May 28 1998 → May 30 1998

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1511 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, LCR 1998
Country/Territory	United States
City	Pittsburgh, PA
Period	05/28/98 → 05/30/98

Keywords

Asynchronous communications
Block-CYCLIC distribution
Distributed arrays
Hpf
Redistribution
Scheduling

Access to Document

10.1007/3-540-49530-4_20

Cite this

Desprez, F., Domas, S., Dongarra, J., Petitet, A., Randriamaro, C., & Robert, Y. (1998). More on scheduling block-cyclic array redistribution. In Languages, Compilers, and Run-Time Systems for Scalable Computers - 4th International Workshop, LCR 1998, Selected Papers (pp. 275-287). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1511 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-49530-4_20

Desprez, Frédéric ; Domas, Stéphane ; Dongarra, Jack et al. / More on scheduling block-cyclic array redistribution. Languages, Compilers, and Run-Time Systems for Scalable Computers - 4th International Workshop, LCR 1998, Selected Papers. Springer Verlag, 1998. pp. 275-287 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{08ed31521d83490a8b9397b6f6c2ab75,

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.",

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",

doi = "10.1007/3-540-49530-4_20",

language = "English",

isbn = "3540651721",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "275--287",

booktitle = "Languages, Compilers, and Run-Time Systems for Scalable Computers - 4th International Workshop, LCR 1998, Selected Papers",

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

}

Desprez, F, Domas, S, Dongarra, J, Petitet, A, Randriamaro, C & Robert, Y 1998, More on scheduling block-cyclic array redistribution. in Languages, Compilers, and Run-Time Systems for Scalable Computers - 4th International Workshop, LCR 1998, Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1511 LNCS, Springer Verlag, pp. 275-287, 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, LCR 1998, Pittsburgh, PA, United States, 05/28/98. https://doi.org/10.1007/3-540-49530-4_20

More on scheduling block-cyclic array redistribution. / Desprez, Frédéric; Domas, Stéphane; Dongarra, Jack et al.
Languages, Compilers, and Run-Time Systems for Scalable Computers - 4th International Workshop, LCR 1998, Selected Papers. Springer Verlag, 1998. p. 275-287 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1511 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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.

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.

KW - Asynchronous communications

KW - Block-CYCLIC distribution

KW - Distributed arrays

KW - Hpf

KW - Redistribution

KW - Scheduling

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

U2 - 10.1007/3-540-49530-4_20

DO - 10.1007/3-540-49530-4_20

M3 - Conference contribution

AN - SCOPUS:84886635325

SN - 3540651721

SN - 9783540651727

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 275

EP - 287

BT - Languages, Compilers, and Run-Time Systems for Scalable Computers - 4th International Workshop, LCR 1998, Selected Papers

PB - Springer Verlag

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

Y2 - 28 May 1998 through 30 May 1998

ER -

Desprez F, Domas S, Dongarra J, Petitet A, Randriamaro C, Robert Y. More on scheduling block-cyclic array redistribution. In Languages, Compilers, and Run-Time Systems for Scalable Computers - 4th International Workshop, LCR 1998, Selected Papers. Springer Verlag. 1998. p. 275-287. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-49530-4_20

More on scheduling block-cyclic array redistribution

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this