片上网络容错路由算法分析和评价

摘 要：片上网络技术是借鉴并行分布式计算机及传统计算机网络的概念解决片上多核系统的通信问题。片上网络代替片上总线通信，解决了片上总线结构所引起的可扩展性、效率、面积、功耗等问题。然而，片上网络在数据传输过程中可能由于各种原因产生故障，因此片上网络可靠性研究是当前一个研究热点。首先总结了片上网络故障分类，比较和分析了当前片上网络容错算法并给出其优势和缺陷，最后对全文进行总结，并给出了片上网络容错算法的展望。

关键词：

中图分类号： TP302．8 文献标识码： A 文章编号：2095－2163（2011）03－0064－03

Analysis and Evaluation of Fault－tolerant Routing Algorithms for NoC

LI Benjuan， WANG Jiafang， JIANG Yu， LI Xuliang

Abstract： Borrowing ideas from the concept of parallel distributed processing system and traditional computer networks, Network-on-Chip technology solves the problems of multi-core SoC . NoC takes the place of the bus on the SoC to solve the reliability， power consumption， area， efficiency which caused by the bus .However, NoC may result in the faults when it transmits the data. So the reliability of network on-chip is a hot topic currently. This paper summarizes the classification of the network on-chip faults, analyzes and compares the fault-tolerant algorithms meanwhile, points out the advantages and disadvantages of these algorithms. Then the paper gives a conclusion. finally presents future works about fault-tolerant routing algorithms on NoC.

Key words：

0 引言

根据ITRS（International Technology Roadmap for Semiconductors，国际半导体技术路线图）中的预测[1]，到2018年，单个芯片上集成的晶体管数目将达到2560亿个。传统以总线互连的片上系统无法满足用户对可展性、能耗、面积、可重用性、服务质量等方面需求。

2000年，片上网络（Network on Chip，以下简称NoC）的概念被提出[2]。图1显示了一个二维4×4 mesh NoC结构，由图可知：NoC主要由交换单元、网络接口和链路组成。在4×4mesh中，一个晶体被分割成16个对称的功能独立的子模块。IP核被映射到这些块上并同NoC进行通信，每个IP核都与一个网络接口和交换单元相连。每个交换单元都与4个邻居交换单元相连。每个网络结点由路由器、IP核、网络接口组成，各个网络结点又由链路相连接构成一个片上网络。

片上网络的研究内容包括拓扑结构、交换机制、服务质量、应用映射、路由器结构、路由算法等6个方面。在研究近年来国内外研究成果的基础上，本文将片上网络故障分为硬故障和软故障两种，并对解决硬故障的容错路由算法进行分析和评价，最后指出片上网络路由容错算法的研究方向。

1 片上网络故障分析

在片上网络研究领域，NoC故障主要分两种：一种是永久性故障（permanent faults），主要由电转移、制作工艺和测试挑战等引起的加速老化效应导致的，又称为硬故障[3]；另一种是瞬时性故障（transient faults），主要由于片上网络路由器及之间的链路受到串扰、电磁干扰和电源噪声的影响，而引起信号、逻辑值和数据位出错等故障，又称为软故障。目前针对软故障主要是包括校正、重传、混合纠错在内的三种解决方法。永久性故障是路由器资源模块故障，一旦发生，就会永远存在，不可逆转；包括路由器节点失效和链路失效（图2所示）[4]。硬故障是突发性的，又是永久性的，一旦发生，除了更换硬件外是无法修复的。所以在实际NoC设计中，往往采用一定的容错路由算法或者添加冗余硬件来实现对硬故障区域的绕道，从而解决问题。

2 NoC容错路由算法

在NoC中，路由算法主要确定数据包的转发端口，从而确定数据包从源节点到目的节点的转发路径。容错路由算法就是在路由算法的基础上增加容错功能。容错路由算法的优劣，直接决定了网络时延和吞吐，影响NoC物理设计。总体来说，Noc容错路由算法可以分为基于自适应思想容错路由算法、基于洪泛思想的容错路由算法和混合类型容错路由算法。

2．1 基于自适应思想的容错路由算法

适应性路由算法的特点是分组数据包从源节点到目的节点不只是存在唯一的一条路径，而是多条路径[5]。因此，适应性路由算法具有一定的容错功能，好的适应性路由算法应能很好地解决网络拥塞状况，从而达到均衡网络中各节点的负载，提高网络整体性能的目的。根据路由适应性程度的不同，适应性路由又可以分为完全适应性路由和部分适应性容错路由算法两大类。

部分适应性容错路由算法，主要通过限制一些方向的转向来避免环路的形成，从而避免死锁的产生。该类型的容错路由算法主要有先西优先路由（West－first Routing），北最后路由（North－last Routing），负优先路由（negative－first Routing）以及奇偶转向路由（Odd－Even Routing）[6]。

完全适应性容错路由进一步提高了路由的适应性程度，因而获得更好的网络性能，但算法的实现比较复杂，研究的相对较少。以Dyxy路由算法[7]为例，主要思想是比较分组的当前节点和目的节点的各维坐标，当某维相同，则避开该维转向其他维路由，否则，选择向拥塞程度最小的相邻节点路由，Dyxy是在维序路由的基础上改进的一种路由算法，且充分考虑了网络的拥塞情况。

2．2 基于洪泛思想的容错路由算法

基于此思想的容错路由算法主要包括：直接洪泛（direct flooding）、概率洪泛（probability flooding）、N－冗余随机走动（N－rodom walk）路由容错算法[3]。

概率洪泛路由算法是最简单的随机路由算法。

图3是概率洪泛路由算法的实例，洪泛过程描述如下：S表示源节点，D表示目的节点。A、B、C、E、F、G、H分别为中间节点。如果S要发送报文到D，需要查找由S到D的路径。这时S需要将路由请求以概率p发送给所有的邻节点A、B、C和F。当C和F收到路由请求后，同样将报文转发给所有的邻节点。依此类推下去，G会收到分别来自于节点C和F发送过来的同一报文，在此过程中，G将转发先到的报文给其所有的邻节点，后到的报文内容如果相同，则将相同报文丢弃。

直接洪泛容错路由算法将目的节点的位置考虑到扩散过程中，降低了概率扩散算法中盲目的扩散数据所引起的较大的功耗。在直接扩散算法中，源节点以不同概率向其邻居节点发送数据包，离目的节点近的节点以较高的概率发送，离目的节点较远的节点以较低的概率发送数据包副本，如此重复，直到数据包路由到目的节点。

文献[3]还提出了一种新的考虑目的节点位置的容错算法：N－冗余随机走动算法。算法在由发送端开始的第一跳采用泛洪机制，但数据包的拷贝数量事先预订好，即N。从第二跳开始，所有收到数据包的节点都在N／S／W／E四端口中选择一个最优端口，将数据发送出去。这种算法中的一个关键点在于第一跳中数据包拷贝份数N的确定，文献指出利用Markov链与随机走动理论推算[8]。

2．3 混合类型容错路由算法

混合类型的容错路由算法可以分以下三种情况：一是可以分为无故障和有故障两个阶段，数据包在从源节点路由到目的节点的过程中，可以在这两个阶段多次转换。二是确定性路由和自适应路由结合的容错路由算法。三是洪泛路由和奇偶转向相结合的容错路由算法。

3 评价和分析

本文是基于三种容错思想进行容错路由算法的分析。表1对以上三种思想的容错路由算法的特点进行了总结。

延迟、吞吐量、功耗是片上网络容错路由算法的评价标准。时延由发送时延、传输时延和接收时延三部分组成。如公式（1）所示：

Li＝Lsender＋Ltransport＋Lreceiver （1）

而电路设计中主要用平均时延进行线路延迟分析。所谓平均时延，就是指在给定周期内发送数据包从源节点到目的节点所需时间的平均值。假设N为在给定周期内所接收到包的数目，Li为第i个包的时延，如公式（2）。

Lavg＝ （2）

片上网络中，消息吞吐量是指接收到的数据包长度占整个发送数据包长度的比值，公式（3）为消息吞吐量T的具体形式。

T＝ （3）

对直接洪泛、概率洪泛、N－冗余容错路由算法的在网络中有一个错误的情况下的成功传输百分比如表2所示。由此

表中可以看出，概率洪泛和直接洪泛容错路由算法有相近的成功传输百分比，而N－冗余随机走动算法则有更高的可靠性和容错能力。

4 结束语

片上网络（NoC）是未来芯片技术的发展趋势，解决片上网络故障是影响片上网络性能的关键因素。本文对片上网络故障分为硬故障和软故障，并总结了解决硬故障的容错路由算法。基于自适应思想、洪泛思想、混合思想三个方面对容错路由算法进行讨论和分析。今后研究工作的重点是在现有的容错路由算法的基础上，设计、研究出在功耗、容错能力、延迟等各个性能上达到平衡的容错路由算法。

参考文献：

[1] BENINI L，DE MICHELI G．Networks on chips：a new SoC Par－

adigm[J]．IEEE Computer，2002：70－78．

[2] 高明伦，杜高明． NoC：下一代集成电路主流设计技术[J]． 微电子

学，2006，36（4）．

[3] SEYRAFI M，ASAD A． A new low cost fault tolerant sdolution

for mesh based NoCs[J]． International Conference on Electroni－

cs and Information Engineering，2010，V2－207－V2－213．

[4] PIRRETTI M，LINK G M，BROOKS R R，et al． Fault tolerant

algorithms for network－on－chip interconnect[C]／／ Proc． Of IEE－

EE International Annual Symposium on VLSI． Tampa USA： I－

EEE Press ，2004：46－51．

[5] NI C G． The turn model for adaptive routing[J]． ACMvol5，1994，

5：874－902．

[6] CHIU M． The odd－even turn model for adaptive routing[J]．IEEE

Trans． On parallel and Distributed Systems，2000：729－738．

[7] LI Ming， ZENG Qingan， JONE Wenben． DyXY－A proximity c－

ongestion－aware deadlock－rree dynamic routing method for net－

work on chip[J]． DAC，2006：849－852．

[8] STEWART W J． Introduction to the numerical solutions of m－

arkov chains[J]． Elizabeth： Princeton University Press，1994：104

－105．