Article

Multi-phase array redistribution: modeling and evaluation

Authors:

S. D. Kaushik,

Chua-Huang Huang,

J. Ramanujam,

P. SadayappanAuthors Info & Claims

IPPS '95: Proceedings of the 9th International Symposium on Parallel Processing

Pages 441 - 445

Published: 25 April 1995 Publication History

Publisher Site

Abstract

Array redistribution is used in languages such as High Performance Fortran to allow programmers to dynamically change the distribution of arrays across processors. Distributed-memory implementations of several scientific applications require array redistribution. In this paper, efficient methods for performing array redistribution are presented. Precise closed forms for determining the processors involved in the communication and the data elements to be communicated are developed for two special cases of array redistribution involving block-cyclically distributed arrays. The general array redistribution problem involving block-cyclically distributed arrays can be expressed in terms of these special cases. Using the closed forms, a cost model for estimating the communication overhead for array redistribution is developed. A multi-phase approach for reducing the communication cost of array redistribution is presented. Experimental results on the Cray T3D to evaluate the multi-phase approach are provided.

Cited By

View all

Yu C(2007)On the complexity of the max-edge-coloring problem with its variantsProceedings of the First international conference on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies10.5555/2399256.2399288(350-361)Online publication date: 7-Apr-2007
https://dl.acm.org/doi/10.5555/2399256.2399288
Chen SHsu C(2007)ISOProceedings of the 9th international conference on Parallel Computing Technologies10.5555/2392094.2392149(507-515)Online publication date: 3-Sep-2007
https://dl.acm.org/doi/10.5555/2392094.2392149
Hsu CChen MYang CLi K(2006)Optimizing Communications of Dynamic Data Redistribution on Symmetrical Matrices in Parallelizing CompilersIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2006.16217:11(1226-1241)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TPDS.2006.162
Show More Cited By

Recommendations

Scheduling GEN_BLOCK Array Redistribution

This article is devoted to the redistribution of arrays that are distributed in a GEN_BLOCK fashion over a processor grid. While GEN_BLOCK redistribution is essential for load balancing, prior research about redistribution has been focused on block-...
Efficient Methods for Multi-Dimensional Array Redistribution

In many scientific applications, array redistribution is usually required to enhance data locality and reduce remote memory access on distributed memory multicomputers. Since the redistribution is performed at run-time, there is a performance tradeoff ...
Tools-supported HPF and MPI parallelization of the NAS parallel benchmarks
FRONTIERS '96: Proceedings of the 6th Symposium on the Frontiers of Massively Parallel Computation

High Performance Fortran (HPF) compilers and communication libraries with the standardized Message Passing Interface (MPI) are becoming widely available, easing the development of portable parallel applications. The Annai tool environment supports ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

IPPS '95: Proceedings of the 9th International Symposium on Parallel Processing

April 1995

661 pages

ISBN:0818670746

Publisher

IEEE Computer Society

United States

Publication History

Published: 25 April 1995

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yu C(2007)On the complexity of the max-edge-coloring problem with its variantsProceedings of the First international conference on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies10.5555/2399256.2399288(350-361)Online publication date: 7-Apr-2007
https://dl.acm.org/doi/10.5555/2399256.2399288
Chen SHsu C(2007)ISOProceedings of the 9th international conference on Parallel Computing Technologies10.5555/2392094.2392149(507-515)Online publication date: 3-Sep-2007
https://dl.acm.org/doi/10.5555/2392094.2392149
Hsu CChen MYang CLi K(2006)Optimizing Communications of Dynamic Data Redistribution on Symmetrical Matrices in Parallelizing CompilersIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2006.16217:11(1226-1241)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TPDS.2006.162
Hsu CLan CChen S(2006)Optimizing scheduling stability for runtime data alignmentProceedings of the 2006 international conference on Emerging Directions in Embedded and Ubiquitous Computing10.1007/11807964_83(825-835)Online publication date: 1-Aug-2006
https://dl.acm.org/doi/10.1007/11807964_83
Yu CHsu CYu KLiang CChen C(2005)Irregular redistribution scheduling by partitioning messagesProceedings of the 10th Asia-Pacific conference on Advances in Computer Systems Architecture10.1007/11572961_24(295-309)Online publication date: 24-Oct-2005
https://dl.acm.org/doi/10.1007/11572961_24
Chen SHsu CLan CYang CLi K(2005)Efficient communication scheduling methods for irregular data redistribution in parallelizing compilersProceedings of the 8th international conference on Parallel Computing Technologies10.1007/11535294_19(216-225)Online publication date: 5-Sep-2005
https://dl.acm.org/doi/10.1007/11535294_19
Hsu CYu K(2004)A Compressed Diagonals Remapping Technique for Dynamic Data Redistribution on Banded Sparse MatrixThe Journal of Supercomputing10.1023/B:SUPE.0000026846.74050.1829:2(125-143)Online publication date: 1-Aug-2004
https://dl.acm.org/doi/10.1023/B%3ASUPE.0000026846.74050.18
Hsu CYu KChen CYu CLian C(2004)Optimal processor mapping scheme for efficient communication of data realignmentProceedings of the Second international conference on Parallel and Distributed Processing and Applications10.1007/978-3-540-30566-8_33(268-273)Online publication date: 13-Dec-2004
https://dl.acm.org/doi/10.1007/978-3-540-30566-8_33
Hsu CYu K(2003)A compressed diagonals remapping technique for dynamic data redistribution on banded sparse matrixProceedings of the 2003 international conference on Parallel and distributed processing and applications10.5555/1761566.1761577(53-64)Online publication date: 2-Jul-2003
https://dl.acm.org/doi/10.5555/1761566.1761577
Knoop JMehofer E(2002)Distribution Assignment PlacementIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2002.101141613:6(628-647)Online publication date: 1-Jun-2002
https://dl.acm.org/doi/10.1109/TPDS.2002.1011416
Show More Cited By

Abstract

Cited By

Recommendations

Scheduling GEN_BLOCK Array Redistribution

Efficient Methods for Multi-Dimensional Array Redistribution

Tools-supported HPF and MPI parallelization of the NAS parallel benchmarks

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations