3维线程格 gpu_论文导读 | GPU加速子图同构算法
GPU加速子圖同構算法
作者： 曾立 鄒磊 M. Tamer ?zsu 胡琳 張藩
論文鏈接：https://arxiv.org/abs/1906.03420
本次論文講解的是曾立、鄒磊、M. Tamer ?zsu、胡琳、張藩等作者在 ICDE 2020上發表的論文 GSI: GPU-friendly SubgraphIsomorphism，主要是分享一些閱讀論文的收獲，希望能對正在學習GPU圖計算的初學者帶來一些啟發。
本文將先對圖模型和子圖同構算法作基本的介紹，然后介紹相關的背景知識，如GPU的體系結構和GPU上做子圖同構算法的最新研究等等。
接著，本文將主要介紹 GSI算法及其優化。
最后是實驗和總結。
子圖同構是互聯網搜索與挖掘中常見的問題，給定查詢圖 Q 和數據圖G（如圖 1(a)），我們需要找出 Q 在G中所有的匹配。由于該問題的搜索空間是指數級別的（如圖 1(b)），串行算法無法處理大圖。在圖 1(b) 中，不同搜索路徑的求解是相互獨立的，因此學者們嘗試引入 GPU 的高并發特性來幫助解決這個難題。
這里給出了子圖同構的嚴格定義。在本文中主要討論的圖是無向圖，且同時帶點標簽和邊標簽。GSI算法也可以很自然地拓展到有向圖上。
CUDA 編程模型提供了對這些處理器進行編程的方法，對應著一個線程層級結構。
每個核都被匹配到一個線程，而一個 warp包含 32 個連續的線程且這些線程以 SIMD 形式運行。當一個 warp 運行到一處分支 (if-else 或者是循環) 的時候，其他線程必須等待，即便只有一部分線程要運行一個特定的分支。這就是眾所周知的 “線程發散”(warp divergence)。一個 block由一系列連續的 warp 組成，每個 block 只會駐留在一個 SM 上。GPU 上啟動的每個進程被稱為一個 “核函數” (kernel function) ，每個核函數會占據一個獨立的網格 grid，每個網格包含若干個同等大小的 block。在一個 block 中的線程可以被顯示同步，但 block 之間沒有直接的同步 API 接口，除非等整個核函數完全結束。每個 SM 上可以有多個 SM 駐留，每個網格和 block 的具體大小由程序員自行決定。
其中全局顯存 (global memory) 是最大也最慢的一層存儲，也是 GPU 上直接與主存通信的部分。每個 SM 擁有一個私有的可編程的高速緩存，被稱作 “共享內存” (shared memory)，一個block內所有線程都可以訪問這個 block 申請的共享內存。雖然共享內存的容量很有限 (比如 Titan XP 上每個 SM 只有 48KB 共享內存)，但它幾乎和線程私有的寄存器一樣快。對全局顯存的訪問是通過 128B 大小的塊傳輸來進行的，并且延遲是訪問共享內存的數百倍。如果一個 warp 中的線程以一種連續對齊的方式訪問全局顯存，需要傳輸的塊更少，因此吞吐量更高。
在圖3中，因為是連續對齊的訪問，所以只需要一次塊傳輸即可完成。
而在圖4中，因為訪問沒有對齊，一共需要三次塊傳輸。
雖然 GPU 支持大規模并行，對其粗淺的使用也可能帶來比細致調優后的CPU 實現更差的結果。
將圖算法移植到 GPU 上，會面臨三個主要的挑戰，接下來我們將簡單討論它們。
1. 如果有足夠多的線程，那么圖 1(b) 中所有路徑都可以并行化。但這是不現實的，而且大量重復的工作會嚴重降低性能。
2. 大圖只能放在全局存儲中，其它層級的存儲都放不下。在這種場景下，由于圖結構的不規則性我們很難合并訪存，因此會增加訪存延遲。
3. 當每個處理單元的任務量都相同時，GPU表現最好。但是，在真實圖中，不同節點的鄰居數量非常不同，甚至有些是呈 “冪律分布”的。這會帶來block間、warp間和線程間嚴重的負載不均衡。均衡負載才是更優的做法，因為總的時間開銷始終是被最長的一個負載決定的。
GpSM和GunrockSM也是我們的算法主要對比的算法，它們都使用了寬度優先的擴展模式，因此更適合并行。
對于圖 1的樣例，圖 5 給出了two-step output scheme的具體流程。
中間表 T1和 T2 分別代表查詢圖 Q的邊 (u0,u1) 和 (u1,u3) 在數據圖 G 中的候選匹配。
為了獲得由節點 u0、u1 和 u3導出的子圖的匹配， GpSM 需要進行一次自然連接：T1和 T2。
每個warp拼接當前中間表的一行，每一行可能對應著若干條新的結果，各個warp要將新的結果并行地寫入新的中間表中。
并行意味著它們不能像串行情況下那樣將結果追加到末尾（如果要實現串行，那必須加鎖，加鎖的代價非常高），因此現有的策略是將拼接過程做兩次：第一次找到每行的匹配數量，然后計算出每行結果在新的中間表中的寫入地址（通過一個前綴和計算，prefix-sum）；第二次根據之前計算好的地址將所有結果并行地寫入新的中間表。
除了使用 two-step output scheme 這點外， GpSM 和 GunrockSM 都缺乏對 GPU 特性的利用，因此它們的負載不均衡（比如各warp的任務量很不一樣）和訪存延遲（GPU上的處理器訪問GPU上global memory的延遲）都非常嚴重。這些缺陷使得這兩個已有算法無法充分發揮GPU的性能，在大圖上表現不佳。
GSI 算法由過濾和拼接兩部分組成，這兩個階段都是在GPU 上進行的，都針對 GPU的體系特點進行了優化。 其中過濾階段會得到每個查詢點的候選集，而拼接階段會將這些候選集拼接成最終的結果表。
每個節點的編碼分為兩部分：節點的標簽哈希到的區域，以及節點相連的邊哈希到的區域。
第二個區域又被分為若干組，每組由 2bits組成。如果沒有邊哈希到這組，記為00；如果只有一條邊哈希到這組，記為01；如果有兩條及以上的邊哈希到這組，記為 11。
在 row-first 的存儲方式中，一個warp的32個線程的訪存地址是不連續的，所以無法合并訪存，需要更多的訪存操作。
而在column-first的存儲方式中，一個warp的32個線程的訪存地址是連續的，因此每輪讀取中只需要一次訪存操作。
與 GpSM 和 GunrockSM 不同， GSI 使用的是基于點拼接的策略，而非基于邊拼接的策略。
每輪會拼接當前的中間表以及一個新的查詢點u的候選表，從而生成新的中間表。
每個 warp處理中間表的一行，需要提取這行元素的鄰接表，并和候選表作交集運算。
因為各行都可能對應著若干條結果，各warp間是并發執行的，所以會有并行寫入結果的問題。
GPU上的圖算法一般都使用 CSR作為數據結構，因為它比鄰接表更緊湊。圖 9給出了對應圖1的CSR結構，在這個結構中提取N(v,l)必須先提取v的所有鄰居然后逐一判斷邊標簽是否為l，這毫無疑問是非常低效的。
GSI 將原本的數據圖按照邊標簽劃分為不同的子圖，從而N(v,l) 是被緊密排在一起的。比如邊標簽a 對應的子圖如圖 8 所示，在這個子圖中 v101 節點是不存在的。因為節點編號不連續，這就牽涉到一個定位問題。
圖 8(a)中為每個子圖維護了所有節點的大數組，因此可以在 O(1)時間獲得鄰接表的位置。但如果邊標簽數量很多，這種表示方法的空間代價是不可承受的。圖 8(b)中為每個子圖額外維護了一層節點的ID，從而可以作二分查找。這種表示方法的空間代價很小，但是查找代價較高。
因此，GSI提出了新的 PCSR 結構，如圖 8(c) 所示。在PCSR結構中，節點的ID會先被哈希至某個 group。每個group的大小是按照GPU顯存傳輸的單位來設置的，即128B。一個group最多可以存放15個點ID，如果有溢出，則可以另外找一個空的group來存放。在PCSR中，定位點的鄰接表N(v,l)只需要一次訪存，空間開銷也較小，因此非常高效。表 1給出了這些結構的性能分析。
為了能并行地寫入新的結果，GSI 提出了一種新的拼接方法。
先估算每行的新結果數量的上界，然后按照這個上界給它們在顯存分配緩沖區。
拼接過程中，新結果可以先寫入緩沖區中保存起來，等新的中間表分配好后，再把這些新結果寫入到新的中間表中。
通過這種方式，無需重做拼接過程，因此節省了大量的工作量。
第8行的差集運算主要是為了滿足同構的要求，匹配中不能有重復的節點。
在第8-11行中，可能存在大量的無效的元素，所以對顯存的寫操作是比較低效的。
比如32個線程讀取了32個元素，其中只有一個元素是有效的，那么一次顯存傳輸 (128B) 只用到了 4B。
因此，GSI 借由 shared memory 為每個warp實現了寫緩存 (128B)，只有寫緩存滿了，才會一次性刷到顯存中。
負載均衡策略：根據鄰接表的大小分別考慮。特別大的鄰接表，單獨啟動一個新的核函數去處理；較大的鄰接表，用整個block去處理；規模一般的鄰接表，用多個warp協同處理；較小的鄰接表，直接用整個warp來處理。
本文在實驗中對比了 CPU 上的三個算法和 GPU 上的四個算法，所用的數據集除了 WatDiv 之外都是真實數據集，涵蓋了社交網絡和道路網絡等多個領域。 其中，WatDiv 和 DBpedia兩個數據集的邊數已經達到了億級。
GSI算法分為兩個版本，一個是基礎實現 GSI，另一個是加上優化（負載均衡和共享輸入緩沖區）后的實現 GSI-opt。
與已有的方法相比，我們的方法成功地利用了GPU 來加速子圖同構的計算，并充分考慮了GPU 的特性來對算法和數據結構進行優化，因此在負載均衡、訪存延遲和總的工作量等方面都有明顯的改進。
從結果中可以看出，GSI在查詢性能上比其他方法提升了幾個數量級，在所有數據集上都實現了秒級的響應。
References
[1] M. R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness.W. H. Freeman, 1979.
[2] Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento.Thirty years of graph matching in pattern recognition.IJPRAI, 18(3):265–298, 2004.
[3] Li Zeng, Lei Zou, M. Tamer ?zsu, Lin Hu, and Fan Zhang.Gsi: Gpu-friendly subgraph isomorphism.ICDE, 2020.
[4] Martin Burtscher, Rupesh Nasre, and Keshav Pingali.A quantitative study of irregular programs on http://gpus.In IISWC, 2012.
[5] Ha Nguyen Tran, Jung-jae Kim, and Bingsheng He.Fast subgraph matching on large graphs using graphics http://processors.In DASFAA, 2015.
[6] Leyuan Wang, Yangzihao Wang, and John D. Owens.Fast parallel subgraph matching on the gpu.HPDC, 2016.
[7] Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra.Worst-case optimal join algorithms: [extended abstract].In PODS, 2012.
[8] Vincenzo Carletti, Pasquale Foggia, Alessia Saggese, and Mario Vento. Challenging the time complexity of exact subgraph isomorphism forhuge and dense graphs with VF3.
IEEE Trans. Pattern Anal. Mach. Intell., 40(4):804–818, 2018.
[9] Fei Bi, Lijun Chang, Xuemin Lin, Lu Qin, and Wenjie Zhang.Efficient subgraph matching by postponing cartesian http://products.In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, SanFrancisco, CA, USA, June 26 - July 01, 2016, pages 1199–1214, 2016.
[10] Amine Mhedhbi and Semih Salihoglu.Optimizing subgraph queries by combining binary and worst-case optimal joins.VLDB, 2019.
[11] Fuad Jamour et al.Matrix algebra framework for portable, scalable and efficient query engines for rdf http://graphs.In EuroSys, 2019.
[12] Siyuan Wang et al.Fast and concurrent rdf queries using rdma-assisted gpu graph http://exploration.In USENIX ATC, 2018.
作者：北京大學 曾立
非授權不可轉載
微信公眾號、知乎號“圖譜學苑”每周發布最新知識圖譜動態，專業知識圖譜相關論文導讀，歡迎關注投稿。
總結
以上是生活随笔為你收集整理的3维线程格 gpu_论文导读 | GPU加速子图同构算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 娃哈哈八宝粥里面的硬壳是什么东西？
- 下一篇： 龙井多少钱 了解龙井茶的市场价格？