Researches On Novel Topologies And Routing Algorithms For High-performance Interconnection Networks

With the emergence of more and more applications and the explosion of application data,the scale of high-performance computing(HPC)systems is increasing rapidly to provide sufficient computing capabilities.Being one of the most important sub-system in HPC systems,interconnection network has a great impact on the overall performance,cost of ownership,power consumption,resiliency and physical layout.Large-scale lowdiameter topology is a key solution to high-performance networks,and has become the trend in interconnection network designing.The growing demand for network scalability brings big challenges to the design of large-scale low-diameter interconnection network topologies due to several limiting factors,including the contention of chip physical resources,the limitation of the state-of-the-art integration technology,the complexity of physical layout,and the cost and power budget.The dissertation focuses on designing network topologies which meet the scalability requirement of exascale HPC systems with commercial-off-the-shelf(COTS)routers and designing routing algorithms which aim at improving the utilization of buffer resources in routers.The problem of cable packaging complexity is also addressed.The main contributions are:(1)We propose Galaxyfly,a novel family of low-diameter topologies,based on techniques of algebraic graphs over finite fields.Galaxyfly lowers the demands for high-radix routers and is able to build exascale networks with routers of moderate radix.Galaxyfly is guaranteed to retain a small constant diameter while achieving a flexible tradeoff between network scale and bisection bandwidth.An congestion sensitive routing algorithm is also designed for Galaxyfly.We conduct extensive simulations and analysis to evaluate the performance,cost,and power consumption of Galaxyfly and compare Galaxyfly against other state-of-the-art topologies.The results show that Galaxyfly achieves better performance than existing topologies with various routing algorithms under typical traffic patterns,and is capable and cost-effective to build exascale HPC systems.(2)Optical fibers are mandatory in connecting cabinets in modern HPC systems.As the number of the inter-cabinet optical fibers grows,the system is meeting more challenges in cable packaging,cable tolerance and cable maintainability.Multicore fiber(MCF)is a cost-effective approach which is potential to replace a bundle of fiber cables between cabinets with a single one,thus lowering the packaging complexity and enhancing the maintainability.We propose Bundlefly,a new topology which utilizes MCFs to construct interconnection networks in a cost-effective way.Bundlefly achieves a flexible tradeoff between intra-cabinet and inter-cabinet router radix,and is capable to build exascale networks of diameter 3.Evaluation results show that Bundlefly with flexible configurations can achieve better performance than most existing topologies.(3)Cost-effective adaptive routing has a significant impact on overall performance for high-radix hierarchical topologies such as Dragonfly.Existing adaptive routing methods for high-radix hierarchical topologies have the drawback that they cost too many virtual channels and utilize buffer resources in an imbalanced way.We propose a label-based routing(LBR)method for high-radix hierarchical networks.LBR utilizes a co-design methodology which coordinates the input queue and routing computation pipelines in routers.While LBR achieves fully adaptive routing,it relaxes the requirement of virtual channels to eliminate routing deadlock,and eliminate buffer resources dedicated to deadlock avoidance,thus improving the efficiency of buffer utilization.We conduct extensive experiments to evaluate the performance of LBR on Dragonfly and compare it with other state-of-the-art routing algorithms.The results show that LBR achieves 10%–35%higher performance than existing routing algorithms under most traffic patterns.