片上网络容错路由算法的综述与展望

陈中胜

摘要：随着多核系统中核芯数量的增加，基于总线的系统在可扩展性、平均传输延迟、功耗、性能等方面都受到严峻的挑战。片上网络（Network-on-Chip NoC）在这样的背景下应运而生，它充分借鉴了计算机网络中的通信思想，并且很好的考虑了片上系统（System On Chip，SoC）的特性，是一种适用于片上系统的通信架构。随着片上网络的提出，相关的研究也日益发展，比如片上网络拓扑，通信服务质量、片上网络路由算法、片上网络容错等等。其中片上网络容错路算法是其中比较重要也是比较有挑战的研究课题之一。本文首先简单介绍了片上网络，然后从几个方面介绍片上网络路由算法以及容错路由算法，最后指明容错路由算法一个值得研究的方向。

关键词：片上网络；容错路由算法；图论

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2019）12-0012-03

1 引言

片上系统指的是集成在一个芯片上完整的多核系统以及通信系统，随着技术的完善和半导体工艺的发展，片上系统能够包含多个处理器、存储器模拟电路等众多元器件和子系统[1]。但是随着集成的核心数量的不断增加，传统的总线式通信架构会遭遇到严重的面积开销和性能问题，这就亟须一种适用于超大规模片上系统的通信架构来替代传统的总线式结构。

在这种背景下，2001年，片上网络被研究机构提出。片上网络主要目标就是追求高质量的片内通信，它的设计借鉴了计算机网络中的成熟的通信思想，结合片上系统的电气特性，一经提出，就受到众多研究机构的关注与进一步研究。

一个典型的片上网络如图1所示，每个路由节点连接一个本地处理器，且直接与两个到四个邻居路由器节点直接相连。其中路由器与路由器之间、路由器与处理器之间通过双向链路连接。

2片上网络拓扑与路由算法

2.1片上网络拓扑

片上网络拓扑结构是片上网络需要研究的一个重要问题，拓扑结构指的片上系统内部各个节点之间以何种方式进行排列和连接。拓扑结构直接决定了片内各节点以何种方式进行通信，也就能够在很大程度上决定了片上网络的通信效率与性能。

最为常见的拓扑结构是2D Mesh[2]，如图2所示，这种结构最容易被理解，也是最容易在硬件上实现的一种拓扑结构。在这种拓扑结构中，路由器節点呈矩形排列，相邻节点之间通过双向链路连接，每个路由器节点连接一个本地处理器。

这种结构的优点是简单且易于实现，缺点是边界的节点没有形成一个闭环，这会导致某些路由需要较长的路由路径。

为了解决这种局限性，二维花托拓扑结构（Torus）[3]被提出。如图3所示这种结构是一种对2D Mesh的改进，通过在边界增加一个长的环路来连接边界节点，这样就可以保证每个节点都是对称的，可以尽量减少传输路径，缓解路由拥塞。这种结构的缺点也显而易见，它增加了布线的复杂度，大大提高的实现的难度。

如图4所示，胖树拓扑（fat tree）[4]是一种能够实现极少通信延迟的拓扑结构，在这种结构中，每个处理器节点与其他节点之间的路由路径都相等，这种结构的缺点就是，在根路由器节点上可能会造成严重的路由拥塞。

2.2路由算法

路由算法是片上网络设计中的另一个重要研究课题。路由算法的作用是负责将数据包准确地发送到目的地节点，除了达到这一目标之外，一个优秀的路由算法还需要考虑到服务质量，也就是要尽可能选择最短的路由路径，尽可能地减少通信延迟，还需要很好的缓解可能出现的路由拥塞，实现负载均衡。

2.2.1路由算法分类

路由算法的种类繁多，根据不同的分类标准也可以对其进行多种分类，本文中根据路由决策与网络状态的关系将路由算法分为静态路由算法与动态路由算法。

2.2.1.1静态路由算法

静态路由算法也可以叫作确定性路由算法或无关路由算法，因为它的路由决策是可以确定或是预先计算得到的，并且它与在线运行时的网络状态无关，也就是说这种路由算法不能很好地兼顾到路由时的网络状态，比如路由拥塞等问题。但是这种路由算法的路由路径也不一定是确定的，因为可以根据其他一些与网络无关的变量来选择不同的备选路径，比如循环选择、随机选择等，这些方式的引入都是为了更好的缓解路由拥塞。虽然选择的路径可能不同，但是这些备选路径都是静态的，都是可以在离线就进行计算好的，所以这种路由算法也还是可以称为静态路由算法。

这种路由算法一般计算较为简单，可以在线进行路由计算，也可以在离线时就把所有路由决策计算好，然后在线通过离线计算得到的路由表进行路由决策。基于路由表的路由算法在线路由计算一般会比不急于路由表的路由算法的在线路由计算要简单高效，但是由于需要在硬件中存储一张路由表，虽有他的缺点也显而易见，就是会造成更大的面积开销。

2.2.1.2动态路由算法

动态路由算法与静态路由算法不同，这种路由算法的路由决策会在片上网络在线运行时，除了根据数据包的源点和目的地，还会综合考虑片上网络的拥塞程度、温度、功耗等状态来进行路由决策。这种路由算法相较于静态路由算法能够更好地提升片上网络的路由性能，缓解路由拥塞，实现负载均衡。但是缺点也是显而易见的，要实现这些状态的综合考量，就必须要实现对应的状态检测机制，这就往片上系统中加入需要额外的硬件。在本来就对面积开销的要求苛刻的片上系统中，这无疑会造成严重的挑战。

除此之外，综合考虑状态来进行路由决策就会对增加路由算法的复杂度与实现难度，这也可会导致增加片上网络的开销和功耗。

2.2.2容错路由算法

片上网络系统由于自身电器特性以及元器件的老化，可能会导致节点、链路或其他元器件发生。在某些情况下，直接修复或替换这些故障元器件难度和成本过高，因此，片上网络需要有容错能力，以保证即使存在故障，片上网络也可以以尽可能小的影响正常工作。

容错相关技术是片上网络的重要支撑技术之一[5]，在路由算法层面，路由由于可以选择不同的路由路径来绕过故障的链路或节点，因此，只要对路由算法加以改进，就可以实现有很好效果的容错路由算法。

通过容错路由算法容忍故障的优点是可以无须或尽可能小的增加片上系统的面积开销，就可以实现对故障的容忍。缺点是由于需要加入对于故障的判断和容忍故障的路由计算，会导致算法的设计和实现较为复杂，路由路径不一定能选择最短路径，这就会导致更高的路由延迟，也就会影响片上网络的通信效率。

3容错路由算法展望

3.1 动机

传统的片上网络规模较小，故障链路的数量也较小。而业界也普遍在片上网络中认为发生单个故障的可能性就已经很低了，所以目前的大多数关于片上网络路由算法的研究工作都是针对单故障展开的，但是随着制造和继承工艺的不断发展和新的架构的提出，超大规模片上网络的实现已经越来越成为可能甚至已经被设计和实现。

Sunway TianHuLight超级计算机[6]，继承了260个核芯，采用的是晶圆级的片上网络架构设计，整个芯片面积仅为25平方厘米。由于它本身的电器特性和硬件老化会导致发生故障的可能性增加，而且这种设计要求极高的硬件集成和制造成本，一旦发生故障，无法对故障元器件进行替换和修复，也不能直接弃用整块芯片，这就需要有针对可能发生众多故障的超大规模片上系统的容错路由算法，来保证片上系统在存在多个故障时也能正常运行，并且对不可用的节点和链路进行弃用，从而可以降级使用片上系统。

3.2 展望

片上网络的结构可以抽象为节点与双向链路的组合，这可以很好的用数学中的图来进行抽象，于是可以将片上网络抽象成一张有向图，图中的节点对应的就是片上网络中的路由器节点，图中的有向边对应的就是片上网络中的链路，针对故障，我们可以删除图中对应的节点或是链路。于是我们可以将片上网络的路由算法和容错算法转化为图论中的问题来处理，比如寻找路由路径就可以看作是对图进行搜索，找到两个节点之间的最短路径，由于已经删除了故障节点和故障链路，那么容错算法也就自然而然地被实现了，且可以容忍数量众多故障。

对于众多故障导致的节点可能不连通的情况，我们可以使用最大强连通分量的概念来对片上网络中的不连通节点进行弃用，从而降级使用片上网络，保证在众多故障发生的情况下片上网络还可正常工作。

使用图论来解决片上网络容错容错路由算法还有一个优点就是无须考虑片上网络的拓扑结构，无论是2D、3D、Torus、异构等等拓扑结构。因为在图中，只需要考虑节点与边的关系，而无须考虑它们是如何排列的。

以上种种观点都能充分表明图论是解决超大规模片上网络中容忍众多故障的一个有前景的研究方案。

4总结

本文介绍了片上网络的相关概念，并总结了片上网络的几种典型的拓扑结构以其其各自的优缺点，通过路由算法与网络状态的关系，本文对片上网络的路由算法进行一个大致的分类，并详细介绍不同路由算法的路由特点以及各自的局限性的优越性。然后介绍了容错路由算法以及其局限性，并介绍了需要在超大规模片上网络中容忍众多故障的动机，最后提出了一个使用图论来进行超大规模片上网络中容错众多故障的路由算法的研究方向，并通过理论论证了其可行性与优点。

参考文献：

[1] W.J. Dally and B. Towles， "Route packets， not wires： On-chip interconnection networks[J]，" in Proc. DAC， 2001， pp. 684-689.

[2] S.Kumar， A.Jantschl，J.P.Soininen，etc.A Network on Chip Architecture and Design Methodology[A].Proceeding of the IEEE Computer Society Annual Symposium on VLSI[C]，April 2002：105-112.

[3] M.Mirza-Aghatabar，S.Koohi，S.Hessabi，M.Pedram.An Empirical Investigation of Mesh and Torus NoC Topologies Under Different Routing Algorithms and Traffic Models.10th Euromicro Conference on Digital System Design Architectures，Methods and Tools.Aug.2007：19-26.

[4] Zhang Shengbing，Wang Jing，Pan Yongfeng.Analysis of Network on Chip Based on Longtium SoC.International Conference on Embedded Software and Systems Symposia[C].July.2008：243-247.

[5] L.enini G. De Micheli. Networks on chips： a new SoC paradigm IEEE Computer Vol. 35 No.1 Jan.2002，pp.70-80.

[6] J. Dongarra， "Report on Sunway TaihuLight System"， Oak Ridge National Laboratory， Jun. 2016.

【通聯编辑：梁书】