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

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

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

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

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

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

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

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

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

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