不使用虚拟通道的2D?Mesh容错路由算法

张弘博 段新明

摘 要： 提出一种2D?Mesh上不使用虚拟通道的容错路由算法。目前，同类算法要牺牲掉网络边缘的所有节点，还要把所有错误都包含到一个错误块中。所提算法虽然也将错误包含到错误块中，但是不会牺牲掉网络边缘的所有节点，而是在错误处形成一个矩形区域，使包在路由时可以发现并绕开它。该算法不使用虚拟通道，能容一个甚至更多错误，允许错误发生在任何位置，不仅不会降低网络性能，而且还能获得与其他算法相似的传输延迟。

关键词： 2D?Mesh； 虚拟通道； 容错路由； 错误块； 网络无死锁； 传输延迟

中图分类号： TN915.02?34； TP393 文献标识码： A 文章编号： 1004?373X（2018）15?0034?05

Fault?tolerant routing algorithm without virtual channel in 2D?Mesh

ZHANG Hongbo， DUAN Xinming

（Tianjin Polytechnic University， Tianjin 300387， China）

Abstract： A fault?tolerant routing algorithm without virtual channel in 2D?Mesh is proposed in this paper， with which all nodes of network edge aren′t sacrificed， and a rectangular region is formed at the error position to make the routing package find and bypass the error though the error is contained in the error block as the other same kinds of algorithms do. The proposed algorithm doesn′t use any virtual channel， but still can accommodate one or more errors， and allows errors to occur in any locations， which can′t reduce the network performance， but can obtain the transmission delay similar to other algorithms.

Keywords： 2D?Mesh； virtual channel； fault?tolerant routing； error block； network without deadlock； transmission delay

0 引 言

多核处理器通常利用片上网络来提供片上通信[1]。2D?Mesh因其平面的拓扑结构而被广泛应用于集成电路制造业。大多数多核处理器使用确定性路由算法，如XY路由算法[2?4]，因为它能充分利用路由器的设计，但XY路由不容错。设计容错路由算法的一个主要挑战就是保证网络无死锁。在不使用虚拟通道的片上网络上，通常用转弯模型来避免死锁[5?7]。文献[6]证明当去掉所有最右列时网络就是无死锁的，但是没有最右列，网络左侧边缘就很难容错[8?10]。为了解决这一问题，文献[8?10]提出了解决方案，但这些解决方案需要牺牲大量的无错节点。

本文提出一种不使用虚拟通道的2D?Mesh容错路由算法来解决这一问题。

1 相关知识

文献[8]提出转弯模型的概念。如果所有通道之间的转弯都不能形成环路，那么网络就不会出现死锁。转弯模型的基本思想就是通过禁止最少数量的转弯，即断开环路中的一个或几个转弯避免形成环路。因此，只要禁止足够数量的转弯就可以断开所有的环路，也就能解决网络死锁的问题。

确定性XY路由算法是最简单的路由算法，该算法禁止4种转弯，剩下的4种转弯不能形成环路，因此能解决网络死锁的问题。实际上，对于2D?Mesh网络来说，并不是必须禁止4种转弯才能断开环路，最少只要禁止2种转弯同样也能断开环路。路由算法转弯模型如图1所示。

本文采用矩形错误模型[11]，假设错误块之间不共享边界。如果两个错误块共享边界，那么就会建立一个更大的错误块来代替原来的两个错误块。同时，本文假设错误块是静态的[10]，即包在路由时网络不会出现新的错误块。

1） 2D?Mesh下的错误块是包含危险节点的矩形区域。

2） 危险节点就是错误节点或不安全节点。

3） 无错节点一开始是安全的，当只有一个邻居是危险节点时，安全节点会变成半安全的节点。

4） 当有两个危险邻居或两个半安全邻居时，安全或半安全节点会变成不安全的节点。

5） 错误块的边界包含水平的、垂直的和斜对角的安全节点。

6） 当错误块的边界形成环时称为错误环，否则称为错误链。

矩形错误模型如图2所示。

2 算法介绍

本文算法根据错误块的具体位置分为9种情况，每种情况都结合类西向优先算法产生容一个错误塊的路由算法，错误块的具体分类如图3所示。

类西向优先算法是当目的节点在源节点的左侧时，包向西路由；当目的节点在源节点的正北侧或东北侧时，包向北路由；当目的节点在源节点的正南侧或东南侧时，包向南路由；否则包向东路由。

当错误出现在网络西北角时，即FB?1的情况，原本向西路由的包因错误块的东边界而沿着边界向南路由；原本向北路由的包因错误块的南边界而沿着边界向东路由。

当错误出现在网络北边界时，即FB?2的情况，原本向西路由的包因错误块的东边界而沿着边界向南路由；原本向北路由的包因错误块的南边界而沿着边界向东路由；原本向东路由的包因错误块的西边界而向南路由。

当错误出现在东北角时，即FB?3的情况，仍然采用类西向优先算法。

当错误出现在西边界时，即FB?4的情况，原本向西路由的包因错误块的东边界而沿着边界路由，若目的节点在北侧，则向北路由，否则向南路由；原本向南路由的包因错误块的北边界而沿着边界向东路由；原本向北路由的包因错误块的南边界而沿着边界向东路由。

当错误块出现在网络中间时，即FB?5的情况，原本向西路由的包因错误块的东边界而沿着边界向南路由；原本向南路由的包因错误块的北边界而沿着边界向西路由；原本向东路由的包因错误块的西边界而沿着边界向南路由；原本向北路由的包因错误块的南边界而沿着边界路由，若目的节点在错误块的北侧，则向西路由，否则向东路由。

当错误出现在东边界时，即FB?6的情况，原本向北路由的包因错误块的南边界而沿着边界向西路由；原本向南路由的包因错误块的北边界而沿着边界向西路由。

当错误出现在西南角时，即FB?7的情况，原本向西路由的包因错误块的东边界而沿着边界向北路由；原本向南路由的包因错误块的北边界而沿着边界向东路由。

当错误出现在南边界时，即FB?8的情况，原本向西路由的包因错误块的东边界而沿着边界向北路由；原本向南路由的包因错误块的北边界而沿着边界向东路由；原本向东路由的包因错误块的西边界而沿着边界向北路由。

当错误出现在东南角时，即FB?9的情况，仍然采用类西向优先算法。

3 算法证明

文献[12]证明当相关通道依赖图无环时网络是无死锁的。之后，文献[6]证明当破坏掉顺时针和逆时针环的最右列时，相关通道依赖图是无环的。因此，为了证明提出的算法是无死锁的，本文将对相关通道依赖图无环做如下证明：如果错误没有出现在网络左侧边缘，就不会生成最右列；如果错误出现在网络左侧边缘，最右列不会构成环。

由默认的类西向优先路由算法可知，西北弯、西南弯、北东弯和南东弯是合理的转弯，并且它们之间的组合也不会出现环，其余转弯只在几个特殊情况中出现。如图4所示，默认情况下的类西向优先算法允许出现的转弯只有4个。

声明1：东南弯只出现在FB?4，FB?7，FB?8的东北角和FB?2，FB?5的西边界。

声明2：东北弯只出现在FB?1，FB?2，FB?4，FB?5的东南角和FB?8的西边界。

声明3：南西弯只出现在FB?1，FB?2，FB?4，FB?5的东南角和FB?5，FB?6的北边界。

声明4：北西弯只出现在FB?4，FB?7，FB?8的东北角和FB?5，FB?6的南边界。

声明5：FB?5东北角既不能出现东南弯，也不能出现北西弯。

声明6：不允许出现0°和180°的转弯。

如图5所示，其余的转弯只能出现在网络中特定的位置，并且需要特别标明的是，为了防止形成环路，FB?5的东北角既不允许出现北西弯，也不允许出现东南弯。

引理1 在FB?7，FB?8东北角和FB?2，FB?5西边界出现的东南弯不属于任何最右列。

证明：当东南弯出现在FB?7，FB?8的东北角时，无法在其南侧形成南西弯来与其组成最右列，因为FB?7，FB?8已经到达网络南侧边缘；当东南弯出现在FB?2，FB?5的西边界时，无法在其南侧形成南西弯来与其组成最右列。

引理2 在FB?1，FB?2，FB?5东南角和FB?8西边界出现的东北弯不属于任何最右列。

证明：当东北弯出现在FB?1，FB?2的东南角时，无法在其北侧形成北西弯来与其组成最右列，因为FB?1，FB?2已经到达网络北侧边缘；当东北弯出现在FB?5的东南角或FB?8的西边界时，无法在其北侧形成北西弯来与其组成最右列。

引理3 在FB?1，FB?2，FB?5东南角和FB?5，FB?6北边界出现的南西弯不属于任何最右列。

证明：当南西弯出现在FB?1，FB?2的东南角时，无法在其北侧形成东南弯来与其组成最右列，因为FB?1，FB?2已经到达网络北侧边缘；当南西弯出现在FB?5的东南角或FB?5，FB?6的北边界时，无法在其北侧形成东南弯来与其组成最右列。

引理4 在FB?7，FB?8东北角和FB?5，FB?6南边界出现的北西彎不属于任何最右列。

证明：当北西弯出现在FB?7，FB?8的东北角时，无法在其南侧形成东北弯来与其组成最右列，因为FB?7，FB?8已经到达网络南侧边缘；当北西弯出现在FB?5，FB?6的南边界时，无法在其南侧形成东北弯来与其组成最右列。

引理5 当且仅当东南弯出现在FB?4东北角并且南西弯出现在FB?4东南角时才会出现顺时针最右列。

证明：根据声明1和声明3可知，东南弯可以出现在FB?4的东北角，南西弯可以出现在FB?4的东南角，即可以组成顺时针最右列；再根据引理1，引理3可知，顺时针最右列只能出现在FB?4的东边界上。

引理6 当且仅当东北弯出现在FB?4东南角并且北西弯出现在FB?4东北角时才会出现逆时针最右列。

证明：根据声明2和声明4可知，东北弯可以出现在FB?4的东南角，北西弯可以出现在FB?4的东北角，即可以组成逆时针最右列；再根据引理2，引理4可知，逆时针最右列只能出现在FB?4的东边界上。

引理7 FB?4右侧即使出现最右列也不会构成环。

证明：由引理5和引理6可知，最右列只能出现在FB?4的右侧；并且由声明6可知，不允许出现180°的转弯，因为FB?4已经到了网络的左侧边缘，所以就不存在构成环的左列，即FB?4右侧即使出现最右列也不会构成环。

定理1 本文提出的算法是无死锁的。

证明：当网络中不存在错误时，路由采用的是默认的类西向优先路由，所以网络是无死锁的。当网络中存在错误时，如果网络左侧边缘没有错误，即网络不存在最右列，所以网络是无死锁的；如果网络左侧边缘存在错误，根据引理7，即使出现最右列也不会构成环，所以网络是无死锁的。

4 实验仿真

本文采用的仿真环境是BookSim 1.0，通过在不同通信模式下改变注入率的方法来测试算法的性能，依赖的指标是平均延迟，通信模式选用Uniform，对比的算法选用本文提出的算法在網络中存在一个错误块时的情况，DOR，ROMM，MAD和VAL。因通信模式对网络基数的限制，实验采用8×8的网络结构，其余设置均为BookSim 1.0的默认设置。

如图6所示，在Uniform通信模式下，当网络存在一个错误块时，在注入率达到5%之前，FB?1～FB?4算法的平均延迟相近且缓慢增加；当注入率达到6%之后，各算法的平均延迟开始显著增加并逐渐显现出差异，其中FB?4增幅最大。需要特别指出的是，FB?0为网络不存在错误块的情况，平均延迟最小。

如图7所示，在Uniform通信模式下，当网络存在一个错误块时，在注入率达到5%之前，FB?5～FB?9算法的平均延迟相近且缓慢增加；当注入率达到6%之后，各算法的平均延迟开始显著增加并逐渐显现出差异，其中FB?8增幅最大。

如图8所示，在Uniform通信模式下，当网络存在一个错误块时，在注入率达到5%之前，最差、最优和平均情况下的平均延迟相近且缓慢增加；当注入率达到6%之后，各情况的平均延迟开始显著增加并逐渐显现出差异。值得注意的是，最差情况为错误块出现在FB?4时，平均情况为FB?1～FB?9按概率出现的加权平均值。

如图9所示，在Uniform通信模式下，随着注入率逐渐增大，本文提出的算法和DOR，ROMM和MAD有着相似的性能，并且比VAL在任何注入率下的性能都要好。

从图9分析可知，本文提出的算法基本达到了理论预期的效果，这可以说是一个比较乐观的结果。因为DOR，ROMM，MAD和VAl是几个性能比较好的Oblivious路由算法，而本文提出的算法是基于类西向优先的容错路由算法；DOR算法和MAD算法虽然不使用虚拟通道，但是却不能容错；ROMM算法和VAL算法都使用了2条虚拟通道，否则网络会形成死锁；本文提出的算法不但不使用虚拟通道，而且还能容一个甚至更多错误，在注入率较低时可以获得不错的性能。

5 结 语

本文提出的2D?Mesh无虚拟通道的容错路由算法在2D?Mesh上不使用虚拟通道，而且能容一个甚至更多错误，减少了牺牲的无错节点数目，保证了网络无死锁。实验结果也表明，该算法在网络存在错误时不仅不会降低网络性能，而且还能获得与其他算法相似的传输延迟。值得一提的是，各FB算法的性能相差无几，这使得网络流量分布更加均匀，并且错误可以出现在网络的任何一个位置，这无疑使得该算法更具适应性和鲁棒性。通过对错误块的限制，还可以容更多的错误，牺牲更少的无错节点，这将是以后研究的方向。

参考文献

[1] DALLY W， TOWLES B. Principles and practices of interconnec?tion networks [M]. San Mateo， CA： Morgan Kaufmann， 2004.

[2] BELL S， EDWARDS B， ZOOK J， et al. Tile64?processor： a 64?core SoC with mesh interconnect [C]// 2008 Solid?State Circuits Conference. [S.l.： s.n.]， 2008： 588?598.

[3] FAN D R， YUAN N， LIU L. Godson?T： an efficient many?core architecture for parallel program executions [J]. Journal of computer science and technology， 2009， 24（6）： 1061?1073.

[4] VANGAL S， HOWARD J， BORKAR S. An 80?tile sub?100?W TeraFLOPS processor in 65?nm CMOS [J]. IEEE journal of solid?state circuits， 2008， 43（1）： 29?41.

[5] GLASS C J， NI L M. The turn model for adaptive routing [J]. Journal of the ACM， 1994， 41（5）： 874?902.

[6] CHIU G. The odd?even turn model for adaptive routing [J]. IEEE transactions on parallel distribution systems， 2000， 11（7）： 729?738.

[7] FU B， HAN Y， MA J， et al. An abacus turn model for time/space?efficient reconfigurable routing [C]// 2011 the 38th Annual International Symposium on Computer Architecture. San Jose： IEEE， 2011： 259?270.

[8] GLASS C J， NI L M. Fault?tolerant wormhole routing in meshes [C]// 1993 23rd International Symposium on Fault?Tolerant Computing. Toulouse： IEEE， 1993： 240?249.

[9] WU J. A fault?tolerant and deadlock?free routing protocol in 2D meshes based on odd?even turn model [J]. IEEE transactions on computing， 2003， 52（9）： 1154?1169.

[10] ZHANG Z， GREINER A， TAKTAK S. A reconfigurable routing algorithm for a fault?tolerant 2D?mesh network?on?chip [C]// 2008 ACM/IEEE Design Automation Conference. Anaheim： IEEE， 2008： 441?446.

[11] BOPPANA R， CHALASANI S. Fault?tolerant routing with non?adaptive wormhole algorithms in mesh networks [C]// Procee?dings of 1994 Supercomputing Conference. Washington， D.C.： IEEE， 1994： 693?702.

[12] DALLY W， SEITZ C. Deadlock?free message routing in multiprocessor interconnection networks [J]. IEEE transactions on computing， 1987， 36（5）： 547?553.