Cost-efficient Dragonfly Topology for Large-scale Systems
Venue
Optical Fiber Communication Conference (OFC 2009)
Publication Year
2009
Authors
John Kim, William J. Dally, Steve Scott, Dennis Abts
BibTeX
Abstract
Evolving technology and increasing pin-bandwidth motivate the use of high-radix
routers to reduce the diameter, latency, and cost of interconnection networks. This
migration from low-radix to high-radix routers is demonstrated with the recent
introduction of high-radix routers and they are expected to impact networks used in
large-scale systems such as multicomputers and data centers. As a result, a
scalable and a cost-efficient topology is needed to properly exploit high-radix
routers. High-radix networks require longer cables than their low-radix
counterparts. Because cables dominate network cost, the number of cables, and
particularly the number of long, global cables should be minimized to realize an
efficient network. In this paper, we introduce the dragonfly topology which uses a
group of high-radix routers as a virtual router to increase the effective radix of
the network. With this organization, each minimally routed packet traverses at most
one global channel. By reducing global channels, a dragonfly reduces cost by 20%
compared to a flattened butterfly and by 52% compared to a folded Clos network in
configurations with at least 16K nodes. The paper also introduces two new variants
of global adaptive routing that enable load-balanced routing in the dragonfly. Each
router in a dragonfly must make an adaptive routing decision based on the state of
a global channel connected to a different router. Because of the indirect nature of
this routing decision, conventional adaptive routing algorithms give degraded
performance. We introduce the use of selective virtual-channel discrimination and
the use of credit round-trip latency to both sense and signal channel congestion.
The combination of these two methods gives throughput and latency that approaches
that of an ideal adaptive routing algorithm.
