LargeGraph：依賴感知的GPU圖計算加速技術
近來，許多out-of-GPU-memory系統被用于支持大規模圖的迭代處理。由于活躍頂點的新狀態沿圖中路徑的傳播效率低，這些系統仍然需要很長時間才能達成收斂。為了有效地支持out-of-GPU-memory下的圖處理，我們設計了LargeGraph系統。不同于現有的out-of-GPU-memory系統，LargeGraph提出了一種依賴感知的數據驅動執行方法，該方法可以顯著加快活躍頂點沿圖中路徑的狀態傳播速度，同時有較低的數據訪存開銷和較高的并行性。具體來說，LargeGraph能夠分析頂點之間的依賴關系，只對與活躍頂點的依賴鏈相關聯的圖數據進行加載和處理，以此來減少訪存開銷。由于現實世界中圖數據普遍存在冪律特性冪律特性，大多數活躍頂點會經常使用一組不斷演化的路徑子集進行新狀態的傳播。通過在GPU上對路徑子集進行動態識別、維護和處理，LargeGraph能夠加速大多數活躍頂點的狀態傳播以更快達成收斂狀態，其他的圖數據則在CPU上進行處理。實驗結果表明，和其他4種最新方案相比，LargeGraph能夠進一步將目前流行的GPU外存儲圖計算系統Totem，Graphie，Garaph和Subway的性能分別提高5.19-11.62倍，3.02-9.41倍，2.75-8.36倍，2.45-4.15倍。
該成果“ LargeGraph: An Efficient Dependency-Aware GPU-Accelerated Large-Scale Graph Processing ”已被期刊ACM Transactions on Architecture and Code Optimization(TACO)收錄（Volume 18，Issue 4，December 2021，Article No.： 58, pp 1-24），該期刊屬于CCF B類英文期刊。
- 論文鏈接：
- https://dl.acm.org/doi/10.1145/3477603
背景與動機
隨著大數據時代的來臨，圖作為一種能夠良好表達數據關聯性的數據結構，在許多領域廣泛應用的同時，圖數據的規模也越來越大。為了加速圖數據處理速度，許多研究選擇將圖工作負載卸載到GPU上，開發出了一批out-of-GPU-memory圖計算系統。這些系統將大規模圖劃分為幾個大小相同的子圖(或稱為塊)，這些子圖能加載到GPU的全局內存中供GPU處理。
實際上，圖計算是基于圖中每個頂點的直接/間接鄰居頂點狀態對其的影響，迭代計算頂點新狀態的過程。然而，對于現有的out-of-GPU-memory圖計算系統，在每輪圖處理中，每個頂點僅根據其直接鄰居頂點的狀態進行頂點狀態更新。因此，算法為了達到收斂，每個間接鄰居頂點的狀態需要沿著圖路徑(間接鄰居頂點與目的頂點之間的路徑)進行多次迭代傳播。如圖1所示，頂點v5的新狀態要傳播到v20需要經過多次迭代才能完成。
圖1 頂點狀態傳播示例
進一步說，由于同一條路徑上的頂點和邊可能被劃分到不同的子圖中，而這些子圖被分配在不同的CPU/GPU核上并發處理，當活躍頂點的狀態沿路徑傳播時，會產生高額的同步開銷和CPU-GPU數據傳輸成本。此外，由于活躍頂點的狀態傳播速度緩慢且代價高昂，許多GPU線程會處于空閑狀態，導致設備利用率低，或者許多GPU核上的頂點使用其直接鄰居的過時狀態進行狀態更新，這導致了大量的冗余圖數據傳輸，當GPU擁有更多處理核心時，冗余圖數據傳輸時間占整個數據傳輸開銷的比率將會更高。
為了充分利用GPU的強大算力來加速out-of-GPU-memory圖計算系統上的大規模圖處理，我們提出了一種基于依賴感知的GPU圖計算加速技術，這是一種輕量級的運行時方法，通過動態獲取源自活躍頂點的依賴路徑來實現更低的數據訪問成本、更快的頂點狀態傳播速度和更高的GPU利用率。
路徑的劃分和存儲
在預處理階段，LargeGraph使用CPU對大規模圖進行并行的路徑劃分。具體來說，LargeGraph首先為每個線程分配一個子圖，這些子圖實際上就是一系列頂點以及和頂點關聯的邊所組成。也就是說，LargeGraph只需要指定每個線程要處理的頂點的起始和結束索引。之后，這些線程會并行地將各個子圖劃分為不相交的路徑。
如圖2所示，對于每個子圖，線程從中選取一個頂點作為路徑的起始頂點，然后以深度優先搜索的方式遍歷邊，并將邊的目的頂點加入到路徑中。在某路徑到達入度大于1的頂點時，線程停止向該路徑繼續加入頂點，并將該入度大于1的頂點作為路徑的終止頂點。之后線程以該終止頂點作為另一路徑的起始頂點繼續進行路徑劃分過程，直到所有邊都被遍歷一遍為止。這樣可以保證劃分的每條路徑除了起始/終止頂點之外，沒有交點。
圖2 路徑劃分示例
劃分完成后，路徑以圖3所示的格式進行存儲。其中數組EIdx存儲頂點索引，兩個連續值表示一條邊。數組Sval大小和EIdx大小相同，它存儲的是EIdx中對應頂點的狀態。PathTable用于存儲每條路徑起始頂點在數組中EIdx的索引值，它相鄰兩項相減的差為前一項對應的路徑長度。Eval和Vval則分別存儲邊的權值和頂點的狀態值(按索引值升序)。
圖3 路徑存儲格式
通過上述路徑劃分方法和存儲格式，LargeGraph可以在執行時根據路徑之間的依賴關系高效地識別所需要的路徑子集。它使我們能夠使用輕量級的運行時方法來動態探索在每一輪圖形處理開始時源自活躍頂點的依賴鏈。
依賴感知的數據驅動執行方法
在圖計算迭代過程中，只有在活躍頂點依賴鏈上的相關數據需要進行處理。因此，在每輪迭代開始前，LargeGraph會將所有活躍路徑進行識別。具體來說，活躍路徑包括：1) 具有活躍頂點的路徑(初始活躍路徑)；2) 從活躍路徑出發，根據路徑之間依賴關系迭代探索到的路徑。在識別完成之后，所有活躍路徑被用于邏輯塊的構成，如圖4所示。然后CPU或GPU會對這些邏輯塊進行處理。這樣，許多與非活動路徑相關聯的圖數據，不會被加載和處理。
圖4 邏輯塊示例
生成邏輯塊時，使用頻率高的路徑被放在同一個塊中。剩余的路徑合并成為使用頻率較低的邏輯塊。然后，邏輯塊調度器將常用邏輯塊的處理分配給GPU。具體實現是，將這些邏輯塊存儲在工作列表Wf中，而使用頻率較低的邏輯塊存儲在其他工作列表Wr中。其中，Wf僅由GPU處理，Wr僅由CPU處理。如圖5所示，Wf和Wr這兩個工作列表是在主機的主內存中創建的。使用頻率高的區塊集和使用頻率低的區塊集會隨著時間的推移而動態變化。工作列表中的邏輯塊分別以異步方式并發驅動CPU線程和GPU線程。當兩個工作列表中都沒有邏輯塊時，流程結束。由于使用頻率高的塊中的圖路徑被反復用于傳播大多數頂點狀態，所以需多輪圖處理來達到收斂。所以，在交換出流多處理器之前，會重復處理每個加載的使用頻率高的邏輯塊，直到其所有頂點都處于非活躍狀態。這樣，每個邏輯塊中的大多數傳播可以通過頻率高的邏輯塊快速到達其他塊。
即使對于列表，其中平均使用頻率較低的邏輯塊可能會使平均使用頻率較高的區塊頻繁地出入GPU，這會導致平均使用頻率更高的塊的緩存抖動。而且，每個邏輯塊的平均使用頻率會隨時間動態變化。因此，LargeGraph還在GPU內存中顯式創建另一個工作列表WfG，并嘗試將使用最頻繁的一些路徑存儲在其中。即使這些路徑在迭代過程中變成了非活躍狀態，也很可能馬上恢復活躍狀態并被頻繁訪問。僅當GPU內存已滿，而且WfG中路徑的平均使用頻率小于需要傳輸到GPU處理路徑的平均使用頻率時，這些路徑才會從GPU中交換出來。換句話說，在GPU線程處理一個頻繁使用邏輯塊后，該線程從GPU內存上的工作列表WfG中獲取下一個要處理的邏輯塊。若無法獲取，則再從主機內存中的工作列表Wf中獲取合適的邏輯塊。
圖5 LargeGraph系統架構
