祝龍婷，武繼剛，姜桂圓，王 超

（1.天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387；2.天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300072）

環(huán)網(wǎng)處理器陣列的容錯(cuò)重構(gòu)技術(shù)*

祝龍婷1，武繼剛1，姜桂圓2，王 超1

（1.天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300387；2.天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300072）

高效的容錯(cuò)技術(shù)對(duì)于提高多處理器系統(tǒng)的可靠性至關(guān)重要。環(huán)網(wǎng)（Torus）是連接多處理器陣列的重要網(wǎng)絡(luò)結(jié)構(gòu)，而環(huán)網(wǎng)處理器陣列上的容錯(cuò)重構(gòu)技術(shù)目前尚屬空白。針對(duì)環(huán)網(wǎng)陣列的特殊連接方式，將環(huán)網(wǎng)陣列重構(gòu)問(wèn)題轉(zhuǎn)化為矛盾圖上求解最大獨(dú)立集問(wèn)題。矛盾圖上的結(jié)點(diǎn)表示故障處理器的替換方案，而邊代表了不同替換方案之間的不可共存特性。主要是根據(jù)三種不同的冗余處理器分布方案，設(shè)計(jì)生成矛盾圖算法，求解最大獨(dú)立集算法，以及由獨(dú)立集生成邏輯處理器陣列算法，取得了令人滿(mǎn)意的結(jié)果。實(shí)驗(yàn)結(jié)果表明，當(dāng)陣列規(guī)模較小或故障率較低時(shí)，一行一列和十字型的冗余單元分布的重構(gòu)能力較好；而隨著陣列規(guī)?；蚬收下实脑龃?，三種冗余單元分布策略的重構(gòu)成功率都隨之下降，但可通過(guò)增加冗余單元以及調(diào)整冗余分布來(lái)改善容錯(cuò)效果。此外，從實(shí)驗(yàn)結(jié)果中還可以看出，環(huán)網(wǎng)處理器陣列的容錯(cuò)能力顯然優(yōu)于網(wǎng)格（Mesh）處理器陣列。

環(huán)網(wǎng)處理器陣列；重構(gòu)算法；容錯(cuò)技術(shù)；矛盾圖

1 引言

隨著超大規(guī)模集成電路VLSI（Very Large Scale Integration）和晶片規(guī)模集成電路WSI（Water Scale Integration）技術(shù)的快速發(fā)展，在單一芯片上集成成百上千的處理器單元PEs（Processing Elements）成為可能。然而，隨著VLSI集成密度的迅速增加，多處理器系統(tǒng)的可靠性成為越來(lái)越嚴(yán)峻的問(wèn)題，因而高效的容錯(cuò)技術(shù)對(duì)于提高多處理器系統(tǒng)的可靠性至關(guān)重要?？傮w來(lái)說(shuō)，有兩類(lèi)策略來(lái)進(jìn)行容錯(cuò)重構(gòu)：冗余策略和降階策略。降階策略的特點(diǎn)是原陣列中不存在冗余單元，要盡量多地使用無(wú)故障單元來(lái)生成邏輯陣列。前人證明了基于降階策略的重構(gòu)問(wèn)題大都為NP完全問(wèn)題，同時(shí)還提出了多種啟發(fā)式的解決算法及相關(guān)改進(jìn)。一個(gè)稱(chēng)為GCR（Greedy Column Rerouting）的算法［1］能夠在限定選路距離的條件下得到在選定行上重構(gòu)問(wèn)題的最大邏輯陣列。文獻(xiàn)［2］結(jié)合 GCR算法，提出一個(gè)有效的算法，通過(guò)減少邏輯陣列中的長(zhǎng)連接來(lái)降低功耗。文獻(xiàn)［3，4］分別采用4-端口和6-端口的通道，研究了在行列同時(shí)選路的模式下重構(gòu)，目的都是獲得盡可能大的邏輯陣列。此外，文獻(xiàn)［5，6］將陣列的重構(gòu)問(wèn)題從二維推廣到三維上，并分別提出了一種三維VLSI陣列上的啟發(fā)式重構(gòu)算法和非回溯的重構(gòu)算法。文獻(xiàn)［7］還使用多線(xiàn)程技術(shù)來(lái)加速重構(gòu)算法速度。然而，只要陣列中存在故障，則得到的陣列的規(guī)模就一定會(huì)下降，而冗余策略的目標(biāo)是保證最終邏輯陣列與原始陣列保持相同規(guī)模，進(jìn)而保證計(jì)算性能不降低。冗余策略［8］中，物理陣列中預(yù)留了一定數(shù)量的冗余單元。當(dāng)電路中某些處理單元不能正常工作時(shí)，使用預(yù)留的冗余單元來(lái)替換故障單元。文獻(xiàn)［9］為基于網(wǎng)格連接的處理器陣列提供了一個(gè)自修復(fù)的電路，使用提前集成的冗余單元來(lái)替換故障單元，但這是通過(guò)面積和功耗來(lái)減少時(shí)間上的延遲，需要在面積、功耗和時(shí)間延遲間尋求一個(gè)合理的平衡。在冗余單元重構(gòu)中，還存在不同的開(kāi)關(guān)機(jī)制，文獻(xiàn)［10］通過(guò)選擇多通道開(kāi)關(guān)來(lái)提高陣列的重構(gòu)率，但是單通道開(kāi)關(guān)顯然占用硬件面積小且出現(xiàn)故障率低，故本文的研究與大多數(shù)以往研究一樣，都是基于單通道開(kāi)關(guān)的。

總結(jié)國(guó)內(nèi)外的研究現(xiàn)狀可知，陣列的容錯(cuò)重構(gòu)技術(shù)正處于日益發(fā)展的階段。盡管前人做出了很多這方面的研究成果，但目前的容錯(cuò)重構(gòu)技術(shù)大多基于網(wǎng)格（Mesh）處理器陣列，對(duì)于環(huán)網(wǎng)（Torus）處理器陣列的容錯(cuò)重構(gòu)方面的工作涉及較少，尤其是環(huán)網(wǎng)的冗余容錯(cuò)技術(shù)尚屬空白。而近年來(lái)，環(huán)網(wǎng)互連網(wǎng)絡(luò)越來(lái)越受重視，基于環(huán)網(wǎng)提出的可重構(gòu)系統(tǒng)、映射算法、片上網(wǎng)絡(luò)結(jié)構(gòu)、路由算法等大量涌現(xiàn)［11，12］，這是因?yàn)榕c網(wǎng)格 相比，環(huán)網(wǎng) 具 有更 高的 通信性能。因而，本文研究基于環(huán)網(wǎng)處理器陣列的容錯(cuò)重構(gòu)技術(shù)。本文將環(huán)網(wǎng)處理器陣列的容錯(cuò)重構(gòu)問(wèn)題轉(zhuǎn)化為矛盾圖上的最大獨(dú)立集問(wèn)題，并設(shè)計(jì)高效算法來(lái)實(shí)現(xiàn)矛盾圖構(gòu)造、最大獨(dú)立集求解以及邏輯處理器陣列生成的過(guò)程。

2 基本定義及相關(guān)研究工作

2.1 物理陣列模型

令H表示原始物理陣列，H中含有故障單元，邏輯陣列是指重構(gòu)后不含故障單元的陣列，稱(chēng)為T(mén)。對(duì)于給定的一個(gè)m×n的物理陣列H，用Nf表示陣列中所含故障單元的個(gè)數(shù)，對(duì)于第i個(gè)故障單元，用ei表示，則row（ei）表示第i個(gè)故障單元的物理行坐標(biāo)，col（ei）表示第i個(gè)故障單元的物理列坐標(biāo)，1≤i≤Nf。

本文所討論的物理陣列包含處理單元、冗余單元、開(kāi)關(guān)單元和連線(xiàn)。如圖1所示是一個(gè)規(guī)模為2× 3的環(huán)網(wǎng)處理器陣列，在其上一行和左一列集成了冗余單元。容錯(cuò)重構(gòu)的功能是通過(guò)向陣列中插入開(kāi)關(guān)和連線(xiàn)實(shí)現(xiàn)的，開(kāi)關(guān)和連線(xiàn)將每個(gè)處理單元連接在一起，從而使得陣列可以靈活地改變處理單元之間的連接方式。其中開(kāi)關(guān)單元具有三種狀態(tài)，這些狀態(tài)可以根據(jù)陣列的需求進(jìn)行切換。為了單獨(dú)考慮處理單元的重構(gòu)情況，本文做出了如下假設(shè)：

（1）故障單元能夠轉(zhuǎn)化為連接單元，即連線(xiàn)；

（2）開(kāi)關(guān)單元、連線(xiàn)及冗余單元均不含故障。

Figure 1 Reconfigurable architecture圖1 可重構(gòu)結(jié)構(gòu)

多數(shù)文獻(xiàn)都采用假設(shè)（1）；而假設(shè)（2），因?yàn)殚_(kāi)關(guān)單元和連線(xiàn)比處理單元有著更加簡(jiǎn)單的硬件結(jié)構(gòu)，而冗余單元個(gè)數(shù)比處理單元要少得多，故相對(duì)于處理單元而言，可認(rèn)為三者均不含故障。

為了更好地理解后面的內(nèi)容，在此處介紹幾個(gè)重要的概念。

（1）補(bǔ)償通道。如果一個(gè)故障單元在物理位置（x，y）處存在故障，它可能被一個(gè)位置在（x1，y1）的正常單元 代 替，而 （x1，y1）又 被 另 一 個(gè) 位 置在（x2，y2）的正常單元代替，如此替換下去，直到一個(gè)冗余單元被利用時(shí)，替換過(guò)程結(jié)束。這個(gè)按物理單元的次序（x，y），（x1，y1），（x2，y2），…的替換過(guò)程就定義了一個(gè)補(bǔ)償通道。

隨著冗余單元分布的不同，每個(gè)故障單元可能有著不同個(gè)數(shù)的補(bǔ)償通道。當(dāng)冗余單元的分布如圖1所示時(shí)，每個(gè)故障單元在理論上有兩個(gè)可能的補(bǔ)償通道，其方向分別是向上、向左，用［x—，y］、［x，y—］來(lái)表示。類(lèi)似地用［x+，y］、［x，y+］表示補(bǔ)償通道的方向向下、向右。

Figure 2 Replacement paths圖2 相鄰和非相鄰補(bǔ)償通道

（3）相交。包括兩種情況：

①兩個(gè)故障單元不在同一行或同一列上；

②兩個(gè)故障單元位于同一行或同一列上。

圖3a所示為兩個(gè)故障單元既非同一行，也非同一列，圖3b所示為兩個(gè)故障單元位于同一行。

Figure 3 Intersect圖3 相交

2.2 問(wèn)題描述及以往研究工作

問(wèn)題R 給定一個(gè)規(guī)模為m×n的環(huán)網(wǎng)連接的物理陣列H，H中還包含一定數(shù)量的冗余處理器單元。當(dāng)H中部分處理器發(fā)生故障時(shí)，利用冗余處理器單元對(duì)故障處理器單元進(jìn)行替換，得到一個(gè)m×n邏輯陣列。

為了構(gòu)造有效的邏輯陣列，原始的m×n的物理陣列中所有故障單元都必須能夠被冗余單元所替換，并且替換補(bǔ)償通道間不能出現(xiàn)相交和相鄰的情況。如圖4所示，當(dāng)故障單元u向右進(jìn)行補(bǔ)償，故障單元v向左進(jìn)行補(bǔ)償時(shí)，即為所定義的相鄰情況，此時(shí)需要使用雙通道進(jìn)行布線(xiàn)才能實(shí)現(xiàn)（圓圈標(biāo)記處），而本文所研究的是在單通道的情況下，因而不允許存在相鄰情況。由于環(huán)網(wǎng)在水平和垂直方向上都有環(huán)繞，因此補(bǔ)償通道上可以存在彎曲，但不可以有折線(xiàn)存在，即不允許某個(gè)故障單元被與其非同行或同列的冗余單元替換。此外，兩個(gè)故障單元不能出現(xiàn)爭(zhēng)用現(xiàn)象，即兩個(gè)故障單元位于同一行或同一列上，而這一行或一列上只有一個(gè)冗余單元用于替換故障單元。

Figure 4 Adjacent relation of replacement paths圖4 故障單元補(bǔ)償通道間的相鄰關(guān)系

3 基于矛盾圖理論的重構(gòu)算法

容錯(cuò)重構(gòu)問(wèn)題就是對(duì)于一個(gè)含有故障單元的物理陣列，為每一個(gè)故障處理器找到一個(gè)補(bǔ)償通道，使得所有的故障處理器都可以被非故障處理器替換。本文將容錯(cuò)重構(gòu)問(wèn)題轉(zhuǎn)化為矛盾圖上求解獨(dú)立集的問(wèn)題：首先利用包含故障單元的物理陣列構(gòu)造矛盾圖，之后求解矛盾圖的最大獨(dú)立集，則可以得到對(duì)應(yīng)的邏輯陣列。在本節(jié)將介紹如何將故障陣列轉(zhuǎn)換為對(duì)應(yīng)的矛盾圖。給定物理陣列H，對(duì)H中任意一個(gè)故障單元ei（1≤i≤Nf），用Vi表示其所有可能的補(bǔ)償通道方向的集合，即，其中分別表示上、下、左、右四個(gè)補(bǔ)償通道方向。本文構(gòu)造矛盾圖G（V，E）如下：V是頂點(diǎn)集，每個(gè)頂點(diǎn)表示某個(gè)故障單元的一個(gè)補(bǔ)償通道方向，E是邊集。對(duì)于u，v∈V，當(dāng)且僅當(dāng)u、v不可共存時(shí)，u和v之間有邊相連。

3.1 冗余單元呈上下兩行分布

如圖5a所示，物理陣列中包含上下兩行的冗余單元，則每個(gè)故障單元有兩個(gè)可能的補(bǔ)償通道，其方向分別是向上和向下。該陣列包含四個(gè)故障單元，故有八個(gè)補(bǔ)償通道供選擇，即所構(gòu)造的矛盾圖將包含八個(gè)結(jié)點(diǎn)。

Figure 5 Physical arrays and the corresponding contradiction graphs圖5 物理陣列與對(duì)應(yīng)的矛盾圖

本文提出的生成矛盾圖G（V，E）的算法GCG （Generating Contradiction Graph）過(guò)程如下：對(duì)于H中的每個(gè)故障單元ei，將兩個(gè)結(jié)點(diǎn)和加入到頂點(diǎn)集合V，其中和分別表示對(duì)故障單元ei采用向上補(bǔ)償和向下補(bǔ)償。矛盾圖的邊集E初始化為?，其構(gòu)造過(guò)程如下：

（1）對(duì)于關(guān)聯(lián)同一故障單元的頂點(diǎn)之間添加邊，將這些邊加入邊集合E中；

（2）對(duì)于任意兩個(gè)故障單元，若它們的補(bǔ)償通道存在相鄰關(guān)系（此處僅考慮列相鄰），將相應(yīng)頂點(diǎn)之間應(yīng)添加的邊加入到E中；

（3）對(duì)于任意兩個(gè)故障單元，若一個(gè)故障單元的補(bǔ)償通道上存在另一個(gè)故障單元，則存在相交關(guān)系，將相應(yīng)頂點(diǎn)之間應(yīng)添加的邊加入到E中。因篇幅所限，GCG的偽代碼已省略。

現(xiàn)在我們分析GCG的時(shí)間復(fù)雜度。生成矛盾圖的算法GCG包含兩個(gè)步驟，步驟1是添加結(jié)點(diǎn)到矛盾圖中，顯然步驟1可在線(xiàn)性時(shí)間完成；步驟2是生成矛盾圖的邊集，主要包括構(gòu)造邊集的三個(gè)過(guò)程：構(gòu)造矛盾圖邊集的過(guò)程（1）可在O（Nf）時(shí)間內(nèi)完成，Nf為故障單元個(gè)數(shù)；構(gòu)造邊集的過(guò)程（2）、（3），需要檢查每個(gè)故障單元與其它故障單元之間的位置關(guān)系至多需要O（Nf·Nf）時(shí)間。因而，步驟2的時(shí)間復(fù)雜度上界為O（Nf·Nf）。綜上，算法GCG的時(shí)間復(fù)雜度為O（）。

圖5a展示了將一個(gè)包含兩行冗余處理器的物理陣列轉(zhuǎn)換為矛盾圖的例子：首先，每個(gè)故障單元都有向上和向下兩個(gè)可能的補(bǔ)償通道方向，分別用兩個(gè)點(diǎn)表示，因而矛盾圖中有八個(gè)節(jié)點(diǎn)；然后按照邊的生成規(guī)則，對(duì)相互矛盾的兩個(gè)點(diǎn)之間添加邊相連，最終得到的矛盾圖如圖5a下方所示。需要說(shuō)明的是，頂點(diǎn)6和頂點(diǎn)7違反了相交規(guī)則中的一個(gè)故障單元的補(bǔ)償通道上存在另一個(gè)故障單元，最后這兩個(gè)頂點(diǎn)都不可能出現(xiàn)在正確的重構(gòu)中，故使用虛線(xiàn)連接。

3.2 冗余單元呈一行一列分布

如圖5b所示，物理陣列中包含一行一列的冗余單元，每個(gè)故障單元有四個(gè)可能的補(bǔ)償通道，其方向分別是向上、向下、向左和向右。該陣列包含四個(gè)故障單元，所構(gòu)造的矛盾圖將包含16個(gè)結(jié)點(diǎn)。對(duì)應(yīng)的矛盾圖如圖5b所示，上方為物理陣列，下方為對(duì)應(yīng)的矛盾圖。

生成矛盾圖G（V，E）的過(guò)程如下：對(duì)于H中的每一個(gè)故障單元ei，將四個(gè)結(jié)點(diǎn)加入到頂點(diǎn)集合V，其中分別表示對(duì)故障單元ei采用向上補(bǔ)償、向下補(bǔ)償、向左補(bǔ)償、向右補(bǔ)償。矛盾圖的邊集E初始化為?，其構(gòu)造過(guò)程如下：

（1）對(duì)于關(guān)聯(lián)同一故障單元的頂點(diǎn)之間添加邊，將這些邊加入邊集合E中；

（2）對(duì)于任意兩個(gè)故障單元，若它們的補(bǔ)償通道間存在相鄰關(guān)系（包括列相鄰和行相鄰），將相應(yīng)的頂點(diǎn)之間應(yīng)添加的邊加入到E中；

（3）對(duì)于任意兩個(gè)故障單元，若存在相交關(guān)系（此處包括：①一個(gè)故障單元比另一個(gè)故障單元行數(shù)大列數(shù)大；②一個(gè)故障單元的補(bǔ)償通道上存在另一個(gè)故障單元），將相應(yīng)的頂點(diǎn)之間應(yīng)添加的邊加入到E中；

（4）當(dāng)兩個(gè)故障單元間存在爭(zhēng)用同一冗余單元的現(xiàn)象時(shí)，將相應(yīng)的頂點(diǎn)之間應(yīng)添加的邊加入到E中。

3.3 冗余單元呈十字型分布

如圖5c所示，物理陣列中包含十字型分布的冗余單元，該十字型的冗余單元將物理陣列分成了

四個(gè)區(qū)間，按逆時(shí)針?lè)较?，從左上依次記為一、二、三、四區(qū)間。圖5c上方所示的陣列包含四個(gè)故障單元，每個(gè)故障單元有四個(gè)可能的補(bǔ)償通道，其方向分別是向上、向下、向左和向右，所構(gòu)造的矛盾圖將包含16個(gè)結(jié)點(diǎn)。生成的矛盾圖如圖5c下方所示。

生成矛盾圖G（V，E）的過(guò)程與一行一列的情況類(lèi)似。考慮到區(qū)間的問(wèn)題，邊的構(gòu)造過(guò)程中的

（2）和（3）略有不同。具體變動(dòng)如下，其中（2′）、（3′）分別對(duì)應(yīng)于原步驟的（2）與（3）：

（2′）對(duì)于任意兩個(gè)故障單元，若它們的補(bǔ)償通道間存在相鄰關(guān)系（包括列相鄰和行相鄰，同時(shí)要考慮兩個(gè)故障單元是否處于同一區(qū)間），將相應(yīng)頂點(diǎn)之間應(yīng)添加的邊加入到E中；

（3′）對(duì)于任意兩個(gè)故障單元：

①兩故障單元同區(qū)間時(shí)，與一行一列的相交情況一樣；

②兩故障單元不同區(qū)間時(shí)，按以下區(qū)間組合分別考慮：兩個(gè)故障單元分別在（一、二）區(qū)間或（三、四）區(qū)間；兩個(gè)故障單元分別在（一、四）區(qū)間或（二、三）區(qū)間；兩個(gè)故障單元在（一、三）區(qū)間；兩個(gè)故障單元在（二、四）區(qū)間，若存在相交關(guān)系，將相應(yīng)頂點(diǎn)之間應(yīng)添加的邊加入到E中。

3.4 求解矛盾圖的最大獨(dú)立集

由于最大獨(dú)立集問(wèn)題是一個(gè) NP完全問(wèn)題，而蟻群算法是模擬螞蟻覓食來(lái)尋求解的一種啟發(fā)式算法，經(jīng)常被用于求解組合優(yōu)化這一類(lèi)問(wèn)題。故對(duì)于生成的矛盾圖，本文設(shè)計(jì)了最大最小蟻群算法MMAS（Max-Min Ant System）來(lái)求其最大獨(dú)立集，根據(jù)最大獨(dú)立集可以判斷該物理陣列是否能夠重構(gòu)。MMAS是一個(gè)以迭代的方式進(jìn)行尋找全局最優(yōu)解的過(guò)程，迭代過(guò)程中包括定義啟發(fā)信息，設(shè)置狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新策略。具體過(guò)程詳見(jiàn)文獻(xiàn)［13］。

4 基于最大獨(dú)立集的生成邏輯陣列算法

本文提出的生成邏輯陣列的算法具體如下：首先，初始化邏輯陣列即為物理陣列。然后，以列為單位，按行號(hào)從小到大依次遍歷每個(gè)非冗余單元，若該單元為故障單元，根據(jù)它的補(bǔ)償通道方向判斷該單元將被哪個(gè)單元替換，即重構(gòu)后該單元的邏輯下標(biāo)；如果該單元為非故障單元，檢查該單元是否在列上用于替換了其它單元，若是，根據(jù)該單元所在補(bǔ)償通道的方向決定其重構(gòu)后的邏輯下標(biāo)，否則就直接輸出該單元的物理下標(biāo)；如果該單元的邏輯下標(biāo)與物理下標(biāo)一致，再檢查其是否在行上用于替換了其它單元，若是，根據(jù)該單元所在補(bǔ)償通道的方向決定其重構(gòu)后的邏輯下標(biāo)，否則就直接輸出該單元的物理下標(biāo)。

生成邏輯陣列的偽代碼Log Arr（Logical Array）如下：

現(xiàn)在我們分析該算法的時(shí)間復(fù)雜度。規(guī)模為m×n的處理器陣列上包含Nf個(gè)故障處理器。顯然，在第1行（初始化）所需要的時(shí)間為O（m·n），這是因?yàn)樘幚砥饕?guī)模為m×n。在第2～11行，分別判斷每個(gè)處理器，當(dāng)其為故障處理器時(shí)，需要確定其補(bǔ)償通道的方向，所花費(fèi)時(shí)間為O（Nf）；當(dāng)其為非故障處理器時(shí)，還要分別判斷其在列上、行上是否用于替換其它單元，該操作分別需要的時(shí)間為O（Nf·m）、O（Nf·n）。因而，第2～11行的時(shí)間復(fù)雜度為O（m·n·max｛m，n｝·Nf），因?yàn)樾枰闅v的處理器個(gè)數(shù)為m×n。綜上，算法Log Arr的時(shí)間復(fù)雜度為O（m·n·max｛m，n｝·Nf）。

需要說(shuō)明的是，當(dāng)冗余單元呈上下兩行分布時(shí)，只需要考慮其在列上是否用于替換其它單元；而冗余單元呈十字型時(shí)，在計(jì)算其邏輯位置時(shí)，還要注意區(qū)間的考慮。

圖6展示了當(dāng)冗余單元呈一行一列分布時(shí)，其生成邏輯陣列的例子。圖6a中單元r在u的補(bǔ)償通道上，故單元u被r所替換。陣列中開(kāi)關(guān)狀態(tài)及連線(xiàn)如圖6b所示，由于本文將故障單元直接轉(zhuǎn)換成為連線(xiàn)，故在圖中表現(xiàn)出來(lái)是直接用連線(xiàn)將故障單元穿過(guò)，而對(duì)于未使用的冗余單元本文也通過(guò)使用連線(xiàn)直接穿過(guò)來(lái)處理。

Figure 6 One-row-one-column distribution圖6 冗余單元呈一行一列分布

5 實(shí)驗(yàn)與分析

本文編程使用的語(yǔ)言為C/C++，環(huán)境為Intel Core CPU 3.3 GHz 2 GB。為了客觀公正地評(píng)價(jià)三種冗余分布的性能，在初始陣列中使用隨機(jī)方法來(lái)產(chǎn)生故障單元，從而保證了實(shí)驗(yàn)數(shù)據(jù)的隨機(jī)性。本文分別在特定的陣列規(guī)模和特定的故障率下，比較這三種冗余單元分布隨著故障率的增高和陣列規(guī)模的增大，陣列重構(gòu)率是如何變化的。本文將陣列重構(gòu)率定義為30次實(shí)驗(yàn)中重構(gòu)成功的概率，用Reliability表示；將三種冗余分布按上下兩行、一行一列及十字型依次定義為case 1、case 2、case 3。

表1展示的是固定陣列規(guī)模分別為16×16和32×32時(shí)，三種冗余單元分布在不同故障率下的重構(gòu)率。從表1中可以看出，在陣列規(guī)模一定的情況下，隨著故障率的增加，三種冗余單元分布的重構(gòu)率都有所下降。這是由于陣列規(guī)模不變，則冗余單元數(shù)量不變，而故障率增加使得故障單元數(shù)量增多，最終導(dǎo)致冗余單元無(wú)法滿(mǎn)足替換全部故障單元的情況。例如，當(dāng)故障率從3%上升到4%時(shí)，在陣列規(guī)模為16×16和32×32的情況下，三種冗余單元分布的重構(gòu)率都下降了，其中上下兩行的重構(gòu)率下降最快，因?yàn)檫@種冗余分布的陣列只能在列上進(jìn)行重構(gòu)，故重構(gòu)能力較差。

Table 1 Impact of fault density on reliability表1 故障率對(duì)重構(gòu)成功率的影響

圖7是將故障率設(shè)為8%，針對(duì)Mesh和Torus的三種冗余單元分布，在不同陣列規(guī)模下得到的重構(gòu)率。從圖7中可以看出，在故障率固定的情況下，隨著陣列規(guī)模的增大，對(duì)于Mesh和Torus網(wǎng)絡(luò)的三種冗余單元分布的重構(gòu)能力都有所下降，尤其是上下兩行的冗余單元分布下降得更明顯。這是因?yàn)殡m然陣列規(guī)模增大，使得冗余單元和故障單元同時(shí)都有所增大，但是由于冗余單元的分布情況使得故障單元數(shù)量比冗余單元數(shù)量增長(zhǎng)得快，因而隨著陣列規(guī)模的增加，三種冗余單元的重構(gòu)能力都有所下降。例如，當(dāng)陣列規(guī)模從8×8上升到16× 16時(shí)，三種冗余單元分布的重構(gòu)率都有所下降。同時(shí)，從圖7中可以看出，對(duì)于三種情況下的冗余分布，Torus網(wǎng)絡(luò)比Mesh網(wǎng)絡(luò)的重構(gòu)成功率要高，這是因?yàn)門(mén)orus具有更靈活的連接方式，故比Mesh中的每個(gè)冗余單元有更多的機(jī)會(huì)選擇替換哪個(gè)故障單元。需要說(shuō)明的是，當(dāng)陣列規(guī)模為16×16時(shí)，在圖7a和圖7b中，Mesh網(wǎng)絡(luò)的重構(gòu)率為0。

不同的冗余分布可以發(fā)現(xiàn)，當(dāng)冗余單元數(shù)目為故障單元的兩倍時(shí)，一行一列和十字型的冗余單元分布的重構(gòu)能力較好，使得陣列具有較高的穩(wěn)定性。

Figure 7 Reliability comparison of Torus and Mesh圖7 Torus與Mesh重構(gòu)率的對(duì)比圖

6 結(jié)束語(yǔ)

本文在環(huán)網(wǎng)處理器陣列上，率先提出了基于矛盾圖理論的容錯(cuò)方法。通過(guò)將故障單元的補(bǔ)償通道方向表示成矛盾圖的頂點(diǎn)集合，從而將故障陣列能否重構(gòu)的問(wèn)題轉(zhuǎn)化為求解矛盾圖的最大獨(dú)立集問(wèn)題，并對(duì)于能夠重構(gòu)的陣列提出了一種生成邏輯陣列的算法。實(shí)驗(yàn)結(jié)果表明，只要保證冗余單元數(shù)目為故障單元的兩倍，就可以使得一行一列和十字型的冗余單元分布得到較好的重構(gòu)率，使得陣列具有較高的穩(wěn)定性。

在本文中，當(dāng)故障單元增多時(shí)，重構(gòu)率較低，這是因?yàn)閿[放的冗余單元數(shù)較少。在接下來(lái)的工作中，作者計(jì)劃研究更多的結(jié)點(diǎn)擺放方案，同時(shí)考慮按照不同的陣列規(guī)模設(shè)定不同的冗余方案，從而使得既不浪費(fèi)大量的冗余單元，還能保證較好的重構(gòu)率。

［1］ Low C P，Leong H W.On the reconfiguration of degradable VLSI/WSI arrays［J］.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，1997，16（10）：1213-1221.

［2］ Wu J G，Srikanthan T，Jiang G Y，et al.Constructing sub-arrays with short interconnects from degradable VLSI arrays ［J］.IEEE Transactions on Parallel and Distributed Systems，2014，25（4）：929-938.

［3］ Wu J G，Srikanthan T.Integrated row and column re-routing for reconfiguration of VLSI arrays with 4-port switches［J］. IEEE Transactions on Computers，2007，56（10）：1387-1400.

［4］ Wu J G，Srikanthan T，Schroder H.Efficient reconfigurable techniques for VLSI arrays with 6-port switches［J］.IEEE Transactions on Very Large Scale Integration Systems，2005，13（8）：976-979.

［5］ Jiang G Y，Wu J G，Sun J Z.Efficient reconfiguration algorithms for communication-aware three-dimensional processor arrays［J］.Parallel Computing，2013，39（9）：490-503.

［6］ Jiang G Y，Wu J G，Sun J Z.Non-backtracking reconfiguration algorithm for three-dimensional VLSI arrays［C］∥Proc of the 18th International Conference on Parallel and Distributed Systems，2012：362-367.

［7］ Shen Y Z，Wu J G，Jiang G Y.Multithread reconfiguration algorithm for mesh-connected processor arrays［C］∥Proc of the 13th International Conference on Parallel and Distributed Computing，Applications and Technologies，2012：659-663.

［8］ Zhang L.Fault-tolerant meshes with small degree［J］.IEEE Transactions on Computers，2002，51（5）：553-560.

［9］ Takanami I，Horita T.A built-in circuit for self-repairing mesh-connected processor arrays by direct spare replacement ［C］∥Proc of the 18th Pacific Rim International Symposium on Dependable Computing，2012：96-104.

［10］ Horita T，Takanami I.Fault-tolerant processor arrays based on the 1.5-track switches with flexible spare distributions ［J］.IEEE Transactions on Computers，2000，49（6）：542-552.

［11］ Luo W，Dong X.An efficient adaptive deadlock-free routing algorithm for torus networks［J］.IEEE Transactions on Parallel and Distributed Systems，2012，23（5）：800-808.

［12］ Ramanujam R S，Lin B.Randomized throughput-optimal oblivious routing for torus networks［J］.IEEE Transactions on Computers，2013，62（3）：561-574.

［13］ Li Y M，Xul Z B.An ant colony optimization heuristic for solving maximum independent set problems［C］∥Proc of the 5th International Conference on Computational Intelligence and Multimedia Applications，2003：206-211.

祝龍婷（1990），女，安徽桐城人，碩士生，研究方向?yàn)楦咝阅荏w系結(jié)構(gòu)。E-mail：zlongting@gmail.com

ZHU Long-ting，born in 1990，MS candidate，her research interest includes high performance architecture.

Reconfiguration approaches for fault-tolerant torus-connected processor arrays

ZHU Long-ting1，WU Ji-gang1，JIANG Gui-yuan2，WANG Chao1
（1.School of Computer Science and Software Engineering，Tianjin Polytechnic University，Tianjin 300387；2.School of Computer Science and Technology，Tianjin University，Tianjin 300072，China）

High-efficient fault-tolerant techniques are essential for improving the reliability of multiprocessor systems.It is well known that torus is an important interconnection network for multiprocessor arrays，but no work has been reported on the faulty tolerance of torus-connected processor arrays.In our work，reconfiguring a torus-connected processor array is modeled to be a maximum independent set problem.The nodes on the contradiction graph represent alternatives of the fault processing elements （PEs），and the edge denotes that different alternatives cannot coexist.Three different distributions of redundant PEs are discussed，and three algorithms are proposed to construct contradiction graphs，solve maximum independent set，and generate logic arrays based on the produced maximum independent set. Simulation results show that，the cross distribution and one-row-one-column distribution perform well in reconfiguration for smaller arrays and smaller fault densities.In addition，the reconfiguration ability of the three proposed distribution patterns decreases as the fault density and array size increase，thus other spare distribution patterns should be investigated，or more spare PEs should be integrated.Moreover，torus arrays outperform mesh arrays in terms of fault-tolerance performance.

torus-connected processor array；reconfiguration algorithm；fault-tolerance；contradiction graph

TP303

A

10.3969/j.issn.1007-130X.2015.08.002

1007-130X（2015）08-1423-07

2014-08-11；

2014-10-11

國(guó)家自然科學(xué)基金資助項(xiàng)目（61173032）；國(guó)家自然科學(xué)基金天元青年基金資助項(xiàng)目（11326211）

通信地址：300387天津市西青區(qū)賓水西道399號(hào)天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院

Address：School of Computer Science and Software Engineering，Tianjin Polytechnic University，399 Binshui Rd West，Xiqing District，

Tianjin 300387，P.R.China