高通量計(jì)算機(jī)的圖算法優(yōu)化技術(shù)研究

賈子昂

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

0 引言

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

1 研究現(xiàn)狀

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

2 算法介紹

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

2.1 歷程優(yōu)化

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

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

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

2.3 去零點(diǎn)優(yōu)化

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

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

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

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

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

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

3 BFS算法優(yōu)化

3.1 基于快查找的地圖訪問(wèn)

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

圖1 未訪問(wèn)頂點(diǎn)的快速遍歷示意

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

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

4 結(jié)語(yǔ)

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