{'fraction_non_alphanumeric': 0.04947939325386467, 'fraction_numerical': 0.010789176020186201, 'mean_word_length': 4.251218397806884, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 33, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimal Direct-Connect Topologies for Collective Communications

We consider the problem of distilling optimal network topologies for collective communications. We provide an algorithmic framework for constructing direct-connect topologies optimized for the latency-bandwidth tradeoff given a collective communication workload. Our algorithmic framework allows us to start from small base topologies and associated communication schedules and use a set of techniques that can be iteratively applied to derive much larger topologies and associated schedules. Our approach allows us to synthesize many different topologies and schedules for a given cluster size and degree constraint, and then identify the optimal topology for a given workload. We provide an analytical-model-based evaluation of the derived topologies and results on a small-scale optical testbed that uses patch panels for configuring a topology for the duration of an application's execution. We show that the derived topologies and schedules provide significant performance benefits over existing collective communications implementations.


INTRODUCTION
Collective communication operations have received significant attention in both machine learning (ML) and highperformance computing disciplines. These operations involve concurrently aggregating and distributing data collected from processes running on a cluster of interconnected nodes. These primitives are not only frequently used but are often the primary source of communication costs. Indeed recent works suggest that with the explosive growth in the size of deep learning models and improved computational capabilities, the collective communication operations for model parameter synchronization across GPUs have become a major source of overhead in distributed ML training [16,35,39].
One approach to accelerate collective communications has been to employ higher-speed optical circuits by using optical circuit switches to avoid the bottlenecks associated with electrical packet switches. These switches adapt to traffic workloads by dynamically reconfiguring the optical circuits, but the reconfiguration delays could be substantial. This has prompted novel lines of work that reduce the reconfiguration delays [13,34], but at the cost of reduced scalability and higher costs, as well as chaining multiple optical circuits, but with a loss in bandwidth efficiency [25,26].
While switch-centered innovations benefit point-to-point datacenter communications, we can have more effective solutions that focus on accelerating the higher-level abstractions associated with collective communications, such as specific styles of data aggregation and distribution. We intend to configure the network topology to specifically leverage the flexibility associated with these abstractions. In particular, we investigate whether one can design algorithms for collective communications that schedule transmissions over statically configured circuits, thus requiring minimal reconfiguration support from the optical switching substrate. We frame the corresponding research question as follows: Can we algorithmically determine the optimal direct-connect network topologies for collective communications?
Several challenges need to be tackled in addressing this research question. First, collective communications can be both latency and bandwidth sensitive depending on the workload and the performance of the low-level communication primitives. A network topology has to balance the need for minimizing the number of hops associated with performing the collective with any load imbalances incurred on specific network links. Second, we seek to distill the appropriate topology for a given cluster size and degree connectivity. Finding a topology and communications schedule for small low-degree networks is tractable, but at large scale, the combination of size and topological structure as a degree of freedom explodes the search space rendering state-of-the-art techniques ineffective. Finally, integrating with existing endhost interfaces and network stacks, e.g., NCCL [21], present a plethora of implementation challenges to realize this vision.
Our work addresses these issues by developing an algorithmic toolchain for quickly producing optimal topologies and schedules for collective communications for a wide range of inputs and hardware constraints even for large scales. We start with small base graphs that have optimal performance for collective communications; these are either well-known regular graphs, modifications to well-known, or synthetically derived graphs that are obtained as solutions to tractable optimization problems. The communication schedules for these graphs are either constructed directly or synthesized using optimization techniques. We then design different graph expansion techniques to construct larger graphs, with possibly larger degrees, while almost preserving the latency and bandwidth properties of the base graphs. Our technique automatically identifies the appropriate base graph(s) and expansion techniques for a desired operating point, i.e., cluster size, node degree constraint, and collective patterns. We also provide a schedule generation algorithm for large expander graphs that work for arbitrary cluster sizes and degrees.
The computed topologies can be utilized in various network fabrics. Since the network topology remains fixed during the duration of an application runtime, e.g., a training run of a distributed machine learning model, the optical interconnect can tolerate reconfiguration delays that are incurred only during application startup time. We deploy our prototype on an optical patch panel [23,37,40], a mechanical reconfiguration solution that is cheaper and has higher port count than optical circuit switched networks, as we can use circuits that are stable for the duration of an experiment. We show that the derived topologies and schedules provide performance benefits over existing collectives, both on the small testbed and on larger simulations.

PROBLEM STATEMENT AND BACKGROUND 2.1 Collective communication primitives
When multiple nodes collaborate on a task, periodic data exchange is necessary. For instance, in data parallel ML training, a data batch is split among multiple GPUs and model parameters are averaged at the end of each iteration. Such collective communications could involve all or a substantial subset of the nodes. First we define some notation: Assume that we have nodes performing collective communication operations on a vector of data (or model) of size .
The reduce-scatter operation performs a reduction operation and terminates with the reduced data scattered across the nodes. Prior to the operation, each node possesses a vector that can be split into shards as follows, = ( 0 , 1 , . . . , −1 ), where | | = / . The operation reduces and scatters the data such that every node receives only a shard of the reduced data, i.e., node receives . The allgather operation starts with each node having a shard of data and ends with all the nodes having the entire data = ( 0 , 1 , . . . , −1 ). This is akin to broadcast operations, where each node broadcasts its own data.
The allreduce operation is much like the reduce-scatter operation, except that the entire data needs to be available at all the nodes. The operation starts with each node having data ( 0 , 1 , . . . , −1 ) and ends with all the nodes having all the data shards obtained from the corresponding reductions: 0 , 1 , .., −1 , where = , 0 ≤ ≤ − 1. The allreduce operation may be modeled as a reduce-scatter followed by an allgather.

Network and Cost model
The network topology is modeled as a directed graph, represented as the tuple = ( , ), where denotes the set of nodes (| | = ) and denotes the set of directed edges. The optical network imposes a constraint that all nodes have degree , which is ideally low and independent of .
We use the well-known -cost model [19]. The cost of sending a message is assumed to consist of node latency and a bandwidth latency component, which is the inverse of the link bandwidth , = 1 . The cost of sending a message of size between two nodes is given as + . This simple model has been shown to be a good proxy for characterizing communication costs on existing GPU interconnects [10,24,36]. The node bandwidth is denoted by , with = .

Collective Communication Schedules
Our goal is to identify efficient communication schedules. We now lay out some technical notation that will be helpful in provide precise descriptions of the schedules that we employ.
We allow collective communication algorithms to operate at a finer granularity than a shard. We define a chunk to be a subset of the shard . is specified using an arbitrary index set identifying the elements of contained within .
The schedule can be specified as which chunks are communicated over which links in any given communication step (or comm step). Thus, a schedule for a topology is a set of tuples (( , ), ( , ), ) with , , ∈ , ( , ) ∈ , and = 1, 2, . . . , max . (( , ), ( , ), ) denotes that node sends 's chunk to node at step . 1 A subschedule is a subset of at some comm step . We note that a schedule can use different sized chunks during its operation, and comm steps could differ in terms of data communicated.
A communication algorithm ( , ) uses the schedule on topology . The runtime of an algorithm can be broken down into a node latency component and a bandwidth latency component. The node latency component ( ) is equal to max . ( ) could also be viewed as the cost of performing a collective operation on an infinitesimal amount of data. The remaining cost associated with the transmission costs of data over links is the bandwidth latency component ( , , ), which is a function of model size and 1 is the destination and source in reduce-scatter and allgather respectively. bandwidth . Especially, ( , , ) = ( , , ) = max ( , ) ∈ 1 / ( ( , ),( , )) ∈ | |. We sometimes omit and to write ( ). For -regular graphs on nodes, the lower bound on both the reduce-scatter and allgather time is approximately log + 1 · ( −1) . The first term represents the latency component associated with communicating across the diameter of a network, while the second term represents the transmission time across all links.
We analyze schedules in terms of node latency optimality and bandwidth optimality. We provide an informal description of these terms and refer to Appendix B for a precise specification. Note that the number of comm steps in the reduce-scatter algorithm is at least the diameter of . We use the graph-theoretic concept of a Moore bound , [28], which represents an upper bound on the number of vertices of a graph with maximum degree and diameter . We say that a reduce-scatter algorithm ( , ) with ( ) = is Moore optimal 2 if and only if > , −1 ; that is, the largest graph that one can construct with diameter − 1 is less than . We define the schedule to be bandwidth optimal if the amount of data sent out by each node is · −1 and the amount sent out each link is the same at any given comm step. The first condition ensures that the minimum amount is sent, and the second condition represents balanced loads.
We now discuss commonly used topologies and schedules. The Ring topology is a popular logical topology used by libraries such as NCCL. The ring allreduce [21] algorithm has an initial reduce-scatter phase where every node acts as the root of the th shard. During this phase, data are sent along the ring to their respective root nodes. The roots then act as source nodes in the allgather phase and distribute the shards along the ring. The total time required for ring all reduce is = 2 ( − 1) + 2( −1) . Note that the node latency term is linear in , while the bandwidth latency is actually optimal. The Double binary trees [22] offers the advantage of logarithmic latency with a suboptimal bandwidth in a (near) 4-regular topology. The topology consists of two rooted binary trees, where the nodes are connected such that each rank is an intermediate node in one tree and a leaf in the other. In the double binary tree, the non-root nodes transmit on both the binary trees. The total allreduce time required for double binary tree is = 2 log 2 + 4 log 2 . While the node latency is logarithmic, the bandwidth latency is suboptimal by a factor of 2 log 2 , which grows with .

Network Fabric
The focus of this work is to identify the optimal directconnect topologies. We believe that the resulting topology and schedules can be realized in a broad range of deployment settings, such as: switch-less physical circuits between pairs 2 Moore optimality is a stronger optimality of node latency optimality ( §B.1). of nodes identified by the network topology, patch-panelbased optical circuits that are constructed for the duration of an application run, and optical circuit switches that could be used to dynamically reconfigure the circuits. These options differ in terms of cost, scalability, and reconfigurability [40].
Switch-less physical circuits require the least amount of fabric hardware. However, the network topology must remain reasonably static for long periods spanning multiple executions of the applications desiring collective communications, as the reconfiguration operations must be manual. This rigidity makes it appropriate only for clusters dedicated to repeatedly running a constrained set of applications.
Patch-panel-based optical circuits provide a higher degree of reconfigurability by using a mechanical solution (e.g., robotic arms) to perform physical reconfigurations through a patch panel. The reconfigurations occur on the scale of minutes, but the patch panel itself can scale to a large number of duplex ports (e.g., about 1000) and is reasonably cheap (e.g., about $100 per port) [37]. This option allows the topology to be reconfigured before each long-running application.
All of the options described above can take advantage of high-speed optical connectivity options without being bottlenecked by the switching fabric, as is the case with clusters interconnected by electrical packet switches.

Related work
Classic work on efficient collective communications in high performance computing (HPC) focused on topologies such as ring, mesh, tori, hypercubes [7,9,18,31] etc. Collective algorithms such as recursive doubling and Bruck algorithm [38] and low latency and bandwidth optimal algorithms for multidimensional mesh/tori and hypercubes [12] make assumptions that are specific to HPC networks. Notably, the focus of these efforts is to optimize the collective algorithm for a given popular topology as opposed to determining an optimal topology for a workload.
Data parallel ML training has driven researchers to intensely study the problem of minimizing collective times, again on given topologies. Within a tree or a ring topology, ring-based collectives were shown to be bandwidth optimal [32]. Horovod [35], Baidu [16], and GLOO [29] implemented ring-based collectives in their systems, all of which suffer from significant latency cost. BlueConnect [14] optimizes collectives on switch-based fully-provisioned Fat-Tree like topologies by following a bandwidth-optimal log-latency multi-phase allreduce algorithm. However, state-of-the-art GPU cluster architectures, e.g., NVIDIA DGX A100, have very high intra-cluster GPU/node bandwidth (2.4 Tbps) with comparatively lower scale-out bandwidth (200 Gbps Infiniband NICs). Achieving bandwidth-optimal collectives on such systems at scale would require increasing the scale-out bandwidth 10+ fold and provisioning a large number of high bandwidth electrical switches connected through a leaf/spine topology. This adds significant cost to the network design. Recent research has focused on generating good collective schedules on arbitrary topologies. The Blink library [39] uses a packing spanning trees approach to generate near bandwidth-optimal schedules but ends up utilizing trees of ( ) depth. The SCCL library [10] uses a Satisfiability Modulo Theory (SMT) solver to find pareto-optimal schedules in terms of node latency and bandwidth latency. TACCL [36] extends SCCL to handle up to = 80 nodes and to account for heterogeneity in link latency and bandwidth. Unlike SCCL and TACCL, we consider the topology as a degree of freedom.
The work that is closest in spirit is TopoOpt [40] that jointly optimizes the network topology and the parallelization strategy in the context of hybrid data/model parallel ML training. Our use of patch panels is inspired by the TopoOpt work, but we view these two efforts as complementary. In particular, TopoOpt does not consider optimizing the communication collectives of data parallel training jobs. Consequently, when data parallel jobs dominate the workload, TopoOpt's network topologies end up being various ring permutations, which do not improve on existing baselines.

OVERVIEW OF OUR APPROACH
We seek to identify optimal network topologies and the appropriate communication schedules for realizing operations such as allreduce. We observe that when the target cluster size is just a handful of nodes, one could easily construct optimal topologies and schedules. But, such constructions are harder to perform for larger cluster sizes.
Consider, for instance, a 4-node cluster with a degree constraint of two. Two possible network topologies for such a cluster are a 4-node circulant graph 1(a) and a 4-node complete bipartite graph 1(b). One can construct by hand schedules that are both latency and bandwidth optimal for operations such as reduce-scatter. Consider, for instance, the circulant graph. Node 0 would send half of its 3 to 1 and the other half to 2 in the first step. Node 0 would then send its 1 and 2 shards to 1 and 2, respectively, in the second step. In parallel, nodes 1 and 2 would accumulate values obtained from node 0 with their own 3 shards before forwarding the results to 3 in the second step. Unfortunately, it isn't obvious how we can extend these 4-node topologies and schedules to larger cluster sizes or higher degrees.
We, therefore, take the following approach. First, we identify a set of base graphs and schedules for small cluster sizes. These base graphs could be well-known structured topologies (as in Figures 1(a) and 1(b)) or synthesized graphs with good network connectivity properties (as in Figure 1(c)). Second, we identify a set of expansion techniques that can operate on these base graphs and schedules to distill much larger graphs with provable properties on latency and bandwidth optimality. The expansion techniques can be iteratively applied to generate multiple candidate topologies from which we can choose. We first discuss the expansion techniques before describing the base network topologies.

EXPANSION TECHNIQUES
This section presents three techniques to construct nearoptimal algorithms with arbitrarily large topologies based on ones with a much smaller scale. The three techniques provide different options for increasing the size of the network and the per-node degree, while preserving the latency or the bandwidth optimality properties of the input network.

Line Graph Expansion
We borrow the concept of line graph from graph theory.
Given a schedule for a topology , the line graph expansion constructs a schedule ( ) for 's line graph   ( ). In particular, ( ) preserves node latency optimality and makes a bounded sacrifice to bandwidth optimality. with ≠ ′ . max is the maximum comm step in .
The above schedule uses the path followed by the chunk ( , ) to construct the path for a corresponding chunk ( ′ , ). The constructed path ends one hop before ′ , given that the graph's size has expanded, so the schedule includes an additional comm step to communicate the entire shard containing ( ′ , ) to the final destination ′ . Figure 2b illustrates the schedule construction with a sample path.
The runtime of schedule ( ) is given below. Theorem 4.3. Given a -regular topology , if ( , ) is an -node reduce-scatter algorithm with ( , , ) = ( / ) for some constant , 5 then ( ( ), ( ) ) is a -node reduce-scatter algorithm satisfying: 3 An equivalent version exists for allgather (corollary A.5). 4 If is multigraph, then given , ∈ , there may be multiple ( , ) ∈ and multiple ∈ ( ) . 5 The assumption ( , , ) = ( / ) for some constant almost always holds. One would reasonably assume the bandwidth runtime is linear in model size and the inverse of bandwidth.
The formal proof is in Appendix C.1, but we provide a brief analysis here. The latency component increases due to the additional comm step introduced in the schedule. Theorem C.1 shows that if and only if ( , ) is Moore optimal, then ( ( ), ( ) ) would also be Moore optimal given the -fold increase in the size of topology. However, the constructed schedule might not be bandwidth optimal even if ( , ) is bandwidth optimal. While the final comm step exhibits balanced communication load across all links, some of the prior comm steps could be unbalanced. In particular, given any edge ( , ′ ), the number of (( ′ , ), ( , ′ ), ) ∈ ( ) for each (( , ), ( , ′ ), ) ∈ could be or less than by definition 4.2. The resulting load imbalance is however bounded by the above theorem.
By repeatedly applying line graph expansion, one can expand the reduce-scatter algorithm to arbitrarily large-scale.
Corollary 4.4. Given a -regular topology , if ( , ) is an -node reduce-scatter algorithm with ( , , ) = ( / ) for some constant , then ( ( ), ( ) ) is a node reduce-scatter algorithm satisfying: In practice, we often construct an optimal reducescatter/allgather algorithm with a small number of nodes, and then apply the line graph expansion to scale it up. Theorem C.2 in Appendix C.1 bounds the bandwidth inefficiency introduced by repeated line graph expansions. In practice, the bandwidth inefficiency is minimal. For example, the 2dimensional Hamming graph is one of our base graphs that admits a latency optimal and bandwidth optimal algorithm with (1 + /2) 2 number of nodes. By applying line graph expansion, we can construct an arbitrarily large reducescatter/allgather while being latency optimal and at most [( − 1) (1 + /2) 2 ] −1 away from * .
Another implication of Theorem C.2 is that the larger the size of the bandwidth-optimal base graph is, the closer the expanded algorithm is to bandwidth optimality. Especially, if one has a bandwidth optimal base graph with Ω( ) number of nodes, the expansion is (1/ +1 ) away from * .

Degree Expansion
While line graph expansion focuses on expanding network size, degree expansion focuses on expanding to a higher degree topology. Given a -regular topology and its schedule , if has no self loops, then degree expansion can construct an -regular topology * and its schedule * with ∈ N.
* preserves bandwidth optimality while having only one additional comm step.
Theorem 4.7. Given a -regular topology without self loops, if ( , ) is an -node reduce-scatter algorithm with ( , , ) = ( / ) for some constant , then ( * , * ) is an -node reduce-scatter algorithm satisfying: Proof. Appendix C.2 provides a formal proof. □ A crucial property of degree expansion is that, if the base graph has balanced communication load across its links, then the expanded graph also exhibits balanced load. Taking a bandwidth optimal base graph, one can easily see the following corollary by Theorem 4.7: Corollary 4.8. If ( , ) is bandwidth optimal and ( , , ) = ( / ) for some constant , then ( , * ) is bandwidth optimal.
One should note that although degree expansion adds only one to by (5), the degree of topology increases in the expansion. The increase of degree results in a decrease of * , so degree expansion does not preserve latency optimality. Nevertheless, it is still very useful when is small.
Although degree expansion does expand the number of nodes, it also increases the degree. Therefore, degree expansion alone is unsuitable for constructing an algorithm for an arbitrarily large scale. In practice, one can use degree expansion to construct an algorithm of a given degree and then use line graph expansion to scale the algorithm to the desired number of nodes.

Cartesian Product Expansion
The Cartesian product of graphs is a well-studied concept.

Cartesian Power Expansion. Given a -regular and schedule
, we can construct a schedule □ for □ , which is -regular and has | | nodes. Like degree expansion, Cartesian power expansion preserves bandwidth optimality and helps generate efficient topologies. Torus (wraparound mesh), Hypercubes, Hamming graphs: The -dimensional directed torus ℓ, is a -way Cartesian product graph with each graph being a unidirectional ring on ℓ nodes. Nodes in ℓ, can be indexed by an -tuple, ( 0 , 1 , . . . , −1 ), with 0 ≤ < ℓ and = ℓ . The nodes indexed by ( 0 , . . . , −1 , , +1 , . . . , −1 ), 0 ≤ < ℓ form a unidirectional ring. Figure 4 shows a 2-dimensional torus with ℓ = 3. The -hypercube is a special case of -dimensional torus with 2 nodes in each dimension connected by a bidirectional edge. Hamming graph ( , ) is the Cartesian product of complete graphs . See Appendix E for further details.
To construct the schedule of □ , observe that given an . Let u, be such a subgraph, then there are | | −1 such subgraphs all isomorphic to . In addition, all such subgraphs have disjoint edge sets, so there is no congestion if we run allgather on these subgraphs simultaneously. As shown in Figure 4 each node u in the torus ℓ,2 belongs to two subgraphsu,1 and u,2 , the   (1) ) and the second subshard gets allgathered vertically ( (2) ); Right (step 2): the subshard allgathered horizontally in step 1 gets allgathered vertically ( (1) ) and vice versa ( (2) ).
horizontal and vertical ring containing node u respectively. Each subgraph is isomorphic to the ring on ℓ nodes.
In the schedule (1) where allgather is performed on subgraphs in order = 1, . . . , : at each allgather, every vertex sends all shards it has received so far to every other vertex in u, . At the end of , each u ∈ □ has received shards from Thus, at the end of = , each vertex has received shards from all other vertices and hence finishes the allgather on □ . Observe that such allgather schedules are far from bandwidth optimal. At , all the edges of subgraphs u, ′ for all u ∈ □ and ′ ≠ are idle.
To utilize all the bandwidth, the schedule □ divides each shard into equal-size subshards, and lets ( ) perform allgather on all the th subshards of nodes. Observe that by performing (1) , . . . , ( ) simultaneously, all edges are utilized at every , and there is no congestion between any two schedules of (1) , . . . , ( ) , because there is exactly one ( ) performing allgather on any u, at any .
Example Figure 4: Each node divides the data into 2 subshards. In accordance to schedule (1) , the first subshard ′ gets allgathered along with the corresponding subshards of other nodes in the horizontal ring ,1 first, and then along vertical rings { ,2 , = 1, . . . , ℓ }; while following schedule (2) , subshard ′′ gets allgathered along the corresponding subshards of nodes in the vertical ring ,2 and then along horizontal rings { ,1 , = 1, . . . , ℓ }. The product schedule, where (1) and (2) are performed simultaneously, will be bandwidth optimal since all the links are fully utilized. The latency is (ℓ − 1). The schedule is formally defined below. to (1) for all x, y ∈ −1 and z ∈ − . max is the maximum comm step in .
4. Divide each shard into subshards. Construct schedule □ such that ( ) performs allgather over the th subshards of all nodes. Appendix C.3 provides a formal analysis of the bandwidth optimality of the Cartesian Power expansion.

Shortest-Path Cartesian Product
Expansion. It turns out that one can also construct a bandwidth optimality preserved schedule for the Cartesian product of distinct topologies. However, such construction involves shortestpath schedule, which we will introduce in §6. Here, we will only briefly mention the conclusions: Theorem 4.11. Let ( 1 , 1 ), . . . , ( , ) be reducescatter algorithms such that are nontrivial simple digraphs; (2) 1 , . . . , are bandwidth optimal shortest-path schedules.
The optimal shortest-path schedule (i.e., schedule given by (7)) Shortest-path Cartesian product expansion is helpful in constructing pareto-optimal topologies. Given = × × , one can simply find three topologies with , , and number of nodes, respectively, and then apply shortest-path Cartesian product expansion to construct an -node topology.

BASE GRAPHS AND SCHEDULES
We consider three categories of -regular base topologies for the application of the above expansion techniques.

Structured, -regular Graphs
Rings: A union of parallel unidirectional rings or /2 bidirectional rings yields simple bandwidth optimal base graphs that are highly latency suboptimal, but a thoughtful application of cartesian product and line graph expansion techniques can yield useful topologies at larger scales. Complete graphs of size + 1: These admit bandwidth and latency optimal schedules (a single-step operation with communicating its to ). Iterative line-graph expansions yield larger graphs of degree and their corresponding schedules. Circulant -regular graphs: Here each vertex is connected to the higher-numbered vertices following it. See Section 3 for bandwidth-and latency-optimal schedules for = 2. Complete bipartite graphs , : Here each vertex in bipartite subset = { 1 , . . . , } ⊂ , is connected to every vertex in the opposite bipartite subset = { 1 , . . . , } ⊂ , . The following 2-step schedule is both latency and bandwidth optimal. First, divides its version of shard into chunks and sends one chunk to each of its neighbors (i.e., the 's) (and similarly 's to 's). Next, sends its version of shard to and sends its version of shard to .

Expander -regular Graphs
Expander graphs are sparse graphs with low modularity, i.e., admit minimal clustering. They allow any small subset of nodes to reach a much larger subset in a small number of hops. This "expansion" property is helpful for collectives.
De Bruijn Graphs: An -dimensional de Bruijn graph of two symbols {0, 1} is a directed graph with = 2 nodes, consisting of all possible length-binary sequences. The vertex and edge sets are given by = 0, 1}, respectively. In other words, if the binary sequence of a vertex can be obtained by shifting all the symbols of the binary sequence of vertex to the left and adding a new symbol at the end, then there exists a directed edge from to , ( , ). An example of 3-dimensional de Bruijn graph is shown in Figure 5(a). The definition can be generalized to symbols, where is the node indegree and outdegree. There is a unique shortest-path reduction tree for each node in the de Bruijn graph. Collectives over such trees are latency optimal and have bounded bandwidth sub-optimality.
Modification on the De Bruijn graphs: In order to improve the collective communications performance of ( , ), we modify the topology by making the following observations: (a) The graph has self loops rooted at the following nodes {( , , . . . , ), = 0, 1, . . . , − 1}, (b) ( − 1)/2 number of 2cycles between nodes of the form Clearly, the self-loops do not help with collectives. Further, the 2-cycles reduce the expansion effect of the graph. Observe that the nodes involved in self-loops and 2-cycles are disjoint. We modify ( , ) by connecting the 2 nodes involved in self-loops and 2-cycles into one long cycle to obtain ( , ) as shown in Figure 5(b). This reduces the bandwidth delay significantly. See Appendix F for details. Unlike ( , ), ( , ) has multiple shortest paths between certain pairs of nodes, so we use an SMT solver, e.g., SCCL [10] to search for the schedule for small values of and .
( , ) graphs (e.g., for ( , ) = (2, 4) or (4, 2), which are tractable for the SMT solver) have optimal bandwidth and near-optimal latency performance and are larger than other base graphs with similar properties. Therefore, they serve as competitive base graphs for expansion techniques, which then distill expanded schedules.

Synthesized Graphs
We now consider synthesizing -regular base graphs on nodes that have optimal or near-optimal bandwidth-delay as well as node-latency for allgather and reduce-scatter collectives. This is a sequential optimization problem as we first seek to synthesize a good topology and then identify the best transmission schedule. Below we describe an approach that uses a combination of mathematical programming and SMT solvers, e.g., SCCL [10] to discover topologies and schedules for small that are both latency and bandwidth optimal.
The first step is to synthesize what are likely to be good network topologies. In allgather, each node wants to send a common message to the other − 1 nodes. Casting such point-to-multipoint collectives in this optimization framework is unwieldy, so we used concurrent point-to-point communication flows as a relaxed proxy. In the latter, each node has a unique message , to send to all nodes ≠ . The problem now is to construct the optimal (throughput maximizing) network topology spanning nodes such that each link has unit link capacity and each node has out-degree and in-degree equal to a fixed constant .
We develop a natural Mixed Integer Quadratic Programming (MIQP) formulation, which we then convert to a standard Mixed Integer Linear Program (MILP) using the special product structure of the variables in the constraints. Running the MILP described in Appendix G.3 for = 8, = 2 for almost a whole day yielded the Diamond topology shown in Figure 1(c). 6 Using SCCL on this topology, we were able to synthesize bandwidth-delay and node-latency optimal schedules for reduce-scatter and allgather collectives.

SHORTEST-PATH SCHEDULE
We now provide an optimization formulation for computing efficient shortest path schedules for certain classes of graphs, such as those produced by a Cartesian product and expander graphs like generalized Kautz graphs (see §D.1.) Definition 6.1 (Shortest-Path Schedule). A reduce-scatter schedule on is a shortest-path schedule if satisfies: For allgather, the statement becomes "(( , ), ( , ), ) ∈ if and only if ( , ) = ( , ) − 1 = − 1." In a shortestpath schedule, each element ∈ always follow the shortest path to its destination. It is easy to see that: Theorem 6.2. If is a shortest-path schedule for , then ( )/ = ( ). 6 We were also able to synthesize for other small values of and , e.g., = 10, = 3.
By theorem B.2, shortest-path schedule always have the minimum node latency given a topology. As for bandwidth runtime, (2) of theorem B.8 is always satisfied in shortestpath schedule. This is an important reason why shortest-path schedule generally has good bandwidth performance. Thus, from (1) of theorem B.8, theorem D.1 shows the necessary and sufficient conditions for the bandwidth optimality of shortest-path schedule.
In many topologies, there are multiple shortest paths from one vertex to another vertex. In order to balance workload, we can divide shards into chunks to utilize all paths. In particular, we have the following theorem proved in Appendix D.
for is a reduce-scatter shortest-path schedule if and only if: (1) Schedule satisfies the condition in definition 6.1; (2) The collection of chunks To understand theorem 6.3, one can imagine the shortestpath schedule as a bus schedule. Each vertex sends buses taking the shard to at comm step ( ) +1− ( , ). Another vertex just needs to make sure that its chunk for arrives at before ( ) + 1 − ( , ) so that the chunk can take the bus to the destination . Now, suppose vertex needs to send its shard to . At comm step ( ) + 1 − ( , ), let 1 , . . . , be the neighbors of such that ( 1 , ) = · · · = ( , ) = ( , ) − 1. Each has a bus departing at comm step ( ) + 2 − ( , ). Thus, vertex only needs to guarantee that each chunk of its shard for arrives at some at comm step ( ) + 1 − ( , ). The size of each chunk can be arbitrary as long as (2) is satisfied. It turns out that we can use linear program to optimize the size of each chunk to construct a schedule with minimum bandwidth runtime.
It is notable that at = ( ), the solution is trivial with , = 1 and , , , = 1 for all ∈ and ( , ) ∈ . To compute a reduce-scatter shortest-path schedule for topology , one needs to solve LP (7)  , , , , and [ , + , , , ) is a subinterval of . The overall bandwidth runtime is given by Note that given a topology , any shortest-path schedule gives the same . Therefore, the one with minimum is the optimal shortest-path schedule of . It follows that Theorem 6.4. Given any topology , linear program (7) gives the optimal shortest-path schedule of .
The linear program (7) makes an assumption: the size of each chunk can be infinitesimal. In practice, each shard of the model may only be divided up to chunks (i.e., the whole model can only be divided up to chunks). In such case, theorem D.2 shows that we can approximate the optimal shortest-path schedule in polynomial time. In particular, if is Moore optimal, then the approximation costs at most · more bandwidth runtime than the optimal one. · is certainly negligible if is sufficiently large.

CASE STUDY OF TOPOLOGY GENERATION
We now show how to use the techniques introduced so far to build a 1024-node algorithm with degree 4. Our tool for topology and schedule generation uses a simple brute-force technique to identify different ways to construct a topology. It starts with the various base graphs and expands them all the way to the desired degree and size using any valid combination of expansion techniques. For example, there are many ways to build a 1024-node topology: one can directly use the generalized Kautz graph Π 4,1024 in §D.1 or the third line graph of Hamming graph 3 ( (4, 2)), and so on. Note that the expansion techniques provide analytical models for latency and bandwidth. For all topologies introduced in this paper, the modeled reduce-scatter/allgather runtime is in the form + ( / ) . Different topologies usually have different values of and . Therefore, at every step, the tool maintains just the Pareto-optimal candidates, i.e., if two topologies have the same properties and one is inferior to the other in both latency and bandwidth, then the inferior one can be dropped. After it exhausts all possibilities, the tool then emits the surviving Pareto-optimal topologies and schedules. For = 1024, = 4, Table 1 shows the pareto-optimal topologies with their s and s.

EVALUATION 8.1 Testbed-Based Evaluation
Testbed: Our testbed consists of 8 servers with an NVIDIA A100 GPU [2] and a 100 Gbps HP NIC [3]. The NICs are configured as 4x25Gbps breakout interfaces [1], and connected directly via a G4 NMT optical patch panel [6]. Our testbed can realize all topologies (upto N=8, d=4) by reconfiguring the patch panel. Observed for RDMA and NCCL calls is 5us and 15us, respectively. We execute collective communication operations using the NCCL library [4], slightly modified as described in [40] to support directly connected topologies. Prototype: We developed an end-to-end pipeline that computes the optimal topology and schedule for a given collective, model size, cluster scale, node constraints mainly degree and bandwidth, and link latency . The first component of the the pipeline involves profiling the bandwidth and latency for a specific cluster. The optimizer component searches the space of base graphs and expansion techniques to determine the best performing topology and schedule by employing our analytical models ( §8.2). The topology manager component configures the simplex connections in the patch panel to match the directional topology. The routing manager component configures the RDMA forwarding rules to enable the overlay paths necessary. The schedule produced by the optimizer is then lowered to the NCCL runtime using the TACCL runtime [27]. The latter extends the NCCL backend with an interpreter for ingesting external schedules of the transfers and lowering these to per rank programs.
We acknowledge that directed topologies present a key practical challenge on our testbed. These topologies can be realized by configuring the patch panel in simplex mode. For servers with directed links, we use overlay routing for the reverse path traffic (acks etc.), We ensure that packets are routed back to the same source NIC (and go out from the dest NIC) for correctly forwarding RDMA traffic. 7 These routing rules are implemented using standard utilities such as arp, route, tc filters, etc. based on previous work [40].
The key limitation is that our NICs do not support hardware offload for all of these rules, and so they are executed in the linux kernel. This leads to significantly higher and unpredictable RTT, as packets must be routed through multiple hops in many cases. Therefore, we can functionally validate these topologies on our testbed, we cannot accurately evaluate their performance. Note that newer NICs (eg. [5]) do support hardware offloading for these rules. Workload: We evaluate the complete bipartite graph ( 4,4 ), which is both latency and bandwidth delay optimal for our testbed size. We use NCCL-tests [30] benchmark for for performing allgather, reduce-scatter and allreduce operations of different sizes. We compare against NCCL's ring based collectives, with schedules realized using our prototype. Ring collectives are bandwidth optimal but have higher latency. Results: Figure 6 presents the collective comm time at different message sizes for the reduce-scatter and all-reduce operations. Observe that the 4,4 has 18-20% lower latency compared to the the ring collectives, because of more optimized schedules (7 latency delay for vs 2 for 4,4 ). Both topologies are bandwidth optimal and achieve similar performance at higher message sizes. We also present how these results translate to the performance of DNN training in §8.2.3; Note that improvements are small at the current scale but more significant at the larger simulated scale.

Analysis and Simulations for Larger Topologies
Deciding the right topology depends on many factors, e.g., , , , , and message size distribution. Because there are too many dimensions, our analyses are interested in fixing some of the parameters and seeing how other parameters affect the optimality of topologies. In this section, we will walk 7 RDMA Forwarding is also needed during the initialization phase of undirected topologies [40].   through some of the analyses we have used to probe into the performance of different topologies. We also perform trace-driven simulations of DNN workloads.

Asymptotic Analysis.
We use asymptotic analysis to study the performance of line graphs of different base graphs. We want to see how those base graphs perform if we expand the algorithms to large . Theorem C.2 tells us that line graph expansion gives us a bounded / * ratio. From Figure  7, one can clearly see the trend that / * monotonically increases as we recursively applying line graph expansion to base graphs. As increases, / * converges to an upper bound. Figure 7 also shows that Hamming graph (2, 3) has the lowest bandwidth runtime asymptotically. The reason is that base graph (2, 3) has the largest size among other base graphs in the figure. As predicted by Theorem C.2, the largest bandwidth optimal base graph has the lowest asymptotic bandwidth by line graph expansion.  Figure 9: The minimum reduce-scatter/allgather runtimes at different for = 4, = 10 , and / = 100MB/100Gbps. "L", "D", "P", and "C" stand for line graph expansion, degree expansion, Cartesian power, and Cartesian product (of different graphs) respectively. For example, "LPC" means the runtime is achieved by a topology whose construction involves line graph expansion, Cartesian power, and Cartesian product. "BiRing" and "GenKautz" stand for bidirectional ring and generalized Kautz graph.  Another way to do asymptotic analysis is to interpolate the total runtime at large and see which base graph has the lowest runtime at different and / . Figure 8 shows an example. One may find it puzzling that 5 performs well at higher and lower / , while its / * is the highest in Figure 7. The reason is that while line graphs of 5 are Moore optimal, just as line graphs of other base graphs, they have much larger than others have at the same / . When is large and / is low, 5 naturally becomes more optimal in terms of total runtime + .

Pareto-Optimal Analysis.
There exist multiple paretooptimal topologies at given and . For different and / , the Pareto-optimal topology with minimum total runtime is also different. To see how affects the optimality of topologies, we have done the analysis in §7 for every from 1 to 2000. In addition, we fix , and / to see what are the best topologies and runtimes at different . Figure 9 shows an example of such analyses. The minimum runtime can be vastly different for different . For example, at = 1999, the minimum runtime is 13.56ms given by generalized Kautz graph; however, at = 2000, 2 (BiRing(2,5)□UniRing(1,5) □2 ) gives 8.53ms minimum runtime. An important reason is that 1999 is a prime number, so no expansion can generate a topology with = 1999.
Despite the chaos, there are some patterns. Bidirectional ring and generalized Kautz graph provide bandwidth optimal solution and Moore optimal solution, respectively, for any . Thus, when expansion techniques fail to generate a good topology for some sizes like prime s, bidirectional ring and generalized Kautz graph can always be used as backup solutions. Especially, when is small, the bandwidth optimality of ring often gives minimum runtimes; when is large, the Moore optimality makes generalized Kautz graph superior to ring. Figure 10 shows the comparison against ring and double binary tree. As shown in the figure, the best topology is significantly better than either ring or double binary tree.

DNN Allreduce Analysis.
We now analyze the performance of topologies from a DNN perspective. In DNN training, we starts allreduce on a layer once it is ready during backpropagation rather than allreduce all layers after the backpropagation completes. Thus, the allreduce overlaps with backpropagation to save total runtime. The design also results in an independent allreduce for each layer. Because layers have different sizes, the in each allreduce is also different. In ResNet [17], the size of a layer goes from 256 bytes to 943184 bytes.
To calculate the total allreduce runtime, we gathered the ready time of each layer and simulated the backpropagation and allreduce. Suppose layers have been sorted in ascending order of their ready times. Let and be the ready time and size of layer respectively. We calculate the finish time for layer such that: The rationale behind (9) is that the allreduce of layer starts only if (1) layer − 1 has finished allreduce, and (2) layer has been ready for allreduce. We run simulations on various DNNs and compare the best of our pareto-optimal topologies against ring topology. The results are shown in Figure 11. As one can see, our performance is very close to theoretical lower bound and significantly better than ring topology. Figure 11 also shows a comparison of the average allreduce time per layer among the best of our pareto-optimal topologies, ring, and double binary tree.

CONCLUDING REMARKS
Collective communications are critical to both large-scale ML training and HPC. Current network architectures do not exploit the regular patterns of distributed data flow embedded in these collectives and often suffer from high latency or contention. In this paper, we demonstrated a novel direct-connect network design of jointly optimal topology and schedule by exploiting the concurrent aggregation and distribution-oriented data flow patterns. By leveraging scalable graph-theoretic approaches, our algorithm framework can provide maximally performant and resource-efficient topologies and schedules even for large scales.
An allgather algorithm has the same definition except 0 = and = . In this paper, many of the techniques are discussed under either reduce-scatter or allgather only. We will show that anything holds in either reduce-scatter or allgather has an equivalent version for the other collective operation.
Theorem A.3. If is a reduce-scatter/allgather schedule on , then is an allgather/reduce-scatter schedule on .
is an allgather schedule on . One can similarly show that if ( , ) is an allgather algorithm, then ( , ) is a reduce-scatter algorithm. □ Theorem A.3 has the following two corollaries: Corollary A.4. Suppose : ↦ → is a function to construct reduce-scatter/allgather schedule on , then : ↦ → ( ) is a function to construct allgather/reduce-scatter schedule on .
For example, the line graph expansion in §4.1 can be seen as a mapping within reduce-scatter, and the linear program (7) can be seen as a function to construct reduce-scatter schedule. Thus, corollary A.4 and A.5 have shown that they both have a equivalent version in allgather.
In undirected topology, it is well-knwon that reducescatter and allgather is a pair of dual operation such that one can be transformed into another by reversing the communication [12]. It is similar in directed topology but with additional requirement and more complicated transformation.

B OPTIMALITY
Because our cost model is only concerned with node latency and bandwidth runtime, the optimality of reducescatter/allgather algorithm is only related to node latency optimality and bandwidth optimality in this paper. The minimum diameter of a regular directed graph with a given number of vertices and degree is still an open question. One can check degree/diameter problem for more information [28]. However, the Moore bound for digraph is sufficient to tell the node latency optimality in most cases.

B.1 Node Latency Optimality
Definition B.4 (Moore Optimal). Let ( , ) be an -node reduce-scatter/allgather algorithm with ( ) = , then ( , ) is Moore optimal if and only if > , −1 , where , −1 is the Moore bound of degree and diameter − 1. Because for any -regular graph , ( ) ≥ as long as | | > , −1 , Moore optimality is a stronger condition than node latency optimality. We define a function * such that * ( ) is equal to the Moore optimal node latency of -node reduce-scatter/allgather algorithms.
Proof. In reduce-scatter/allgather, each node needs to either send at least · −1 amount of data. Thus, the minimum bandwidth runtime is · −1 . □ Because it is trivial to construct a schedule with ( ) = · −1 for an unidirectional ring of size , it follows the corollary: Corollary B.7. An -node reduce-scatter/allgather algorithm ( , ) is bandwidth optimal if and only if Thus, we define a function * such that * ( ) = · −1 is the optimal bandwidth runtime of -node reducescatter/allgather algorithms.
From corollary B.7, we have the following necessary and sufficient condition for bandwidth optimality.
Proof. If ( ) = * ( ), then the amount of data sent out by each vertex must be equal to · −1 . Thus, if ( , ) is bandwidth optimal, (2) must hold. If (1) does not hold, there exists some link ( , ) not fully utilized at some comm step. Because part of the bandwidth of ( , ) is wasted, ( ) > * ( ).
To compare this with the ultimate lower bound, in [31], the authors have proved that 2 * ( ) is indeed the lower bound of bandwidth runtime of any allreduce algorithm. As for node latency, one can use allgather alone to construct an allreduce with node latency * ( ). However, such an algorithm is miserable in bandwidth runtime. Thus, in this paper, we only consider allreduce algorithms with reduce-scatter followed by allgather.

C OPTIMALITY ANALYSIS OF EXPANSION TECHNIQUES
In this section, we provide proofs for the latency and bandwidth optimality properties of the various expansion techniques. with ≠ ′ . max is the maximum comm step in .
as desired. The new algorithm ( ( ), ( ) ) has total data length, because the number of nodes has grown -fold while the size of a shard remains the same. 8 An equivalent version exists for allgather (corollary A.5). 9 If is multigraph, then given , ∈ , there may be multiple ( , ) ∈ and multiple ∈ ( ) .
Because ( Proof. If ( , ) is bandwidth optimal, then (4) gives: It is trivial to see that (12)/ * ( Let be a shortest-path reduce-scatter schedule on with | − ( )| > 1 for all ∈ , then the expanded schedule ( ) is a shortest-path reduce-scatter schedule on ( ). In particular, if is the optimal shortest-path schedule on , then ( ) is the optimal shortest-path schedule on ( ) satisfying: Proof. It is trivial to see that ( ) is a shortest-path reduce-scatter schedule on ( ) by property (2) in §4.1. For the sake of contradiction, suppose there exists a shortestpath schedule ′ ( ) that ( ′ ( ) ) < ( ) + · 1 . Let * , ′ , ′ , s be the solution of (7) corresponding to ′ ( ) . We build a schedule ′ by constructing a solution of (7) such that where ∈ − ( )\{ } is arbitrary. To verify the construction is a valid solution, given any ∈ and ∈ ( )+1− ( ), the equality of (7) follows: The second equality follows property (2) in §4.1, and the third equality follows the equality constraint in (7). Now, given ( , ′ ) ∈ , observe that Thus, it holds that , = max ′ , ′ , , ≤ 1 , and hence max Given = | |, by (8), we have contradicting being the optimal shortest-path schedule. Thus, combined with inequality (2), we have proven ( ) being optimal as well as the equality (14). □ Corollary C.4. Let be a shortest-path reduce-scatter schedule on with | − ( )| > 1 for all ∈ , then the expanded schedule ( ) is a shortest-path reduce-scatter schedule on ( ). In particular, if is the optimal shortestpath schedule on , then ( ) is the optimal shortest-path schedule on ( ) satisfying:
as desired. Now, suppose = in , then in first step of definition 4.6, has been send to some neighbor ′ of . Since ′ ≠ , by previous proof, we can find a sequence taking from ′ to . Thus, there exists a sequence in * taking from to ′ and then to , so * is a reducescatter algorithm. From second step of definition 4.6, it is easy to see that ( [  *  ]   to (1) for all x, y ∈ −1 and z ∈ − . max is the maximum comm step in . 3. Similarly, construct ( ) for = 2, . . . , such that each vertex v in (1) is shifted by − 1 to (v[ − + 2 : ], v[1 : − + 1]). 4. Divide each shard into subshards. Construct schedule □ such that ( ) performs allgather over the th subshards of all nodes. Theorem C.5. Given a -regular topology , if ( , ) is an -node allgather algorithm with ( , , ) = ( / ) for some constant , then □ is an -regular topology, and ( □ , □ ) is an -node allgather algorithm satisfying:

C.3 Cartesian Power Expansion
Proof. We have already shown that □ is a valid allgather schedule for □ , and (15) is trivial. To prove (16), observe that at each , the total size of data needs to be allgathered at each subgraph u, is −1 / . It follows that Again, by assumption ( , , ) = ( / ), we have □ We then have the following corollary. Corollary C.6. If ( , ) is bandwidth optimal and ( , , ) = ( / ) for some constant , then ( □ , □ ) is bandwidth optimal.
Theorem D.2. Suppose each shard of the model can only be divided up to chunks. Given a topology , let OPT be the optimal bandwidth runtime of reduce-scatter shortest-path schedule. Then, one can compute a shortest-path schedule with bandwidth runtime ≤ OPT + · ( ( ) −1) in polynomial time. In addition, if is Moore optimal, then ≤ OPT + · .
Proof. Consider the following integer program: Compared with (7), one can easily see that the optimal solution of (21) gives the optimal reduce-scatter shortest-path schedule when each shard of the model can only be divided up to chunks. One can also easily solve the LP relaxation of (21) in polynomial time. Suppose the LP relaxation gives a schedule with bandwidth runtime LP , then we have LP ≤ OPT . Consider the solution to (21) obtained by rounding the optimal solution of LP relaxation. Let , , , s be the rounded solution. At comm step , there are at most ( )− number of s whose shortest path from passes a given edge ( , ). Thus, we have , ≤ LP , + ( )− . By (8), Note that we need to divide (8) by , because , , , ∈ [0, ] in (21) while , , , ∈ [0, 1] in (7). If is Moore optimal (i.e. > , ( )−1 ), it follows that

D.1 Generalized Kautz Graph
In §4.1, we have introduced line graph expansion as a technique to scale a base topology to arbitrarily large size. However, the resulting topology size can only be for some positive integer leaving large gaps in sizes. To design an algorithm for an arbitrary size, one can use the linear program (7) on generalized Kautz graph [20][8]: Definition D.3 (Generalized Kautz Graph). The Π , digraph has the set of integers modulo as vertex set. Its arc set is defined as follows: The Kautz graph ( +1 ) is always Moore optimal. In fact, Kautz graph is the largest known digraph in degree/diamter problem for any degree > 2 [28]. The following theorem shows that the node latency of generalized Kautz graph satisfies ≤ * ( ) + 1: Proof. From [20], we know that ≤ ⌈log ⌉. Then, □ From figure 12, one can also see that is also close to bandwidth optimality, especially at higher degrees.

E CARTESIAN PRODUCT GRAPHS
We list several examples of Cartesian product graphs, and investigate their collective performance under the algorithm detailed in Section 4.3.
The unidirectional ring is a 1-dimensional directed torus, while the standard wraparound mesh is a 2-dimensional directed torus. An -dimensional torus on nodes with = ℓ has diameter (ℓ − 1) . Note that each node in ℓ, belongs to subgraphs ,1 , ,2 , . . . , , . Each subgraph is isomorphic to the ring on ℓ nodes. The Reduce-Scatter or All-gather algorithm splits data at each node into subshards, and the nodes performs BKT collectives ( ( ) 's) in each subgraph sequentially while utilizing all the links. Consider the case where = 2 for All-gather: Each node has / sized data. Each node divides the data into 2 subshards; As shown in Figure 13, subshard ′ gets allgathered along with the corresponding subshards of other nodes in the horizontal ring ,1 first, and then along vertical rings { ,2 , = 1, . . . , ℓ }; while subshard ′′ gets allgathered along the corresponding subshards of other nodes in the vertical ring ,2 and then along horizontal rings { ,1 , = 1, . . . , ℓ }. Since the individual allgather  Figure 12: / * of generalized Kautz graph Π , up to = 2000. As one can see that the bandwidth runtime of Π , is less than or equal to 2 * at all time for = 2, 4, 8, 16. In particular, the higher the degree is, the closer is to optimal. As for node latency, theorem D.4 shows that ≤ * ( ) + 1.
collectives ( ) 's are BW delay optimal in their respective subgraphs, following Corollary C.6 the product collective will also be BW delay optimal. The latency is (ℓ − 1).
With the torus ℓ, as a base graph, the line transformation will have a BW delay cost of Φ . Note that for any fixed degree , we can get base graphs arbitrarily close to BW delay optimality. The latency cost will be approximately (ℓ − 1) − log ℓ with respect to the Moore's lower bound.

E.2 Hypercubes
-hypercube is a special case of -dimensional torus with 2 nodes in each dimension connected by a bidirectional edge. The BW optimal algorithm in each dimension, ( ) , exchanges the model between the two nodes in the same dimension. Following previous results, the product collective will be BW optimal and will have latency units.

E.3 Hamming graphs
Hamming graphs ( , ) is the Cartesian product of complete graphs . The BW optimal algorithm in each dimension performs the full torus collective. Following Corollary C.6, the product collective will be BW optimal as well with latency units.

E.4 Cycle-mesh graphs
Since the multidimensional directed torus topology described in E.1 takes an -way cartesian product of rings of length ℓ, it has number of nodes scaling as = ℓ . We present a construction that loosens this restriction on and produces graph that has = × where ≠ . This offers more degrees of freedom in the graph expansion process since this process allows the generation of a base graph on any that is factorizable into a product of two non-trivial factors. First, we observe that a standard rectangular ( , ) wraparound mesh where ≠ may not lead to ring-based bandwidth optimal schedules. This is because if < , the ring reduce/gather in the dimension takes more comm steps than the ring reduce/gather in the dimension, thus leading to suboptimal bandwidth-delay performance. We avoid this by following a different construction.
Suppose we want to build a bandwidth optimal graph on = 15 nodes with good latency properties. Observe that = 3 × 5 (thus = 3, = 5). We group the set of = 15 nodes into = 3 groups of = 5. For such factorizable , it is always possible to cover the set of nodes by a union of disjoint rings of length in two different ways. In this example, the first way is to just put the first = 5 nodes into the first ring {1, 2, 3, 4, 5}, the second set of 5 into the second ring {6, 7, 8, 9, 10}, and the third set of 5 in the third ring {11, 12, 13, 14, 15}, etc. The second way is to skip the node indices in each ring by = 3, e.g., the first ring will be {1, 4, 7, 10, 13}, the second will be {2, 5, 8, 11, 14} and the third ring will be {3, 6, 9, 12, 15}. Now we have = 3 sets of = 5-rings in two different dimensions, and hence we can do ring reduce/gather with equal number of comm steps ( = 5) in each dimension. Following the methods used for constructing schedules for step cartesian product of rings from individual steps, we can construct a bandwidth optimal schedule for this = × node graph.
Note that to be able to construct ring reduce/gather schedules, a necessary property that must hold is that for each ring in the first dimension, the set of orthogonal rings (i.e., rings in the second dimension) passing through each of the nodes in must cover the entire vertex space; otherwise the two-step ring reduce/gather procedure will not reach all nodes in the graph. Our construction satisfies this property.
Since the length of all the rings is equal to max( , ), the reduce/gather latency for the 2-step process = 2 max( −1, − 1). Thus for factorizations of where , are the closest in value to

√
, we can achieve low-latency bandwidth optimal schedules. Figure 14 shows the bandwidth optimal topology for = 15 with latency 8. This is not too far off from the 16 node perfect square wraparound mesh with latency equal to 6.

F MODIFYING THE DE-BRUIJN GRAPH
An n-dimensional -symbol De-Bruijn graph = ( , ) has self loops at the following nodes {( , , . . . , ), = 0, 1, . . . , −1}, and ( −1) 2 number of 2-cycles involving nodes of the form {( 1 , 2 , . . .), 1 ≠ 2 }. We propose modifying the De-Bruijn graph where the self loops and 2-cycles are removed and a single long cycle is constructed. Note that this process does not violate the degree regularity of the graph. Let the nodes involved in self loops and 2-cycles be denoted as ′ . Note that | ′ | = 2 . A valid modification that introduces a long cycle given by the edge set ′ ⊂ ′ × ′ must satisfy the following: For every edge = ( , ) ∈ ′ , both and ′ = ( , ) must not appear in the De-Bruijn graph unless they belong to a 2-cycle. This ensures that a multiedge or a 2-cycle does not get formed due to the modification.
We construct a symmetric directed graph ′ on the vertex set ′ that only contains symmetric directed edges that do not appear in the graph (in either direction) unless they are 2-cycles in . The problem of finding a valid modification boils down to finding an undirected Hamiltonian cycle in the symmetric directed graph ′ viewed as an undirected graph.
Any node in ′ which participated in either a self loop or a 2-cycle in must have degree at least 2 − 2( − 1) − 1. This lower bound is obtained by considering the worst case scenario where all the outdegrees and indegrees of , not considering the self loop or the 2-cycle, were to lie in ′ . Using Ore's theorem [41] which states that a Hamiltonian circuit exists if every node of a graph ′′ = ( ′′ , ′′ ) has degree at least | ′′ |/2, we obtain that for ≥ 4 we will always be able to perform a modification. We use efficient algorithms for finding Hamiltonian cycles in dense graphs for the purpose of making such modifications [15].For = 2, 3, only a small number of nodes are involved in the rewiring process, and thereby brute force approaches for finding Hamiltonian cycles are sufficient. Figure 15 shows the modification process on a 8 node binary De-Bruijn graph. Indicator variable denoting if link → should exist. ∀ , ∈ , ∈ {0, 1} Flow variable pertaining to commodity along link → . ∀ , ∈ , ∈ : 0 ≤ ≤ , ∈ R Demand variable for each commodity (considered equal from each source to target), ∈ R

G.2 Mixed Integer Quadratic Programming
The quadratic program optimizes the decision of laying down the links between each pair of nodes while adhering to the degree constraint, the flow conservation constraints, such that the per-node demand (throughput) is maximized. A uniform throughput maximizing solution that yields optimal rates at each node also corresponds to a minimum bandwidth-delay solution. Note that although we do not attempt to explicitly minimize the node-latency metric, we find that this optimization formulation tends to find low diameter topologies due to the -regularity requirement and the all-to-all nature of the traffic load. In other words, a high-diameter topology is unlikely to be the one that has the highest throughput since all nodes are supposed to communicate with every other node. max subject to constraints: ∀( , ) ∈ × : ∈ ≤ ∀ ∈ : = ∀ ∈ : = ∀ ∈ , ∀ ∈ , ≠ ( ), ≠ ( ) : = ∀ ∈ , = ( ) : = ∀ ∈ , = ( ) : = The first constraint ensures that the total amount of traffic flowing through each link ( , ) (summed over all commodities) does not exceed the link's capacity. The second and the third constraints enforce the out-degree and in-degree requirements. The fourth constraint ensures per-commodity flow conservation at each node that is neither the source nor the target for that commodity. The fifth and the sixth constraints ensure that each source and sink of a commodity, respectively, sources and sinks are given (equal) amount of traffic, , which is the quantity that needs to be maximized.

G.3 Linearization of the Quadratic Program
Mixed integer quadratic programs (MIQP) are prohibitively expensive to solve even using state-of-the-art solvers like Gurobi, especially if the constraints are quadratic as well, which is the case above. However, we exploit some special structure in the problem that helps us linearize it as follows. When encountering the product · , one can introduce a real-valued variable = · . If is binary-valued and is real valued and has lower and upper bounds, i.e., ≤ ≤ , the following constraints can be added to linearize the problem while preserving the structure of the solution: Although MILPs are also computationally intractable in general, it is tractable for small values of . This allows us to produce interesting base graphs that can be expanded using the techniques proposed in this paper, while preserving the bandwidth and latency-optimality properties of the synthesized base graphs.

H UNDIRECTED TOPOLOGY
While this paper focuses on directed topologies, many of the techniques can be conveniently applied to undirected topologies. For example, the shortest-path schedule including the linear program (7), degree expansion, and Cartesian product can all be used on undirected topologies. Although line graph expansion does not apply to undirected topologies, there is a way to convert a directed-topology schedule to undirectedtopology schedule. In this section, we will show how to convert a skew-symmetric -regular directed topology and its reduce-scatter schedule to a 2 -regular undirected topology ′ and its schedule ′ such that ( ) = ( ′ ) and ( ) = ( ′ ).
Let : → be the isomorphism from to , then it is trivial to see that ( ) is a reduce-scatter schedule for . Observe that ′ = ∪ is a 2 -regular undirected topology. Consider schedules and ( ) as schedules for undirected topology ′ . or ( ) alone is a reduce-scatter schedule for ′ . In addition, and ( ) do not congest on any edge, because ( ) and use opposite directions of edges. Thus, we can divide each shard into two halves. Let one half follow schedule and the other half follow ( ). Let such schedule be ′ .
It is trivial to see that ( ) = ( ′ ). As for ( ) = ( ′ ), it follows the fact that the total model size is halved for each of and ( ), but the bandwidth per edge is also halved due to the double of degree. Note that if is bandwidth optimal, then ′ is bandwidth optimal; however, ′ is not necessarily node latency optimal if is node latency optimal.