A Multilevel Approach to Topology-aware Collective Operations in Computational Grids

The ecient implementation of collective communication operations has received much attention. Initial eorts produced \optimal " trees based on network communi-cation models that assumed equal point-to-point latencies between any two processes. This assumption is violated in most practical settings, however, particularly in heteroge-neous systems such as clusters of SMPs and wide-area \computational Grids, " with the result that collective operations perform suboptimally. In response, more recent work has focused on creating topology-aware trees for collective operations that minimize com-munication across slower channels (e.g., a wide-area network). While these eorts have signi cant communication benets, they all limit their view of the network to only two layers. We present a strategy based upon a multilayer view of the network. By creating multilevel topology-aware trees we take advantage of communication cost dierences at every level in the network. We used this strategy to implement topology-aware versions of several MPI collective operations in MPICH-G2, the Globus Toolkit TM-enabled ver