Broadcast scheduling optimization for heterogeneous cluster systems

Networks of workstations (NOWs) offer a cost-effective alternative to massively parallel supercomputers. As commercially available off-the-shelf processors become cheaper and faster, it is now possible to build a PC or workstation cluster that provides high computing power within a limited budget. However, a cluster may consist of different types of processors, and this heterogeneity within a cluster complicates the design of efficient collective communication protocols. This paper shows that a simple heuristic called fastest-node-first (FNF) is very effective in reducing the broadcast time for heterogeneous cluster systems. Despite the fact that the FNF heuristic fails to give the optimal broadcast time for a general heterogeneous network of workstations, we prove that FNF always gives the optimal broadcast time in several special cases of clusters. Based on these special case results, we show that FNF is an approximation algorithm that guarantees a competitive ratio of 2. From these theoretical results we also derive techniques to speed up the branch-and-bound search for the optimal broadcast schedule in heterogeneous NOWs.