PFR:一个基于平面的完全自适应路由器

互连网络路由器是ＭＰＰ系统的关键部件，其性能优劣直接影响系统性能。路由器根据其所采用的路由算法可分为确定性和自适应路由器两种，其中自适应路由器有灵活性好，网络的通道利用率高和网络容错能力强等优点，正逐步为新一代的ＭＰＰ系统所采用，但其工程实现难度较大。本文在ｍｅｓｈ结构上，采用虫孔路由切换技术，给出了一个可扩展性好，自适应性强的基于平面的完全自适应路由算法ＰＢＦＡＡ，并采用基于虚通道的综合流控策略     

SpaceFibre总线路由器的设计

为实现SpaceFibre标准协议中网络层的功能,提出一种以FPGA为核心的路由器设计方案.根据协议的规范,设计出5个端口的路由器,包括4个普通端口和1个配置端口,每个普通端口有4条虚拟通道.考虑到虚拟通道路由依然存在数据阻塞的可能,在交叉开关矩阵(CrossBar)结构上增添轮询仲裁的路由算法.用Verilog代码实现该路由器功能,使用XC6SLX9型号的FPGA进行Modelsim的仿真,验证了该设计方案的正确性和有效性.     

片上网络中面向报文有序传输的自适应路由算法研究

与确定性路由算法相比,自适应路由算法可以提高片上网络的通信性能,但是报文可能会无序到达。在目的节点对报文排序将会导致严重的面积和计算开销,甚至可能会抵消采用自适应路由算法带来的性能增益。为此,本文首先提出一种部分自适应路由算法,以满足报文的有序到达。然后,描述了对本文算法提供支持的路由器硬件结构。最后,在二维片上网络下对本文算法及确定性和自适应路由算法进行了性能评估和比较。与XY算法相比,本文算法显著降低了报文延时,提升了饱和点。同时讨论了对路由器面积和功耗影响。虽然路由器的功耗有所上升,但是由于报文交付性能提升,因此每个flit的能耗增长可忽略不计。     

用户模式下虚拟路由器的优化

网络虚拟化体系实现了在同一共享底层架构之上同时运行多个虚拟网络。然而,构建多异构网络并存的、可灵活配置的虚拟网络平台具有一定的挑战性,不仅需要减少虚拟网络之间的交互,还需要提供高速传输的网络特性。对此,提出了一种传统软件虚拟路由器优化方法,实现了用户模式中有效的数据包处理方式,以支持高速、灵活的虚拟网络。采用操作系统层虚拟化过程将物理主机分成多个虚拟机,虚拟路由的数据处理过程在独立的虚拟机中运行,以确保路由处理的安全配置;同时,采用一种优化的用户模式中数据包处理机制,实现了虚拟路由器的高速传输。实验结果证明,该设计中的虚拟路由与传统用户模式中的软件路由器相比,其传输速率提高了3倍以上。     

6LoWPAN嵌套移动网络路由优化方案*

提出一种6LoWPAN嵌套移动网络路由优化方案,在此方案中,6LoWPAN移动网络节点无须经过家乡代理也无须建立隧道即可与通信节点通信,节省了数据传输开销,缩短了数据传输延迟。提出了移动路由器转交地址的分层结构,根据此分层结构,提出了基于最短路径的移动路由器转交地址配置算法,缩短了数据传输延迟。从理论和仿真两个角度对所提出的路由优化方案的路由优化开销、路由延迟及路由代价等性能参数进行了比较分析,分析结果验证了本方案的有效性和高效性。     

一种二维结构的互连路由设计与实现

针对阵列处理单元之间互连传输拥塞的问题,设计了一种在二维结构中互连的虚通道路由器模型。采用改进的自适应XY路由算法,智能地分配虚通道空闲资源,从逻辑上减少拥塞和等待时间,多路选择器交叉开关完成数据传输。通过ASIC设计,完成虚通道路由器硬件电路,应用Modesim工具进行仿真,达到网络互连传输的目的。     

Mesh网中高效无死锁自适应路由算法

提出了一种新的应用于三维Mesh网中的无死锁路由算法.在当今的商用多计算机系统中,二维和三维的Mesh网是多处理器网络最为常用的拓扑结构之一.在应用于Mesh网的平面自适应路由(Planar Adaptive Routing)算法中,每条物理通道只需三条虚拟通道就可以有效地在三维以及更高维的Mesh网中避免死锁的产生.然而,采用该算法,网络拓扑一维和三维分别有两条和一条虚拟通道始终处于空闲状态.该文所提出的算法针对三维Mesh网,每条物理通道只需两条虚拟通道就可以有效地避免死锁.文中通过充分的模拟数据验证了此算法的有效性.     

基于虚拟通道非均匀分布的路由算法

随着片上系统(systems on chip,SoC)集成度的提高,IP核之间的通信成为SoC急需解决的问题。近年来提出的片上网络(network on chip,NoC)是解决SoC通信问题的一种有效方法。虚拟通道和路由算法是NoC设计中的关键技术,对NoC的延时、吞吐量等性能有重要的影响。根据NoC负载分布特点,提出一种新的虚拟通道非均匀分布技术VCND。该技术在Mesh内部使用虚拟通道,在边界上使用非虚拟通道,从而减少缓冲单元的数量。同时提出一种改进的无死锁路由算法CXY(combination XY)。仿真结果表明,与XY路由算法和XY-YX路由算法相比,CXY路由算法提高了网络吞吐量,并降低了网络平均延时;相比虚拟通道均匀分布技术,VCND技术能够以较小的吞吐量和网络延时损失获得可观的缓冲单元利用率提升,并减少了路由器的面积。     

一种动态分配虚拟输出队列结构的片上路由器

传统虚通道流控技术的片上路由器通过增加虚通道缓解排头阻塞引起的链路吞吐率下降以及网络拥塞的同时,面临缓冲区低利用率、仲裁开销较大等问题.而动态虚通道流控的片上路由器虽可通过动态管理缓冲单元,提高缓冲区利用率与链路吞吐率,但却不可避免流控与仲裁逻辑复杂度与开销的快速增长.为了提高链路吞吐率与缓冲区利用率,获得较好的性能与开销折中,提出一种动态分配虚拟输出队列结构的片上路由器DAVOQ,该结构通过快速链表动态组织虚拟输出队列,同时使用超前路由机制以简化仲裁逻辑,优化流水线.模拟与综合的结果表明,相比传统虚通道路由器,DAVOQ路由器改善报文传输延迟与吞吐率的同时,在0.13μm CMOS工艺下,节省了15.1%的标准单元面积与12.9%的漏电流功耗;而相比动态虚通道路由器,DAVOQ路由器能够以较小的吞吐率损失获得可观的延迟改善,同时节约15.6%的标准单元面积与20.5%的漏电流功耗.     

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

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

采用泛播路由构建高效中继路由系统

中继路由系统由一组中继路由器组成,为不能交换路由信息的路由域提供中继路由.该系统的关键是为路由域配置恰当的中继路由器.为所有中继路由器分配一个泛播地址,将它们当作一个逻辑节点,借助泛播路由以最短路径到达该逻辑节点.此外,采用源路由的方法将数据报文路由至中继路由器.基于泛播的中继路由系统实现了中继路由的自动配置,提高了中继路由的性能和可靠性,并且与现有网络系统兼容,实施代价很小.     

Fuzzy-based Adaptive Routing Algorithm for Networks-on-Chip

In this paper, we propose two adaptive routing algorithms to alleviate congestion in the network. In the first algorithm, the routing decision is assisted by the number of occupied buffer slots at the corresponding input buffer of the next router and the congestion level of that router. Although this algorithm performs better than the conventional method, DyXY, in some cases the proposed algorithm leads to non-optimal decisions. Fuzzy controllers compensate for ambiguities in the data by giving a level of confidence rather than declaring the data simply true or false. To make a better routing decision, we propose an adaptive routing algorithm based on fuzzy logic for Networks-on-chip where the routing path is determined based on the current condition of the network. The proposed algorithm avoids congestion by distributing traffic over the routers that are less congested or have a spare capacity. The output of the fuzzy controller is the congestion level, so that at each router, the neighboring router with the lowest congestion value is chosen for routing a packet. To evaluate the proposed routing method, we use two multimedia applications and two synthetic traffic profiles. The experimental results show that the fuzzy-based routing scheme improves the performance over the DyXY routing algorithm by up to 25% with a negligible hardware overhead.     

A Necessary and Sufficient Condition for Deadlock-Free Wormhole Routing

An important open problem in wormhole routing has been to find a necessary and sufficient condition for deadlock-free adaptive routing. Recently, Duato has solved this problem for a restricted class of adaptive routing algorithms. In this paper, a necessary and sufficient condition is proposed that can be used for any adaptive or nonadaptive routing algorithm for wormhole routing, as long as only local information is required for routing. The underlying proof technique introduces a new type of dependency graph, thechannel waiting graph, which omits most channel dependencies that cannot be used to create a deadlock configuration. The necessary and sufficient condition can be applied in a straightforward manner to most routing algorithms. This is illustrated by proving deadlock freedom for a partially adaptive nonminimal mesh routing algorithm that does not require virtual channels and a fully adaptive minimal hypercube routing algorithm with two virtual channels per physical channel. Both routing algorithms are more adaptive than any previously proposed routing algorithm with similar virtual channel requirements.     

LCFAA:一个低代价的完全自适应路由算法

大规模并行处理机系统（ＭＰＰ）中路由算法对互联网络通信性能和系统性能起着重要作用。自适应路由算法具有灵活性好、网络的通道利用率高和网络容错能力强等优点,但其实现难度较大,因而目前仅在少数ＭＰＰ系统中得以实现。文中在ｍｅｓｈ结构上提出了一个低代价无死锁的安全自适应最短虫孔路由算法ＬＣＦＡＡ,该算法所需虚通道数少,具有代价低、自适应性强的特点。文中证明了算法的无死锁、无活锁性和完全自适应性,并模拟验证     

基于嵌入式技术的传感器网络无尺度路由算法

提出了一种基于无尺度特征的传感器网络路由算法，该算法可以实现自组创建并动态调整网络的无尺度网络拓扑结构，并在该拓扑结构的上层构成虚拟骨干网，支撑整个网络的数据传输。为提高数据的冗余可靠性，采用了多路径路由的设计原则。同时结合了信息融合的概念，各骨干节点把收到的冗余互补数据遵循“先融合后转发”的原则，可有效地获得被感知对象的确知信息，大大降低了网络的传播代价，提高了网络的生命周期。     

Compressionless wormhole routing: an analysis for hypercube with virtual channels

Several recent studies have shown that adaptive routing algorithms based on deadlock recovery have superior performance characteristics than those based on deadlock avoidance. Most of these studies, however, have relied on software simulation due to the lack of analytical modelling tools. In an effort towards filling this gap, this paper presents a new analytical model of compressionless routing in wormhole-routed hypercubes. This routing algorithm exploits the tight coupling between wormhole routers for flow control to detect and recover from potential deadlock situations. The advantages of compressionless routing include deadlock-free adaptive routing with no extra virtual channels, simple router design, and order-preserving message transmission. The proposed analytical model computes message latency by determining the message transmission time, blocking delay at each router, multiplexing delay at each network channel, and waiting time in the source before entering the network. The validity of the model is demonstrated by comparing analytical results with those obtained through simulation experiments.     

一个高效完全自适应路由器的设计

路由器在大规模并行处理机（MPP）系统中对互连网络通信性能和系统性能的发挥起着关键作用。根据全自适应路由算法BNP设计框架,给出Mesh上一类基于BNP的全自适应路由算法BBFAM（thBNR-based fully adaptive algorithms on mesh);同时提出并采用动态优先级流控,“自由度”通道选择策略,设计了一个基于BNR,简洁,低代价的高效完全自适应路由器BFR（the BNR-based fully adaptive router),并采用Aletera CPLD器件构造了原型系统。     

Adaptive Virtual Cut-Through as a Viable Routing Method

Adaptivevirtual cut-throughis considered as a viable alternative towormhole switchingfor fast and hardware-efficient interprocessor communication in multicomputers. Computer simulations are used to show that our implementation of a minimal-path fully-adaptive virtual cut-through algorithm outperforms both deterministic and adaptive wormhole switching methods under both uniform random message distributions and clustered distributions such as the matrix transpose. A hardware-efficient implementation of adaptive virtual cut-through has been implemented using a semi-custom-designed router chip that requires only 2.3% more area than a comparable deterministic wormhole router chip. A network interface controller chip, which is crucial to our adaptive virtual cut-through method, has also been designed and is under fabrication.