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. While previous studies have concentrated on efficiently generating the communication messages to be exchanged by the processors involved in the redistribution, we focus on the scheduling of those messages: how to organize the message exchanges into "structured" communication steps that minimize contention. We build upon results of Walker and Otto, who solved a particular instance of the problem, and we derive an optimal scheduling for the most general case, namely, moving from a CYCLIC (r) distribution on a P-processor grid to a CYCLIC (s) distribution on a Q-processor grid, for arbitrary values of the redistribution parameters P, Q, r, and s.
| Original language | English |
|---|---|
| Pages (from-to) | 192-205 |
| Number of pages | 14 |
| Journal | IEEE Transactions on Parallel and Distributed Systems |
| Volume | 9 |
| Issue number | 2 |
| DOIs | |
| State | Published - 1998 |
Funding
We thank the reviewers whose comments and suggestions have greatly improved the presentation of the paper. This work was supported in part by the U.S. National Science Foundation Grant no. ASC-9005933; by the U.S. Defense Advanced Research Projects Agency under contract DAAH04-95-1-0077, administered by the U.S. Army Research Office; by the U.S. Department of Energy Office of Computational and Technology Research, Mathematical, Information, and Computational Sciences Division under Contract DE-AC05-84OR21400; by the U.S. National Science Foundation Science and Technology Center Cooperative Agreement no. CCR-8809615; by the CNRS–ENS Lyon–INRIA project ReMaP; and by the Eureka Project EuroTOPS. Yves Robert is on leave from Ecole Normale Supérieure de Lyon and is partly supported by DRET/DGA under contract ERE 96-1104/A000/DRET/DS/SR. The authors acknowledge the use of the Intel Paragon XP/S 5 computer, located in the Oak Ridge National Laboratory Center for Computational Sciences, funded by the U.S. Department of Energy’s Mathematical, Information, and Computational Sciences Division subprogram of the Office of Computational and Technology Research.
| Funders | Funder number |
|---|---|
| DRET/DGA | ERE 96-1104/A000/DRET/DS/SR |
| National Science Foundation Science and Technology Center | CCR-8809615 |
| Office of Computational and Technology Research | |
| U.S. Army Research Office | |
| National Science Foundation | ASC-9005933 |
| U.S. Department of Energy | DE-AC05-84OR21400 |
| Defense Advanced Research Projects Agency | DAAH04-95-1-0077 |
| Oak Ridge National Laboratory | |
| Centre National de la Recherche Scientifique |
Keywords
- Block-cyclic distribution
- Distributed arrays
- HPF
- MPI
- Redistribution
- Scheduling