基于2D Mesh的NoC路由算法设计与仿真

在研究Turn Model模型的基础上,提出一种基于2D Mesh结构的XY-YX路由算法,是一种确定性的无死锁的最短路径路由算法。给出无死锁的证明,通过片上网络（NoC）模拟仿真实验平台NIRGAM,将该算法在一个4×4的2D Mesh网络中进行仿真,并与XY路由算     

基于不规则Mesh的NoC无死锁路由

网络拓扑的选择是NoC设计中的一个重要问题,目前典型的特定应用NoC系统通常集成多个不同功能、不同尺寸、不同通讯需求的组件,而规则的网络拓扑结构并不适于在这种类型的NoC中应用,因此不规则Mesh网络被提出并被应用于不规则结构的NoC系统.为解决规则 Mesh路由算法在不规则Mesh中无法保证路由连通性的问题,本文提出一种不规则Mesh无死锁路由算法,无论NoC系统集成组件的版图如何变化,这一算法始终是连通的,即算法与不规则Mesh的规模和结构是无关的,同时算法仅使用较低的虚拟通道.     

2D Mesh结构中一种新的自适应路由模式

针对2D Mesh拓扑结构中的损坏节点会导致静态XY路由算法无法有效传输的问题,提出了一种新的路由算法——FTXY路由算法。首先对网络拓扑结构中的平均延时、理想平均吞吐量和能量消耗进行了理论评估,然后在NIRGAM仿真软平台上采用FTXY路由算法对上述三个参数进行验证,并与XY路由算法进行比较。实验结果显示,新的路由算法可以有效地绕过损坏节点,并且不会造成阻塞,提高了网络的传输性能。     

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

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

一种不规则2DMesh的NoC路由算法

NoC的网络拓扑结构是其研究的重要方面,在一些实际应用中,NoC系统通常集成多个不同功能、不同尺寸、不同通讯需求的组件,而规则的拓扑结构并不适应于在这种类型的NoC中应用,因此不规则Mesh网络被应用于不规则的NoC系统,为解决规则Mesh路由算法在不规则Mesh中无法保证路由连通性问题。提出一种不规则Mesh无死锁路由算法,同时此算法与其他算法相比,具有更少的虚通道和更优秀的路由路径选择。     

多优先级自适应片上网络路由算法设计

提出一种适用于二维网格结构的片上网络(NoC)路由算法,该算法具有自适应性与最短路径的特点.采用多种优先级对数据进行裁决并传输,能提高系统的吞吐量,降低网络延迟.通过采用NIRGAM仿真平台对算法进行仿真,在4×4网格结构下,与其他NoC路由算法进行性能对比,结果显示该算法在热点模式下具有优势.     

基于报文检测的快速自适应NoC容错路由算法

传统的自适应片上网络(NoC)容错路由算法采用一步一比较的方式来确定最优端口, 未能有效降低传输延迟。根据数据包在2D Mesh NoC前若干连续的跳数内最优端口固定的特点, 提出了一种基于报文检测的快速(FPIB)自适应容错路由算法。算法采用跳步比较的方式来减少数据包的路由时间, 并使用模糊优先级策略来进行容错路由计算。实验结果表明, 与uLBDR容错路由算法相比, 该算法能有效地降低平均延迟, 且实现算法的硬件开销更低。     

WiMAXMesh网络路由与调度算法研究

WiMAX Mesh网络引入多跳的方式实现远距离通信,取得覆盖范围和吞吐量的性能优化.在集中式Mesh网络中,路由与调度算法对网络性能有重要影响.针对Mesh模式提出一个新的方案,在基于冲突感知与负载平衡路由的基础上,利用多信道单收发机模式,采用联合调度和信道分配算法提高系统性能.仿真结果表明,该算法在调度长度和归一化...     

基于一种新网络拓扑结构的低功耗研究

随着芯片集成度的提高,片上网络(Network on Chip,NoC)是片上系统(System on Chip,SoC)发展的必然趋势,其中功耗成为限制性能提高的瓶颈.为了降低NoC的功耗,提出一种新的拓扑结构HMesh(Hexagon Mesh)及适用于该拓扑结构的HM路由算法,并对Mesh、Torus和HMesh结构的功耗进行了仿真实验.实验结果表明,在网络不发生拥塞时,HMesh结构的平均功耗比Mesh结构和Torus结构分别降低了12.9％和11.24％,更适合片上网络的构造.     

一种邻节点状态感知的NoC可重构容错路由

芯片特征尺寸的减小导致NoC的故障发生率越来越高.针对传统NoC容错算法中容错路由路径过长的问题,提出了一种可重构容错路由算法.该算法基于扩展的细粒度功能故障模型,对邻节点的故障情况及时掌握,并结合新的路由端口优先级策略和奇偶转向模型,实现了数据包的无死锁最优化容错路由.实验表明,该算法的路由路径更接近于最短路由路径,同时以增加较少的硬件开销为代价,获得了更优的容错性能,并具有更低的延迟和更高的吞吐量.     

基于拥塞控制的片上网络多播路由算法

为了满足片上网络日益丰富的应用要求,多播路由机制被应用到片上网络,以弥补传统单播通信方式的不足。以Mesh和Torus类的片上网络为例,分析了基于路径的3种多播路由算法(即XY路由、UpDown路由和SubPartition路由算法),并研究了相应的拥塞控制策略。通过模拟实验表明,多播较单播通信具有更小的平均传输延时和更高的网络吞吐量,且负载分配均匀;特别是SubPartition路由算法随着规模增大效果更加明显;提出的多播拥塞控制机制,能更有效地利用多播通信,提高片上网络的性能。     

A novel 3D NoC architecture based on De Bruijn graph

Networks on Chip (NoC) and 3-Dimensional Integrated Circuits (3D IC) have been proposed as the solutions to the ever-growing communication problem in System on Chip (SoC). Most of contemporary 3D architectures are based on Mesh topology, which fails to achieve small latency and power consumption due to its inherent large network diameter. Moreover, the conventional XY routing lacks the ability of fault tolerance. In this paper, we propose a new 3D NoC architecture, which adopts De Bruijn graph as the topology in physical horizontal planes by leveraging its advantage of small latency, simple routing, low power, and great scalability. We employ an enhanced pillar structure for vertical interconnection. We design two shifting based routing algorithms to meet separate performance requirements in latency and computing complexity. Also, we use fault tolerant routing to guarantee reliable data transmission. Our simulation results show that the proposed 3D NoC architecture achieves better network performance and power efficiency than 3D Mesh and XNoTs topologies.     

一种对片上网络中Mesh结构的改进策略及路由算法

Mesh结构以其简单、规整、易于实现与扩展的特性而成为现在广泛应用的片上网络拓扑模型。对2D-Mesh结构进行了改进,给出了顶点互连的Vertices interconnect Mesh(VMesh)结构;同时,提出了在此结构上的无死锁路由算法。最后,通过详细的计算证明,此结构可以减小网络直径和平均延迟,增加吞吐量;并用gpNoCsim模拟器对此结构及算法进行了仿真,结果表明,此结构具有较小的平均延迟和平均距离。     

三维片上网络研究综述

三维片上网络以其更短的全局互连、更高的封装密度、更小的体积等诸多优势,已引起国内外学术界和产业界的高度重视.对三维片上网络的研究,将直接影响一个国家未来三维集成电路和三维芯片产业的发展,也关系到国家安全.近年来,三维片上网络逐渐成为片上网络研究领域的一个重要方向,已取得了许多研究进展,但仍然存在许多挑战性的课题.对三维片上网络的基本问题作了简介;分析了三维片上网络在国内外的研究现状;讨论了三维片上网络研究中的关键问题,归纳出网络拓扑结构、路由机制、性能评估、通信容错、功耗、映射、测试、交换技术、服务质量、流量控制、资源网络接口等12类研究课题;分类综述了关键问题的研究进展;分析了三维片上网络存在的问题;指出,在三维片上网络拓扑结构方面:个性化拓扑结构设计、仿真平台研究开发、基于新型拓扑结构的三维芯片样片试制以及无线技术的引入等,在路由算法方面:适合3D Torus的路由算法、结合无关路由与自适应路由算法优点的新路由算法、适合各种新型拓扑结构的高效路由算法等,在性能评估方面:永久故障的容错、改进仿真程序增加对物理链路的建模、充分考虑通信的局部性等,在功耗方面:对拓扑结构/映射算法/路由算法和布局进行综合优化、动态和静态控制相结合、更为精确的3D NoC功耗模型等,在映射方面:发热均匀性、动态路由策略下映射评估模型的优化、低功耗映射算法、基于优化算法的组合映射等,都将是三维片上网络未来的重要研究课题.     

一种用于片上网络的拥塞感知哈密尔顿最短路径路由算法

类脑处理器能够支持多种脉冲神经网络SNN的部署来完成多种任务。片上网络NoC能够用较少的资源和功耗解决片上复杂的互连通信问题。现有的类脑处理器多采用片上网络来连接多个神经元核,以支持神经元之间的通信。SNN在时间步内瞬时突发的通信会在短时间内产生大量的脉冲报文。在这种通信行为下,片上网络会在短时间内达到饱和,造成网络拥塞。片上网络中非拥塞感知路由算法会进一步加剧网络拥塞状态,如何在每一个时间步内有效处理这些数据包,从而降低网络延迟,提高吞吐率,成为了目前需要解决的问题。首先对SNN的瞬时猝发通信特性进行了分析;然后提出一种拥塞感知的哈密尔顿路径路由算法,以降低NoC平均延迟和提高吞吐率;最后,使用Verilog HDL实现该路由算法,并通过模拟仿真进行性能评估。在网络规模为16×16的2D Mesh结构的片上网络中,相对于没有拥塞感知的路由算法,在数量猝发模式和概率猝发模式下,所提出的拥塞感知路由算法的NoC平均延迟分别降低了13.9%和15.9%;吞吐率分别提高了21.6%和16.8%。     

2D Mesh片上网络分区容错路由算法

为了减小路由表的规模且避免使用较多虚通道(VC),从而降低硬件资源用量,针对虫孔交换的2D Mesh片上网络提出了一种分区容错路由(RFTR)算法。该算法根据故障节点和链路的位置将2D Mesh网络划分为若干个相连的矩形区域,数据包在矩形区域内可使用确定性或自适应路由算法进行路由,而在区域间则按照up^*/down^*算法确定路由路径。此外,利用通道依赖图(CDG)模型,证明了该算法仅需两个虚通道就能避免死锁。在6×6 Mesh网络中,RFTR算法能减少25%的路由表资源用量。仿真结果表明,在队列缓存资源相同的情况下,RFTR算法能实现与up^*/down^*算法和segment算法相当甚至更优的性能。     

片上网络的星型簇结构通信能耗研究

相对于传统的平面结构,三维片上网络具有更好的集成度和性能。提出一种基于三维网格的星型簇结构的片上网络(3D SCBM-NoC),3D SCBM-NoC可以减少路由节点,降低处理节点间的通信代价。通过分析3DSCBM-NoC的拓扑结构,建立了针对星型簇结构的片上网络通信能耗模型,分别使用顺序方法和蚁群算法实现了片上网络映射。实验结果表明,相对于处理节点规模相同且数目为16的3D Mesh-NoC和2D Mesh-NoC,3DSCBM-NoC的通信能耗明显降低。     

A survey of routing algorithm for mesh Network-on-Chip

With the rapid development of semiconductor industry, the number of cores integrated on chip increases quickly, which brings tough challenges such as bandwidth, scalability and power into on-chip interconnection. Under such background, Network-on-Chip (NoC) is proposed and gradually replacing the traditional on-chip interconnections such as sharing bus and crossbar. For the convenience of physical layout, mesh is the most used topology in NoC design. Routing algorithm, which decides the paths of packets, has significant impact on the latency and throughput of network. Thus routing algorithm plays a vital role in a wellperformed network. This study mainly focuses on the routing algorithms of mesh NoC. By whether taking network information into consideration in routing decision, routing algorithms of NoC can be roughly classified into oblivious routing and adaptive routing. Oblivious routing costs less without adaptiveness while adaptive routing is on the contrary. To combine the advantages of oblivious and adaptive routing algorithm, half-adaptive algorithms were proposed. In this paper, the concepts, taxonomy and features of routing algorithms of NoC are introduced. Then the importance of routing algorithms in mesh NoC is highlighted, and representative routing algorithms with respective features are reviewed and summarized. Finally, we try to shed light upon the future work of NoC routing algorithms.