Network topology aware scheduling of collective communications

A method is proposed for the optimal scheduling of collective data exchanges relying on the knowledge of the underlying network topology. The concept of liquid schedules is introduced. 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 might be several times higher than the throughput of topology-unaware techniques. To create a liquid schedule, it is important 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 transfer grows exponentially with the number of transfers. Several methods are proposed 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