近年來,人們?cè)絹碓疥P(guān)注計(jì)算機(jī)對(duì)數(shù)據(jù)密集型課題的處理能力。寬度優(yōu)先搜索（Breadth First Search,BFS）是一種典型的數(shù)據(jù)密集型課題,被廣泛應(yīng)用于多種圖算法。Graph 500 Benchmark以BFS搜索為核心算法,已經(jīng)成為評(píng)價(jià)計(jì)算機(jī)處理大數(shù)據(jù)能力的基準(zhǔn)。神威太湖之光超級(jí)計(jì)算機(jī)從2016年6月至2017年11月連續(xù)4次榮登Top 500榜單榜首,其處理器SW26010是首款由我國自主研制的異構(gòu)眾核處理器。文中研究了如何利用SW26010的體系結(jié)構(gòu)特點(diǎn)加速BFS算法的問題,在SW26010上實(shí)現(xiàn)了基于單個(gè)核組的方向優(yōu)化的融合BFS算法,使用字節(jié)圖（bytemap）釋放內(nèi)層循環(huán)依賴性,利用異步DMA隱藏計(jì)算與便簽存儲(chǔ)器的訪問開銷,利用異構(gòu)架構(gòu)協(xié)同運(yùn)算并對(duì)圖做預(yù)處理。最終,以Graph 500作為基準(zhǔn)測(cè)試程序處理scale為22的圖,SW26010處理器單核組BFS的性能達(dá)到457.54MTEPS。 

【文章來源】：計(jì)算機(jī)科學(xué). 2020,47(08)北大核心

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

【部分圖文】：

SW26010 運(yùn)算的核心簇結(jié)構(gòu)

使用bitmap可以壓縮BFS算法中In,Out和Vis數(shù)組的存儲(chǔ)空間,進(jìn)而增加這些數(shù)據(jù)的局部性;還能并行判斷64個(gè)頂點(diǎn)是否都在Frontier中或都沒有被訪問過,從而降低循環(huán)開銷。但對(duì)于SW26010這種眾核架構(gòu),CSR格式下,使用bitmap會(huì)在TD算法中產(chǎn)生競(jìng)爭(zhēng)問題:1)如果將bitmap放在從核陣列中,須寫其他從核的SPM,目前硬件不支持RDMA,而寄存器通信必須收發(fā)雙方顯式配對(duì),不適合TD算法的需求。2) 如果將bitmap放在主存中,從核陣列內(nèi)多個(gè)核心有可能同時(shí)試圖改寫Out數(shù)組,進(jìn)而產(chǎn)生“讀-修改-寫”競(jìng)爭(zhēng)。若兩個(gè)從核恰好同時(shí)試圖將Out中屬于同一字節(jié)的兩個(gè)不同比特位置1,則后完成的寫操作會(huì)覆蓋稍前完成的操作,造成某些比特位置1失敗。如圖3所示,Bytek的正確值應(yīng)當(dāng)是0x84,但當(dāng)競(jìng)爭(zhēng)出現(xiàn)時(shí),Bytek的值變?yōu)?x04或0x80。因此,為保證結(jié)果的正確性,TD算法對(duì)Out數(shù)組執(zhí)行置1操作時(shí)必須使用鎖,這將導(dǎo)致TD算法內(nèi)層循環(huán)“串行化”,效率較低。為避免使用鎖,在SW26010上設(shè)計(jì)實(shí)現(xiàn)了兩種topdown算法:利用bitmap結(jié)合父親樹中特殊標(biāo)記的tag-TD算法(算法3)和利用bytemap表示主存中Out數(shù)組的bytemap-TD算法(算法4)。

SW26010的基本結(jié)構(gòu)[13]

【參考文獻(xiàn)】：
期刊論文
[1]The Sunway Taihu Light supercomputer:system and applications[J]. Haohuan FU,Junfeng LIAO,Jinzhe YANG,Lanning WANG,Zhenya SONG,Xiaomeng HUANG,Chao YANG,Wei XUE,Fangfang LIU,Fangli QIAO,Wei ZHAO,Xunqiang YIN,Chaofeng HOU,Chenglong ZHANG,Wei GE,Jian ZHANG,Yangang WANG,Chunbo ZHOU,Guangwen YANG.  Science China（Information Sciences）. 2016(07)



本文編號(hào)：2998760