為了實現(xiàn)由軟件和硬件執(zhí)行小世界圖搜索的加速器系統(tǒng),提出了一種在單芯片F(xiàn)PGA-CPU異構(gòu)硬件平臺上基于廣度優(yōu)先搜索算法實現(xiàn)的混合加速器系統(tǒng)設(shè)計;提出了采用線性代數(shù)語言實現(xiàn)的BFS;提出了一種處理單元結(jié)構(gòu),它由一個負責(zé)與主存儲器全部交互的后端、用于執(zhí)行布爾塥運算的前端和一個距離生成器構(gòu)成;在ZedBoard平臺上設(shè)計了一種采用Xilinx Zynq Z7020 FPGA-CPU混合結(jié)構(gòu)的實際加速器系統(tǒng)。實驗結(jié)果表明,設(shè)計的混合加速器不僅能夠?qū)崿F(xiàn)小世界圖的快速搜索,而且相比于目前其他先進的基于BFS算法的混合加速器結(jié)構(gòu)有更好的加速性能。 

【文章來源】：火力與指揮控制. 2019,44(10)北大核心

【文章頁數(shù)】：6 頁

【部分圖文】：

稀疏xt的內(nèi)存請求結(jié)構(gòu)

痹げ獾腂FS步長時間對于FPGA更短時，就切換到FPGA執(zhí)行。利用密集變量的可預(yù)測性來建模它的執(zhí)行時鐘周期如下：（1）式中，β是利用的帶寬部分。FPGA繼續(xù)執(zhí)行直至前沿尺寸下降到低于全部圖節(jié)點的θ%。之后，軟件BFS接管直到搜索終止。β，θ憑經(jīng)驗確定。3實驗結(jié)果為了評價本文提出的加速器系統(tǒng)，采用Graph500基準參數(shù)（A=0.57，B=0.19，C=0.19）［1，4］綜合生成的RMAT圖，把一個具有規(guī)模S（2S個節(jié)點）和邊因子E（E×2s條邊）的RMAT圖稱為RMAT-S-E。3.1軟件BFS和基于BFS的稀疏和密集變量加速器性能比較圖4RMAT-19-32上加速器和軟件BFS每步執(zhí)行時間先比較基于BFS的稀疏和密集變量加速器與BFS軟件算法的性能。對于2種加速器變量，在有相等數(shù)目（4）的PE和時鐘頻率（100MHz）的RMAT-·98·1770

（總第44-）火力與指揮控制2019年第10期何時讀取新的輸入向量元素。一個為0的輸入向量值意味著邊來自于一個還未被訪問過的節(jié)點，而且這個數(shù)據(jù)被簡單地丟棄而無需進一步運算。加速器的控制和狀態(tài)接口通過內(nèi)存映射寄存器提供。虛線表示只在距離生成操作期間是激活的圖2密集xt處理單元的體系結(jié)構(gòu)2）稀疏x變量：根據(jù)整體架構(gòu)，稀疏xt變量與密集xt變量是相同的，除了它不需要輸入向量FIFO（因為稀疏處理意味著全部xt值是1）部分。圖3所示為稀疏xt后端的內(nèi)部結(jié)構(gòu)，與密集xt變量本質(zhì)上是不同的。稀疏輸入向量是通過前沿濾波器內(nèi)部生成，它掃描距離數(shù)組的值，并發(fā)送索引值，全部值被寫入在先前的BFS步驟中。之后，每個生成索引的開始和結(jié)束指針被請求，這兩個指針用于請求該節(jié)點的邊數(shù)據(jù)，并生成前端的邊計數(shù)信息。圖3稀疏xt變量的后端結(jié)構(gòu)3）失速y寫入：為了保持加速器運行而無停頓，前端能夠如后端生成數(shù)據(jù)一樣快地消耗數(shù)據(jù)是很重要的，因此，可以抽取出前端的功能作為處理一個流寫入到隨機地址。如果結(jié)果向量被存儲在DRAM中，則連接的寫請求緩存器和存儲控制器可能填滿并暫停整個加速器。為了避免這種情況，解決方案是利用向量表示的稀疏性。由于本文的方法要求僅保留每個圖節(jié)點的1位，故可以有效地利用片上RAM的雙端口FPGA，在每個周期提供2個非�？斓碾S機訪問。4）距離生成器：在每個BFS步驟完成后，調(diào)用距離生成器來執(zhí)行DistGen。這涉及到比較輸入和結(jié)果向量，并找到從未被訪問過的節(jié)點到訪問過的節(jié)點。這些節(jié)點的索引被傳遞給后端作為實際寫當(dāng)前BFS距離到對應(yīng)的存儲位置，并為密集變量的下一個BFS步驟更新x向量。2.5一個實際加速器系統(tǒng)的構(gòu)建本文構(gòu)建的加速器系統(tǒng)采用XilinxZynqZ7020FPGA

【參考文獻】：
博士論文
[1]面向異構(gòu)體系結(jié)構(gòu)的稀疏矩陣算法研究[D]. 鄒丹.國防科學(xué)技術(shù)大學(xué) 2013

碩士論文
[1]EGPU處理單元的研究與設(shè)計[D]. 汪洋.山東大學(xué) 2016
[2]基于GPU/多核CPU平臺下并行計算的實時超分辨和立體視圖生成[D]. 孫增增.西安電子科技大學(xué) 2014



本文編號：3051261