面向圖搜索的流加速部件片上數(shù)據(jù)通路的設(shè)計(jì)、實(shí)現(xiàn)及性能優(yōu)化.pdf

1、近年來，信息社會(huì)的飛速發(fā)展引發(fā)了數(shù)據(jù)規(guī)模的爆炸式增長(zhǎng)，大數(shù)據(jù)問題逐漸引起了研究者的廣泛關(guān)注。然而，大數(shù)據(jù)問題表現(xiàn)出與傳統(tǒng)科學(xué)計(jì)算問題不同的負(fù)載特性，使得通用處理器面臨嚴(yán)峻挑戰(zhàn)。圖問題是大數(shù)據(jù)中的典型問題，在分析大數(shù)據(jù)集中數(shù)據(jù)對(duì)象間的關(guān)系中扮演著重要角色，尤其是以BFS算法為代表的圖搜索算法，更是廣泛存在于社交網(wǎng)絡(luò)、人工智能等眾多領(lǐng)域?？紤]到流處理器高性能、高效能等特點(diǎn)，探索基于流體系結(jié)構(gòu)解決圖搜索大數(shù)據(jù)問題具有重要的意義。因此，本課題以

2、特定的流加速部件為研究平臺(tái)，面向圖搜索大數(shù)據(jù)問題，研究其片上數(shù)據(jù)通路的設(shè)計(jì)和優(yōu)化。
　　針對(duì)該流加速部件，本文在深入分析其執(zhí)行圖搜索算法時(shí)負(fù)載特性的基礎(chǔ)上，重點(diǎn)研究了其片上數(shù)據(jù)通路的設(shè)計(jì)與優(yōu)化，主要從以下四個(gè)方面展開研究：
　　第一，針對(duì)已有流處理器中的SRF數(shù)據(jù)通路，分析其在解決圖搜索問題時(shí)多線程訪問SRF激烈競(jìng)爭(zhēng)的不足，提出了多體多控制器的SRF結(jié)構(gòu)，增加SRF的并行度，并基于AXI協(xié)議實(shí)現(xiàn)了SRF中的體與處理器中的核之

3、間的交叉互連。該數(shù)據(jù)通路能夠均衡處理多線程訪問SRF的請(qǐng)求，且具有較好的吞吐帶寬，有效適應(yīng)了處理器核對(duì)SRF的細(xì)粒度訪問。
　　第二，通過深入分析該流加速部件在執(zhí)行圖搜索算法時(shí)訪問SRF的負(fù)載特性，進(jìn)一步優(yōu)化SRF數(shù)據(jù)通路，提出了處理器核私有SRF中的體方法，避免了它們之間復(fù)雜的交叉互連，提升了流加速部件的整體性能。
　　第三，分析已有流處理器中的訪存數(shù)據(jù)通路，針對(duì)其不適合多線程細(xì)粒度訪存的問題，設(shè)計(jì)了基于消息包的高并發(fā)、低

4、延遲的訪存數(shù)據(jù)通路，該方法不僅能夠均衡處理各線程的訪存請(qǐng)求，而且也具有較好的訪存帶寬和延遲，滿足了多線程處理圖搜索問題的需求。
　　第四，針對(duì)圖搜索算法中共享數(shù)據(jù)一致性的問題，首先探索了通過加解鎖SPM來維護(hù)一致性的方法，但發(fā)現(xiàn)該方法會(huì)導(dǎo)致訪問SPM的激烈沖突。然后，進(jìn)一步研究了多線程執(zhí)行圖搜索算法時(shí)訪問共享數(shù)據(jù)的特性，提出了在訪存數(shù)據(jù)通路中加入事務(wù)型訪存的機(jī)制，通過原子性操作內(nèi)存中的共享數(shù)據(jù)來保護(hù)其一致性，避免了頻繁訪問SPM的