Collective operations for wide-area message-passing systems using adaptive spanning trees. (21st October 2008) - Saito, Hideo; Taura, Kenjiro; Chikayama, Takashi
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.