面向3维片上网络的轻量级细粒度容错机制

周 君 李华伟 王天成 李晓维

1（计算机体系结构国家重点实验室（中国科学院计算技术研究所） 北京 100190）2（中国科学院大学 北京 100049）（zhoujun＠ict．ac．cn）

面向3维片上网络的轻量级细粒度容错机制

周 君1，2李华伟1王天成1，2李晓维1

1（计算机体系结构国家重点实验室（中国科学院计算技术研究所） 北京 100190）2（中国科学院大学 北京 100049）
（zhoujun＠ict．ac．cn）

A Lightweight Fine－Grained Fault－Tolerant Scheme for 3DNetworks－on－Chip

片上网络（networks－on－chip，NoC）是3维集成电路的主要通信技术之一．其中，路由器是3维片上网络的重要组成部件．现有的面向3维片上网络中路由器的容错技术，通常采取路由器整体冗余技术或者直接舍弃失效路由器的方法，这导致网络资源损失较为严重．提出一种面向3维片上网络的轻量级细粒度容错机制，充分利用故障路由器中仍能正常运行的有效资源，保障系统通信．提出的容错机制包括一种高可靠性路由器微体系结构设计和一种与之匹配的容错路由机制．通过实验对比和分析，相比较于已有的3维片上网络容错机制，提出的细粒度容错机制具备较高的通信性能和可靠性，同时面积和功耗开销较小．

片上网络；3维mesh；细粒度；容错；路由机制

片上网络（network－on－chip，NoC）是一种主流的3维集成电路［1－2］通信技术．网络中的每一个处理单元（processing element，PE）皆通过网络接口（network interface，NI）及路由器节点（简称“节点”，下文同）与网络中的其他处理单元通信．不同的节点（node）是通过水平或者垂直链接（link）与周围的其他节点通信的．图1所示的是一个典型的4× 2×3的3维mesh网络．图1中每个节点表示一个路由器，是网络通信的基本单元部件．

Fig．1 A sketch of the 3Dmesh NoC．图1 3维mesh结构片上网络示意图

随着集成电路复杂度和集成度的提高，片上网络通信也受到了较为严重的影响，部件故障发生概率不断提高．为了保证集成电路的正常通信，需要引入高效的容错机制．一般而言，片上网络的故障分为瞬时性故障和永久性故障．这些故障可能发生在处理单元、链接、或者是路由器中．在本文中，我们主要关注的是3维片上网络中的永久性故障．这类故障不可修复，对于片上网络的正常功能有较为严重的影响．

本文的主要研究目的，是针对资源有限且存在永久性故障的3维片上网络，提出并实现一种低成本、高可靠性，且通信性能适度降级（相比较于无故障网络，下文同）的容错机制．

国内外面向传统2维片上网络路由器容错机制的研究已经有较丰富的研究成果，但是面向3维片上网络的相关研究进展较少．通常，针对片上网络路由器永久性故障的容错机制主要有以下4类［3－4］：

1）将故障的路由器内部模块由对应的冗余模块整体替换；

2）通过在路由器中故障部分添加一些外围逻辑电路使数据包绕过故障区；

3）设计细粒度的高可靠性路由器微体系结构，利用路由器剩余有效资源执行网络任务；

4）使用容错路由机制，直接绕过故障路由器．

通常，路由器包含控制通路和数据通路2部分．控制通路包括路由计算单元（routing computation unit，RCU）和仲裁器（arbiter）；数据通路包括流水线寄存器（pipeline register，PR）、端口缓存（port buffer）、内部链接和交叉开关（crossbar，CR）．图2表示的是一个典型的路由器内部模块面积分布，我们可以从中发现数据通路整体占据了较大的面积［4］．

Fig．2 A typical area distribution of the NoC router．图2 片上网络路由器面积的典型分布

由于冗余机制和设计外围电路的方法会产生一定的面积和功耗需求，电路规模越大该需求越明显．因此，在低成本的设计前提下，这2项容错技术对于面积较大的路由器数据通路并不适用．另一方面，控制通路占据的面积相对于数据通路小很多，则可以考虑使用冗余机制或设计外围电路的方法进行容错，对系统整体开销的影响不大．

由于数据通路占据了路由器中的较大面积，这使得数据通路的故障发生概率比控制通路高出很多，因此这里我们主要关注的是数据通路上的功能模块故障．考虑到系统开销，成本较低的细粒度高可靠性路由器微体系结构设计和容错路由机制将是合适的选择，特别适合于某些资源受限的多处理器芯片．

同时，我们注意到，3维片上网络中路由器的功能模块一般比2维片上网络的对应功能模块的结构要更加复杂．因此，3维片上网络路由器的功能模块故障对网络通信会产生更加严重的影响．这也为引入细粒度的路由器容错控制提供了可能性，从而获得较高的通信可靠性．因此，路由器中数据通路上的模块功能需要细化来提高路由器的容错能力．

在本文中，我们提出一种面向3维片上网络的轻量级细粒度容错机制，包括：

1）一种新的高可靠性路由器微体系结构．在该结构中，我们细化了交叉开关的功能，使得故障路由器中的有效资源可以继续工作．

2）一种与提出的路由器微体系结构匹配的低成本容错路由机制．在该机制中，我们给出了一种基于逻辑的3维容错路由算法．同时，本文还提出一种用于引导该路由算法的3维转向模型，用于避免网络通信的死锁现象，并且保证3维mesh网络中较高的转向公平度和流量平衡．

1 片上网络细粒度容错机制

已有的面向片上网络的细粒度容错机制主要面向的是传统的2维片上网络．

在文献［5］中，一个传统的2维片上网络路由器中的交叉开关被分为2个独立的子模块．东向和西向的通信由行交叉开关子模块管理．类似地，北向和南向的通信由列交叉开关子模块控制．这种结构可以缓解路由器中东－西向和南－北向2个维度上可能出现的通信竞争，并且在其中一个交叉开关子模块出现故障时保证路由器的部分功能依然可以正常执行．在文献［6］中，2维片上网络的路由器故障被分为静态故障与动态故障2类．该文提出了动态缓存交换机制（dynamic buffer swapping，DBS）和动态多路选择器交换机制（dynamic MUX swapping，DMS），分别用于发生故障的路由器输入缓存和交叉开关，用有效的模块“交换”失效的资源．与前二者不同，文献［4］关注的是路由器中的“切片级（slicelevel）”故障，作者采用时分复用（time division multiplexer）技术，利用数据通路上功能模块的有效切片维持路由器的正常操作．

以上的容错机制主要关注的是路由器微体系结构的可靠性设计．此外，也有一些容错机制不仅设计了不同的路由器结构，同时还提出了相应的防死锁路由机制．在文献［7］中，作者通过在线的诊断，获得路由器中永久性故障的细节信息；同时，结合网络中的通信冲突区域信息，提出了一种基于代价矩阵的自适应路由机制．其中，代价矩阵用于判断路由器合法输出端口的优先级．缓存重用技术是文献［8］中提出的另一种容错技术．通过在路由器同一端口的输入缓存和输出缓存之间添加一种自通信通道（selfcommunication channel，SCC），经由有效内部链接绕过2个端口之间的故障链接．此外，该文还使用经典的奇偶转向模型（Odd－Even turn model）［9］确保网络无死锁．

但是，针对片上网络，尤其是3维片上网络，现有方案中很少提出与路由器可靠性设计相匹配的容错路由机制，从而缺少一个整体的、可以获得较高通信可靠性和适度性能降级特性的片上网络容错机制．路由器微体系结构和路由机制之间的关联在之前的工作中没有得到较好的重视和体现．

在本文中，我们提出的轻量级细粒度容错机制是面向3维mesh片上网络的一个整体的容错解决机制．具体而言，我们设计出一种新的针对路由器数据通路的可靠性微体系结构及其故障模型．此外，我们还提出一种与该高可靠性路由器微体系结构匹配的、基于逻辑的低成本容错路由机制，其中还包括用于引导该路由机制的公平3维转向模型和用于驱使数据包避开通信冲突区域的端口选择机制．

2 相关工作

路由器可靠性设计、路由算法的执行方式和网络防死锁方法是本文方法的核心组成部分，本节将提供针对这些方面的一些背景技术．

2．1 路由器微体系结构

在传统2维片上网络中，每个路由器有5个端口．每个端口对应一个方向：东（east，E），南（south，S），西（west，W），北（north，N）和本地（local，L）．在3维网络中，随着垂直链接的引入，又添加了上（up，U）和下（down，D）2个方向的端口．如图3（a）所示，标准的7×7路由器在3维片上网络中应用广泛［10］．

Fig．3 Conceptual view of the routers in 3DNoCs．图3 3维片上网络路由器概念图

在文献［11］中，Lafi等人提出一种层次化路由器，其示意图如图3（b）所示．该路由器由一个5×5的水平子路由器和一个4×4的垂直子路由器组成．在这个结构中，路由器的整体功能并没有改变，同时可以有效缓解不同内部子路由器之间的通信竞争．与标准的路由器相比，层次化路由器可以获得较高的系统通信性能和容错能力．

但是，层次化路由器内部2个子路由器以及本地端口间的密切联系是彼此的功能独立性的一大阻碍．例如，垂直子路由器的故障不仅影响到本地数据的接收与发送，还会影响到来自或待发送至水平子路由器的数据包通信．因此，我们提出一种新的高可靠性路由器微体系结构来更好地解决这一问题．

2．2 基于逻辑的分布式路由

一般而言，路由算法有2种实现方式：一种是基于逻辑，另一种是基于路由表．基于逻辑的路由算法，比如XYZ路由，具备时间和空间的有效性，不足是这种方法的灵活性较差．而基于路由表的实现方式比较灵活，不过可能引入较大的面积和时延开销．

Flich等人在文献［12］中提出一种基于逻辑的分布式路由算法（logic－based distributed routing，LBDR）．该算法是一种最短路径路由算法，通过4个连接位（CE，CS，CW，CN）和8个路由位（REN，RES，RSE，RSW，RWN，RWS，RNE，RNW）由转向模型引导执行．其中，连接位表明相应的邻居节点是否可连接，路由位表明邻居节点是否能够接收需要发生该路由位下标所示转向的数据包．例如，CE＝1和RES＝1表明当前节点的东边邻居节点是可连通的，同时能够接收东南方向的数据包（允许ES转向）．此外，作者在文献［12］中还将LBDR拓展至任意方向（即东、南、西、北4个方向）的前2跳场景，并命名为LBDRe（extended LBDR）方法．

考虑到LBDR及LBDRe的低成本特性和较好的灵活性，本文在3维场景下对其进行了融入容错特性的拓展，详见3．3节的介绍．

2．3 3维转向模型

通常，转向模型和虚通道技术是2种最常见的用于解决片上网络死锁问题的方法［13－15］．由于虚通道会引入额外的缓存面积和复杂的控制逻辑，因此转向模型对于开销敏感的电路更加适用．

在3维mesh网络中，若干转向模型也被相继提出．Glass等人在文献［16］中提出了3种转向模型，分别是West－South－First，North－Up－Last和Negative－First．这些模型是基于2维场景中的West－First，North－Last和Negative－First模型［16］拓展而来．在文献［17］中，Pasricha等人提出另一种3维转向模型4NP－First．这个模型可以分为2个子模型：4N－First和4P－First．虞潇等人在文献［18］中将3维空间划分为8个区域，共禁止12个转向．基于此模型，作者提出了一种名为TFRA的高度自适应路由算法．Chiu在文献［9］中，给出了一种基于奇偶转向模型拓展的经典3维转向模型OE－3D．在文献［19］中，Dahir等人同样也是在奇偶转向模型的基础上设计了名为Balanced－OE的3维转向模型．在该模型中，奇偶转向模型和一种修改后的奇偶转向模型分别被应用于3维集成电路的奇数器件层和偶数器件层，使得网络流量相对于OE－3D变得更加平衡．由于文献［17－18］中在全网络范围中存在不同的转向模型，需要使用虚通道支持，因此，这2种方法并不适用于低开销容错机制的设计．

Balanced－OE作为OE－3D的改进型版本，是目前最新提出的3维转向模型．在3．4节中，我们将对Balanced－OE的转向公平度和网络通信流量平衡作进一步的改进．

3 本文方法

本文目的是提升路由器微体系结构的可靠性，同时利用LBDR和LBDRe的特点使我们的容错机制轻量级化．

3．1 可靠性路由微体系结构

针对文献［11］中的层次化路由器，一旦数据包需要在水平和垂直方向之间交叉路由，同时某一个子路由器出现故障，则会使整个层次化路由器的功能失效．此外，当数据包到达目的节点，如果垂直子路由器存在故障，则对应的处理单元将无法获得该数据包．

在本文中，我们提出一种新的高可靠性路由微体系结构Re－MA（reliable micro－architecture），来进一步提高3维片上网络的通信可靠性．如图4所示，本文提出的路由器微体系结构主要针对数据通路上的重要模块交叉开关进行优化，而并不像层次路由器那样将路由器划分为若干子路由器．图4中，交叉开关划分为水平交叉开关子模块和垂直交叉开关子模块2部分．为了获得较好的容错能力，我们选用文献［5］中的2维交叉开关结构设计水平交叉开关子模块，通过设置行交叉开关和列交叉开关（即图4所示的行通信模块和列通信模块），分离水平2维空间中的东－西向和南－北向通信，缓解通信竞争，提高子模块容错能力．和层次化路由器中的子路由器类似，Re－MA中的每个交叉开关子模块都是控制不同方向维度上的通信．但与之不同的是，Re－MA中每个交叉开关子模块的功能相对独立，之间关联较少．在数据包被路由分流模块分流之后，数据包可以根据自己的目的端口选择对应的交叉开关子模块进行输出操作．在这样的架构下，即使其中一个交叉开关子模块出现故障无法正常使用，也不影响所有输入路由器的数据包通过另一个交叉开关子模块输出．并且，本地输出端口独立于其他输出端口，这样本地的输出操作就不会受到路由器水平、垂直通信的影响．

Fig．4 The proposed Re－MA for routers．图4 路由器的Re－MA结构

应注意到，Re－MA是2级流水架构．第1级流水由路由分流模块负责执行，其中包括路由计算（routing computing，RC）和开关分配（switch allocating，SA）；第2级流水负责交叉开关传输（crossbar traversal，CT）．路由分流模块其实可以视作一个虚拟模块，因此在图4中也是用虚线框表示．该模块是由路由计算单元、仲裁器和一些额外的分流判断逻辑构成，主要功能是根据路由计算的结果将由本地处理单元注入网络或者经过当前路由器的数据包分流至对应的交叉开关子模块或者是本地端口．此处的分流判断逻辑可以通过一个简单的1∶2的DEMUX实现．相对于路由器整体面积而言，其所占比重很小．因此，与控制通路类似，这一部分电路的容错机制可以通过冗余技术来实现．

3．2 故障模型和故障诊断

故障模型对于一个失效模块的分析至关重要．故障模型设置的不同会极大影响容错机制的设计复杂度和执行效率．在引言部分我们已经提到，本文主要关注的是路由器数据通路上的故障模块．作为数据通路上重要的组成部分，输入端口缓存和交叉开关占据了数据通路较大的面积比例．例如，在文献［20］中的示例路由器中，FIFO缓存和交叉开关分别占据了67．68%和11．14%的比例．因此，大部分的故障可能发生在这2个部件上［6，20］．在本文中，我们基于此提出相应的故障模型．

这里，我们引入故障矩阵来记录检测到的故障信息．图5所示是2个故障矩阵的示例．其中，“Input”表示路由器输入端口，“Output”表示输出端口．矩阵中的“1”表示相应2个端口之间的通信正常，“0”则表示无法通信的情形．为了避免死锁，片上网络中禁止180°的路由转向，因此相应的矩阵元素值置为“－”．显然，在图5（a）中，该故障矩阵对应的路由器的水平交叉开关子模块中的行通信模块出现故障，因此目的输出端口在东－西向的数据包无法正常通过路由器输出．同理，在图5（b）中，除了水平交叉开关子模块中的列通信模块，路由器的东向（E）端口的输入缓存也同样失效．

Fig．5 Examples of the fault matrice for routers．图5 路由器故障矩阵示例

电路的故障诊断技术主要是用来定位故障的位置，同时确定故障的类型和其他相关信息．由于本文主要关注的是永久性故障，因此适宜采用离线式的诊断技术．离线式故障诊断可以通过生产测试（production test）和内建自检（built－in self－test，BIST）等技术执行．在本文的容错机制设计中，负责诊断执行的检测模块设置于网络的各处理单元中，这样可以缓解路由器的设计成本压力．

在系统通电后，特定的故障检测数据包由处理单元中的检测模块经由网络接口发送至本地路由器．通过分析获得的反馈可以掌握路由器中的故障情况，并建立相应的故障矩阵．同时，故障矩阵也需要在检测模块中进行维护．随后，生成的故障矩阵再次通过网络端口传回路由器中的指定寄存器保存，并通过路由器各端口发送至临近的相关路由器节点（具体操作详见3．3节）．故障矩阵通过使用路由器中设计的独立串行线路进行传输．所以，存在故障的输入端口缓存不会给故障矩阵的接收带来影响．

需要注意的是，以上的相关操作需要在片上网络的初始化阶段内完成．所以，故障的诊断可以与网络的正常通信相互隔离开来．由于瞬时性故障并不是本文关注的重点，我们设定在网络常规通信时不进行内建自检操作．同时，因为只涉及小范围、小规模（例如，单个故障矩阵的信息量仅30b）的故障信息传输，网络初始化阶段不会占用太多的时间．另一方面，在路由器中只需要很少的面积开销来用于传输和存储故障矩阵．因此，这一部分额外的电路依然可以通过冗余技术来进行低成本的容错操作．

3．3 轻量级路由算法

考虑到LBDR和LBDRe的低成本和高效率特性，我们在设计的新容错机制中也采用这些方法来降低系统开销．

需要注意的是，在3维片上网络中，一些失效的节点可能会成为“死胡同”节点．一旦成为这种节点，数据包在该节点将无法继续路由至目的节点．这主要是由于该节点的故障模块及其他的操作限制导致的．由于LBDR和LBDRe这2个方法都是面向无故障的2维片上网络设计的，并且获取的路由信息有限，因此无法直接将其拓展至3维场景来避免可能的“死胡同”节点．这里，为了消除可能的通信“死胡同”现象，当前节点需要获得更多的路由信息来加以判断输出端口的选择．在本节中，考虑到较低系统开销的设计需求，我们设定路由信息的来源范围为距离当前节点2跳距离以内的任意节点，来有效避免数据包路由至“死胡同”节点．例如，如果西向（W）端口是可选择的输出端口之一，则不仅是当前节点西边的距离在2跳范围内的节点的故障矩阵，其余任意可经由W端口到达并且在2跳范围之内的节点的故障矩阵也应发送至当前节点．这一点和LBDRe方法不同，后者只接收在某一个方向上的且距离在2跳范围之内的节点路由信息．

因此，我们将与本文需求较为接近的LBDRe方法拓展至3维场景，并记为LBDRem（modified LBDRe）方法．该方法将容错能力和“死胡同”现象纳入考虑范畴．在3维mesh片上网络中，除本地端口外，一个节点最多有6个端口．对于6个距离为1跳的邻居节点而言，LBDRem的连接位的个数增至6b（CE，CS，CW，CN，CU，CD），同时路由位个数增至30b（REN，RES，REU，RED，REE，RSE，RSW，RSU，RSD，RSS，RWN，RWS，RWU，RWD，RWW，RNE，RNW，RNU，RND，RNN，RUN，RUE，RUS，RUW，RUU，RDN，RDE，RDS，RDW，RDD）．这些路由信息所表明的含义与LBDRe中的相同．

类似地，根据3维空间中方向和维度上的推导，对于距离当前节点为2跳的节点，需要另外的30b连接位和126b路由位作为当前节点的“辅助路由信息”．例如，CES表明当前节点的东边邻居节点（记为A）是否与节点A的南边邻居节点可连接；再比如，RSE?EU表明当前节点的东南方向的、与其距离为2跳的节点（记为B）是否可以允许从节点B西向（W）端口输入的数据包发生EU转向．由于原理类似，我们这里不再逐一列举所有相应的连接位与路由位．作为“辅助路由信息”，距离当前节点2跳距离的节点路由信息主要是用于辅助距离当前节点为1跳范围的路由信息的取值判断，从而有效避开可能的“死胡同”节点．这是因为当前节点的下一跳节点选择，最终还是要根据上面枚举的6b连接位和30b路由位的取值进行操作．由于本文不考虑路由器节点之间的链接故障，因此LBDRem方法中的所有连接位取值始终为“1”．

LBDRem方法的执行步骤为2步：1）比较当前节点和目的节点的网络坐标．比较的结果将得出可选数据包的继续行进方向，从而使数据包与目的节点的距离更近一步．2）当前节点检查掌握的所有路由信息，并决定选择的合法输出端口．需要说明的是，这里的路由信息是由在网络初始化阶段获得的周边邻居节点的故障矩阵转化而来．例如，假设图5（b）中的故障矩阵来自于当前节点的北边邻居节点，则RNU和RND的取值为“0”，而CN，RNE，RNW，RNN的取值则为“1”．

3．4 用于引导路由算法的转向模型

作为一种最短路径路由算法，LBDRem可以为3维片上网络的通信提供足够的灵活性．但是，若不加入一些其他限制，网络死锁现象依然无法避免．作为一种有效且开销较低的方法，转向模型对于我们的轻量级容错机制很适用．

与具有统一限制的转向模型（即每个节点的转向限制相同）相比，基于区域的转向模型，例如2．3节提到的OE－3D和Balanced－OE模型，通常具备更好的路由自适应度和转向公平性．在网络的不同区域的节点，需要执行的转向限制也不相同，这与“完全不同的多个转向模型”的概念是有区别的，后者需要高成本的虚通道加以支持．以经典的奇偶转向模型为例，如图6所示．在2维mesh网络中的奇数列和偶数列（奇、偶数列取决于列上节点的X坐标的奇偶性）．在奇数列上的所有节点禁止NW和SW转向，而在偶数列上的节点禁止EN和ES转向．

Fig．6 Turn constraints of the classical Odd－Even model．图6 经典奇偶转向模型示意图

这里，我们提出一种相比较于最新的Balanced－OE模型转向更加公平且流量更加平衡的转向模型，命名为Full－OE（即完全OE模型）．Full－OE模型相比较于Balanced－OE模型的不同之处在于，二者的水平器件层内部的转向限制不同．在垂直转向（即层间转向）方面，Full－OE模型采用和Balanced－OE模型相同的转向限制．

图7是Balanced－OE模型的水平器件层的转向限制示意图．传统的奇偶转向模型和修改后的奇偶转向模型分别应用于3维集成电路的奇数器件层和偶数器件层．图7（a）中虚线左边是奇数列的禁止转向NW和SW，右边是偶数列的禁止转向EN与ES．类似地，图7（b）中虚线上面是奇数行的禁止转向EN和WN，下面是偶数行的禁止转向SE和SW．这一点也是Balanced－OE模型相比较于OE－3D模型的改进之处．OE－3D模型在各平面内仅采用单一的奇偶转向模型，因此，Balanced－OE模型在整个网络范围内可以达到更好的转向公平度及流量平衡．

ig．7 The prohibited turns of the horizontal layers in Balanced－OE．

图7 Balanced－OE中水平器件层的转向限制

在Full－OE模型中，为了进一步改善转向公平度和网络流量平衡，我们将奇偶转向模型和其在2维mesh网络中的其他3个对称性“变体”一起加入到3维mesh网络的水平器件层的转向限制中，如图8所示．和图7类似，在图8中，虚线左边是奇数列的禁止转向，右边是偶数列的禁止转向，虚线上面是奇数行的禁止转向，下面是偶数行的禁止转向．具体的转向名不再一一列举．从图8（a）～（d），这4个模型依次执行于第4n，4n＋1，4n＋2，4n＋3（n≥0）层．更多不同的层内转向限制可以使得3维网络中的转向公平度获得提高，并能针对不同方向的数据包使得网络中各区域的流量更加均衡，有效避免可能的冲突热区的出现，网络规模越大，相应的有益效果则越明显．需要说明的是，禁止转向和某些故障模块带来的实际效果一样，也都会使得LBDRem算法中的相应路由位置为“0”．

Fig．8 The prohibited turns of the horizontal layers in Full－OE．图8 Full－OE中的水平器件层转向限制

3．5 端口选择机制

由于在路由过程中可能会出现合法的可选择输出端口不唯一的情形，因此一个合适的端口选择机制对于本文提出的完整容错机制十分必要，以用于避开网络热点和冲突区域（congestion area）．

在文献［21］中，Mak等人提出的动态规划（dynamic programming，DP）选择机制是一个面向传统2维片上网络的低开销、高效率的端口选择机制．相比较于经典的NoP机制［3，22］，DP并不是根据临近的区域流量情况，而是根据实时的路径规划更新情况，在所有备选合法端口中获取最优的选择．在传统2维网络中，该机制与奇偶转向模型的结合方案已经获得较好的实验效果．因此，我们将DP机制进行3维场景的拓展，记为DP－3D机制，以适用于本文提出的轻量级细粒度容错机制．

4 本文方法示例及相关分析

4．1 方法示例

Fig．9 An typical example of the proposed scheme．图9 本文方法的典型示例

为了利于本文所提容错机制的理解，这里给出了一个具体的方法执行实例．图9所示是一个典型的4×2×3的3维mesh网络（注意，这里仅仅是用于方法示意，并没有限定本文方法的适用规模）．节点0是源节点，节点20是目的节点．图9中黑色的实心节点是无故障路由器节点，空心的节点（旁边配有“×”）是存在故障的路由器节点．具体而言，相关的故障描述详见表1所示：

Table 1 Node Fault Descriptions表1 节点故障描述

在网络的初始化阶段之后，源节点将对接收到的来自于节点1，2，6，7，8，9，15，16的故障矩阵进行分析，获得这些节点的包括连接位和路由位的相关路由信息．对于节点0，节点1，7，8都是可以选择的下一跳节点．但是，由于节点9的西向输入端口的缓存失效，如果数据包在节点8发生UE转向，则节点9就会成为“死胡同”节点．类似的潜在“死胡同”皆需要避免，否则会极大影响网络的通信性能．根据Full－OE转向模型和DP－3D端口选择机制，我们假定在当前网络条件下节点1被选为下一跳节点．在数据包到达节点1后，其下一步的路由操作依然需要依靠对在网络初始化阶段来自节点2，3，5，6，9，10，14，17的故障矩阵的分析．节点2，6，9是节点1可选的下一跳节点，随后的操作与之前相同．类似地，基于当前节点的坐标和目的节点的坐标的比较，数据包依次通过节点14，13，12，并最终到达节点20．在这条路径上，节点9不再是一个“死胡同”节点．这也说明，“死胡同”节点只是一个动态的概念．

与其他的细粒度容错机制相比，本文所提的方法可以对3维片上网络中的有限资源进行更加充分地利用．例如，即使节点9的垂直交叉开关子模块发生故障，数据包依然可以通过其水平交叉开关子模块中的列通信模块继续路由．节点13亦同理．

4．2 防死锁特性分析

死锁是由于数据包始终获取不了需要的网络资源，从而无法被发送至目的节点的现象［15］．3维转向模型的死锁通常是由平面（层）间和平面（层）内的转向限制保障避免的．因此，这里将从平面（层）间、平面（层）内2方面进行对应的分析和说明．

设3维空间中X维度的2个方向分别为X＋和X－，分别表示X坐标的增大和减小．同理，我们还可以定义出Y＋，Y－，Z＋，Z－等方向．我们用X＋－Y＋表示一个2维空间中的转向，该转向是由X＋方向转到Y＋方向．类似地，在3维空间中，2维转向X＋－Y＋，X＋－Y－，X＋－Z＋，X＋－Z－结合在一起，构成了一个3维转向X＋－YZ．由于本文所提的Full－OE模型采用的平面（层）间的转向限制和Balanced－OE模型相同，即在奇数层禁止XY－Z－转向，偶数层禁止Z＋－XY转向．如同文献［9］中经典的奇偶转向模型的Y－X－和X＋－Y之间的联系在2维空间中完全割裂一样，Z＋－XY和XY－Z－之间的联系在3维空间中也完全割裂，确保了平面（层）间无法形成通信抽象环，因此可以预防相应区域的死锁发生．

另一方面，由于Full－OE模型的水平器件层内部的转向模型仅仅是在不同的层采用了奇偶转向模型的所有不同变体，因此，拓展的原理和Balanced－OE对OE－3D的拓展本质上是一样的，并没有引入“全新”的转向限制．因此，Full－OE模型的平面（层）内的转向限制可以确保相应区域内死锁的避免．加之平面（层）间的转向限制，可以保证Full－OE模型在整个3维mesh网络中的无死锁需求．

此外，还需要说明的是：1）由于网络故障导致的路径限制并不会影响到本文方法中死锁的预防．这是因为转向模型本身就是一种避免死锁的有效方法，路径限制仅可能导致本是合法的转向无法继续执行，而非法的转向依旧不能使用．2）死胡同和死锁现象虽然表现相似（即数据包无法继续传输），但二者本质不同．死胡同是由于网络限制（如故障、转向模型等）的原因，导致数据包无法继续“前进”的．

4．3 补充操作及不足

由于LBDRem方法是一个基于最短路径的路由算法，源节点和目的节点之间的所有中间节点都须处于“最短路径”上．但是，在一些特殊的场景中，例如源节点和目的节点在3维mesh网络的同一边上（即二者的网络坐标在X，Y，Z这3个维度上有2个维度的坐标值都相等），一旦这2个节点之间的直线路径（即最短路径）上存在不可逾越的永久性故障，则会导致二者间通信的失败．因此这里需要对类似场景做本文所提方法的补充说明．

一旦在2个节点之间的最短路径上无法找到一个合适的下一跳节点，则在不触犯Full－OE模型的前提下，在非最短路径上结合DP－3D机制找到当前节点新的下一跳节点，并在此节点继续使用2．2节中描述的容错机制继续对数据包进行路由．需要注意的是，由于网络中不允许180°的路由转向，因此数据包传输路径上的前一个节点不能作为当前节点的下一跳节点的可选对象．

需要说明的是，本文提出的是一种轻量级的细粒度容错机制，因此和其他的低成本容错机制类似，本文的方法也存在一些相同的不足，例如由于网络中的转向限制和较多的故障致使2个节点之间的通信无法达成．但是与同类型轻量级方法相比，本文在相同的网络故障率下具备更高的网络通信可靠性和适度的性能降级特性．由于轻量级容错机制针对高故障率网络的性能保障意义不大，因此一般推荐适用的网络故障率在0%～30%［23－24］，且尽量在10%以内（详见第5节实验部分的分析）．

5 实验与分析

5．1 实验方法介绍

为了评估本文提出的面向3维mesh网络的轻量级细粒度容错机制的通信性能和系统开销，我们基于意大利卡塔尼亚大学的Noxim模拟器［25］设计了面向3维网络的周期精准级（cycle－accurate）模拟器NoCer．我们还在若干实际应用的传输模式下进行了轨迹驱动（trace－driven）的仿真过程．其中，GEMS模拟器［26］基于全系统模拟器Simics［27］的功能设计，用于获得实际应用传输模式的轨迹文件（trace）．实验使用的基准测试集是PARSEC［28］．此外，我们还运用NoCer和Synopsys公司的Design Compiler分析了相关的系统开销．

在本节中，我们将本文提出的容错机制与其他2种同样是完整的面向3维mesh网络的容错机制进行比较，这3种方法中的路由器微体系结构和容错路由机制都是互不相同的．我们将7×7的传统路由器（normal router）、基于路由表的（table－based）容错路由算法、OE－3D转向模型和NoP－3D端口选择机制结合起来，形成第1种方法，命名为NTON方法（为方便说明，选取各部分英文表述的第1个大写字母）．同样，我们用层次化路由器（hierarchical router）、Balanced－OE模型和DP－3D选择机制分别替换NTON方法中的对应部分，就形成了另一种容错机制，命名为HTBD（命名规则与NTON同理）．类似地，本文提出的方法按照该命名规则可以命名为RLFD方法（Re－MA结构、Logic－based容错路由、Full－OE模型、DP－3D选择机制）．为了可以进行全面地比较，NTON，HTBD和本文提出的RLFD方法的网络通信性能和系统开销皆须通过上述的模拟器和综合器进行评估．需要注意的是，本文提出的轻量级细粒度容错机制适用于任意规模的3维 mesh网络，这里，我们选用常见的4×4×4三维mesh网络进行实验和相应的结果分析．

片上网络模拟器NoCer的整体参数设置详见表2所示．我们选择3种主要的综合传输模式（synthetic traffic pattern）：Uniform，Transpose，Hotspot［15］．这里简要介绍一下这3种模式．Uniform模式下，网络中每个节点将一个数据包发送至其他所有节点的可能性相同．在Transpose模式下，一个坐标为（i，j，k）的节点只会将数据包发送至坐标为（I－i－1，J－j－1，K－k－1）的节点．这里，（I，J，K）是这个3维mesh网络的最大维度．而在Hotspot模式下，某些节点会被设置成“热点”．相比较于其他节点，这类热点将会收到比Uniform模式下多h的数据量．这里，h是Hotspot模式的重要参数，常以百分数形式表示．

Table 2 Simulation Parameters of NoCer表2 NoCer模拟器的参数设置

由于本文关注的是存在故障的3维片上网络，因此网络中的故障率是一个核心参数．我们将路由器中的故障，包括输入缓存故障和交叉开关内部故障按照最细的粒度随机插入网络中．即将路由器输入缓存故障、交叉开关内部的水平交叉开关子模块中的行通信模块、列通信模块及垂直交叉开关子模块的故障作为一个等级的故障独立开来对待，随机插入网络的各路由器中．如果针对具体的故障率，故障部分的数目不是一个整数，则对该数值进行向上取整操作．实验的结果是通过多次实验（≥20）取平均值的方式获取，以消除模拟器中的随机数的变化可能带来的影响．

5．2 网络通信性能分析

全局平均时延（global average latency，GAL）是一个重要的衡量网络通信性能的指标．GAL的增长趋势是通过一条在网络注入率（injection rate，IR）不断提升下持续变化的光滑曲线来表示的．曲线越平滑，说明容错机制的时延性能越好．

首先，将3种容错机制NTON，HTBD，RLFD在3种不同的综合传输模式，以及网络故障率（faultrate，FR）为0%（即无故障）和5%（常见故障率［3］）2种情形下进行比较．比较结果如图10所示，RLFD的时延性能在2种故障率和3种综合传输模式下都获得较好的实验效果．其中，在故障率为5%的网络中，本文方法相比于NTON和HTBD的性能优势更加明显．特别地，在Uniform和Hotspot（h＝10%）模式下，RLFD可以获得与无故障网络中NTON很接近的时延性能．

Fig．10 Global average latency of the fault－tolerant schemes in 4×4×4 3Dmesh NoC．图10 4×4×4三维mesh网路中的全局平均时延比较

根据上面的实验，我们可以发现RLFD能够获得较好的性能．但是真实的应用程序产生的网络流量多数是非均匀的，在很多情况下会呈现一种突发特性，这一点与之前的综合传输模式不同．为了进行更加精确的性能分析，我们将PARSEC基准测试集作为3维网络的负载进行仿真实验．具体的全系统模拟器参数设置详见表3所示：

Table 3 Full－System Simulation Configurations表3 全系统模拟参数设置

图11是将NTON，HTBD，RLFD在PARSEC基准测试集作为负载下的网络数据包平均延迟全部归一化为NTON的网络延迟的实验结果，其中网路故障率设定为5%．我们可以发现，RLFD依然可以有效地降低数据包的传输延迟．特别地，对于类似于canneal和freqmine这样的高度拥塞的应用程序，网络提升的性能较为可观；而对于像streamcluster这样的低冲突的应用程序而言，性能的提升相对较少．平均来看，通过RLFD可以最大幅度降低12．67%、平均减少7．48%的数据包传输延迟．

Fig．11 Packet latency across PARSEC benchmarks．图11 基于PARSEC基准测试集的数据包传输延迟

5．3 网络通信可靠性分析

定义1．设NS是网络中注入的全部数据包数目，NA是网络中所有的目的节点在设定的时间内接收到的数据包的数目．片上网络传输机制的可靠性指标R可以表示为［3，24］：

图12给出了NTON，HTBD，RLFD三种容错机制在Hotspot（h＝10%）模式下不同网络故障率下的通信可靠性比较．实验结果是在网络注入率为0．003时获得的．在网络故障率分别为1%，5%，10%的4×4×4三维mesh网络中，RLFD的可靠性指标分别为88．7%，76．4%，43．5%．相比于其他2种机制，本文提出的方法具有一定的优势．类似的实验比较结果在另外2种综合传输模式（Uniform和Transpose）下同样可以获得．

Fig．12 Reliability of the fault－tolerant schemes under the Hotspot pattern（h＝10%）．图12 Hotspot模式下（h＝10%）的可靠性指标比较

由于在较高的网络故障率下，通信可靠性指标普遍偏低，比如故障率为5%和10%时的情形．这说明，相比于冗余技术，轻量级容错机制在针对高故障率网络方面确实存在一定的局限性．不过，在本例中，也可以通过降低网络数据包注入率或者Hotspot模式下的h取值来获得不同程度的可靠性指标提升．例如，在故障率为1%的网络中，若数据包注入率降为0．001，本文所提RLFD的可靠性指标可达到98．6%．

5．4 系统开销

作为一个面向开销敏感的3维集成电路设计的容错机制，RLFD同样具备可以接受的面积与功耗开销．由于采用了基于逻辑的LBDRem路由算法，并且不需要引入高成本的虚通道技术用于避免网络死锁现象，因此相比较于需要虚通道分配器（virtual channel allocator）、额外的复杂控制逻辑，并且是基于路由表实现的容错机制而言，本文提出的方法需要较少的存储空间．

我们通过Design Compiler的综合结果对硬件开销进行评估，利用的是UMC的90nm工艺库．本文提出的轻量级细粒度容错机制在路由器的开销上相较于传统的7×7路由器仅提高了5．2%．根据英特尔公司的报告［29］，路由器占据整个tile（即包括本地处理单元、网络接口和路由器在内）11%左右的面积，因此，本文所提容错机制的开销小于1%．

通过NoCer模拟器，我们可以得到如表4中所示的能耗实验结果．每种方法分别在网络注入率（IR）为0．001和0．003、网络故障率为5%的场景下，同时针对3种不同的综合传输模式进行实验．实验结果说明本文提出的RLFD在网络中的操作能耗要全面地低于其他2种容错机制．尤其是在Hotspot（h＝10%）模式下，实验效果较为明显．

Table 4 Operation Energy for Analysis表4 操作能耗分析μJ

另一方面，随着网络注入率的提高，RLFD的操作能耗与NTON和HTBD之间的差值会逐步增大．这是因为网络操作所需要的能量和GAL的变化趋势是基本保持一致的．例如，在Hotspot（h＝10%）模式下，当网络数据包注入率为0．001时，RLFD相比于NTON可以节省5．87%的能耗；而当网络注入率升高为0．005时，RLFD相比于NTON则可以节省高达31．73%的能耗．

6 结束语

在本文中，我们面向3维片上网络提出一种轻量级细粒度容错机制．该机制提供了一种高可靠性的路由器微体系结构，以及一种与之匹配的容错路由机制，二者组成了一个完整的面向3维mesh网络的容错机制．此外，本文的方法可以在不使用成本较高的虚通道技术下确保网络能够防止死锁现象的发生．最后的实验结果说明，本文提出的轻量级细粒度容错机制相比于之前的相关研究成果，具备较好的通信性能及可靠性，同时系统开销较小．

其次，本文所提方法在其他3维片上网络拓扑结构（例如3DTorus，Folded Torus，BFT等）上的拓展，以及与针对路由器间链接故障的容错机制的兼容性问题，是我们以后的重点研究方向．

［1］Banerjee K，Souri S J，Kapur P，et al．3－D ICs：A novel chip design for improving deep－submicrometer interconnect performance and systems－on－chip integration［J］．Proceedings of the IEEE，2001，89（5）：602 633

［2］Wang Di，Zhao Tianlei，Tang Yuxing，et al．A communication feature－oriented 3DNoC architecture design［J］．Journal of Computer Research and Development，2014，51（9）：1971 1979（in Chinese）（王谛，赵天磊，唐遇星，等．一种面向通信特征的3DNoC体系结构设计［J］．计算机研究与发展，2014，51（9）：1971 1979）

［3］Zhou J，Li H，Fang Y，et al．HARS：A high－performance reliable routing scheme for 3DNoCs［C］??Proc of IEEE ISVLSI 2014．Piscataway，NJ：IEEE，2014：393 397

［4］Liu C，Zhang L，Han Y，et al．A resilient on－chip router design through data path salvaging［C］??Proc of ACM?IEEE ASP－DAC 2011．New York：ACM，2011：437 442

［5］Kim J，Nicopoulos C，Park D，et al．A gracefully degrading and energy－efficient modular router architecture for on－chip networks［C］??Proc of ACM?IEEE ISCA 2006．New York：ACM，2006：4 15

［6］Qian Z，Teh Y F，Tsui C．A fault－tolerant network－on－chip design using dynamic reconfiguration of partial－faulty routing resources［C］??Proc of IEEE?IFIP VLSI－SoC 2011．Piscataway，NJ：IEEE，2011：192 195

［7］Kohler A，Schley G，Radetzki M．Fault tolerant network on chip switching with graceful performance degradation［J］．IEEE Trans on Computer－Aided Design of Integrated Circuits and Systems，2010，29（6）：883 896

［8］Zhang S，Han G，Zhang F．Very fine－grained fault－tolerant routing algorithm of NoC based on buffer reuse［C］??Proc of IEEE ICSESS 2013．Piscataway，NJ：IEEE，2013：758 762

［9］Chiu G．The odd－even turn model for adaptive routing［J］．IEEE Trans on Parallel and Distributed Systems，2000，11（7）：729 738

［10］Kim J，Nicopoulos C，Park D，et al．A novel dimensionallydecomposed router on－chip communication in 3Darchitecture［J］．ACM SIGARCH Computer Architecture News，2007，35（2）：138 149

［11］Lafi W，Lattard D，Jerraya A，et al．An efficient hierarchical router for large 3DNoCs［C］??Proc of IEEE RSP 2010．Piscataway，NJ：IEEE，2010：1 5

［12］Flich J，Rodrigo S，Duato J．An efficient implementation of distributed routing algorithms for NoCs［C］??Proc of ACM? IEEE NOCS 2008．New York：ACM，2008：87 96

［13］Seiculescu C，Murali S，Benini L，et al．A method to remove deadlocks in networks－on－chips with wormhole flow control［C］??Proc of IEEE?ACM DATE 2010．Piscataway，NJ：IEEE，2010：1625 1628

［14］Fu B，Han Y，Ma J，et al．An abacus turn model for time? space－efficient reconfigurable routing［C］??Proc of ACM? IEEE ISCA 2011．Piscataway，NJ：IEEE，2011：259 270

［15］Richard H．Deadlock free routing in mesh networks on chip with regions［D］．Link ping，Sweden：Link ping University，2009

［16］Glass C J，Ni L M．Adaptive routing in mesh－connected networks［C］??Proc of IEEE ICDCS 1992．Piscataway，NJ：IEEE，1992：12 19

［17］Pasricha S，Zou Y．A low overhead fault tolerant routing scheme for 3DNetworks－on－Chip［C］??Proc of IEEE ISQED 2011．Piscataway，NJ：IEEE，2011：1 8

［18］Yu Xiao，Li Li，Zhang Yuang，et al．A power－aware dead lock avoid three－dimensional full－adaptive routing algorithm for 3DNoC［J］．Acta Electronica Sinica，2013，41（2）：329 334（in Chinese）（虞潇，李丽，张宇昂，等．一种面向功耗免死锁3维全动态3DNoC路由算法［J］．电子学报，2013，41（2）：329 334）

［19］Dahir N，Mak T，Al－Dujaily R，et al．Highly adaptive and deadlock－free routing for three－dimensional networks－on－chip［J］．IET Computers ＆Digital Techniques，2013，7（6）：255 263

［20］Lin S，Shen W，Hsu C，et al．Fault－tolerant router with built－in self－test?self－diagnosis and fault－isolation circuits for 2D－mesh based chip multiprocessors systems［C］??Proc of IEEE VLSI－DAT 2009．Piscataway，NJ：IEEE，2009：72 75

［21］Mak T，Cheung P Y K，Lam K，et al．Adaptive routing in network－on－chips using a dynamic－programming network［J］．IEEE Trans on Industrial Electronics，2011，58（8）：3701 3716

［22］Ascia G，Catania V，Palesi M，et al．Implementation and analysis of a new selection strategy for adaptive routing in networks－on－chip［J］．IEEE Trans on Computers，2008，57（6）：809 820

［23］Akbari S，Shafiee A，Fathy M，et al．AFRA：A low cost high performance reliable routing for 3Dmesh NoCs［C］?? Proc of IEEE?ACM DATE 2012．Piscataway，NJ：IEEE，2012：332 337

［24］Ebrahimi M，Daneshtalab M，Plosila J．Fault－tolerant routing algorithm for 3DNoC using hamiltonian path strategy［C］??Proc of ACM?IEEE DATE 2013．Piscataway，NJ：IEEE，2013：1601 1604

［25］University of Catania．Noxim：The NoC simulator［EB? OL］．（2010－01－26）［2014－12－06］．http：??www．noxim．org

［26］Martin M M K，Sorin D J，Beckmann B M，et al．Multifacet s general execution－driven multiprocessor simulator（GEMS）toolset［J］．ACM SIGARCH Computer Architecture News，2005，33（4）：92 99

［27］Magnusson P S，Christensson M，Eskilson J，et al．Simics：A full system simulation platform［J］．IEEE Computer，2002，35（2）：50 58

［28］Bienia C，Kumar S，Singh J P，et al．The parsec benchmark suite：Characterization and architectural implications［C］?? Proc of IEEE?ACM PACT 2008．Piscataway，NJ：IEEE，2008：72 81

［29］Vangal S R，Howard J，Ruhl G，et al．An 80－tile sub－100－w teraflops processor in 65－nm cmos［J］．IEEE Journal of Solid－State Circuits，2008，43（1）：29 41

Zhou Jun，born in 1984．PhD candidate at the Institute of Computing Technology，Chinese Academy of Sciences．His main research interests include VLSI design and fault－tolerance．

Li Huawei，born in 1974．Professor at the State Key Laboratory of Computer Architecture，Institute of Computing Technology，Chinese Academy of Sciences．IEEE senior member，senior member of China Computer Federation．Her main research interests include VLSI test，verification and design for reliability．

Wang Tiancheng，born in 1983．Received his master degree from the Institute of Computing Technology，Chinese Academy of Sciences in 2009．Engineer at the State Key Laboratory of Computer Architecture．His main research interests include VLSI design and verification．

Li Xiaowei，born in 1964．Professor at the State Key Laboratory of Computer Architecture，Institute of Computing Technology，Chinese Academy of Sciences．IEEE senior member，senior member of China Computer Federation．His main research interests include VLSI test，design for reliability andfaulttolerance．

Zhou Jun1，2，Li Huawei1，Wang Tiancheng1，2，and Li Xiaowei11（State Key Laboratory of Computer Architecture（Institute of Computing Technology，Chinese Academy of Sciences），Beijing100190）2（University of Chinese Academy of Sciences，Beijing100049）

3Dnetwork－on－chip（NoC）is one of the main trends of the communication technology for 3Dintegrated circuits（ICs）．Each processing element（PE）in the networks communicates with its attached router node through the network interface（NI），and different nodes are connected to their neighbors with the horizontal or vertical links．With the increase of complexity and integration level，the interference to the communication of NoCs becomes more and more serious，and the probability of fault occurrence also rises up．In order to guarantee the normal operation of the circuits，effective fault－tolerant schemes need to be designed for the networks．The routers are one of the main components of NoCs．For most of the existing fault－tolerant schemes，faulty routers are usually completely replaced by the redundant ones or even deprecated．In this paper，we propose a lightweight fine－grained fault－tolerant scheme to take full advantage of the remaining valid resources of the routers in 3DNoCs．Our scheme includes a new reliable micro－architecture designed for the routers and a matching lightweight fault－tolerant routing scheme．Experimental results show that the proposed scheme possesses higher performance，improved reliability and lower overhead compared with the state－of－the－art fault－tolerant schemes for 3DNoCs．

networks－on－chip；3Dmesh；fine－granularity；fault－tolerance；routing scheme

TP302

2014－12－29；

2015－06－23

国家自然科学基金项目（61432017，61176040，61221062）；国家“九七三”重点基础研究发展规划基金项目（2011CB302501）This work was supported by the National Natural Science Foundation of China（61432017，61176040，61221062）and the National Basic Research Program of China（973Program）（2011CB302501）．