Query: Recursively scalable fat-trees as interconnection networks

Candidate papers:

abstract: We introduce orthogonal fat trees as a type of interconnection network for parallel computers, and show how they can be used to maximize the number of processors in a massively parallel computer when the degree of the internal nodes and the diameter of the network are physically constrained. The basic building block of these orthogonal fat trees is a two level fat tree that is obtained from a complete set of mutually orthogonal Latin Squares. As a practical application of orthogonal fat trees, we propose a new interconnection network for a massively parallel computer based on the QROOOl Data Stream Controller Interface, an integrated circuit produced by National Semiconductor, which can sustain a throughput of up to 180 MBytes/sec. The network consists of multiple interconnected rings and is constrained to have at most 16 nodes per ring and a maximum diameter of four. Our solution yields a maximum of 51,984 processors.
author_names: Marcos Valerio

Louise E Moser

P M Melliar-Smith
title: Recursively scalable fat trees as interconnection networks
venue: Proceeding of 13th IEEE Annual International Phoenix Conference on Computers and Communications
year: 1994

abstract: Orthogonal fat trees are a type of interconnection network with several desirable characteristics: short distance between processors, constant degree of the switching elements, uniform traffic load, symmetry, and recursive scalability. We first show how to build two level orthogonal fat trees, where each node has a fixed degree and there is a maximum distance of two between any two leaves. We then show how to provide fault tolerance by including redundant paths at the cost of reducing the number of leaves. Finally, we show how to construct large orthogonal fat trees from two level fat trees recursively.<ETX>
author_names: Marcos Valerio

Louise E Moser

P M Melliar-Smith
title: Fault tolerant orthogonal fat trees as interconnection networks
venue: Proceedings 1st International Conference on Algorithms and Architectures for Parallel Processing
year: 1995

abstract: We introduce and analyze a new family of multiprocesser interconnection networks, called generalized fat trees, which include as special cases the fat trees used for the connection machine architecture CM 5, pruned butterflies, and various other fat trees proposed in the literature. The generalized fat trees provide a formal unifying concept to design and analyse a fat tree based architecture. The extended generalized fat tree network XGFT(h; m/sub 1/ m/sub h/ w/sub 1/ w/sub h/ of height h has /spl Pi//sub i=1//sup h/ m/sub i/ leaf processors and the inner nodes serve only as switches or routers. Each non leaf node in level i has m/sub i/ children and each non root has w/sub i+1/ parent nodes. The generalized fat trees provide regularity, symmetry, recursive scalability, maximal fault tolerance, logarithmic diameter bisection scalability, and permit simple algorithms for fault tolerant self routing and broadcasting. These networks are also versatile, since they can efficiently embed rings, meshes and tori, trees, pyramids and hypercubes.<ETX>
author_names: Sabine R Ohring

Maximilian Ibel

Sajal K Das

Mohan Kumar
title: On generalized fat trees
venue: Proceedings of 9th International Parallel Processing Symposium
year: 1995

abstract: The BCDC network is a new server centric data center network based on crossed cube. Its decentralized and recursively defined features solve the bandwidth bottleneck problem of the upper switch in the tree structure and make it more scalable. In addition, the degree of BCDC server is constant, which reduces connection cost and technical difficulty relative to DCell and BCube. In this paper, we study and analyze the data communication, fault tolerance, and node disjoint paths of BCDC through practical experiments. The results show that BCDC is superior to DCell and Fat Tree in data communication. Moreover, in terms of fault tolerant routing and node disjoint paths, the performance of BCDC is no worse than that of DCell and FatTree. We also propose a one to one communication algorithm in BCDC under 1 restricted connectivity, analyze time complexity of algorithm, and give an upper bound of the conditional faulty diameter of BCDC under 1 restricted connectivity. The work in this paper provides an important basis for the design and application of the new data center network.
author_names: Shuangxiang Kan

Jianxi Fan

Baolei Cheng

Xi Wang
title: The Communication Performance of BCDC Data Center Network
venue: 2020 12th International Conference on Communication Software and Networks (ICCSN)
year: 2020

abstract: As the scale of supercomputers grows, so does the size of the interconnect network. Topology aware task mapping, which maps parallel application processes onto processors to reduce communication cost, becomes increasingly important. Previous works mainly focus on the task mapping between compute nodes (i.e. inter node mapping) while ignoring the mapping within a node (i.e. intra node mapping) In this paper, we propose a hierarchical task mapping strategy, which performs both inter node and intra node mapping. We consider supercomputers with popular fat tree and torus network topologies, and introduce two mapping algorithms: (1) a generic recursive tree mapping algorithm, which can handle both inter node mapping and intra node mapping; (2) a recursive bipartitioning mapping algorithm for torus topology, which efficiently partitions the compute nodes according to their coordinates. Moreover, a hierarchical task mapping library is developed. Experimental results show that the proposed approach significantly improves the communication performance by up to 77 with low runtime overhead.
author_names: Jingjin Wu

Xuanxing Xiong

Zhiling Lan
title: Hierarchical task mapping for parallel applications on supercomputers
venue: The Journal of Supercomputing
year: 2014

abstract: The performance of the interconnect network is massively important in the modern day supercomputer and data centers. As a PhD student in the FSUCSEXPLORER (EXtreme scale comPuting,modeLing, netwORking systEms Research) lab under the supervision of Dr. Xin Yuan, my research activity revolves around the analysis, improvement and performance evaluation of a number of topology and routing schemes widely used in the eld of high performance computing. Over the years, I worked in a number of projects that is brie y described over the next few paragraphs. 1 LOAD BALANCED SLIM FLY NETWORKS The Slim Fly topology [2] has been proposed recently for future generation supercomputers. In this project, we investigated how the tra c is expected to disperse among the network, and discovered that in Slim Fly certain links are more likely to carry tra c than the rest of the links for both minimal and non minimal routing. As a result, hot spots are more likely to form in these links. To mitigate the issue, we came up with two di erent approaches. The rst approach, which we call the bandwidth provisioning scheme, is to modify the topology and increase the bandwidth of the overused links in such a rate so that the original load imbalance goes away. For a given Slim Fly topology, we identify the links that needs to get the added capacity, and the amount of extra bandwidth needed. This approach eliminates the load imbalance completely, but comes with implementation issues. The second approach, that we call the Weighted non minimal routing scheme, is to modify the non minimal routing to distribute the tra c in a more loadbalanced fashion. Essentially, we assigned some weights to the non minimal nodes to counter balance the inherent routing bias that comes with the topology. We presented two strategies to tune the necessary weights to implement this approach. We validated our resultswith detailed analysis and simulation, and demonstrated that both the approaches result in a more e ective Slim Fly network that its present form. 2 DRAGONFLY DESIGN SPACE: LINK ARRANGEMENT AND PATH DIVERSITY Dragon y [9] is a popular cost e ective interconnect design which has been used in a number of current and future generation supercomputers. In this topology, the nodes are grouped together into Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro t or commercial advantage and that copies bear this notice and the full citation on the rst page. Copyrights for third party components of this workmust be honored. For all other uses, contact the owner/author(s) ICPP'18, August 2018, Eugene, OR, USA (c) 2018 Copyright held by the owner/author(s) ACM ISBN 978 x xxxx xxxx x/YY/MM. https:/doi.org/10.1145/n clusters, and the clusters are connected to each other to form a diameter three network. The original Dragon y paper left a few issues open, like how the nodes inside the groups will be connected, towhich router and global channel should be connected to, orwhat happens when the total number of groups in the system is less than the maximum it can support. There has been e orts to answer these questions [5] and there are systems [4] that were built with deviations from the original Dragon y design, but there are still a lack of formal answers of the open questions. In this project, we investigate the design space of Dragon y. Our objective is twofold. First, we want to gure out how the inter group connections should be implemented to get optimum performance from the network, specially when the network contains less than maximum number of groups. Second, we analyze the minimal path distribution within the entire design space, and investigate the performance of the existing routing algorithms. This project is currently on going and we are using a number of modeling, simulation and learning techniques to attain our objectives. 3 TRAFFIC PATTERN BASED ADAPTIVE ROUTING IN DRAGONFLY NETWORKS In Dragon y topology, routing is done through minimal and nonminimal paths, and adaptive routing [13] is used to toggle between them. Traditionally, adaptive routing algorithms use locally available information, for example bu er queue length, to detect congestion scenario in the network. This poses a challenge for Dragon y as the inter group nodes may not have the most accurate information about congestion in the gateway routers. There have been a number of research [14] [8] on how to convey the congestion information e ciently to the local routers. For our project, we investigated the performance of adaptive routing in the Dragon y network used in Cray Cascade [4] and presented a novel scheme to improve over it. The idea is to gather link usage statistics through performance counters within a certain history window, and use that information to infer the tra c pattern: benign or adversarial. Then the nal routing decision is taken using both the tra c pattern and link load information. We performed simulation using a number of tra c patterns and demonstrated that our scheme achieves lower latency for benign tra c and higher throughput for adversarial tra c over the existing UGAL adaptive routing scheme. The rst phase of the project only considered the intra group communications. For the second phase, we are currently working to expand in to inter group communications as well. 4 PERFORMANCE MODELING STUDIES I worked in a number of projects over the years which analyzed and devised scalable modeling methods to evaluate various topologies, routings and performancemetrics. In one project,wemodeled ICPP'18, August 2018, Eugene, OR, USA Shafayat Rahman the UGAL[13] routing over Dragon y topology to get a better theoretical understanding on how the routing works. UGAL is extensively used on various systems to implement adaptive routing, but there had been no theoretical understanding on its e ectiveness; all the prior studies were simulation or experiment based. In our project, we modeled UGAL's performance with varying level of controls over the minimal and non minimal paths, and compared the modeling results with simulation output. The verdict was that individual level control on every path generally overestimates the system's output, full random control on all paths (basically treating each path as same) generally underestimates the output, and controlling the same length paths as a group goes within 10% of simulation output. So this gives a good estimation of system output under UGAL routing while is also computationally feasible. In another project, we evaluated a number of commonly used throughput models and identi ed similar and contradictory trends in their performance. The models we studied were max min fairness (MMF) [1] maximum concurrent ow (MCF) [12] Hoe er's method (HM) [6] and Jain's method (JM) [7] We showed that even though the later three models approximate MMF, they have subtle di erences and may even produce contradictory results depending on the topology and tra c pattern. Finally, Iworked in another project that studied the performance characteristics of a number of topologies that provide either low diameter (Dragon y and Slim Fly) or high path diversity (fat tree [11] RandomRegular graph [10] and Generalized De BruijnGraph [3] We investigated the performance of some HPC applications paired with some routing schemes on each of the topologies. We observed that the adaptive routing techniques developed for lowdiameter topologies are e ective on high path diversity topologies as well. Also, we determined that high path diversity topologies generally perform better than equivalent sized low diameter topologies. I started the program in FSU in 2011. I spent a number of years taking various core and elective courses, going through the PhD comprehensive exam, and exploring a number of research areas. I started working with Dr. Yuan from 2014. I acquired the background knowledge necessary to excel in the eld of HPC, completed my area exam and worked in a summer internship at Oak Ridge National Lab. I am on course to wrap up the current projects and complete my degree by the end of 2018. ACM Reference Format: Shafayat Rahman. 2018. Topologies and Adaptive Routing on large Scale Interconnects. In Proceedings of ACM Conference (ICPP'18) Eugene, OR, USA 2 pages. https:/doi.org/10.1145/n
author_names: Shafayat Rahman
title: Topologies and Adaptive Routing on large Scale Interconnects
year: 2018

abstract: BXI, Bull eXascale Interconnect, is the new inter connection network developed by Atos for High Performance Computing. It has been designed to meet the requirements of exascale supercomputers. At such scale, faults have to be expected and dealt with transparently so that applications remain unaffected by them. BXI features various mechanisms for this purpose, one of which is the BXI routing component presented in this paper. The BXI routing module computes the full routing tables for a 64k nodes fat tree in a few minutes. But with partial re computation it can withstand numerous inter router link failures without any noticeable impact on running applications.
author_names: Pierre Vigneras

Jean-Noel Quintin
title: Fault Tolerant Routing for Exascale Supercomputer: The BXI Routing Architecture
venue: 2015 IEEE International Conference on Cluster Computing
year: 2015

abstract: Orthogonal fat trees are a type of interconnection network with several desirable characteristics: short distance between proceamrs, constant degree of the .switching elements, uniform traffic load, symmetry, and recursive scalability. We first show how to build two level orthogonal fat trees, where each node has a fixed degree and there is a maximum distance of two between any two leaves. We then show how to pm vide fault tolerance by including redundant paths at the cost of reducing the number of leaves. Finally, we &ow how to construct large orthogonal fat trees from two level fat trees recursively.
author_names: Marcos Valerio

Louise E Moser

P M Melliar-Smith
title: Interconnection Networks
year: 1995

abstract: We study recursive cube of rings (RCR) a class of scalable graphs that can potentially provide rich inter connection network topology for the emerging distributed and parallel computing infrastructure. Through rigorous proof and validating examples, we have corrected previous misunderstandings on the topological properties of these graphs, including node degree, symmetry, diameter and bisection width. To fully harness the potential of structural regularity through RCR construction, new edge connecting rules are proposed. The modified graphs, referred to as \it Class II RCR} are shown to possess uniform node degrees, better connectivity and better network symmetry, and hence will find better application in parallel computing.
author_names: Kai Xie

Jing Li

Yumei Wang

Chau Yuen
title: Recursive Cube of Rings (RCR) Revisited: Properties and Enhancement
year: 2013

abstract: Interconnection networks of modern distributed computer systems are now hierarchical. In such systems communication time between processors depends on their placement in a computer system. In large scale NUMA/SMP computer clusters first two levels are formed by network switches of two stage fat tree/dragonfly topology and a third level is presented by a shared memory of computer nodes. In this paper, we describe a dynamic optimization method for collective all to all communication operations on hierarchical computer clusters. Our approach exploits knowledge of the L level hierarchy of a computer system and is based on a mapping of intensively communicating processes into the same computer nodes. Optimized versions of the Bruck and recursive doubling algorithms for MPI_Allgather operation are proposed. Algorithms are implemented in our experimental library TopoMPI. Performance results on multicore SMP computer clusters with InfiniBand and Gigabit Ethernet networks indicate that the Allgather algorithms based on our approach outperform the original Allgather algorithms (Bruck and recursive doubling)
author_names: Mikhail G Kurnosov
title: Dynamic mapping of all to all collective operations into hierarchical computer clusters
venue: 2016 13th International Scientific Technical Conference on Actual Problems of Electronics Instrument Engineering (APEIE)
year: 2016