• LUGH is a new buffer architecture for Dragonfly Interconnection Networks. • LUGH achieves high performance and fairness in Dragonfly networks. • A theoretical model to compare the fairness of buffer architectures has been obtained. • Theoretical throughput calculations align with simulation results. • LUGH is a cost-effective solution which outperforms other VC mechanisms in most scenarios. Dragonfly networks offer a viable solution for large-scale supercomputers and datacenters. However, developing efficient routing mechanisms for these networks presents significant challenges. Current solutions often lead to unstable network behavior due to congestion and fairness issues, exacerbating performance variability and the tail-latency problem. An analysis of the topology and its standard deadlock avoidance mechanisms reveals that server access to global network links varies based on their location in the network, resulting in throughput unfairness. To address this issue, this paper introduces a novel switch buffer architecture which reduces head-of-line blocking and enhances fairness, to significantly improve overall network performance. Despite offering comparable cost to existing solutions, the proposed buffer architecture proves superior performance. Real-world synthetic simulations scenarios further confirm these findings, showing performance improvements between 10 % and 47 % against conventional solutions in medium sized Dragonflies.

High-radix, low-diameter networks like HyperX and Dragonfly use a Full-mesh core, and rely on multiple virtual channels (VCs) to avoid packet deadlocks in adaptive routing. However, VCs introduce significant overhead in the switch in terms of area, power, and design complexity, limiting the switch scalability. This paper starts by revisiting VC-less routing through link ordering schemes in Full-mesh networks, which offer implementation simplicity but suffer from performance degradation under adversarial traffic. Thus, to overcome these challenges, we propose TERA (Topology-Embedded Routing Algorithm), a novel routing algorithm which employs an embedded physical subnetwork to provide deadlock-free non-minimal paths without using VCs. In a Full-mesh network, TERA outperforms link ordering routing algorithms by 80% when dealing with adversarial traffic, and up to 100% in application kernels. Furthermore, compared to other VC-based approaches, it reduces buffer requirements by 50%, while maintaining comparable latency and throughput. Lastly, early results from a 2D-HyperX evaluation show that TERA outperforms state-of-the-art algorithms that use the same number of VCs, achieving performance improvements of up to 32%. Index Terms-Deadlock-free routing, Full-mesh, virtual channels, adaptive routing.

Abstract Since today’s HPC and data center systems can comprise hundreds of thousands of servers and beyond, it is crucial to equip them with a network that provides high performance. New topologies proposed to achieve such performance need to be evaluated under different traffic conditions, aiming to closely replicate real-world scenarios. While most optimizations should be guided by common traffic patterns, it is essential to ensure that no pathological traffic pattern can compromise the entire system. Determining synthetic adversarial traffic patterns for a network typically relies on a thorough understanding of its topology and routing. In this paper, we address the problem of identifying a generic adversarial traffic pattern for low-diameter direct interconnection networks. We first focus on Random Regular Graphs (RRGs), which represent a typical case for these networks. Moreover, RRGs have been proposed as topologies for interconnection networks due to their superior scalability and expandability, among other advantages. We introduce Ant Mill, an adversarial traffic pattern for RRGs when using routes of minimal length. Secondly, we demonstrate that the Ant Mill traffic pattern is also adversarial in other low-diameter direct interconnection networks such as Slimfly, Dragonfly, and Projective networks. Ant Mill is thoroughly motivated and evaluated, enabling future studies of low-diameter direct interconnection networks to leverage its findings.

To interconnect their growing number of servers, current supercomputers and data centers are starting to adopt low-diameter networks, such as HyperX, Dragonfly and Dragonfly+. These emergent topologies require balancing the load over their links and finding suitable non-minimal routing mechanisms for them becomes particularly challenging. The Valiant load balancing scheme is a very popular choice for non-minimal routing. Evolved adaptive routing mechanisms implemented in real systems are based on this Valiant scheme. All these low-diameter networks are deadlock-prone when non-minimal routing is employed. Routing deadlocks occur when packets cannot progress due to cyclic dependencies. Therefore, developing efficient deadlock-free packet routing mechanisms is critical for the progress of these emergent networks. The routing function includes the routing algorithm for path selection and the buffers management policy that dictates how packets allocate the buffers of the switches on their paths. For the same routing algorithm, a different buffer management mechanism can lead to a very different performance. Moreover, certain mechanisms considered efficient for avoiding deadlocks, may still suffer from hard to pinpoint instabilities that make erratic the network response. This paper focuses on exploring the impact of these buffers management policies on the performance of current interconnection networks, showing a 90% of performance drop if an incorrect buffers management policy is used. Moreover, this study not only characterizes some of these undesirable scenarios but also proposes practicable solutions.

Supercomputer and datacenter networks can comprise hundreds of thousands of severs. Focusing on direct networks, different topologies have been proposed to attain such a high scalability, from Flattened Butterfly and Dragonfly to the most disruptive approach represented by Jellyfish, which is based on a random interconnection pattern. The routing problem on such networks remains a challenge that can be tackled as a topology aware solution, or with an agnostic approach. The case of random networks is a very special one because of the lack of an acceptable routing algorithm for them since no a priori topological clues can be exploited. In this paper, we introduce the Polarized Routing Algorithm, an adaptive non-minimal hop-by-hop mechanism for direct networks that can be used in a number of topologies, including Jellyfish. Polarized routing was conceived following two design criteria: a source-destination symmetry in the routes to enable load-balancing and to avoid undoing previously taken hops. A thorough experimentation shows Polarized routing constitutes an efficient and versatile solution, attaining the highest performance both in benign scenarios under uniform traffic patterns and in adverse ones on the tested networks. Interestingly, this algorithm provides important performance gains of more than 30% in the Jellyfish topology, for different traffic patterns, when compared to the state of the art solutions.

Large computer systems, like those in the TOP 500 ranking, comprise about hundreds of thousands cores. Simulating application execution in these systems is very complex and costly. This article explores the option of using application skeletons, together with an analytic simulator, to study the performance of these large systems. With this aim, the Dimemas simulator has been enhanced with the capability of simulating application skeletons. This enhancement allows simulating the skeleton of Lulesh, an application with 90k processes in a single day. In addition, it also generates traces, which is of great value to validate skeletons and simulations.

Big scale, high performance and fault-tolerance, low-cost and graceful expandability are pursued features in current datacenter networks (DCN). Although there have been many proposals for DCNs, most modern installations are equipped with classical folded Clos networks. Recently, regular random topologies, as the Jellyfish, have been proposed for DCNs. However, their completely unstructured nature entails serious design problems. In this paper we propose Random Folded Clos (RFC) and Hydra networks in which the interconnection between certain switches levels is made randomly. Both RFCs and Hydras preserve important properties of Clos networks that provide a straightforward deadlock-free multi-path routing. The proposed networks leverage randomness to be gracefully expandable, thereby allowing for fine grain upgrading. RFCs and Hydras are compared in the paper, in topological and cost terms, against fat-trees, orthogonal fat-trees and random regular networks. Also, experiments are carried out to simulate their performance under synthetic traffic patterns emulating common loads present in warehouse scale computers. These theoretical and empirical studies reveal the interest of these topologies, concluding that Hydra constitutes a practicable alternative to current datacenter networks since it appropriately balance all the main design requirements. Moreover, Hydras perform better than the fat-trees, their natural competitor, being able to connect the same or more computing nodes with significant lower cost and latency while exhibiting comparable throughput.

In datacenter networks, big scale, high performance and faulttolerance, low-cost, and graceful expandability are pursued features. Recently, random regular networks, as the Jellyfish, have been proposed for satisfying these stringent requirements. However, their completely unstructured design entails several drawbacks. As a related alternative, in this paper we propose Random Folded Clos (RFC) networks. They constitute a compromise between total randomness and maintaining some topological structure. As it will be shown, RFCs preserve important properties of Clos networks that provide a straightforward deadlock-free equal-cost multi-path routing and enough randomness to gracefully expanding. These networks are minutely compared, in topological and cost terms, against fat-trees, orthogonal fat-trees and random regular graphs. Also, experiments are carried out to simulate their performance under synthetic traffics that emulate common loads in datacenters. It is shown that RFCs constitute an interesting alternative to currently deployed networks since they appropriately balance all the important design requirements. Moreover, they do that at much lower cost than the fat-tree, their natural competitor. Being able up to connect the same number of compute nodes, saving up to 95% of the cost, and giving similar performance.

The interconnection network comprises a significant portion of the cost of large parallel computers, both in economic terms and power consumption. Several previous proposals exploit large-radix routers to build scalable low-distance topologies with the aim of minimizing these costs. However, they fail to consider potential unbalance in the network utilization, which in some cases results in suboptimal designs. Based on an appropriate cost model, this paper advocates the use of networks based on incidence graphs of projective planes, broadly denoted as Projective Networks. Projective Networks rely on generalized Moore graphs with uniform link utilization and encompass several proposed direct (PN and demi-PN) and indirect (OFT) topologies under a common mathematical framework. Compared to other proposals with average distance between 2 and 3 hops, these networks provide very high scalability while preserving a balanced network utilization, resulting in low network costs.

A construction of two-quasi-perfect Lee codes is given over the space ℤnpfor p prime, p ≡ ±5 (mod 12), and n = 2[p/4]. It is known that there are infinitely many such primes. Golomb and Welch conjectured that perfect codes for the Lee metric do not exist for dimension n ≥ 3 and radius r ≥ 2. This conjecture was proved to be true for large radii as well as for low dimensions. The codes found are very close to be perfect, which exhibits the hardness of the conjecture. A series of computations show that related graphs are Ramanujan, which could provide further connections between coding and graph theories.

In the late years many different interconnection networks have been used with two main tendencies. One is characterized by the use of high-degree routers with long wires while the other uses routers of much smaller degree. The latter rely on two-dimensional mesh and torus topologies with shorter local links. This paper focuses on doubling the degree of common 2D meshes and tori while still preserving an attractive layout for VLSI design. By adding a set of diagonal links in one direction, diagonal networks are obtained. By adding a second set of links, networks of degree eight are built, named king networks. This research presents a comprehensive study of these networks which includes a topological analysis, the proposal of appropriate routing procedures and an empirical evaluation. King networks exhibit a number of attractive characteristics which translate to reduced execution times of parallel applications. For example, the execution times NPB suite are reduced up to a 30 percent. In addition, this work reveals other properties of king networks such as perfect partitioning that deserves further attention for its convenient exploitation in forthcoming high-performance parallel systems.

Torus networks of moderate degree have been widely used in the supercomputer industry. Tori are superb when used for executing applications that require near-neighbor communications. Nevertheless, they are not so good when dealing with global communications. Hence, typical 3D implementations have evolved to 5D networks, among other reasons, to reduce network distances. Most of these big systems are mixed-radix tori, which are not the best option for minimizing distances and efficiently using network resources. This paper is focused on improving the topological properties of this kind of networks. By using integral matrices to deal with Cayley graphs over Abelian groups, we have been able to propose and analyze a family of high-dimensional mesh-based interconnection networks. As they are built over n-dimensional grids that induce a regular tiling of space, these topologies have been denoted lattice graphs. Higher dimensional networks can be composed over these graphs by means of a lift operation, which is also introduced in the paper. Easy network partitioning and minimal routing algorithm are also provided for these topologies based on this new network operation. Later we focus on cubic crystal lattices for modeling symmetric 3D networks and to show how lattice graphs can help in the design of twisted interconnection networks. In all cases, the networks obtained are better, in topological terms, than their standard tori counterparts. Finally, some practical issues such as implementability and preliminary performance evaluations have been addressed at the end of this work.

A complete family of Cayley graphs of degree four, denoted as L-networks, is considered in this paper. L-networks are 2D mesh-based topologies with wrap-around connections. L-networks constitute a graph-based model which englobe many previously proposed 2D interconnection networks. Some of them have been extensively used in the industry as the underlying topology for parallel and distributed computers of different scales. Tori, twisted and doubly twisted tori, toroidal diagonal meshes, chordal rings, and circulant graphs are, among others, members of the L-network family. Therefore, many results obtained in previous studies on these networks can be deduced from the general framework presented in this work. In addition, the network model presented in this work allows for new results on the domain of low-degree interconnection networks. Particularly, closed expressions for the graph distance properties have been derived and an optimal routing algorithm of constant complexity is provided. Since symmetry has a big impact on network performance, we have also identified which L-networks are symmetric by studying their group of automorphisms. Finally, a very simple model that predicts the performance of L-networks is also presented. Such model has been contrasted with empirical evaluation.

The problem of searching for perfect codes has attracted great attention since the paper by Golomb and Welch, in which the existence of these codes over Lee metric spaces was considered. Since perfect codes are not very common, the problem of searching for quasi-perfect codes is also of great interest. In this aspect, also quasi-perfect Lee codes have been considered for 2-D and 3-D Lee metric spaces. In this paper, constructive methods for obtaining quasi-perfect codes over metric spaces modeled by means of Gaussian and Eisenstein-Jacobi integers are given. The obtained codes form ideals of the integer ring thus preserving the property of being geometrically uniform codes. Moreover, they are able to correct more error patterns than the perfect codes which may properly be used in asymmetric channels. Therefore, the results in this paper complement the constructions of perfect codes previously done for the same integer rings. Finally, decoding algorithms for the quasi-perfect codes obtained in this paper are provided and the relationship of the codes and the Lee metric ones is investigated.

In this paper we consider perfect codes over two dimensional QAM-type constellations of any cardinal. Such constellations are going to be modeled by L-graphs, which are the two-dimensional family of multidimensional circulants, defined. We show that Gaussian graphs, Lee graphs and the Kronecker product of two cycles are included in this family. Therefore, our method to obtain perfect codes over these lattice subsets is a generalization of the techniques for searching perfect two-dimensional Lee codes and perfect codes over the Kronecker products of two cycles. In addition, we introduce some previously unreported perfect codes.

Many current parallel computers are built around a torus interconnection network. Machines from Cray, HP, and IBM, among others, make use of this topology. In terms of topological advantages, square (2D) or cubic (3D) tori would be the topologies of choice. However, for different practical reasons, 2D and 3D tori with different number of nodes per dimension have been used. These mixed-radix topologies are not edge symmetric, which translates into poor performance due to an unbalanced use of network resources. In this work, we analyze twisted 2D and 3D mixed-radix tori that remove the network bottlenecks present in nontwisted ones. Such topologies recover edge symmetry, and consequently, balance the utilization of their links. The distance-related properties of twisted tori together with a full characterization of their bisection bandwidth are described in this paper. A simulation-based performance evaluation has been carried out to assess the network performance under synthetic and trace-driven workloads. The obtained results show noticeable and consistent performance gains (up to an increase of 74 percent in accepted load). In addition, we propose scalable and practicable packet routing mechanisms and wiring layouts for these interconnection systems. The complexity of the architectural proposals is similar to the one exhibited by routing and folding mechanisms in standard tori.

The search for perfect error-correcting codes has received intense interest since the seminal work by Hamming. Decades ago, Golomb and Welch studied perfect codes for the Lee metric in multidimensional torus constellations. In this work, we focus our attention on a new class of four-dimensional signal spaces which include tori as subcases. Our constellations are modeled by means of Cayley graphs defined over quotient rings of Lipschitz integers. Previously unexplored perfect codes of length one will be provided in a constructive way by solving a typical problem of vertices domination in graph theory. The codewords of such perfect codes are constituted by the elements of a principal (left) ideal of the considered quotient ring. The generalization of these techniques for higher dimensional spaces is also considered in this work by modeling their signal sets through Cayley-Dickson algebras.

In order to propose a new metric over QAM constellations, diagonal Gaussian graphs defined over quotients of the Gaussian integers are introduced in this paper. Distance properties of the constellations are detailed by means of the vertex-to-vertex distribution of this family of graphs. Moreover, perfect codes for this metric are considered. Finally, notable subgraphs of diagonal Gaussian graphs are studied which leads to relate the proposed metric to other well-known graph-based metrics such as the Lee distance.

In this paper we consider a broad family of toroidal networks, denoted as Gaussian networks, which include many previously proposed and used topologies. We will define such networks by means of the Gaussian Integers, the subset of the Complex numbers with integer real and imaginary parts. Nodes in Gaussian networks are labeled by Gaussian integers, which confer these topologies an algebraic structure based on quotient rings of the Gaussian integers. In this sense, Gaussian integers reveal themselves as the appropriate tool for analyzing and exploiting any type of toroidal network. Using this algebraic approach, we can characterize the main distance-related properties of Gaussian networks, providing closed expressions for their diameter and average distance. In addition, we solve some important applications, like unicast and broadcast packet routing or the perfect placement of resources over these networks.

Many parallel computers use Tori interconnection networks. Machines from Cray, HP and IBM, among others, exploit these topologies. In order to maintain full network symmetry, 2D and 3D Tori must have the same number of nodes (k) per dimension resulting in square or cubic topologies. Nevertheless, for practical reasons, computer engineers have designed and built 2D and 3D Tori having a different number of nodes per dimension. These mixed-radix topologies are not edge-symmetric which translates into poor performance provoked by an unbalanced use of the network links. In this paper, we propose and analyze twisted 2D and 3D Tori which remove the network bottlenecks present in mixed-radix standard Tori. These new topologies recover edge-symmetry and, consequently, balance the utilization of their links. We describe the distance-related parameters of these twisted networks and use simulation to asses their performance under synthetic loads. The obtained results show noticeable and consistent performance gains. In addition, we propose scalable and practicable packet routing and folding techniques for these interconnection subsystems. The complexity of the resulting architectural solutions is similar to the one exhibited by traditional routing and folding mechanisms employed in standard Tori. This fact together with the performance improvements obtained could justify the use of these twisted topologies in the future.

Cayley graphs over quotients of the quaternion integers are going to be used to define a new metric over four dimensional lattices. We will consider perfect 1-error correcting codes according to this metric space. We will show that, in some cases, these lattices can be represented as two-dimensional constellations, which allow us to state a relation between the Lee metric and this new Lipschitz metric.

An algebraic methodology for defining new metrics over two-dimensional signal spaces is presented in this work. We have mainly considered quadrature amplitude modulation (QAM) constellations which have previously been modeled by quotient rings of Gaussian integers. The metric over these constellations, based on the distance concept in circulant graphs, is one of the main contributions of this work. A detailed analysis of some degree-four circulant graphs has allowed us to detail the weight distribution for these signal spaces. A new family of perfect codes over Gaussian integers will be defined and characterized by providing a solution to the perfect t-dominating set problem over the circulant graphs presented. Finally, we will show how this new metric can be extended to other signal sets by considering hexagonal constellations and circulant graphs of degree six.

In this paper we present perfect codes for two-dimensional constellations derived from generalized Gaussian graphs, a family of graphs built over quotient rings of Gaussian integers. Using the generalized Gaussian graphs distance, we solve the problem of finding t-dominating sets and, then, we build new perfect codes over these graphs. The well-known perfect Lee codes can be viewed as a particular subcase of the perfect Gaussian codes introduced in this work

The basis for designing error-correcting codes for two dimensional signal sets is considered in this paper. Both, algebraic and graph-theoretical approaches are employed in this research for establishing the fundamentals of these codes. We give a solution to the t-dominating set problem in a subfamily of degree four circulant graphs which directly provides perfect codes over the Gaussian integers. In order to show the applicability of our results, simple examples for designing different coding schemes are also presented