Efficient collective communication in distributed heterogeneous systems

Publisher Website
Google Scholar
Abstract
The Information Power Grid (IPG) is emerging as an in- frastructure that will enable distributed applications - s uch as video conferencing and distributed interactive simula- tion - to seamlessly integrate collections of heterogeneou s workstations, multiprocessors, and mobile nodes, over het - erogeneous wide-area networks. This paper introduces a framework for developing efficient collective communica- tion schedules in such systems. Our framework consists of analytical models of the heterogeneous system, scheduling algorithms for the collective communication pattern, and performance evaluation mechanisms. We show that previ- ous models, which considered node heterogeneity but ig- nored network heterogeneity, can lead to solutions which are worse than the optimal by an unbounded factor. We then introduce an enhanced communication model, and de- velop three heuristic algorithms for the broadcast and mul- ticast patterns. The completion time of the schedule is cho- sen as the performance metric. The heuristic algorithms are FEF (Fastest Edge First), ECEF (Earliest Completing Edge First), and ECEF with look-ahead. For small system sizes, we find the optimal solution using exhaustive search. Our simulation experiments indicate that the performance of ou r heuristic algorithms is close to optimal. For performance evaluation of larger systems, we have also developed a sim- ple lower bound on the completion time. Our heuristic algo- rithms achieve significant performance improvements over previous approaches.

This publication has 16 references indexed in Scilit: