面向眾核體系結(jié)構(gòu)的寬度優(yōu)先搜索算法研究.pdf

1、寬度優(yōu)先搜索（Breadth-first Search，簡稱BFS）是一種基礎(chǔ)的圖形算法，是眾多算法的核心組件，在大量領(lǐng)域中得到廣泛應(yīng)用，如網(wǎng)絡(luò)安全、醫(yī)學信息、數(shù)據(jù)挖掘、社交網(wǎng)絡(luò)、語義網(wǎng)等等。寬度優(yōu)先搜索算法還是一種典型的數(shù)據(jù)密集型應(yīng)用，Graph500即使用其對超級計算機處理數(shù)據(jù)密集型應(yīng)用的能力進行排名。近年來，得益于較低的功耗和較高的性價比，眾核體系結(jié)構(gòu)的加速器在高性能計算領(lǐng)域得到廣泛應(yīng)用。MIC（Many Integreated

2、Core）作為最新的眾核體系結(jié)構(gòu)協(xié)處理器，相對于其它加速器來說，具有和傳統(tǒng)并行編程模型兼容的優(yōu)勢。隨著采用CPU+MIC的“天河二號”登上Top500榜首，MIC在高性能計算領(lǐng)域得到廣泛重視。寬度優(yōu)先搜索算法的并行實現(xiàn)具有數(shù)據(jù)競爭較嚴重、問題不規(guī)則和訪存局部性差等特點，而MIC具有大量線程和寬向量處理能力且每線程的平均緩存較小，因而要充分發(fā)揮MIC硬件的優(yōu)勢高效實現(xiàn)寬度優(yōu)先搜索，將面臨線程間競爭開銷較大，向量部件利用率不高，緩存利用率差

3、等問題。
　　本研究主要內(nèi)容包括：⑴設(shè)計并實現(xiàn)了自上向下和自下向上相結(jié)合的混合BFS算法。該算法根據(jù)圖形的特點，在不同的搜索層使用不同的搜索策略，能夠結(jié)合兩種搜索策略的優(yōu)勢，性能分別為自上向下和自下向上策略的3.21和2.15倍。⑵提出了一種面向MIC優(yōu)化的多線程BFS算法。該算法以混合BFS算法為基礎(chǔ)，通過減少數(shù)據(jù)競爭，消除原子操作，并采用動靜相結(jié)合的線程調(diào)度方式，能夠很好地利用MIC提供的大量線程處理能力。⑶提出了一種使用寬向

4、量部件進一步加速BFS的方法。該方法在自上向下搜索部分采用SIMD指令同時掃描頂點的鄰居，在自下向上搜索部分采用SIMD指令并行查找未訪問的頂點，能夠進一步加速BFS算法，最高加速比達到1.85。⑷設(shè)計并實現(xiàn)了CPU和MIC協(xié)同計算的異構(gòu)混合BFS算法。該算法以混合BFS算法為基礎(chǔ)，在搜索層中任務(wù)較多時采用CPU和MIC協(xié)同計算，通過比例可調(diào)的任務(wù)劃分方法以及重疊計算的通信設(shè)計，解決了協(xié)同計算中任務(wù)不均衡和通信開銷較大的問題，相對于CP