基于高层次故障模型的片上网络交换机的诊断策略

柯敏辉

摘要：该文提出了一种基于高层次故障模型的片上网络交换机的诊断策略。该文采用了XY和YX相结合的路由算法以覆盖网格装片上网络的每一个交换机。在高层次故障模型的基础上，通过建立和匹配故障字典可准确定位出发生故障的交换机位置。实验结果表明该诊断方法在仅需要很少硬件成本你的条件下可达到很高的故障覆盖率。

关键词：片上网络交换机；高层次故障模型；故障字典；故障覆盖率

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）28-0038-04

1 背景

随着半导体技术以及集成电路技术的飞速发展，单个芯片中IP（Intellectual Property）核数量越来越多。当单个芯片上集成的IP核数目达到成百上千的时候，基于片上总线的SoC（System-on-chip）在设计上遇到了全局时钟难以同步、地址空间有限、无法支持多节点并行通讯与系统拓展不够灵活等问题，严重制约了集成在单一芯片上的IP核规模及系统性能。

将计算机网络技术引入SoC设计领域，以片上网络的形式从体系结构上彻底解决上述问题成为该领域的研究热点。片上网络的可伸缩性和易扩展性很好地满足了新设计的要求。片上网络逐渐发展成为片上总线之外的一种新的通信结构[1]。

NoC（Network on Chips）可以定义为在单一芯片上实现的基于网络通信的多处理器系统。NoC包括计算和通信两类节点，计算节点完成广义的计算任务，它们可以是SoC，也可以是各种单一功能的IP；通信节点负责计算节点之间的数据通信，通信节点及其之间的网络成为NoC，它借鉴了分布式计算机系统的通信方式，用路由和分组交换技术代替传统的总线技术完成通信任务。

为了让片上网络有效应用于复杂的数字系统，必须要对片上网络进行有效的测试以判断片上网络能否正常工作。对NoC的测试包括对IP核的测试，对网络中的连接链路的测试，以及对交换机的测试[2]。对NoC交换机制测试的重要性能指标有测试功耗、故障覆盖率及测试时间。

对片上网络交换机的测试和诊断一直是NoC研究的热点。文献[3]提出了一种对片上网络交换机制的可拓展的外部测试方法。此方法采用支持确定性路由的偏向交换机。实验表明此方法相比于基于测试设计方法，具有更高的故障覆盖率。并且此方法还具有更少的测试数据量。文献[4]提出了一种对片上网络交换机的并行测试的方法。它重用了芯片上的网络作为测试访问机制（TAM），并通过片上网络来广播测试矢量到被测交换机，通过比较各交换机的输出反馈来检测故障。文献[5]提出了一种片上网络交换机的无扫描的测试方法。其提出了一种对片上网络交换机的高等级故障模型。相比于基于扫描的测试方法，此测试方法还具有更少的硬件开销。文献[6]提出了一种对片上网络交换机的可拓展的测试方法。此方法基于部分扫描链，并利用了一种IEEE 1500兼容的封装器，充分利用片上网络的常规设计来减少测试的面积成本和测试时间。文献[7]提出了一种对片上网络交换机的在线测试的有效方法。实验证明该测试方法具有很高的故障覆盖率和较小的硬件开销。

相比于其他的片上网络交换机的测试方法，基于洪泛算法的片上网络交换机测试方法[6]是一种故障覆盖率高、硬件成本低、简单易行、具有高延展性的测试交换机的算法，然而现有的基于洪泛算法的片上网络交换机测试方法只给出了判定片上网络是否有交换机存在故障，并没有给出明确的故障诊断的方法，即没有精确定位故障交换机。本文基于传统的利用洪泛算法测试片上网络交换机的方法，应用了一种高层次的功能性故障模型，给出了故障诊断的方法，以定位发生故障的片上网络交换机。

2 故障模型和基于洪泛算法的测试方法

2.1 故障模型

针对2D-MESH结构的片上网络，[8]建立了一种高层次的功能性故障模型：

在片上网络交换机中主要包括两类功能故障：数据故障和控制故障。数据故障指数据包中的负载错误，而控制故障指交换机中的路由机制的故障，这是交换机故障在功能方面最主要的表现。

在片上网络中，从功能角度看，交换机发生控制故障的表现形式是数据包被发送到一个错误的输出接口。一种控制故障类型是固定出口（固定方向）型故障，即交换机收到的所有数据包都会被发送至同一输出接口。因此，定义以下含有五个固定型方向的故障模型：

Stuck-at East，Stuck-at West，Stuck-at South，Stuck-at North， Stuck-at Processor。

2.2 洪泛算法

洪泛算法定义如下：源节点将分组发送给所有其相邻节点。在每个节点处，新到来的分组将会被发送至除了到达接口之外的所有其他出口。除非有终止这种不断重传分组的信号，从单个源分组衍生出的分组数量将会是无限的。一种简单的追踪这种传输方式的方法是在每个分组上设定一块跳变计数区。这个计数参数起始值设定为一个最大值，例如在网络中最长的“最短跳变路径”。每当分组经过了一个交换机，其计数参数就会减一。当此技术参数降为0的时候，改分组就会被丢弃。

2.3 传统的洪泛算法测试片上网络交换机的方法

首先设定网格状NoC的测试入口和出口分别在网格的左下和右上角。规定Manhattan 路径：使起点（x1， y1）到终点（x2， y2） 跳变距离最短的路径，路径长度为： |x1 - x2| + |y1 - y2|。一个3×3网格状NoC的Manhattan路径有六种。一个m * n的片上网络的Manhattan路径有条。在测试入口的信息包中插入一个跳变总数值（value），其值等于Manhattan 路径的长度。信息包到达某个路由后，此值减一，并且向除了反方向之外的另外三个方向发送。信息包以此种方式在NoC中传输。当value值等于0时，信息包被丢弃。其中，所需的信息包的数量为存在的路径总数。这样，如果最终到达出口的路径条数等于K（m，n），则转换机制没有问题。否则转换机制有问题。

此方法的优点在于：

1）相比于基于扫描链硬件或BIST测试方法，本方法所需硬件成本低；

2）故障覆盖率很高（接近100%）。

缺点在于：

1）洪泛算法所需测试包数量过多，有很多测试包最终肯定会被丢弃，因而造成了浪费；

2）测试时间和功耗很高，且无法预计；

3）没有实现故障交换机的定位。

2.4 优化的基于洪泛算法测试片上网络交换机的方法

基于上述的洪泛算法测试故障交换机的方法，Mahshid Sedghi等人提出了一种改进的测试方法[9]。此方法将测试包的路由算法由完全的洪泛算法改为采用XY和YX相结合的路由算法，每个收到测试包的交换机都会按XY和YX路由算法发送测试包，这样既保证了100%的故障覆盖率，又能够有效避免测试包的浪费，使测试包数量、测试时间和功耗可预测。

然而，此方法依然只能判定片上网络是否有交换机存在固定方向型故障，却不能实现故障定位。

3 对片上网络交换机的故障诊断

3.1 片上网络拓扑结构：2D MESH结构

2D Mesh结构是目前应用最广泛的拓扑结构，如图1。每个节点连接着一个资源和四个相邻的路由器，每个资源通过一个网络接口（NI）连接着一个路由器。其中的资源，可以是一个处理器核，内存，一个用户自定义硬件模块或者是其他任何可以插入插槽并且可以和网络接口相配的IP（intellectual property）模块。路由器与路由器之间，路由器与资源之间是由一对输入和输出通道连接。通道是由两条单向的点对点总线组成。

3.2 测试生成策略

本文采用[9]中使用的测试生成策略。将片上网络的左下角和右上角处的交换机（记为TAS1和TAS2）同时作为测试输入接口和输出接口。测试包分别从TAS1和TAS2输入，从TAS2和TAS1获得测试结果。测试包在片上网络中采用的路由算法是XY和YX算法相结合的算法，即每个收到测试包的交换机都将该测试包复制一份，并根据目的交换机的位置分别按XY和YX路由算法发出。如图2所示。

采用XY和YX路由算法相结合的路由算法，并从两个方向相互发送测试包，可以在保证故障覆盖率100%的情况下有效减少由洪泛算法造成的测试包的浪费。

3.3 故障诊断方法

为了诊断出片上网络中发生固定型方向的交换机的位置和故障类型，本文采用故障字典匹配的方式诊断片上网络交换机。其诊断流程如下：

1）根据mesh结构片上网络的规模建立完整的故障字典，故障字典的建立方法将在下一章说明；

2）测试入口TAS1（TAS2）分别按XY和YX路由算法发出两个测试包，记录下路由方向，分别用1、2、3、4表示方向E、N、W、S；

3）每个收到测试包的交换机都将该分组复制一份，并按XY和YX路由算法发出，记录下路由方向；

4）在TAS2（TAS1）收集到所有能到达出口的测试包，按故障字典匹配测试包的数据，最终确定故障交换机，故障字典的匹配方法将在下一章说明。

4 故障字典的建立和匹配方法

4.1 故障字典建立方法

如第三章所述，TAS1（TAS2）分别按XY和YX路由算法发出两个测试包，记录下路由方向； 每个收到测试包的交换机都将该测试包复制一份，并按XY和YX路由算法发出，记录下路由方向。按此方式记录下所有到达测试出口的测试包的路径信息应是一个类似于二叉树的结构。图3表示3*3NoC交换机（1，1）发生stuck-at-S故障时，从TAS1至TAS2发送测试包时，在测试出口出获得的类树形结构的路径集合。

因此，建立某交换机发生某固定接口故障对应的二叉树后，取出每一条从根节点到叶子节点且路径长度为Manhattan 路径长度的路径，该集合即为此交换机发生此固定接口故障的故障字典。

按上述方式，取出所有交换机发生所有固定接口故障的路径集合，则建立了完整的故障字典。

由分析可知，单个方向（TAS1至TAS2）的故障字典并不能精确表示故障路径集合（如图中故障交换机发生stuck-at-S和stuck-at-W故障字典相同）。因此需建立两个方向（TAS1至TAS2和TAS2至TAS1）的故障字典。

4.2 故障字典模型

本文建立的故障字典，其每个单元表示片上网路中某一个交换机发生某种固定型方向故障时，在测试出口处所获得的测试包路径的集合，如图4所示。

4.3 故障字典与实际路径匹配方法

故障字典建立完成之后，从测试入口发送测试包至测试出口，在测试出口获得路径集合。将实际在两个测试出口得到的路径集合分别与对应的故障字典进行一一匹配，当发现实际路径集合与故障字典某单元的路径集合完全一致时，则表示此单元对应的交换机可能发生了此单元对应的故障。按此方式可得到两个方向的匹配结果。

一般情况下，将两个方向的结果取交集，则可以得到精确的故障定位结果，即精确定位出哪个交换机发生了哪种故障。

对于如图5所示的特殊情况，即数据包被传至MESH边缘交换机时，不论按XY或YX路由都只能往同一方向发出，而正好故障出现在这个方向。

在此种情况下，有一个方向的匹配结果会无法匹配出故障，而另一个方向的匹配结果能匹配出某一交换机可能发生超过一种故障类型。当出现这种情况时，需要判断该交换机所在位置以精确定位其发生的故障类型。匹配方法如下：

IF “result1 and 2 are not empty” THEN -- “Calculate intersection”

Else

IF “result 1 and 2 are both empty” THEN -- “Not fault”

ELSIF “result 2 is empty”

IF ”fault switch is at the right edge ” THEN -- “stuck-at N fault”

ELSIF ”fault switch is at the top edge ” THEN -- “stuck-at E fault”

ESLE

“return error”

END IF

ELSE

IF ”fault switch is at the leftt edge ” THEN -- “stuck-at S fault”

ELSIF ”fault switch is at the bottom edge ” THEN -- “stuck-at W fault”

ESLE

“return error”

END IF

END IF

END IF

5 仿真实验

本文提出的片上网络交换机的诊断方法通过一种片上网络交换机模拟器NoCSim来实现。本章通过与其他诊断方法比较故障覆盖率、硬件成本和测试时间来说明本文的诊断方法的研究意义和可行性。

5.1 故障覆盖率和硬件成本比较

本文将所提出的诊断方法与两种同样使用高层次故障模型的片上网络交换机模拟器的诊断方法“Slow train and fast train”方法[6]和“自测试交换机”方法[7]以及基于扫描链[5]和基于自建内测试[10]的方法相比较。这些方法所能获得的故障覆盖率和所需硬件成本如表1所示。

由上表可以看出，相比于其它诊断方法，本文所提出的方法仅需要很少的硬件成本就可以达到极高的故障覆盖率（100%）。

5.2 诊断时间

通过仿真实验，获得了本诊断方法对不同规模片上网络的交换机进行故障诊断所需要的诊断时间，如表2所示。

由上表可以看出，在可以达到100%故障覆盖率且硬件成本需求较少的情况下，所需诊断时间可以接受。

6 结束语

本文提出了一种基于高层次故障模型的片上网络交换机的诊断方法。此方法使用XY和YX相结合的路由算法来实现对片上网络所有交换机的完全覆盖。通过记录测试包在片上网络中的跳变方向来获取测试包的路径信息，通过建立故障字典并将实际路径信息与故障字典匹配的方式定位故障交换机。仿真实验表明本方法在仅需要很少硬件成本的条件下能获得极高的故障覆盖率，且诊断时间合理。

参考文献：

[1] ?rika Cota， Fernanda Lima Kastensmidt，Maico Cassel.A High-Fault-Coverage Approach for the Test of Data， Control， and Handshake Interconnects in Mesh Networks-on-Chip[J]. IEEE Transactions on Computers，2006，57（9）：1202-1215.

[2] Yan Zheng， Hong Wang， Shiyuan Yang， et al. Accelerating strategy for functional test of NoC communication fabric[C]. Proceeding of 19th IEEE Asian Test Symposium， 2010， 224-227.

[3] Jaan Raik， Vineeth Govind， Raimund Ubar. External test approach for network-on-a-chip switches[C]. Proceeding of 15th Asian Test Symposium， 2006： 437-442.

[4] Mohammad Hosseinabady， Abbas Banaiyan， Mahdi Nazm Bojnordi， Zainalabedin Navabi. A concurrent testing method for NoC switches[C]. Proceedings of the Design Automation & Test in Europe Conference， 2006： 414-420.

[5] Mahshid Sedghi， Armin Alaghi， Elnaz Koopahi， et al. An HDL-based platform for high level NoC switch testing[C]. Proceeding of 16th Asian Test Symposium， 2007： 453-458.

[6] Alexandre M Amory， Eduardo Bri?o， ?rika Cota， et al. A scalable test strategy for network-on-chip routers[C]. Proceeding of IEEE International Conference on Test， 2005： 591-599.

[7] Armin Alaghi， Naghmeh Karimi， Mahshid Sedghi， et al. Online NoC switch fault detection and diagnosis using a high level fault model[C]. Proceeding of 22nd IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems， 2007： 21-29.

[8] Mahshid Sedghi， Elnaz Koopahi， Armin Alaghi，et al.An Exhaustive Test Strategy Based on Flooding routing for NoC Switch Testing[C]// Proceeding of IEEE East-West Design and Test Symposium （EWDTS）， Yerevan， Armenia， September 2007： 262-267.

[9] Mahshid Sedghi， Elnaz Koopahi， Armin Alaghi， et al. An NoC test strategy based on flooding with power， test time and coverage considerations[C]// Proceeding of 21st International Conference on VLSI Design， 2008： 409-414.

[10] Hsiang-Ning Liu，Yu-Jen Huang，Jin-Fu Li. Memory built-in self test in multicore chips with mesh-base networks. IEEE Computer Society， 2009，50（9）：46-55.