賈子昂

(北方工業(yè)大學(xué) 電氣與控制工程學(xué)院,北京 100144)

0 引言

圖數(shù)據(jù)通常用來處理一些稀疏數(shù)據(jù),由于其具有較強的靈活性,被廣泛應(yīng)用在各行業(yè)中,而如何有效計算這些圖數(shù)據(jù)成為學(xué)術(shù)界目前急需解決的問題。傳統(tǒng)橫向優(yōu)先搜索算法是利用Graph500基準作為核心,通過Open-closed表來計算圖數(shù)據(jù),但其存在很多缺點,如數(shù)據(jù)處理局部性差、擴展性差、并行效率低等問題,在處理一些大型圖數(shù)據(jù)時很容易出現(xiàn)力不從心的現(xiàn)象。基于此,本文提出高通量計算機算法,其具有高并發(fā)、實時強、功耗低等特點。在計算一些大型圖數(shù)據(jù)時,這種算法表現(xiàn)出獨特的優(yōu)勢性。本文對BFS算法的性能進行了系統(tǒng)的評估,優(yōu)化后的BFS算法在高通量計算機上評價性能為24.26 GTEPS和兩路X86構(gòu)建服務(wù)器相比,單節(jié)點更具性能優(yōu)勢。

1 研究現(xiàn)狀

近些年,BFS算法優(yōu)化方面取得了較好的研究成果。在MAT平臺上,Bader等[1]通過進一步研究算法的并行度,采用多線程技術(shù)解決了訪存方面的問題；Agarwal等[2]部分人員對數(shù)據(jù)結(jié)構(gòu)進行升級,降低了數(shù)據(jù)的限制性,提高了算法效率；Beamer等[3]提出將遍歷算法和傳統(tǒng)算法相融合,實現(xiàn)方向性優(yōu)化,減少沉余訪存數(shù)據(jù),提高效率。目前,傳統(tǒng)的眾核體系結(jié)構(gòu)不能滿足BFS算法的運用,需要對傳統(tǒng)綜合體系結(jié)構(gòu)進行升級,滿足大規(guī)模離散隨機訪問和執(zhí)行機制,本研究降低緩存訪存,對Bottom-up算法深入優(yōu)化,提高了緩存數(shù)據(jù)的效率。

2 算法介紹

以下算法研究是以BFS算法為基礎(chǔ),其中主要有歷程優(yōu)化、去零點優(yōu)化和靜態(tài)優(yōu)化等。

2.1 歷程優(yōu)化

傳統(tǒng)的BFS算法是從頂向下運行,前期表現(xiàn)良好,中后期會逐漸出現(xiàn)沉余現(xiàn)象。Beamer等[3]提出從下向上的算法,減少沉余,該算法使用后綴數(shù)組的一個增強信息——LCP表,并通過堆棧模擬自底向上的遍歷。圖數(shù)據(jù)通常用來處理一些稀疏數(shù)據(jù),由于其具有較強的靈活性,被廣泛應(yīng)用于各個行業(yè),而如何有效計算這些圖數(shù)據(jù)成為學(xué)術(shù)界目前急需解決的問題。Bottom-up算法,具有工作期間優(yōu)先訪問沒有訪問頂點的優(yōu)點,一旦發(fā)現(xiàn)頂點被訪問,就會直接跳出循環(huán),減少沉余的訪存時間。現(xiàn)階段,有研究人員將這兩種方式結(jié)合,進一步提高BFS的效應(yīng)。

2.2 頂點排序優(yōu)化

頂點排序優(yōu)化主要是通過頂點索引來實施降序排列,從而提高訪存效率。但在處理較大圖數(shù)據(jù)時,由于數(shù)據(jù)的分布以冪的形式出現(xiàn),相鄰兩個頂點數(shù)據(jù)變化較大,處理數(shù)據(jù)需要耗費大量時間,影響執(zhí)行時間,甚至?xí)霈F(xiàn)負載不均勻現(xiàn)象[4]。

2.3 去零點優(yōu)化

研究表明,在kronecker圖當(dāng)中,有很多頂點都是孤立存在,這些孤立存在的定量占據(jù)總頂點量的40%～60%,且處于直線上升趨勢。從以上的算法看來,孤立頂點會產(chǎn)生大量無效訪存,從而去零點優(yōu)化能夠提升歷程效率[5]。

2.4 靜態(tài)shuffle優(yōu)化

靜態(tài)shuffle優(yōu)化主要是在頂點優(yōu)先排序的情況下,提高優(yōu)化效率的方式[6]。其算法輸入:segment num數(shù),采用排好序的row 緩存的old array；輸出:shuffle計算row緩存新的節(jié)點編號。

經(jīng)過以上循環(huán),發(fā)現(xiàn)靜態(tài)shuffle循環(huán)不但能夠保存數(shù)據(jù)信息,還能突破頂點數(shù)據(jù)排序的局限,避免了重新分配和調(diào)度,提高了內(nèi)存的利用率[7]。

2.5 度數(shù)感知優(yōu)化

Bottom-up算法遍歷中會掃描所有未訪問頂點的鄰居頂點,只要找到一個鄰居頂點在 currentfrontier 中,則結(jié)束對剩余鄰居節(jié)點的遍歷。如果終止的越早,則可以減少鄰居檢查的數(shù)量。在正常情況下,Bottom-up方法只需要檢查未訪問頂點的首要相鄰節(jié)點,就能滿足檢查要求,在后期工作中將跳過所有剩余的鄰居頂點。但從實際情況來看,工作人員根本無法確定鄰居列表的最佳順序,從而選擇不同的源頂點,鄰居列表的最佳順序很容易出現(xiàn)差異性。在經(jīng)過大量實驗發(fā)現(xiàn),頂點度數(shù)和訪問頻率之間的關(guān)聯(lián)性,頂點的度數(shù)越大,其訪問頻率越高,為了進一步提高訪存效率,將鄰接列表A 拆分為只含最高度數(shù)鄰居頂點的AB+與剩余按照度數(shù)降序排列的鄰接列表AB-,將算法1中的一次遍歷循環(huán)拆分為采用鄰接列表AB+與AB-的2次循環(huán)。實驗發(fā)現(xiàn),度數(shù)感知優(yōu)化可以極大地減少冗余邊的遍歷,提高數(shù)據(jù)訪問效率。

3 BFS算法優(yōu)化

3.1 基于快查找的地圖訪問

在實施BFS算法時,主要由位圖確定訪問狀態(tài),能夠提升最后一級緩存性能,減少DRAM訪問沉余,降低訪存消耗[8]。Bottom-up算法,是由順序掃描位圖來確定沒有訪問的頂點,通過Kronecker圖的特點,經(jīng)過連續(xù)多次Bottom-up的優(yōu)化后,將未訪問的頂點樹立減少,在處理大規(guī)模數(shù)據(jù)圖時,順序掃描會對位圖產(chǎn)生嚴重的影響。從以上情況,位圖訪問優(yōu)化能夠加強快速尋找未訪問頂點位置功能,如圖1所示。在位圖優(yōu)化時,位圖定位狀態(tài)能夠?qū)⒋至６茸鳛榕袛鄻藴蔥9]。現(xiàn)如今我國最先的處理器最大寬度為64位,能夠同時訪問64個點的狀態(tài),因此一個block的大小設(shè)置為64,傳統(tǒng)算法只能查找block中采用順序遍歷的方式,只有一個未訪問點,需要迭代block大小和次數(shù),影響找尋未訪問頂點的效率[7]。

圖1 未訪問頂點的快速遍歷示意

3.2 Bottom-up歷程優(yōu)化

Bottom-up歷程優(yōu)化主要是采用current-frontier功能,提高當(dāng)前頂點的活躍度；visit能夠自動將被遍歷過的頂點自動保存；next-frontier能放在下個活躍的頂點,每一個結(jié)點對應(yīng)后綴樹的一個內(nèi)部結(jié)點。有些應(yīng)用中,遍歷時需要知道每個結(jié)點信息。

4 結(jié)語

在信息化時代背景下,我國在2018就出現(xiàn)了高通量眾核體系結(jié)構(gòu)技術(shù)高通量計算機,又被稱為Hing-Throughput computer HTC。圖數(shù)據(jù)通常用于數(shù)據(jù)處理工作,在每個行業(yè)都有所涉及。因此,提高計算圖數(shù)據(jù)的效率成為現(xiàn)階段學(xué)術(shù)界的重要任務(wù)。傳統(tǒng)的橫向優(yōu)先搜索法是通過Graph500為核心測試程序,以openclose表為載體,但由于傳統(tǒng)橫向優(yōu)先搜索法具有處理數(shù)據(jù)局部性較差、效率低、擴展性差等特點,不能滿足大型圖數(shù)據(jù)處理需求。在新型的高通量計算機的圖算法優(yōu)化技術(shù)當(dāng)中,具有高并發(fā)、時效性強、功能消耗低等特征,能夠降低沉余訪存。在計算大型圖數(shù)據(jù)時,這種發(fā)算法具有較大的優(yōu)勢[10]。