QVal: A Novel Routing Algorithm for Dragonfly Networks

Dragonfly is becoming one of the networks of choice for high-performance computer systems as it offers a sweet spot in terms of cost, simplicity, performance, fault-tolerance and power. In a Dragonfly topology, compute nodes are connected to routers forming fully-connected groups, which are then connected to every other group. This provides very high connectivity with very low diameter which are desired characteristics of high performance interconnection networks. In this work, we propose Quick Valiant, a new routing algorithms for dragonfly networks which leverages Valiant routing with novel proxy selection criteria which reduce the utilization of network resources and eases congestion under pathological loads. These criteria restrict the possible proxies to these that are adjacent to either the local or the remote router, codenamed QVL and QVR, respectively. We compare our proposals with canonical routing functions and observe reductions of average path length of up to 27% and throughput improvements of up to 46% when compared with Valiant routing. Out of these criteria, restricting to local proxies only, QVL, obtains the best results in all scenarios.