会议室分配时间最长_论文导论动态任务分配GPU上图计算的高效处理方式
背景介紹
上圖是一個GPU上的圖架構的簡單表示。硬件層來說GPU上的全局內存與主機內存相通，可以進行數據傳輸；GPU上有許多流多處理器(SM)，每個流多處理器上有自己若干個核和自己的片上緩存，是相對獨立的單元。軟件層次上，程序員啟動核函數(grid)，其中包括多個block，每個block上又有若干warp。Block是依賴于流多處理器的，每個block只會運行于一個流多處理器。值得一提的是，每個warp中包含32個線程，這32個線程是按照嚴格單指令多線程的形式運行的，是嚴格的同步關系，因而warp內部線程在運行代碼遇到分支或者循環結構時的線程發散會導致warp內部分線程的空閑，并且warp內線程執行的任務量的不均衡會導致很嚴重的線程發散，因為所有線程都在等待運行時間最長的線程結束。
線程發散是我們試圖尋找更好的任務分配方式的初衷，更好的任務分配方式能夠保證更少的線程發散，從而提升整體性能。上圖是GPU上的存儲訪問示意圖，圖(a)中，相鄰的線程訪問的是相鄰并且對齊的地址，這樣多個線程所需要的數據可以在較少的訪存請求中一起取回來，而(b)圖中線程訪問的地址是隨機的，無序的，就需要更多的訪存次數。我們稱(a)圖中的模式是合并訪存模式，是一種更加高效的訪存方式。例子：
首先我們會以三角形計數為例子，講解什么是更好的任務分配方式。在圖(graph)表示中，三個彼此相鄰的節點我們稱作一個三角形，三角形計數算法是求解一個圖中所有三角形數目。通常三角形計數的方式如上圖所示：對于一條邊，對這條邊的起點(src)和終點(dst)的鄰接表取交集，交集的大小就是這條邊所在的三角形的數目。很自然的，在三角形計數算法移植到GPU上的時候，我們可以以邊作為任務分配的單位，一個線程負責處理一條邊，計算這條邊所在的三角形的個數。這種分配方式看起來很直觀，但是會導致任務分配不均衡的情況，因為在常見的power-law圖中鄰接表的大小區別很大，線程的工作量也就會有很大區別，從而導致線程發散。上圖中介紹了一種優化了的任務分配方式，首先對于所有邊的任務進行估計，然后把邊按照任務量的大小分成不同的組。對于任務量很大的邊所在的組，每個邊分配多一些線程去處理，任務量少的邊就分配較少的線程。這個方式利用事先對任務量的估計，根據任務量分配計算資源，在一定程度上緩和了線程工作量負載不均衡的問題，比前面介紹的根據邊分組相比，有更好的效果。論文1:?GPU-based Graph Traversal on Compressed Graphs
SIGMOD 2019
本文設計了一個GCGT的圖處理系統，針對的是大規模圖中的并行算法，并且算法中包含“擴張—過濾—壓縮”的過程。
上圖以BFS為例，展示了在BFS的每一輪擴展的前沿(frontier)生成過程中，“擴張—過濾—壓縮”的具體過程。這里“擴張”的依據是鄰接關系，“過濾”是取出未訪問節點，“壓縮”是生成新的前沿節點。這種計算模式在BC (Betweeness Centrality), CC(Connected Component)等算法中也有很多的應用。?由于是大規模圖，本文中首先采用已有的方式進行圖的壓縮表示，如下圖所示。上圖表示了圖中鄰接表的壓縮過程，鄰接表中連續的元素成為一個interval，只記錄其首個元素和大小，不連續的元素成為residual，單獨列在后面。Interval和residual記錄的都是和前一個元素的差，這樣可以減小存儲空間。同時文章又采用了VLC 編碼的方式，壓縮字符的存儲位數，進一步減少存儲空間。這里我們只討論圖遍歷算法，即給出一個前沿向外擴展，并如此迭代進行的過程。上圖算法一中給出了一個直觀的算法，每個線程負責處理一個點的鄰接表，直接擴展這個鄰接表中的所有節點。跟例子中介紹的直觀三角形計數算法影響，由于圖的power-law的性質，線程之間會存在比較明顯的工作量負載不均衡的情況。
算法二中給出了GCGT的實現：所有的線程會先處理intervals然后處理residual，并且一個warp中的所有線程會同時進入處理residuals的階段。并且處理interval也是分成兩步，先處理長度大于32(一個warp的大小)的interval，再處理小于32的。上圖中給出了一個圖表示，圖中共有8個節點。同時，圖例中是線程處理residual和interval的圖例。在這個算法中，每個線程起初仍然先獲得一個鄰接表，只不過后面warp中的32個線程協同處理獲得的32個鄰接表。上圖中是直觀實現中，示例圖的處理流程圖。每個線程面對一個鄰接表，都要先解碼，然后處理interval和residual。考慮到warp內線程的lock-step執行特性，decoding、處理interval、處理residual是不能同時進行的。所以圖中會有大量idle的存在，并且整個warp的運行時間是由運行時間最長的線程決定的。上圖中表示的是GCGT框架下的處理流程圖。這里主要是針對interval做了改進。所有的線程先協同處理最長的interval(圖中t2獲得的鄰接表)，剩下的Interval拼接起來，也由全部的線程協作完成。這里整體的處理周期由25縮減成11，有了非常明顯的提高。?對于residual部分，也有一些改進，如下圖所示。對于residual的處理也包括了解碼和訪存兩部分，這里采用的優化是所有的線程先完成自己任務中residual的解碼，然后把任務拼接起來所有線程共同完成訪存。可以看到整體周期進一步縮減成9。每個線程要獨自完成解碼的原因是由編碼的方式導致的，解碼需要用到前一個元素的真實值。最后從實驗結果來看，橫向比較中GCGT比其他框架都有性能優勢，只比GPU上的CSR表示略差，但是提供了一定的壓縮比；縱向來看，每一步策略都取得了一定的優化效果。論文2:?High Performance and Scalable?GPU Graph Traversal
TOPC?2015
本文中使用到任務動態分配的部分，也僅僅是從鄰接表中收集鄰居的部分。詳細來說，對于一個BFS過程，這個算法僅僅從一系列鄰接表中讀進來所有的鄰居，并且加載進本地存儲或寄存器中。接下來我們比較幾種實現。
1. ?順序讀取
每個線程獲取一個鄰接表的起始和終止范圍，然后負責記載這個鄰接表中的所有元素。很顯然，這是一個非常na?ve的想法，線程的負載均衡會很差。
2. ?粗粒度的，warp協同的方法
下圖算法5中展示了warp協同的方法，warp中的線程競爭warp的控制權，競爭的勝利者將自己的任務廣播給warp中所有的線程，大家一起完成該任務，然后重復“競爭-廣播-協作”的過程。
此方法中，warp內每個線程的工作都是由整個warp內所有的線程協同完成的，比較好地均衡分配了任務。
3. ?細粒度的，基于scan的方法
下圖展示了基于scan的方法的算法流程。這個方法中，將一個block中所有的線程獲得的鄰接表都拼接到一起，然后所有block中的線程協作處理這個拼接完成后的表。這個算法比上一個算法更好的地方在于協調了整個block內線程的工作負載，但是也有額外的拼接代價。
4. ?Scan+warp 協調+block協調的方式。
1)?鄰接表長度非常大的線程首先競爭整個block的控制權，整個block的運算資源都一起處理這個鄰接表。
2)?剩下的線程中，鄰接表長度適中的，線程競爭warp控制權，整個warp協作處理。
3)?最后剩下工作量比較小的線程，所有的任務拼接到一起，由整個block協作完成。
這個算法很好地協調了整個block內的工作負載的均衡性，又減少了大量拼接的代價，是最優的解決方案。從下面的三個性能指標中也能看出來，上面幾種算法的性能，以及跟最優性能之間的差異。論文3:Update on Triangle Counting on GPU
HPEC 2019
這篇文章研究的是GPU上的三角形計數算法，其中na?ve的三角形計數的任務分配在前面已經介紹過了，使用一個線程處理一條邊。下面的算法1就是這種實現的偽代碼。上文中我們還介紹了優化的三角形計數的任務分配，即根據任務量的預先估計，給每個邊分配合適的線程，使得線程的任務大致相當。但是這種算法也有它的局限性：預先估計需要消耗額外的時間；并且同一組中的邊獲得相同數目的線程，但是實際上它們的任務量也有區別。本文中提出了動態分配的三角形計數算法，算法偽碼如下算法2所示這里采用的方法跟前面的兩種論文中的思想有些類似，一個線程獲得整個warp的控制權，向所有線程廣播自己的任務，然后大家協同完成這組任務，這樣warp內線程的工作是非常均衡的。實驗效果如下圖所示總結
動態任務分配是GPU上進行圖計算任務中一種比較好的任務分配方式，可以使線程之間的工作量更加均衡，很好解決圖的不規則形帶來的問題，并且能夠減少線程的發散，實際上也有更好的合并訪存效果。這種方法也不是完美的，動態計算需要額外的計算開銷，以便得到線程各自的任務。當然這種負面影響完全可以被所帶來的性能提升抵消。綜合而言，這種方法還是非常值得我們學習和借鑒。參考文獻
[1]?J. Fox, O. Green, K. Gabert, X. An, and D. A. Bader. Fast and adaptive list intersections on the gpu. In 2018 IEEE High Performance extreme Computing Conference (HPEC), pages 1–7. IEEE, 2018.?[2]?O. Green, J. Fox, A. Watkins, A. Tripathy, K. Gabert, E. Kim, X. An, K. Aatish, and D. A. Bader. Logarithmic radix binning and vectorized triangle counting. In 2018 IEEE High Performance extreme Computing Conference (HPEC), pages 1–7. IEEE, 2018.[3]?Sha M, Li Y, Tan K, et al. GPU-based Graph Traversal on Compressed Graphs[C]. international conference on management of data, 2019: 775-792.[4]?Duane Merrill, Michael Garland, and Andrew Grimshaw. 2015. High-Performance and Scalable GPU Graph Traversal. ACM Trans. Parallel Comput. 1, 2, Article 14 (January 2015), 30 pages.[5]?C. Pearson?et al., "Update on Triangle Counting on GPU,"?2019 IEEE High Performance Extreme Computing Conference (HPEC), Waltham, MA, USA, 2019, pp. 1-7, doi: 10.1109/HPEC.2019.8916547.總結
以上是生活随笔為你收集整理的会议室分配时间最长_论文导论动态任务分配GPU上图计算的高效处理方式的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 光大银行上门催款吗？
- 下一篇： 储蓄卡不用要注销吗？