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

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

局部扭立方体环互连网络及其性质

优化网络的拓扑结构是互连网络研究的重要研究方向。局部扭立方体（locally twisted cube,LTQn ）是对超立方体（hypercube,Qn ）互连网络的优化变种,然而当对LTQn 升级时,需要成倍地增加网络的节点,这不利于LTQn的应用和发展。为了克服LTQn 这一缺陷,提出了一种新的互连网络拓扑结构：局部扭立方体环互连网络（locally twisted cube-connected ring interconnect network,LRN）,给出了LRN的定义及其拓扑结构,并研究了LRN的网络直径、连接度、汉密尔顿连通性、泛圈性、路由等问题,证明了LRN是一种易于升级又具有LTQn 许多优良性质的层次环互连网络（hierarchical ring interconnection networks,HRN）。     

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

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

基三分层网络中的受限多播路由算法

多播路由算法对互连网络的通信性能和多处理机系统性能的发挥起着重要作用。针对基三分层互连网络,在权衡性能、成本和实现的基础上,提出一种基于树的受限多播路由算法TRMA。该算法充分利用基三分层互连网络的层次特性和节点编码中所含的网络拓扑信息实现消息路由,算法设计简单,易于硬件实现。和其他基于树的多播路由算法相比,TRMA算法不需要源节点在发送消息前构建多播树,并将多播树的信息存放在消息中,大大降低了源节点的工作负载,提高整个系统的性能。通过仿真比较了TRMA和基于单播的多播路由算法,结果表明TRMA具有较低的网络延迟和较小的网络流量。     

一种高效的超节点网络容错机制

超节点网络采用超节点作为普通节点服务器,负责管理和查询处理的机制,提高了搜索效率。但是,如果超节点失效,将会严重影响网络的稳定性和查询效率。提出一种高效的容错机制。首先,改进了无向双环结构,提出k-无向双环拓扑结构,并利用此技术,构建了超节点层拓扑结构,使网络具有高容错特性;同时在此基础上,给出了超节点选择和超节点负载均衡的方法,降低了超节点因负载过重而失效的可能性,另外,给出了超节点失效恢复算法和容错路由算法,解决了超节点失效后的恢复和路由问题。实验结果显示,该网络具有易维护、高容错的特点。     

基于超立方体拓扑结构的发布订阅系统

从网络拓扑结构着手,提出基于超立方体拓扑结构的发布订阅系统,并在此基础上设计对应的路由算法。基于超立方体拓扑结构网络不仅仅具有一般结构化P2P网络的特性,即能够支持大规模、动态的分布式应用,而且由于自身结构的特点使其更适合于发布订阅系统中对大量事件传播的要求。仿真结果表明,超立方体结构的引入能显著降低系统负载,节省带宽。     

NoC节点编码及路由算法的研究

NoC的设计和实现受到芯片的面积、功耗、深亚微米效应的限制.将拓扑结构和节点编码相结合,提出一种基于约翰逊码的二维平面编码.该编码隐含了Torus网络拓扑结构以及网络节点之间的连接关系并且有很好的扩展性,能够简化Torus拓扑结构上路由算法的实现和降低硬件成本.基于此编码和利用X-Y路由的路由确定性特点,提出改进X-Y路由,在中间节点只需要3或5个逻辑运算,降低路由的计算复杂性和硬件成本.最后,进行了节点结构设计.提出的编码不仅用于NoC的路由方面而且在NoC任务映射方面有重要应用.     

基于InfiniBand的多链路mesh/torus大规模并行系统互连网络

在大规模并行系统中,系统级互连网络的设计至关重要.InfiniBand作为一种高性能交换式网络被广泛应用于大规模并行处理系统中.mesh/torus拓扑结构相较于目前普遍应用于InfiniBand网络的胖树拓扑结构拥有更好的性能与可扩展性.尽管如此,研究发现,用传统的mesh/torus拓扑结构构建InfiniBand互连网络存在诸多问题.分析了传统网络拓扑结构的缺陷,并提出了一种基于InfiniBand的多链路mesh/torus互连网络.这种改进型的拓扑结构通过充分利用交换机间的多链路可以获得比传统mesh/torus网络更高的带宽.另外,同时给出了与该网络拓扑结构相配套的高效路由算法.最后,通过网络仿真技术对提出的算法进行了评估,实验结果显示提出的路由算法相较于其他路由算法拥有更好的性能与可扩展性.     

全互连立方体网络在并行处理系统中的应用

提出一种应用于大规模并行处理系统的结点度等于常数的递归多级分层互连网络 ,称为全互连立方体网络 (fully connected cubic network,FCCN) .FCCN具有可扩展性好、延伸性能好等优点 .一个 m- FCCN可以由 8个(m - 1) - FCCN递归得到 ,FCCN网络的结点度与网络的规模大小无关等于常数 4,网络的直径和平均结点距离都与结点数的立方根成正比 .提出 FCCN中的简单路由算法 .并将 FCCN互连网络结构在大规模光电混合处理系统中进行应用 ,通过实际计算结果证明 FCCN具有比较高的并行处理效率     

全互连立方体网络的并行处理系统中的应用

提出一种应用于大规模并行处理系统的结点度等于常数的递归多级分层互连网络,称为全互连立方体网络（fully connected cubic network,FCCN）。FCCN具有可扩展性好、延伸性能好等优点,一个m-FCCN可以由8个（m－1）－FCCN递归得到,FCCN网络的结点度与网络的规模大小无关等于常数4,网络的直径和平均结点距离都与结点数的立方根成正比,提出FCCN中的简单路由算法,并将FCCN互连网络结构在大规模光电混合处理系统中进行应用,通过实际计算结果证明FCCN具有比较高的并行处理效率。     

Linear recursive networks and their applications in distributedsystems

We present a new class of interconnection topologies called the Linear Recursive Networks (LRNs) and examine their possible applications in distributed systems. Each LRN is characterized by a recursive pattern of interconnection which can be specified by simple parameters. Basic properties such as node degree, diameter, and the performance of routing algorithms for all LRNs are then collectively analyzed in terms of these parameters. By choosing appropriate values for the parameters, our results can assist a network designer in selecting a topology with required routing performance and cost of interconnection. A subclass of LRNs, called Congruent LRNs (CLRNs), is also identified here and shown to possess desirable properties for more tightly coupled systems. It is shown that the CLRNs include existing networks such as hypercube and generalized Fibonacci cubes. These results suggest that the linear recursive networks potentially have applications in interconnecting distributed systems     

一种新型大容量路由器交换网络中的高效路由策略

路由算法对交换网络性能具有很大的影响。本文针对一种新型的大容量路由器交换网络拓扑-XD（Cross-Direct）网络的特点,提出了一类和应用于传统直连网络中的基于简单维序路由算法具有相同网络性能的路由算法一对角矢量映射法（DVM）。该类算法分为两种,文中对这两种算法进行了详细描述和性能分析,给出了它们各自的应用场合。     

A flexible bit-pattern associative router for interconnectionnetworks

A programmable associative approach to execute implicit routing algorithms is presented. Algorithms are mapped onto a set of bit-patterns that are matched in parallel. We have studied and mapped a large number of routing algorithms for a wide range of interconnection network topologies. Here we report three cases that illustrate the capabilities of the router scheme. For the studied topologies, the number of required bit-patterns is of the same order as the topology degree. The proposed approach is one of the fastest routers and requires a very small amount of hardware     

基三分层互连网络及其路由算法设计

从降低节点度、减少网络链路数和缩短网络直径的角度出发,提出一种新型的互连网络结构--基三分层互连网络,深入地研究了该网络的静态度量并和2-D Mesh做了相应的比较.针对基三分层互连网络提出了一种使消息沿两节点间确定路径传递的分布式确定路由算法DDRA.该算法充分利用基三分层互连网络的层次特性,不需要构建路由表,且算法实现简单,路由效率高,且易于硬件实现.     

OBQA: Smart and cost-efficient queue scheme for Head-of-Line blocking elimination in fat-trees

High-speed interconnection networks are essential elements for different high-performance parallel-computing systems. One of the most common interconnection network topologies is the fat-tree, whose advantages have turned it into the favorite topology of many interconnect designers. One of these advantages is the possibility of using simple but efficient routing algorithms, like the recently proposed deterministic routing algorithm referred to as DET, which offers similar (or better) performance than Adaptive Routing while reducing complexity and guaranteeing in-order packet delivery. However, as other deterministic routing proposals, DET cannot react when packets intensely contend for network resources, leading to the appearance of Head-of-Line (HoL) blocking which spoils network performance. In this paper, we describe and evaluate a simple queue scheme that efficiently reduces HoL-blocking in fat-trees using the DET routing algorithm, without significantly increasing switch complexity and required silicon area. Additionally, we propose an implementation of OBQA in a feasible switch architecture.     

一类层次双环网络的构造及其路由算法

高效互联网络的拓扑结构一直是人们关注的热点问题。提出了一类层次双环互联网络HDRN（k）,给出了HDRN（k）网络的构造方法,研究了它的性质,并且通过与相关网络的比较,证实了HDRN（k）具有好的连接性、短的直径以及简单的拓扑结构,是一种实用的互联网络。另外,讨论了HDRN（k）网络的路由性质,设计了点点路由和Broadcast路由算法,证明了这两种路由算法的通信效率与层次环网络上对应算法的通信效率相比均有明显的提高。综上所述,HDRN（k）是一种具有良好拓扑性质的新型互联网络。     

An optimal fault-tolerant routing algorithm for weighted bidirectional double-loop networks

Double-loop networks are widely used in computer networks. In this paper, we present an optimal message routing algorithm and an optimal fault-tolerant message routing algorithm for weighted bidirectional double-loop networks. The algorithms presented are novel, and they do not use routing tables. After a precalculation of O(log N) steps to determine network parameters, the algorithms can route messages using constant time at each node along the route. The algorithm presented can route messages in the presence of up to three faulty nodes or links. The fault-tolerant routing algorithm guarantees an optimal route in the presence of one node failure.     

Cube connected Mobius ladders: an inherently deadlock-free fixeddegree network

The authors introduce a multiprocessor interconnection network, known as cube-connected Mobius ladders, which has an inherently deadlock-free routing strategy and hence has none of the buffering and computational overhead required by deadlock-avoidance message passing algorithms. The basic network has a diameter φ of 4n-1 for n2ⁿ⁺² nodes and has a fixed node degree of 4. The network can be interval routed in two stages and can be represented as a Cayley graph. This is the only practical fixed degree topology of size O(2^φ) which has an inherently deadlock-free routing strategy, making it ideally suited for medium and large sized transputer networks