Efficient algorithms for array redistribution
Authors:
- A. ChoudharyACA. Choudhary
- J. RamanujamJRJ. Ramanujam
Open Access
- 1 June 1996
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 7 (6) , 587-594
Abstract
Dynamic redistribution of arrays is required very often in programs on distributed presents efficient algorithms for redistribution between different cyclic(k) distributions, as defined in High Performance Fortran. We first propose special optimized algorithms for a cyclic(x) to cyclic(y) redistribution when x is a multiple of y, or y is a multiple of x. We then propose two algorithms, called the GCD method and the LCM method, for the general cyclic(x) to cyclic(y) redistribution when there is no particular relation between x and y. We have implemented these algorithms on the Intel Touchstone Delta, and find that they perform well for different array sizes and number of processors.Keywords
This publication has 6 references indexed in Scilit:
- Complete exchange on the CM-5 and Touchstone DeltaThe Journal of Supercomputing, 1995
- Irregular Personalized Communication on Distributed Memory MachinesJournal of Parallel and Distributed Computing, 1995
- Generating Communication for Array Statements: Design, Implementation, and EvaluationJournal of Parallel and Distributed Computing, 1994
- An approach to communication-efficient data redistribution1994
- A new approach to array redistribution: Strip mining redistributionLecture Notes in Computer Science, 1994
- Compile-time generation of regular communications patterns1991