片上网络的拓扑结构研究

胡伟

（黄山学院 信息工程学院，安徽 黄山 245021）

片上网络的拓扑结构研究

胡伟

（黄山学院 信息工程学院，安徽 黄山 245021）

随着SoC体系结构设计复杂度的提高，传统的总线结构已成为IP核之间通信的瓶颈，新的设计方法片上网络(NoC)应运而生。在对NoC拓扑结构进行了分类的基础上，分析了各种网络拓扑的相关特性，结果表明这些拓扑结构都具有良好的可扩展性，文章还探讨了NoC拓扑结构的发展方向。

片上网络（NoC）；片上系统（SoC）；拓扑结构

1 引 言

随着半导体工艺技术步入纳米阶段，在单一芯片中集成上亿晶体管已经成为现实，片上系统（SoC）的发展已经进入极其迅速的时代。按照不同的片上互连方式，多核SoC可分为两大类，即传统的基于总线的互连和基于网络的互连。前者是现有SoC的扩展，通过多总线及层次化总线等技术使得片上集成更多的处理器核，从而实现高复杂度和高性能，而后者是近些年提出的崭新概念，即多处理器核之间采用分组路由的方式进行片内通信，从而克服了由总线互连所带来的各种瓶颈问题，这种片内通信方式称为片上网络 (Network on a Chip，NoC)。自从NoC概念在2000年第一次被提出，已经过10年的发展，已经进入技术逐步成熟的阶段。

2 片上网络体系结构

NoC中允许存在任意类型的资源节点，典型的资源节点可以是带缓冲的嵌入式微处理器和DSP核、专用硬件资源、可重构硬件资源，或者是上述各种硬件的组合。图1显示了资源节点中可能包含的硬件资源。计算类的资源节点以微处理器核、DSP核等形式存在，而存储类的资源节点则要求尽可能地分散，以避免访问数据时要跨越整个芯片。各种尺寸的SRAMS、DRAMS、FLASH满足了不同的需求。

图1 资源节点中包含各种类型的硬件资源

通讯节点是互连网络中的主要部分，其核心就是交换开关。如网络中的路由器，其主要作用是寻找出信息从起点到终点的最短最有效的路径。在数据传输中，有两种路由方式可供设计者选择：确定性路由（deterministic routing）和自适应路由（adaptive routing）但是对于NoC设计，自适应路由规则并不适合。这并不是考虑自适应路由中路由表的存在，而是由计算升级和维持信息的复杂度决定的。

3 片上网络的拓扑结构

为了满足不同的性能和成本等需求，人们设计了很多不同的专用多处理器网络拓扑。MPSoC (Multi-Processor System-on-Chip)网络可以被分成直接网络和间接网络两类。在直接网络MPSoC中，节点处理器通过网络直接相互连接，每个节点执行数据流路由和仲裁。在间接网络MPSoC中，节点处理器通过一个或多个中间节点开关相连，开关节点执行路由和仲裁功能。间接网络也称为多阶段互连网络（Multistage Interconnect Networks,MIN）。

NOC的拓扑结构有直接网络Orthogonal拓扑，立体连接循环（Cube-Connected-Cycle）拓扑、Octagon拓扑等；间接网络拓扑Crossbar Switch结构、Fully-Connected网络、Butterfly拓扑等。

3.1 直接网络拓扑

3.1.1 Orthogonal拓扑

Orthogonal拓扑网络中节点以K-阵列N-维Mesh[1]或者K-阵列N-维Torus[2]形式互连。如图2所示的就是一个2-D Mesh网格结构，从图中可以看到，每个资源节点和一个交换节点相连，而一个交换节点和4个相邻的交换节点相连，二维网格结构在带宽、时延等通信性能上并不是最优，但其结构简单、可重用性好、可扩展性强，因此成为研究最多的拓扑结构。Torus网络结构在Mesh网格结构的基础上,将位于边缘的两个节点也连接了起来，如图3所示，环面网络结构的优点在于增强了位于边缘的节点之间的通讯，其缺点在于增加的边缘的节点之间的连线与其它连线有交叉,增加了布线的困难。Mesh和Torus网络在并行计算平台中被广泛使用。

图2 Mesh网络

图3 Torus网络

3.1.2 立方体连接循环拓扑

立方体连接循环拓扑是为了减少Orthogonal拓扑中每个节点的度而设计的。如图4所示，3-立方结构的每个节点有3个度，而在Mesh和Torus网络中每个节点有2n个度，立方体互连周期拓扑有一个层次化结构，在立方体的每个角上3个节点形成一个局部环。

图4 Octagon网络

3.1.3 Octagon拓扑

Octagon网络是为网络处理器提出的一个片上通信结构。F.Kariml[3]等人在设计网络处理器时提出了一个如图5所示的八角形网络。这种结构中，8个处理器通过一个Octagon环和3个直径相连。任意两个处理器之间的延迟在局部环中不超过两个阶段，即通过一个中间节点，这个Octagon网络是可伸缩的。如果一个处理器作为桥节点，可以把更多的Octagon连在一起。

图5 立方连接循环

3.2 间接网络拓扑

3.2.1 Crossbar Switch结构

一个N×N Crossbar网络连接N个输入端口和N个输出端口。N个输入端口的任意一个都可以和任意一个输出端口通过对应的交叉点上的节点开关相连。

图6 CrossbarSwitch结构

3.2.2 Fully-Connected网络

一个N×N完全互连网络使用MUXes把每个输入聚合到输出，如图7所示。仲裁器控制着每个MUX，决定哪个输入指向哪个输出。

图7 全连接Switch结构

与交叉网络相似，完全互连开关网络也常称为Crossbar，在完全互连开关网络中，每个源-目的连接有专门的数据路径。

3.2.3 Butterfly拓扑

Butterfly网络（如图8）是一个间接网络结构。在Butterfly结构中，每个源到目的路由是用一个专门的数据路径。任意两个处理器节点之间的延迟是一样的，延迟时间由开关结构上的中间阶段数目决定。

图8 Butterfly结构

Butterfly拓扑有很多不同的同构变体，如Banyan Network，Batcher-Banyan Networks等。

3.2.4 Fat-tree拓扑

树中的内节点是开关，叶子是处理器。除了根节点，每个内节点只与其父节点和若干个子节点相连。传统K叉树的主要问题是单个父节点尤其是根节点,容易成为通信瓶颈。Leiserson[4]于1985年提出的胖树，一个节点可拥有多个父节点,可以缓解此问题。因此，和Butterfly网络不同，胖树网络从源节点到目的节点提供了多个数据路径。胖树网络可被看作一个扩展的有多个根节点的n-列树网络，网络延迟依赖于树的深度。

如图9所示，SPIN[5]网络是一个4-列胖树拓扑的设计例子，每个处理器位于这个胖树的叶子节点上。被分割为分组的消息通过向上或向下遍历胖树网络在处理元件之间进行分组交换。一个分组被定义为一个36位的字。分组的头占用第一个字，头的一个字节代表目的地址，其他位用于作分组标志和路由信息。分组的有效负载时可变的，每个分组由一个尾部来终止，尾部不含数据，而是用来检错的。

图9 SPIN网络

4 各种拓扑结构的对比

用来刻划一个拓扑结构的特征，并影响其性能的而又彼此关联的参数有：节点数，节点度，网络直径和链路数等。表1总结了一些典型规则拓扑的特性参数，这些参数常用来估计网络的复杂性、通信效率、成本等，是选择网络拓扑的重要依据。

表1 典型规则拓扑的特性

5 结 论

NoC解决了在SoC设计中存在的问题，是一种新的设计方法，它在信息吞吐量、延迟、能耗和芯片面积等方面做出了很大的改进。本文分析了NoC中常见的拓扑结构，指出了每种拓扑结构的主要特点，并综合地对几种典型拓扑从节点数，网络直径，节点度，链路数等方面进行了对比分析，这些拓扑结构都具有良好的可扩展性。

未来NoC拓扑结构的主要发展方向是：

1.增强系统的可测试性和可靠性，降低设计的风险；

2.研究Noc模拟工具，降低设计成本，提高设计效率；

3.设计低复杂度的拓扑结构，减小芯片面积；

4.研究NoC降低功耗，提高系统性能。

同时，NoC涉及了从物理实现到体系结构，到操作系统，到应用的各个层次，也就需要对其各个层面进行研究。

[1]M.Forsell,A scalable high-performance computing solution for networks on chips[J].IEEE Micro,2002,22(5):46-55.

[2]WJDally,B Towles,RoutePackets,NotWires:On-Chip Interconnection Networks[J].DAC 2001,IEEE,2001,18 (6):684-689.

[3]F.Karim,A.Nguyen,S.Dey,R.Rao.On -chip communication architecture for OC -768 network processors [J]. Proceedings of 38th Design Automation Conference,June 2001,25(6):.678-683.

[4]LEISERSON C E.Fat-trees:Universalnetworks for hardware-effi-cient supercomputing[J].IEEE Transactions on Computers,1985,34(10):892-901.

[5]ADRIAHANTENAINA A,CHARLERY H,GREINER A,et al.SPIN:A scalable,packetswitched,on-chipmicronetwork[C]//Proceedings of Design,Automation and Test in Europe Conferenceand Exhibition.Washington, DC, USA:IEEE ComputerSociety,2003:70-73.

Research on the Topology Structure of Network-on-Chip

Hu Wei
(School of Information Engineering,Huangshan University,Huangshan 245021,China)

With the increasing complexity of SoC structure design,the traditional bus structure has become the bottleneck of communication among IP blocks,thus a new design method for network-on-chip (NoC)came into being.On the basis of a classification for NoC topology structures,each specific topology was discussed in details.The results showed that the topology structures have good scalability.At the end of the paper,the future research direction of NoC topology structure was presented.

Network-on-Chip(NoC);System-on-Chip(SoC);topology structure

TP302

A

1672-447X(2010)04-0083-04

2010-05-10

胡 伟(1978-),安徽绩溪人,黄山学院信息工程学院讲师，硕士,主要研究方向为嵌入式系统综合与测试、计算机控制。

胡德明