DocumentCode :
2435065
Title :
Efficient algorithms for multi-dimensional block-cyclic redistribution of arrays
Author :
Lim, Young Won ; Park, Neungsoo ; Prasanna, Viktor K.
Author_Institution :
Dept. of Electr. Eng. Syst., Univ. of Southern California, Los Angeles, CA, USA
fYear :
1997
fDate :
11-15 Aug 1997
Firstpage :
234
Lastpage :
241
Abstract :
We present a uniform framework for a classical problem, redistribution of a multi-dimensional array. Using a generalized circulant matrix formalism, we derive efficient direct, indirect and hybrid contention-free communication schedules. Our indirect schedule reduces the number of communication steps significantly compared with the previous approaches. Our approach exploits the regularity of the block-cyclic redistribution to minimize the index computation overheads. For the case of 2-d redistribution, when the block size increases by factors of K1 and K2 along each dimension and the process topology remains fixed, our indirect schedule performs the redistribution in O(log(K1K2)) communication steps. For the case of fixed block size and the processor topology is transposed, our indirect schedule results in O(log(L/G)) communication steps. Implementations of our algorithms on the IBM SP-2 show superior performance over previous approaches
Keywords :
block codes; cyclic codes; parallel algorithms; performance evaluation; 2-d redistribution; IBM SP-2; block-cyclic redistribution; communication steps; contention-free communication schedules; fixed block size; generalized circulant matrix formalism; index computation overheads; multi-dimensional block-cyclic redistribution; processor topology; Application software; Costs; Distributed computing; Phased arrays; Processor scheduling; Program processors; Programming profession; Radar signal processing; Signal processing algorithms; Topology;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Processing, 1997., Proceedings of the 1997 International Conference on
Conference_Location :
Bloomington, IL
ISSN :
0190-3918
Print_ISBN :
0-8186-8108-X
Type :
conf
DOI :
10.1109/ICPP.1997.622650
Filename :
622650
Link To Document :
بازگشت