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

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

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

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

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