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

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

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

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

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

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

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