面向眾核體系結(jié)構(gòu)的圖算法并行優(yōu)化技術(shù)研究.pdf

1、跨入新時(shí)代，計(jì)算機(jī)融入到人們生活的方方面面，隨之也產(chǎn)生了數(shù)量巨大的數(shù)據(jù)需要處理。云計(jì)算、物聯(lián)網(wǎng)、物理學(xué)、生物學(xué)、環(huán)境生態(tài)學(xué)等領(lǐng)域更需要對(duì)海量數(shù)據(jù)進(jìn)行挖掘和處理，這預(yù)示著我們進(jìn)入了“大數(shù)據(jù)”時(shí)代。“大數(shù)據(jù)”時(shí)代處理的數(shù)據(jù)量非常大，數(shù)據(jù)種類繁多，對(duì)數(shù)據(jù)處理提出了新的挑戰(zhàn)。
　　圖提供了非結(jié)構(gòu)化數(shù)據(jù)的自然表現(xiàn)，是大數(shù)據(jù)的一種非常有效的表示方法。圖的遍歷是一種基礎(chǔ)的圖形算法在社交網(wǎng)絡(luò)、商業(yè)分析、高性能計(jì)算等領(lǐng)域有廣泛應(yīng)用的圖形算法。在單節(jié)

2、點(diǎn)上圖的遍歷已經(jīng)被研究和優(yōu)化的非常完善。目前異構(gòu)計(jì)算正變得越來(lái)越流行，而CPU+MIC是一種典型的異構(gòu)體系結(jié)構(gòu)。Intel的MIC（Many Integrated Core）是一種為高并行計(jì)算設(shè)計(jì)的眾核協(xié)處理器，它擁有大約60個(gè)核心。在圖的遍歷方面，MIC還沒(méi)有被很好的利用起來(lái)。同時(shí)圖具有：小世界性、無(wú)標(biāo)度性、社區(qū)結(jié)構(gòu)等屬性。即一部分頂點(diǎn)的度較小，另一部分頂點(diǎn)的度非常大。因此當(dāng)用MIC來(lái)遍歷圖形時(shí)，劃分到MIC各個(gè)核心的頂點(diǎn)的度差別會(huì)很

3、大。經(jīng)量化分析證明MIC處理并行圖算法存在很嚴(yán)重的負(fù)載不平衡現(xiàn)象，這會(huì)對(duì)系統(tǒng)的性能造成不利影響。
　　本文將提出一種算法設(shè)計(jì)和優(yōu)化技術(shù)來(lái)改善MIC上的負(fù)載不平衡現(xiàn)象。關(guān)于這一優(yōu)化設(shè)計(jì)，它的核心思想是將度高的點(diǎn)和度低的點(diǎn)區(qū)分處理。為了實(shí)現(xiàn)這一思想，本文還提出一種改進(jìn)的數(shù)據(jù)結(jié)構(gòu)，以達(dá)到將胖節(jié)點(diǎn)和瘦節(jié)點(diǎn)區(qū)分處理的目的。通過(guò)這些優(yōu)化措施，相較于未經(jīng)優(yōu)化的算法優(yōu)化算法獲得了非常高的性能提升。同時(shí)我們相信這一新穎的算法將會(huì)得到廣泛的應(yīng)用，特別

4、是對(duì)擁有多個(gè) MIC的大規(guī)模并行系統(tǒng)中。
　　本文主要包括以下幾個(gè)方面的研究工作：
　?。?）MIC是一種超多核心架構(gòu)的處理器，在處理并行圖算法時(shí)存在嚴(yán)重的負(fù)載不均衡現(xiàn)象。針對(duì)這一負(fù)載不均衡現(xiàn)象，本文做了深入的量化分析。首先在單一節(jié)點(diǎn)上采用方向優(yōu)化的策略在MIC上實(shí)現(xiàn)并行BFS算法，統(tǒng)計(jì)出規(guī)模是20每次BFS第三層的最大邊差（處理邊數(shù)最多的核的邊數(shù)減去處理邊數(shù)最少的核的邊數(shù)）和最大邊差比（處理邊數(shù)最多的核的邊數(shù)減去處理邊數(shù)最

5、少的核的邊數(shù)除以每個(gè)核處理的平均邊數(shù)）。通過(guò)對(duì)這兩個(gè)參數(shù)的分析，量化地分析了MIC處理并行圖算法的負(fù)載不均衡現(xiàn)象。
　?。?）本文主要研究如何減輕MIC上各核處理并行BFS時(shí)的負(fù)載不均衡現(xiàn)象。圖形頂點(diǎn)度的差異是造成MIC負(fù)載不均衡的關(guān)鍵因素，因此對(duì)MIC的優(yōu)化的關(guān)鍵是將胖節(jié)點(diǎn)和瘦節(jié)點(diǎn)區(qū)分出來(lái)處理。即選擇圖中度大的若干頂點(diǎn)組成胖節(jié)點(diǎn)集合，剩下的度小的頂點(diǎn)組成瘦節(jié)點(diǎn)集合。然后將胖節(jié)點(diǎn)均勻的分配到MIC的各個(gè)核，進(jìn)行并行寬度優(yōu)先搜索。再

6、將瘦節(jié)點(diǎn)均勻的分配到MIC的各個(gè)核，進(jìn)行并行寬度優(yōu)先搜索。在進(jìn)行寬度優(yōu)先搜索時(shí)，采用雙向搜索的優(yōu)化策略。即在對(duì)胖節(jié)點(diǎn)和瘦節(jié)點(diǎn)分別進(jìn)行并行BFS處理的同時(shí)，對(duì)算法進(jìn)行雙向搜索的優(yōu)化，算法性能取得了很大提升。
　?。?）同時(shí)本文設(shè)計(jì)算法將單節(jié)點(diǎn)的優(yōu)化方法推廣到大規(guī)模并行系統(tǒng)上。設(shè)計(jì)采用一維和二維的圖劃分方法，節(jié)點(diǎn)間的劃分方式不變，對(duì)每個(gè)節(jié)點(diǎn)內(nèi)的MIC運(yùn)用上述方法進(jìn)行負(fù)載均衡優(yōu)化。通過(guò)提高每個(gè)MIC的性能，提高整個(gè)系統(tǒng)的性能。同時(shí)采用w