基于網絡流的高效VLSI子陣列重構

黃弼勝， 錢俊彥

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

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

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

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

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

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

1.1 陣列結構

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

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

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

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

1.2 問題描述

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

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

2 算法改進

2.1 主陣列到網絡模型的轉換

圖2 主陣列的網絡模型

給定一個m×n的二維網狀結構的主陣列，R1,R2,…,Rm為主陣列的物理行。為簡化描述算法，假設重構得到的目標陣列包含主陣列的所有物理行。由于主陣列是簡單且排列整齊的網狀拓撲結構，可將主陣列分成多個層次，主陣列的物理行和層次一一對應。因此，可用一個分層的有向圖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相當于在網絡模型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層的網絡模型，如圖2(b)所示。

2.2 網絡流改進算法

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

int split_first為PE的上半部分；

int split_sec為PE的下半部分；

int weight_first為上半部分的權值；

int weight_sec為下半部分的權值；

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

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

圖3 帶數據結構的新網絡模型

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

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

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

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

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

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

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

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

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

算法1ACCFLOW

輸入：m×n的主陣列；

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

1)根據主陣列，建立帶數據結構的新網絡模型。

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

while 還有路徑存在 do

for nodeu∈第1行 do

heap.push(u)；

for heap不空 do

curt=heap.pop()；

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

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

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

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

3 仿真實驗與分析

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

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

圖4 ACCFLOW和ALG16模型結點個數對比

表1為ACCFLOW與ALG16進行比較的實驗結果。從表1可看出，兩者均可獲得相同大小的高性能目標陣列，而ACCFLOW的運行時間更少。如在一個規模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 結束語

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