基于最短長(zhǎng)鏈接優(yōu)先選擇的VLSI陣列重構(gòu)算法

莫福浩, 錢俊彥

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

隨著超大規(guī)模集成(VLSI)技術(shù)和晶圓規(guī)模集成(WSI)技術(shù)的發(fā)展,集成系統(tǒng)得以在芯片上構(gòu)建。然而,隨著VLSI陣列中處理單元(PE)密度的增加,VLSI陣列發(fā)生故障的概率也隨之增加,從而導(dǎo)致處理器的計(jì)算能力和穩(wěn)定性受到影響,進(jìn)而影響整個(gè)集成系統(tǒng)的正常工作。因此,需要采用容錯(cuò)技術(shù)對(duì)陣列進(jìn)行重構(gòu)來提高陣列的可靠性。

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的VLSI重構(gòu)技術(shù)主要有冗余法和降階法[1]2種。在冗余法中,集成系統(tǒng)存在部分備用的處理單元,當(dāng)系統(tǒng)中出現(xiàn)故障處理單元時(shí),可用備用的處理單元對(duì)故障的處理單元進(jìn)行替換;在降階法中,系統(tǒng)的元件均以統(tǒng)一的方式進(jìn)行處理,無額外的備用元件,這種方法使用陣列中盡可能多的無故障處理單元來重構(gòu)目標(biāo)陣列,從而提高無故障處理單元的使用效率。

在過去的幾十年間,二維處理器陣列的重構(gòu)策略被廣泛研究。Kuo等[2]提出了二維處理器陣列下3種路由重構(gòu)方案:1)行、列旁路;2)行旁路和列重路由;3)行、列重路由,同時(shí)證明了陣列的重構(gòu)問題是NP完全問題。Low等[3]用GCR算法構(gòu)建包含所選行的最大目標(biāo)陣列?；谄暇W(wǎng)絡(luò)陣列,Xiang等[4]提出了一種新的用于全網(wǎng)單播組播核心測(cè)試的傳輸容錯(cuò)路由算法,并基于重疊虛擬網(wǎng)絡(luò)策略,提出了片上網(wǎng)絡(luò)無死鎖自適應(yīng)路由方案;此外,Xiang等[5]提出了一種高性能自適應(yīng)路由策略,有效降低了芯片網(wǎng)絡(luò)的功耗;基于重復(fù)轉(zhuǎn)向模型,Cai等[6]提出了基于無死鎖自適應(yīng)方案的三維片上網(wǎng)絡(luò)路由算法。重構(gòu)方案主要從時(shí)間、規(guī)模、內(nèi)部鏈接長(zhǎng)度等方面對(duì)陣列進(jìn)行優(yōu)化。在降低陣列重構(gòu)時(shí)間方面,Wu等[7]用并行算法減少陣列的構(gòu)建時(shí)間;Qian等[8]提出了一種智能搜索算法,有效提升了陣列的重構(gòu)效率;Qian等[9]提出了一種可滿足最大功率效率VLSI陣列重構(gòu)的有效方法。在減少陣列長(zhǎng)連接方面,Srikanthan等[10]通過重構(gòu)緊耦合目標(biāo)陣列優(yōu)化了陣列的長(zhǎng)連接;肖漢鵬等[11]設(shè)計(jì)了緊耦合陣列的整數(shù)規(guī)劃模型;Qian等[12]提出了一種構(gòu)造高性能VLSI子陣列的有效多重最短增廣路徑算法;黃弼勝等[13]利用網(wǎng)絡(luò)流模型減少陣列的連接長(zhǎng)度。在擴(kuò)大陣列規(guī)模方面,王意萍等[14]基于整數(shù)規(guī)劃思想獲取了最大規(guī)模陣列;Qian等[15]在行和列重路由方案下重構(gòu)了VLSI子陣列的數(shù)學(xué)模型;Ding等[16]提出了在行和列重路由下重構(gòu)二維網(wǎng)格連接VLSI子陣列的靈活方案;Qian等[17-18]利用網(wǎng)絡(luò)流算法對(duì)陣列進(jìn)行優(yōu)化,并提出了一種新的算法,擴(kuò)大了陣列的規(guī)模。白章順等[19]提出了一種容錯(cuò)處理器陣列的重構(gòu)抽象模型;胡佳等[20]提出了一種高性能陣列重構(gòu)的SAT 描述模型;Wu等[21]將陣列的研究從二維陣列向三維陣列延伸;Jiang等[22]提出了一種高效的重構(gòu)算法,降低了三維陣列中的連接長(zhǎng)度;Jiang等[23]在取消限制補(bǔ)償距離的條件下提出的FLX算法進(jìn)一步擴(kuò)大了獲取的陣列規(guī)模,并在FLX 算法的基礎(chǔ)上,基于分治策略的思想,提出了RIL算法,減少了陣列中的長(zhǎng)鏈接數(shù)。然而,由于RIL算法在重構(gòu)邏輯列的過程中需要對(duì)局部區(qū)域內(nèi)所有的節(jié)點(diǎn)進(jìn)行訪問,在一定程度上影響了陣列的重構(gòu)時(shí)間,降低了重構(gòu)效率。因此,為了減少構(gòu)建陣列過程中對(duì)節(jié)點(diǎn)的訪問數(shù),加快陣列的重構(gòu)速度,在RIL算法的基礎(chǔ)上,提出了一種基于最短長(zhǎng)鏈接優(yōu)先選擇原則的重構(gòu)(acceleration of RIL,簡(jiǎn)稱ACRIL)算法。

1 二維陣列結(jié)構(gòu)與問題描述

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

在二維VLSI陣列中,制造產(chǎn)生的原始陣列用H表示,陣列大小為m×n,其中m、n分別為原始陣列的行數(shù)和列數(shù)。假設(shè)p為原始陣列的故障密度,0≤p≤1,則原始陣列中出現(xiàn)故障的處理單元的個(gè)數(shù)N表示為N=(1-p)×m×n。故障的處理單元表示不能對(duì)數(shù)據(jù)進(jìn)行處理或者從其他處理單元獲取數(shù)據(jù)的處理單元。原始陣列經(jīng)過重新配置后獲得的陣列稱為邏輯陣列,用T表示,陣列大小為m′×n′(m′≤m,n′≤n),邏輯陣列中不包含故障的處理單元。原始陣列和邏輯陣列中的行(列)分別稱為物理行(列)和邏輯行(列)。原始陣列的物理結(jié)構(gòu)如圖1所示。

圖1 VLSI陣列體系結(jié)構(gòu)

每個(gè)開關(guān)有4種鏈路狀態(tài)。每個(gè)處理單元都可通過改變路由開關(guān)的鏈接狀態(tài)來改變處理單元之間的連接方式。ei,j、e′i,j分別為物理陣列、邏輯陣列中處于位置(i,j)的處理單元,其中i為處理單元的行號(hào),j為處理單元的列號(hào)。原始陣列有2種基本的重構(gòu)方案,分別是行旁路方案和列重路由方案。在行旁路方案中,ei,j-1可直接通過改變內(nèi)部開關(guān)連接狀態(tài),繞過故障的處理單元ei,j,直接與ei,j+1相連,同理,列旁路方案的定義與之類似。在列重路由方案中,ei+1,j為故障處理單元,可通過外部開關(guān)直接連接到ei,j′,其中j-j′＜d,d為補(bǔ)償距離,通常限制為1,從而能夠有效保證硬件實(shí)現(xiàn)低功耗。同理,行重路由方案的定義與之類似。

根據(jù)補(bǔ)償距離的定義,每個(gè)處理單元的上相鄰節(jié)點(diǎn)集合和下相鄰節(jié)點(diǎn)集合分別記為A-(u)、A+(u),且定義如下:

定義1 對(duì)于行中的每個(gè)無故障處理單元,

1)A-(u)={v:v∈Ri-1,v為無故障處理單元,且col(u)-col(v)≤1},2≤i≤m。

2)A+(u)={v:v∈Ri+1,v為無故障處理單元,且col(u)-col(v)≤1},1≤i≤m-1。

3)對(duì)于任意的v∈A+(u)(A-(u)),當(dāng)col(u)-col(v)=-1時(shí),v稱為u的左下(上)鄰接處理單元;當(dāng)col(u)-col(v)=0時(shí),v稱為u的中下(上)鄰接處理單元;當(dāng)col(u)-col(v)=1時(shí),v稱為u的右下(上)鄰接處理單元。

一個(gè)二維邏輯陣列有6種可能的鏈路方式,根據(jù)鏈路使用的開關(guān)數(shù),可分為短連接與長(zhǎng)連接。只使用一個(gè)開關(guān)來連接目標(biāo)陣列中的處理單元的鏈路方式稱為短連接,而使用2 個(gè)開關(guān)的鏈路方式稱為長(zhǎng)連接。

定義2 長(zhǎng)連接數(shù)量最少的陣列稱為高性能邏輯陣列(HPTA)。

1.2 問題描述

在行旁路和列重路由條件下對(duì)二維處理器陣列的重構(gòu)問題進(jìn)行研究,研究?jī)?nèi)容包括尋找高性能的無故障目標(biāo)陣列。

問題1 給定一個(gè)規(guī)模大小為m×n的帶有故障節(jié)點(diǎn)的網(wǎng)狀連接處理器陣列,找到長(zhǎng)鏈接數(shù)目最小的無故障高性能目標(biāo)陣列。

2 ACRIL算法介紹

RIL算法通過運(yùn)用分治策略的思想解決了不限制補(bǔ)償距離條件下的問題1。為了優(yōu)化RIL算法的效率,采用ACRIL算法,通過減少對(duì)無故障節(jié)點(diǎn)的訪問次數(shù),重構(gòu)局部?jī)?yōu)化邏輯列,以降低邏輯陣列的重構(gòu)時(shí)間。

ACRIL算法的求解結(jié)果如圖2所示。該算法主要分為3個(gè)子過程:Up_Process表示第一個(gè)公共處理單元到第一行的子邏輯列求解過程;Down_Process表示最后一個(gè)公共處理單元到最后一行的子邏輯列求解過程;Shest_Process表示公共處理單元之間的子邏輯列求解過程。圖2中的數(shù)字表示處理單元的長(zhǎng)連接。

圖2 ACRIL算法的求解結(jié)果

ACRIL算法的整體思路如下:

1)在一次迭代過程中,找到左右2條邏輯列的交點(diǎn),并將交點(diǎn)放入交點(diǎn)集合中。

2)利用智能搜索算法分別求解Up_Process、Down_Process及Shest_Process三個(gè)子過程,每個(gè)子過程獲得一段路徑。

3)將這3個(gè)子過程獲得的路徑進(jìn)行合并,得到一條完整的路徑,此路徑即是所要求的一條邏輯列。

4)將新獲取的邏輯列作為新的邊界,繼續(xù)重構(gòu)邏輯列,重復(fù)1)、2)、3)過程。

算法1 ACRIL算法

輸入:m×n的原始陣列。輸出:m×k的目標(biāo)陣列。1)根據(jù)主陣列,依次分別從左至右和從右至左的方式重構(gòu)邏輯列。

2)直到從2個(gè)方向構(gòu)建的邏輯列連接到相同的節(jié)點(diǎn),形成公共區(qū)域。在邏輯列的公共區(qū)域構(gòu)建具有最短長(zhǎng)連接的邏輯列。

將3個(gè)部分獲得的路徑合并形成一條完整的路徑P=P1∪P2∪P3。

3)以新構(gòu)建的邏輯列作為新的邊界,重復(fù)步驟1)、2),直到所有的邏輯列構(gòu)建完畢。

Shest_Process子過程主要運(yùn)用啟發(fā)式搜索思想進(jìn)行求解,其求解過程描述如下:

輸入:2個(gè)公共節(jié)點(diǎn)S、T。

輸出:S、T之間的一段路徑P。

1)設(shè)置2個(gè)列表,分別為開放列表與關(guān)閉列表。

2)遍歷節(jié)點(diǎn),計(jì)算當(dāng)前節(jié)點(diǎn)的權(quán)值,根據(jù)情況將節(jié)點(diǎn)放入相應(yīng)的列表中;當(dāng)節(jié)點(diǎn)已位于開放列表時(shí),重新計(jì)算權(quán)值。

3)當(dāng)開放列表為空時(shí),表示子過程執(zhí)行完畢。求解子過程的偽代碼如下:

計(jì)算u的權(quán)值,將u放入開放列表;

從下鄰接集合中去除u。

Up_Process和Down_Process子過程的求解方式與子過程Shest_Process類似。

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

為驗(yàn)證ACRIL算法的有效性,用C++語言實(shí)現(xiàn)了該算法,還原了現(xiàn)有的重構(gòu)算法RIL,并將2種重構(gòu)算法進(jìn)行對(duì)比。為保證實(shí)驗(yàn)數(shù)據(jù)具有可比性和可靠性,2種重構(gòu)算法均在相同的實(shí)驗(yàn)環(huán)境下運(yùn)行。執(zhí)行程序的實(shí)驗(yàn)配置環(huán)境為Inter?CoreTM3.10 GHz 的 CPU 和8 GiB RAM,操 作 系 統(tǒng) 為Windows 10。

RIL算法與ACRIL 算法的訪問節(jié)點(diǎn)數(shù)的對(duì)比如圖3所示。圖3中,在64×64規(guī)模下的原始陣列的錯(cuò)誤率分別設(shè)置為1%、5%、10%、15%。從圖3可看出,在錯(cuò)誤率為1%的原始陣列中,RIL算法對(duì)陣列中的節(jié)點(diǎn)訪問數(shù)為5 091,而ACRIL算法對(duì)陣列中的節(jié)點(diǎn)訪問數(shù)為3 989;在錯(cuò)誤率為10%的原始陣列中,RIL算法對(duì)陣列中的節(jié)點(diǎn)訪問數(shù)為5 191,而ACRIL算法對(duì)陣列中的節(jié)點(diǎn)訪問數(shù)為3 573。2種重構(gòu)算法的實(shí)驗(yàn)數(shù)據(jù)比較結(jié)果表明,相較于現(xiàn)有的重構(gòu)算法RIL,ACRIL算法能在一定程度上減少陣列在重構(gòu)邏輯列的過程中對(duì)節(jié)點(diǎn)的訪問數(shù),提高陣列的重構(gòu)效率。

圖3 RIL與ACRIL算法的訪問節(jié)點(diǎn)數(shù)對(duì)比

RIL算法與ACRIL算法性能指標(biāo)如表1所示。從表1可看出,兩者在相同錯(cuò)誤率條件下都可獲取相同規(guī)模的目標(biāo)邏輯陣列,且相比于RIL算法,ACRIL算法的陣列重構(gòu)時(shí)間更短,這表明陣列從故障狀態(tài)恢復(fù)的效率更高。例如,在錯(cuò)誤率為1%、規(guī)模為32×32的原始陣列中,RIL算法的重構(gòu)時(shí)間為674 ms,而ACRIL算法的重構(gòu)時(shí)間為574 ms,重構(gòu)效率提高了14.83%;在錯(cuò)誤率為5%,規(guī)模為48×48的原始陣列中,RIL算法的重構(gòu)時(shí)間為956 ms,而ACRIL算法的重構(gòu)時(shí)間為821 ms,重構(gòu)效率提高了14.13%。這表明ACRIL算法的運(yùn)行性能明顯優(yōu)于RIL算法。

表1 RIL與ACRIL算法的性能指標(biāo)

4 結(jié)束語

基于現(xiàn)有的重構(gòu)算法,提出了一種通過減少處理單元的訪問次數(shù),進(jìn)一步提高原始陣列重構(gòu)速度的方案。實(shí)驗(yàn)結(jié)果表明,與現(xiàn)有的重構(gòu)算法相比,該算法顯著減少了處理單元的訪問次數(shù),減少了重構(gòu)時(shí)間,降低了運(yùn)行時(shí)的性能開銷。本研究未考慮在構(gòu)建陣列過程中邏輯列的選擇對(duì)陣列規(guī)模的影響。今后的研究將著重于考慮新的改進(jìn)算法,為可降階的VLSI陣列的重構(gòu)提供更好的性能優(yōu)化。