TY - GEN
T1 - An efficient algorithm for computing communication sets for data parallel programs with block-cyclic distribution
AU - Hwang, Gwan Hwan
N1 - Publisher Copyright:
© 2002 IEEE.
PY - 2002
Y1 - 2002
N2 - We present an algorithm for computing the communication sets in array section movements with block-cyclic (cyclic(k) in HPF) distribution. Our framework can handle multi-level alignments, multi-dimensional arrays, array intrinsic functions, affine indices and axis exchanges in the array subscript. Instead of employing the linear diophantine equation solver, a new algorithm which does not rely on the linear diophantine equation solver to calculate communication sets is proposed We use formal proof and experimental results to show that it is more efficient than previous solution to the same problem. Another important contribution of the paper is that we prove that the compiler is able to compute efficiently the communication sets of block-cyclic distribution as long as the block sizes of the arrays are set to be identical or the lowest common multiple (LCM) of block sizes is not a huge integer We demonstrate it by thorough complexity analyses and extensive experimental results.
AB - We present an algorithm for computing the communication sets in array section movements with block-cyclic (cyclic(k) in HPF) distribution. Our framework can handle multi-level alignments, multi-dimensional arrays, array intrinsic functions, affine indices and axis exchanges in the array subscript. Instead of employing the linear diophantine equation solver, a new algorithm which does not rely on the linear diophantine equation solver to calculate communication sets is proposed We use formal proof and experimental results to show that it is more efficient than previous solution to the same problem. Another important contribution of the paper is that we prove that the compiler is able to compute efficiently the communication sets of block-cyclic distribution as long as the block sizes of the arrays are set to be identical or the lowest common multiple (LCM) of block sizes is not a huge integer We demonstrate it by thorough complexity analyses and extensive experimental results.
KW - Block-Cyclic Distributions
KW - Data Parallel Programs
KW - Distributed Memory Machines
KW - HPF Compiler
KW - Parallelizing Compiler
UR - http://www.scopus.com/inward/record.url?scp=84954518547&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84954518547&partnerID=8YFLogxK
U2 - 10.1109/ICPPW.2002.1039785
DO - 10.1109/ICPPW.2002.1039785
M3 - Conference contribution
AN - SCOPUS:84954518547
T3 - Proceedings of the International Conference on Parallel Processing Workshops
SP - 623
EP - 631
BT - Proceedings - International Conference on Parallel Processing Workshops, ICPPW 2002
A2 - Olariu, Stephan
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - International Conference on Parallel Processing Workshops, ICPPW 2002
Y2 - 18 August 2002 through 21 August 2002
ER -