方 冉， 沈麗娜

(安徽工商職業(yè)學(xué)院 應(yīng)用工程學(xué)院,安徽 合肥 231131)

引 言

粗粒度可重構(gòu)體系結(jié)構(gòu)CGRA(coarse grained reconfigurable architectures)在循環(huán)內(nèi)核處理層面具有較高的執(zhí)行效率和低的功耗消費(fèi)，傳統(tǒng)單核架構(gòu)在處理計(jì)算密集型循環(huán)任務(wù)時(shí)效率低下，在這樣的背景下，可重構(gòu)計(jì)算模式被提出，可重構(gòu)計(jì)算目前是國(guó)際研究前沿和熱點(diǎn)，近三年相關(guān)典型的研究列舉如下：文獻(xiàn)[1]對(duì)可重構(gòu)計(jì)算系統(tǒng)的數(shù)據(jù)流圖執(zhí)行進(jìn)行了研究，該文針對(duì)多緩沖和控制開(kāi)銷(xiāo)問(wèn)題，提出了一種可重構(gòu)計(jì)算系統(tǒng)優(yōu)化數(shù)據(jù)流圖執(zhí)行方法，通過(guò)該種方法，獲得了計(jì)算任務(wù)3.4倍的加速[1]。文獻(xiàn)[2]針對(duì)芯片在指令存儲(chǔ)器上消耗能量大的問(wèn)題，給出了一種基于代碼的統(tǒng)計(jì)分析方法，同時(shí)提出將配置存儲(chǔ)器重組為單獨(dú)分區(qū)的硬件/軟件協(xié)同設(shè)計(jì)方法，實(shí)驗(yàn)結(jié)果表明指令解碼邏輯所消耗的能量減少了70%[2]。文獻(xiàn)[3]對(duì)可重構(gòu)計(jì)算系統(tǒng)的容錯(cuò)問(wèn)題進(jìn)行了研究，基于三重模塊冗余和編碼技術(shù)的錯(cuò)誤檢測(cè)和糾正理論，該文提出了一個(gè)容錯(cuò)模型，實(shí)驗(yàn)結(jié)果表明任務(wù)劃分執(zhí)行效率制約了容錯(cuò)模塊恢復(fù)時(shí)間[3]。文獻(xiàn)[4]提出了兩種減少可重構(gòu)系統(tǒng)能量消費(fèi)的方法，一種是減少配置切換單元的數(shù)量；另外一種是減少配置存儲(chǔ)器的容量[4]。文獻(xiàn)[5]利用程序轉(zhuǎn)換來(lái)獲得能量和模型性能的權(quán)衡，通過(guò)一組信號(hào)處理和代數(shù)內(nèi)核基準(zhǔn)測(cè)試表明，該方法獲得了50%到80%的資源利用率[5]。文獻(xiàn)[6]提出了一種流處理CGRA可重構(gòu)系統(tǒng)，該系統(tǒng)采用SMIC標(biāo)準(zhǔn)55納米單元技術(shù)，基于7個(gè)典型算法，在450MHz的頻率下，流處理CGRA平均功耗消費(fèi)僅為0.84w[6]。文獻(xiàn)[7]針對(duì)并行數(shù)據(jù)計(jì)算時(shí)需要多次訪存的問(wèn)題，提出基于一種CGRA多存儲(chǔ)器架構(gòu)，通過(guò)循環(huán)基準(zhǔn)測(cè)試，相對(duì)于傳統(tǒng)CGRA架構(gòu)，獲得了較好的計(jì)算性能改進(jìn)[7]。文獻(xiàn)[8]提出了一種圖最小化映射方法[8]。文獻(xiàn)[9]給出了粗粒度可重構(gòu)計(jì)算系統(tǒng)的量化評(píng)估指標(biāo)體系，為可重構(gòu)計(jì)算系統(tǒng)的量化評(píng)估獲得了依據(jù)，效果較好[9]。

但是上述工作均是對(duì)同構(gòu)可重構(gòu)計(jì)算系統(tǒng)進(jìn)行的研究，均沒(méi)有對(duì)異構(gòu)可重構(gòu)系統(tǒng)進(jìn)行設(shè)計(jì)和同異構(gòu)可重構(gòu)系統(tǒng)進(jìn)行運(yùn)算分析。如何設(shè)計(jì)一種異構(gòu)可重構(gòu)計(jì)算系統(tǒng)？如何結(jié)合計(jì)算模型來(lái)評(píng)估異構(gòu)可重構(gòu)計(jì)算系統(tǒng)顯得極為重要。本文對(duì)這一問(wèn)題展開(kāi)研究。

1 異構(gòu)可重構(gòu)計(jì)算系統(tǒng)設(shè)計(jì)與相關(guān)定義

為了便于問(wèn)題研究，下面設(shè)計(jì)了一種異構(gòu)可重構(gòu)計(jì)算系統(tǒng)，具體如圖1所示：

圖1 異構(gòu)可重構(gòu)計(jì)算系統(tǒng)

圖2 同構(gòu)可重構(gòu)處理單元陣列

異構(gòu)可重構(gòu)計(jì)算系統(tǒng)HRCS(heterogeneous reconfigurable computing system)主要包括主處理器、主存儲(chǔ)器，局部存儲(chǔ)器，配置控制與存儲(chǔ)器，異構(gòu)可重構(gòu)處理單元PE(processing element)陣列(說(shuō)明：圖1中PE1類(lèi)型的單元在處理乘法運(yùn)算時(shí)無(wú)需配置，處理其他運(yùn)算均需要配置，PE2類(lèi)型的單元可以處理所有的算術(shù)邏輯運(yùn)算)等組件，圖形圖像等計(jì)算密集型任務(wù)包含大量矩陣運(yùn)算，其運(yùn)算主要乘法和加法的運(yùn)算，相比較二維無(wú)跳變點(diǎn)點(diǎn)近鄰互連的mesh結(jié)構(gòu)而言，HRCS具有如下特點(diǎn)：(1)矩陣運(yùn)算中的乘法運(yùn)算映射到固定處理單元上，目的是減少重復(fù)配置成本；(2)根據(jù)設(shè)計(jì)映射調(diào)度算法可以實(shí)現(xiàn)行無(wú)依賴并行執(zhí)行。

本文研究的兩個(gè)前提：(1)針對(duì)矩陣及類(lèi)似的運(yùn)算。(2)計(jì)算平臺(tái)采用網(wǎng)格型異構(gòu)可重構(gòu)計(jì)算系統(tǒng)。

本文的主要貢獻(xiàn)列舉如下：

(1)設(shè)計(jì)了一種網(wǎng)格型異構(gòu)可重構(gòu)計(jì)算結(jié)構(gòu)，同時(shí)提出了網(wǎng)格加節(jié)點(diǎn)GAM(grid add-node mapping)和網(wǎng)格不加節(jié)點(diǎn)映射GNM(grid no-add-node mapping)兩種任務(wù)映射算法，相比較網(wǎng)格型同構(gòu)可重構(gòu)計(jì)算結(jié)構(gòu)，兩種算法在配置成本層面均有減少。

(2)針對(duì)網(wǎng)格型異構(gòu)結(jié)構(gòu)，對(duì)比GAM和GNM兩種算法，結(jié)果發(fā)現(xiàn)GAM算法在N1、N2、CCON、TTOTAL等參數(shù)方面要優(yōu)于GNM。

本文要用到的相關(guān)定義列舉如下：

定義1：可重構(gòu)異構(gòu)處理單元陣列RHPEA(reconfigurable heterogeneous processing element array)：設(shè)待處理的任務(wù)集合V={v1,v2,…,vn}，V=V1∪V2，其中集合V1屬于計(jì)算密集型任務(wù)常用的運(yùn)算一種類(lèi)型集合，如矩陣運(yùn)算的乘法運(yùn)算等；剩余其他運(yùn)算V2=V-V1；RHPEA的特征是：用PE1處理集合V1類(lèi)型的計(jì)算并且不需要配置，但是處理V2類(lèi)型等運(yùn)算需要配置；用PE2可處理V2類(lèi)型或V1∪V2類(lèi)型的運(yùn)算，每處理一種運(yùn)算均需要配置，RHPEA就是指包含兩類(lèi)或以上的處理單元(如圖1中的PE1和PE2)的陣列。

定義2：可重構(gòu)同構(gòu)處理單元陣列RIPEA(reconfigurable isomorphic processing element array)：設(shè)待處理的任務(wù)集合V={v1,v2,…,vn}，V=V1∪V2，每個(gè)PE均可以處理集合V中所有的運(yùn)算，每處理一種運(yùn)算均需要配置，處理單元陣列中的每個(gè)PE均具有相同的功能，這樣的陣列被稱為RIPEA。

定義3：RHPEA配置成本弱化：RHPEA中有一類(lèi)執(zhí)行單元專(zhuān)門(mén)執(zhí)行有規(guī)律頻繁出現(xiàn)的次數(shù)較多某種運(yùn)算，如矩陣計(jì)算中的乘法運(yùn)算，通過(guò)某一算法把頻繁出現(xiàn)的某種運(yùn)算任務(wù)調(diào)度到專(zhuān)門(mén)的PE，這樣PE就不需要配置，直接執(zhí)行，這樣就會(huì)節(jié)省一定數(shù)量的重復(fù)配置成本，這種現(xiàn)象稱為RHPEA配置成本的弱化，但是RIPEA每個(gè)單元在運(yùn)算前均需要配置。

定義4：網(wǎng)格型CGRA行無(wú)依賴映射：設(shè)待處理的任務(wù)集合V={v1,v2,…,vn}，假設(shè)成功映射到CGRA中陣列后的同一行某一任意任務(wù)節(jié)點(diǎn)vi和vj，i，j∈[1，n]，vi和vj沒(méi)有前驅(qū)和后繼的依賴關(guān)系，這種情況稱為網(wǎng)格型CGRA的行無(wú)依賴映射，行無(wú)依賴映射可以獲得行節(jié)點(diǎn)按塊運(yùn)行的并行度的最大化。

定義5：網(wǎng)格型HRCS量化指標(biāo)體系：本文用到的量化指標(biāo)體系為配置時(shí)間CCON、非原始輸入次數(shù)N1、非原始輸出次數(shù)N2、原始輸入次數(shù)Norg1、原始輸出次數(shù)Norg2、劃分塊數(shù)M、跨層時(shí)延IID(由于網(wǎng)格型結(jié)構(gòu)不允許跨層映射，所以本文的IID=0)、計(jì)算任務(wù)的執(zhí)行時(shí)延SSD，本文計(jì)算任務(wù)的執(zhí)行總時(shí)延TTOTAL=CCON+N1+Norg1+N2+Norg2+SSD，具體見(jiàn)文獻(xiàn)[9]，限于篇幅，不再累述。

本文研究有兩個(gè)前提：(1)RHPEA和RIPEA的陣列每塊加少量過(guò)渡路由節(jié)點(diǎn)的個(gè)數(shù)為2，路由節(jié)點(diǎn)可表示為ri，其中i∈[1,n]。(2)每塊可重構(gòu)陣列固定配置時(shí)間等參數(shù)與文獻(xiàn)[9]一致。

2 二維HRCS可調(diào)度性分析

2.1 二維HRCS特征分析

二維HRCS具有以下特征：(1)屬于片上多核系統(tǒng)，這種結(jié)構(gòu)克服了常用運(yùn)算重復(fù)配置的問(wèn)題，每個(gè)PE單元均可編譯程序，其結(jié)構(gòu)及互連形式如圖1所示。(2)在主處理器的控制下HRCS完成計(jì)算任務(wù)的編譯，主存儲(chǔ)器用來(lái)存儲(chǔ)計(jì)算密集型任務(wù)的最后運(yùn)算結(jié)果，局部存儲(chǔ)器用來(lái)存儲(chǔ)中間的運(yùn)算結(jié)果。(3)配置控制與存儲(chǔ)器作用是用來(lái)生成編譯所用的配置字。

2.2 矩陣運(yùn)算的實(shí)例映射分析

實(shí)例1：設(shè)A為1×4的矩陣，B為4×2的矩陣，矩陣Y=A×B，則

=(i1×i5+i2×i6+i3×i7+i4×i8i1×i9+i2×i10+i3×i11+i4×i12)

(1)

式1的運(yùn)算控制數(shù)據(jù)流圖DFG(data flow graph)如圖3所示：運(yùn)算任務(wù)ai,bi,ci,di,i∈[1,2]均為乘法運(yùn)算，其執(zhí)行時(shí)間為2cycle，任務(wù)ej,fj,gj,j∈[1,2],均為加法運(yùn)算，其執(zhí)行時(shí)間為1cycle。

一個(gè)循環(huán)任務(wù)子圖(見(jiàn)圖3)任務(wù)間的關(guān)系描述見(jiàn)表1，說(shuō)明本文只討論圖形圖像矩陣運(yùn)算中的循環(huán)程序。

基于HRCS平臺(tái)和行無(wú)依賴規(guī)則，采用按網(wǎng)格加節(jié)點(diǎn)映射GAM和網(wǎng)格不加節(jié)點(diǎn)映射GNM兩種方法對(duì)圖3的循環(huán)任務(wù)進(jìn)行了映射。

圖3 兩個(gè)循環(huán)子圖

GAM算法流程：

輸入：循環(huán)任務(wù)圖

輸出：可執(zhí)行任務(wù)坐標(biāo)

硬件約束：二維網(wǎng)格型可重構(gòu)異構(gòu)或同構(gòu)處理單元陣列

Step1輸入數(shù)據(jù)表和硬件約束。

Step2掃描就緒列表獲得就緒的節(jié)點(diǎn)。

表1 循環(huán)任務(wù)圖間順序關(guān)系描述

(1)若是乘法運(yùn)算，映射的起始行是第一行，然后進(jìn)行點(diǎn)點(diǎn)加少量過(guò)渡節(jié)點(diǎn)進(jìn)行行無(wú)依賴映射和列有依賴映射，如第一行放滿就轉(zhuǎn)第2行，依次映射；

(2)若不是乘法運(yùn)算或是乘法運(yùn)算，但第一行放滿了，映射的起始行是第二行，然后進(jìn)行點(diǎn)點(diǎn)加少量過(guò)渡節(jié)點(diǎn)進(jìn)行行無(wú)依賴映射和列有依賴映射，如第二行放滿就轉(zhuǎn)第3行，依次映射。

Step3若任務(wù)點(diǎn)映射沒(méi)有完成轉(zhuǎn)Step2，否則算法結(jié)束。

GNM算法流程：

輸入：循環(huán)任務(wù)圖

輸出：可執(zhí)行任務(wù)坐標(biāo)

硬件約束：二維網(wǎng)格型可重構(gòu)異或同構(gòu)處理單元陣列

Step1輸入數(shù)據(jù)表和硬件約束。

Step2掃描就緒列表獲得就緒的節(jié)點(diǎn)。

(1)若是乘法運(yùn)算，映射的起始行是第一行，然后進(jìn)行點(diǎn)點(diǎn)不加過(guò)渡節(jié)點(diǎn)進(jìn)行行無(wú)依賴映射和列有依賴映射，如第一行放滿就轉(zhuǎn)第2行，依次映射；

(2)若不是乘法運(yùn)算或是乘法運(yùn)算，但第一行放滿了，映射的起始行是第二行，然后進(jìn)行點(diǎn)點(diǎn)不加過(guò)渡節(jié)點(diǎn)進(jìn)行行無(wú)依賴映射和列有依賴映射，如第二行放滿就轉(zhuǎn)第3行，依次映射。

Step3若任務(wù)點(diǎn)映射沒(méi)有完成轉(zhuǎn)Step2，否則算法結(jié)束。

若可重構(gòu)處理單元陣列規(guī)模為2×4，分別采用GNM和GAM兩種算法獲得了圖3的兩個(gè)循環(huán)子圖映射結(jié)果，具體見(jiàn)圖4和圖5。由圖4和圖5可知，若采用異構(gòu)可重構(gòu)陣列RHPEA，第一行是專(zhuān)用，且為乘法運(yùn)算，其組合邏輯電路不需要重復(fù)配置，a1，b1，c1，d1和a2，b2，c2，d2只需要配置一次。故可以節(jié)省4cycle；若采用同構(gòu)可重構(gòu)陣列RIPEA，陣列被重復(fù)使用時(shí)，均需要配置，配置成本為8cycle，從而說(shuō)明異構(gòu)可重構(gòu)陣列RHPEA具有合理性。

(1)

(2)

(3)

(4)

圖4 GNM映射結(jié)果

(1)

(2)

(3)

圖5 GAM映射結(jié)果

圖3的循環(huán)子圖原始輸入Norg1=16，原始輸出Norg2=2，其他參數(shù)的計(jì)算方式如定義5所述。

相比較同構(gòu)RIPEA結(jié)構(gòu)，基于異構(gòu)RHPEA結(jié)構(gòu)GNM和GAM算法，CCON均節(jié)省4cycle，從而說(shuō)明異構(gòu)結(jié)構(gòu)具有合理性。相關(guān)比較見(jiàn)表2。

2.3 一個(gè)4×4矩陣的算例分析

一個(gè)4×4矩陣運(yùn)算展開(kāi)的數(shù)據(jù)流循環(huán)子圖共16個(gè)，原始輸入Norg1=128，原始輸出Norg2=16，若可重構(gòu)處理單元陣列規(guī)模為4×4，基于異構(gòu)RHPEA架構(gòu)分別采用GAM和GNM算法獲得,實(shí)驗(yàn)結(jié)果如表3所述。

表2 RHPEA結(jié)構(gòu)GAM和GNM映射算法比較

基于4×4矩陣運(yùn)算，通過(guò)算法實(shí)驗(yàn)，基于異構(gòu)RHPEA架構(gòu)GNM算法的配置時(shí)間為219cycle，基于同構(gòu)RIPEA架構(gòu)GNM算法的配置時(shí)間為231cycle，節(jié)省12cycle；基于異構(gòu)RHPEA架構(gòu)GAM算法的配置時(shí)間為

228cycle，基于同構(gòu)RIPEA架構(gòu)GAM算法的配置時(shí)間為248cycle，節(jié)省20cycle。由此看出，在節(jié)省配置時(shí)間層面，異構(gòu)RHPEA架構(gòu)較具優(yōu)勢(shì)。

基于異構(gòu)RHPEA結(jié)構(gòu)，可重構(gòu)處理單元陣列規(guī)模為4×4，為了進(jìn)一步驗(yàn)證GAM和GNM算法的優(yōu)劣，本文采用了更為復(fù)雜的例證快速傅立葉變換FFT(fast Fourier transform)4次和8次展開(kāi)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表4和表5所述：

表3 RHPEA結(jié)構(gòu)4×4矩陣運(yùn)算GAM和GNM算法比較

表4 RHPEA結(jié)構(gòu)FFT4運(yùn)算的GAM和GNM算法比較

表5 RHPEA結(jié)構(gòu)FFT8運(yùn)算的GAM和GNM算法比較

分析與小結(jié)：針對(duì)3.2和3.3節(jié)四個(gè)算例，由表2-表5可知，針對(duì)異構(gòu)RHPEA，采用了GAM和GNM兩種任務(wù)映射算法，進(jìn)行定量分析，發(fā)現(xiàn)GAM在N1、N2、CCON、TTOTAL等方面均要優(yōu)于GNM算法，但是GNM的SSD要優(yōu)于GAM算法。

3 結(jié) 語(yǔ)

本文設(shè)計(jì)了一種網(wǎng)格型異構(gòu)可重構(gòu)計(jì)算系統(tǒng)，基于網(wǎng)格加節(jié)點(diǎn)映射GAM算法和網(wǎng)格不加節(jié)點(diǎn)映射GNM算法對(duì)異構(gòu)可重構(gòu)計(jì)算結(jié)構(gòu)進(jìn)行了性能評(píng)估，結(jié)果發(fā)現(xiàn)相比較同構(gòu)網(wǎng)格型可重構(gòu)計(jì)算系統(tǒng)而言，基于一組算例的實(shí)驗(yàn)結(jié)果可知，網(wǎng)格型異構(gòu)可重構(gòu)計(jì)算系統(tǒng)具有一定優(yōu)勢(shì)。就4×4矩陣運(yùn)算而言，GAM和GNM算法分別節(jié)省配置時(shí)間為20cycle和12cycle，同時(shí)對(duì)比了異構(gòu)可重構(gòu)計(jì)算系統(tǒng)的GAM和GNM算法，結(jié)果表明，相比較GNM算法，GAM算法改進(jìn)的百分比為2.72%；基于RHPEA結(jié)構(gòu)，相比較GNM算法，GAM在FFT4和FFT8兩個(gè)較為復(fù)雜的測(cè)試用例，GAM算法改進(jìn)的百分比分別為22.8%和18.8%，從而說(shuō)明了網(wǎng)格型異構(gòu)可重構(gòu)計(jì)算系統(tǒng)下的GAM算法具有可行性。