Bandwidthefficient Collective Communication for Clustered Wide Area Systems

Metacomputing infrastructures couple multiple clusters (or MPPs) via wide-area networks. A major problem in pro-gramming parallel applications for such platforms is their hierarchical network structure: latency and bandwidth of WANs often are orders of magnitude worse than those of local networks. Our goal is to optimize MPI’s collective operations for such platforms. In this paper, we focus on optimized utilization of the (scarce) wide-area bandwidth. We use two techniques: selecting suitable communication graph shapes, and splitting messages into multiple segments that are sent in parallel over different WAN links. To deter-mine the best graph shape and segment size, we introduce a performance model called parameterized LogP (P-LogP), a hierarchical extension of the LogP model that covers mes-sages of arbitrary length. With P-LogP, the optimal segment size and the best broadcast tree shape can be determined at runtime. (For conciseness, we restrict our discussion to the broadcast operation.) An experimental performance eval-uation shows that the new broadcast has significantly im-proved performance (for large messages) and that there is a close match between the theoretical model and the mea-sured completion times.