A generalized basic-cycle calculation method for efficient array redistribution
Authors:
- Ching-Hsien HsuCHChing-Hsien Hsu
- Sheng-Wen BaiSBSheng-Wen Bai
- Yeh-Ching ChungYCYeh-Ching Chung
- Chu-Sing YangCYChu-Sing Yang
- 1 January 2000
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 11 (12) , 1201-1216
Abstract
[[abstract]]In many scientific applications, dynamic array redistribution is usually required to enhance the performance of an algorithm. In this paper, we present a generalized basic-cycle calculation (GBCC) method to efficiently perform a BLOCK-CYCLIC(s) over P processors to BLOCK-CYCLIC(t) over Q processors array redistribution. In the GBCC method, a processor first computes the source/destination processor/data sets of array elements in the first generalized basic-cycle of the local array it owns. A generalized basic-cycle is defined as lcm(sP, tQ)/(gcd(s,t) × P) in the source distribution and lcm(sP, tQ)/(gcd(s,t) × Q) in the destination distribution. From the source/destination processor/data sets of array elements in the first generalized basic-cycle, we can construct packing/unpacking pattern tables to minimize the data-movement operations. Since each generalized basic-cycle has the same communication pattern, based on the packing/unpacking pattern tables, a processor can pack/unpack array elements efficiently. To evaluate the performance of the GBCC method, we have implemented this method on an IBM SP2 parallel machine, along with the PITFALLS method and the ScaLAPACK method. The cost models for these three methods are also presented. The experimental results show that the GBCC method outperforms the PITFALLS method and the ScaLAPACK method for all test samples. A brief description of the extension of the GBCC method to multidimensional array redistributions is also presented.[[fileno]]2030220010017[[department]]資訊工程學Keywords
This publication has 21 references indexed in Scilit:
- Runtime array redistribution in HPF programs2002
- Efficient Algorithms for Block-Cyclic Redistribution of ArraysAlgorithmica, 1999
- Fast Runtime Block Cyclic Data Redistribution on MultiprocessorsJournal of Parallel and Distributed Computing, 1997
- Efficient Computation of Address Sequences in Data Parallel Programs Using Closed Forms for Basis VectorsJournal of Parallel and Distributed Computing, 1996
- Optimizations for Efficient Array Redistribution on Distributed Memory MulticomputersJournal of Parallel and Distributed Computing, 1996
- Redistribution of block‐cyclic data distributions using MPIConcurrency: Practice and Experience, 1996
- Efficient algorithms for array redistributionIEEE Transactions on Parallel and Distributed Systems, 1996
- Generating Local Addresses and Communication Sets for Data-Parallel ProgramsJournal of Parallel and Distributed Computing, 1995
- Generating Communication for Array Statements: Design, Implementation, and EvaluationJournal of Parallel and Distributed Computing, 1994
- Computational Frameworks for the Fast Fourier Transform1992