Shortest paths in Dragonfly systems

Written with Ryland Curtsinger (Knox `19).
Proceedings of the 5th IEEE International Workshop of High-Performance Interconnection Networks in the Exascale and Big-Data Era (HiPINEB), 2019.

Materials related to this paper:

Preprint version as a pdf.
©2019 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

Abstract:

Dragonfly is a topology for high-performance computer systems designed to exploit technology trends and meet challenging system constraints, particularly on power. In a Dragonfly system, compute nodes are attached to switches, the switches are organized into groups, and the network is organized as a two-level clique, with an edge between every switch in a group and an edge between every pair of groups. This means that every pair of switches is separated by at most three hops, one within a source group, one from the source group to the destination group, and one within the destination group. Routing using paths of this form is typically called "minimal routing". In this paper, we show that the resulting paths are not always the shortest possible. We then propose a new class of paths that can be used without additional networking hardware and count its members that are shorter than or of equal length to these "minimal paths".