郭振華,吳艷霞,張國(guó)印,戴 葵
(哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江哈爾濱 150001)
?
面向類仿射型數(shù)組下標(biāo)應(yīng)用的參數(shù)化并行存儲(chǔ)結(jié)構(gòu)模板
郭振華,吳艷霞,張國(guó)印,戴 葵
(哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江哈爾濱 150001)
為了解決目前可重構(gòu)編譯技術(shù)在為類仿射型數(shù)組下標(biāo)應(yīng)用生成循環(huán)流水陣列時(shí),生成的存儲(chǔ)系統(tǒng)對(duì)數(shù)據(jù)并行與重用支持不完善的問題,本文提出了一種參數(shù)化并行存儲(chǔ)結(jié)構(gòu)模板.此模板采用模塊化設(shè)計(jì)思想,根據(jù)數(shù)據(jù)訪存特征生成由多體交叉并行存儲(chǔ)子模塊、單體串行存儲(chǔ)子模塊、RAW Buffer緩存子模塊及Smart Buffer緩存子模塊構(gòu)成的存儲(chǔ)結(jié)構(gòu).為靈活生成存儲(chǔ)結(jié)構(gòu)及充分挖掘數(shù)據(jù)的并行性和重用性,本文采用訪存數(shù)據(jù)依賴圖方法計(jì)算存儲(chǔ)模板的參數(shù)值.和相關(guān)工作相比,根據(jù)本文提出的存儲(chǔ)結(jié)構(gòu)模板生成的硬件,可以在占用較少的硬件資源情況下,獲得較高的硬件執(zhí)行速度.
類仿射數(shù)組下標(biāo);可重構(gòu)編譯;存儲(chǔ)結(jié)構(gòu);數(shù)據(jù)重用;模板
電子學(xué)報(bào)URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.026
目前,一些國(guó)內(nèi)外大學(xué)、科研機(jī)構(gòu)及工業(yè)界針對(duì)循環(huán)流水中的并行存儲(chǔ)結(jié)構(gòu)技術(shù)已經(jīng)進(jìn)行了初步的相關(guān)研究,但是,這些編譯器在為類仿射數(shù)組下標(biāo)的應(yīng)用生成硬件存儲(chǔ)結(jié)構(gòu)時(shí),對(duì)數(shù)據(jù)重用及并行支持的還不夠完善.其中,GarpCC[1]、Nymble[2]、NAPA C[3]只為循環(huán)流水陣列生成了提供數(shù)據(jù)的單體串行存儲(chǔ)結(jié)構(gòu);PACT[4]和SPC[5]沒有考慮循環(huán)流水陣列中數(shù)據(jù)重用問題;CHiMPS[6,7]主要采用多Cache結(jié)構(gòu)提供并行訪問數(shù)據(jù),在提升程序性能的同時(shí)明顯地增加了硬件面積開銷,尤其當(dāng)程序中存在循環(huán)迭代間流依賴時(shí),生成的硬件存儲(chǔ)結(jié)構(gòu)會(huì)出現(xiàn)Cache一致性的問題;Vivado HLS[8,9]主要研究如何為類仿射數(shù)組下標(biāo)應(yīng)用自動(dòng)生成并行存儲(chǔ)體及防止數(shù)據(jù)并行訪問沖突的調(diào)度方法;ROCCC[10]、DEFACTO[11]針對(duì)滑動(dòng)窗口類特殊應(yīng)用提出的存儲(chǔ)結(jié)構(gòu)模板無法用于循環(huán)迭代間流依賴的應(yīng)用;國(guó)防科技大學(xué)的竇勇教授項(xiàng)目組針對(duì)ROCCC中存在的問題提出了優(yōu)化后的參數(shù)化三層存儲(chǔ)體系結(jié)構(gòu)模板[12],但此模板的并行性還存在可以改進(jìn)的空間,并且無法為迭代間流依賴生成存儲(chǔ)結(jié)構(gòu).針對(duì)目前可重構(gòu)編譯器在為類仿射數(shù)組下標(biāo)的應(yīng)用生成硬件存儲(chǔ)結(jié)構(gòu)時(shí)的不足之處,本文主要探討如何為只有層內(nèi)數(shù)據(jù)重用的仿射類數(shù)組下標(biāo)應(yīng)用編譯生成高效的模塊化多層次存儲(chǔ)結(jié)構(gòu).并在ASCRA(Application-Specific Compiler for Reconfigurable Architecture)編譯器[13]中進(jìn)行了相關(guān)技術(shù)實(shí)現(xiàn)與驗(yàn)證.
本文的主要?jiǎng)?chuàng)新點(diǎn)如下:
(1)提出了一種面向類仿射型數(shù)組下標(biāo)應(yīng)用的參數(shù)化并行存儲(chǔ)結(jié)構(gòu)模板.采用多體交叉并行存儲(chǔ)結(jié)構(gòu)能夠有效提高循環(huán)中數(shù)據(jù)的并行性,采用RAW Buffer和Smart Buffer結(jié)構(gòu)能夠提高循環(huán)中數(shù)據(jù)重用性,該模板可以在消耗較少硬件資源的情況下獲得較高的硬件執(zhí)行速度.
(2)提出了針對(duì)參數(shù)化并行存儲(chǔ)結(jié)構(gòu)模板的模板參數(shù)自動(dòng)生成算法.通過訪存數(shù)據(jù)依賴圖生成算法自動(dòng)計(jì)算模板參數(shù)信息,提高了可重構(gòu)編譯器實(shí)現(xiàn)類仿射型數(shù)組下標(biāo)應(yīng)用到異構(gòu)加速平臺(tái)上的部署效率.
類仿射型數(shù)組下標(biāo)應(yīng)用是指參與循環(huán)運(yùn)算的數(shù)組元素下標(biāo)為類仿射型應(yīng)用,如定義1所示.
定義1 類仿射型數(shù)組下標(biāo)應(yīng)用.
在循環(huán)程序中,如果數(shù)組每維的下標(biāo)都具有ain+c(in-1,…,i2,i1) 的形式,其中a為整數(shù),n為循環(huán)嵌套層數(shù),i1,i2,…,in為循環(huán)索引變量,c(in-1,…,i2,i1)為由i1,i2,…,in-1所構(gòu)成的函數(shù)(若n=1,c(in-1,…,i2,i1)為常數(shù)),則稱該循環(huán)程序?yàn)轭惙律湫蛿?shù)組下標(biāo)應(yīng)用.
本文針對(duì)只有層內(nèi)數(shù)據(jù)重用的仿射類數(shù)組下標(biāo)應(yīng)用程序,提出了參數(shù)化并行存儲(chǔ)模板結(jié)構(gòu),結(jié)構(gòu)如圖1所示.
根據(jù)數(shù)組數(shù)據(jù)依賴關(guān)系,生成基于RAM的多體交叉并行存儲(chǔ)結(jié)構(gòu),為流水線提供并行的輸入數(shù)據(jù)讀取(Load)與輸出數(shù)據(jù)寫回(Store)操作.同時(shí),為復(fù)用數(shù)據(jù)生成RAW Buffer、Smart Buffer結(jié)構(gòu),專用于存儲(chǔ)需要復(fù)用的數(shù)據(jù),消除對(duì)RAM的訪問沖突,保證流水線的效率.根據(jù)需要訪存的復(fù)用數(shù)據(jù)依賴類型生成不同的緩存結(jié)構(gòu):為輸入依賴的復(fù)用數(shù)據(jù)生成Smart Buffer緩存結(jié)構(gòu),為循環(huán)迭代間的流依賴(寫后讀相關(guān))的復(fù)用數(shù)據(jù)自動(dòng)生成RAW Buffer緩存結(jié)構(gòu).其中Smart Buffer直接服務(wù)于運(yùn)算單元,RAW Buffer和RAM為運(yùn)算單元和Smart Buffer服務(wù).靈活匹配生成由多體交叉并行存儲(chǔ)結(jié)構(gòu)、單體串行存儲(chǔ)結(jié)構(gòu)(并行度為1的多體交叉并行存儲(chǔ)結(jié)構(gòu))、RAW Buffer緩存結(jié)構(gòu)及Smart Buffer緩存結(jié)構(gòu)組成的存儲(chǔ)體系.
本節(jié)主要論述自動(dòng)生成并行存儲(chǔ)硬件結(jié)構(gòu)過程中的難點(diǎn)問題,即數(shù)組數(shù)據(jù)訪存特征描述方法及各子模塊參數(shù)值計(jì)算方法.
4.1 訪存數(shù)據(jù)依賴圖生成算法
定義2 訪存數(shù)據(jù)依賴圖.
訪存數(shù)據(jù)依賴圖MDDG=(V,E,R),其中V為節(jié)點(diǎn)集合,E為連接相鄰節(jié)點(diǎn)的有向邊,R為數(shù)據(jù)重用度.
XA[ain+d(in-1,…,i2,i1)]∈V,X={L,S},即循環(huán)迭代空間內(nèi)數(shù)組元素A[ain+d(in-1,…,i2,i1)]進(jìn)行了Load或Store操作,每個(gè)e=(XA[ain+c(in-1,…,i2,i1)],XA[ain+d(in-1,…,i2,i1)])∈E存在一個(gè)數(shù)據(jù)重用度R
本文提出的訪存數(shù)據(jù)依賴圖生成算法描述如算法1所示.
4.2 計(jì)算模板參數(shù)
根據(jù)訪存數(shù)據(jù)依賴圖,為每個(gè)不同名的數(shù)組生成參數(shù)化并行存儲(chǔ)結(jié)構(gòu)所需參數(shù)值:(1)多體交叉存取度:Ram-num;(2)存儲(chǔ)體深度:Ram-depth;(3)存儲(chǔ)體位寬:Ram-width;(4)RAW Bufffer個(gè)數(shù):RBuffer-num;(5)RAW Bufffer深度:RBuffer-depth;(6)Smart Buffer個(gè)數(shù):SBuffer-num;(7)Smart Buffer深度:Register-num.設(shè)輸入的數(shù)組元素個(gè)數(shù)Arrary-depth;輸入的數(shù)組元素位寬I-width.
(1)多體交叉存儲(chǔ)度Ram-num
生成訪存數(shù)據(jù)依賴圖過程中,如果集合Sxam的個(gè)數(shù)為n,或者集合Sx0m的個(gè)數(shù)為m,計(jì)算RAM的多體交叉存儲(chǔ)度Ram-num的公式如(2)所示.當(dāng)Ram-num等于1時(shí),硬件結(jié)構(gòu)為單體串行結(jié)構(gòu).
(2)
(2)存儲(chǔ)體深度Ram-depth
計(jì)算方法如式(3).
Ram-depth=Arrary-depth/Ram-num
(3)
(3)存儲(chǔ)體位寬Ram-width
計(jì)算方法如式(4).
Ram-width=I-width
(4)
(4)RAW Buffer結(jié)構(gòu)個(gè)數(shù)RBuffer-num
如果訪存數(shù)據(jù)依賴圖集合中存在流依賴的訪存數(shù)據(jù)依賴圖有f個(gè),根據(jù)參數(shù)化并行存儲(chǔ)模板規(guī)則,為重用數(shù)據(jù)生成RAW Buffer結(jié)構(gòu).其RAW Buffer結(jié)構(gòu)的個(gè)數(shù)等于有流依賴的訪存數(shù)據(jù)依賴圖中的葉子節(jié)點(diǎn)的個(gè)數(shù)f,如式(5).
RBuffer-num=f
(5)
(5)RAW Bufffer深度RBuffer-depth
為具有流依賴的輸入數(shù)據(jù)設(shè)計(jì)RAW Buffer結(jié)構(gòu),每個(gè)RAW Buffer結(jié)構(gòu)的深度由進(jìn)行Store操作的數(shù)組元素所在數(shù)據(jù)通路中的流水段號(hào)(Ln)同訪存數(shù)據(jù)依賴圖中葉子節(jié)點(diǎn)(SA[ai+d])和其相連節(jié)點(diǎn)(LA[ai+b])間的數(shù)據(jù)重用度R
RBuffer-depth
(6)
式(7)中RBuffer-depth=0表示直連線,不生成寄存器.
(6)Smart Buffer結(jié)構(gòu)個(gè)數(shù)SBuffer-num
Smart Buffer的個(gè)數(shù)等于訪存數(shù)據(jù)依賴圖中劃分出的集合個(gè)數(shù)S,如式(7).
SBuffer-num=S
(7)
(7)Smart Buffer結(jié)構(gòu)深度Register-num
在含流依賴的訪存數(shù)據(jù)依賴圖中,其葉子節(jié)點(diǎn)生成的數(shù)據(jù)存儲(chǔ)在RAW Buffer中,非葉子節(jié)點(diǎn)中所需的數(shù)據(jù)從Smart Buffer中讀取,此時(shí)Smart Buffer的深度如式(8)所示.
Register-num=∑Rxkmnv-RBuffer-depth+1
(8)
其中,∑Rkmnv表示集合Sxkmnv(v=v0,…,vn)對(duì)應(yīng)的訪存數(shù)據(jù)依賴圖中相鄰節(jié)點(diǎn)數(shù)據(jù)重用度之和.
在含輸入依賴(或只有單節(jié)點(diǎn))的訪存數(shù)據(jù)依賴圖中,其葉子節(jié)點(diǎn)數(shù)據(jù)需要從并行存儲(chǔ)結(jié)構(gòu)中讀取,并行讀取的數(shù)據(jù)需要存儲(chǔ)到相應(yīng)Smart Buffer中,此時(shí)Smart Buffer的深度如式(9)所示.
Register-num
=MAX(∑Rxkmnv0,∑Rxkmnv1,…,∑Rxkmnvn)+1
(9)
目前和本文研究?jī)?nèi)容接近的主要包括CHIMPS編譯器生成的硬件存儲(chǔ)結(jié)構(gòu)[7]和竇勇教授提出的三層存儲(chǔ)結(jié)構(gòu)模板(DY)[12].本文采用5-tap FIR測(cè)試用例(其問題復(fù)雜度為4096,數(shù)據(jù)輸入輸出寬度為32bits),將三種方法進(jìn)行對(duì)比.表1中CHIMPS的數(shù)據(jù)是根據(jù)文獻(xiàn)[7]提到的方法計(jì)算生成,DY中的數(shù)據(jù)根據(jù)文獻(xiàn)[12]提出的模板公式計(jì)算生成.
通過表1中實(shí)驗(yàn)結(jié)果可以得知,針對(duì)類仿射型數(shù)組下標(biāo)應(yīng)用來說,與CHIMPS相比,隨著程序循環(huán)并行度的增加,采用本文所提出的參數(shù)化并行存儲(chǔ)結(jié)構(gòu)模板自動(dòng)生成的存儲(chǔ)結(jié)構(gòu)中,所消耗的RAM硬件資源具有明顯的優(yōu)勢(shì),并且在緩存方面也優(yōu)于CHIMPS;與DY相比,雖然在RAM資源整體消耗上,兩者是相同的,但是,本文所提方法增加了并行的RAM個(gè)數(shù),并且降低了RAM的深度,這種設(shè)計(jì)方式能夠有效的提高存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)訪問的并行度和復(fù)用度,降低RAM訪存沖突,尤其是當(dāng)程序可以同時(shí)讀取多個(gè)RAM中數(shù)據(jù)時(shí),本文具有明顯的優(yōu)勢(shì),此外,本文采用增加緩存高度的方式提高了層內(nèi)循環(huán)數(shù)據(jù)重用性.
表1 存儲(chǔ)結(jié)構(gòu)對(duì)比
表2為5-tap FIR測(cè)試用例采用三種不同方法生成硬件的執(zhí)行時(shí)間隨循環(huán)展開度的變化情況,從表2中可以看出,三種方法生成的硬件執(zhí)行頻率相當(dāng),但隨著循環(huán)展開次數(shù)的不斷增加,由于DY提出的方法沒有為應(yīng)用生成并行存儲(chǔ)結(jié)構(gòu),因此,數(shù)據(jù)訪存開銷較大,增加了程序的執(zhí)行時(shí)間,相比之下,本文生成的硬件執(zhí)行時(shí)間和CHIMPS生成的硬件執(zhí)行時(shí)間較短,當(dāng)循環(huán)程序的并行度增加時(shí),對(duì)程序循環(huán)并行性具有更好的適應(yīng)性,能夠提升程序的性能.
結(jié)合表1和表2結(jié)果可以得知,與CHIMPS相比,本文所提的模板在性能相當(dāng)情況下具有明顯的資源優(yōu)勢(shì),而與DY所提方法相比,在消耗資源相當(dāng)情況下,具有明顯性能優(yōu)勢(shì),結(jié)合了兩者的優(yōu)勢(shì),從而實(shí)現(xiàn)對(duì)類仿射型數(shù)組下標(biāo)應(yīng)用的存儲(chǔ)結(jié)構(gòu)進(jìn)行了改進(jìn).
表2 硬件的執(zhí)行時(shí)間隨循環(huán)展開度的變化情況
本文針對(duì)類仿射數(shù)組下標(biāo)應(yīng)用,提出了一種參數(shù)化并行存儲(chǔ)結(jié)構(gòu)模板.該存儲(chǔ)模板結(jié)構(gòu)不僅為輸入依賴的復(fù)用數(shù)據(jù)生成Smart Buffer緩存結(jié)構(gòu),還為循環(huán)迭代間的流依賴的復(fù)用數(shù)據(jù)生成RAW Buffer緩存結(jié)構(gòu).實(shí)驗(yàn)表明,本文提出的存儲(chǔ)模板具有較高的靈活性,可以為不同應(yīng)用生成不同結(jié)構(gòu)的存儲(chǔ)系統(tǒng),較好的支持了數(shù)據(jù)的重用及并行訪問,同時(shí),在為循環(huán)展開程序生成存儲(chǔ)結(jié)構(gòu)時(shí),和相關(guān)工作相比,在占用較少的資源情況下,可以獲得較高的硬件執(zhí)行速度,從整體上提高了程序性能.
[1]Callahan T.Kernel formation in garpcc[A].Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines[C].Napa Valley,CA,USA,2003.308-309.
[2]Huthmann J,Liebig B,Oppermann J,et al.Hardware/software co-compilation with the Nymble system[A].2013 8th International Workshop on Reconfigurable and Communication-Centric Systems-on-Chip (ReCoSoC)[C].Darmstadt,Germany,2013.1-8.
[3]Gokhale M B,Stone J M.NAPA C:Compiling for a hybrid RISC/FPGA architecture[A].1998 Proceedings IEEE Symposium on FPGAs for Custom Computing Machines[C].Napa Valley,CA,USA,1998.126-135.
[4]Alex J,Debabrata B,Sartajit P et al.PACT HDL:A C compiler targeting ASICs and fPGAs with power and performance optimizations[A].Proceedings of the 2002 International Conference on Compilers,Architecture,and Synthesis for Embedded Systems,CASES '02[C].Grenoble,France,2002.188-197.
[5]Metzgen P.Software-to-hardware compiler:U.S.Patent 8,473,926[P].2013-6-25.
[6]Seung J.Lee,David K.Raila,Voelodymyr V.Kindratenko.LLVM-CHiMPS:Compilation environment for FPGAs using LLVM compiler infrastructure and CHiMPS computational model[A].Proceedings of 4th Annual Reconfigurable Systems Summer Institute[C].Urbana,USA,2008.1-10.
[7]Putnam A,Bennett D,Dellinger E,et al.CHiMPS:A C-level compilation flow for hybrid CPU-FPGA architectures[A].2008 IEEE International Conference on Field Programmable Logic and Applications[C].Heidelberg,2008.173-178.
[8]Monson J,Wirthlin M,Hutchings B L.Implementing high-performance,low-power FPGA-based optical flow accelerators in C[A].2013 IEEE 24th International Conference on Application-Specific Systems,Architectures and Processors (ASAP)[C].Washington,DC,2013.363-369.
[9]Navarro D,Lucia O,Barragan L A,et al.High-level synthesis for accelerating the FPGA implementation of computationally demanding control algorithms for power converters[J].IEEE Trans.Industrial Informatics,2013,9(3):1371-1379.
[10]Villarreal J,Park A,Najjar W,et al.Designing modular hardware accelerators in C with ROCCC 2.0[A].2010 18th IEEE Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)[C].Charlotte,NC,2010.127-134.
[11]Diniz P,Park J.Automatic synthesis of data storage and control structures for FPGA-based computing engines[A].Proceedings of 8th IEEE Symposium on Field-Programmable Custom Computing Machines[C].Napa Valley,CA,2000.91-100.
[12]竇勇,董亞卓,徐進(jìn)輝,等.基于參數(shù)化存儲(chǔ)結(jié)構(gòu)的滑動(dòng)窗口IP核自動(dòng)生成[J].軟件學(xué)報(bào),2009,20(2):246-255.
Dou Y,Dong YZ,Xu JH et al.Automatic generation of IP core for sliding-window operations based on a parameterized memory architecutre[J].Journal of Software,2009,20(2):246-255.(in Chinese)
[13]吳艷霞,顧國(guó)昌,孫延騰,等.面向應(yīng)用的可重構(gòu)編譯ASCRA[J].計(jì)算機(jī)科學(xué)與探索,2011,5(3):267-279.
Wu Yanxia,Gu Guochang,Sun Yanteng et al.Application-specific compiler for reconfigurable architecture ASCRA[J].Journal of Fronotiers of Computer Science & Technology,2011,5(3):267-279.(in Chinese)
郭振華 男,1988年生于河北省,2010年獲哈爾濱工程大學(xué)學(xué)士學(xué)位,現(xiàn)為哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院博士研究生.主要研究方向?yàn)橛?jì)算機(jī)體系結(jié)構(gòu)、可重構(gòu)編譯、信息安全.
E-mail:hrbeu.guozhenhua@gmail.com
吳艷霞(通信作者) 女,1979年生于哈爾濱,2008年獲得哈爾濱工程大學(xué)博士學(xué)位,哈爾濱工程大學(xué)副教授,碩士生導(dǎo)師,研究方向?yàn)橛?jì)算機(jī)體系結(jié)構(gòu)、可重構(gòu)編譯、信息安全.
E-mail:wuyanxia@hrbeu.edu.cn
A Parameterized Parallelism Memory Template for Affine Array Subscript Application
GUO Zhen-hua,WU Yan-xia,ZHANG Guo-yin,DAI Kui
(CollegeofComputerScienceandTechnology,HarbinEngineeringUniversity,Harbin,Heilongjiang150001,China)
In current reconfigurable compiling approach for solving affine subscript operations,the automatic generated feeding memory system is not optimal,especially to support an iteration pipeline structure.This paper presents a parameterized parallel memory template to mine parallelism and reusability of data,which is considered to address the lack of such aspect in reconfigurable compilers at hand.According to the analysis of characteristics of data access to affine subscript arrays in pipeline iteration,our template configures alternative sub-structures such as parallel multi-bank memory,sequential access memory,RAW Buffer and Smart Buffer.Furthermore,in phase of calculating parameter values to fill the template,the memory data dependence graph method is used,in which approach the flexibility of way to create memory structure is kept.The experimental result shows that compared with related works,the compiler can generate reconfigurable hardware performing a higher execution speed with less resources usage by employ the proposed memory template.
affine array subscript;compiler for reconfigurable computing;memory architecture;data reuse;template
2014-12-01;
2015-03-10;責(zé)任編輯:馬蘭英
國(guó)家自然科學(xué)基金(No.61003036);計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室開放課題(No.CARCH201301);博士后科研啟動(dòng)基金(No.LBH-Q12134);中央高校基本科研業(yè)務(wù)經(jīng)費(fèi)專項(xiàng)基金(No.HEUCF100606)
TP302
A
0372-2112 (2016)08-1956-06