引言
GPU最初是針對圖形渲染等應用而進行專門的設計，并且做為外圍裝置的形态而存在，随着制造技術的發展，GPU中內建了更多了并行計算單元和控制單元，其并行計算能力得到了長足的發展，由于近年來衆多計算密集型應用的發展，GPU逐漸被應用于高性能計算、智能計算等多種場景，成為目前高性能計算領域不可或缺的一種重要計算單元。
在典型的GPU處理器架構中，一個GPU處理器包含多個多流處理器（SM），SM之間通過高速内部網際網路絡進行連接配接。一個SM中包含若幹個流處理器（SP）和片内共享存儲單元等部件，一個SM中的多個SP通過共享存儲單元進行資料共享，不同的SM之間則隻能通過GPU闆載記憶體DRAM進行資料共享，GPU與主機之間則通過PCI-E擴充總線進行連接配接，典型的GPU體系結構如圖1所示。
圖（1）GPU體系結構示意圖
GPU和CPU的主存都是采用DRAM實作，存儲結構也十分類似。但是CUDA将GPU記憶體更好地呈現給程式員，提高了GPU程式設計的靈活性。GPU記憶體結構如圖1所示，主要包括位于SP内部的寄存器（Register）、位于SM上的共享記憶體和GPU闆載的全局記憶體（Globalmemory）。
圖2GPU記憶體結構示意圖
在NVIDIA提出的CUDA統一程式設計模型中采用Grid的方式管理GPU上的全部線程，每個Grid中又包含多個線程塊（Block），每個Block中又可以劃分成若幹個線程組（Warp），Warp是GPU線程管理的最小機關，Warp内的線程采用單指令多線程（SIMT）的執行模式。
CUDA線程管理的基本結構如圖3所示：
（圖3CUDA線程管理模型示意圖）
GPU獨特的體系架構和強大的并行程式設計模型，使得GPU在并行計算和記憶體通路帶寬方面具有獨特的性能優勢，相對于傳統的CPU體系結構，GPU具有一些獨特的優勢：
①并行度高、計算能力強；②訪存帶寬高，圖處理由于其計算訪存比高，算法執行過程中計算次數多、單次計算量小的特點天然地與GPU的硬體特征相比對。
- 以顔色為中心的着色機制對算法性能的影響
（圖4不同着色方法中沖突頂點占活躍頂點的比例）
本文通過監測不同着色方法中沖突頂點占活躍頂點的比例，來驗證以顔色為中心的着色機制對算法性能的影響。
實驗結果如圖4所示，在不采用以顔色為中心的線程管理機制時Stanford,youtube以及random分别需要24輪以上疊代方可收斂，然而在采用以顔色為中心的線程管理機制的算法中，僅需要不超過11輪疊代即可收斂。
圖5通過GPU多流處理器上線程運作的滿載率來展示了算法每一輪疊代中GPU的使用率。
如圖所示，采用以顔色為中心的線程管理機制可以将GPU使用率提高111%—410%（分别在RoadNet和Stanford兩個資料集上取得最小和最大值），也就是說每一輪計算過程中，以顔色為中心的線程管理機制有更多指令被加載到GPU執行，這也證明了以顔色為中心的線程管理機制可以提高算法的并行度。
（圖5GPU多流處理器上線程運作滿載率）
圖6展示了算法每一輪疊代中平均活躍線程組的變化。
實驗結果表明，不采用以顔色為中心的線程管理機制時，在RoadNet資料集上平均活躍線程組最多，但是也不超過2.2個，然而在采用以顔色為中心的線程管理機制後，RoadNet資料集上的平均活躍線程組可達3.12個，在Stanford資料集上，采用以顔色為中心的線程管理機制，可以将活躍線程組的數量提高4.9倍。
（圖6平均每輪疊代中平均活躍線程組的數量）
實驗展示了以顔色為中心的線程管理機制在算法執行過程中可以有更多的活躍線程組，也就是采用以顔色為中心的線程管理機制将使得算法具有更高的并行度。
- 不同GPU裝置對算法性能的影響
(圖7 Feluca在不同GPU上的性能表現)
為了測試Feluca算法在不同GPU裝置上的可擴充性，本文章采用了NVIDIAK20M,NVIDIAK40以及NVIDIAP100三款GPU來對Feluca的進行評估，NVIDIAK20M的闆載記憶體空間為5GB，配備2496個CUDA核心，NVIDIAK40的闆載記憶體為12GB，同時配備2880個CUDA核心，而NVIDIAP100則具有16GB闆載記憶體和3584個CUDA核心，在不同GPU上對算法均采用相同的參數，圖2.10展示了Feluca在不同GPU上的性能表現。
實驗結果表明，Feluca的計算性能随着GPU的計算能力擴充，具有較好的可擴充性。
針對GPU上圖着色算法中由于顔色選擇過程中的資料依賴導緻的并行度低的問題，本章提出了一種以顔色為中心的兩階段着色算法。Feluca，Feluca中融合了疊代式着色方法和周遊式着色方法，通過檢測每一輪計算過程中活躍頂點與沖突頂點的比例進行不同着色方法的切換，本文章所提出的方法充分利用了兩種着色方法的優勢，同時避免了各自的缺陷。
3、面向局部記憶體的活躍隊列維護和更新技術
在多個并發的周遊操作中，如何共享一個任務隊列将成為影響算法性能的關鍵，為此，本章進一步提出了一種基于部分和的任務隊列維護和更新政策，将多個活躍頂點對應的工作隊列合并到一個任務隊列中，進而降低多個活躍隊列的記憶體開銷。
（圖8聯合周遊示意圖）
聯合周遊技術分别采用一個status數組和一個frontier隊列來記錄頂點狀态及其對應的活躍頂點圖8展示了一個簡單的聯合周遊示意圖，示例中展示了同時從頂點1和5周遊圖如圖所示：
采用兩個元素來追蹤不同頂點開始的周遊過程中頂點的狀态（每個元素對應從一個頂點開始周遊的狀态），在該示例中，計算核心包含兩個線程/線程組，每個線程/線程組從各自對應的頂點（頂點1和5）開始執行周遊過程。
然而，FrontierArray則通過WarpVote操作将所有線程/線程組通路過程中的活躍頂點進行了合并，并将所有頂點存放于一個統一的隊列中。
是以，對應于多個線程/線程組的同一活躍頂點在活躍隊列中僅出現一次，這一技術将有效去除活躍隊列中重複的元素，進而降低活躍隊列的内開銷，基于以上技術背景，在O(n)空間開銷内實作粗粒度并行的介數中心度算法成為可能，但是聯合周遊技術在合并多個活躍隊列的過程中打亂了活躍頂點的順序，進而破壞了周遊過程中線程對記憶體的連續通路。
（圖9 面向局部記憶體的活躍隊列更新和維護技術示意圖）
為了合并多個活躍隊列，同時保持連續記憶體通路，本章提出一種面向局部記憶體的活躍隊列更新和維護政策，本章采用一個分段和數組來記錄每一個周遊中的活躍隊列（也就是目前通路頂點的前序頂點）。
如圖9所示，與聯合周遊政策中的WarpVote操作不同的是，本章将一個周遊所對應的活躍頂點通過分段和的形式映射到FrontierArray中的一個固定長度的區域，例如第j個周遊中的活躍頂點将被映射成FrontierArray中的第j個塊。
4、混合消息傳遞政策
Push/Pull政策是圖處理算法中常用的消息傳遞技術之一，圖10展示了基于push和pull的消息傳遞政策，左側為push模型，右側為pull模型，在push模型中，目前活躍頂點主動推送需要更新的消息值給候選活躍頂點（下一輪次中被執行的頂點）。
相反，在pull模型中，則是采用候選活躍頂點主動向上一輪中的活躍頂點請求需要更新的資訊，如圖在push模型中，一個頂點可以同時向多個頂點發送消息，并啟動消息寫操作。
（圖10push/pull消息傳遞模型示意圖）
目前已有工作充分研究了GPU上push/pull模型各自的開銷，研究結果顯示，push模型更适合高度數頂點上的同步計算模型，但是在幂率圖中需要大量的原子操作來處理高入度頂點上的資訊更新，以防止寫—寫沖突，相反，pull模型則更适合于高入度頂點，因為高入度頂點可以一次性擷取來自更多頂點的消息傳遞。
由于pull模型可以在上一輪頂點計算完成時立即擷取其所需要更新的資訊，是以不會出現寫—寫沖突的問題，但是在pull模型中，目前頂點需要等待與其關聯的上一輪活躍頂點全部執行完畢方可執行計算操作。基于push/pull的混合消息傳遞模型算法
（公式1）
為了平衡push/pull消息傳遞模型中的沖突，本章同時實作了基于push和pull的消息傳遞模型，Galliot在高度數頂點上采用push模型進行消息傳遞，對于其他低度數頂點則采用pull模型進行處理，在本章的實作中，定義一個變量ϑ來監控不同線程上的執行任務。算法啟動時采用基于pull的消息傳遞模型，當ϑ>1時切換至push模型（類似于基于方向優化的BFS技術）。
（表A介數中心度算法實驗資料集）
上節中采用了NVIDIAK20M，K40C以及P100三種GPU來評估Galliot在不同GPU上的性能表現，其餘實驗均在NVIDIA P100上完成；NVIDIA P100 GPU配備16GB闆載記憶體以及3584個CUDA核心，NVIDIAK40C則配備12GB闆載記憶體和2880個CUDA核心，NVIDIAK20M的闆載記憶體則隻有5GB，且CUDA核心數為2496個。
本文實驗采用的主機配置2顆Intel(R)Xeon(R)E5-2670CPU，每台主機配備8個CPU和32GB記憶體，作業系統為Ubuntu (version 16.04.10)，CUDA版本為9.0，代碼編譯過程中均采用“-arch=sm35”參數來指定 GPU計算能力。
- 記憶體空間消耗的具體情況
為了驗證Galliot對記憶體空間消耗的情況，首先驗證Galliot與目前已有工作在相同裝置上可處理的圖資料的規模，然後進一步設計實驗驗證Galliot在執行過程中臨時記憶體開銷。與目前已有工作的評估方法類似，我們采用MTEPS（每秒所周遊的百萬條邊數）來衡量算法的性能。如果m和n分别表示圖資料的邊數和頂點數，t表示算法的執行時間，那麼TEPS（每秒所周遊的邊的條數）的定義如（公式2）所示：
（公式2）
（圖11Hybrid_BC每秒所周遊的邊數）
（圖12Hybrid_BC以及Galliot的算法性能 ）
圖11和圖12分别展示了GPU上介數中心度計算方法Hybrid_BC以及上述所提出的Galliot算法的性能。
圖11顯示，在闆載記憶體為16GB 的NVIDIAP100GPU上Hybrid_BC在執行RMAT16-2以及更大的twitter-2010等大規模圖時發生了記憶體溢出的錯誤；圖12中實線對應左側縱坐标表示算法執行過程中每秒周遊的百萬條邊數；虛線對應右側縱坐标，表示算法的執行時間，機關為毫秒(ms)。
圖12顯示，本章所提出的介數中心度計算方法Galliot能夠正常處理超大規模圖twitter-2010和webbase-2001，其中webbase-2001資料集的頂點數和邊數分别為RMAT16-2資料集的11.32倍和5.67倍；本節實驗充分證明了Galliot所提出的面向局部記憶體的活躍隊列維護和更新政策能夠減少介數中心度計算過程中臨時記憶體的開銷，所處理圖資料的規模相對于已有工作可以提升近一個數量級。
（圖13不同算法中頂點更新所需的記憶體load操作數）
圖13中柱狀圖示對應左側縱坐标，表示算法執行過程中所需的全局記憶體load操作數；折線圖示對應右側縱坐标，表示一次頂點更新操作的所需的平均記憶體load操作數；其中“OF”表示Hybrid_BC在執行過程中出現“Over Flow”錯誤，而“OOM”則表示執行過程中出現記憶體溢出的問題。
實驗結果顯示，相比于Hybrid_BC算法，本章所提出的Galliot算法在每次記憶體通路操作中所需的load操作數更少；具體而言，本章所提出的Galliot算法平均需要4—6次load操作即可完成一次頂點更新，然而Hybrid_BC則需要大約8次load操作才能完成一次頂點更新。另外，在大規模資料集webbase-2001上，Galliot平均僅需2.9次記憶體load操作即可完成一次頂點更新，然而在Hybrid_BC中，擷取每一個活躍頂點的過程中，算法需要至少一次訪存。
- 局部記憶體的活躍隊列更新和維護政策
監測算法在采用面向局部記憶體的活躍隊列維護政策與否兩種情況下cache命中率，來驗證本章所提出的活躍隊列維護政策對算法性能的影響。實驗結果顯示，采用面向局部記憶體的活躍隊列維護政策能夠取得更好的記憶體通路模式，其中L2cache命中率以及統一cache命中率分别如圖14和圖15所示。
（圖14局部記憶體的活躍隊列維護方法與否算法L2cache的使用率）
圖14顯示，采用面向局部記憶體的活躍隊列維護政策在不同實驗資料集上可以将L2級Cache命中率提高14.43—23.49個百分點，實驗同時還顯示L2級cache命中率的提升在web-Stanford，dblp-2011；youtube以及Live Journal等幂率圖上顯得較為直覺，并且在大直徑圖Road Net-CA上的性能提升最大。
由于圖資料複雜的關聯關系，導緻圖資料處理過程中存在大量的随機通路，進而導緻大量的cache miss開銷。本節通過實驗證明，我們所提出的面向局部記憶體的活躍隊列維護政策，可以将介數中心度計算這一應用L2級Cache命中率提升至72.18%。
（圖15局部記憶體的活躍隊列維護方法與否算法cache的使用率）
圖15顯示在采用面向局部記憶體的活躍隊列維護政策前後Galliot在除了webbase-2001之外的資料集上的cache命中率處于一個穩定區間。實驗結果還顯示，面向局部記憶體的活躍隊列維護政策對cache命中率的提升分别在youtube和twitter-2010資料集上達到最佳和最差表現，但是另一方面，Galliot在兩個資料集上的cache命中率卻始終維持在一個較低的水準。Galliot在多個圖資料集上的統一cache命中率均不超過35.94%，結合圖14中顯示的GalliotL2級Cache命中率可達72.18%的現象，這也從側面反映了Galliot算法中仍然存在較多的通路沖突。
本小節中所提出的面向局部隊列的活躍隊列維護政策中，首先将活躍隊列劃分成多個資料塊（資料塊的大小為線程/線程組大小的整數倍），然後根據線程/線程組與活躍隊列中活躍頂點的對應關系，将不同線程/線程組對應的活躍頂點通過分段和的方法映射到統一活躍隊列中的某一片段。
- Galliot 在不同GPU上的性能表現
（圖16 Galliot 在不同GPU上的性能表現）
實驗在不同裝置上執行Galliot算法，并監測其性能表現。實驗結果如圖16所示。實驗中采用了NVIDIAK20M、K40C以及P100三個GPU裝置，其中K20M和K40C為Kepler架構，而P100則為Pascal架構。實驗結果顯示Galliot在K40C上相較于K20M上平均可獲得1.13倍性能加速，在P100上相較于K40C上平均可獲得3.26倍性能加速，算法性能在一定程度上随GPU性能擴充。
總結：
基于圖資料處理的研究工作引入了多種方法來度量頂點特性和重性，介數中心度通過研究頂點在最短路徑上出現的頻率來衡量該頂點的重要性，既能保留圖結構的局部資訊，也能反映圖結構的全局資訊，然而，目前已有的介數中心度計算算法都存在計算過程中記憶體膨脹的問題。
針對GPU上介數中心度計算過程中存在的計算備援和記憶體空間膨脹問題，提出了一種基于路徑合并技術的介數中心度計算方法，首先通過合并計算過程中的局部最短路徑對計算過程進行剪枝，然後對多個臨時隊列進行合并，降低計算過程中的臨時記憶體開銷。從理論上證明了路徑合并政策的可行性，提出了一種面向局部記憶體的活躍隊列維護和更新政策，實作了多個活躍隊列的合并，降低了計算過程中的臨時記憶體開銷。