A Two-Opt Collective-Communication Method for Low-Latency Random Network Topologies

Abstract

Random network topologies have been proposed as low-latency network for parallel-computing systems. Although their unicast routing algorithms have been well researched, collective communication methods consist of a large number of unicasts are not well optimized for random network topologies. In this context, we apply a two-opt method to collective communication on random network topologies. It attempts to minimize the average shortest-path length (ASPL) of unicasts that form a target collective communication. Simulation results interestingly show that our collective communication using the two-opt operation outperforms by 13% in terms of network latency the existing topology-agnostic collective communications that attempt to minimize the number of network contentions and those used in MPI implementations, respectively.