Exploiting hierarchy in parallel computer networks to optimize collective operation performance

The eÆcient implementation of collective commu-nication operations has received much attention. Ini-tial eorts modeled network communication and pro-duced \optimal " trees based on those models. How-ever, the models used by these initial eorts assumed equal point-to-point latencies between any two pro-cesses. This assumption is violated in heterogeneous systems such as clusters of SMPs and wide-area \com-putational grids", and as a result, collective operations that utilize the trees generated by these models perform suboptimally. In response, more recent work has fo-cused on creating topology-aware trees for collective operations that minimize communication across slower channels (e.g., a wide-area network). While these ef-forts have signicant 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 trees we take advantage of communication cost dierences at every level in the network. We used this strategy to imple-ment topology-aware versions of several MPI collective operations in MPICH-G, the Globus-enabled version of the popular MPICH implementation of the MPI stan-dard. Using information about topology discovered by Globus, we construct these topology-aware trees auto-matically during execution, thus freeing the MPI ap-plication programmer from having to write special les or functions to describe the topology to the MPICH li-brary. We present results demonstrating the advan-tages of our multilevel approach by comparing it to the default (topology-unaware) implementation provided by MPICH and a topology-aware two-layer implementa-tion. 1