TY - GEN
T1 - Faster topology-aware collective algorithms through non-minimal communication
AU - Sack, Paul
AU - Gropp, William
PY - 2012
Y1 - 2012
N2 - Known algorithms for two important collective communication operations, allgather and reduce-scatter, are minimal-communication algorithms; no process sends or receives more than the minimum amount of data. This, combined with the data-ordering semantics of the operations, limits the flexibility and performance of these algorithms. Our novel non-minimal, topology-aware algorithms deliver far better performance with the addition of a very small amount of redundant communication. We develop novel algorithms for Clos networks and single or multi-ported torus networks. Tests on a 32k-node BlueGene/P result in allgather speedups of up to 6x and reduce-scatter speedups of over 11x compared to the native IBM algorithm. Broadcast, reduce, and allreduce can be composed of allgather or reduce-scatter and other collective operations; our techniques also improve the performance of these algorithms.
AB - Known algorithms for two important collective communication operations, allgather and reduce-scatter, are minimal-communication algorithms; no process sends or receives more than the minimum amount of data. This, combined with the data-ordering semantics of the operations, limits the flexibility and performance of these algorithms. Our novel non-minimal, topology-aware algorithms deliver far better performance with the addition of a very small amount of redundant communication. We develop novel algorithms for Clos networks and single or multi-ported torus networks. Tests on a 32k-node BlueGene/P result in allgather speedups of up to 6x and reduce-scatter speedups of over 11x compared to the native IBM algorithm. Broadcast, reduce, and allreduce can be composed of allgather or reduce-scatter and other collective operations; our techniques also improve the performance of these algorithms.
KW - Collective-communication algorithms
UR - http://www.scopus.com/inward/record.url?scp=84858436109&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84858436109&partnerID=8YFLogxK
U2 - 10.1145/2145816.2145823
DO - 10.1145/2145816.2145823
M3 - Conference contribution
AN - SCOPUS:84858436109
SN - 9781450311601
T3 - Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP
SP - 45
EP - 54
BT - PPoPP'12 - Proceedings of the 2012 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
T2 - 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'12
Y2 - 25 February 2012 through 29 February 2012
ER -