基于高通量計(jì)算機(jī)的圖算法優(yōu)化技術(shù)分析*

江西工程學(xué)院智能制造與能源工程學(xué)院 曾宏志

隨著現(xiàn)代化信息技術(shù)的發(fā)展及廣泛應(yīng)用,使得圖數(shù)據(jù)得到了迅速的增長,因此如何準(zhǔn)確、快速的對各種圖數(shù)據(jù)進(jìn)行處理成為了主要研究的問題。寬度優(yōu)先搜索算法(BFS)是一種解決圖遍歷問題的主要算法,其優(yōu)化算法取得了重要的進(jìn)展。高通量計(jì)算機(jī)是一種利用ARM架構(gòu)的體系,具有低功耗、實(shí)時(shí)性強(qiáng)等特點(diǎn),能夠應(yīng)用在大規(guī)模的圖計(jì)算當(dāng)中。本文介紹了BFS算法過程,在BFS算法的基礎(chǔ)上,提出了兩種基于高通量計(jì)算機(jī)的圖算法優(yōu)化技術(shù),極大的提升了算法的訪問速度。

0 引言

圖數(shù)據(jù)能夠快速、靈活的處理大量的、稀疏的數(shù)據(jù),并且完成大數(shù)據(jù)的實(shí)時(shí)分析,被廣泛的應(yīng)用在知識(shí)圖譜、交通網(wǎng)絡(luò)等方面。由于圖數(shù)據(jù)的迅速增加,如何對圖數(shù)據(jù)進(jìn)行快速的處理成為了目前研究的重要內(nèi)容。寬度優(yōu)先搜索(Breadth First Search,BFS)算法主要利用Graph500基準(zhǔn)的核心測試程序,是一種典型的圖遍歷方法,但是具有訪存比低、擴(kuò)展性差等一系列缺陷,不能較好的處理大規(guī)模的圖數(shù)據(jù)[1]。高通量計(jì)算機(jī)應(yīng)用了高通量眾核體系結(jié)構(gòu),具有低功耗、實(shí)時(shí)性強(qiáng)等特點(diǎn),因此可以應(yīng)用在大規(guī)模、密集性的數(shù)據(jù)處理當(dāng)中。因此,對基于高通量計(jì)算機(jī)的圖算法優(yōu)化技術(shù)進(jìn)行研究具有重要的意義。

1 相關(guān)工作

為了進(jìn)一步提高性能,降低功耗,BFS并行算法得到了許多學(xué)者的廣泛關(guān)注,目前,主要研究內(nèi)容包括分布式系統(tǒng)、共享內(nèi)存系統(tǒng)以及GPU等,相關(guān)的BFS優(yōu)化算法也得到了創(chuàng)新和發(fā)展[2]。針對現(xiàn)階段BFS算法當(dāng)中存在的負(fù)載不均衡以及局限性等缺陷,本文在以上優(yōu)化算法的基礎(chǔ)上,提出了基于塊查找的位圖訪問優(yōu)化算法,極大的提升了訪存效率。同時(shí),對Bottom-up算法的遍歷過程進(jìn)行創(chuàng)新,從而解決傳統(tǒng)算法當(dāng)中數(shù)據(jù)處理的局限性問題。

2 算法介紹

2.1 歷程優(yōu)化

BFS算法可以看做一種自頂而下的歷程優(yōu)化算法,在遍歷的時(shí)候會(huì)存在很多的冗余遍歷。自下而上的算法,能夠在一定程度上減少冗余。Bottom-up算法能夠在各層優(yōu)先對沒有訪問的頂點(diǎn)(行(8))進(jìn)行處理,當(dāng)頂點(diǎn)已經(jīng)被訪問時(shí)則跳出循環(huán)過程,對其余的頂點(diǎn)進(jìn)行查找,極大的減短了冗余的訪問時(shí)間。另外,在后續(xù)的研究過程中,進(jìn)一步強(qiáng)化了BFS算法的性能。

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

Kronecker生成圖當(dāng)中具有較多的孤立頂點(diǎn),即頂點(diǎn)位置的出度等于0,根據(jù)研究結(jié)果,孤立頂點(diǎn)的數(shù)量在生成圖當(dāng)中大約占據(jù)50%,且頂點(diǎn)規(guī)模越大數(shù)量越多。在遍歷的時(shí)候,先找到?jīng)]有訪問的頂點(diǎn),再在這些頂點(diǎn)當(dāng)中搜索節(jié)點(diǎn)。在對每層遍歷的時(shí)候,孤立頂點(diǎn)的產(chǎn)生會(huì)存在無效遍歷以及無效訪問等問題,所以必須進(jìn)行去零點(diǎn)優(yōu)化操作,從而提升遍歷的速度。

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

利用頂點(diǎn)度數(shù)將頂點(diǎn)完成降序排列,把低索引和高度數(shù)的頂點(diǎn)相結(jié)合,從而解決局部性等問題,提升訪存速度。然而由于圖數(shù)據(jù)分布呈現(xiàn)冪律分布,所以在對塊粒度大的數(shù)據(jù)進(jìn)行處理時(shí),使得不同度數(shù)塊的處理時(shí)間存在較大的差異,存在明顯的負(fù)載不均等問題。而對于塊粒度較小的數(shù)據(jù),雖然可以解決負(fù)載不均衡的問題,然而線程調(diào)度會(huì)提升操作時(shí)的成本以及時(shí)間,降低整體的性能。

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

對于高通量計(jì)算機(jī)高并發(fā)的結(jié)構(gòu)特征,提出靜態(tài)Shuffle優(yōu)化算法,主要是以頂點(diǎn)優(yōu)先排序的原則基礎(chǔ)上,進(jìn)行度數(shù)輪詢分配的優(yōu)化算法,不僅解決了負(fù)載均衡的問題,而且提升了高通量計(jì)算機(jī)中BFS算法的效果[3]。靜態(tài)Shuffle優(yōu)化算法的具體過程為:對于圖數(shù)據(jù)中的存儲(chǔ)結(jié)構(gòu),根據(jù)度數(shù)降序的原則對行列表當(dāng)中的頂點(diǎn)進(jìn)行排列,通過輪詢的形式把頂點(diǎn)放置在各個(gè)數(shù)組當(dāng)中,確保不同度數(shù)頂點(diǎn)在各個(gè)線程當(dāng)中分布的均衡性,同時(shí)將頂點(diǎn)按照降序的原則在線程數(shù)據(jù)中進(jìn)行排列,并且實(shí)現(xiàn)新頂點(diǎn)向舊頂點(diǎn)的映射,以便在完成圖遍歷之后恢復(fù)相關(guān)的圖數(shù)據(jù)。通過靜態(tài)Shuffle循環(huán),不僅能夠保存頂點(diǎn)的數(shù)據(jù)信息,防止出現(xiàn)由于線程調(diào)度產(chǎn)生的開銷問題,及時(shí)的調(diào)整與優(yōu)化動(dòng)態(tài)分配過程中的塊粒度值,而且還解決了頂點(diǎn)數(shù)據(jù)排序中的局限性問題,極大的提升了利用效率。

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

在遍歷的過程中,Bottom-up算法能夠獲取沒有進(jìn)行訪問的頂點(diǎn)的鄰居頂點(diǎn),當(dāng)尋找到一個(gè)鄰居節(jié)點(diǎn)的時(shí)候則停止遍歷過程,結(jié)束越早,遍歷時(shí)間越短。Bottom-up算法能夠檢測到?jīng)]有訪問的頂點(diǎn)的第一個(gè)鄰居節(jié)點(diǎn),可以直接跳過其余的頂點(diǎn),但是在實(shí)際操作過程中,不能明確鄰居頂點(diǎn)的排序位置,其最佳順序存在較大的差異性[4]。基于此,為了提升訪存效率,即:訪問次數(shù)隨著頂點(diǎn)度數(shù)的增大而增加,提出了度數(shù)感知優(yōu)化算法,能夠在一定程度上降低冗余遍歷次數(shù),同時(shí)提升數(shù)據(jù)的訪問頻率。

3 BFS算法的優(yōu)化處理

針對BFS算法不能較好的處理大規(guī)模的圖數(shù)據(jù)這一問題,根據(jù)高通量計(jì)算機(jī)的結(jié)構(gòu)特征以及相關(guān)的優(yōu)化算法,本文提出了基于塊查找的位圖訪問以及Bottom-up歷程優(yōu)化算法,極大的提升了BFS算法在高通量計(jì)算機(jī)當(dāng)中的應(yīng)用性能。

3.1 基于塊查找的位圖訪問

在進(jìn)行遍歷的時(shí)候,BFS算法通過位圖的方式記錄頂點(diǎn)的情況。位圖屬于數(shù)據(jù)結(jié)構(gòu)類型,能夠放置最后一級(jí)緩存當(dāng)中,減少了訪存的時(shí)間及成本。對于Bottom-up算法,遍歷時(shí)對Visit位圖進(jìn)行掃描以便搜索沒有訪問的頂點(diǎn)。在Kronecker生成圖當(dāng)中,算法經(jīng)過迭代會(huì)減少?zèng)]有訪問的頂點(diǎn)的數(shù)量,具有稀疏的特性。因此,對于大規(guī)模的圖數(shù)據(jù),通過掃描Visit位圖有著明顯的性能改善。

針對上述問題,本文提出基于塊(Block)查找的Visit位圖訪問算法,利用Bottom-up算法遍歷的過程中,可以較快的得出沒有訪問的頂點(diǎn)在塊當(dāng)中的具體位置。未訪問頂點(diǎn)的快速遍歷過程如圖1所示。

圖1 未訪問頂點(diǎn)的快速遍歷過程Fig.1 Fast traversal of unvisited vertices

在進(jìn)行遍歷時(shí),以Block為單位,對Visit位圖的頂點(diǎn)情況進(jìn)行判斷。一般而言,在處理器當(dāng)中,通用寄存器的位寬是64位,因此能夠顯示出64個(gè)頂點(diǎn)的訪問情況,所以可以將一個(gè)“塊”的面積設(shè)置成64。進(jìn)行遍歷的時(shí)候,把Visit位圖里面第i個(gè)Block的訪問情況加入到通用寄存器Block_Visit當(dāng)中,再把其中的整型變量進(jìn)行取反操作,從而獲得寄存器變量Block_no_visit,當(dāng)寄存器變量顯示0時(shí),說明Block當(dāng)中沒有未訪問的頂點(diǎn),可以選擇跳過對頂點(diǎn)情況的訪問;而當(dāng)寄存器變量存在除0之外的數(shù)據(jù),則可以基于塊查找對頂點(diǎn)實(shí)現(xiàn)快速定位。

在寄存器變量當(dāng)中尋找未訪問頂點(diǎn),循環(huán)的次數(shù)和比特位等于1的數(shù)量存在關(guān)聯(lián),但是和Block沒有關(guān)系。但是對于傳統(tǒng)的算法,在進(jìn)行順序遍歷的過程中,遍歷Block大小的次數(shù)也會(huì)影響到訪問的性能。針對BFS算法局部性差、訪存效率低等問題,提出基于塊查找的位圖訪問優(yōu)化算法,把Block的位移入到寄存器當(dāng)中,能夠降低對Cache的訪問次數(shù),減少錯(cuò)誤的發(fā)生。

從算法優(yōu)化前后頂點(diǎn)遍歷數(shù)量的對比結(jié)果能夠得出:當(dāng)遍歷第五次時(shí),存在99.8%的頂點(diǎn)是已經(jīng)訪問的情況,Visit位圖出現(xiàn)很多無效的訪存。當(dāng)對Visit位圖進(jìn)行優(yōu)化后,根據(jù)Block為單位進(jìn)行粗粒度的判別,基于塊查找的位圖訪問優(yōu)化算法能夠快速、準(zhǔn)確的找到未訪問的頂點(diǎn),且和傳統(tǒng)的方式相比較,可以減少98.4%的頂點(diǎn)判斷,從而提高了遍歷的速度。

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

Bottom-up歷程優(yōu)化算法是在Bottom-up算法的基礎(chǔ)上進(jìn)行改進(jìn),利用current-frontier等結(jié)構(gòu)來存儲(chǔ)遍歷時(shí)的數(shù)據(jù)信息。其中,current-frontier用來提升頂點(diǎn)的活躍程度,Visit保存遍歷好的頂點(diǎn),而next-frontier保存下次遍歷的活躍頂點(diǎn)。利用Visit圖能夠節(jié)約數(shù)據(jù)結(jié)構(gòu)的應(yīng)用,在遍歷時(shí)不需要對該層活躍的頂點(diǎn)進(jìn)行訪問,從而把Bottom-up算法當(dāng)中應(yīng)用的三個(gè)數(shù)據(jù)結(jié)構(gòu)減少為兩個(gè),極大的提升了訪存的速度。此外,根據(jù)度數(shù)感知優(yōu)化算法,針對Bottom-up算法的性能缺陷,把鄰接列表A分別AB+(度數(shù)高的鄰接頂點(diǎn))和AB-(度數(shù)降序排列的其余頂點(diǎn)),對兩個(gè)相鄰的列表進(jìn)行遍歷,從而提升鄰居頂點(diǎn)的搜索速度,提高數(shù)據(jù)的訪存效率。

對算法在鄰接列表的AB+和AB-遍歷效率進(jìn)行分析,頂點(diǎn)規(guī)模為226(其中,26表示規(guī)模,即頂點(diǎn)數(shù)為226)時(shí)該算法遍歷后的頂點(diǎn)數(shù)量,可以得出:Bottom-up算法在遍歷的過程中,鄰接列表AB+更新的頂點(diǎn)數(shù)量達(dá)到96.14%,且隨著遍歷層數(shù)的增加,活躍頂點(diǎn)數(shù)量也在上升。在第三次遍歷時(shí),全部的活躍頂點(diǎn)均利用鄰接列表的AB+完成更新。所以,對于Bottom-up歷程優(yōu)化算法,可以把鄰接列表AB+和AB-進(jìn)行合并,僅進(jìn)行一次遍歷過程,不但能夠保證AB+的局部性,而且避免出現(xiàn)AB-中數(shù)據(jù)的無效訪存等問題。

4 結(jié)論

針對BFS算法不能較好的處理大規(guī)模的圖數(shù)據(jù)這一問題,根據(jù)高通量計(jì)算機(jī)的結(jié)構(gòu)特征以及相關(guān)的優(yōu)化算法,本文提出了基于塊查找的位圖訪問以及Bottom-up歷程優(yōu)化算法,極大的提升了BFS算法在高通量計(jì)算機(jī)當(dāng)中的應(yīng)用性能。通過對優(yōu)化算法在高通量計(jì)算機(jī)當(dāng)中的性能評(píng)估,可以得到:對于性能而言,與x86服務(wù)器相比較,高通量計(jì)算機(jī)不用進(jìn)行NUMA優(yōu)化,且其平均性能達(dá)到了24.26GTEPS,并且具有2.5倍作用的功耗比優(yōu)勢,在大規(guī)模、密集型的圖數(shù)據(jù)過程當(dāng)中有著明顯的優(yōu)勢。

引用

[1] 丁旭陽,謝盈,張小松.基于邊緣計(jì)算的進(jìn)化多目標(biāo)優(yōu)化圖像隱寫算法[J].計(jì)算機(jī)研究與發(fā)展,2020(11):2260-2270.

[2] 葉楠,郝子宇,鄭方,等.BFS算法與眾核處理器的適應(yīng)性研究[J].計(jì)算機(jī)研究與發(fā)展,2015(5):1187-1197.

[3] 劉建友,蔣春霞.一種基于高通量計(jì)算機(jī)的圖算法優(yōu)化技術(shù)[J].信息與電腦,2020(22):69-71.

[4] 張嘉文,董曉斌,苗桂君,等.基于計(jì)算機(jī)視覺的液滴圖像拼接與識(shí)別算法研究[J].中國生物醫(yī)學(xué)工程學(xué)報(bào),2021(3):375-379.