Title :
A generalized basic cycle calculation method for efficient array redistribution
Author :
Chung, Yeh-Ching ; Bai, Sheng-Wen ; Hsu, Ching-Hsien ; Yang, Chu-Sing
Author_Institution :
Dept. of Inf. Eng., Feng Chia Univ., Taichung, Taiwan
Abstract :
In many scientific applications, dynamic array redistribution is usually required to enhance the performance of an algorithm. 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. 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 multi dimensional array redistributions is also presented
Keywords :
distributed algorithms; parallel machines; parallel programming; BLOCK-CYCLIC; GBCC method; IBM SP2 parallel machine; PITFALLS method; ScaLAPACK method; array elements; cost models; destination distribution; dynamic array redistribution; generalized basic cycle calculation method; local array; multi dimensional array redistributions; packing/unpacking pattern tables; scientific applications; source distribution; source/destination processor/data sets; test samples; Costs; Parallel machines; Testing;
Conference_Titel :
Parallel and Distributed Systems, 1998. Proceedings. 1998 International Conference on
Conference_Location :
Tainan
Print_ISBN :
0-8186-8603-0
DOI :
10.1109/ICPADS.1998.741147