Collective operations for wide-area message-passing systems using adaptive spanning trees. (21st October 2008)

• Record Type: Journal Article
• Authors: Saito, Hideo; Taura, Kenjiro; Chikayama, Takashi
• Is Part Of: International journal of high performance computing and networking. Volume 5:Number 3(2008)
• Page Start: 179
• Page End: 188
• Publication Date: 2008-10-21
• Subjects: wide-area networks -- WANs -- message passing -- collective operations -- broadcast -- reduction -- adaptive spanning trees -- latency; High performance computing -- Periodicals; Computer networks -- Periodicals; High performance computing; Periodicals; 004.05
• Languages: English
• ISSNs: 1740-0562

Abstract

We propose a method for wide-area message-passing systems to perform broadcasts and reductions efficiently using latency and bandwidth-aware spanning trees constructed at run-time. These trees are updated when processes join or leave a computation, allowing effective execution to continue. We have implemented our proposal on the Phoenix Message-Passing Library and performed experiments using 160 processors distributed across four clusters. Compared to a static Grid-aware implementation, the latency of our broadcast was within a factor of two, and the bandwidth was 82%. When some processes joined or left a computation, our broadcast temporarily performed poorly, but completed successfully even during that time.