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

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

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

【部分圖文】：

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

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

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

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

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



本文編號(hào)：3051261