Efficient algorithms for array redistribution

Rajeev Thakur*, Alok Choudhary, J. Ramanujam

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

49 Scopus citations

Abstract

Dynamic redistribution of arrays is required very often in programs on distributed memory parallel computers. This paper 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.

Original languageEnglish (US)
Pages (from-to)587-594
Number of pages8
JournalIEEE Transactions on Parallel and Distributed Systems
Volume7
Issue number6
DOIs
StatePublished - 1996

Keywords

  • Array redistribution
  • Data distribution
  • Distributed-memory computers
  • High Performance Fortran (HPF)
  • Runtime support

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Efficient algorithms for array redistribution'. Together they form a unique fingerprint.

Cite this