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

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

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

0 引言

圖數(shù)據(jù)能夠快速、靈活的處理大量的、稀疏的數(shù)據(jù),并且完成大數(shù)據(jù)的實(shí)時(shí)分析,被廣泛的應(yīng)用在知識(shí)圖譜、交通網(wǎng)絡(luò)等方面。由于圖數(shù)據(jù)的迅速增加,如何對(duì)圖數(shù)據(jù)進(jìn)行快速的處理成為了目前研究的重要內(nèi)容。寬度優(yōu)先搜索(Breadth First Search,BFS)算法主要利用Graph500基準(zhǔn)的核心測(cè)試程序,是一種典型的圖遍歷方法,但是具有訪(fǎng)存比低、擴(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)中。因此,對(duì)基于高通量計(jì)算機(jī)的圖算法優(yōu)化技術(shù)進(jìn)行研究具有重要的意義。

1 相關(guān)工作

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

2 算法介紹

2.1 歷程優(yōu)化

BFS算法可以看做一種自頂而下的歷程優(yōu)化算法,在遍歷的時(shí)候會(huì)存在很多的冗余遍歷。自下而上的算法,能夠在一定程度上減少冗余。Bottom-up算法能夠在各層優(yōu)先對(duì)沒(méi)有訪(fǎng)問(wèn)的頂點(diǎn)(行(8))進(jìn)行處理,當(dāng)頂點(diǎn)已經(jīng)被訪(fǎng)問(wèn)時(shí)則跳出循環(huán)過(guò)程,對(duì)其余的頂點(diǎn)進(jìn)行查找,極大的減短了冗余的訪(fǎng)問(wèn)時(shí)間。另外,在后續(xù)的研究過(guò)程中,進(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)]有訪(fǎng)問(wèn)的頂點(diǎn),再在這些頂點(diǎn)當(dāng)中搜索節(jié)點(diǎn)。在對(duì)每層遍歷的時(shí)候,孤立頂點(diǎn)的產(chǎn)生會(huì)存在無(wú)效遍歷以及無(wú)效訪(fǎng)問(wèn)等問(wèn)題,所以必須進(jìn)行去零點(diǎn)優(yōu)化操作,從而提升遍歷的速度。

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

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

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

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

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

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

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

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

3.1 基于塊查找的位圖訪(fǎng)問(wèn)

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

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

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

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

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

從算法優(yōu)化前后頂點(diǎn)遍歷數(shù)量的對(duì)比結(jié)果能夠得出:當(dāng)遍歷第五次時(shí),存在99.8%的頂點(diǎn)是已經(jīng)訪(fǎng)問(wèn)的情況,Visit位圖出現(xiàn)很多無(wú)效的訪(fǎng)存。當(dāng)對(duì)Visit位圖進(jìn)行優(yōu)化后,根據(jù)Block為單位進(jìn)行粗粒度的判別,基于塊查找的位圖訪(fǎng)問(wèn)優(yōu)化算法能夠快速、準(zhǔn)確的找到未訪(fǎng)問(wè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)來(lái)存儲(chǔ)遍歷時(shí)的數(shù)據(jù)信息。其中,current-frontier用來(lái)提升頂點(diǎn)的活躍程度,Visit保存遍歷好的頂點(diǎn),而next-frontier保存下次遍歷的活躍頂點(diǎn)。利用Visit圖能夠節(jié)約數(shù)據(jù)結(jié)構(gòu)的應(yīng)用,在遍歷時(shí)不需要對(duì)該層活躍的頂點(diǎn)進(jìn)行訪(fǎng)問(wèn),從而把Bottom-up算法當(dāng)中應(yīng)用的三個(gè)數(shù)據(jù)結(jié)構(gòu)減少為兩個(gè),極大的提升了訪(fǎng)存的速度。此外,根據(jù)度數(shù)感知優(yōu)化算法,針對(duì)Bottom-up算法的性能缺陷,把鄰接列表A分別AB+(度數(shù)高的鄰接頂點(diǎn))和AB-(度數(shù)降序排列的其余頂點(diǎn)),對(duì)兩個(gè)相鄰的列表進(jìn)行遍歷,從而提升鄰居頂點(diǎn)的搜索速度,提高數(shù)據(jù)的訪(fǎng)存效率。

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

4 結(jié)論

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

引用

[1] 丁旭陽(yáng),謝盈,張小松.基于邊緣計(jì)算的進(jìn)化多目標(biāo)優(yōu)化圖像隱寫(xiě)算法[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ī)視覺(jué)的液滴圖像拼接與識(shí)別算法研究[J].中國(guó)生物醫(yī)學(xué)工程學(xué)報(bào),2021(3):375-379.