PaperlayerView exact revision on arXiv

Source-linked AI summary

Slim Fly: A Cost Effective Low-Diameter Network Topology

Maciej Besta, Torsten Hoefler

arXiv:1912.08968v2cs.NI

TL;DR

Large-scale HPC and datacenter networks require high bandwidth, low latency, resilience, and efficient resource use. The paper designs Slim Fly using near-Moore-bound graphs and evaluates its routing, topology, and physical implementation. It reports lower cost and power than comparable Dragonfly networks while retaining low latency, full bandwidth, and resilience.

  • Problem

    HPC and datacenter networks must provide high bandwidth, low latency, resilience, and cost and power efficiency as network scale and per-node performance increase.

  • Method

    The paper constructs Slim Fly from graphs approaching the Moore Bound, evaluates deadlock-free routing and competing topologies, and develops layouts plus cost and energy models.

  • Results

    Slim Fly provides low-latency, full-bandwidth, resilient networks at lower cost, including a reported 25% cost and power benefit over Dragonfly.

  • Takeaways & Limitations

    Slim Fly supports cost-efficient large datacenter and HPC architectures using fewer network resources while maintaining high bandwidth and resilience.

Abstract

from arXiv · show

We introduce a high-performance cost-effective network topology called Slim Fly that approaches the theoretically optimal network diameter. Slim Fly is based on graphs that approximate the solution to the degree-diameter problem. We analyze Slim Fly and compare it to both traditional and state-of-the-art networks. Our analysis shows that Slim Fly has significant advantages over other topologies in latency, bandwidth, resiliency, cost, and power consumption. Finally, we propose deadlock-free routing schemes and physical layouts for large computing centers as well as a detailed cost and power model. Slim Fly enables constructing cost effective and highly resilient datacenter and HPC networks that offer low latency and high bandwidth under different HPC workloads such as stencil or graph computations.

I. INTRODUCTION

Large-scale HPC and datacenter networks must balance bandwidth, latency, resilience, cost, and power. Slim Fly targets this balance by reducing diameter toward the degree-diameter optimum while maintaining high bandwidth.

  • Motivation: Networks are increasingly important in large-scale computing systems as per-node performance and memory bandwidth grow.Tens of thousands of nodes are deployed in warehouse-sized HPC and datacenter systems.
  • Motivation: High bandwidth, low latency, resilience to link failures, and cost and power efficiency are key topology requirements.Networks can represent up to 33% of system cost and 50% of overall system energy consumption.
  • Slim Fly approach: Slim Fly aims to lower latency, cost, and energy by reducing packet traversals, router-buffer contention, and the required number of routers and connections.The paper links shorter paths to fewer traversed SerDes, sinks, and router buffers while maintaining high bisection bandwidth.
  • Slim Fly approach: Slim Fly reduces network diameter toward the lowest attainable value for a given router radix while maintaining high bandwidth and resiliency.The design is based on graphs related to the degree-diameter problem and compares average hops under uniform traffic with minimal routing.
  • Scale and construction: Slim Fly supports full-bandwidth networks with over 100K endpoints at diameter two and networks with up to tens of millions of endpoints at diameter three.The constructions use readily available high-radix routers, including 64-port and 108-port examples.
  • Contributions: The work designs Slim Fly topologies, evaluates deadlock-free minimal and adaptive routing, and provides practical topology resources for construction and reproducibility.The authors also provide a physical layout, cost and energy model, and simulation code.

B. Diameter-2 Networks

Slim Fly’s diameter-2 construction uses MMS graphs, which are close to the Moore Bound and provide a symmetric algebraic basis for connecting routers. The construction proceeds through a prime-power ring, generator sets, and equations defining intra- and inter-subgraph links.

  • B. Diameter-2 Networks: MMS graphs are close-to-optimal diameter-2 graphs used as the basis for the SF MMS topology.The paper notes that universal optimal constructions are unavailable for most degree-diameter settings, motivating MMS graphs as a near-optimal family.
  • B. Diameter-2 Networks: The construction selects a prime power q satisfying q = 4w + δ, then generates an MMS graph with radix k′ = 3q−δ2 and Nr = 2q2 routers.
  • 1) Connecting Routers:: The router set is {0, 1} × Zq × Zq, with two router subgraphs connected through algebraic rules.Routers in the two subgraphs are represented as (0, x, y) and (1, m, c).
  • 1) Connecting Routers:: Within each subgraph, routers connect when coordinate differences belong to generator sets X or X′, while cross-subgraph links satisfy y = mx + c.
  • 1) Connecting Routers:: The MMS structure is highly symmetric, consisting of identical router subgroups in two subgraphs, a property later used for physical network layouts.
  • 1) Connecting Routers:: For q = 5, the construction uses ξ = 2, X = {1, 4}, and X′ = {2, 3}, then applies the three connection rules to form the Hoffman–Singleton example.

2) Attaching Endpoints:

SF MMS attaches endpoints to routers by choosing concentration to balance endpoint injection with network-channel load. The resulting design dedicates roughly two-thirds of router ports to the network and one-third to endpoints while preserving full global bandwidth.

  • 2) Attaching Endpoints:: A balanced network lets each endpoint inject at full capacity, requiring pNr = [(2Nr − k′ −2) · p2]/k′.
  • 2) Attaching Endpoints:: Each endpoint injects toward approximately N = pNr destinations through its single uplink.
  • 2) Attaching Endpoints:: The selected concentration is p ≈⌈k′/2⌉, so approximately 67% of router ports connect to the network and 33% connect to endpoints.This concentration is chosen to achieve full global bandwidth.
  • 2) Attaching Endpoints:: SF MMS is very close to the diameter-2 Moore Bound: with k′ = 96, it has 8,192 routers versus an upper bound of 9,217, only 12% worse.
  • 2) Attaching Endpoints:: For diameter three, Delorme and BDF graphs achieve 68% and 30% of the Moore Bound, respectively, compared with Dragonfly’s 14% at k′ = 96.

1) Constructing BDF graphs:

The paper constructs diameter-3 graphs from projective-plane graphs and a graph product, then compares their router counts with other diameter-3 topologies. These constructions approach the Moore Bound, although the paper focuses primarily on MMS graphs for scalability.

  • 1) Constructing BDF graphs:: The ∗product combines graphs G1 and G2 into a Cartesian-product graph whose edges encode either G2 connections or mapped G1 arcs.
  • 1) Constructing BDF graphs:: For an odd prime power u, Pu is built from projective-plane points and has diameter 2, degree u + 1, and u2 + u + 1 vertices.
  • 1) Constructing BDF graphs:: Combining Pu with a graph satisfying property P∗ produces a graph with diameter 3 and degree k′.
  • 1) Constructing BDF graphs:: The paper focuses on MMS graphs because their scalability suffices for most large-scale networks with more than 100K endpoints.Diameter-three constructions show lower but similar cost and performance benefits because they approach the optimal structure.

A. Network Diameter

Slim Fly achieves diameter two, the lowest among the compared topologies, while providing higher bisection bandwidth than several alternatives.

  • A. Network Diameter: Slim Fly has diameter 2, the lowest diameter among all compared topologies.Any two endpoints are separated by at most two hops.
  • A. Network Diameter: Slim Fly’s average distance is the lowest across all analyzed network sizes and approaches the network diameter asymptotically.
  • A. Network Diameter: Slim Fly offers higher bisection bandwidth than Dragonfly, FBF-3, T3D, and T5D.For SF and DLN, bisection bandwidth is approximated using the METIS partitioner.

D. Resiliency

Slim Fly is highly resilient to link failures, combining strong path diversity with better diameter-failure tolerance than Dragonfly in the reported comparisons.

  • D. Resiliency: Slim Fly is among the three most resilient topologies under random link removals before disconnection.The comparison uses cable failures in 5% increments with samples targeting a 95% confidence interval of width 2.
  • D. Resiliency: Slim Fly’s 2q inter-group links provide path diversity that dampens the effects of global link failures.
  • D. Resiliency: 40% link failures can be tolerated before Slim Fly’s diameter grows beyond four.This is slightly below DLN’s 60% tolerance and above Dragonfly’s 25% tolerance.
  • D. Resiliency: 55% link failures can be tolerated by Slim Fly before its average path length increases by more than one hop.The comparison assumes that an increase of one hop in average distance is tolerable.

B. Valiant Random Routing

The paper evaluates minimal, Valiant, and adaptive routing for Slim Fly, including deadlock-avoidance mechanisms, across traffic scenarios representing major HPC workloads.

  • B. Valiant Random Routing: Valiant routing load-balances adversarial traffic by routing packets through a randomly selected intermediate router.The resulting paths contain 2, 3, or 4 hops depending on connectivity.
  • B. Valiant Random Routing: UGAL selects between a minimal path and a Valiant-generated path using hop distance and queue information.UGAL-G uses global queue sizes, whereas UGAL-L uses local output queues.
  • B. Valiant Random Routing: Selecting 4 random paths empirically gives lower overall latency for UGAL-L, while UGAL-G also performs best with 4 paths.
  • B. Valiant Random Routing: Slim Fly’s minimal routing uses two virtual channels for two-hop paths, and adaptive routing uses four virtual channels for paths with up to four turns.OFED DFSSSP consistently required three VCs for all evaluated Slim Fly networks.
  • B. Valiant Random Routing: Under random traffic, Slim Fly has the lowest latency, while UGAL-G and minimal routing achieve the best performance.UGAL-L saturates at 80% injection rate and converges toward full bandwidth at high load.

B. Bit Permutation and Shift Traffic for Collective Operations

Slim Fly is evaluated on bit-permutation, shift, and adversarial traffic, where adaptive routing improves load distribution and oversubscription allows additional endpoints while retaining substantial bandwidth.

  • B. Bit Permutation and Shift Traffic for Collective Operations: The bit-permutation evaluation activates 8,192 endpoints and tests shuffle, bit-reversal, and bit-complement traffic patterns.The source and destination addresses are represented with bit-level transformations.
  • B. Bit Permutation and Shift Traffic for Collective Operations: Under shift and permutation traffic, Slim Fly offers slightly higher bandwidth and lower latency than Dragonfly.Fat tree has higher bandwidth than UGAL-L and is only slightly better than UGAL-G in the reported comparison.
  • B. Bit Permutation and Shift Traffic for Collective Operations: For adversarial traffic, Valiant and UGAL-L disperse traffic across multiple channels, supporting up to 40% and 45% offered load, respectively.Minimal routing is limited to 1/(p+1) throughput in the stated worst case.
  • B. Bit Permutation and Shift Traffic for Collective Operations: Oversubscribing Slim Fly increases endpoint capacity and port-count flexibility but prevents full global bandwidth.
  • B. Bit Permutation and Shift Traffic for Collective Operations: The full-bandwidth Slim Fly configuration accepts up to 87.5% of random-uniform offered traffic, while concentrations 16 and 18 accept up to 80% and 75%.These oversubscribed configurations connect 11,552 to 15,162 endpoints and illustrate the flexibility to add endpoints while preserving high bandwidth and low latency.

VI. COST AND POWER COMPARISON

Slim Fly is arranged as a modular, rack-based network derived from MMS graphs, with physical layouts designed to reduce cabling costs while preserving structured connectivity. Compared with Dragonfly, it uses fewer local cables, more inter-group connections, and higher endpoint concentration.

  • Physical layout: Slim Fly partitions MMS graphs into modular router groups that are rearranged and merged into racks for datacenter deployment.The layout places racks in a square or near-square arrangement to reduce global cable lengths.
  • Physical layout: Each rack has the same intra-group cable pattern, and the datacenter can be viewed as a fully connected graph of identical racks.Every pair of racks is connected by 2q interconnections.
  • Example configuration: For q = 19, an example network has 10,830 endpoints, 19 racks, 38 routers per rack, 570 endpoints per rack, and 38 global channels to every other group.An alternative layout uses 39 racks with 19 routers and 285 endpoints per rack.
  • Comparison with Dragonfly: Compared with Dragonfly, Slim Fly groups use approximately 50% fewer local cables and connect groups with 2q cables rather than one inter-group cable.These structural differences are presented as part of the explanation for Slim Fly’s lower diameter and higher resiliency.
  • Comparison with Dragonfly: Balanced Slim Fly has approximately 33% router radix concentration versus approximately 25% for same-size balanced Dragonfly, yielding higher endpoint density and approximately 25% fewer routers or racks.The comparison concerns balanced networks of the same size.

B. Cost Model

The cost model estimates router and cable expenses using rack, link-type, distance, bandwidth, and radix assumptions. It then applies these estimates to comparable configurations of tori, hypercubes, fat trees, flattened butterflies, Dragonflies, and random networks.

  • Model assumptions: The model includes router and interconnection-cable costs, which are assumed to constitute most of the overall network cost.Routers and endpoints are grouped in 1 × 1 × 2 meter racks; local links are electrical and global channels are optical.
  • Cable model: Electrical and optical cable costs are modeled as f(x) = 0.4079x + 0.5771 and f(x) = 0.0919x + 2.7452 [$ / Gb/s], respectively.The functions are obtained by linear regression on pricing data for Mellanox InfiniBand FDR10 40Gb/s QSFP cables.
  • Router model: Router cost is modeled as a linear function of radix, f(k) = 350.4k − 892.3 [$].The model assumes router-chip cost is relatively constant while SerDes are a major cost component.
  • Comparison methodology: Flattened butterfly, Dragonfly, and random networks are modeled through their group sizes, local connectivity, inter-group links, and cable placement.Dragonfly groups form a clique, whereas random-network cables are placed randomly between same-sized groups.
  • Comparison methodology: The comparison evaluates low-radix tori, hypercubes, long-hop hypercubes, and fat trees using topology-specific assumptions about geometry, cable type, and connectivity.Tori are modeled as folded cuboids or hypercuboids, while other topologies combine electrical intra-rack and optical inter-rack links as specified.

4) Discussion of the Results:

The cost and power evaluation finds Slim Fly substantially cheaper and more energy-efficient than comparable high-radix networks, while also supporting resilience and flexible construction. Its main engineering boundary is that simple constructions do not support arbitrary router radices.

  • Cost results: Slim Fly is significantly more cost-effective than low-radix networks because it uses fewer routers and cables.Against Long Hops, cost results vary by only approximately 1% because those networks have excessive routers and endpoints and are identical in size to Slim Fly.
  • Cost results: Approximately 25% more cost-effective than Dragonfly, and almost 30%, 40%, and 50% less expensive than FBF-3, DLN, and FT-3, respectively.For k = 43 and N ≈ 10,000, Dragonfly uses 990 routers while Slim Fly uses 722.
  • Power results: Over 25% more energy-efficient than Dragonfly, FBF-3, and DLN.Lower power consumption is attributed to Slim Fly’s smaller number of routers and SerDes.
  • Construction flexibility: Simple Slim Fly constructions cannot use arbitrary router radices because they are based on powers of prime q.The paper discusses solutions for matching existing routers with different radices.
  • Construction flexibility: For network sizes up to 20,000, Slim Fly offers 11 balanced full-global-bandwidth variants, compared with 8 for Dragonfly.Several variants can be constructed with readily available Mellanox routers having 18, 36, or 108 ports.
  • Construction flexibility: Using random channels to fill unused ports could improve latency and bandwidth, but the analysis of this option is left for future research.The example considers a k = 43, N = 10830 network built with 48-port routers.

B. Constructing Dragonfly-type Networks

Slim Fly combines Moore-Bound-oriented construction, modular deployment, and routing strategies to target low-latency, full-bandwidth, resilient networks at lower cost and power. The discussion emphasizes resilience, incremental expansion, and possible integration with Dragonfly designs.

  • Extensions: Slim Fly could implement higher-radix logical routers within Dragonfly or connect multiple Dragonfly groups to reduce costs.The paper also suggests extending Moore-Bound-based optimization to higher-diameter networks supporting millions of endpoints.
  • Scalability: Slim Fly can handle incremental endpoint growth because relatively small oversubscription of p has negligible performance impact.A 10,830-endpoint network can be extended by approximately 1,500 endpoints before performance drops by more than 10%.
  • Topology construction: Slim Fly is proposed as a new topology class for large datacenter and HPC architectures, using Moore-Bound optimization and MMS graphs approaching the D = 2 bound.The design targets fewer expensive network resources while maintaining high bandwidth.
  • Cost and power: Slim Fly achieves a 25% cost and power benefit over Dragonfly under current technology constraints.The paper expects cheaper fiber optics and higher-radix routers to increase this relative benefit.
  • Routing and deployment: Slim Fly’s routing strategies work well under bit-permutation and worst-case traffic and asymptotically achieve high bandwidth for random traffic.Its modular structure also makes deployment easier than for random networks.
  • Resilience: Theoretical analyses show greater link-failure resilience than Dragonfly, approaching highly resilient random topologies.The paper attributes this result to the expander-graph properties of Slim Fly’s underlying structure.
Loading 1912.08968v2…