Two-tree collective communication in distributed heterogeneous systems

Abstract

A computational grid, or simply Grid, is a new way of cost-effective and high performance parallel computing. It can solve large problems by combing computing resources across the network but traditional components for parallel computing need to be midified. This thesis studies the collective communication under the Grid environment, which can be represented by the combination of heterogeneous networks. To generate a schedule for collective communication, scheduling algorithms use network information, but network information service in the grid provides erratic information. The proposed approach, called $\emph{TTCC(Two-Tree Collective Communication)}$, generated efficient schedule which can tolerate this unfavorable condition. This thesis also studies the collective communication primitives of modified MPI under the Grid environment, such as multilevel broadcast, and identifies the increased overhead of multilevel broadcast. The second proposed approach, called $\emph{SRT(Send and Receive Table)}$, alleviate the overhead of multilevel broadcast but it does not increase the network cost since the proposed method has the same network access pattern as the conventional method. Benefit of the proposed methods are quantified via simulations and experiments on a cluster system.