基于網(wǎng)絡(luò)流的高效VLSI子陣列重構(gòu)

黃弼勝， 錢俊彥

(桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院，廣西 桂林 541004)

近年來，隨著超大規(guī)模集成電路(very large scale integration，簡(jiǎn)稱VLSI)技術(shù)的飛速發(fā)展，單一芯片上的集成密度不斷提高，這使得芯片處理數(shù)據(jù)的能力有了很大提高。然而，隨著處理單元(process element，簡(jiǎn)稱PE)數(shù)量的指數(shù)級(jí)增長(zhǎng)，使得芯片中的處理單元出現(xiàn)故障的概率也大大增加,其中損壞的處理單元會(huì)影響整個(gè)芯片系統(tǒng)的運(yùn)行。因此，為了保證芯片的可靠性和穩(wěn)定性，容錯(cuò)技術(shù)在VLSI領(lǐng)域上的運(yùn)用也勢(shì)在必行。

VLSI領(lǐng)域中的容錯(cuò)技術(shù)總的來說有冗余法和降階法2種方法。冗余法[1-2]的主要思路是：在VLSI陣列生產(chǎn)過程中會(huì)生產(chǎn)一些多余的備用處理單元，當(dāng)芯片上的單元有損壞時(shí)，這些多余的單元就以某種方法替換受損的處理單元，從而保證整個(gè)芯片的正常運(yùn)行。降階法與冗余法有所不同，VLSI陣列中不會(huì)有多余的備用處理單元，當(dāng)有單元損壞時(shí)，通過算法改變單元間的開關(guān)和線路的鏈接方式來構(gòu)造一個(gè)結(jié)點(diǎn)規(guī)模盡可能大的邏輯子陣列，盡可能地提高剩余無故障處理單元的利用率。

基于網(wǎng)絡(luò)拓?fù)浞植嫉腣LSI陣列，Kuo等[3]提出了3種不同的降階重構(gòu)路由方案，并證明了在這些不同的路由方案下的重構(gòu)問題是NP完全問題。Low等[4]提出了一種最優(yōu)貪婪算法，可在線性時(shí)間內(nèi)構(gòu)造最大目標(biāo)陣列(maximum target array，簡(jiǎn)稱MTA)。其他一些重要的降階法分別在文獻(xiàn)[5-6]有詳細(xì)的介紹。

目標(biāo)子陣列的內(nèi)部總鏈接長(zhǎng)度對(duì)于整個(gè)芯片系統(tǒng)的性能有較大影響。Wu等[7]提出一種基于動(dòng)態(tài)規(guī)劃的算法來減少邏輯子陣列的長(zhǎng)鏈接個(gè)數(shù)，該算法雖然可以減少長(zhǎng)鏈接個(gè)數(shù)，但不能讓長(zhǎng)鏈接數(shù)減到最少。針對(duì)此問題，Wu等[8]又提出一種基于分治策略的算法，相較于之前的算法在減少長(zhǎng)鏈接方面有較大提高。但這2種算法都不能構(gòu)造出最優(yōu)的高性能目標(biāo)陣列。Qian等[9]基于網(wǎng)絡(luò)流提出一種構(gòu)造高性能目標(biāo)陣列的最優(yōu)算法(ALG16)，可在多項(xiàng)式時(shí)間內(nèi)構(gòu)造出高性能目標(biāo)陣列。然而，由ALG16構(gòu)造的網(wǎng)絡(luò)模型比原始的網(wǎng)絡(luò)拓?fù)淠Ｐ蛶缀醵喑?倍的結(jié)點(diǎn)數(shù)量，且傳統(tǒng)的網(wǎng)絡(luò)流算法在VLSI陣列的網(wǎng)絡(luò)拓?fù)浞植枷掠性S多不足的地方，所以ALG16算法在運(yùn)行時(shí)間上表現(xiàn)不足。為了加快高性能目標(biāo)陣列的重構(gòu)速度，在ALG16的基礎(chǔ)上，提出一種帶數(shù)據(jù)結(jié)構(gòu)的高效網(wǎng)絡(luò)模型，減少模型的結(jié)點(diǎn)個(gè)數(shù)，并對(duì)ALG16中所使用的傳統(tǒng)網(wǎng)絡(luò)流算法進(jìn)行改進(jìn)，減少算法的迭代次數(shù)，從而提高算法的運(yùn)行速度。

1 處理器陣列結(jié)構(gòu)與問題描述

1.1 陣列結(jié)構(gòu)

用H表示一個(gè)m×n的主陣列，其中m、n分別為主陣列的物理行數(shù)和物理列數(shù)。p(0≤p≤1)為主陣列的錯(cuò)誤率，則剩余的可用處理單元數(shù)為(1-p)×m×n個(gè)。經(jīng)重構(gòu)得到的無損壞結(jié)點(diǎn)的m′×n′的子陣列，稱為目標(biāo)陣列，用T表示。

主陣列的物理結(jié)構(gòu)如圖1所示，ei,j為位于主陣列第i行、第j列的處理單元。若ei,j損壞，則ei,j-1可直接穿過ei,j與ei,j+1進(jìn)行數(shù)據(jù)通信，這樣的方案叫做行旁路方案。同理，可類似地定義列旁路方案。若ei+1,j為損壞的單元，則ei,j可通過外部的開關(guān)與兩邊相鄰列的結(jié)點(diǎn)ei+1,j'進(jìn)行通信，這里定義|j′-j|≤d，d為補(bǔ)償距離，這樣的方案叫做列重路由方案。為了減少開關(guān)的過載，補(bǔ)償距離d應(yīng)設(shè)置為一個(gè)較低的數(shù)值，這里將d設(shè)置為1。同理，可類似地定義行重路由。

圖1 處理器陣列體系結(jié)構(gòu)

設(shè)col(u)為u的列序號(hào)，基于補(bǔ)償距離的限制，將u的下鄰接結(jié)點(diǎn)集合A+(u)和上鄰接結(jié)點(diǎn)集合A-(u)定義如下。

定義1對(duì)于行Ri中的每個(gè)無錯(cuò)結(jié)點(diǎn)，有

1)A+(u)={v:v∈Ri+1，v為無錯(cuò)結(jié)點(diǎn)，且|col(u)-col(v)|≤1}，1≤i≤m-1。

2)A-(u)={v:v∈Ri-1，v為無錯(cuò)結(jié)點(diǎn)，且|col(u)-col(v)|≤1}，2≤i≤m。

3)對(duì)于任意的v∈A+(u)(A-(u))，當(dāng)col(u)-col(v)=-1時(shí)，v被稱為u的左下(上)鄰接結(jié)點(diǎn)；當(dāng)col(u)-col(v)=0時(shí)，v被稱為u的中下(上)鄰接結(jié)點(diǎn)；當(dāng)col(u)-col(v)=1時(shí)，稱v為u的右下(上)鄰接結(jié)點(diǎn)。

根據(jù)使用的開關(guān)數(shù)量，分為2種類型的鏈接，即短鏈接和長(zhǎng)鏈接。若用一個(gè)開關(guān)來鏈接相鄰處理單元，稱為短鏈接，而其他使用2個(gè)開關(guān)相鏈接的，稱之為長(zhǎng)鏈接。在同等規(guī)模下，目標(biāo)陣列的長(zhǎng)鏈接總數(shù)(number of long interconnects，簡(jiǎn)稱nlis)越少，則系統(tǒng)的耗能就越少。

定義2高性能目標(biāo)陣列(high performance target array，簡(jiǎn)稱HPTA)：長(zhǎng)鏈接總數(shù)最少的最大目標(biāo)陣列(MTA)被稱為高性能目標(biāo)陣列。

1.2 問題描述

研究在行旁路和列重路由約束下高性能目標(biāo)陣列的重構(gòu)問題，且加快求解速度。該問題可形式化描述為：

問題1給定一個(gè)m×n的二維網(wǎng)狀結(jié)構(gòu)的主陣列H，在行旁路和列重路由約束下，在最短時(shí)間內(nèi)尋找一個(gè)m×k的最大規(guī)模目標(biāo)陣列，且該目標(biāo)陣列為高性能目標(biāo)陣列。

2 算法改進(jìn)

2.1 主陣列到網(wǎng)絡(luò)模型的轉(zhuǎn)換

圖2 主陣列的網(wǎng)絡(luò)模型

給定一個(gè)m×n的二維網(wǎng)狀結(jié)構(gòu)的主陣列，R1,R2,…,Rm為主陣列的物理行。為簡(jiǎn)化描述算法，假設(shè)重構(gòu)得到的目標(biāo)陣列包含主陣列的所有物理行。由于主陣列是簡(jiǎn)單且排列整齊的網(wǎng)狀拓?fù)浣Y(jié)構(gòu)，可將主陣列分成多個(gè)層次，主陣列的物理行和層次一一對(duì)應(yīng)。因此，可用一個(gè)分層的有向圖G=(V,E)來表示一個(gè)主陣列，其中：V表示結(jié)點(diǎn)的集合，對(duì)應(yīng)主陣列的無故障處理單元；E表示結(jié)點(diǎn)間有向邊的集合，對(duì)應(yīng)主陣列的可行鏈接。給該有向圖添加一個(gè)s源結(jié)點(diǎn)和t匯結(jié)點(diǎn)，且對(duì)于R1行的每個(gè)無故障結(jié)點(diǎn)u，添加一條從s到u的邊，對(duì)于Rm行的每個(gè)無故障結(jié)點(diǎn)v，添加一條v到t的邊。由此，最終可得到一個(gè)m+2層的有向圖G′=(V,E,s,t)。圖2(a)為由一個(gè)帶2個(gè)故障結(jié)點(diǎn)的4×4主陣列構(gòu)造的有向圖。從圖2(a)可看出，在MTA中每條邏輯列都是一條從s源結(jié)點(diǎn)到t匯結(jié)點(diǎn)路徑(簡(jiǎn)稱s-t路徑)的一部分。文獻(xiàn)[9]詳述了目標(biāo)陣列中邏輯列與s-t路徑的對(duì)應(yīng)關(guān)系，在此不再贅述。因此，在行旁路和列重路由約束下的重構(gòu)HPTA相當(dāng)于在網(wǎng)絡(luò)模型N中以最小的費(fèi)用找到最多條不相交的s-t路徑。為確保每條邊至多屬于一條s-t路徑，將每條邊的容量設(shè)置為1。用c(u,v)表示結(jié)點(diǎn)u到v的費(fèi)用，則可定義c(u,v)=|col(u)-col(v)|，即長(zhǎng)鏈接和短鏈接的成本分別為1和0。為了保證每個(gè)結(jié)點(diǎn)至多屬于一條s-t路徑，ALG16將R2行到Rm-1行的結(jié)點(diǎn)u拆分為u′、u″兩個(gè)子結(jié)點(diǎn)，這2個(gè)子結(jié)點(diǎn)間用一條短鏈接相連，生成一個(gè)2m層的網(wǎng)絡(luò)模型，如圖2(b)所示。

2.2 網(wǎng)絡(luò)流改進(jìn)算法

為了解決問題1，提出一個(gè)帶數(shù)據(jù)結(jié)構(gòu)的新型高效網(wǎng)絡(luò)模型，以減少模型的結(jié)點(diǎn)數(shù)。在新模型的基礎(chǔ)上，提出一種多條最短路徑同時(shí)尋路的網(wǎng)絡(luò)流改進(jìn)算法。帶數(shù)據(jù)結(jié)構(gòu)的新網(wǎng)絡(luò)模型如圖3所示。用高效數(shù)據(jù)結(jié)構(gòu)表示處理單元的目的是減少結(jié)點(diǎn)數(shù)量，從而減少算法的運(yùn)行時(shí)間。這些數(shù)據(jù)結(jié)構(gòu)的含義如下：

int split_first為PE的上半部分；

int split_sec為PE的下半部分；

int weight_first為上半部分的權(quán)值；

int weight_sec為下半部分的權(quán)值；

PE* pre_first為上半部分的前驅(qū)；

PE* pre_sec為下半部分的前驅(qū)。

圖3 帶數(shù)據(jù)結(jié)構(gòu)的新網(wǎng)絡(luò)模型

將一個(gè)結(jié)點(diǎn)看作split_first、split_sec兩個(gè)獨(dú)立的部分，分別表示u結(jié)點(diǎn)的上半部分、下半部分，這2個(gè)變量用于獲取獨(dú)立的最短路徑。用weight_first和weight_sec分別記錄PE上半部分和下半部分的權(quán)值，這2個(gè)變量記錄從起始結(jié)點(diǎn)到當(dāng)前部分的距離，從該距離可知哪部分是在最短路徑上。用w(u)表示結(jié)點(diǎn)u的權(quán)值，在算法中每個(gè)結(jié)點(diǎn)的權(quán)重將使用有序的最小堆，

根據(jù)這些權(quán)值信息，找到相應(yīng)部分的前驅(qū)，并將相應(yīng)的前驅(qū)信息存儲(chǔ)在pre_first和pre_sec中。

算法的整體思路概述如下。

1)在一次迭代中，將第一行中的結(jié)點(diǎn)壓入堆中，彈出權(quán)值最小的結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)。

2)利用dijkstra算法的思想計(jì)算出當(dāng)前結(jié)點(diǎn)左下鄰接結(jié)點(diǎn)和右下鄰接結(jié)點(diǎn)的weight_first和weight_sec值。

3)若這些結(jié)點(diǎn)已在堆中，則將其權(quán)值更新到最小的值；若不在堆中，則直接將其壓入堆。

4)將堆中權(quán)重最小的結(jié)點(diǎn)視為下一個(gè)當(dāng)前結(jié)點(diǎn)，并重復(fù)步驟2)的操作。

在每個(gè)迭代過程中，算法會(huì)將每個(gè)結(jié)點(diǎn)相應(yīng)部分的前驅(qū)信息存儲(chǔ)在pre_first和pre_sec中。經(jīng)過一次迭代后，根據(jù)這些前驅(qū)信息從最后一行回溯到第一行，可以同時(shí)找到多條最短的路徑，然后更新這些最短路徑的流，把這些路徑上的結(jié)點(diǎn)標(biāo)為已用。最后，重置每個(gè)結(jié)點(diǎn)的權(quán)值和前驅(qū)信息，并重復(fù)上述過程，直到主陣列中不能找出路徑為止。流的數(shù)量和總費(fèi)用分別等于邏輯列的最大數(shù)量和目標(biāo)陣列的長(zhǎng)鏈接總數(shù)。

該算法命名為ACCFLOW(acceleration of flow algorithm)，偽代碼如算法1所示，其中：heap表示堆；curt表示當(dāng)前遍歷結(jié)點(diǎn)。

算法1ACCFLOW

輸入：m×n的主陣列；

輸出：m×k的高性能目標(biāo)陣列。

1)根據(jù)主陣列，建立帶數(shù)據(jù)結(jié)構(gòu)的新網(wǎng)絡(luò)模型。

2)遍歷每個(gè)結(jié)點(diǎn)，并計(jì)算每個(gè)結(jié)點(diǎn)相應(yīng)部分的權(quán)值。根據(jù)這些權(quán)值，記錄每個(gè)結(jié)點(diǎn)的前驅(qū)信息。

while 還有路徑存在 do

for nodeu∈第1行 do

heap.push(u)；

for heap不空 do

curt=heap.pop()；

計(jì)算A+(curt)中結(jié)點(diǎn)的權(quán)值；

將A+(curt)中的結(jié)點(diǎn)壓入堆；

更新相應(yīng)結(jié)點(diǎn)的前驅(qū)信息。

3)根據(jù)前驅(qū)信息，從最后一行回溯到第一行，同時(shí)找到多條最短路徑，并更新這些路徑上的流，將這些路徑上的結(jié)點(diǎn)標(biāo)記為已使用。

3 仿真實(shí)驗(yàn)與分析

ACCFLOW用C++語言實(shí)現(xiàn)，ALG16用LEMON[10]庫(kù)中的Suurballe算法實(shí)現(xiàn)，兩者的實(shí)驗(yàn)條件相同。程序的運(yùn)行配置為i5 4590 3.30 GHz的CPU，6 GiB的內(nèi)存，操作系統(tǒng)為centos 7。

圖4為ACCFLOW與ALG16的模型結(jié)點(diǎn)數(shù)量對(duì)比。網(wǎng)絡(luò)模型的規(guī)模大小對(duì)重構(gòu)的時(shí)間有較大影響。圖4中的每個(gè)主陣列上的錯(cuò)誤率為1%。在不同規(guī)模的主陣列中，ALG16模型的結(jié)點(diǎn)個(gè)數(shù)分別為1 966、4 468、7 987、12 515，而ACCFLOW模型的結(jié)點(diǎn)個(gè)數(shù)分別為1 014、2 281、4 056、6 336。很顯然，與ALG16模型相比，ACCFLOW網(wǎng)絡(luò)模型可在很大程度上減少網(wǎng)絡(luò)模型的結(jié)點(diǎn)數(shù)。

圖4 ACCFLOW和ALG16模型結(jié)點(diǎn)個(gè)數(shù)對(duì)比

表1為ACCFLOW與ALG16進(jìn)行比較的實(shí)驗(yàn)結(jié)果。從表1可看出，兩者均可獲得相同大小的高性能目標(biāo)陣列，而ACCFLOW的運(yùn)行時(shí)間更少。如在一個(gè)規(guī)模48×48故障率為0.1%的主陣列上，ALG16運(yùn)行時(shí)間為4.68 ms，而ACCFLOW運(yùn)行時(shí)間為0.65 ms，提高了86.11%；在64×64故障率為5%的主陣列上，ALG16運(yùn)行時(shí)為20.70 ms，ACCFLOW運(yùn)行時(shí)間為9.39 ms，提高了54.64%。

表1 算法ACCFLOW和ALG16的性能比較

4 結(jié)束語

在網(wǎng)絡(luò)流算法的基礎(chǔ)上，提出了一種快速構(gòu)造高性能子陣列的有效方法。首先，提出一種帶數(shù)據(jù)結(jié)構(gòu)的新網(wǎng)絡(luò)模型，很大程度上減少了結(jié)點(diǎn)個(gè)數(shù)；其次，在新模型基礎(chǔ)上，提出了可同時(shí)找出多條最短路徑的算法，從而減少重構(gòu)時(shí)間。仿真實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的算法相比，該算法可有效減少運(yùn)行時(shí)間，提高重構(gòu)速度。本研究未考慮中下鄰接結(jié)點(diǎn)的特殊性對(duì)算法運(yùn)行時(shí)間的影響，下一步將在考慮中下鄰接結(jié)點(diǎn)的特殊性的前提下，進(jìn)一步提高高性能子陣列的重構(gòu)速度。