Network Topology Aware Scheduling of Collective Communications

E. Gabrielyan, R.D. Hersch

ICT03, 10th International Conference on Telecommunications (ICT 2003), February 23-March 1, 2003, Vol. 2, 1051-1058

We propose a method for the optimal scheduling of collective data exchanges relying on the knowledge of the underlying network topology. We introduce the concept of liquid schedules. Liquid schedules ensure the maximal utilization of a network’s bottleneck links and offer an aggregate throughput as high as the flow capacity of a liquid in a network of pipes. The collective communication throughput offered by liquid schedules in highly loaded networks may be several times higher than the throughput of topology-unaware techniques. To create a liquid schedule we need to find the smallest partition of all transfers into subsets of mutually non-congesting transfers. The number of combinations of non-overlapping subsets of mutually non-congesting transfers grows exponentially with the number of transfers. We propose several methods to reduce the search space without affecting the solution space. On a real 32 node computer cluster, the measured throughputs of data exchanges scheduled according to our method are very close to the theoretical liquid throughputs.

Download the full paper: PDF 548 KB