Full Bandwidth Broadcast, Reduction and Scan with Only Two Trees

Event Sponsor: 
Mathematics and Computer Science Division Seminar
Start Date: 
Mar 14 2008 (All day)
Building/Room: 
Building 221 Conference Room A216
Location: 
Argonne National Laboratory
Speaker(s): 
Jesper Larsson Traff
Speaker(s) Title: 
Chief Researcher, NEC Laboratories Europe
Host: 
Rajeev Thakur

We present a new, simple algorithmic idea for exploiting the capability for
bidirectional communication present in many modern interconnects for the
collective MPI operations broadcast, reduction and scan. Our algorithms
achieve up to twice the bandwidth of most previous and commonly used
algorithms. In particular, our algorithms for reduction and scan are the
currently best known. Experiments on clusters with Myrinet and InfiniBand
interconnects show significant reductions in running time for broadcast and
reduction, for reduction even close to the best possible factor of two.

Miscellaneous Information: