Low-diameter network topologies require non-minimal routing, such as Valiant routing, to avoid network congestion under challenging traffic patterns like the so-called adversarial. However, this mechanism tends to increase the average path length, base latency, and network load. The use of shorter non-minimal paths has the potential to enhance performance, but it may also introduce congestion depending on the traffic patterns. This article introduces LIA (Latency-Improved Adaptive), a routing mechanism for Dragonfly networks which dynamically exploits minimal and non-minimal paths. LIA harnesses the traffic counters already present in contemporary switches to determine when it is safe to shorten non-minimal paths and to adjust routing decisions based on their information about the network conditions. Evaluations reveal that LIA achieves nearly optimal latency, outperforming state-of-the-art adaptive routing mechanisms by reducing latency by up to 30% while maintaining stable throughput and fairness.

The integration of many processing elements per die makes it more difficult to provide low latency in the Network-on-Chip (NoC). Multihop bypass proposals, such as SMART, attack this problem by allowing flits to skip multiple routers in the path in a single cycle, drastically reducing latency while preserving a regular tiled layout. However, multihop bypass routers are more complex and relatively different from traditional NoC routers, since they rely on global broadcast signals and global allocation mechanisms. Additionally, the maximum number of nodes that can be bypassed within a single cycle is limited by the Critical Path Delay (CPD) of the NoC. Hence, a practical multihop bypass mechanism must also minimize this delay.

Many-core processors demand scalable, efficient and low latency NoCs. Bypass routers are an affordable solution to attain low latency in relatively simple topologies like the mesh. SMART improves on traditional bypass routers implementing multi-hop bypass which reduces the importance of the distance between pairs of nodes. Nevertheless, the conservative buffer reallocation policy of SMART requires a large number of Virtual Channels (VCs) to offer high performance, penalizing its implementation cost. Besides, SMART zero-load latency values highly depend on HPCMaxHPCMax, the maximum number of hops that can be jumped per cycle. In this article, we present Speculative-SMART++ (S-SMART++), with two mechanisms that significantly improve multi-hop bypass. First, zero-load latency is reduced by speculatively setting consecutive multi-hops. Second, the inefficient buffer reallocation policy of SMART is reduced by combining multi-packet buffers, Non-Empty Buffer Bypass and per-packet allocation. These proposals are evaluated using functional simulation, with synthetic and real loads, and synthesis tools. S-SMART++ does not need VCs to obtain the performance of SMART with 8 VCs, reducing notably logic resources and dynamic power. Additionally, S-SMART++ reduces the base-latency of SMART by at least 29.2 percent, even when using the biggest HPCMaxHPCMaxpossible.

Network-on-Chips are a critical part of modernmultiprocessors and their relevance will grow with the number ofcores. The development of future NoC designs relies on detailedsimulation models that accurately estimate their performance, power and hardware cost. Bypass routers are very relevant and promising proposals dueto their improved performance. Bypass routers reduce latencythanks to a combination of speculation, pre-routing (lookaheadrouting) and buffer bypass, which also reduce energy consumption by avoiding unnecessary buffer writes and reads. Multi-hop bypass NoCs, known as SMART, even bypass the crossbar of multiple routers in a single cycle. However, publicly available NoC simulators, such as BookSim or Garnet, do not implement bypass mechanisms or do not model them accurately. In this work, we present Bypass Simulation Toolset(BST), a set of tools to accurately simulate NoCs with single-and multi-hop bypass routers. BST combines and extends several simulation tools: an extension of BookSim with state-of-the-art cycle-accurate bypass router models and additional flow control mechanisms; an RTL implementation of multi-hop bypass mechanisms based on OpenSMART; an API to ease a modular integration of the BST NoC simulator in full system simulators; and a set of scripts to automate simulation execution and data collection. To showcase BST, we i) validate BookSim SMART models with the RTL implementation; ii) compare bypass and traditional non-bypass router models; iii) integrate BookSim in gem5 using the proposed API and compare it with gem5's Simple and Garnet 2.0 NoC models; and iv) present a case study evaluating different combinations of router types and topologies recently proposed for NoCs, highlighting the flexibility of the BST toolset. The toolset is available at www.atc.unican.es/software.html.

Low latency and low implementation cost are two key requirements in NoCs. SMART routers implement multi-hop bypass, obtaining latency values close to an ideal point-to-point interconnect. However, it requires a significant amount of resources such as Virtual Channels (VCs), which are not used as efficiently as possible, preventing bypass in certain scenarios. This translates into increased area and delay, compared to an ideal implementation.

Summary Low‐diameter networks require non‐minimal adaptive routing to deal with varying traffic characteristics and avoid pathological performance. Such routing is based on local estimations of network congestion, based on link‐level flow control credits. Dragonfly networks based on the extensions of commodity Ethernet networks using OpenFlow have been proposed for large HPC deployments with low power consumption. However, this network technology does not implement credit‐based flow control. This work explores a range of routing solutions based on exploiting explicit congestion notification messages (in particular, 802.1Qau) to adapt the number of packets using non‐minimal paths. The design (denoted QCN‐Switch) associates a probability value to each output port. This value is updated to reflect downstream congestion and used to statistically divert traffic away from congested areas when the load is uneven, as in the case of adversarial traffic. A feedback comparison variant is designed to separate the cases of uniform traffic at saturation and adversarial traffic at low loads. Evaluation results show that QCN‐Switch is a competitive design for both the uniform traffic and adversarial traffic. Furthermore, it is able to react to changes in traffic conditions in 0.4 ms or less. A sensitivity analysis identifies the best configuration and shows its performance trade‐offs.

The growing complexity of multi-core architectures has motivated a wide range of software mechanisms to improve the orchestration of parallel executions. Task parallelism has become a very attractive approach thanks to its programmability, portability and potential for optimizations. However, with the expected increase in core counts, finer-grained tasking will be required to exploit the available parallelism, which will increase the overheads introduced by the runtime system. This work presents Task Dependence Manager (TDM), a hardware/software co-designed mechanism to mitigate runtime system overheads. TDM introduces a hardware unit, denoted Dependence Management Unit (DMU), and minimal ISA extensions that allow the runtime system to offload costly dependence tracking operations to the DMU and to still perform task scheduling in software. With lower hardware cost, TDM outperforms hardware-based solutions and enhances the flexibility, adaptability and composability of the system. Results show that TDM improves performance by 12.3% and reduces EDP by 20.4% on average with respect to a software runtime system. Compared to a runtime system fully implemented in hardware, TDM achieves an average speedup of 4.2% with 7.3x less area requirements and significant EDP reductions. In addition, five different software schedulers are evaluated with TDM, illustrating its flexibility and performance gains.

Deadlock avoidance mechanisms for lossless lowdistance networks typically increase the order of virtual channel (VC) index with each hop. This restricts the number of buffer resources depending on the routing mechanism and limits performance due to an inefficient use. Dynamic buffer organizations increase implementation complexity and only provide small gains in this context because a significant amount of buffering needs to be allocated statically to avoid congestion. We introduce FlexVC, a simple buffer management mechanism which permits a more flexible use of VCs. It combines statically partitioned buffers, opportunistic routing and a relaxed distancebased deadlock avoidance policy. FlexVC mitigates Head-of-Line blocking and reduces up to 50% the memory requirements. Simulation results in a Dragonfly network show congestion reduction and up to 37.8% throughput improvement, outperforming more complex dynamic approaches. FlexVC merges different flows of traffic in the same buffers, which in some cases makes more difficult to identify the traffic pattern in order to support nonminimal adaptive routing. An alternative denoted FlexVCminCred improves congestion sensing for adaptive routing by tracking separately packets routed minimally and nonminimally, rising throughput up to 20.4% with 25% savings in buffer area.

Summary The Graph500 benchmark attempts to steer the design of High‐Performance Computing systems to maximize the performance under memory‐constricted application workloads. A realistic simulation of such benchmarks for architectural research is challenging due to size and detail limitations. By contrast, synthetic traffic workloads constitute one of the least resource‐consuming methods to evaluate the performance. In this work, we provide a simulation tool for network architects that need to evaluate the suitability of their interconnect for BigData applications. Our development is a low computation‐ and memory‐demanding synthetic traffic model that emulates the behavior of the Graph500 communications and is publicly available in an open‐source network simulator. The characterization of network traffic is inferred from a profile of several executions of the benchmark with different input parameters. We verify the validity of the equations in our model against an execution of the benchmark with a different set of parameters. Furthermore, we identify the impact of the node computation capabilities and network characteristics in the execution time of the model in a Dragonfly network.

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.

Managing criticality in task-based programming models opens a wide range of performance and power optimization opportunities in future manycore systems. Criticality aware task schedulers can benefit from these opportunities by scheduling tasks to the most appropriate cores. However, these schedulers may suffer from priority inversion and static binding problems that limit their expected improvements. Based on the observation that task criticality information can be exploited to drive hardware reconfigurations, we propose a Criticality Aware Task Acceleration (CATA) mechanism that dynamically adapts the computational power of a task depending on its criticality. As a result, CATA achieves significant improvements over a baseline static scheduler, reaching average improvements up to 18.4% in execution time and 30.1% in Energy-Delay Product (EDP) on a simulated 32-core system. The cost of reconfiguring hardware by means of a software-only solution rises with the number of cores due to lock contention and reconfiguration overhead. Therefore, novel architectural support is proposed to eliminate these overheads on future manycore systems. This architectural support minimally extends hardware structures already present in current processors, which allows further improvements in performance with negligible overhead. As a consequence, average improvements of up to 20.4% in execution time and 34.0% in EDP are obtained, outperforming state-of-the-art acceleration proposals not aware of task criticality.

High-performance computing (HPC) is recognized as one of the pillars for further progress in science, industry, medicine, and education. Current HPC systems are being developed to overcome emerging architectural challenges in order to reach Exascale level of performance, projected for the year 2020. The much larger embedded and mobile market allows for rapid development of intellectual property (IP) blocks and provides more flexibility in designing an application-specific system-on-chip (SoC), in turn providing the possibility in balancing performance, energy-efficiency, and cost. In the Mont-Blanc project, we advocate for HPC systems being built from such commodity IP blocks, currently used in embedded and mobile SoCs. As a first demonstrator of such an approach, we present the Mont-Blanc prototype; the first HPC system built with commodity SoCs, memories, and network interface cards (NICs) from the embedded and mobile domain, and off-the-shelf HPC networking, storage, cooling, and integration solutions. We present the system's architecture and evaluate both performance and energy efficiency. Further, we compare the system's abilities against a production level supercomputer. At the end, we discuss parallel scalability and estimate the maximum scalability point of this approach across a set of applications.

Dragonfly networks have a two-level hierarchical arrangement of the network routers, and allow for a competitive cost-performance solution in large systems. Non-minimal adaptive routing is employed to fully exploit the path diversity and increase the performance under adversarial traffic patterns. Throughput unfairness prevents a balanced use of the resources across the network nodes and degrades severely the performance of any application running on an affected node. Previous works have demonstrated the presence of throughput unfairness in Dragonflies under certain adversarial traffic patterns, and proposed different alternatives to effectively combat such effect. In this paper we introduce a new traffic pattern denoted adversarial consecutive (ADVc), which portrays a real use case, and evaluate its impact on network performance and throughput fairness. This traffic pattern is the most adversarial in terms of network fairness. Our evaluations, both with or without transit-over-injection priority, show that global misrouting policies do not properly alleviate this problem. Therefore, explicit fairness mechanisms are required for these networks.

Exascale systems will require large networks with hundreds of thousands of endpoints. Ethernet technology is employed in a significant fraction of the Top500 systems, and will remain as a cost-effective alternative for HPC interconnection. However, its current design is not scalable to Exascale systems. Different solutions have been proposed for scalable Ethernet fabrics for data center, but not specifically for HPC applications. This work identifies the major differences in network requirements from both environments. Based on them, it studies the application of Ethernet to Exascale HPC systems, considering the topology, routing, forwarding table management, and address assignment, with a focus on performance and power. Our scalability solution relies on OpenFlow switches to implement hierarchical MAC addressing with the introduction of compaction mechanisms for TCAM table reduction. To simplify deployment, a protocol denoted DMP performs automated address assignment without interfering with layer-2 service announcement protocols. An analysis of latency requirements of HPC applications shows that their communication phases are very short, making controller-centric adaptive routing unfeasible. We introduce Conditional OpenFlow rules as an instrument which allows for adaptive routing with proactive rule instantiation. Routing decisions are taken in the switch depending on network status, without controller interaction. This mechanism supports multiple topologies which require minimal or non-minimal adaptive routing and improve performance and power. Altogether, this work introduces a realistic and competitive implementation of a scalable lossless Ethernet network for Exascale-level HPC environments, considering low-diameter and low-power topologies such as Flattened Butterflies or Dragonflies, and allowing for power savings up to 54%.

Dragonfly topologies are one of the most promising interconnect designs for enabling large, potentially exascale compute systems, particularly those envisioned to accommodate workloads that are sensitive to system diameter and end-to-end latency. They are cost-effective designs with a very low diameter and close to optimal performance for workloads which induce a balanced load across the network. However, these benefits are balanced by a reduced path diversity, which leaves Dragonflies vulnerable to certain adversarial traffic patterns. The performance of such workloads can be significantly improved using indirect routing approaches. However, the indirect routing approach that is most commonly used today exhibits in turn significant vulnerability to a subset of these traffic patterns for reasons that have not been, up to now entirely, understood. In exploring this vulnerability, we manage to provide a theoretical justification, based on inherent properties of the Dragonfly topology, of why performance degrades. Furthermore, we manage to isolate what specifically in the structure of a traffic pattern makes it a worst case in this context, and thus we are able to characterize the precise workload subset that will experience poor performance. By building upon the understanding of the interaction that causes sub-optimal behavior, we then show how simple changes to either the routing strategy or the process to node assignment can bring performance back close to ideal levels. Finally, we not only provide a theoretical justification for our performance models, but also validate them via comprehensive simulation-based studies of systems with up to 16,512 nodes.

Adaptive routing is an efficient congestion avoidance mechanism for modern Data enter and HPC networks. Congestion detection traditionally relies on the occupancy of the router queues. However, this approach can hinder performance due to coarse-grain measurements with small buffers, and potential routing oscillations with large buffers. We introduce an alternative mechanism, labelled Contention-Based Adaptive Routing. Our mechanism adapts routing based on an estimation of "network contention", the simultaneity of traffic flows contending for a network port. Our system employs a set of counters which track the demand for each output port. This exploits path diversity thanks to earlier detection of adversarial traffic patterns, and decouples buffer size and queue occupancy from contention detection. We evaluate our mechanism in a Dragonfly network. Our evaluations show this mechanism achieves optimal latency under uniform traffic and similar to best previous routing mechanisms under adversarial patterns, with immediate adaptation to traffic pattern changes.

Current High-Performance Computing (HPC) and data center networks rely on large-radix routers. Hamming graphs (Cartesian products of complete graphs) and dragonflies (two-level direct networks with nodes organized in groups) are some direct topologies proposed for such networks. The original definition of the dragonfly topology is very loose, with several degrees of freedom, such as the inter- and intragroup topology, the specific global connectivity, and the number of parallel links between groups (or trunking level). This work provides a comprehensive analysis of the topological properties of the dragonfly network, providing balancing conditions for network dimensioning, as well as introducing and classifying several alternatives for the global connectivity and trunking level. From a topological study of the network, it is noted that a Hamming graph can be seen as a canonical dragonfly topology with a high level of trunking. Based on this observation and by carefully selecting the global connectivity, the Dimension Order Routing (DOR) mechanism safely used in Hamming graphs is adapted to dragonfly networks with trunking. The resulting routing algorithms approximate the performance of minimal, nonminimal, and adaptive routings typically used in dragonflies but without requiring virtual channels to avoid packet deadlock, thus allowing for lower cost router implementations. This is obtained by properly selecting the link to route between groups based on a graph coloring of network routers. Evaluations show that the proposed mechanisms are competitive with traditional solutions when using the same number of virtual channels and enable for simpler implementations with lower cost. Finally, multilevel dragonflies are discussed, considering how the proposed mechanisms could be adapted to them.

High-radix hierarchical networks are cost-effective topologies for large scale computers. In such networks, routers are organized in super nodes, with local and global interconnections. These networks, known as Dragonflies, outperform traditional topologies such as multi-trees or tori, in cost and scalability. However, depending on the traffic pattern, network congestion can lead to degraded performance. Misrouting (non-minimal routing) can be employed to avoid saturated global or local links. Nevertheless, with the current deadlock avoidance mechanisms used for these networks, supporting misrouting implies routers with a larger number of virtual channels. This exacerbates the buffer memory requirements that constitute one of the main constraints in high-radix switches. In this paper we introduce two novel deadlock-free routing mechanisms for Dragonfly networks that support on-the-fly adaptive routing. Using these schemes both global and local misrouting are allowed employing the same number of virtual channels as in previous proposals. Opportunistic Local Misrouting obtains the best performance by providing the highest routing freedom, and relying on a deadlock-free escape path to the destination for every packet. However, it requires Virtual Cut-Through flow-control. By contrast, Restricted Local Misrouting prevents the appearance of cycles thanks to a restriction of the possible routes within super nodes. This makes this mechanism suitable for both Virtual Cut-Through and Wormhole networks. Evaluations show that the proposed deadlock-free routing mechanisms prevent the most frequent pathological issues of Dragonfly networks. As a result, they provide higher performance than previous schemes, while requiring the same area devoted to router buffers.

Dragonfly networks have been recently proposed for the interconnection network of forthcoming exascale supercomputers. Relying on large-radix routers, they build a topology with low diameter and high throughput, divided into multiple groups of routers. While minimal routing is appropriate for uniform traffic patterns, adversarial traffic patterns can saturate inter-group links and degrade the obtained performance. Such traffic patterns occur in typical communication patterns used by many HPC applications, such as neighbor data exchanges in multi-dimensional space decompositions. Non-minimal traffic routing is employed to handle such cases. Adaptive policies have been designed to select between minimal and nonminimal routing to handle variable traffic patterns. However, previous papers have not taken into account the effect of saturation of intra-group (local) links. This paper studies how local link saturation can be common in these networks, and shows that it can largely reduce the performance. The solution to this problem is to use nonminimal paths that avoid those saturated local links. However, this extends the maximum path length, and since all previous routing proposals prevent deadlock by relying on an ascending order of virtual channels, it would imply unaffordable cost and complexity in the network routers. In this paper we introduce a novel routing/flow-control scheme that decouples the routing and the deadlock avoidance mechanisms. Our model does not impose any dependencies between virtual channels, allowing for on-the-fly (in-transit) adaptive routing of packets. To prevent deadlock we employ a deadlock-free escape sub network based on injection restriction. Simulations show that our model obtains lower latency, higher throughput, and faster adaptation to transient traffic, because it dynamically exploits a higher path diversity to avoid saturated links. Notably, our proposal consumes traffic bursts 43% faster than previous ones.

The performance of an interconnection network is typically measured by two metrics: average latency and peak network throughput. Average network throughput is usually reported in the belief the network is fair and all source nodes are supposedly able to inject at the same rate. However, most systems exhibit significant network unfairness under non-uniform loads. At high loads, if link utilization is uneven, the injection matrix will also become uneven. This unfairness significantly degrades the performance of some nodes, and eventually the whole system. Fairness issues have been previously reported for direct topologies such as mesh and torus, but this work evaluates throughput fairness in indirect networks, specifically the fat-tree topology. We will see fairness is still an issue for indirect networks in the presence of hot-spots. The SAT protocol was initially proposed to provide throughput fairness for ring networks. This paper extends the original protocol to implement a fairness injection mechanism that works for indirect networks. A thorough evaluation will show that for most scenarios it is possible to achieve throughput fairness without a significant lost of peak throughput.

Many shared-memory parallel systems use lock-based synchronization mechanisms to provide mutual exclusion or reader-writer access to memory locations. Software locks are inefficient either in memory usage, lock transfer time, or both. Proposed hardware locking mechanisms are either too specific (for example, requiring static assignment of threads to cores and vice-versa), support a limited number of concurrent locks, require tag values to be associated with every memory location, rely on the low latencies of single-chip multicore designs or are slow in adversarial cases such as suspended threads in a lock queue. Additionally, few proposals cover reader-writer locks and their associated fairness issues. In this paper we introduce the Lock Control Unit (LCU) which is an acceleration mechanism collocated with each core to explicitly handle fast reader-writer locking. By associating a unique thread-id to each lock request we decouple the hardware lock from the requestor core. This provides correct and efficient execution in the presence of thread migration. By making the LCU logic autonomous from the core, it seamlessly handles thread preemption. Our design offers richer semantics than previous proposals, such as try lock support while providing direct core-to-core transfers. We evaluate our proposal with micro benchmarks, a fine-grain Software Transactional Memory system and programs from the Parsec and Splash parallel benchmark suites. The lock transfer time decreases in up to 30% when compared to previous hardware proposals. Transactional Memory systems limited by reader-locking congestion boost up to 3x while still preserving graceful fairness and starvation freedom properties. Finally, commonly used applications achieve speedups up to a 7% when compared to software models.

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.

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.