基于GPU異構體系結構的大規(guī)模圖數(shù)據(jù)挖掘關鍵技術研究.pdf

1、圖（graph）作為最基本的數(shù)據(jù)結構之一，在生物信息學、化學數(shù)據(jù)分析、社交網絡研究以及程序 bug檢測等眾多應用領域被用于構建和表示對象之間的復雜關系。隨著這些應用領域的不斷發(fā)展，圖數(shù)據(jù)挖掘作為這些應用領域的關鍵基礎工具，重要性日益凸顯，涉及領域和內涵不斷擴展。由于這些領域應用圖數(shù)據(jù)規(guī)模的不斷增長，而且大多數(shù)圖處理算法具有很高的計算復雜度，因此大規(guī)模的圖數(shù)據(jù)挖掘急需高性能計算研究的支持。近些年來，相對通用CPU計算平臺GPU異構計算平臺

2、由于在計算能力、訪存帶寬、性能功耗比方面的明顯優(yōu)勢，逐漸被廣泛的應用于眾多通用計算領域，也為高效的處理大規(guī)模圖數(shù)據(jù)提供了機遇。本文針對大規(guī)模圖數(shù)據(jù)挖掘領域的幾類重要問題，其中包括：圖遍歷、圖分析、圖同構與圖挖掘，研究了其典型算法在 GPU平臺上的細粒度并行問題，提出了相應的基于 GPU的并行算法，集中解決了基于 GPU的細粒度并行算法設計中面臨的若干技術難點，達到了提高大規(guī)模圖數(shù)據(jù)挖掘性能的目的。本文取得的重要研究成果如下：
　　

3、1.基于GPU的大規(guī)模圖遍歷研究
　　本文提出了基于優(yōu)化的頂點前沿隊列的GPU廣度優(yōu)先搜索算法，解決了已有基于頂點前沿隊列的并行廣度優(yōu)先搜索算法在每層迭代內兩個階段中遇到的性能瓶頸。主要包括：針對已有算法鄰居收集過程中采用的prefix-sum和warp-centric任務調度方法在 GPU Warp內出現(xiàn)負載不均衡問題，提出了基于虛擬隊列的任務調度方法更好的緩解鄰居收集過程中的負載不均衡問題；其次針對已有的邊前沿隊列局部去重方法

4、的不足，提出了一種新的全局去重方法，完全剔除邊前沿隊列的重復頂點，另一方面針對無尺度圖的廣度優(yōu)先遍歷中某幾次迭代中邊前沿隊列冗余頂點多的問題，提出了一種正向和逆向混合的遍歷方法，有效的減少了對冗余頂點的遍歷。實驗結果表明，本文提出的算法相對目前性能最好的GPU廣度優(yōu)先搜索算法Merrill算法，在基于Nvidia K40c GPU的異構計算平臺上最高獲得了3.2倍的性能加速比。
　　2.基于GPU的大規(guī)模圖分析研究
　　本文

5、提出了一種基于GPU的圖中介中心度計算算法。針對中介中心度計算過程中的最短路徑計算階段和相關度累加階段，首先結合前一章提出的基于虛擬隊列的任務調度方法和全局去重方法給出一種基于前沿隊列的方法，有效的解決了已有的基于前沿隊列方法中遇到的負載不均衡問題，同時消除了其對原子操作的使用。此外，提出一種基于收集的最短路徑數(shù)目計算方法，消除了最短路徑數(shù)目統(tǒng)計中的數(shù)據(jù)競爭。其次，提出一種改進的基于頂點并行的方法，解決了已有基于頂點并行方法負載不均衡問

6、題。最后，提出一種混合方法，有效的整合了前面兩種算法各自的優(yōu)勢。實驗結果表明，本文提出的算法相對目前性能最好的GPU中介中心度計算算法Mc-Sampling算法，在基于Nvidia K40c GPU的異構計算平臺上獲得了1.2-1.9倍的性能加速比。同時，該算法還具有良好的可擴展性。
　　3.基于GPU的大規(guī)模子圖同構查詢研究
　　本文首次提出了一種基于圖遍歷的GPU子圖同構算法，該算法使用區(qū)域遍歷方法確定匹配順序，主要由

7、GPU區(qū)域遍歷和 GPU子圖匹配兩部分組成。工作主要包括：首先，針對區(qū)域遍歷過程，基于深度優(yōu)先遍歷過程中形成的部分子樹映射樹中不同分支上頂點（部分子樹映射）之間的獨立性和不同分支控制流的相似性，給出了一種遞歸計算模式的數(shù)據(jù)集細粒度并行方法，提出了一種細粒度的數(shù)據(jù)級并行的區(qū)域遍歷算法，同時給出了一種高效的面向并行區(qū)域遍歷的用于存儲候選頂點集合的數(shù)據(jù)結構。其次，針對子圖匹配過程，利用子圖匹配迭代中不同的部分子圖映射的獨立性，提出了一種基于候

8、選頂點擴展的GPU子圖匹配算法。最后，針對圖的不規(guī)則性帶來的區(qū)域遍歷和子圖匹配過程中負載不均衡問題，提出了兩種負載均衡的任務分配策略。研究結果表明，相比目前性能最好的CPU子圖同構算法TurboISO算法，在基于Nvidia K40c GPU的異構計算平臺上，本文提出的GPU算法獲得了1.4-2.6倍的加速比。
　　4.基于CPU/GPU異構平臺的頻繁子圖挖掘研究
　　本文提出了一種基于CPU/GPU異構平臺的gSpan頻繁

9、子圖挖掘算法，有效的挖掘了gSpan算法的粗粒度和細粒度并行性。工作主要包括：首先，針對模式圖擴展，提出一種基于虛擬隊列的并行子圖映射擴展算法，解決了已有并行子圖映射擴展的負載不均衡問題。其次，針對擴展邊的支持度計算，提出兩種相比已有方法時間復雜度更低的并行支持度計算算法，基于數(shù)據(jù)圖收集的方法和基于擴展邊排序的方法，分別用于處理兩種不同類型圖數(shù)據(jù)集的支持度計算。然后，針對最小DFS編碼驗證可并行性低的問題，提出了一種基于CPU的粗粒度并