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

黃弼勝， 錢俊彥

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

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

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

基于網(wǎng)絡拓撲分布的VLSI陣列，Kuo等[3]提出了3種不同的降階重構路由方案，并證明了在這些不同的路由方案下的重構問題是NP完全問題。Low等[4]提出了一種最優(yōu)貪婪算法，可在線性時間內構造最大目標陣列(maximum target array，簡稱MTA)。其他一些重要的降階法分別在文獻[5-6]有詳細的介紹。

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

1 處理器陣列結構與問題描述

1.1 陣列結構

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

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

圖1 處理器陣列體系結構

設col(u)為u的列序號，基于補償距離的限制，將u的下鄰接結點集合A+(u)和上鄰接結點集合A-(u)定義如下。

定義1對于行Ri中的每個無錯結點，有

1)A+(u)={v:v∈Ri+1，v為無錯結點，且|col(u)-col(v)|≤1}，1≤i≤m-1。

2)A-(u)={v:v∈Ri-1，v為無錯結點，且|col(u)-col(v)|≤1}，2≤i≤m。

3)對于任意的v∈A+(u)(A-(u))，當col(u)-col(v)=-1時，v被稱為u的左下(上)鄰接結點；當col(u)-col(v)=0時，v被稱為u的中下(上)鄰接結點；當col(u)-col(v)=1時，稱v為u的右下(上)鄰接結點。

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

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

1.2 問題描述

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

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

2 算法改進

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

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

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

2.2 網(wǎng)絡流改進算法

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

int split_first為PE的上半部分；

int split_sec為PE的下半部分；

int weight_first為上半部分的權值；

int weight_sec為下半部分的權值；

PE* pre_first為上半部分的前驅；

PE* pre_sec為下半部分的前驅。

圖3 帶數(shù)據(jù)結構的新網(wǎng)絡模型

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

根據(jù)這些權值信息，找到相應部分的前驅，并將相應的前驅信息存儲在pre_first和pre_sec中。

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

1)在一次迭代中，將第一行中的結點壓入堆中，彈出權值最小的結點作為當前結點。

2)利用dijkstra算法的思想計算出當前結點左下鄰接結點和右下鄰接結點的weight_first和weight_sec值。

3)若這些結點已在堆中，則將其權值更新到最小的值；若不在堆中，則直接將其壓入堆。

4)將堆中權重最小的結點視為下一個當前結點，并重復步驟2)的操作。

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

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

算法1ACCFLOW

輸入：m×n的主陣列；

輸出：m×k的高性能目標陣列。

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

2)遍歷每個結點，并計算每個結點相應部分的權值。根據(jù)這些權值，記錄每個結點的前驅信息。

while 還有路徑存在 do

for nodeu∈第1行 do

heap.push(u)；

for heap不空 do

curt=heap.pop()；

計算A+(curt)中結點的權值；

將A+(curt)中的結點壓入堆；

更新相應結點的前驅信息。

3)根據(jù)前驅信息，從最后一行回溯到第一行，同時找到多條最短路徑，并更新這些路徑上的流，將這些路徑上的結點標記為已使用。

3 仿真實驗與分析

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

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

圖4 ACCFLOW和ALG16模型結點個數(shù)對比

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

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

4 結束語

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