<meter id="pryje"><nav id="pryje"><delect id="pryje"></delect></nav></meter>
          <label id="pryje"></label>

          新聞中心

          EEPW首頁(yè) > EDA/PCB > 設(shè)計(jì)應(yīng)用 > 嘗試通過(guò)算法重構(gòu)和Vivado HLS生成高效的處理流水線

          嘗試通過(guò)算法重構(gòu)和Vivado HLS生成高效的處理流水線

          作者: 時(shí)間:2016-10-16 來(lái)源:網(wǎng)絡(luò) 收藏

          通過(guò)用于重構(gòu)高級(jí)算法描述的簡(jiǎn)單流程,就可以利用高層次綜合功能生成更高效的處理流水線。

          本文引用地址:http://www.ex-cimer.com/article/201610/308333.htm

          如果您正在努力開(kāi)發(fā)計(jì)算內(nèi)核,而且采用常規(guī)內(nèi)存訪問(wèn)模式,并且循環(huán)迭代間的并行性比較容易提取,這時(shí),設(shè)計(jì)套件高層次綜合(HLS)工具是創(chuàng)建高性能加速器的極好資源。通過(guò)向C語(yǔ)言高級(jí)算法描述中添加一些編譯指示,就可以在FPGA上快速實(shí)現(xiàn)高吞吐量的處理引擎。結(jié)合使用軟件管理的DMA機(jī)制,就可以比通用處理器提速數(shù)十倍。

          然而,實(shí)際應(yīng)用中經(jīng)常會(huì)遇到難以處理的復(fù)雜內(nèi)存訪問(wèn)問(wèn)題,尤其是當(dāng)突破科學(xué)計(jì)算和信號(hào)處理算法領(lǐng)域時(shí)更是如此。我們?cè)O(shè)計(jì)出了一種簡(jiǎn)單方法,可供您在此類情況下生成高效的處理流水線。在詳細(xì)介紹之前,我們首先了解一下 HLS的工作原理,更重要的是了解它何時(shí)不起作用。

          HLS工具如何起作用?

          高層次綜合功能試圖獲取由高級(jí)語(yǔ)言描述的控制數(shù)據(jù)流圖 (CDFG)中的并行性。對(duì)計(jì)算操作和內(nèi)存訪問(wèn)進(jìn)行分配和調(diào)度時(shí),應(yīng)根據(jù)它們之間的依賴約束和目標(biāo)平臺(tái)的資源約束來(lái)執(zhí)行。電路中特定操作的激活與某個(gè)時(shí)鐘周期相關(guān),同時(shí),沿?cái)?shù)據(jù)路徑綜合的中央控制器協(xié)調(diào)整個(gè)CDFG的執(zhí)行。

          單純?cè)趦?nèi)核上應(yīng)用HLS可以建立一條具有眾多指令級(jí)并行性的數(shù)據(jù)路徑。但是當(dāng)它被激活時(shí),就需要頻繁停下來(lái)等待數(shù)據(jù)送入。

          由于調(diào)度工作是在靜態(tài)下完成的, 因此加速器運(yùn)行時(shí)間的行為相當(dāng)簡(jiǎn)單。所生成電路的不同部分相互之間以相同步調(diào)運(yùn)行;并不需要?jiǎng)討B(tài)的相關(guān)性檢查機(jī)制,例如高性能CPU上出現(xiàn)的那種。例如,在圖1(a) 所示的函數(shù)中,循環(huán)索引添加和curInd的加載可以并行處理。此外,下次迭代可以在當(dāng)前迭代完成前開(kāi)始。

          同時(shí),由于浮點(diǎn)乘法通常使用上次迭代的乘法結(jié)果

          因此可以開(kāi)始新迭代的最短間隔受到浮點(diǎn)乘法器時(shí)延的限制。該函數(shù)的執(zhí)行調(diào)度如圖2(a)所示。

          該方案何時(shí)達(dá)不到理想效果?

          這種方案的問(wèn)題在于整個(gè)數(shù)據(jù)流圖嚴(yán)格按調(diào)度運(yùn)行。片外通信產(chǎn)生的拖延會(huì)傳播到整個(gè)處理引擎,從而導(dǎo)致性能大幅下降。當(dāng)內(nèi)存訪問(wèn)模式已知,數(shù)據(jù)能在需要使用之前移動(dòng)到芯片上,或者如果數(shù)據(jù)集足夠小,則可完全高速緩存在FPGA上,這類情況下不會(huì)有問(wèn)題。然而,就很多有趣的算法而言,數(shù)據(jù)訪問(wèn)取決于計(jì)算結(jié)果,而且內(nèi)存占用決定了需要使用片外RAM。現(xiàn)在,在內(nèi)核上單純應(yīng)用HLS可建立一條具有眾多指令級(jí)并行性的數(shù)據(jù)路徑。但是,當(dāng)它被激活時(shí),就需要頻繁停下來(lái)等待數(shù)據(jù)送入。

          嘗試通過(guò)算法重構(gòu)和Vivado HLS生成高效的處理流水線

          圖1 – 設(shè)計(jì)實(shí)例:(a) 包含不規(guī)則內(nèi)存訪問(wèn)模式的函數(shù);(b) 重構(gòu)得到的流水線結(jié)構(gòu)

          嘗試通過(guò)算法重構(gòu)和Vivado HLS生成高效的處理流水線

          圖2 – 不同情形下的執(zhí)行調(diào)度:(a) 當(dāng)所有數(shù)據(jù)都在片上高速緩存;

          (b) 動(dòng)態(tài)取數(shù)據(jù);(c) 解耦運(yùn)算

          圖2(b)給出了針對(duì)實(shí)例函數(shù)生成的硬件模塊的執(zhí)行情況,此時(shí)數(shù)據(jù)集太大,需要?jiǎng)討B(tài)送入片上高速緩存。注意減速程度如何反映所有高速緩存缺失時(shí)延的綜合影響。不過(guò),情況并非一定如此,因?yàn)橛?jì)算圖中有些部分的進(jìn)展不需要立即提供內(nèi)存數(shù)據(jù)。這些部分應(yīng)該可以向前移動(dòng)。執(zhí)行調(diào)度中這點(diǎn)額外自由度有可能產(chǎn)生顯著影響,就像我們看到的那樣。

          重構(gòu)/解耦實(shí)例

          我們看一下剛才的實(shí)例函數(shù)。假設(shè)浮點(diǎn)乘法的執(zhí)行和數(shù)據(jù)訪問(wèn)沒(méi)有全部由統(tǒng)一的安排聯(lián)系在一起。當(dāng)一個(gè)負(fù)載運(yùn)算符等待數(shù)據(jù)返回時(shí),另一個(gè)負(fù)載運(yùn)算符可以開(kāi)始新的內(nèi)存請(qǐng)求,乘法器的執(zhí)行也能向前移動(dòng)。為達(dá)到此目的,每項(xiàng)內(nèi)存訪問(wèn)都應(yīng)該由一個(gè)模塊來(lái)負(fù)責(zé),并按各自的調(diào)度運(yùn)行。此外,乘法器單元應(yīng)該與所有內(nèi)存操作異步執(zhí)行。

          不同模塊間的數(shù)據(jù)相關(guān)性

          通過(guò)硬件FIFO來(lái)通信。對(duì)于我們的實(shí)例而言,可能的重構(gòu)形式如圖1(b)所示。用于各階段之間通信的硬件隊(duì)列可以緩沖已經(jīng)取回但尚未使用的數(shù)據(jù)。當(dāng)內(nèi)存訪問(wèn)部件因高速緩存缺失而出現(xiàn)拖延時(shí),當(dāng)前已產(chǎn)生的積壓數(shù)據(jù)還可以繼續(xù)供乘法器單元使用。在經(jīng)歷較長(zhǎng)時(shí)間后,形成的拖延時(shí)間會(huì)被浮點(diǎn)乘法的長(zhǎng)時(shí)延掩蓋。

          圖2(c)給出了使用解耦處理流水線時(shí)的執(zhí)行調(diào)度。這里,通過(guò)FIFO的時(shí)延沒(méi)有考慮在內(nèi),不過(guò)如果迭代量很大,該時(shí)延的影響會(huì)達(dá)到最小。

          我們?nèi)绾芜M(jìn)行重構(gòu)?

          為了給解耦處理模塊生成流水線,首先需要將初始CDFG中的指令進(jìn)行組合以構(gòu)成子圖。為使所得的實(shí)現(xiàn)方案性能最大化,聚類方法必須滿足幾個(gè)要求。

          首先,正如我們之前所見(jiàn), HLS工具在前面的迭代完成之前使用軟件流水線發(fā)起新的迭代。CDFG中最長(zhǎng)循環(huán)依賴的時(shí)延決定可發(fā)起新迭代的最小間隔,最終會(huì)限制加速器所能實(shí)現(xiàn)的總吞吐量。因此,很重要的一點(diǎn)在于這些依賴循環(huán)不能遍歷多個(gè)子圖,例如用于模塊間通信的FIFO總是會(huì)增加時(shí)延。

          其次,應(yīng)該將內(nèi)存操作與涉及長(zhǎng)時(shí)延計(jì)算的依賴循環(huán)分開(kāi),這樣高速緩存缺失就會(huì)被慢速的數(shù)據(jù)處理所“掩蓋”。在這里,“長(zhǎng)時(shí)延”是指操作需要一個(gè)周期以上的時(shí)間才能完成;在這里,我們使用Vivado HLS調(diào)度來(lái)獲取這一指標(biāo)。例如,乘法是長(zhǎng)時(shí)延操作,而整數(shù)加法不是。

          最后,為了將高速緩存缺失引起的拖延影響限定在局部范圍內(nèi),您需要將每個(gè)子圖中的內(nèi)存操作數(shù)量減至最少,尤其是在需要尋址存儲(chǔ)空間中的不同部分時(shí)更是如此。

          第一個(gè)要求——防止依賴循環(huán)遍歷多個(gè)子圖——很容易滿足,只需要找到原始數(shù)據(jù)流圖中的強(qiáng)連通分量(SCC),并在將它們分為不同集群之前將其打開(kāi)變成節(jié)點(diǎn)。這樣,我們就得到一個(gè)有向的非循環(huán)圖,其中有些節(jié)點(diǎn)是簡(jiǎn)單指令,其它則為一組相關(guān)的操作。

          要滿足第二和第三個(gè)要求,即分離內(nèi)存操作和局部化拖延的影響,我們可以對(duì)這些節(jié)點(diǎn)進(jìn)行拓?fù)渑判?,然后將它們分區(qū)。最簡(jiǎn)單的分區(qū)方法是在每個(gè)內(nèi)存操作或長(zhǎng)時(shí)延SCC節(jié)點(diǎn)后畫一條“邊界”。圖3展示了如何將此方案應(yīng)用于我們的實(shí)例。集群與圖1中流水線結(jié)構(gòu)之間的對(duì)應(yīng)關(guān)系應(yīng)該做到顯而易見(jiàn)。每個(gè)子圖都是一個(gè)新的C函數(shù),可獨(dú)立通過(guò)HLS推送。這些子圖在執(zhí)行時(shí)相互間的步調(diào)并不一致。

          我們構(gòu)建了一個(gè)簡(jiǎn)單的源到源轉(zhuǎn)換工具,用以執(zhí)行重構(gòu)。

          我們使用IP核,支持FIFO,以連接所生成的獨(dú)立模塊。當(dāng)然,重構(gòu)給定計(jì)算內(nèi)核的方法不止一種,而且設(shè)計(jì)空間探索仍在進(jìn)行中。

          流水線化內(nèi)存訪問(wèn)

          有了解耦處理流水線的初步實(shí)施方案后,我們就可以對(duì)其執(zhí)行幾項(xiàng)優(yōu)化,以提高其效率。正如我們所見(jiàn),當(dāng)使用HLS映射C函數(shù)時(shí),內(nèi)存讀取出現(xiàn)阻塞。這個(gè)問(wèn)題也出現(xiàn)在流水線中的個(gè)別階段。例如,負(fù)責(zé)加載x[curInd]的模塊在等待數(shù)據(jù)時(shí)可能會(huì)產(chǎn)生拖延,即使在下個(gè)curInd已經(jīng)就緒而且FIFO下游有足夠空間的情況下亦是如此。

          為了解決這個(gè)問(wèn)題,我們可以做一下轉(zhuǎn)變以簡(jiǎn)化內(nèi)存訪問(wèn)。對(duì)于某個(gè)特定階段,我們不在C函數(shù)中執(zhí)行簡(jiǎn)單的內(nèi)存加載,而是將地址推送到新的FIFO。然后,單獨(dú)實(shí)例化一個(gè)新的硬件模塊,以讀取地址FIFO送出的地址,并將它們發(fā)送到內(nèi)存子系統(tǒng)。返回的數(shù)據(jù)被直接推送到下游FIFO?,F(xiàn)在,內(nèi)存訪問(wèn)得到了有效的流水線化。

          地址的推送操作可在Vivado HLS中通過(guò)向FIFO接口的內(nèi)存存儲(chǔ)來(lái)代表,AXI總線協(xié)議允許您指定突發(fā)長(zhǎng)度;而且,通過(guò)對(duì)解耦C函數(shù)進(jìn)行一些小的修改,并利用流水線化的內(nèi)存訪問(wèn)模塊,我們就可利用該功能。

          3.jpg

          圖3 – 對(duì)子圖的重構(gòu)

          4.jpg

          圖4 – 背包問(wèn)題

          除了生成地址以外,解耦C函數(shù)中每個(gè)內(nèi)存操作符還要在連續(xù)存儲(chǔ)塊被訪問(wèn)時(shí)計(jì)算突發(fā)長(zhǎng)度。循環(huán)計(jì)數(shù)器的復(fù)制還有助于突發(fā)訪問(wèn)的生成,因?yàn)楸辉L問(wèn)的字?jǐn)?shù)量可以在每個(gè)解耦函數(shù)中本地確定。

          不過(guò),用以監(jiān)測(cè)下游FIFO和發(fā)送內(nèi)存請(qǐng)求的硬件模塊則采用Verilog實(shí)現(xiàn)。這是因?yàn)樵谟蒝ivado HLS綜合的內(nèi)存接口中,外發(fā)地址和響應(yīng)數(shù)據(jù)沒(méi)有捆綁在一起。不過(guò)這是一個(gè)簡(jiǎn)單模塊,能在不同基準(zhǔn)測(cè)試中重用很多次,因此設(shè)計(jì)工作就被攤銷了。

          復(fù)制或通信?

          在重構(gòu)內(nèi)核并生成解耦處理流水線的過(guò)程中,用來(lái)在不同階段移動(dòng)數(shù)據(jù)的FIFO會(huì)形成很大開(kāi)銷。通過(guò)復(fù)制少量計(jì)算指令可以去除一些FIFO,這樣通常很有好處,因?yàn)榧词故亲钚∩疃鹊腇IFO也會(huì)占用不少FPGA資源。

          一般而言,在權(quán)衡利弊以探究最佳設(shè)計(jì)點(diǎn)的過(guò)程中,您可以使用成本模型和規(guī)范的優(yōu)化技術(shù)。但在大多數(shù)基準(zhǔn)測(cè)試中,僅僅為它的每個(gè)用戶復(fù)制簡(jiǎn)單的循環(huán)計(jì)數(shù)器就可以節(jié)省很多面積,這也正是我們所做的。在這個(gè)引導(dǎo)性實(shí)例中, 該優(yōu)化是指復(fù)制i的整數(shù)加法器,因此存儲(chǔ)結(jié)果 i時(shí)不需要從其它模塊獲得索引。

          內(nèi)存的突發(fā)訪問(wèn)

          第三項(xiàng)優(yōu)化是內(nèi)存的突發(fā)訪問(wèn)(burst-memory access)。為了更高效地利用內(nèi)存帶寬,我們希望通過(guò)一次內(nèi)存事務(wù)處理攜帶多個(gè)數(shù)據(jù)字。

          實(shí)驗(yàn)評(píng)估

          我們應(yīng)用上述方案做了幾個(gè)案例研究。 為評(píng)估這種方法的優(yōu)勢(shì),我們將使用該方案生成的解耦處理流水線 (DPP)與單純使用HLS生成的加速器進(jìn)行比較。當(dāng)為單純或DPP實(shí)現(xiàn)方案調(diào)用Vivado HLS時(shí),我們將目標(biāo)時(shí)鐘頻率設(shè)置到150MHz,并在布局布線后使用所能達(dá)到的最高時(shí)鐘速率。此外,我們針對(duì)加速器和內(nèi)存子系統(tǒng)之間的交互嘗試了不同的機(jī)制。所用的端口為ACP和HP。我們?yōu)槊總€(gè)端口在可重配置陣列上實(shí)例化一個(gè)64KB高速緩存。

          本實(shí)驗(yàn)所用的物理器件是的Zynq®-7000 XC7Z020全可編程SoC,安裝在ZedBoard評(píng)估平臺(tái)上。

          我們還在Zynq SoC 的ARM®處理器上運(yùn)行應(yīng)用的軟件版本,并將其性能作為實(shí)驗(yàn)的基準(zhǔn)。生成的所有加速器功能齊全,無(wú)需任何DMA機(jī)制將數(shù)據(jù)移入和移出可重配置架構(gòu)。

          5.jpg

          圖5 – 針對(duì)背包問(wèn)題的運(yùn)行時(shí)間比較

          案例研究1:

          背包問(wèn)題

          眾所周知,背包問(wèn)題是一個(gè)組合問(wèn)題,可以通過(guò)動(dòng)態(tài)編程來(lái)求解。內(nèi)核的結(jié)構(gòu)如圖4所示。其中黑體字的變量都是在運(yùn)行時(shí)間從

          內(nèi)存讀取。因此,無(wú)法確切知道從哪個(gè)位置加載的變量opt_without。當(dāng)w和n 比較大時(shí),我們無(wú)法在片上緩沖整個(gè)opt陣列。我們只能讓計(jì)算引擎取回所需的部分。

          圖5給出了運(yùn)行時(shí)間對(duì)比情況,將使用我們的方案(DPP)生成的加速器與單純通過(guò)HLS推送函數(shù)而生成的加速器進(jìn)行比較。圖中還顯示了在ARM處理器上運(yùn)行函數(shù)時(shí)的性能。 我們將n(項(xiàng)數(shù))固定為40,使w (背包的總重量)在100至3,200之間變化。

          6.jpg

          圖6 – 稀疏矩陣向量乘法

          從對(duì)比中很容易看出,通過(guò)單純使用Vivado HLS來(lái)映射軟件內(nèi)核這種方法得到的 ARM處理器性能高出約4.5倍。另外,當(dāng)使用

          加速器性能比基準(zhǔn)要求慢很多。 DPP時(shí),各種內(nèi)存訪問(wèn)機(jī)制之間的Zynq SoC 上的超標(biāo)量 差別相當(dāng)小——使用我們的方案時(shí),無(wú)序式ARM內(nèi)核能受內(nèi)存訪問(wèn)時(shí)延的影響要小很多。

          7.jpg

          圖7 – 針對(duì)稀疏矩陣向量乘法的運(yùn)行時(shí)間對(duì)比

          很大程度開(kāi)拓指令級(jí)并行性,而且具有一個(gè)高性能片上高速緩存。Vivado HLS工具提取的案例研究2:稀疏矩陣向量乘法

          附加并行性顯然不足以補(bǔ)償硬處理器內(nèi)核對(duì)于稀疏矩陣向量(SpMV)乘法是一個(gè)可編程邏輯的時(shí)鐘頻率優(yōu)勢(shì)計(jì)算內(nèi)核,已經(jīng)在各種研究項(xiàng)目中以很多不同方法進(jìn)行過(guò)研究、變換和基準(zhǔn)確定。這里,我們的目的不是以及來(lái)自可重配置陣列的使用特殊數(shù)據(jù)結(jié)構(gòu)和存儲(chǔ)分配方式更長(zhǎng)的數(shù)據(jù)訪問(wèn)時(shí)延。構(gòu)建最佳性能的SpMV乘法,不過(guò),當(dāng)內(nèi)核被解耦,分成而是想根據(jù)最基本的算法描述多個(gè)處理階段時(shí),看看在使用Vivado HLS時(shí)重構(gòu)性能就會(huì)明顯比傳遞能提供多少優(yōu)勢(shì)。

          如圖6所示,在我們的實(shí)驗(yàn)中,稀疏矩陣以壓縮稀疏行(CSR)格式存儲(chǔ)。在取回?cái)?shù)字以進(jìn)行實(shí)際的浮點(diǎn)乘法之前,需要先執(zhí)行來(lái)自索引數(shù)組的負(fù)載。用來(lái)決定訪問(wèn)哪個(gè)控制流程和內(nèi)存位置的數(shù)值只有在運(yùn)行時(shí)間才知道。在圖7所示的運(yùn)行時(shí)間對(duì)比中,矩陣的平均密度為1/16,尺寸在32和2,048之間變化。

          此處,單純的映射法在性能上再次落后于軟件版。當(dāng)不使用FPGA上的高速緩存時(shí),用我們的方法生成的解耦處理流水線在性能上幾乎與基準(zhǔn)性能相同。

          當(dāng)在可重配置陣列上實(shí)例化一個(gè)64KB高速緩存時(shí),DPP的性能接近基準(zhǔn)的兩倍。與之前的基準(zhǔn)相比,高速緩存的增加對(duì)DPP的性能具有更顯著的影響。

          案例研究3:FLOYD-WARSHALL 算法

          Floyd-Warshall是一種圖形算法,用來(lái)找到任意一對(duì)頂點(diǎn)之間成對(duì)的最短路徑。內(nèi)存訪問(wèn)模式比之前的基準(zhǔn)要簡(jiǎn)單。因此,有可能存在一種方法可以設(shè)計(jì)出DMA+加速器結(jié)構(gòu),以獲得很好的計(jì)算重疊和片外通信。我們的方案能試著自動(dòng)實(shí)現(xiàn)這種重疊,但是我們尚未進(jìn)行相關(guān)的研究,以表明絕對(duì)最佳與實(shí)際所得之間的差距。

          不過(guò),與之前的基準(zhǔn)一樣,我也進(jìn)行了運(yùn)行時(shí)間對(duì)比。這里,我們使圖形的大小在40個(gè)節(jié)點(diǎn)至160個(gè)節(jié)點(diǎn)之間變化。每個(gè)節(jié)點(diǎn)平均有全部節(jié)點(diǎn)的1/3作為其鄰點(diǎn)。得到的結(jié)果與背包問(wèn)題中的十分類似。

          8.jpg

          圖8 –Floyd-Warshall算法

          解耦處理流水線所實(shí)現(xiàn)的性能約為軟件基準(zhǔn)的3倍,吞吐量達(dá)到任何單純映射法的兩倍多。當(dāng)使用DPP時(shí),對(duì)FPGA高速緩存的影響也很小,展示出了對(duì)于內(nèi)存訪問(wèn)時(shí)延的容限。

          我們這種簡(jiǎn)單的技術(shù)構(gòu)建出的處理流水線可以更好地使用內(nèi)存帶寬,而且對(duì)內(nèi)存時(shí)延有更好的容限,因此能夠改善Vivado HLS的性能。所描述的方法可對(duì)控制數(shù)據(jù)流圖中的內(nèi)存訪問(wèn)和較長(zhǎng)的依賴循環(huán)解耦,這樣高速緩存缺失就不會(huì)拖延加速器的其它部分。

          9.jpg

          圖9 – 針對(duì)Floyd-Warshall算法的運(yùn)行時(shí)間比較



          關(guān)鍵詞: 算法重構(gòu) Vivado 賽靈思

          評(píng)論


          相關(guān)推薦

          技術(shù)專區(qū)

          關(guān)閉
          看屁屁www成人影院,亚洲人妻成人图片,亚洲精品成人午夜在线,日韩在线 欧美成人 (function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https') { bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else { bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })();