高通量計算機的圖算法優化技術研究

賈子昂

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

0 引言

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

1 研究現狀

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

2 算法介紹

以下算法研究是以BFS算法為基礎,其中主要有歷程優化、去零點優化和靜態優化等。

2.1 歷程優化

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

2.2 頂點排序優化

頂點排序優化主要是通過頂點索引來實施降序排列,從而提高訪存效率。但在處理較大圖數據時,由于數據的分布以冪的形式出現,相鄰兩個頂點數據變化較大,處理數據需要耗費大量時間,影響執行時間,甚至會出現負載不均勻現象[4]。

2.3 去零點優化

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

2.4 靜態shuffle優化

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

經過以上循環,發現靜態shuffle循環不但能夠保存數據信息,還能突破頂點數據排序的局限,避免了重新分配和調度,提高了內存的利用率[7]。

2.5 度數感知優化

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

3 BFS算法優化

3.1 基于快查找的地圖訪問

在實施BFS算法時,主要由位圖確定訪問狀態,能夠提升最后一級緩存性能,減少DRAM訪問沉余,降低訪存消耗[8]。Bottom-up算法,是由順序掃描位圖來確定沒有訪問的頂點,通過Kronecker圖的特點,經過連續多次Bottom-up的優化后,將未訪問的頂點樹立減少,在處理大規模數據圖時,順序掃描會對位圖產生嚴重的影響。從以上情況,位圖訪問優化能夠加強快速尋找未訪問頂點位置功能,如圖1所示。在位圖優化時,位圖定位狀態能夠將粗粒度作為判斷標準[9]。現如今我國最先的處理器最大寬度為64位,能夠同時訪問64個點的狀態,因此一個block的大小設置為64,傳統算法只能查找block中采用順序遍歷的方式,只有一個未訪問點,需要迭代block大小和次數,影響找尋未訪問頂點的效率[7]。

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

3.2 Bottom-up歷程優化

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

4 結語

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