2. 专用集成电路与系统国家重点实验室(复旦大学), 上海 201203
2. State Key Laboratory of ASIC and System(Fudan University), Shanghai 201203, China
随着大数据和云计算等大批量、高速数据处理应用的出现，单核处理系统已经远远不能满足数据处理的需求，基于片上网络互连的多核系统逐渐成为高性能数据处理系统发展的趋势。路由器作为多核互联的核心部件，承担着网络路由和数据交换的重要任务。目前对于路由器的研究主要集中在低功耗/低成本、高性能和可靠性三个方面。在低功耗/低成本方面：文献[1]在系统级对影响路由器功耗的关键因素进行分析，提出了一种低功耗路由器；文献[2]提出了一种新的轻量级灵活缓存结构，在不影响性能的情况下最小化缓存面积。在高性能方面，文献[3]提出了一种提前分配路径的低延时片上网络结构，明显改善了网络的延时和吞吐率；文献[4]提出了一种新颖的虚通道高效动态分配的路由器，被认为是目前最高效的虚通道组织方案。在可靠性方面：文献[5]采取通道切片技术设计了一款能高效容错的路由器；文献[6]提出了一种高可靠，低成本的容错路由器，分别修改了路由计算、虚通道分配、交叉开关分配和交叉开关结构，实现了路由器的全方位容错。
目前得到广泛应用的是虚通道静态分配式路由器，但其缓存利用率较低且仍然存在队列头阻塞等问题，而虚通道动态分配式路由器通过为每个虚通道动态分配缓存容量，提高缓存利用率，最大化虚通道并行转发粒度，也最大化消除了头阻塞的发生，能大大提高片上网络性能，因此，对虚通道动态分配式路由器的研究是高性能路由器发展的一个重要方面。对于虚通道动态分配式路由器，其虚通道组织方式主要有三种：第一种是基于链接表实现的，如文献[7-8]等使用的动态分配多队列(Dynamically Allocated Multi-Queue, DAMQ)方式；第二种是基于映射表实现的，最典型的是文献[9]提出的动态虚拟通道分配器(Dynamic Virtual Channel Regulator, ViCHaR)以及文献[10]提出的虚通道固定动态分配方式(Fixed VC Assignment with Dynamic VC Allocation, FVADA)和虚通道可调节式动态分配方式(Adjustable VC Assignment with Dynamic VC Allocation, AVADA)；第三种是基于硬件控制电路实现的，如文献[4]提出的高效的虚拟通道动态分配方式(Efficient Dynamic Virtual Channel organization, EDVC)。但是不管哪种实现方式都需要庞大集中的缓存资源和复杂的控制逻辑，这些都极大增加了虚通道动态分配式路由器端口发生故障的概率，也使得对其端口故障的研究显得十分必要。目前针对路由器的容错技术主要分成两种：1) 利用容错路由算法绕开故障节点。如文献[11]提出了一种基于内建自测试技术的无虚通道容错路由算法；文献[12]提出的粗粒度和细粒度的前瞻性容错路由算法。但是这些方法容错粒度较大，一旦发现故障节点就选择绕开或者丢弃，极大地浪费了片上缓存等资源。2) 修改路由器微结构进行容错。如文献[13]提出了一种可靠的容错路由器架构，称其为Vicis；文献[14]提出了一种全方位防护的容错路由器，将其命名为Shield。但是这些研究大都集中于虚通道静态分配式路由器，并且也主要都是针对路由计算、虚通道分配和交叉开关等的容错设计，缺少对虚通道动态分配式路由器庞大集中的缓存资源和复杂的控制逻辑的故障研究。
综合以上问题，本文根据虚通道动态分配式路由器的特点，针对其端口故障，设计了一款对端口容错的路由器。本文主要工作如下：1) 根据虚通道动态分配式路由器缓存组织方式特点，提出了一种基于粒度划分的统一的端口故障与拥塞预测模型；2) 设计了一种高度可靠的邻端口共享模块；3) 设计了一种容错式读写指针控制逻辑电路。
1 故障及拥塞预测模型建立针对国内外对高性能虚通道动态分配式路由器的研究现状，本文着重对最易发生故障的路由器端口进行研究，提出了端口故障的粒度划分，并根据排队论原理建立了端口故障粒度划分的故障与拥塞预测模型。
1.1 虚通道动态分配式路由器结构虚通道动态分配式路由器的结构如图 1所示，借鉴文献[4]提出的路由器输入端口架构，其与一般虚通道静态分配式路由器的区别主要在于输入端口缓存的组织方式以及数据包进出虚通道的方式上。对于虚通道动态分配式路由器，一般采用集中式缓存组织方式，数据包进出由控制逻辑(Control Logic, CL)来实现，控制逻辑可由链接表、组合电路或硬件电路实现。虚通道动态分配式路由器端口主要由缓存和控制逻辑组成。
|
图 1 虚通道动态分配式路由器结构 Figure 1 Structure of router for virtual channel dynamic allocation |
虚通道动态分配式路由器端口架构如图 2所示。缓存使用静态随机存取存储器(Static Random Access Memory, SRAM)实现，假设缓存块深度为L个缓冲槽，宽度根据实际采用的虚通道动态分配方式确定。
|
图 2 路由器端口 Figure 2 Port of the router |
由文献[13]可知，缓存占用整个路由器80%~94%的面积，而在虚通道动态分配式路由器端口中90%以上都是缓存资源，故其端口缓存发生故障概率大于70%，再加上复杂的控制逻辑，使得其端口故障发生概率远高于其他部件发生故障的概率，因此需要对其端口故障进行容错设计。
在端口中可能发生两种形式的故障：缓存故障和控制逻辑故障。当发生缓存故障时会出现两种情况：一种是剩余缓存不能满足节点间通信需求，弃用整个端口；另一种是剩余缓存仍能满足节点当前通信需求，可保留整个端口，但控制逻辑需作出相应的改变。当发生控制逻辑故障时，则必须放弃整个端口。为此，本文对端口故障粒度划分如下：
1) 细粒度端口故障。当缓存块中a(0≤a≤L-1) 个缓冲槽发生故障，而剩余的L-a个缓冲槽仍然能够满足当前节点间通信需求，并且不造成节点阻塞，则认为发生了端口细粒度缓存故障。
2) 粗粒度端口故障。本文中的粗粒度端口故障分为两种：一种是当缓存块中的b(1≤b≤L)个缓冲槽发生故障，而剩余的L-b个缓冲槽无法满足当前节点间通信需求，造成数据包阻塞；二是控制逻辑发生故障，数据包进出SRAM产生未知错误。这两种情况归纳为端口粗粒度故障。对端口故障划分如图 3所示。
|
图 3 端口故障粒度划分 Figure 3 Port fault granularity partition |
端口故障的发生势必会导致端口堵塞或端口失效，划分完故障粒度后，需要针对不同粒度的端口故障采取不同的容错方案，最大限度地减小故障对系统性能产生的影响，关键问题是如何定量确定端口故障粒度。为此，本文借鉴文献[15]提出的一种故障现场实时检测方法，利用一种可以对缓存故障和控制逻辑故障现场实时检测的方法，提出一种统一的粒度划分的故障及拥塞预测模型。当发生故障时，先通过故障检测模块区分出是缓存故障还是控制逻辑故障，再根据排队论原理对缓存故障进行划分；在无故障发生时，可对各端口拥塞程度预测，选择相邻端口中拥塞程度最小的端口进行传输。
1.3.1 排队论当数据包进入虚通道动态分配式的路由器时，其本质上是采用一种先来先服务的服务方式，路由器控制逻辑可看作单服务台。数据包到达各节点的过程是随机且相互独立的，可以将这一过程看作服从泊松分布，则对于路由器东、南、西、北、本地五个方向上的每一个缓冲都可以看作一个服从M/M/1/K规律的排队模型(第一个M表示数据包到达服从泊松到达，第二个M表示服务时间服从负指数分布，1表示单服务台，K表示队列容量)。根据排队论原理，有以下公式：
| $\begin{array}{l} \quad {P_n} = \frac{{1 - \rho }}{{1 - {\rho ^{k + 1}}}} \times {\rho ^n};\quad n = 0,1, \cdots k\\ {\rm{s}}{\rm{.t}}{\rm{.}}\quad \rho = \lambda /u \end{array}$ | (1) |
其中：Pn表示队列中有n个顾客等待的概率；ρ为队列的利用率，其值为顾客到达速率λ与服务速率μ的比值。
1.3.2 模型假设构建一个2D-mesh型大小为m×n的片上网络拓扑结构，借鉴文献[4]提出的虚通道动态分配方式，所建模型基于如下假设：
1) 采用虫孔交换方式以及确定性路由算法，通信基本单位为微片(flit)。
2) 数据包长度可变，其长度用W表示，链路带宽为B flit/s。
3) 路由器本地输入端口上的缓存为无限大，因为处理单元(Processing Element, PE)内有存储器，且数据包一旦到达PE就立即被接收。
1.3.3 模型建立根据式(1)，对于节点(x, y)处dir端口的缓冲Bufferx, y, dir，有n个微片等待的概率Px, y, dirn为：
| $\begin{array}{l} \quad \quad P_{x,y,dir}^n = \frac{{1 - {\rho _{x,y,dir}}}}{{1 - \rho _{x,y,dir}^{L + 1}}} \times \rho _{x,y,dir}^n;\quad n = 0,1, \cdots l\\ {\rm{s}}{\rm{.t}}{\rm{.}}\quad \;{\rho _{x,y,dir}} = {\lambda _{x,y,dir}}/{u_{x,y,dir}} = {\lambda _{x,y,dir}} \times {T_{x,y,dir}} \end{array}$ | (2) |
其中：ρx, y, dir为Bufferx, y, dir的利用率; λx, y, dir为节点(x, y)处dir端口输入通道的数据注入率; ux, y, dir为节点(x, y)处dir端口输入通道的服务速率; Tx, y, dir为节点(x, y)处dir端口输入通道的平均服务时间。
一般认为，路由器缓存中会发生两种类型的堵塞：由输出资源竞争导致的队列头阻塞以及由缓存资源不足引起的队列内阻塞。虚通道动态分配式路由器的出现就是为了消除队列头阻塞，因此本文只考虑缓存资源不足导致的队列内阻塞。为确定缓存故障粒度，本文提出故障粒度阈值这一概念，用δ表示。当堵塞概率εx, y, dir小于等于δ时，认为是细粒度缓存故障；当堵塞概率εx, y, dir大于δ时，则认为发生粗粒度缓存故障。根据排队论，对于M/M/1/K排队模型的有限长队列，数据包被堵塞在队列内的概率εx, y, dir可近似等于队列中有m个微片(1≤m≤L)的概率之和。则有:
| $\begin{array}{l} \quad {\varepsilon _{x,y,dir}} = \sum\limits_{m = 1}^L {P_{x,y,dir}^m} = \sum\limits_{m = 1}^L {\frac{{1 - {\rho _{x,y,dir}}}}{{1 - \rho _{x,y,dir}^{L + 1}}}} \times \rho _{x,y,dir}^m = \\ \quad \quad \frac{{1 - \rho _{x,y,dir}^L}}{{1 - \rho _{x,y,dir}^{L + 1}}} \times {\rho _{x,y,dir}} = \\ \quad \quad \frac{{1 - {{({\lambda _{x,y,dir}} \times {T_{x,y,dir}})}^L}}}{{1 - {{({\lambda _{x,y,dir}} \times {T_{x,y,dir}})}^{L + 1}}}} \times {\lambda _{x,y,dir}} \times {T_{x,y,dir}}\\ {\rm{s}}{\rm{.t}}{\rm{.}}\quad {\lambda _{x,y,dir}} = \sum\limits_{\forall i,j} {\sum\limits_{\forall i',j'} {{\lambda _{i,j}} \times {P_{i,j,i',j'}} \times R(i,j,i',j',x,y,dir)} } \end{array}$ | (3) |
其中：λi, j表示节点(i, j)处的PE向网络中注入数据的平均速率; Pi, j, i′, j′表示(i, j)处的PE向(i′, j′)发送数据的概率; R(i, j, i′, j′, x, y, dir)表示路由算法，如果从节点(i, j)到(i′, j′)的数据要经过(x, y)处dir端口，则R(i, j, i′, j′, x, y, dir)为1，否则为0。对于一个确定的应用来说，Pi, j, i′, j′是已知的，而本文针对的是确定性路由算法，所以R(i, j, i′, j′, x, y, dir)也可以确定下来。对于λi, j，本文在每个路由器的本地网络接口上增加流量监测模块，检测在一定的时钟周期内网络中每个节点的PE向网络中发送的数据流量，从而计算出λi, j，最后可计算出λx, y, dir。
为了计算出εx, y, dir，还需要计算出服务时间Tx, y, dir，服务时间指数据包的头微片进入路由节点到尾微片离开路由节点的时间。在无阻塞发生的情况下，有：
| $\begin{array}{l} \quad {T_{x,y,dir}} = {T_{\rm{H}}} + W \times {T_{\rm{M}}}\\ {\rm{s}}{\rm{.t}}{\rm{.}}\quad {T_H} = {T_{{\rm{RC}}}} + {T_{{\rm{VA}}}},{T_{\rm{M}}} = {T_{{\rm{ST}}}} + {T_{{\rm{CS}}}} + {T_{{\rm{LINK}}}} \end{array}$ | (4) |
其中：TRC为完成对头微片的路由计算的时间；TVA为头微片发出虚通道分配请求及仲裁成功的时间，若路由器控制逻辑固定，则TH为定值；TM为转发单个体微片所需的时间；TST为交叉开关分配的时间; TCS为微片经交叉开关传输的时间; TLINK为微片在链路传输的时间。TCS和TLINK都和数据包长度有关。当数据包遇到阻塞时，有：
| $\begin{array}{l} \quad {T_{x,y,dir}} = {T_{\rm{H}}} + W \times {T_{\rm{M}}} + T_{x,y,dir}^B\\ {\rm{s}}{\rm{.t}}{\rm{.}}\quad T_{x,y,dir}^B = {\omega _{x,y,dir}} \times {\varepsilon _{x,y,dir}}\quad \end{array}$ | (5) |
其中：Tx, y, dirB为遇到缓存不足阻塞的延迟时间；ωx, y, dir为微片在缓存中等待平均时间。ωx, y, dir的计算式如下：
| ${\omega _{x,y,dir}} = \frac{1}{{{u_{x,y,dir}} - {\lambda _{x,y,dir}}}} - \frac{1}{{{u_{x,y,dir}}}} = \frac{{{\lambda _{x,y,dir}} \times T_{x,y,dir}^2}}{{1 - {\lambda _{x,y,dir}} \times {T_{x,y,dir}}}}$ | (6) |
联立式(3)、(5) ~(6)，可求解出平均服务时间Tx, y, dir，再代入式(3)，即可得到数据包被堵塞在队列内的概率εx, y, dir与队列长L的关系。根据故障粒度阈值δ，即可求出故障粒度，建立的粒度划分的故障模型如下：
| ${\varepsilon _{x,y,dir}} = f(L) = \left\{ {\begin{array}{*{20}{l}} {f(a) \le \delta ,} & {\rm{细粒度缓存故障}}\\ {f(b) \ge \delta ,} & {\rm{粗粒度缓存故障}} \end{array}} \right.$ |
其中：a为发生细粒度缓存故障时的缓存数目；b为发生粗粒度缓存故障时的缓存数目。
在无故障发生时，可用εx, y, dir=f(L)拥塞预测模型预测各个端口将要发生拥堵的概率。
2 路由器架构及容错原理本文综合考虑虚通道动态分配式路由器发生粗粒度和细粒度端口故障的情况，提出了一种虚通道动态分配式容错路由器(Fault-tolerant Dynamic Virtual Channel router, FDVC)。主要原理是根据提出的故障及拥塞预测模型，采用邻端口共享方式实现对粗粒度端口故障容错，通过修改控制逻辑指针读写电路对细粒度端口故障容错，且可在无故障出现时，预测端口拥堵情况，提前作出路由决策。
2.1 容错路由器整体设计FDVC路由器整体架构如图 4所示，相比传统的虚通道动态分配式路由器，本文增加了故障实时检测与容忍(Fault Real-time Test and Tolerant, FRTT)模块、邻端口共享(Adjacent Port Sharing, APS)模块，并修改了读写指针电路。故障实时检测与容忍模块负责对虚通道端口故障进行实时检测，并对故障粒度进行划分，通知路由器采用不同的容错方案；邻端口共享模块可在本端口发生故障或拥塞时提供一个备份端口，完成粗粒度端口容错及缓解端口拥塞；通过设计指针读写电路，可为细粒度缓存故障提供容错方案。
|
图 4 容错路由器整体架构 Figure 4 Overall structure of the fault-tolerant router |
在实际应用中，对于2D-mesh型网络中的路由器，网络中间的路由器有5个端口，边界路由器有4个端口，角落路由器有3个端口，所以对于不同端口数目的路由器需采用不同的邻端口共享方案。对于每一种共享方式可用(x, y, z)表示，其中：x、y、z表示端口共享的数目，当x、y、z为1时，表示该端口不采用共享方式。对于3端口共享方式，可采用如图 5(a)所示的(2, 1) 共享方式或图 5(b)所示的(3) 共享方式。这样对于5端口路由器，可采用(2, 2, 1) 或(2, 3) 共享方式，4端口可采用(2, 2) 共享方式。
|
图 5 3端口共享方式 Figure 5 Sharing mode of three ports |
故障实时检测与容忍模块主要由实时端口故障检测(Real-time Buffer Test, RBT)模块、故障粒度诊断(Fault Granularity Diagnosis, FGD)模块和端口分配(Port Allocation, PA)模块组成，其整体结构如图 6所示。
|
图 6 故障实时检测与容忍模块 Figure 6 Fault real-time test and tolerant module |
在路由器正常工作时，实时端口故障检测模块可实时检测端口中发生的缓存故障以及控制逻辑故障，其检测方法结合文献[15-16]提出的故障检测方法，在此不详细叙述。故障测试模块有单独的测试时钟和测试周期，可在路由器正常工作时对端口故障进行实时检测，并将故障信息发送给故障粒度诊断模块，故障信息包括故障端口号、端口故障类型及故障内容，若为控制逻辑故障，故障类型为1，故障内容为空；若为缓存故障，故障类型为2，故障内容为发生故障的缓冲槽的位置；若无故障发生，则故障类型为3，故障内容为空。当故障粒度诊断模块接收到故障信息后，先判断故障类型，若为控制逻辑故障则诊断为粗粒度端口故障，若为缓存故障，则根据预测的端口流量以及接收到的故障缓冲槽的位置信息，计算出端口拥塞程度，并与故障粒度阈值作比较，判断出是粗粒度端口故障还是细粒度端口故障。对于细粒度端口故障，直接由故障粒度诊断模块使能slot_update信号，该信号负责更新缓冲槽故障表(slot_fault_table)，用于启动细粒度端口故障容错方案；对于粗粒度端口故障，由故障诊断模块使能port_update信号，该信号连接至端口选择模块，用于启动粗粒度端口容错方案。
2.3 邻端口共享模块设计当发生粗粒度端口故障时，若继续使用该端口则会造成端口严重堵塞以至于片上网络功能失效，为此，本文设计了APS模块来避免这种情况的发生。相邻两端口的APS结构如图 7所示。
|
图 7 邻端口共享模块结构 Figure 7 Structure of adjacent port sharing module |
APS主要由三路数据选择器和数据解码器构成，第一路数据选择器用于选择输入通道，第二路数据解码器和第三路数据选择器用于选择数据输入端口。相比文献[17]提出的资源减弱共享(Decoupled Resource Sharing, DRS)结构，APS结构能有效阻断数据微片进入故障端口。
图 7中列出了APS模块中几个关键的进出信号，分别是Clock、Data、VC_ID和VC_Full信号，Clock信号用于同步通道数据发送，Data为微片数据，VC_ID为给数据包分配的虚通道ID号，VC_Full信号为下游路由器给上层路由器发送的缓冲满信号。在默认状态下，各个输入通道都选择各自的输入端口，如图 7所示，与端口分配模块相连的信号Channel_sel、Port_sel1和Port_sel2默认状态下都为0。当故障粒度诊断模块发出的信号port_update有效时，端口分配模块使能对APS模块的控制信号，从而为相应的通道分配无故障的输入端口。
2.4 虚通道容错控制逻辑设计对于虚通道动态分配式路由器，最关键的是控制逻辑的设计，控制逻辑主要有三种实现方式：基于链接表实现[7-8]、基于映射表实现[9]和基于快速读写电路实现[4]，一般最常见的是基于链接表的实现方式。为保证路由器在发生细粒度端口故障时，仍能充分利用剩余缓存资源，本文结合后两种实现方式的优缺点，提出一种故障表和快速读写电路相结合的虚通道容错控制逻辑结构。
1) 写指针容错生成电路控制逻辑中的写指针容错生成电路如图 8所示。主要由缓冲槽状态表、缓冲槽故障表以及写指针生成电路构成，缓冲槽状态表中的0表示缓冲槽空，1表示有数据微片；缓冲槽故障表中的0表示缓冲槽无故障，1表示缓冲槽经故障测试后存在故障，与其相连的slot_ update信号负责对缓冲槽故障表进行更新。
|
图 8 写指针生成电路 Figure 8 Generating circuit of writing pointer |
假设某一时刻的写指针为1，并且缓冲槽1位置上的状态为0，数据微片在时钟信号作用下进入缓冲槽1，此时缓冲槽状态表位置1上的状态信号立即由0变为1。如图 8所示，这时，由于数据选择器mul1的输出选择信号由mul2的输出决定，其值为当前写指针缓冲槽故障表上的值与缓冲槽状态表上的值相或后变为1。则mul1选择mul3的输出作为其有效输入，mul3的输出选择信号由mul4的输出信号决定，mul4查询位置为指针加1后的缓冲槽状态，即第2个缓冲槽位置状态，发现虽然其空闲但已发生故障，经由一个或门后mul3选择信号变为1。则mul3选择mul5的输出作为其有效输入，mul5的输出选择信号由mul6的输出信号决定，mul6查询位置为指针加2后的缓冲槽状态，即第3个缓冲槽位置状态，无故障，输出为0，则mul5的输出变为3，即mul1的输出变为3。则在下一时钟到来时，写指针变为3，完成了写指针电路的快速生成以及细粒度端口容错。
2) 读指针容错生成电路读指针容错生成电路如图 9所示。输入到选择器中的信号是由缓冲槽故障表信号取非后与缓冲槽状态信号相与后得到，缓冲槽表的原理与写指针生成电路类似。
|
图 9 读指针生成电路 Figure 9 Generating circuit of reading pointer |
假设当前的读指针(Read Pointer, RP)为1，并且缓冲槽状态表 1位置上值为1，对于图中数据选择器mul1，其输出选择信号由mul2的输出信号决定，mul2查询读指针加1位置上的缓冲槽状态，即槽2上的缓冲槽状态，发现其虽然空闲但是存在故障，故障信号经取非操作后与状态信号相与为0，则mul2输出为0，mul1选择mul3的输出信号作为其输出信号，mul3输出选择信号由mul4的输出信号决定，mul4查询槽位置3上有数据微片且无故障，输出为1，mul3选择(RP+2) 作为输出，即mul1输出为(RP+2) =3。在时钟信号到来时，读取槽1上的数据微片，并且读指针变为3，用于读取下一个数据微片。
3 容错与拥塞缓解方案虚通道动态分配式路由器端口包含最易发生故障的缓存单元以及复杂的控制逻辑，是最易发生故障和拥堵的部位，本文结合第2章提出的路由器架构针对不同的情况提出相应的解决方案。
3.1 端口故障粒度划分的容错方案基于端口粒度划分的容错方案流程如图 10所示。故障实时检测单元RBT在一定的检测周期内实时掌握端口的状态，当在某一时刻检测到端口发生故障，将故障信息发送给故障粒度诊断模块FGD，故障信息包括故障类型、故障端口以及故障内容。FGD根据故障信息判断端口故障的粒度，若为缓存故障，则根据故障模型判断出缓存故障粒度，对于细粒度缓存故障，通过slot_update信号对缓存故障表进行更新，由容错读写指针电路对其进行容错，对于粗粒度缓存故障以及控制逻辑故障，FGD使能slot_update信号发送给端口分配单元，由端口分配模块PA为输入通道分配无故障输入端口，实现基于端口故障粒度划分的容错方案。
|
图 10 容错方案 Figure 10 Fault-tolerant scheme |
路由器一般都用信贷(Credit)方式实现流控，即当下游路由器某端口缓存发生拥堵或缓存满时，通知上游路由器停止往该端口发送数据微片，直到该端口存在可用缓存才通知上游路由器继续发送数据微片，这种方式会带来较大的延时。结合本文提出的拥塞预测模型，本文提出的FDVC路由器能动态感知全局网络流量，实时预测各个端口的拥塞程度，选择拥塞程度低的数据端口路由数据包。当路由器无故障发生时，FGD模块根据接收到的流量信息以及拥塞预测模型，计算相邻端口的拥塞概率，使能port_update信号，由PA模块为数据通道分配输入端口，在一定程度上能有效缓解网络拥堵。
4 实验结果在容错路由器性能评估方面，本文采用修改后的周期精确的片上网络仿真器，搭建8×8的2D-mesh拓扑结构，端口缓存深度为32个数据槽，路由算法采用XY维序路由方式；在面积开销方面，本文采用55 nm工艺标准单元库对本文所提出的路由器进行综合。
4.1 性能评估本文选取三种路由器作为性能比较对象，第一种是基准虚通道静态分配路由器(Baseline Router)，每个端口设置4个虚通道，每个虚通道有8个缓冲槽(缓冲槽总数与动态分配式保持一致)；第二种是借鉴文献[4]提出的动态分配方式设计的高性能路由器(Dynamic Allocated Virtual Channel router, DAVC)，不采取任何容错方案；第三种是在DAVC路由器端口设置文献[17]提出的减弱资源共享模块构造的路由器(Decoupled Resource Sharing router, DRS)。实验方案为在不同的故障模式下，测试采用包括本文提出的FDVC路由器在内的四种路由器的片上互联网络的平均延时和吞吐率。延时指数据包包头从进入网络到包尾离开网络的平均时间差，吞吐率指单位时间内网络处理的数据量，它们是衡量片上网络性能的重要指标。设置FDVC路由器的故障粒度阈值δ为0.8。分别设置3种故障模式：1) 只存在粗粒度端口故障；2) 只存在细粒度端口故障；3) 粗粒度端口故障和细粒度端口故障共存。每种模式设定的故障数目以及位置固定，采用均匀随机模式(uniform)，在三种故障模式下进行性能测试。具体实验结果如下：
图 11为在粗粒度端口故障模式下采用四种不同路由器的网络的延时和吞吐率对比。对于采用基准虚通道路由器的网络，在粗粒度端口故障模式下，其延时急剧增大，吞吐率也较低，在注入率为0.25左右便出现严重的网络堵塞，系统接近饱和。而DAVC因采用动态分配方式，在故障条件下的性能一定程度上优于普通路由器，但在注入率为0.3左右时其延时也会急剧增大，吞吐率较小。而DRS与FDVC路由器性能表现相似，在注入率接近于0.45时才出现一定的延时急剧增加，容错能力较好，吞吐率较高，这是因为在这两种路由器端口增加了容错模块，能够容忍一定的粗粒度端口故障。
|
图 11 粗粒度端口故障模式性能对比 Figure 11 Performance comparison under the mode of coarse-grained port failure |
图 12为在细粒度端口故障模式下的网络的延时与吞吐率对比。在细粒度端口故障模式下，采用基准虚通道静态分配路由器的网络，在注入率为0.3左右时其延时也会急剧增加，吞吐率较小，DRS路由器虽然采用了一定的容错方案，但在出现细粒度缓存故障时未提供较好的容错方案，其性能略优于DAVC路由器。而对于本文提出的FDVC路由器，因设计了虚通道容错控制逻辑，性能表现优良，在注入率为0.4左右才出现延时大幅增加，吞吐率改善明显。
|
图 12 细粒度端口故障模式性能对比 Figure 12 Performance comparison under the mode of fine-grained port failure |
图 13分别为在混合故障模式下的网络的延时与吞吐率对比。在混合故障模式下，对于采用基准虚通道静态分配路由器的网络，相比前两种模式，在相同注入率下，其延时更长，且延时增加得更快，吞吐率较低。而DRS路由器因能容忍一定的粗粒度端口故障，在相同的注入率下，其延时较普通的DAVC路由器较小，吞吐率也比DAVC高，但因无法容忍细粒度端口故障，性能改善不大。对于本文提出的FDVC路由器，在混合故障模式下其性能也有一些损失，这是因为在粗粒度端口故障存在时，有些相邻通道需要用一个端口分时路由数据微片，也会带来一定的延时，但是相比其他三种路由器性能改善较为明显，在注入率为0.5左右时，其吞吐率相比普通的DAVC路由器提高了37.12%。
|
图 13 混合故障模式下性能对比 Figure 13 Performance comparison under the mode of mixed port failure |
本文对不采取任何容错措施的虚通道动态分配式容错路由器DAVC、仅在DAVC端口设置资源减弱共享模块的DRS路由器以及本文的FDVC路由器进行综合，DRS和FDVC共享方案均设置为(2, 2, 1)，并提出性能提升与面积开销比(Ratio of Performance improvement and Area overhead, RPA)这一概念，其代表路由器性能提升与面积开销的比值。性能提升指在各种故障模式下各路由器相对DAVC路由器的饱和吞吐率改善百分比，面积开销指路由器相对DAVC路由器增加的面积百分比，一般RPA值越大, 容错性能就越好，实验结果如表 1所示，表 1中RPA1、RPA2、RPA3分别指在细粒度故障、粗粒度故障和混合故障模式下的平均性能提升与面积开销比。
|
表 1 不同路由器面积对比及评估 Table 1 Area comparison and evaluation of different routers |
从表 1中可以看出，在三种故障模式下，FDVC路由器均能保持较好的性能提升与面积开销比，而对于DRS路由器而言虽然面积开销小，但是在细粒度故障模式下其性能提升与面积开销比并不大，因此本文提出的FDVC路由器的面积开销在一定程度上是可以容忍的。
5 结语本文选取高性能虚通道动态分配式路由器容错设计作为研究内容，结合片上网络性能分析模型与路由器端口故障发生方式，建立了针对端口故障粒度划分的故障与拥塞预测模型，在此基础上设计路由器故障实时检测与容忍模块，邻端口共享模块以及容错读写指针生成逻辑电路。实验结果表明该容错路由器在各种端口故障模式下，均能保持良好的性能且具有容错特性。本文的容错研究尚且停留在端口故障部分，对于高性能路由器的其他模块的容错研究是未来的一个重要研究方向。
| [1] | 周端, 彭景, 张剑贤, 等. 低功耗片上网络路由器设计[J]. 计算机应用, 2011, 31(10): 2621-2624. ( ZHOU D, PENG J, ZHANG J X, et al. Low-power NoC router design[J]. Journal of Computer Applications, 2011, 31(10): 2621-2624. ) |
| [2] | SEITANIDIS I, PSARRAS A, CHRYSANTHOU K, et al. ElastiStore:flexible elastic buffering for virtual-channel-based networks on chip[J]. IEEE Transactions on Very Large Scale Integration Systems, 2015, 23(12): 3015-3028. doi: 10.1109/TVLSI.2014.2383442 |
| [3] | 郑小富, 顾华玺, 杨银堂, 等. 基于提前分配路径的低时延片上路由器结构[J]. 电子与信息学报, 2013, 35(2): 341-348. ( ZHENG X F, GU H X, YANG Y T, et al. Pre-allocated path based low latency router architecture for network-on-chip[J]. Journal of Electronics & Information Technology, 2013, 35(2): 341-348. ) |
| [4] | OVEIS-GHARAN M, KHAN G N. Efficient dynamic virtual channel organization and architecture for NoC systems[J]. IEEE Transactions on Very Large Scale Integration Systems, 2016, 24(2): 465-478. doi: 10.1109/TVLSI.2015.2405933 |
| [5] | LI C, YANG M, AMPADU P. An energy-efficient NoC router with adaptive fault-tolerance using channel slicing and on-demand TMR[J]. IEEE Transactions on Emerging Topics in Computing, 2016, PP(99): 1-1. |
| [6] | WANG L, MA S, WANG Z Y. A high performance reliable NoC router[EB/OL].[2016-10-19]. http://www.aspdac.com/aspdac2016/technical_program/pdf/8A-1.pdf. |
| [7] | LAI M, GAO L, SHI W, et al. Escaping from blocking:a dynamic virtual channel for pipelined routers[C]//CISIS 2008:Proceedings of the 2008 International Conference on Complex, Intelligent and Software Intensive Systems. Piscataway, NJ:IEEE, 2008:795-800. |
| [8] | EVRIPIDOU M, NICOPOULOS C, SOTERIOU V, et al. Virtualizing virtual channels for increased network-on-chip robustness and upgradeability[C]//ISVLSI'12:Proceedings of the 2012 IEEE Computer Society Annual Symposium on VLSI. Washington, DC:IEEE Computer Society, 2012:21-26. |
| [9] | NICOPOULOS C A, PARK D, KIM J, et al. ViChaR:a dynamic virtual channel regulator for network-on-chip routers[C]//Proceedings of the 2006 39th Annual IEEE/ACM International Symposium on Microarchitecture. Piscataway, NJ:IEEE, 2006:333-346. |
| [10] | XU Y, ZHAO B, ZHANG Y T, et al. Simple virtual channel allocation for high-throughput and high-frequency on-chip routers[C]//HPCA 16:Proceedings of the 16th International Symposium on High-Performance Computer Architecture. Piscataway, NJ:IEEE, 2010:1-11. |
| [11] | 姚磊, 蔡觉平, 李赞, 等. 基于内建自测技术的Mesh结构NoC无虚通道容错路由算法[J]. 电子学报, 2012, 40(5): 983-989. ( YAO L, CAI J P, LI Z, et al. A fault-tolerant routing algorithm based on BIST for 2D-mesh network-on-chip without using virtual channels[J]. Acta Electronica Sinica, 2012, 40(5): 983-989. ) |
| [12] | LIU J X, HARKIN J, LI Y H, et al. Fault-tolerant networks-on-chip routing with coarse and fine-grained look-ahead[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2016, 35(2): 260-273. doi: 10.1109/TCAD.2015.2459050 |
| [13] | DEORIO A, FICK D, BERTACCO V, et al. A reliable routing architecture and algorithm for NoCs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2012, 31(5): 726-739. doi: 10.1109/TCAD.2011.2181509 |
| [14] | POLURI P, LOURI A. Shield:a reliable network-on-chip router architecture for chip multiprocessors[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(10): 3058-3070. doi: 10.1109/TPDS.2016.2521641 |
| [15] | GHOSHAL B, MANNA K, CHATTOPADHYAY S, et al. In-field test for permanent faults in FIFO buffers of NoC routers[J]. IEEE Transactions on Very Large Scale Integration Systems, 2016, 24(1): 393-397. doi: 10.1109/TVLSI.2015.2393714 |
| [16] | VAN DE GOOR A, SCHANSTRA I, ZORIAN Y. BIST for ring-address SRAM-type FIFOs[C]//Proceedings of the 1994 IEEE International Workshop on Memory Technology, Design, and Testing. Piscataway, NJ:IEEE, 1994:112-118. |
| [17] | VALINATAJ M, SHAHIRI M. A low-cost, fault-tolerant and high-performance router architecture for on-chip networks[J]. Microprocessors & Microsystems, 2016, 45(PA): 151-163. |
| [18] | 欧阳一鸣, 陈义军, 梁华国, 等. 一种故障通道隔离的低开销容错路由器设计[J]. 电子学报, 2014, 42(11): 2142-2149. ( OUYANG Y M, CHEN Y J, LIANG H G, et al. Design of a low-overhead fault channel isolated fault-tolerant router[J]. Acta Electronica Sinica, 2014, 42(11): 2142-2149. doi: 10.3969/j.issn.0372-2112.2014.11.003 ) |
| [19] | 王坚, 李玉柏, 蒋勇男. 片上网络通信性能分析建模与缓存分配优化算法[J]. 电子与信息学报, 2009, 31(5): 1059-1062. ( WANG J, LI Y B, JIANG Y N. Communication performance analytical model and buffer allocation optimizing algorithm for network-on-chip[J]. Journal of Electronics & Information Technology, 2009, 31(5): 1059-1062. ) |
| [20] | LANGAR M, BOURGUIBA R, MOUINE J. Virtual channel router architecture for network on chip with adaptive inter-port buffers sharing[C]//Proceedings of the 2016 13th International Multi-Conference on Systems, Signals & Devices. Piscataway, NJ:IEEE, 2016:691-694. |