Torus连接Petersen图互连网络及路由算法

可扩展性和短直径是设计大规模并行计算机系统互连网络的两个重要因素.基于Petersen图的短直径和正规性和Torus拓扑结构的可扩展性,提出了一种新的互连网络拓扑结构,称为Torus连接Petersen图互连网络.该互连网络拓扑结构具有短直径、正规性、对称性和良好的扩展性.网络节点采用混合编码方法,使得路由算法设计简单.分别设计了基于混合编码的单播、广播路由算法.分析表明提出的互连网络具有较好的拓扑性质.     

TM:一种新的片上网络拓扑结构

片上网络拓扑结构对芯片的性能有直接的影响.文中提出了一种新的拓扑结构TM,它结合了torus网络和mesh网络的优点.对于n×n的网络,在物理链路数方面,TM和mesh网络相同,比torus网络少2n;在拓扑直径方面,TM的拓扑直径为n,而torus和mesh网络的拓扑直径分别为2×(n/2)和2×(n-1);在完全适应性路由算法设计方面,torus网络需要的虚拟通道数至少为3,且虚拟网络划分机制不能直接应用其中,然而,虚拟网络划分机制适用于mesh和TM网络,且它们只需要2条虚拟通道.文中从理论和模拟实验两方面对TM网络进行了验证,实验结果表明无论在均衡负载还是非均衡负载下,TM的性能都要优于mesh网络,在大部分情况下,TM的性能介于mesh和torus之间,在某些通信模型下,torus的性能比TM差,主要原因在于这些通信模型下torus网络中虚通道使用不均衡.     

超立方体双环互连网络及路由算法*

给出了一种可扩展的互连网络拓扑结构,称为超立方体双环。该互连网络拓扑结构结合了超立方体拓扑的短直径、高连通性、对称性、路由简单和一种新的双环拓扑结构的可扩展性和常数节点度的优点,使得网络规模增大时,网络节点度可以保持常数;网络节点采用格雷编码和约翰逊编码的混合编码方法,网络的任意相邻节点编码有且仅有一位不同,使得路由算法设计简单。最后分别设计了基于混合编码的单播、广播路由算法。分析表明提出的互连网络具有较好的拓扑性质和通信性能。     

Up*/Down*路由算法的改进方案

机群系统 (NOWs)用于并行计算具有性能价格比高、结构灵活、可扩展性好等优点 ,但要实现高性能的机群系统 ,必须采用交换式高速互连网络 .交换器之间连接的不规则性 ,使路由与死锁避免问题非常复杂 .介绍了不规则拓扑网络中经典的 up* / down*路由算法 ,分析它的实现原理 ,指出了它在链路方向指派方面的不合理性 ,并基于贪婪算法的思想 ,给出了优化的链路方向指派方法 ,由此确定新的路由算法 greedy- U D.经模拟实验证明 ,greedy- U D算法较up* / down*路由算法性能有了显著提高     

Paleyfly:一种可扩展的高速互连网络拓扑结构

高速互连网络是高性能计算系统的重要组成部分.随着网络规模需求的扩大,如何搭建更大规模的网络是高速互连网络拓扑结构设计的关键.因此,提出一种新型层次化的拓扑结构Paleyfly (PF),其结合了Paley图强正则的特性和Random Regular(RR)图支持任意规模大小的特点.相比其他新型高速互连网络拓扑结构,Paleyfly能够有效解决在路由芯片端口数受限的背景下,Dragonfly (DF)可扩展性受限、Fat tree(Ft)物理成本高、RR结构物理布局难、路由表规模大等问题.同时,根据强正则属性在路由策略上负载均衡的优势,提出了4种路由策略来解决网络的拥塞问题.最后,通过模拟器实验比较分析PF结构与其他拓扑结构及PF结构不同路由策略的性能,验证了PF结构在不同规模以及不同通信模式配置下网络延迟优于RR结构.     

三维无线自组网络的成簇及自适应路由算法

针对三维无线自组织网络拓扑结构复杂导致的不易寻路的问题,提出成簇算法和基于部分超立方体网络结构(PCCN)的自适应路由算法.成簇算法考虑到节点疏密不均的情况,利用节点的空间密度分布将节点分割成候选簇,采用融合机制将候选簇构建成更均匀的簇结构.使用实际拓扑到虚拟拓扑的转化策略,在簇结构的基础上构建PCCN.PCCN作为虚拟拓扑结构,简化了实际网络拓扑,具有可扩展性、延伸性能好等优点.利用PCCN,对节点进行编号之后进行自适应路由.自适应路由算法包括簇内和簇间路由两种情况.算法分析及算例表明,PCCN简化了三维网络的拓扑结构,能够有效路由,为三维自组织网络的管理提出了新的方法和手段.     

一种改进负载均衡的网络编码多播路由算法

已有研究证明,在多播网络中使用网络编码可以显著提高多播通信的性能。总结了网络编码多播理论的研究进展,同时对网络编码多播路由问题进行了研究与分析。考虑到影响链路负载和资源消耗的因素,提出了一种改进链路负载均衡的网络编码多播路由算法,优化了路径间链路的共享。通过使用常见的Waxman网络拓扑模型,产生随机网络拓扑。在这些拓扑中,分别针对传统IP多播路由、低速率网络下的网络编码多播路由以及提出的路由算法进行性能仿真。仿真结果表明,与其他两种路由算法相比,该算法在可达吞吐量、资源消耗和负载均衡等性能上均有很好的表现。     

CR:基于一类新型结构的可扩展路由器

互连网络,例如3-D torus拓扑结构,已成功应用于可扩展路由器的设计中.但是,3-D torus结构在实际应用时存在设计缺陷,扩展规模受到了限制.提出了一类新型的交换架构,称为蜂巢式路由器.基本蜂巢结构存在一些问题,通过引入镜像点可以有效解决,还给出线卡的具体设计方案.最后介绍了该架构下几类路由算法的设计.蜂巢结构表现出优秀的扩展能力和容错性,非常适合可扩展路由器的设计.     

计算机网络互连的路由算法的设计及仿真研究

互连网络目前应用最广泛、最流行的一种网络拓扑,广泛应用于多处理器系统、电话网络、分布式计算机系统及路由器交换机等领域。本文主要对直连网络的负载均衡路由算法进行了研究,提出了一种新的负载均衡路由算法。通过对该算法的仿真发现在相同的网络仿真环境下,该算法的性能要优于传统路由算法。     

使用多级交换网络进行高性能路由器设计

拓扑结构和路由算法是影响多级交换网络性能的重要因素．在比较多种多级互连拓扑属性的基础上,提出将3D Torus结构应用于大规模交换网络设计．然后针对3D Torus交换网络中报文路由面临的两个关键问题：多路径负载均衡和报文保序,提出一种基于维序的多路径路由算法DMR(dimension-order—based multi—path routing)．该算法可在保证报文顺序的同时在多条路径上平衡负载,提高交换网络吞吐率．最后通过模拟验证了算法的性能,并与维序路由和随机路由算法进行了比较．模拟结果表明,DMR算法的性能优于维序路由算法,能够达到随机路由算法性能水平,同时具有随机路由算法所不具备的报文保序特性．     

TM: a new and simple topology for interconnection networks

The selection of a topology is essential to the performance of interconnection networks, so designing a new, cost-effective topology is very significant. 2D mesh is one of the most popular topologies. However, the diameter and average distance of a 2D mesh are large enough to greatly influence the performance of the network. This paper presents a novel topology called TM, which combines the advantages of both a 2D torus and a 2D mesh. For an n×n network, the total number of links in a TM is the same as that in a mesh, while the diameter of a TM is extremely close to that of a torus. Besides, the average distance of a TM is at the middle of that of a torus and that of a mesh. To prevent deadlocks in TMs, a virtual network partitioning scheme is adopted into the TM network. Moreover, both of the deterministic and fully-adaptive routing techniques in TMs are proposed in this paper. Compared to mesh, the TM network provides average distance and diameter reduction, which contributes to the performance enhancement. Sufficient simulation results are presented to show the effectiveness of the TM network, and the new routing schemes proposed for it, by comparing with the mesh network. Compared to the torus, which requires at least 3 virtual channels to support fully-adaptive routing, the TM network can support fully-adaptive routing with only 2 virtual channels. Seen from the experimental results, in most cases, the performance of TM is worse than the torus, while in some cases, the performance of TM is comparable to torus or even better than the torus.     

VTFTR：高维胖树中的无死锁容错路由算法

随着近年来高性能计算系统规模的急剧扩大,高性能互连网络的可靠性成为愈发重要的问题。高维胖树是一种结合了胖树与多维环网优点的网络拓扑结构,凭借其良好的可扩展性与网络性能在E级时代具有广阔的应用前景。然而,目前关于高维胖树中容错路由算法的相关研究较为有限,其可靠性问题亟待解决。为提高高维胖树拓扑在高性能互连网络中的容错能力,进一步提高对应超算系统的运行效率,提出一种用于高维胖树中叶交换机故障的容错路由算法VTFTR。该算法结合转向模型与虚通道切换的思想,通过严格控制报文在无故障路径与容错路径中的转向,使用少量的容错虚通道与额外跳步实现高维胖树中的无死锁容错。实验结果表明,在单点故障情况下,VTFTR算法的容错路径较对比算法有2~4个跳步的减少,在4 096个节点规模的网络中,当叶交换机故障数量为10时,在故障叶交换机不同的分布情况下,该算法能够以1.4%~2.0%的吞吐率下降作为代价来保持全网无故障节点之间的互连。     

The triangular pyramid: Routing and topological properties

In this paper, a new topology for multicomputer interconnection networks, based on triangular mesh, is proposed. The new network, referred to as the triangular pyramid (or tripy for short), has L levels of triangular mesh. We study some basic important properties of the proposed network as well as introduce a routing algorithm for the tripy network based on the routing of triangular meshes. We prove that this form of pyramidal network is Hamiltonian, Hamiltonian-connected, and pancyclic. We also prove that the proposed network is 6-colorable and conduct a brief comparison of the tripy and its traditional pyramid counterpart. Our results show that the proposed network has higher scalability, connectivity, and total network bandwidth while preserving the important properties of the traditional pyramid network.     

A parallel implementation of Strassen’s matrix multiplication algorithm for wormhole-routed all-port 2D torus networks

A new parallel implementation of Strassen’s matrix multiplication algorithm is proposed for massively parallel supercomputers with 2D, all-port torus interconnection networks. The proposed algorithm employs a special conflict-free routing pattern for better scalability and is able to yield a performance rate very close to the theoretical bound for many practical network and matrix sizes. It effectively scales up to very large networks typically containing hundreds-of-thousands processors where petaflop or exaflop processing rates are sought.     

Optimal all-to-all personalized exchange in self-routablemultistage networks

All-to-all personalized exchange is one of the most dense collective communication patterns and occurs in many important applications in parallel computing. Previous all-to-all personalized exchange algorithms were mainly developed for hypercube and mesh/torus networks. Although the algorithms for a hypercube may achieve optimal time complexity, the network suffers from unbounded node degrees and thus has poor scalability in terms of I/O port limitation in a processor. On the other hand, a mesh/torus has a constant node degree and better scalability in this aspect, but the all-to-all personalized exchange algorithms have higher time complexity. In this paper, we propose an alternative approach to efficient all-to-all personalized exchange by considering another important type of networks, multistage networks, for parallel computing systems. We present a new all-to-all personalized exchange algorithm for a class of unique-path, self-routable multistage networks. We first develop a generic method for decomposing all-to-all personalized exchange patterns into some permutations which are realizable in these networks, and then present a new all-to-all personalized exchange algorithm based on this method. The newly proposed algorithm has O(n) time complexity for an n×n network, which is optimal for all-to-all personalized exchange. By taking advantage of fast switch setting of self-routable switches and the property of a single input/output port per processor in a multistage network, we believe that a multistage network could be a better choice for implementing all-to-all personalized exchange due to its shorter communication latency and better scalability     

InfiniBand网络胖树路由算法分析

胖树拓扑结构是搭建集群和HPC比较流行的结构,它具有无阻塞传输和对分带宽的优点。本文介绍了In-finiBand子网管理和胖树结构,分析了胖树路由算法的计算过程和相关改进。     

Loss-aware routing algorithm for photonic networks on chip

Photonic network on chip was introduced as an efficient communication platform to overcome the existing challenges in traditional networks on chip. Optical networks provide high bandwidth and low power dissipation infrastructure. Insertion loss is one of the important parameters in photonic networks on chip. In this study, we propose a solution in routing algorithm level in order to reduce insertion loss in photonic network on chip, by passing packets through paths with lower number of optical elements. Simulation results reveal that a novel approach in the routing level decreases insertion loss as much as possible, energy consumption and optical power budget. Our proposed routing has 29.05% less insertion loss under all2all traffic pattern for blocking torus topology, and it has about 12.37% less insertion loss for TorusNX topology in comparison with primary dimension-ordered routing. Proposed routing algorithm increases both the network bandwidth and scalability.     

InfiniBand交换机基板管理的研究与实现

作为一种互连技术,InfiniBand技术具有高带宽、低延时等许多优势,被认为是消除当前I/O架构性能瓶颈的一种新途径.InfiniBand子网实现了数十个到数百个节点间的高速互连与数据传输.目前,InfiniBand技术已在高性能计算领域得到广泛应用,正逐渐成为高性能计算互连的首选协议.基板管理实现对InfiniBa...