连接主从IP核的Octagon环形网络拓扑结构

摘要：本文提出了一种连接主从IP核的Octagon环型（Master-Slave IP Core connected Octagon Loop ,MSOL）拓扑结构,该拓扑结构具有8m个节点,并且每个节点分别连接主从IP核，除外层环上各核连接3个相邻节点外，内层环上各节点均与4个相邻节点连接。MSOL 是一种拓扑结构简单、平面的、对称的并且具有良好扩展性的互连网络，采用基于最短路径的路由算法，在仿真实验中，对MSOL，Mesh和Cluster-Mesh网络的平均通讯延迟和平均吞吐量进行了模拟分析，结果表明MSOL互连网络较好的平衡了网络性能和成本，是一种更为优化、高效的片上网络拓扑结构。

关键词：片上网络 NoC 拓扑结构 路由算法

Master-Slave IP core connected Octagon

Loop Topology for Network-on-chip

WANG Hui，WANG Chang-shan

（School of Computer Science&Technology，Xidian University，Shannxi ，Xi’an ，710071）

Abstract:This paper presents a topology - Octagon loop structure connect the Master-Slave IP core （Master-Slave IP Core Octagon Loop, MSOL）, the topology has 8m nodes and each node connects Master-Slave IP core, respectively, except for layer ring each node connects 3 adjacent nodes, each node on the inner ring connects 4 adjacent nodes. MSOL is a topology simple, flat, symmetrical and has a good scalability of the interconnection network, routing based on shortest path algorithm, in the simulation experiment,the MSOL was compared with Mesh and Cluster-Mesh for the average network communication delay and the throughput, The results show that the MSOL topology is a good trade-off between performance and cost．It is a more optimal and efficient network-on-chip topology.

Key words: network-on-chipNoCtopologyrouting algorithm

随着片上系统（SoC）和纳米级 CMOS 集成电路技术的不断发展，片上多处理器（CMP）技术开始朝多核化和异构化的方向发展。 SoC 设计中广泛采用的共享总线结构，已经无法满足 SoC 系统的需要，成为制约CMP 性能的主要瓶颈。片上网络（Network-on-chip，NoC）技术应运而生，核心思想就是将计算机网络技术移植到芯片设计中来，用网络取代传统的总线结构，从而省去了大量的专属线，减少了布线资源。同时，它使电参数可控，计算与通信分离，并且提供了良好的并行处理与通信能力，是一个能在芯片级上进行路由的微型网络。

片上网络的拓扑结构体现了 NoC 中的通讯节点是如何在芯片中分布和连接的。拓扑结构的选择对系统性能和芯片面积具有显著的影响。拓扑结构的衡量标准通常是以理论上影响路由成本和性能为基础的，除了要考虑普通网络中所关心的节点数量、边的数量、网络维度、网络直径、平均距离、对分宽度之外，还要考虑通信模式的嵌入属性，例如消息吞吐量、传输延迟、功耗、芯片面积等因素。

在NoC中，最适合且使用最广的网络结构是包交换的直接网络。每个节点通过双向通道连接到相邻的节点。在大规模的集成芯片中，NoC并非是单一的拓扑结构，很可能是一种层次化的混合网络拓扑结构，通信密集的组件组合在一起，构成一个子网络，以实现高效的通信。本文提出了一种新的、称为MSOL的NoC拓扑结构，实验结果表明，这种结构与现有的几种拓扑结构相比，在某些特定条件下，性能更加优化、高效[1-3]。

1MSOL网络拓扑的基本结构

在NoC的研究过程中，人们在简单的环型总线结构的基础上提出了一个笼统的拓扑规范――Spidergon，它是对环总线结构的一种改进，缩短了平均距离，并且使网络具有了一定的可扩展性。而Octagon是Spidergon当N=8时的特例。这种结构的最大特点就是网络距离短，任何两个结点之间通信最多只需两步即可完成。运用在其上的分组形式和路由算法均比较灵活，并且布线复杂度较交叉开关结构低很多[5]。

图1中，对Octagon的布线方式和传统的交叉开关（Crossbar）的布线方式进行了比较。如图1（a），各连接之间采用两条反向的单向链路，共24条，在布线复杂度上明显低于交叉开关结构。

Octagon有两种扩展方式（如图2）。其一是两个Octagon通过一个中间节点连接的结构，但很显然这种结构的中间节点将成为通信的瓶颈。另一种结构是把一个Octagon中的每一个节点都扩展成一个Octagon，再把相应位置的节点连接起来，但这种方法的致命弱点是布线复杂度太高[4]。

为解决Octagon以上两种扩展方式的突出瓶颈，本人提出了一种连接主从IP核的Octagon环型（Master-Slave IP Core Octagon Loop，MSOL）拓扑结构，该拓扑结构具有8m个节点，并且每个节点分别连接主从IP核，除外层环上各核连接3个相邻节点外，内层环上各节点均与4个相邻节点连接。MSOL是一种拓扑结构简单、平面的、对称的并且具有良好扩展性的互连网络。

图3所示为外接一环，具有16个节点的MSOL结构。

MSOL结构有效回避了Octagon原结构的扩展瓶颈，具有良好的扩展性，在每环节点固定的情况下只需扩展环数，网络是平面性的，极大地方便了网络的布局布线，并且有效地继承了Octagon结构网络距离短的优点，与环、Mesh及Octagon自身扩展结构相比具有明显的网络距离优势，其与各个拓扑结构性能参数对比如表1所示。

2基于最短路径的路由算法

路由算法是影响片上网络通信效率的重要因素．充分利用MSOL 网络拓扑结构和节点分布连接的特点，每个节点接收到消息后，由本节点决定是接收该消息到主或从IP核还是计算路由将该消息发送到相邻节点，本节点采用基于最短路径的路由算法[5]，具体步骤如下：

输入：源节点（SR ,Sθ），目的节点（DR ,Dθ）

输出：路由路径routpath

算法步骤：（cur_routerR ,cur_routerθ）

Step1：初始化当前路由节点（cur_routerR ,cur_routerθ）=（SR ,Sθ）；路由路径routpath=cur_router；

Step2：判断cur_routerR =DR？若cur_routerR =DR则执行步骤step3；否则执行步骤step4；

Step3：检查cur_routerθ =Dθ？若是则算法终止，输出路由路径routpath；否则，执行计算|Sθ -Dθ|值，并执行步骤step5；

Step4：判断cur_routerR >DR？，若cur_routerR >DR则执行（cur_routerR ,cur_routerθ）=（cur_routerR -1,cur_routerθ），routpath=[routpath,cur_router]，并返回步骤step2；否则执行（cur_routerR ,cur_routerθ）=（cur_routerR +1,cur_routerθ），routpath=[routpath,cur_router]，并返回步骤step2；

Step5：若00?，若是则（cur_routerR ,cur_routerθ）=（cur_routerR ,cur_routerθ-1），routpath=[routpath,cur_router]返回步骤step2；否则（cur_routerR ,cur_routerθ）=（cur_routerR ,cur_routerθ+1），routpath=[routpath,cur_router]返回步骤step2；

Step6: 若6≤|cur_routerθ-Dθ|≤7，则判断cur_routerθ-Dθ>0?，若是则（cur_routerR ,cur_routerθ）=（cur_routerR ,（cur_routerθ+1）mod8），routpath=[routpath,cur_router]返回步骤step2；否则（cur_routerR ,cur_routerθ）=（cur_routerR ,（cur_routerθ-1）mod8），返回步骤step2；

Step7: 若3≤|cur_routerθ-Dθ|≤6，则（cur_routerR ,cur_routerθ）=（cur_routerR ,（cur_routerθ+4）mod8）,routpath=[routpath,cur_router]返回步骤step2；

对主从IP核的说明：片上网络系统芯片内部由于各个IP核的功能不同，相互之间的数据访问量不同，通信和数据交换的频繁程度也不尽相同，这就造成了IP核之间的不对等性，一些IP核经常需要在其它IP核的配合下共同完成某项功能。那些能够主动产生请求的IP核，称之为主（master）IP核。另外一些IP核只是对主IP核的请求进行应答，称之为从（slave）IP核。已经有研究表明，采用经过优化设计的路由器连接区分主从的两个IP核可有效降低能耗，提高网络运行效率。

3仿真分析

NoC拓扑结构设计的两个重要的性能参数是平均通讯延迟和平均吞吐量。为了进一步研究MSOL互连网络的性能，模拟和分析了MSOL，Mesh和Cluster―Mesh结构，MSOL采用基于最短路径的路由算法，Mesh和Cluster―Mesh结构采用了x-y路由算法．x-y路由算法是一种维序路由算法，采用一条虚信道，虫孔交换机制，除Cluster―Mesh每个节点有4个外部网络接口连接IP到NoC外，Mesh及MSOL均连接主从两个IP核，根据模拟情况的不同可以是信源或者信宿。信源IP产生的数据包为8个字节分为1字节的头flit（flowcontrol unit，流控单元）、4字节的数据flit和3字节的尾flit，每个flit为4个字节，流入网络的速率和目的节点可以控制．每个输入通道具有8个flit的fifo，每个输出通道有1个flit的buffer，仿真时采用4×4的网络结构（网络节点数均为16），链路速率为100 Mbps。以下主要对均匀流量模式及10%热点模式下的几种互连网络的性能进行评估[6-8]。

图4（a）为均匀流量模式下三种网络拓扑中消息延迟比较，图4（b）是热点10%模式下三种网络中消息延迟比较，可以看出均匀流量模式和热点流量模式下，当所有的源节点均匀地增加注入速率时，网络的平均延迟增加直到达到饱和，采用MSOL结构的平均延迟都明显低于另两者，这与其较短的网络直径密切相关。

图5（a）为均匀流量模式下三种网络拓扑中网络吞吐性能比较，图5（b）是热点10%模式下两种网络中网络吞吐性能比较，可以看出均匀流量模式和热点流量模式下，采用MSOL结构的吞吐性能优于另两者。当所有的节点增加注入速率时，网络的吞吐量差别急剧增大，直到饱和状态。

4结论

本文在对现有经典平面拓扑结构进行深入分析与研究的基础上，提出了一种连接主从IP核的Octagon环型拓扑结构――MSOL，该结构具有网络距离短、扩展性好、可行性高的突出特点，针对该结构的特性，提出了适应该结构的基于最短路径的路由算法，有效地避免了死锁。对比分析了其与Mesh和CMesh拓扑结构的网络特性，仿真结果表明，MSOL有较低的通信延迟，较高的网络吞吐，是一种简单高效的平面互联网络。

参考文献

[1] 张恒龙，顾华玺，王长山. 片上网络拓扑结构的研究. 中国集成电路，16（11），pp. 42-46, 2007。

[2] Jayasimha D N，Zafar B，Hoskote Y．On-Chip Interconnection Networks：why They are Different and How to Compare Them[EB/OL]．[2008―09―12]．blogs．intel．com/research/terascale/．

[3] Tobias Bjerregaard, Shankar Mahadevan. A survey of research and practices of Network-on-chip. ACM

（下转第52页）

Computing Surveys, Vol.38,Issue 1, March 2006.

[4] Kim. Daewook, Packet Switch Scalable On-Chip Interconnection Architecture Design and Impleme- ntation for Networks-on-Chip, University of Minnesota,DAI-B 67/02, Aug 2006.

[5] Bononi L，Concer N．Simulation and Analysis of Network on Chip Architectures：Ring，Spidergon and 2D Mesh[C]//Proc of the Design，Automation and Test in Europe（DATE）．Munich：IEEE，2006：54―159．

[6] Salminen E，Kulmala A，Hamalainen T D．On Network-on-chip Comparison[CJ//10th Euromicro Conference on Digital System Design Architectures，Methods and Tools．Lubeck：IEEE，2007：503―510．

[7] N. Eisley, L-S Peh. High-level power analysis for on-chip networks, CASES'04, Washington, DC, USA, September 22-25, 2004.

[8] Axel Jantsch, Hannu Tenhunen. Networks on Chip. Dordrecht: Kluwer Academic Publishers, 2003.

作者简介

王辉，现就读于西安电子科技大学计算机学院，硕士研究生，主要研究方向为片上网络拓扑结构。