arXiv CSopen access

Resource Allocation in HyperX Networks

Resource Allocation in HyperX Networks Alejandro Cano† , Cristóbal Camarero† , Carmen Martı́nez† , Ramón Beivide†,∗ † Universidad de Cantabria, SPAIN ∗ Barcelona Supercomputing Center, SPAIN {alejandro.cano, cristobal.camarero, carmen.martinez,ramon.beivide} @unican.es

arXiv:2605.28205v1 [cs.DC] 27 May 2026

May 28, 2026

Abstract

In practice, HPC systems receive a diverse set of jobs, each representing an application composed of multiple processes or tasks that must be executed across the system’s available endpoint computers. The process of assigning computing resources to applications is known as job allocation or resource allocation. Subsequently, the task mapping assigns each task of the application to a specific compute node within the selected set. Both steps are critical to minimizing communication overhead and improving the overall performance of the system. In most HPC systems, job allocation is handled by workload managers such as SLURM, which queue and assign jobs to available resources based on system policies. While such tools provide the framework for managing system workload, the underlying allocation strategies must account for the characteristics of the interconnection network, as they indirectly determine how network resources are utilized. For example, if all the endpoints allocated to an application are connected to the same switch, the application’s communication will remain local and avoid traversing any network link. However, if the application requires more endpoints than those available under a single switch, the job allocator must select a set of endpoints from different switches to host the application. Depending on the physical location of these switches, the application’s traffic may traverse different network paths, leading to variations in latency and available bandwidth. For this reason, resource allocation has long been an active area of research across a wide range of networks. Current HPC systems are increasingly adopting modern low-diameter topologies such as Dragonfly [19], Dragonfly+ [25], and HyperX [2], which offer greater scalability and lower cost than Fattrees. Representations of some of these topologies can be seen in Figure 1. In them, circles represent switches and lines that join them are physical cables. Logically, these switches and cables form a graph. The rounded rectangles are the endpoints,

As high-performance computing systems scale in size and complexity, efficient resource management is essential to minimize communication overhead. The HyperX is a richly connected, low-diameter network that offers a scalable and cost-effective alternative to traditional topologies. However, resource allocation in HyperX remains underexplored, and strategies designed for networks like Torus, Fat-tree, or Dragonfly do not directly transfer. In this work, we propose and formalize several resource allocation strategies for HyperX networks, categorized into linear, geometric, and stochastic functions. We characterize these strategies theoretically by analyzing their topological properties, including dilation, convexity, and partition bandwidth. Furthermore, we conduct an exhaustive experimental evaluation using synthetic traffic and application communication kernels to assess the impact of these strategies on performance under different routing algorithms. Our results indicate that partition bandwidth and switch locality are decisive factors in mitigating interferences. Notably, the Diagonal allocation strategy, which is not convex, consistently outperforms traditional approaches in most scenarios. Finally, we provide a set of lessons learned to guide the implementation of resource allocation policies in HPC systems based on HyperX networks.

1

Introduction

Efficient resource management has become a critical concern for HPC system architects, administrators, and users. Current parallel applications often require thousands of processing cores, making the communication overhead between compute nodes, or network endpoints, a key performance bottleneck. To fully exploit the computational power of these systems, minimizing communication costs is essential. 1

Figure 1: Three topologies employed in HPC. From left to right: a 54-server, 6-radix, 3-level Fat-tree, a 4 × 4 × 4 torus, and a Dragonfly with 9 groups. Endpoints in Torus are omitted, but each switch is supposed to be connected to one endpoint. each one connected to a single switch. The diameter of a network is the number of switch-to-switch links that are necessary to traverse to connect any source-destination pair, using minimal paths. Nowadays, 8 out of the 10 most powerful supercomputers in the TOP500 list employ one of these low diameter networks [26]. Resource allocation in such networks presents challenges distinct from those addressed by traditional approaches for lowradix topologies, such as tori, or full-bisection bandwidth fabrics, like Fat-trees. While modern topologies exhibit low distances between endpoints, they are often constrained by limited bisection bandwidth. In this work, we focus on the HyperX topology—a richly connected, low-diameter network that has gained traction in HPC system design but remains underexplored in the context of resource allocation. Our primary objective is to analyze how different resource allocation strategies affect application performance when executed on systems based on a HyperX network. The main contributions of the paper are:

The remainder of this paper is organized as follows. Section 2 introduces the fundamentals of HyperX networks, including topology, routing, and scalability. Section 3 presents the motivation of this work and reviews resource allocation strategies in well-known topologies such as Fat-tree, Torus, and Dragonfly. Section 4 formulates the proposed resource allocation management using mathematical functions. Their fundamental properties are analyzed in Section 5. The proposed approaches are then experimentally validated. Section 6 describes the experimental methodology, while Section 7 presents the obtained results. Finally, Section 8 summarizes the main lessons learned of the complete study. Section 9 concludes the paper and briefly discusses the extension of the techniques presented to higher-dimensional HyperX networks.

2

The HyperX Network

This section introduces HyperX networks by defining their topology and the routing mechanism employed, and compares their scalability to other high-degree low-diameter networks.

• A theoretical model for the different possibilities of resource allocation in HyperX networks based on mathematical functions with different foundations: geometric, algebraic, and random.

2.1

Topology

The HyperX topology is a low-diameter, high-radix interconnection network proposed as a scalable alternative to traditional networks such as Fat-trees. It has been adopted in systems like Intel’s PIUMA [1], Cray’s Cascade [13] and in [12], underscoring its relevance in current and forthcoming • An exhaustive evaluation through simulation HPC architectures. of the proposed techniques. The HyperX networks are those networks having • A comprehensive list of outcomes from which a Hamming graph as the topology of their switches architects, administrators, and programmers [2]. The Hamming graph is the Cartesian graph of HPC systems based on HyperX topologies product of complete graphs. A complete graph has could benefit. a link between every pair of vertices. • A complete characterization of the most critical properties of the applications derived from the aforementioned theoretical modeling, namely: dilation, convexity and bandwidth.

2

The name of Hamming graph refers to the fact that the graph distance, that is the count of hops in a minimal path, coincides with the Hamming distance, used in Coding theory. This name has appeared in Graph Theory from at least 1974 [6, 23]. As a computer network, it was considered in [5] under the name of Generalized Hypercube. In that paper the authors noted that the Butterfly network could be understood as an unflattening of the Hamming graph. Later, in [20] the same graphs were considered as computer networks, under the pretense of enabling interstellar travel. In [18] these networks received the name of Flattened Butterflies. Then, in [2] it received a flashier name: HyperX, which is the one employed in Intel’s PIUMA [1]. It is to be noticed that previous definitions differ in aspects such as enforcing all sides to be equal, the number of endpoints per switch, whether to use parallel links for some edges, or if links are electrical or optical. Regardless of these details, a symmetric qD HyperX organizes its switches in a q-dimensional logical grid with each side having the same size, n. Each switch S has an address of q coordinates (sq , sq−1 , . . . , s2 , s1 ), with si ∈ {0, 1, . . . , n − 1}. Two switches are connected by an edge if their Hamming distance is 1, meaning that their addresses differ only in a single coordinate. Endpoint computers are connected to every switch. A direct network, as HyperX, is said to be well-balanced when, under uniform random traffic, every endpoint can inject data at full rate. A well-balanced qD HyperX of side n, requires n local ports on each of its nq switches to connect endpoint computers, leading to a total of nq+1 endpoints in the system. In addition, the switches require q(n − 1) network ports, (n − 1) of them per each of its q dimensions, to implement the complete graphs that compose each dimension. The diameter in a qD HyperX is q. This just considers traversed network links, disregarding injection and ejection local connections. In the same way, the average distance between pairs of switches is q − q/n. Note that this calculation, as well as all subsequent in the paper, is obtained assuming that every source may have itself as destination, which simplify its mathematical expression and further manipulations. The total number of network wires is q(n − 1)nq /2. In terms of raw cost, each endpoint computer requires 1/n switches and q(n − 1)/2n wires. This is, the cost in wires per endpoint computer approaches q/2 from below. Figure 2 shows a 2D HyperX with 5 switches per dimension and 125 endpoints. Observe that every row and column is a complete graph and, consequently, the network diameter is 2.

0,4

1,4

2,4

3,4

4,4

0,3

1,3

2,3

3,3

4,3

0,2

1,2

2,2

3,2

4,2

0,1

1,1

2,1

3,1

4,1

0,0

1,0

2,0

3,0

4,0

Figure 2: HyperX 5 × 5 topology with 5 servers per switch. 0,4

1,4

2,4

3,4

4,4

0,4

1,4

2,4

3,4

4,4

0,3

1,3

2,3

3,3

4,3

0,3

1,3

2,3

3,3

4,3

0,2

1,2

2,2

3,2

4,2

0,2

1,2

2,2

3,2

4,2

0,1

1,1

2,1

3,1

4,1

0,1

1,1

2,1

3,1

4,1

0,0

1,0

2,0

3,0

4,0

0,0

1,0

2,0

3,0

4,0

(a) Aligned source and destination.

(b) Unaligned source and destination.

Figure 3: Minimal (solid) and non-minimal routing paths (dotted) in Omni-WAR routing in a 5 × 5 HyperX. Links are omitted for clarity.

2.2

Routing

To deal with different traffic patterns, the network must be equipped with an adaptive routing mechanism. A well-established routing for HyperX topologies is Omni-WAR [22]. A closely related mechanism that uses the same set of routes is DAL [2]. The algorithm for Omni-WAR routing works over the difference in coordinates from the current switch to the destination switch. From the source switch, a dimension is said to be unaligned if it has a different value than the destination switch. Omni-WAR proceeds hop by hop, allowing a packet to move only through unaligned dimensions. Inside an unaligned dimension there is a single minimal hop and many potential deroutes. The minimal hop is given a preference over the deroutes, which is combined with their occupancies to obtain the selected port. The routing employs a hop-count mechanism to avoid both livelocks and deadlocks, a limit of m non-minimal hops is imposed, forcing hops beyond this limit to be minimal. This is a global limit, 3

with the same radix, would employ 4 096 switches to provide 65 536 endpoints. Thus, the scalability of a 3D HyperX is a bit above a Dragonfly with its required trunking. 106 As examples of diameter 2, consider using again switches with radix 64. A two-level Fat-tree can support 2048 endpoints whereas a 2D HyperX with 104 22 × 22 switches provides 10 648 endpoints. Using switches with radix 128, a two-level Fat-tree can support 8192 endpoints whereas a 2D HyperX with Dragonfly 102 3D HyperX 43 × 43 switches provides 79507 endpoints. Hence, Dragonfly (t=4) 2D HyperX among diameter-two topologies, 2D HyperX clearly Fat-Tree 2lvl outperforms leaf-spine Fat-trees in terms of scala100 0 50 100 150 200 250 bility. Number of ports per switch (Radix) Given this balance of cost, scalability, and simFigure 4: Scalability of HyperX and other topolo- plicity, this work focuses on the 2D HyperX topolgies. ogy as a strong candidate for future HPC systems. Moreover, the findings presented in this study can be naturally extended to 3D HyperX configuraspecifically allowing more than one deroute in the tions. same dimension. Thus, it allows each packet to perform up to q + m hops, where m is the non-minimal hops permitted, and q is the number of dimensions 3 Preliminaries on resource in the HyperX. For some adverse traffic patterns it allocation is necessary that m ≥ q to achieve acceptable performance, and m = q is always sufficient; this is The communication pattern of a parallel applicaassumed henceforth. The possible routes are illustrated in Figure 3. tion can be modeled as a graph, called the applicaFor aligned switches, (a), there is a single minimal tion graph, in which vertices represent the applicapath and all switches visited by any route belong tion’s ranks or processes, and edges connect pairs to the same row. For unaligned switches, (b), there of ranks that communicate. A vertex in the apare two minimal paths and any switch can be vis- plication graph is considered to occupy an entire endpoint. This could represent a MPI rank that ited by some route. uses multithreading (e.g., via OpenMP) to exploit all available cores on that endpoint. If modeling a 2.3 Scalability pure MPI application with multiple ranks per endA key advantage of HyperX is its ability to offer ex- point, each application vertex should instead reprecellent scalability at a relatively low cost. Figure 4 sent an aggregate of those ranks. Thus, an applicacompares the scalability of HyperX with other net- tion vertex abstracts the communication generated work topologies, such as Fat-tree and Dragonfly, and consumed by a single endpoint. In a parallel machine, the application graph must represented in Figure 1. The three top lines of the be mapped onto physical endpoints. First, the refigure correspond to topologies with diameter 3 and source allocation function selects a set of system the other two lines, at the bottom, to topologies of endpoints to host the application, forming the pardiameter 2. Note that the number of cables per tition. The process of mapping the application endpoint grows proportionally to the diameter. graph onto this partition is referred to as task mapWhile 3D HyperX is slightly less scalable than ping. As the term partition suggests, different Dragonfly, the latter typically requires trunking to applications are assigned disjoint partitions; that be implementable in practice, which means that is, practices such as co-location are not considered there are multiple links between groups. For examhere. ple, in the Frontier supercomputer, its Dragonfly network is implemented with a trunking factor of From a graph-theoretical perspective, the applit = 4, that is, there are 4 links between any pair of cation graph is the guest graph, which is embedgroups. It employs 2 464 switches with radix 64 to ded into the system topology or host graph. The provide 39424 endpoints connecting Network Inter- composition of the resource allocation function and face Cards (NICs) from the server’s GPUs. A 3D task mapping defines an embedding function that HyperX of dimensions 16 × 16 × 16 using switches maps vertices of the guest graph onto vertices of

Number of servers (NICS)

108

4

the dilation of the edge {A, B} ∈ E is defined as the length of a shortest path between f (A) and f (B) in G′ (V ′ , E ′ ).

process ranks 56–63 48–55 40–47

Therefore, key metrics for evaluating a resource allocation strategy include the average and maximum distances induced by the allocation function f within the selected system partition, or host graph. These metrics directly bound the dilation of any application graph mapped onto the host graph. Another important concept is convexity, which indicates whether an application is isolated, as it controls the interference between sets of switches. This property is formalized by the following definition.

32–39 24–31 16–23 8–15 0– 7

switches in a HX 7

zoom of switch 0,0 6 5 4 3

Definition 2 Let G = (V, E) be a graph. A set S ⊆ V is convex if for every pair of vertices in S, every minimal path joining them lies entirely within S. The set S is weakly-convex [4] if for every pair of vertices, at least one minimal path lies entirely within S.

servers

2 1 0

Figure 5: Inter-group communication from reduce scatter a la Rabenseifner of 64 processes with 8 We introduce next another property that indigroups of 8 processes each. Each group is mapped cates whether the set of endpoints of a switch is to the servers attached to one switch of a 8 × 8 associated to a single partition. HX. The 8 selected switches lie in a diagonal of the topology. Definition 3 A partition P is said to have switch locality if for every switch x connected to an endpoint in P, every endpoint connected to x is also in the host graph. When considering multiple appliP. A resource allocation function that provides parcations, the embedding can be considered jointly, titions with switch locality is called locality-aware. by taking as guest graph the disjoint union of all applications graphs. Note that the host graph repThe problem of resource allocation has been resents switches, but allocation units are endpoints. widely considered in well-known topologies, such Thus, the graph embedding is many-to-one, limited as Fat-tree, Torus and Dragonfly networks. Next, to the number of endpoints per switch. This ter- main findings are summarized to motivate the minology follows prior work and the functions we present study on HyperX resource allocation. provide are always defined on the vertices of multiple applications onto the set of network endpoints. 3.1 Fat-Tree Figure 5 illustrates the idea. The application graph can be inferred from the communication pattern Fat-tree topologies are widely used in HPC systems shown on the left, where each process communi- due to their high bisection bandwidth and path dicates with its neighbors in a hypercube graph. The versity, as demonstrated in large-scale systems such host graph corresponds to a 2D HyperX topology, as Eagle and Summit [26]. Fat-trees are non-blocking when fully utilized, aland under certain resource allocation function, the guest graph is mapped onto the set of endpoints be- lowing for flexible resource allocation without siglonging to the switches along the selected diagonal. nificant performance degradation. However, reDifferent strategies for resource allocation and source allocation in Fat-trees typically focuses on task mapping lead to distinct challenges and trade- packing jobs into subtrees to minimize interference offs. One particularly relevant concept for under- between applications [16]. A tree is a convex graph. A pod is technically standing the impact of these strategies is the dilation, which is already considered in [3, 27] and is just weakly-convex, as its top-level switches introadapted here for convenience in the following defi- duce indirect paths through the root layer. This is a consequence of applying graph-theoretic convexnition. ity to an indirect network and is not central to our Definition 1 Let f be a graph embedding of the discussion. When endpoints within the pod comgraph G(V, E) onto the graph G′ (V ′ , E ′ ). Then, municate, no link outside the pod is utilized. Thus, 5

convexity becomes a key consideration in Fat-tree allocations, as allocating jobs within convex subtrees helps isolate traffic and limit congestion propagation.

3.2

tal characteristic of these topologies is that, while achieving optimal throughput under uniform random traffic, they generally do not provide full bisection bandwidth, making the network susceptible to severe degradation under adversarial traffic. To mitigate this, adaptive, non-minimal routing is essential to redistribute load across all available links. Thus, resource allocation schemes that prioritize maximizing both minimal and non-minimal path diversity become crucial. For instance, a representative allocation policy for Dragonfly networks is LevelSpread [28]. In a full-sized Dragonfly, any pair of groups is connected by a single global link, which constitutes a bottleneck under heavy load. A poorly placed job can easily saturate these global links, severely impacting network performance. Allocating a job into just two groups causes half the endpoints of the job to be connected primarily through a single global link. Unlike conventional schemes, LevelSpread does not focus on minimizing dilation or preserving convexity. Instead, it maximizes available bandwidth by distributing tasks across multiple groups in a round-robin fashion when a job exceeds the capacity of a single group. However, when a job exactly fits within a single group, LevelSpread prioritizes compact placement inside the group, as the bisection bandwidth is high within a group, and this behaves similarly to a rearrangeably non-blocking subnetwork—assuming no external traffic is routed through it. Overall, allocation objectives in Dragonflies shift from minimizing dilation and enforcing convexity toward maximizing path diversity and bandwidth.

Torus

Torus networks have been widely used in systems such as Blue Gene, Fugaku, and Google TPU architectures [27, 21, 17]. Formally, a torus is defined as the Cartesian graph product of cycles. Figure 1 illustrates an example of a 3D torus. Torus topologies are particularly well-suited for applications that exhibit strong spatial locality. In such cases, the multi-dimensional structure of the torus helps to preserve communication locality and reduce contention. However, a significant challenge with torus networks is the potential for long communication paths. This makes dilation a particularly critical metric in Torus based systems, as increased dilation can directly lead to performance degradation. There are two main strategies for resource allocation in Tori: partitioning, which divides the network into mesh-like regions using regular cuts [11], and reconfiguration, which enables more flexible, disjoint partitions by dynamically reshaping the topology. The latter includes systems such as the IBM Blue Gene family and Google TPUv4. In these systems, resource-allocation consists of reconnecting, via link-chips or optical switches, basic blocks into a torus dedicated to the application [14, 17]. These basic blocks are meshes that span one or half a rack; some instances of used partitions can comprise up to 64 such blocks wired into a single Torus. Task mapping is approached geometrically as in the strategies based on partitioning, under the assump- 4 A Proposal of Allocation tion that the whole Torus is allocated to the appliFunctions for HyperX Netcation [27]. Other parallel machines, such as the Cray XK series, employ a Torus interconnect that works is not reconfigurable, limiting resource allocation to fixed partitions. In both cases, the goal is to Although both Dragonfly and HyperX are highradix, low-diameter networks, their internal orgaminimize dilation by allocating convex regions. nization differs significantly. While Dragonfly has high internal bandwidth inside each group and lim3.3 Dragonfly ited global bandwidth between groups, HyperX High-radix, low-diameter interconnects—such as uses a symmetrical structure with all-to-all connecDragonflies—are being increasingly used in modern tions without network bottlenecks and higher path HPC systems. Resource allocation in these high- diversity. Consequently, allocation strategies like radix topologies differs fundamentally from that of LevelSpread, designed for Dragonfly, do not apply to HyperX. Instead, HyperX opens new possibilities traditional networks. First, they are low-diameter networks, where the for resource allocation, shifting the focus toward exmaximum distance between any pair of switches is ploiting its symmetry and connectivity. This sectypically limited to 2 or 3 hops, values that bound tion presents the foundations of them. the dilation. Second, performance is primarily conAs stated before, we concentrate on the 2D Hystrained by bisection bandwidth. A fundamen- perX topology with diameter 2. In a system based 6

f (p, ry , rx ) = (sy , sx , c),

(1)

where • p denotes the partition identifier. rows

• (sy , sx ) denotes the decomposed coordinates of the physical switch s, such that s = sy · n + sx .

diagonal

• c denotes the local index of the endpoint connected to switch s (offset within the switch). Next, the proposed allocation policies are studied in terms of the nature of the mapping functions: linear, geometric-based or stochastic. rectangles

L-shapes

4.1

Linear

Resource

Allocation

Figure 6: Some linear and tile based partitions for Functions resource allocation. Each colored region is a set of 8 switches and 64 servers where a job can be A class of deterministic allocation functions that can be expressed as linear functions of the mapallocated. ping f (p, ry , rx ) = (sy , sx , c) are considered in this subsection. on this network, an application can request a parThe Row Selection function concentrates a partition of any size, but to simplify the present study tition’s resources within a single dimension of the we focus on partitions of size n2 . Thus, we assume switch grid. This function ensures that all enda scenario where a partition P is defined to contain points reside in switches sharing the same row, reexactly n2 endpoints. A representative example of sulting in a maximum partition distance of 1 hop. such a partition is a set of n switches, where each Formally, this corresponds to the identity function switch is connected to n different endpoints (a con- defined as: centration factor of n). In a 2D HyperX comprised of n × n switches row(p, ry , rx ) = (p, ry , rx ). with concentration n, the system capacity supIn contrast, the Full Spread function maximizes ports exactly n non-overlapping partitions of size n2 . Each partition Pp is uniquely identified by distribution by allocating exactly one endpoint p ∈ {0, . . . , n − 1}. Examples of such partitions from every switch in the system. This is achieved are represented in Figure 6 and will be later stud- by mapping the partition identifier to the local endied in detail. In practical implementations, these point offset, thereby exposing the partition to the mappings are built incrementally. As applications global bisection bandwidth of the topology: are launched, the resource manager identifies a parfull spread(p, ry , rx ) = (ry , rx , p). tition of idle nodes satisfying the requirements. Following this allocation, a secondary local task mapFinally, the Diagonal Selection function allocates ping function binds specific ranks from application resources along a topological diagonal. All interto the endpoints within the allocated partition. switch communication within the partition must We define the logical space inside of a partition traverse exactly 2 hops, representing the worst-case Pp by labeling its endpoints with a linear index r ∈ locality scenario for this topology: 2 {0, . . . , n − 1}. To map this linear space onto the network topology, it is advantageous to decompose diagonal(p, ry , rx ) = (ry , (ry + p) (mod n), rx ). r into a two-dimensional logical coordinate system using the Euclidean division: This resource allocation functions is the one employed in Figure 5. r = n · ry + rx , where 0 ≤ rx < n. Here, rx = r (mod n) and ry = ⌊r/n⌋. 4.2 Tiled Resource Allocation FuncAccordingly, the resource allocation policy is fortions malized as a mapping function f that translates these logical coordinates into physical topology co- Since the set of nodes of a HyperX can be natuordinates, rally set onto a grid, allocation functions based on 7

the vast majority of intra-partition communication pairs are at a distance of 2 hops, with a small fraction at distance 1 or 0. Alternatively, the Random Switch Selection function preserves switch locality while randomizing the selection of switches. Each application is placed on a partition of n random switches and their n2 total endpoints. By convention, let ry be used as selector of the switch and use rx to select the endpoint. Formally, let σ be a random permutation of the set {0, . . . , n − 1}2 of coordinates all the n2 switches. rectangular(p, ry , rx ) =
The allocation function is n rem(ry , 2)+ rem(p, 2), quo(ry , 2)+2 quo(p, 2), rx . 2 random switch(p, ry , rx ) = (sy , sx , rx ), Alternatively, the L-shape Tessellation function where (sy , sx ) = σ(p, ry ). allocates resources to a set of switches forming an orthogonal L-shaped structure. This shape is con- In contrast to the previous case, groups of n endstructed by uniting a vertical segment and a hori- points are at distance 0. However, the connectivity zontal segment that intersect at a common vertex between these switch groups remains randomized; (the partition anchor). The mapping function is de- thus, inter-switch traffic predominantly traverses 2 fined piecewise to distribute the logical coordinate hops, similar to the fully random approach. ry across these two arms: geometric tessellations of the grid are also included. Given the Cartesian structure of the 2D HyperX, valid resource partitions can be constructed by tiling the switch plane with compact geometric shapes. Unlike the linear functions, these strategies focus on forming contiguous or semi-contiguous 2D structures. The Rectangular Tessellation function partitions the network into compact rectangular blocks:

5

L shape(p, ry , rx ) = ( (p + ry , p, rx ), for ry < quo(n, 2), (p, p + ry − quo(n, 2) + 1, rx ), otherwise.

of

The allocation functions proposed in the previous section are intended to cover most reasonable strategies. In this section, the properties of the partitions resulting from these allocation functions are analyzed. Three aspects are considered: distance, convexity, and a new metric introduced by the authors, referred to as partition bandwidth. It should be noted that the HyperX topology admits many automorphisms [15], which makes some function formulations equivalent. The clearest example is the equivalence between Row and Column allocations. An equivalence also exists between Lshaped partitions and star-shaped partitions, that is, a central switch with four rays. Likewise, any diagonal partition is equivalent to any partition that selects exactly one switch in each row and each column.

Modular arithmetic (modulo n) is implicitly applied to the resulting switch coordinates. This configuration represents a compromise between dimension-ordered alignment and local clustering.

4.3

Topological Properties the Partitions

Randomized Resource Allocation Functions

Randomization techniques have been usually employed to balance the use of resources and avoid hotspots. Moreover, randomization may help to remove bias from artificial choices. Next, the resource allocation functions based on randomization are formalized. The Random Endpoint Selection function performs a complete scattering of resources, ignoring topological locality entirely. Let π be a random permutation of the set {0, . . . , n − 1}3 , the set of the 5.1 Distance properties coordinates of the n3 physical endpoints. That is, π sends each triplet to a randomly chosen triplet. The average and maximum distance of a partition The allocation function maps the linear index of the provide direct upper bounds on the average and requested resource directly to this permuted space: maximum dilation of an application placed on that partition. Moreover, uniform applications attain these distances as their dilation. Distances are also random endpoint(p, ry , rx ) = π(p, ry , rx ) fundamental for the analysis of other properties, Under this function, for any two endpoints from such as partition bandwidth, which is studied later. The impact of distances on performance is more the same partition, the probability they reside in the same switch is roughly 1/n2 and of residing in limited in a low-diameter topology such as HyperX the same dimension is about 2/n. Consequently, than in topologies such as a Torus. This does not 8

imply that distance is unimportant, as it may contribute up to a factor of two in performance variation; rather, it is not the dominant factor. For the same reason, the bounds relating dilation and distance are necessarily tighter. The average distance of the endpoints of a partition Pp , assuming that every source may have itself as destination, can be calculated as: DPp =

1 |Pp |

X e1 ,e2 ∈Pp

d(e1 , e2 ),

Random allocation functions inherit their distance metrics from the host topology. Indeed, due to linearity of expectation, the distance between two random endpoints matches the average distance of Full Spread, which is the average distance of the whole HyperX topology. Similarly, the average switch distance of Random Switch and Random Endpoint coincides with the average switch distance of the whole HyperX topology. And by the (2) above argument, for partitions with switch-locality it also coincides with the endpoint distance.

The term d(e1 , e2 ) denotes the number of switchto-switch links in a minimal path, as before. As the simplest case, Full Spread selects one endpoint from each switch, which implies that the average and maximum distance of the partition coincide with the average and maximum distance of the topology. This is an average distance of 2 − n2 and a diameter of 2 for the n × n HyperX. In the case of locality-aware allocation functions, it is natural to consider the distance at the switch level, denoted as DS , instead of the endpoint level. Let us find out that they match exactly. Denote by S the set of switches connected to the partition Pp , which has switch locality. Then, P the sum of the distances between endpoints is e1 ,e2 ∈Pp d(e1 , e2 ) = P 2 s1 ,s2 ∈S n d(s1 , s2 ). Rewriting this expression as average distances results |Pp |2 DPp = n2 |S|2 DS . Since n|S| = |Pp |, it follows that DPp = DS . Consequently, it is indistinct to use endpoint versus switch terminology for these functions. Following the same type of calculations, the maximum and average distances can be obtained for the rest of the allocation functions, as follows:

5.2

Convexity and locality

Convexity refers to whether the minimal paths between switches of a partition are contained inside it or not. If an application is mapped onto the endpoints of a convex set of switches, communications can be performed without affecting switches outside the set. This property can help to reduce interference, especially in well-established topologies such as Torus and Fat-tree, which typically employ minimal routing. However, in modern lowdiameter topologies, such as Dragonfly and HyperX, even when using convex partitions, employing non-minimal routes that extend beyond the partition may be critical for performance. The significance of this depends on the traffic pattern, and its feasibility depends on the routing algorithm used. Row, Full Spread, and Rectangular Tessellation functions provide convex partitions. In Full Spread, the partition comprises all the network switches, so it is trivially convex. With Row, each horizontal link corresponds to the unique minimal path between their endpoints. With Rectangular Tessellation, the partitions are smaller HyperX instances within the whole network. The Diagonal function is the archetype of nonconvexity since it enforces that there is no link between any switches of the partition. As an intermediate allocation function, Lshape Tessellation provides weakly-convex partitions. From the horizontal ray to the vertical ray the XY minimal path is contained, whereas the YX minimal path is not. In the opposite direction the ordering is reversed. Random functions provide non-convex partitions asymptotically almost surely except for the trivially convex cases comprising 0, 1 or n2 switches, and the weak-convex case of n2 − 1 switches. A Random Endpoint partition involves n2 switches when it comprises more than n2 log n endpoints. For the ongoing assumption of n2 endpoints, both random functions are non-convex. Almost all the allocation functions are localityaware, with the exception of the Random Endpoint

• Row selects all the endpoints in a row, which means that all pairs of switches are at maximum distance of 1 and average distance of 1 − 1/n. • With Diagonal, no two selected switches share the same row or column. Then, the value for the maximum distance is 2 and average distance is 2 − 2/n. • In a Rectangular Tessellation the distance values are those of the smaller allowed HyperX subgraph. This is, a maximum distance of 2 and an average distance of 2 − 1/na − 1/nb for a na × nb rectangle. • In L-shape Tessellation, average distance is roughly 1 + 1/2, as switches are divided into the two rays. Switches are at distance 1 when they are in the same ray and 2 when they are in different rays. 9

Selection function and Full Spread, which are the the whole topology with its n2 (n − 1) links, holding PBFull Spread = n. ones that share switches among partitions. For the Rectangle partition, let us consider the case in which one side doubles the pside for √ other 5.3 Partition Bandwidth the calculation. In general, this is 2n × n/2, inAs it will be seen in Section 7, neither distance cluding the 4 × 2 case used later in the experimennor convexity are topological properties of the par- tation. The bound (3) gives PBRectangle ≤ 2√32n , titions that enable a correct interpretation of the but the available bandwidth is lesser since there empirical results. For filling this gap, a new metric are proportionally fewer links along the shortest is introduced next. We define partition bandwidth, dimension. Instead, the bound can be applied denoted as PB, to the greatest rate at which load for each dimension, thus getting PBRectangle = could be generated by every endpoint of a parti- min{PB √ H , PBV }1.5= PBV . The partition comprises tion, with uniform destinations across such par- √2n n/2
∼ n√ vertical links, and the vertical 2 2 2 p tition, and employing minimal routing. The PB metric gives an idea of how much total traffic could average distance1 is 1 − 1/ n/2. This results in manage a partition before reaching its saturation PBRectangle = √2n . The convex hull of an L-shape partition compoint. To estimate the maximum bandwidth that a partition can support, computing PB assumes an prises those links incident into the L-shape that are idealistic scenario in which the endpoints of a par- within the smallest rectangle that contains the Ltition can send uniform traffic across such partition shape. Consider the ray with n/2 switches beyond 2 at an unlimited rate. In other words, it indicates the center. Its n /2 endpoints, generating messages how well the partition is provisioned in total band- half
the time in the same ray, are able to fit the n/2 links within. Approximately the same for the width. The PB metric leverages the following defi2 other ray. It can be seen that routing all other nition. messages to the outside, also fit the outgoing links, Definition 4 Given a graph G = (V, E), the con- giving PBL-shape ≈ 1. This asymptotically matches vex hull of a subset S of the vertices is the subgraph the value provided by (3). With respect to random mappings, intuitively, induced by those edges in a shortest path between Random Switch can be thought to be similar to vertices in S. Diagonal. The chance of having aligned switches Only the links belonging to the convex hull of a is small, giving an average distance close to 2 and partition can be employed to compute its partition using most links of each switch. However, the link bandwidth. Assuming all links are full-duplex, the utilization is not asymptotically 1. The number maximum traffic load in the partition cannot exceed of rows covered by some switch is asymptotic to twice the number of links in its convex hull, denoted n(1 − e−1 ). This limits the number of available as 2L. Since each packet injected by each endpoint links, resulting in PBRandom Switch ∼ 2(1 − e−1 ) ≈ of a partition traverses an average of DPp links, the 1.26. Finally, Random Endpoint is similar to Full following expression bounds its bandwidth. Spread. In this case, almost every link belongs to 2L (3) the convex hull, but again, not in an asymptotic PB ≤ 2 n DPp sense. The number of switches in the partition is about n2 (1−e−1 ), and for a link to be in the convex For symmetric cases, in which every link of the hull it is enough for any endpoint to belong to the convex hull is used in the same proportion, it is obpartition. The chance for a link to belong to the  2 tained that this upper bound is actually an equality. n2 (1−e−1 ) = 1 − e−2 . 2 This means that every endpoint within the parti- convex hull is then 1 − 1 − n tion could inject, at most, PB phits/cycle before The available bandwidth is then seen to be asympsaturating the partition. The PB values of the dif- totic to PBRandom Endpoint ∼ n(1 − e−2 ) ≈ 0.86n. ferent partitions are considered next. Since the convex hull of a Row partition is a com
n(n−1) 5.4 Partition’s topological propern plete graph of n switches, it has 2 = links. 2 ties summary This gives PBRow = n2n(n−1)/2 2 ·(n−1)/n = 1. In a Diagonal partition there are four times the The findings of the previous analysis are summalinks of the previous case, that is, 2n(n − 1), and rized in Table 1. The content of the table, comparthe average distance is the double, which results in ing the different partitions, reveals insights that will PBDiagonal = 2. The convex hull of Full Spread is be contrasted against empirical results in Section 7. 10

Table 1: Properties of the allocation functions and the partitions they provide. Considering partitions of n2 endpoints. Rough round approximation for distance and partition bandwidth. Allocation function Row Diagonal Full Spread L-shape Tessellation Rectangular Tessellation Random Endpoint Random Switch

Function type linear linear linear tiling tiling random random

Avg. distance 1 2 2 1 + 1/2 2 2 2

Max. distance 1 2 2 2 2 2 2

With respect to distance properties, all partitions but Row and L-shape, share the same values. However, this up to ×2 improvement is overshadowed by bandwidth shortcomings. With respect to the convexity of partitions, there are three convex cases, other three non-convex and one more which is weakly-convex. Nevertheless, convexity loses some of its value when non-minimal routing has to be employed. This is the case of HyperX, in which partitions are naturally disturbed by remote traffic injected by other partitions. Larger differences can be observed with respect to partition bandwidth. Both Row partition and L-shape have PBRow = PBL-shape = 1, Rectangular has PBRectangular < 1 and the remainder partitions have PB > 1. This means that in Row, with a PB value of exactly 1, endpoints could inject uniform traffic at full rate. Remember that the actual network injection rate is 1 phit/cycle/endpoint. Injecting at this maximum rate means that there is no slack to absorb neither any external traffic nor any traffic non-uniformities in the partition, making the approach fragile. It could be good when all applications generate uniform traffic and fit nicely within a single row, provided that the routing is simple or guided enough to keep traffic confined to that row. It becomes limited when dealing with non-uniform traffic loads. Diagonal partition has PBDiagonal = 2, which ensures that, even injecting at full rate, the partition is able to manage twice as much traffic. This is an advantage for dealing with remote traffic in a fully utilized machine. In fact, it would be possible to handle adversarial traffic loads within a single partition at full rate by de-routing traffic through randomly selected switches across the partition. In spite of its non-convex nature, Diagonal partition is a strong candidate for maximizing global throughput. Full Spread, with PBFull Spread = n, is a straightforward approach to ensure that all links in the network are utilized. However, it disregards switch locality and could result in complete interference. Random partitions have also PB > 1. Random 11

Convexity convex non-convex convex weakly-convex convex non-convex non-convex

locality-aware yes yes no yes yes no yes

PB 1 2 n 1 √ 1/ 2n n(1 − e−2 ) 2(1 − e−1 )

Switch Selection is close to Diagonal in all parameters and Random Endpoint selection is close to Full Spread. Both have, however, a notable decrease in the number of links in their convex hull due to the expected coincidences. They can be a little worse, in general, than their deterministic counterparts.

6

Experimental Methodology

In order to compare the proposed allocation techniques, an exhaustive experimental evaluation will be conducted. The evaluation will consist of measuring the performance of different applications over a HyperX, in which the allocation strategy changes. First, the set of employed workloads is described and analyzed. Second, the experimental setup is detailed along with the two frameworks considered to evaluate the allocation functions. Lastly, the simulated scenarios are outlined.

6.1

Simulated Workloads

Two kind of synthetic workloads are considered: static traffic patterns and kernels of real applications. The static traffic patterns are used to carry a preliminary analysis, while the kernels of real applications are used to validate the conclusions in a more realistic scenario. 6.1.1

Static traffic patterns

Messages used by these patterns are generated at a rate of 1 phit/cycle/endpoint, which is the maximum injection rate of the network. The patterns considered are: • Uniform Random. Each message is sent to a randomly selected destination within the same partition, with uniform (independent and identical) probability. It represents a benign scenario, where minimal routing is expected to perform well. • Random Permutation. Each task sends messages to a unique destination, forming a random permutation of the tasks. This pattern

is more challenging than the uniform random, as it creates a more structured load that can lead to congestion if not properly managed.

Table 2: Simulation Parameters Parameter Switch Internal Speedup Allocator Packet Size Input Buffer Size Output Buffer Size Number of VCs

Value 2× Random 16 flits 8 packets per VC 4 packets per VC 4 per port

• Random Switch Permutation. Individual tasks are organized into groups of n tasks, and between those groups a random permutation is applied. So, each group of tasks send messages only to another group of tasks. This pattern is extremely adversarial, as groups of tasks are mapped into unique switches when the allocation function preserves switch-locality and task tern. Stencil patterns represent one-to-many commapping is linear. It requires the use of nonminimal routes to achieve good performance in munication, where each process interacts with its neighbors in a bidimensional space. The neighmost partitions. bor patterns used are von Neumann Neighborhood, in which communication occurs with immediate 6.1.2 Communication kernels of real applineighbors in the four cardinal directions, and Moore cations Neighborhood, where communication extends to diThey have been selected as representative kernels of agonal neighbors. Stencil patterns are prevalent in communication patterns commonly found in HPC scientific computing applications. Like the all-toand AI workloads. The selection was guided by ref- all operation, the communication can be organized erences from prior studies, and all chosen applica- in multiple rounds, allowing a more uniform and tions are characterized by intensive network usage. efficient use of the network. In the Random Involution, data is exchanged Next, they are detailed and their communication between randomly paired processes, as typically ocneeds are discussed. curs in applications using unstructured or irregular The All-to-All MPI collective is a fundamengrids, such as those arising in the finite element tal operation in which every process communicates method. with all other processes in the system. It is widely used in numerical applications such as the Fast Fourier Transform (FFT) and in AI applications 6.2 Experimental Setup based on model parallelism. When performed over k processes, each rank performs a number of steps One goal of the present study is to experimentally multiple of k − 1. At step i, rank r sends data evaluate the resource allocation strategies described to rank r + i mod k, and receives data from rank in the previous sections. This evaluation is done usr−i mod k. Each rank sends and receives indepen- ing the CAMINOS simulator [10, 9]. CAMINOS is dently from the other ranks in a completely asyn- an event-driven network simulator that operates at chronous manner. The operation completes once flit granularity and models the switch microarchievery task has exchanged messages with all other tecture. The parameters considered in each simutasks, thereby distributing the network load evenly. lation are detailed in Table 2. Employing a larger amount of steps entails smaller The network evaluated is a 2D HyperX with 8×8 chunks of data at every step, which makes the re- switches, 8 endpoints per switch, giving a total of sulting communication more uniform. It is adjusted 512 endpoints. All the resource allocation strateto make each chunk fit into a single packet. gies defined in Section 4 are considered. To assess The All-Reduce operation is a collective com- these strategies, the traffic patterns and application munication pattern where all processes contribute communication kernels described in previous subdata, and a reduction operation (e.g., sum, max, section are used. The kernels are generated with min) is applied to produce a single result dis- three different sizes: 64, 128 and 256-process aptributed back to all processes. This pattern is plications. For applications with 64 processes the critical in large-scale machine learning workloads. partitions are exactly as described in Section 4. For The algorithm used is the optimal Rabenseifner al- applications with a number of processes multiple of gorithm [24]. In this approach, processes are ar- 64, a partition consists on the union of consecutive ranged in a hypercube, and the algorithm has two blocks that would be partitions for 64. For example, phases (Scatter-Reduce and All-Gather) of log k Row Selection with 128 processes makes partitions steps each. Variants of the algorithm for non- of two consecutive rows. In the case of 256-process power-of-two process counts follow a similar pat- applications, the Row strategy allocates four com12

plete rows, which coincides with the 8 × 8 × 4 rectangle from the Rectangular Selection, and the later is omitted. The routing algorithm employed is OmniWAR [22]. However, minimal adaptive routing, MIN, is employed for a preliminary study. Occupancy-based prioritization is performed, this is, the queue with least occupancy is selected, with deroutes being given an extra occupancy penalty, P , of 64 phits to discourage its use. Other routing algorithms, such as Polarized routing [8] have been also evaluated but not reported in this paper for brevity. Due to the nature of Polarized routing, the differences between the resource allocation strategies are less pronounced, but the conclusions drawn are consistent with those obtained with Omni-WAR. Two different frameworks are considered: interference analysis and single-application scaling. In the interference analysis scenario, one target application is allocated in the network and its completion time is measured. Background noise is generated with the remaining endpoints, sending traffic as a Random Permutation. In the singleapplication scaling scenario, k replicas of the same application are launched and the makespan (time until all replicas complete) is measured. The replica count increases from k = 1 up to the maximum that fits in the 512-server system. This maximum size is 8, 4, and 2 for applications of 64, 128, and 256 processes, respectively.

patterns Uniform and Random Permutation. Secondly, an interference analysis is performed using Omni-WAR routing, with Uniform and Random Switch Permutation traffic patterns. In this case, the background noise is generated using a Random Permutation. In both scenarios, applications are conformed by 64 processes. The use of MIN routing for the interference analysis scenario is not considered, as it would not be able to handle the adversarial traffic patterns nor load balance the load.

6.3

To remove head of line (HoL) blocking and isolate partitions from each other, each partition is given its own set of virtual channels. Thus, each partition is provided with 4 unique virtual channels. So, for example, in the case of 8 replicas of a 64-process application, which occupies all the 512 endpoints, there are 8 partitions and each partition has its own set of 4 virtual channels, giving a total of 32 virtual channels per switch port.

Analyzed scenarios

Traffics with different characteristics can lead to different performance results for the same resource allocation strategy. In addition, resource allocation strategies are very sensitive to other network characteristics, such as the number of virtual channels used. So, to ensure that the conclusions drawn are robust and not specific to a particular configuration, the performance of the different strategies is evaluated under different scenarios. 6.3.1

Static traffic analysis

Simulations with static traffic are carried out to analyze the performance of the different strategies under controlled conditions. Furthermore, simulations using both MIN routing and Omni-WAR are carried out to confirm that the different strategies yield different performance results, and that the choice of the allocation function is relevant for the performance of applications. So, two scenarios are considered: the first one is a single-application scaling using MIN routing and employing the traffic 13

6.3.2

Kernel traffic analysis

The performance of the different resource allocation strategies is evaluated using the communication kernels described. Two scenarios are considered, as before. The first one is a single-application scaling of the kernels and the second, an interference analysis, in which the performance of one application is measured under the presence of a global background noise generated by a Random Permutation. For both scenarios the size of the application varies from 64 to 256 processes, and the makespan is measured for up to 8 replicas of the application, depending on its size. However, to draw specific conclusions not all the simulations are reported, but only a subset are shown to illustrate the main points of the analysis, and a summary of the results is provided in the form of tables. 6.3.3

7

Fabric partitioning

Experimental Results

This section is organized into three different subsections. Subsection 7.1 is devoted to show the relevance of the resource allocation strategies, by comparing their performance under MIN and OmniWAR routing with simple synthetic traffic patterns. Subsection 7.2 is based on the communication kernels and uses Omni-WAR routing. It has two parts, the first one considering the escalation of a unique application, and the second, showing the behavior of one application when it experiences interference from a global background noise. Subsection 7.3 is

Diagonal L-shape Full-Spread

Random Switch Row Selection

Rectangular Random Endpoint

Diagonal L-shape Full-Spread

Random Switch Row Selection

Rectangular Random Endpoint

·105

·105

4 3 Cycles

Cycles

4

2

Random permutation

0 0

2

4

6

2 1

8

Allocated Kernels ·105

0 Uniform

Cycles

3 2

Figure 8: Makespan of 64-process kernels with Omni-WAR routing. The light-colored bars show the time running isolated and the dark part shows the extra time taken due to the interference.

1

Uniform

0 0

2

4

6

Random Switch Perm

8

Allocated Kernels

Figure 7: Makespan for load escalation of 64processes kernels with MIN routing, allocating in seen, Random and Full Spread are the worst stratethe network from 1 to 8 replicas of the same app in gies as the ones most troubled by interference and HoL blocking. Then Rectangles, L-shapes, Rows each chart. and Random Switch Selection follow, with similar performance. Finally, Diagonal is the best strategy, devoted to show equivalent results but using more as it is more robust to interference than Full-Spread and Random, and maintains a high Partition Bandvirtual channels. width.

7.1

Static traffic analysis

In Figure 7 MIN is used, and it can be observed that the choice of the resource allocation strategy has a significant impact on application performance. Rectangles is the worst strategy in both traffic patterns, next Random Switch Selection, L-shapes and Rows follow, and lastly Diagonal, Random Endpoint and Full Spread are the best strategies, with similar performance. It can be observed that, due to the asymmetry of the partition, the performance of Random Switch Selection is worse than expected under Uniform traffic pattern. Here, the routing algorithm is not able to properly load balance the traffic, and some switches have to handle more traffic than others, which leads to unfairness between the endpoints of the partition and a decrease in performance. An ideal routing algorithm with global knowledge of the traffic would be able to balance the traffic across the network and achieve better performance, but MIN is not able to do so. The performance of the different strategies is consistent with the Partition Bandwidth values shown in Table 1. In Figure 8 it can be observed the performance of the different strategies for Uniform and Random Switch Permutation with the presence of background noise generated with a Random Permutation. Omni-WAR routing is used. As it can be 14

7.2

Kernel traffic analysis

7.2.1

Application escalation

The application escalation study has been done considering 64, 128 and 256-process applications. For brevity only the case of 64 processes is shown in Figure 9, since it presents the most interesting situations due to the differences observed. However, all the experiments are also summarized in Table 3. The best strategies are close to Diagonal allocation across all configurations. For this reason, values in the table are normalized with respect to it. Full Spread and Random Endpoint occasionally achieve slightly higher mean speedups (up to about 1.05) at 50% load, but the differences are small and tend to disappear at 100% load. Random Switch is close to Diagonal but Rectangular is clearly worse. Row and L-shape consistently exhibit mean slowdowns, particularly for 64–128 ranks and at 50% occupancy. In summary, in these experiments, Full Spread, Random Endpoint, Diagonal and Random Switch selection functions form a group of high-quality strategies with similar behaviour across applications and loads, whereas Row, L-shape Tessellation and Rectangular selection functions are clearly less favorable in terms of average execution time. Lastly, with bigger applications, the differences are

·105

·105

·105

1.5

1

0.5 2

4

6

1 0.5

All-reduce 0

Cycles

Cycles

Cycles

1.5

8

All2All 0

2

Allocated Kernels

4

6

8

1.5 1 0.5

RandomInvolution 0

Allocated Kernels

·104 1.2

Cycles

Cycles

1 5 4 3

Stencil von Neumann 0

2

4

6

8

Allocated Kernels

0.8 0.6 0.4

Stencil Moore 0

2

4

6

4

8

Allocated Kernels

·105

Cycles

Diagonal Selection Rectangular Tessellation Row Selection Full-Spread

2

Random Switch L-shape Tessellation Random Endpoint

1 0 All2All

RandomInvolution Stencil von Neumann

Stencil Moore

All-reduce

Figure 10: Makespan for different 64-process kernels. Background traffic is a random permutation. The light-colored bars show the time running isolated and the dark part shows the extra time taken due to the interference.

15

8

Diagonal Selection Random Switch Rectangular Tessellation L-shape Tessellation Row Selection Random Endpoint Full-Spread

Figure 9: Makespan for load escalation of 64-processes kernels with Omni-WAR routing, allocating in the network from 1 to 8 replicas of the same app in each chart.

3

6

Allocated Kernels

·105

6

2

less pronounced.

64 ranks

Diagonal R. Switch Rect. L-shape Row R. Endpoint Full S.

128 ranks

100%

50%

100%

50%

100%

1.00 0.99 0.88 0.77 0.74 1.02 1.05

1.00 0.93 0.88 0.88 0.93 1.00 1.00

1.00 0.95 0.89 0.87 0.77 0.99 1.02

1.00 0.96 0.99 0.97 0.94 1.03 1.03

1.00 0.98 0.91 0.87 1.01 1.03

1.00 0.97 0.97 0.96 1.02 1.02

Rectangular Tes. Random Endpoint Sel.

3

256 ranks

50%

Random Switch Sel. Row Selection

·105

Cycles

Table 3: Average performance of each strategy normalized to the performance of Diagonal Selection. Employing Omni-WAR routing. Including values for a half-occupied and a completely-filled system.

Diagonal Sel. L-shape Tes. Full-Spread

2 1 0 Uniform

Random Switch Perm

Figure 11: Makespan of 64-process kernels providing a different VC set to the background traffic. The dark part shows the extra time taken due to the interference over running isolated.

Table 4: Average slowdown in the interference analysis scenario of each allocation function normalized not reported here for brevity, as they yielded simito the performance of Diagonal Selection. lar conclusions to the other cases. 64 ranks

128 ranks

1.00 0.90 0.84 0.78 0.70 0.66 0.66

1.00 0.98 0.93 0.96 0.93 0.80 0.76

Diagonal Selection Random Switch Selection Rectangular Tessellation L-shape Tessellation Row Selection Random Endpoint Selection Full Spread

7.2.2

7.3

Interference analysis

Figure 10 reports the per-application interference experiments, and Table 4 condenses them into the mean slowdown of each strategy relative to Diagonal for 64 and 128 ranks. The observed differences indicate that the choice of mapping becomes notable, and that Diagonal is the most robust strategy on average, with Random Switch as a reasonable alternative. The robustness of a partition must be understood as the ability to remain as immune as possible to external traffic interferences. For 64 ranks, Diagonal is substantially faster than Rectangular, Random Endpoint, Full Spread, L-shape and Row allocation functions, while Random Switch Selection is closer. At 128 ranks, differences are smaller but the same trend holds, with Random Endpoint and Full Spread occupying the last positions. In this respect, in Section 7.3 it is shown how the addition of costly VCs can mitigate the effects of interference in both Full Spread and Random Endpoint, improving their performance and outperforming the other strategies. Simulations with 256 ranks were also conducted but are 16

Fabric partitioning

Figures 11 and 12 show interference analysis results with more virtual channels, for both basic traffic and kernel traffic. The addition of virtual channels has a significant impact on the performance of the different strategies, particularly for those that are more sensitive to HoL blocking, such as Full Spread and Random Endpoint Selection. With more virtual channels, these strategies are able to separate different traffic flows and reduce contention for resources, leading to improved performance. Full Spread and Random Endpoint outperform Diagonal, which was previously the best strategy. This highlights the importance of considering virtual channel configurations when evaluating resource allocation strategies in HyperX networks. Nevertheless, the number of virtual channels must be kept as small as possible due to cost and power constraints.

8

Lessons Learned

In this section lessons learned from the experimentation are established and explained in the light of the topological characteristics of the partitions. Lesson 1: The HyperX topology demands for new resource allocation strategies. The experimental results confirm that the most relevant performance metric for a resource allocation strategy is strongly topology-dependent, and

·105 Diagonal Selection Rectangular Tessellation Row Selection Full-Spread

Cycles

2

Random Switch L-shape Tessellation Random Endpoint

1

0 All2All

RandomInvolution Stencil von Neumann

Stencil Moore

All-reduce

Figure 12: Makespan of 64-process kernels providing a different VC set to the background traffic. The light-colored bars show the time running isolated and the dark part shows the extra time taken due to the interference. that heuristics effective in Tori, Fat-trees, and Dragonflies do not transfer directly to HyperX. As discussed in Section 3, allocation strategies in Tori are designed to minimize dilation. If dilation were also the dominant factor in HyperX, Row allocation—in which all endpoints are at distance one—would be expected to perform best. However, experiments show several cases in which Row exhibits the worst performance, most notably for Random Involution and All-reduce patterns. In the same way, L-shapes, which also provide low average distance, yield poor results in most scenarios. These observations indicate that, unlike in Tori, minimizing dilation alone is not sufficient in HyperX. A similar deviation is observed when comparing HyperX versus Fat-tree networks. In Fat-trees, convexity of allocated partitions is a key property for job placement, as it helps isolate partition traffic by exploiting the hierarchical network structure. In HyperX, by contrast, non-convex partitions can provide better performance: for example, Diagonal, which is non-convex, consistently outperforms convex strategies such as Row and Rectangular in most scenarios, as shown experimentally. Furthermore, when interference is evaluated, the Row strategy—despite allocating convex partitions—fails to isolate traffic effectively due to nonminimal routes going through target application partition, leading to significant performance degradation. Lastly, although resource allocation for Dragonflies aims to maximize bandwidth, its strategies do not carry over directly. As recalled in Section 3, Dragonfly allocation policies typically either pack an application within a single group or spread it across the network using as few endpoints per group as possible. The natural analogues in HyperX would be to place small applications within a single row (Row allocation) and to use a strategy 17

such as Full Spread for large applications. However, for applications of size 64—i.e., those that would fit in a single “group” (row or column)—Row performs clearly poorly. In addition, Full spread alone leads to a bad performance in interference scenarios limited to 4VCs, as shown in Figure 8. Altogether, these results indicate that, while dilation is the central metric in Tori, convexity in Fat-trees, and bandwidth in Dragonflies, HyperX requires dedicated allocation strategies and cannot rely on a direct reuse of those devised for other topologies. Lesson 2: Partition Bandwidth emerges as a key performance indicator. Bandwidth availability and its distribution across the topology appear as decisive aspects. In low interference scenarios, Full Spread, Random Endpoint, Diagonal and Random Switch strategies are, in this order, the schemes that provide the highest empirical throughput to the allocated application, as Table 3 shows. The measured values are quite close but they are clearly better than the others. This perfectly correlates with the values provided by the theoretical partition bandwidth metric, PB, introduced in Subsection 5.3. In the same order and particularized for n = 8, Full Spread, Random Endpoint, Diagonal, and Random Switch have a PB of 8.0, 5.1, 2.0, and 1.3, respectively. The other three strategies, Rectangular, L-shape and Row, have PB ≤ 1. The impact of the partition bandwidth is more pronounced at lower occupancy levels, where contention is reduced and the benefits of higher throughput allocations can be fully exploited. For instance, the maximum speedup of Diagonal over other strategies across all applications is 2.16 with one application allocated and 2.30 with half the

endpoints allocated, under RandomInvolution traffic, and 1.30 with all endpoints allocated under All2All traffic, as shown in Figure 9. All other experiments show similar trends, confirming that partition bandwidth availability is a key factor in determining the effectiveness of a resource allocation strategy in HyperX networks. Lesson 3: Under certain demanding load conditions, strategies that do not preserve switch locality result in lower performance due to interference and HoL blocking. Partition Bandwidth alone is not capable of estimating the performance of each allocation strategy, especially in scenarios under high interference. It is the combination of partition bandwidth along with the HoL blocking and interference patterns that determines the performance of each strategy. While all allocation strategies benefit from low system occupancy, the impact of interferences becomes evident as the load increases and competition for switches and links is intense. Full Spread and Random Endpoint create partitions that do not preserve switch-locality, this is, they share switches with other concurrent workloads. Consequently, applications allocated via these methods provoke higher interferences than using partitions that preserve switch-locality, resulting in lower performance. In contrast, all other strategies do preserve switch-locality, being Diagonal and Random Switch the ones exhibiting better performance, as shown in Figure 10. Lesson 4: If fabric partitioning is used to isolate application traffic, strategies which maximize partition bandwidth are the best. Partitions such as Full Spread and Random Endpoint achieve the highest PB; however, they often suffer from significant HoL blocking because they do not preserve switch locality, spreading applications across the entire network. By implementing virtual channels to isolate flows, this HoL blocking is mitigated. This allows the high bandwidth potential of these strategies to be fully exploited, resulting in superior performance. In contrast, strategies like Row do not see similar performance gains from virtual channels, as their low partition bandwidth remains its primary bottleneck.

graph constructions, such as Dragonfly or Dragonfly+. These networks stand out for their favorable distance properties, good scalability, and notable cost–performance ratio. Regarding their deployment as system networks in the market, several works have explored how to address practical challenges in these topologies, including routing [22] and fault tolerance [7]. In the present study, the authors focus on the problem of partitioning and resource allocation, given its potential impact on performance, as previously observed in Torus and Dragonfly-type networks. To this end, different resource allocation functions for HyperX networks have been modeled, taking into account algebraic, geometric, and stochastic aspects. For these functions, several relevant properties have been characterized, namely dilation, convexity, and the resulting local bandwidth. In addition, an extensive experimental evaluation of the different strategies has been conducted under two increasingly realistic scenarios: from the scaling behavior of a single application to a setting in which interference among multiple applications running simultaneously on the system is evaluated. Considering these theoretical and experimental results, the article provides a set of lessons learned that serve as guidelines for the implementation of resource allocation policies in HyperX based systems. Although the HyperX topology proves to be largely immune to suboptimal decisions in this respect, choosing an effective routing algorithm or selecting the most stable allocation policy can still yield performance gains of up to 2.30×. The article focuses exclusively on partitioning 2D HyperX networks. However, 3D HyperX networks can also benefit from this study, as our methodology should extend naturally to higher dimensions. For example, it is clear that functions based on algebraic criteria—such as linear functions—or those based on random permutations can be defined without difficulty in q dimensions. In summary, the study presented in this article provides yet another reason for HyperX networks to be regarded as excellent alternatives to be used in forthcoming HPC systems.

Acknowledgment

This work has been supported by the Spanish Ministry of Science and Innovation under contracts PID2022-136454NB-C21 and RYC2021-033959-I, 9 Conclusions the European HiPEAC Network of Excellence, and HyperX networks are presented as efficient alter- the Barcelona Supercomputing Center under connatives to other topologies based on complete- tract CONSER02023011NG. 18

References

[10] CAMINOS. caminos.

https://crates.io/crates/

[1] Sriram Aananthakrishnan, Shamsul Abedin, Vincent Cavé, Fabio Checconi, Kristof [11] Mehmet Deveci, Sivasankaran Rajamanickam, Vitus J Leung, Kevin Pedretti, Stephen L Du Bois, Stijn Eyerman, Joshua B Fryman, Olivier, David P Bunde, Umit V Catalyürek, Wim Heirman, Jason Howard, Ibrahim Hur, and Karen Devine. Exploiting geometric partiet al. The intel programmable and integrated tioning in task mapping for parallel computers. unified memory architecture graph analytics In 2014 IEEE 28th international parallel and processor. IEEE Micro, 43(5):78–87, 2023. distributed processing symposium, pages 27–36. [2] Jung Ho Ahn, Nathan Binkert, Al Davis, IEEE, 2014. Moray McLaren, and Robert S. Schreiber. HyperX: Topology, routing, and packaging of ef- [12] Jens Domke, Satoshi Matsuoka, Ivan R. ficient large-scale networks. In Proceedings of Ivanov, Yuki Tsushima, Tomoya Yuki, Akithe Conference on High Performance Computhiro Nomura, Shin’ichi Miura, Nic McDonald, ing Networking, Storage and Analysis, SC ’09, Dennis L. Floyd, and Nicolas Dubé. HyperX pages 1–11, New York, NY, USA, 2009. ACM. topology: First at-scale implementation and comparison to the fat-tree. In Proceedings of [3] R. Aleliunas and A.L. Rosenberg. On embedthe International Conference for High Perfording rectangular grids in square grids. IEEE mance Computing, Networking, Storage and Transactions on Computers, 31(09):907–913, Analysis, SC ’19, New York, NY, USA, 2019. September 1982. Association for Computing Machinery. [4] Bijo S Anand, Jonecis A Dayap, Leomarich F [13] Greg Faanes, Abdulla Bataineh, Duncan Casinillo, Karen Luz P Yap, et al. ReRoweth, Tom Court, Edwin Froese, Bob Alvervisiting the outer-weakly convex domination son, Tim Johnson, Joe Kopnick, Mike Higgins, number in graph products. arXiv preprint and James Reinhard. Cray Cascade: a scalarXiv:2501.15524, 2025. able HPC system based on a dragonfly network. In Proceedings of the International Con[5] Laxmi N. Bhuyan and Dharma P. Agrawal. ference on High Performance Computing, NetGeneralized hypercube and hyperbus strucworking, Storage and Analysis, SC ’12, pages tures for a computer network. Computers, 1–9, Los Alamitos, CA, USA, November 2012. IEEE Transactions on, C-33(4):323–333, April IEEE Computer Society Press. 1984. [14] Alan Gara, Matthias A Blumrich, Dong Chen, GL-T Chiu, Paul Coteus, Mark E Giampapa, Ruud A Haring, Philip Heidelberger, Dirk Hoenicke, Gerard V Kopcsay, et al. Overview of the Blue Gene/L system architecture. IBM Journal of research and development, 49(2.3):195–212, 2005.

[6] Norman Biggs. Algebraic graph theory. Cambridge university press, 1993.

[7] Cristóbal Camarero, Alejandro Cano, Carmen Martı́nez, and Ramón Beivide. Achieving high-performance fault-tolerant routing in HyperX interconnection networks. In SC24W: Workshops of the International Conference for High Performance Computing, Net- [15] F Harary and EM Palmer. On the automorphism group of a composite graph. Studia Sci. working, Storage and Analysis, pages 472–483, Math. Hungar, 3:439–441, 1968. 2024. [8] Cristóbal Camarero, Carmen Martı́nez, and [16] Ana Jokanovic, Jose Carlos Sancho, German Rodriguez, Alejandro Lucero, Cyriel MinkenRamón Beivide. Polarized routing: an effiberg, and Jesus Labarta. Quiet neighborhoods: cient and versatile algorithm for large direct Key to protect job performance predictabilnetworks. In 2021 IEEE Symposium on Highity. In 2015 IEEE International Parallel and Performance Interconnects (HOTI), pages 52– Distributed Processing Symposium, pages 449– 59, 2021. 459, 2015. [9] Cristóbal Camarero, Daniel Postigo, and Pablo Fuentes. The CAMINOS interconnec- [17] Norm Jouppi, George Kurian, Sheng Li, Petion networks simulator. Journal of Parallel ter Ma, Rahul Nagarajan, Lifeng Nai, Nishant and Distributed Computing, 204:105136, 2025. Patil, Suvinay Subramanian, Andy Swing, 19

Brian Towles, et al. TPU v4: An optically re- [26] Erich Strohmaier, Jack Dongarra, Horst Siconfigurable supercomputer for machine learnmon, and Martin Meuer. TOP500 list of suing with hardware support for embeddings. In percomputer sites, November 2025. Proceedings of the 50th annual international symposium on computer architecture, pages 1– [27] Hao Yu, I-Hsin Chung, and José E. Moreira. Topology mapping for Blue Gene/L supercom14, 2023. puter. In SC 2006 Conference, Proceedings of [18] John Kim, William J. Dally, and Dennis Abts. the ACM/IEEE, November 2006. Flattened butterfly: a cost-efficient topology for high-radix networks. In Proceedings of the [28] Yijia Zhang, Ozan Tuncer, Fulya Kaplan, Katzalin Olcoz, Vitus J Leung, and Ayse K 34th annual international symposium on ComCoskun. Level-spread: A new job allocaputer architecture, ISCA ’07, pages 126–137, tion policy for dragonfly networks. In 2018 New York, NY, USA, 2007. ACM. IEEE International Parallel and Distributed [19] John Kim, William J. Dally, Steve Scott, Processing Symposium (IPDPS), pages 1123– and Dennis Abts. Technology-driven, highly1132. IEEE, 2018. scalable dragonfly topology. In Proceedings of the 35th Annual International Symposium on Computer Architecture, pages 77–88. IEEE Computer Society, 2008. [20] Laurence E. LaForge, Kirk F. Korver, and M. Sami Fadali. What designers of bus and network architectures should know about hypercubes. Computers, IEEE Transactions on, 52(4):525–544, April 2003. [21] Satoshi Matsuoka. Fugaku and A64FX: the first exascale supercomputer and its innovative Arm CPU. In 2021 Symposium on VLSI Circuits, pages 1–3. IEEE, 2021. [22] Nic McDonald, Mikhail Isaev, Adriana Flores, Al Davis, and John Kim. Practical and efficient incremental adaptive routing for HyperX networks. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’19, New York, NY, USA, 2019. Association for Computing Machinery. [23] Henry Martyn Mulder. Interval-regular graphs. Discrete Mathematics, 41(3):253–269, 1982. [24] Rolf Rabenseifner. Optimization of collective reduction operations. In Computational Science-ICCS 2004: 4th International Conference, Kraków, Poland, June 6-9, 2004, Proceedings, Part I 4, pages 1–9. Springer, 2004. [25] Alexander Shpiner, Zachy Haramaty, Saar Eliad, Vladimir Zdornov, Barak Gafni, and Eitan Zahavi. Dragonfly+: Low cost topology for scaling datacenters. In 2017 IEEE 3rd International Workshop on High-Performance Interconnection Networks in the Exascale and Big-Data Era (HiPINEB), pages 1–8. IEEE, 2017. 20