面向圖搜索的流寄存器文件設(shè)計(jì)與協(xié)同BFS算法優(yōu)化.pdf

1、隨著信息時(shí)代的迅速發(fā)展，大數(shù)據(jù)應(yīng)用日益火熱。圖搜索問題是大數(shù)據(jù)應(yīng)用中的經(jīng)典問題，BFS算法是圖搜索中的核心算法也是Graph500測(cè)試基準(zhǔn)中的核心搜索程序。BFS算法具有訪存量大、運(yùn)算簡(jiǎn)單、每訪存字節(jié)操作比低的特征，另外地，BFS算法中的訪存呈現(xiàn)出不規(guī)律的特征，其時(shí)空局部性較差，這導(dǎo)致商用處理器中在運(yùn)行BFS算法時(shí)cache的失效率過高?；谏鲜隹紤]，課題組參考流處理器中的結(jié)構(gòu)，開發(fā)了多核交叉多線程的流處理器原型，用SRF來替代cach

2、e在存儲(chǔ)層次中的位置，然而在該原型中，一方面由于SRF延遲過高導(dǎo)致SRF的實(shí)際帶寬過低；另一方面由于算法訪存過多導(dǎo)致性能不高。本課題采用軟硬件協(xié)同優(yōu)化的方法，首先在商用處理器上對(duì)BFS算法進(jìn)行了分析和優(yōu)化，然后對(duì)流處理器原型中的SRF進(jìn)行了設(shè)計(jì)與實(shí)現(xiàn)，最后在該流處理器上對(duì)BFS算法進(jìn)行了設(shè)計(jì)和優(yōu)化，最終提高流處理器原型的性能。
　　首先，本文在商用處理器上對(duì)并行BFS算法進(jìn)行了分析和優(yōu)化。分別從減少訪問延遲、減少訪問次數(shù)、增大數(shù)據(jù)

3、的局部性等方面來減少訪存的開銷，以提高程序的性能。先后實(shí)現(xiàn)了混合算法、面向NUMA結(jié)構(gòu)的算法、采用數(shù)據(jù)預(yù)處理技術(shù)的算法，提出了關(guān)鍵數(shù)據(jù)結(jié)構(gòu)的混合表示的優(yōu)化方法，并通過pthread、OpenMP兩種并行編程語言進(jìn)行了實(shí)現(xiàn)，比較了在兩種語言下，各種優(yōu)化技術(shù)對(duì)算法的加速比。
　　然后，針對(duì)流處理器原型中SRF指令訪問延遲較高的問題，設(shè)計(jì)并實(shí)現(xiàn)了私有SRF和共享SRF兩種結(jié)構(gòu)。私有SRF結(jié)構(gòu)下SRF指令可以實(shí)現(xiàn)無延遲，共享SRF結(jié)構(gòu)可以

4、使核間在SRF中實(shí)現(xiàn)共享。文章重點(diǎn)對(duì)共享SRF結(jié)構(gòu)中的交叉開關(guān)進(jìn)行了設(shè)計(jì)，在無SRF體訪問沖突時(shí)，訪問并發(fā)度可以達(dá)到8。
　　最后，針對(duì)兩種不同SRF結(jié)構(gòu)的流處理器特征，分別設(shè)計(jì)了基于私有SRF結(jié)構(gòu)的BFS算法以及基于共享SRF結(jié)構(gòu)的BFS算法。在基于共享SRF的結(jié)構(gòu)中，重新設(shè)計(jì)了SRF指令格式，并設(shè)計(jì)了關(guān)鍵數(shù)據(jù)在SRF中的組織，對(duì)BFS算法進(jìn)行了優(yōu)化。實(shí)驗(yàn)測(cè)試表明，私有SRF結(jié)構(gòu)下，算法性能比原流處理器的算法性能提高了92％，共