1. Two-tree algorithms for full bandwidth broadcast, reduction and scan
- Author
-
Jesper Larsson Träff, Jochen Speck, and Peter Sanders
- Subjects
Prefix ,Tree traversal ,Binary tree ,Artificial Intelligence ,Computer Networks and Communications ,Hardware and Architecture ,Computer science ,InfiniBand ,Parallel computing ,Computer Graphics and Computer-Aided Design ,Software ,Theoretical Computer Science ,Scheduling (computing) - Abstract
We present a new, simple algorithmic idea for the collective communication operations broadcast, reduction, and scan (prefix sums). The algorithms concurrently communicate over two binary trees which both span the entire network. By careful layout and communication scheduling, each tree communicates as efficiently as a single tree with exclusive use of the network. Our algorithms thus achieve up to twice the bandwidth of most previous algorithms. In particular, our approach beats all previous algorithms for reduction and scan. Experiments on clusters with Myrinet and InfiniBand interconnect show significant reductions in running time for all three operations sometimes even close to the best possible factor of two.
- Published
- 2009