面向高通量計算機的圖算法優化技術

張承龍 曹華偉 王國波 郝沁汾 張 洋 葉笑春 范東睿

1(計算機體系結構國家重點實驗室(中國科學院計算技術研究所) 北京 100190)2(中國科學院大學計算機與控制學院 北京 100049)

圖具有極強的抽象性和靈活性，是一種表示和分析大數據的有效方法.圖計算可進行巨量、稀疏、超維關聯的挖掘和分析，已廣泛應用于社交網絡、交通網絡、生物信息網絡、知識圖譜等[1-4].隨著圖數據規模的爆炸式增長和圖計算需求的不斷增加，如何高效地處理大規模圖數據成為大數據領域的研究重點，也是工業界關注的焦點.

寬度優先搜索(breadth first search, BFS)算法是一種經典的圖遍歷算法，也是眾多圖分析算法的基礎，例如連通分量(connected component, CC)、中介核心性(betweenness centrality, BC)以及單源最短路徑(single-source shortest path, SSSP)等算法.BFS應用具有數據局部性差、計算訪存比低、并行效率低和擴展性差等數據密集型應用的典型特征.2010年，國際上提出了Graph500排行榜來評估服務器和超級計算機處理數據密集型應用的能力，而BFS算法是Graph500的基準測試程序之一[5].

針對數據密集型應用，中國科學院計算技術研究所高通量計算機研究中心在2018年的中國計算機大會上發布了新一代高通量計算機“金剛”[6].高通量計算機(high-throughput computer, HTC)采用高通量眾核體系結構，在一系列體系結構創新技術的加持下，高通量計算機具有高并發、強實時、低功耗等適于大數據計算的特點.目前，高通量計算機已經針對深度學習、高通量視頻處理、科學大數據處理和信息安全監測等典型場景開展示范引用.

本文將對單節點下BFS算法的優化技術進行系統介紹，并在此基礎上提出2種面向高通量計算機的優化手段，通過減少冗余訪存和提高緩存局部性，有效提高了算法的訪存效率.基于這些優化手段，我們對BFS算法在高通量計算機上的性能進行系統的評估，同時與通用服務器進行對比，展現高通量計算機處理數據密集型應用的優越性.

1 相關工作

為了獲取更高的性能和更低的能耗，近年來BFS的并行算法在共享式內存系統、分布式內存系統和GPU等平臺上都得到了廣泛的研究，國際上針對BFS算法的優化工作也取得了一系列的進展.

在Cray的MTA平臺上，Bader等人[4]通過挖掘算法的并行度，采用多線程技術來隱藏遍歷過程中的訪存延遲.Agarwal等人[7]針對數據結構進行優化，改善了數據的局部性，提高了算法性能.為了充分利用GPU的多線程技術，Hong等人[8]提出一種面向GPU平臺的并行BFS算法，結合多線程技術和細粒度同步機制提高了系統的整體性能.2011年，Beamer開創性地提出了一種自底向上(bottom-up)的遍歷算法[9]，通過結合傳統自頂向下(top-down)的算法，實現了方向性優化的BFS算法，通過減小冗余的訪存開銷，提高了算法性能.2015年，葉楠等人在在眾核體系結構上對BFS算法進行了測試，發現當前典型的眾核結構無法滿足BFS算法的需求，新型處理器體系結構需要支撐大量離散隨機訪問以及更為簡單的執行機制[10].2013年，Yasui等人針對非統一內存訪問架構(non-uniform memory access architecture, NUMA)提出了相應的NUMA感知和度數感知優化技術，在Intel的四路Xeon E5-4640服務器上取得了29.1 GTEPS的性能[11].基于上述研究，我們發現BFS并行處理時仍然存在嚴重的負載不均衡性，基于此提出一種靜態shuffle優化，改善了眾核間的負載均衡性，顯著提高了線程利用率，同時也避免了動態調度方式的一些缺點[12].

本文在已有工作的基礎上，提出了一種高效的基于塊查找的位圖訪問方式，減少了不必要的緩存訪存；此外，我們對Bottom-up算法的遍歷過程做了進一步優化，有效改善了緩存數據的局部性，提高了訪存效率.

本文主要貢獻有3個方面：

1) 為了充分利用高通量計算機的大容量緩存，提出一種高效地位圖訪問方法，顯著提高了未訪問點的查找效率，能夠顯著減少對cache的訪問，提高寄存器訪問的局部性.

2) 針對Bottom-up的核心算法進行了深入優化，將3個bitmap減少為2個bitmap，在此基礎上將Degree-Aware中的2次遍歷過程合并為一次，提高了緩存局部性和分支效率.

3) 在高通量計算機上對BFS的性能和能耗表現進行了系統評估，并與x86架構的服務器進行了對比.詳細分析了所提算法的有效性，優化后的算法顯示出性能和性能功耗比優勢.

2 算法背景介紹

本節我們將對BFS算法及現有的優化技術進行系統的介紹和總結，包括方向性優化、去零點優化、度數感知優化、頂點排序優化和靜態shuffle優化等.最后的實驗也是集合了這些優化技術.

2.1 方向性優化

傳統的BFS算法是一種自頂向下(top-down)的遍歷方法，遍歷中后期會產生大量的冗余遍歷.Beamer創造性地提出了一種Bottom-up 算法來減少冗余邊的遍歷.如算法1所示.

算法1.Bottom-up BFS算法.

輸入:圖G={V,E}、遍歷起始點s;

輸出:存儲父親信息的數組parent.

①visit[v]←0, for ?v∈V;

②visit[s]←1;

③parent[s]←s;

④currentfrontier←{s};

⑤nextfrontier←?

⑥ whilecurrentfrontiernot empty do

⑦ for eachu∈Vin parallel do

⑧ ifvisit[u]==0 then

⑨ for eachwadjacent toudo

⑩ ifw∈currentfrontier

{u};

Bottom-up采用與Top-down完全相反的思想，在算法1執行的每一層優先選擇所有未訪問的頂點(行⑧)，通過查找其鄰居頂點是否位于currentfrontier來替子節點尋找父節點.一旦未訪問的頂點在currentfrontier中找到父節點，則跳出循環結束對剩余鄰居頂點的訪問，有效減少了冗余的訪存開銷.由此導致Bottom-up算法在初始幾層遍歷時產生大量的無效遍歷.基于此，Beamer等人提出結合Top-down和Bottom-up的方向性優化算法[9].在算法1中，首先使用Top-down算法開始遍歷，當currentfrontier隊列變得足夠大時切換到Bottom-up執行，結合二者的優勢，從而顯著提高BFS性能.

2.2 去零點優化

在Graph500中，數據集采用的是Kronecker生成圖.研究發現[11]，Kronecker生成圖中存在大量的孤立頂點，即這部分頂點的出度為0.通過統計，孤立頂點在不同規模的生成圖中所占比例如表1所示:

Table 1 Ratio of Isolated Vertices in Kronecker Graphs with Different Scales表1 不同規模下的Kronecker生成圖中孤立頂點的比例

從表1可以看出，孤立頂點在Kronecker生成圖中的占比超過50%，并且隨頂點規模的增加而增長.Bottom-up算法在遍歷每一層的過程中，首先會從所有頂點中找出所有未被訪問過的頂點，然后從這些未訪問過的頂點出發去搜索其父親節點.孤立頂點的存在，使得Bottom-up算法在每層遍歷中，產生大量對孤立頂點的無效遍歷和無效訪存.因此，在預處理中去掉孤立頂點，會進一步提高遍歷效率.

2.3 度數感知優化

如2.1節所述，Bottom-up算法遍歷中會掃描所有未訪問頂點的鄰居頂點，只要找到一個鄰居頂點在currentfrontier中，則結束對剩余鄰居節點的遍歷.如果終止的越早，則可以減少鄰居檢查的數量.理想情況下，Bottom-up方法只檢查未訪問頂點的第1個相鄰節點，就能夠檢查成功，其后將跳過所有剩余的鄰居頂點.然而事實上，我們難以確定鄰居列表的最佳順序，選定不同的源頂點，鄰居列表的最佳順序都可能是不同的.Yasui等人通過實驗發現了頂點度數和訪問頻率之間的關聯性，頂點的度數越大，其訪問頻率越高[13].為了進一步提高訪存效率，Yasui將鄰接列表A拆分為只含最高度數鄰居頂點的AB+與剩余按照度數降序排列的鄰接列表AB-，將算法1中的一次遍歷循環(行⑨～)拆分為采用鄰接列表AB+與AB-的2次循環.實驗發現，度數感知優化可以極大減少冗余邊的遍歷，提高數據訪問效率.

2.4 頂點排序優化

為了改善數據的局部性、提高訪存效率，Yasui等人提出一種頂點排序的優化方法[14]，基于頂點度數降序對行列表(row)中的頂點索引進行排序，將較低的索引分配給具有高度數的頂點.盡管頂點排序方法可以改進數據的局部性來減少訪存開銷，但是在動態調度過程中，數據塊粒度和調度開銷存在博弈.當塊粒度很小時，可以很好地解決線程間的負載均衡問題，但頻繁的線程調度將顯著提高執行時間的開銷，導致整體性能下降.當塊粒度很大時，由于圖數據頂點度數分布遵循冪律分布[15]，因此相鄰頂點塊中度數分布變化很大.高度數塊的處理時間遠大于低度數塊的執行時間，導致嚴重的負載不均衡問題.

圖1顯示了頂點排序方法下線程的平利用率，可以看到采用動態調度的方式每個線程的利用率波動很大，線程間存在嚴重的負載極不均衡問題.

Fig.1 The thread utilization of two methods when 2scale=227圖1 當規模為227時2種方法的線程利用率

2.5 靜態shuffle優化

針對高通量計算機高并發的體系結構特點，我們在之前的工作中提出了一種按照頂點度數輪詢分配的靜態shuffle優化方法[12]，在利用頂點排序優勢的同時，改善了高通量計算機核間的負載均衡性，提高了并行BFS算法在高通量計算機上的性能.

如算法2所示，在圖數據的CSR存儲結構中，對行列表row中的頂點按度數降序排序，以輪詢的方式依次將頂點分配給不同段數組(分別存儲線程執行頂點信息)，保證高度數頂點與低度數頂點均勻地分配給每個線程，并在線程段數組內依然保持頂點按度數的降序排列.與此同時，建立新頂點ID到舊頂點ID的映射，從而可以在圖遍歷結束后恢復原始圖拓撲的父節點信息.

算法2.頂點輪詢分配的靜態shuffle算法.

輸入:劃分個數segmentNum、原始的排好序的row緩存old_array；

輸出:shuffle之后的row緩存new_array、節點shuffle前的編號new2old.

①num←vertexNums/segmentNums;

② for(tid=0;tid

do

③ for (j=0;j

④new_array[tid×num+j]←

old_array[tid+segmentNums×j];

⑤new2old[tid×num+j]←tid+

segmentNums×j;

⑥ end for

⑦ end for

⑧ returnnew_array,new2old.

通過上述靜態shuffle分配，一方面保持了頂點排序的數據局部性，提高了內存帶寬的利用率;另一方面，在預處理時已經將每個線程處理的頂點信息保存下來，避免了頻繁的線程調度引起的開銷，以及動態分配中塊粒度的經驗參數調整.

3 BFS算法優化

針對高通量計算機高并發和大容量緩存的體系結構特點，我們在第2節優化工作的基礎上，提出了基于塊查找的位圖訪問優化和Bottom-up遍歷優化2種方法，進一步提高BFS算法在高通量計算機上的性能.具體來說，我們提高了未訪問頂點的搜索效率與片上緩存的數據局部性，有效提高了BFS算法的訪存效率.

3.1 基于塊查找的位圖訪問

BFS在遍歷過程中采用位圖的形式來標記頂點的訪問狀態.位圖是一種緊湊的數據結構，可以放在最后一級緩存(cache)中，有效減少了片外DRAM的訪問，降低了訪存開銷.在Bottom-up算法中，每次迭代都通過順序掃描visit位圖來尋找未訪問頂點(算法1行⑦～⑧).由于Kronecker圖結構的冪律分布特點，經過幾次Bottom-up迭代后，未訪問頂點的數量將急劇減少，并呈稀疏分布.在處理大規模圖數據時，順序掃描visit位圖將對性能產生極大的影響.

Fig.2 The quick search for unvisited vertices圖2 未訪問頂點的快速遍歷示意圖

基于此，我們提出一種基于塊(block)查找的visit位圖訪問優化技術，在每一層的Bottom-up遍歷中，能快速找到未訪問頂點在block中的位置.如圖2所示，在遍歷過程中以visit位圖中的block為單位進行頂點狀態的粗粒度判斷.現代通用處理器中通用寄存器的最大位寬為64位，最多可以表示64個點的訪問狀態，因此一個block的大小設置為64.在遍歷開始時，首先將visit位圖中第i個block的訪問狀態從內存中加載到64位寬的寄存器block_visit中.然后，對visit位圖的第i個block對應的整型變量block_visit取反，得到寄存器變量block_no_visit，取反后狀態位為0是已遍歷的頂點，狀態位為1則為待查詢的未訪問頂點.如果block_no_visit中的狀態位全為0，則說明當前block不包含未訪問頂點，直接跳過對當前block中所有頂點的狀態訪問；如果block_no_visit的狀態位不全為0，通過算法3可以快速定位block_no_visit中最右側的未訪問頂點的位置(最右側1 bit位)，并將寄存器block_no_visit中該點對應的位置置0，依次循環，從右到左依次訪問block_no_visit中的未訪問頂點(bit位為1)，如圖2所示.在從block_no_visit中查找未訪問點時，其循環次數僅與bit位為1的數目(即未訪問的頂點數目)有關，而與block大小無關.而傳統算法在查找block中未訪問點時采用順序遍歷，即使block中只有1個未訪問點，也需要迭代block大小次數.

算法3.基于塊查找的頂點快速定位.

輸入:一個block 的遍歷狀態(uint64_t)block_no_visit(block_no_visit=1表示尚未遍歷，block_no_visit=0表示已經遍歷);

輸出:一個block寄存器變量中最低位未遍歷點的位置pos、 更新之后的block_no_visit.

① uint64_tbit_no_visit=block_no_visit& (-block_no_visit);

② uint64_tmask=bit_no_visit-1;

③pos=__builtin_popcountl(mask);

④block_no_visit=block_no_visit& ～bit_no_visit; /*set the lowest unvisited vertex to visited*/

⑤ returnpos,block_no_visit.

算法3中核心函數的算法復雜度為O(log(k))，優于傳統順序查找的算法復雜度O(k).優化后，將原有的細粒度逐位掃描方式，轉換為粗粒度的快速定位方式，在Bottom-up的后幾層遍歷過程中，減少了大量的訪存操作.此外，BFS算法的局部性非常差、cache miss率高，會發生頻繁的cache替換.本節提出的基于塊查找的位圖訪問方法，將一個block的位從原有的visit位圖存入寄存器，減少了對cache的頻繁訪問，提高了訪問效率.引入塊查找位圖訪問后的Bottom-up遍歷如算法4所示.

算法4.使用3個bitmap的塊查找的Bottom-up算法.

輸入:圖G={V,E}={V,(AB+,AB-)}、遍歷起始點s;

輸出:存儲父親信息的數組parent.

①visit[v]←0, for ?v∈V;

②visit[s]←1;

③parent[s]←s;

④currentfrontier←{s};

⑤nextfrontier←?

⑥BlockNum←vertex_num/BlockSize; /*頂點總數vertex_num除以block寬度BlockSize*/

⑦ whilecurrentfrontiernot empty do

⑧ fori0～BlockNumin parallel do

/*當前層遍歷，依次取每個block*/

⑨block_visitgetBlock(visit,i);

/*獲取第i個block的訪問狀態，存入寄存器變量block_visit*/

⑩block_no_visit～block_visit;

(block_no_visit); /*block中最右側未訪問點的位置pos*/

then /*如果v在當前層*/

(1?pos);

(1?pos);

表2給出了優化前后Bottom-up每層遍歷的頂點數目對比.可以看出，在遍歷到第5層時，99.8%的頂點是已訪問狀態，順序掃描visit位圖將產生大量無效訪存.優化后，每次以粗粒度的block進行判斷，對于包含未被訪問的頂點，基于塊查找的位圖訪問優化可以高效地定位未訪問頂點.相對于順序掃描，最多能節省98.4%的頂點訪存狀態判斷，極大地提升了算法的遍歷效率.

Table 2 Number of Traversed Vertices with and without Bitmap Optimization表2 位圖訪問優化前后的頂點遍歷數目

3.2 Bottom-up遍歷優化

在本節中，我們提出針對Bottom-up遍歷方式的優化.在原有的Bottom-up算法中，需要current_frontier,next_frontier和visit三個數據結構來保存遍歷過程中更新的信息.current_frontier保存當前層的活躍頂點，visit保存已經被遍歷過的頂點，next_frontier用于存放下一層將遍歷的活躍頂點.事實上，visit中包含處于current_frontier中的活躍頂點信息，位于current_frontier中的頂點一定已經在visit中置位，因此在判斷未訪問頂點u是否有鄰居頂點在current_frontier中時，我們考慮用visit位圖代替來達到同樣的效果，減少額外數據結構的使用.如算法5的行～所示，結合使用visit和visit_new，能夠在遍歷過程中省去對當前層的躍頂點結構current_frontier的訪問，將Bottom-up遍歷過程中所需要的3個數據結構減少為2個，每次迭代只有一次visit讀操作和一次visit_new寫操作，其余操作都是對寄存器block_visit進行的，提高了cache訪問的緩存局部性，進而提高了訪存效率.

算法5.基于塊查找的Bottom-up BFS算法(block search bottom-up BFS, BSBB).

輸入:圖G={V,E}={V,(AB+,AB-)}、遍歷起始點s;

輸出:存儲父親信息的數組parent.

①visit[v]←0, for ?v∈V;

②visit[s]←1;

③parent[s]←s;

④currentfrontier←{s};

⑤nextfrontier←?;

⑥BlockNumvertex_num/BlockSize;

/*頂點總數vertex_num除以block寬度BlockSize*/

⑦ whilecurrentfrontiernot empty do

⑧ fori0～BlockNumin parallel do /*當前層遍歷，依次取每個block*/

⑨block_visitgetBlock(visit,i);

/*獲取第i個block的訪問狀態，存入寄存器變量block_visit*/

⑩block_no_visit～block_visit;

(block_no_visit); /*block中最右側未訪問點的位置pos*/

/*如果v在當前層*/

(1?pos);

另一方面，在Yasui等人提出的度數感知優化中[14]，闡明了Bottom-up算法的主要性能瓶頸是對未訪問頂點的鄰居頂點的訪存開銷.他們將鄰接列表A拆分為只含最高度數鄰居頂點的AB+與剩余按照度數降序排列的鄰接列表AB-，分別遍歷2個鄰接列表來提高鄰居頂點在current_frontier中的搜索效率.我們進一步統計了Bottom-up算法在鄰接列表AB+與AB-的遍歷效率，測試結果如算法5所示.

表3可以看到，在Bottom-up算法的每層遍歷中，通過鄰接列表AB+更新的活躍頂點數目超過96%，并且隨遍歷層數的推進，活躍頂點的比重不斷增加.在測試樣例的第5層遍歷中，所有的活躍頂點都是通過鄰接列表AB+更新.基于此，在我們優化后的Bottom-up算法中，我們將對鄰接列表AB+與AB-的遍歷合并為一個，在保證AB+數據局部性的同時，又減少了對AB-結構無效的訪存次數.

Table 3 Number of Active Vertices Under Degree-aware Optimization for Graph Scale 227表3 頂點規模為227時度數感知優化下Bottom-up 每一層遍歷的頂點數目

4 實驗結果與分析

為了評估高通量計算機處理大規模圖數據的能力，我們搭建了2套測試系統用于評估BFS算法的性能.一套基于自研的高通量計算機，配備一顆ARM架構的Centriq 2434眾核處理器，該處理器包含40個處理核心和50 MB的L3 cache，TDP為110 W；另一套系統采用傳統的x86架構服務器，配有兩路Intel Xeon E5-2683處理器，每路CPU包含14個核心和35 MB L3 cache,TDP為120 W.系統的詳細配置信息如表4所示，2套系統均使用gcc7.3.0進行編譯.

Table 4 Configure Information表4 系統配置信息

測試數據集采用Graph500基準測試中的Kronecker生成圖，其參數設置為默認值(A=0.57,B=C=0.19,D=0.05).Kronecker生成圖可以通過輸入scale和edgefactor等參數來調整圖的性質，其中，scale參數表示圖的頂點規模，edgefactor表示每個頂點的平均度數.生成的圖數據滿足冪律分布，包含2scale的頂點數目以及2scale×edgefactor的總邊數.對于每個測試數據圖，隨機選擇64個源頂點執行BFS算法并取平均時間，采用指標每秒遍歷億條邊 (giga-traversed edges per second, GTEPS)來對性能進行評估.

4.1 高通量計算機介紹

實驗用的高通量計算機主要用于數據中心大數據處理[16]，其微結構主要包括：1)高吞吐處理核.共有40個處理核，每個處理核采用變長流水線和多發射結構，顯著提高了指令吞吐效率，有效地掩蓋了圖遍歷過程中鄰居邊訪問時延.2)大容量片上存儲.高通量計算機具有較大容量的L3 cache，大小為50 MB，可以將更大的圖放到緩存中，進一步提高了訪存局部性.3)易擴展片上網絡.處理核通過環形總線進行互聯，可以提供250 GB/s的聚集帶寬，能夠滿足圖遍歷時的核間數據共享帶寬需求.4)快速同步機制.支持基于數據流的核間細粒度快速同步，相比傳統的基于內存的同步機制，性能可獲得數量級的提升，有效緩解了每次迭代后的層同步壓力.5)可編程數據通信機制.可編程數據傳輸引擎結構，可以快速實現數據的水平 (片上處理器核之間)和垂直(從內存到片上存儲)搬運，實現了數據通信的低延遲.高通量計算機有效解決了高通量典型應用BFS的緩存利用率低、內存訪問效率低等問題.

4.2 優化手段評估

Fig.3 BFS performance on HTC with different graphscale and edgefactor=16圖3 不同規模的圖數據在平均度數為16的高通量計算機上的BFS性能

圖3給出了頂點規模為224～230，平均度為16的Kronecker生成圖在高通量計算機上執行BFS算法的性能變化趨勢.在不做任何優化時，Graph500基準程序的平均性能只有0.69 GTEPS，生成圖頂點規模對性能的影響較小.采用方向性優化后(Hybrid)，性能得到明顯提升，平均性能達到了6.52 GTEPS，性能提升趨勢與Beamer采用四路Xeon E7-8870的結果(5.12 GTEPS)[9]基本一致.基于Yasui提出的去零點優化(remove zero, RZ)和度數感知優化(degree aware, DA)[13]，我們提出了靜態shuffle優化[12]來改善線程間的負載均衡性.如圖3所示，優化前的最優性能為25.92 GTEPS，在頂點規模為226時取得.隨著圖頂點規模的增加，性能呈下降趨勢.增加本文提出的位圖訪問優化和Bottom-up遍歷優化之后，由于訪存效率的改善，對于226的圖，BFS算法在高通量計算機上提升到了29.71 GTEPS，且性能隨圖頂點規模的變化趨勢與之前基本一致.相比Graph500的基準測試程序，實現了43.01倍的性能提升.對于所有SCALE的性能，性能平均提高11.4%.充分說明了本文提出方法的有效性.表5對近年來基于CPU和高通量計算機的BFS優化工作進行了匯總.通過對比，進一步說明高通量計算機在圖處理領域具有顯著的優越性.

Table 5 Compare with Related Work表5 與相關工作對比

4.3 擴展性評估

Fig.4 Scalability of BFS Algorithm on HTC圖4 BFS算法在高通量計算機上的擴展性

為了研究優化后的BFS算法在高通量計算機上的擴展性，針對頂點規模為225的圖數據，圖4和表6給出了不同線程數目下的BFS性能變化.在平均度為16時，40線程下的高并發處理比單線程的性能提升了將近17.8倍，同時性能隨線程數目的增加呈近似的線性擴展.隨后我們對平均度數的影響進行了研究.由圖4可以看出，隨著平均度數的增加，算法性能提升幅度明顯，平均度數越高，性能越好.在平均度為32時，算法的平均性能可以達到40.2 GTEPS，優于平均度為16時的27.2 GTEPS和平均度為8時的13.14 GTPES.這主要是由Kronecker生成圖的特性造成的.隨著平均度的增加，Kronecker生成圖將會產生大量的重復邊，降低了圖數據的稀疏性.這些重復邊在BFS的遍歷過程中不會對運行時間造成影響，進而表現出更優的搜索效率.為了保證圖拓撲結構的稀疏性，我們在后續的實驗中選用Graph500中默認的16作為生成圖的平均度.

Table 6 Scalability and Speed-up Under Different Numbers of Threads表6 不同線程數目下的擴展性和加速比

4.4 CPU性能分析

Fig.5 CPU profiling parameters with and withoutthe optimizations圖5 優化前后的CPU參數對比

本文提出的塊查找位圖訪問優化、Bottom-up遍歷優化主要是對L1 Data Cache訪存和分支跳轉進行的優化，因此本節使用Perf對優化前后的Bottom-up函數進行了代碼插裝，獲取了L1 Data Cache(L1D)讀訪問次數、Branch指令數的變化情況，進一步驗證我們算法的有效性.如圖5所示，L1D讀訪問次數平均減少了24.29倍，因為塊查找位圖訪問優化對L1 Data Cache按照block的粒度進行讀取，將頂點數據讀取到寄存器中，即使block中所有點都需要判斷，也只需讀取一次cache，后續操作都是針對寄存器的運算.Branch指令數平均減少了39.34倍，這是因為塊查找位圖算法復雜度低，能夠快速找到未判斷的點，減少了分支指令次數.上述性能分析說明本文的優化手段有效改善了緩存局部性和分支效率，提高了訪存效率.

4.5 性能對比

本節將對比分析BFS算法在高通量計算機和x86服務器上的性能，圖6給出了優化后的BFS算法在高通量計算機和通用x86服務器下執行的性能對比，默認采用的優化手段為方向性優化、去零點優化、度數感知優化、靜態shuffle優化以及本文提出的優化方法.如表4所示，我們使用的x86服務器擁有2個NUMA節點，當CPU訪問非本地NUMA上的數據時，產生較長的訪存時延.在文獻[11]中，作者提出針對多NUMA架構的性能優化方法，保證線程在執行BFS遍歷時只訪問本地的DRAM，避免了遠程DRAM的訪問開銷.因此，在x86服務器上，我們增加了NUMA感知優化手段.由圖6可以看出，BFS算法在兩路x86服務器上的整體性能與高通量計算機大致相仿，在頂點規模為226時，x86服務器上的最優性能為23.94 GTEPS.在絕對性能方面，高通量計算機展現了優越的表現.表7給出了不同圖規模下高通量計算機相比x86服務器的性能加速比.可以看出，在大規模的圖數據集下，高通量計算機的執行性能全面占優.在頂點規模為227時，最大性能加速比有1.31倍.

Fig.6 Performance comparison of BFS between HTCand x86 Server圖6 BFS算法在高通量計算機與x86服務器的性能對比

Table 7 Performance Comparison Between HTC and x86 Server
表7 高通量計算機相比x86服務器的性能加速比

2scaleSpeed-up2241.072251.172261.242271.312281.182291.082301.18

然而，多NUMA感知的優化方法增加了額外的編程復雜度，需要針對Top-down和Bottom-up過程分別進行不同的數據預處理，而且為避免線程跨NUMA節點訪問遠程數據，需要在每個NUMA節點的本地內存增加額外的數據結構,滿足Top-down和Bottom-up的遍歷需求，這同時也會引起內存膨脹.如圖7所示，在使用NUMA優化后，內存的占用率提升了將近1.3倍.在圖的頂點規模為230時，高通量計算機系統的內存使用接近350 GB，而采用NUMA感知優化的x86服務器內存占用超過420 GB.對于共享式內存系統，內存占用率是影響圖數據處理規模的核心因素.綜上，高通量計算機本身雖然無需采用NUMA優化，但是加入本文優化方法后在性能上可以超過額外增加NUMA優化的x86服務器，說明本文提出的方法能夠發揮高通量計算機的性能，而且與傳統計算機相比，高通量計算機占用的內存更少、編程復雜度也更小，高通量計算機在圖數據處理方面具有顯著的優勢.

Fig.7 Memory Consumption with and withoutNUMA optimization圖7 NUMA優化前后的內存使用

4.6 性能功耗比

本節將圍繞能效方面展開研究.測試數據采用頂點規模為230、平均度為16的Kronecker大圖數據，并采用微型電力監測儀實時監測2套系統的功耗.實驗結果如表8所示，未經優化的Graph500基準測試程序的性能功耗比僅為2.41 MTEPS/W.采用之前的優化方法優化后性能功耗比為165.97 MTEPS/W，增加本文提出的優化方法BSBB后，高通量計算機的整機功耗為134 W，性能功耗比為181.04 MTEPS/W，性能功耗比顯著提高.x86服務器的整機功耗為286 W,性能功耗比為71.92 MTEPS/W.面向超大規模的圖數據集，高通量計算機相比x86服務器在單節點上擁有2.51倍的性能功耗比優勢.高通量計算機的性能功耗比結果在2019年6月發布的Green Graph500面向大數據集的排行榜上可以排名第2位[17].綜上，高通量計算機的高并發和低功耗等特點非常適合處理大規模圖計算等數據密集型應用.

Table 8 Energy Efficiency of BFS Implementation Between HTC and x86 Server表8 高通量計算機與x86服務器的性能功耗對比 (2scale=230)

5 總 結

本文對單節點的并行BFS算法和BFS算法的優化技術進行了介紹，并在此基礎上提出2種面向高通量計算機的優化手段塊查找位圖優化和Bottom-up遍歷優化，提高BFS的緩存局部性和訪存效率.基于上述的優化手段，我們對BFS算法在高通量計算機上的性能進行了系統的評估.對于頂點規模為230的大圖，在性能方面，高通量計算機在單節點的平均性能為24.26 GTEPS；在性能功耗比方面，高通量計算機的結果為181.04 MTEPS/W，在2019年6月發布的Green Graph500面向大數據集的排行榜上可以排名第2位[17].與通用的x86服務器相比，高通量計算機在單節點具有1.18倍的性能優勢以及2.51倍的性能功耗比優勢.由于高通量計算機的高并發、強實時和低功耗等特點，在處理大規模圖數據時，結合應用特征采用新型的高通量計算機系統，可獲得更高的處理能效.