本文關(guān)鍵詞：基于GPU的空間并行算法研究與實(shí)現(xiàn)

  更多相關(guān)文章： GPU 快速排序 R-Tree索引 最近鄰搜索 并行計(jì)算

【摘要】：GPU(Graphics Processing Units)是由NVIDIA公司研發(fā)的一種專門用在移動(dòng)設(shè)備上的微處理器。GPU不僅促進(jìn)了圖像處理等應(yīng)用領(lǐng)域的發(fā)展,而且為圖形學(xué)以外的其他領(lǐng)域提供了良好的運(yùn)行平臺(tái)。因此,從傳統(tǒng)問題入手,選擇典型算法,使其借助GPU平臺(tái)得以實(shí)現(xiàn)并行加速,就顯得十分重要了。論文主要選擇了快速排序法(Quicksort)、R-Tree索引和K-近鄰連接算法(K-Nearest-Neighbor Join,KNNJ)。快速排序法在分區(qū)過程中將消耗大量時(shí)間,對其的大多改進(jìn)并沒有從本質(zhì)上改變分區(qū)速度慢的問題。R-Tree是空間數(shù)據(jù)處理中一種非常常用的索引結(jié)構(gòu),對于算法加速起著至關(guān)重要的作用。KNNJ算法是空間數(shù)據(jù)查詢中最常見的算法之一,一般采用暴力搜索,計(jì)算量十分龐大。因此,針對GPU的高性能計(jì)算架構(gòu),論文對快速排序法、R-Tree索引和KNNJ算法進(jìn)行了改進(jìn)和優(yōu)化。具體研究工作主要集中在以下三個(gè)方面:1.通過對傳統(tǒng)串行快速排序法的分析比較,選擇隨機(jī)數(shù)產(chǎn)生器生成樞軸元素,結(jié)合快速排序分區(qū)可并行性的特點(diǎn),對快速排序法分初始化、預(yù)處理、重定位、最終排序四個(gè)步驟進(jìn)行處理,實(shí)現(xiàn)了基于GPU的快速排序算法的并行改進(jìn)。2.利用無依賴并行和串行同步計(jì)算的形式化定義了GPU并行編程模型,針對此并行抽象模型,提出了R-Tree索引的并行快速構(gòu)建。在索引構(gòu)建過程中,引入最小外包框的概念,利用遞歸網(wǎng)格排序算法以快速確立空間劃分函數(shù),使得索引構(gòu)建符合無依賴并行和串行同步計(jì)算抽象。3.針對K-近鄰連接本身存在的可并行性特點(diǎn),論文基于GPU對其實(shí)現(xiàn)并行,共分為四個(gè)部分。第一部分是建立索引機(jī)制;第二部分是歐氏距離的并行計(jì)算;第三部分是對求得距離的并行排序;最后引入KNN擴(kuò)展框的概念,限定子樹索引中所有對象KNNJ查詢范圍,獲得最近的K個(gè)對象。論文將這種基于GPU平臺(tái)的查詢算法稱為G-rKNNJ(R-Tree based KNNJ)算法。通過以上算法的并行改進(jìn),實(shí)驗(yàn)結(jié)果表明,在不斷更改數(shù)據(jù)參數(shù)的情況下,GPU下的算法并行具有一定的可行性和高效性。
【關(guān)鍵詞】：GPU 快速排序 R-Tree索引 最近鄰搜索 并行計(jì)算
【學(xué)位授予單位】：南京航空航天大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP391.41
【目錄】：

• 摘要4-5
• ABSTRACT5-10
• 注釋表10-11
• 縮略詞11-12
• 第一章 緒論12-17
• 1.1 課題研究背景及意義12-13
• 1.1.1 研究背景12
• 1.1.2 研究意義12-13
• 1.2 國內(nèi)外研究現(xiàn)狀13-15
• 1.3 主要研究內(nèi)容15-16
• 1.4 論文組織結(jié)構(gòu)16-17
• 第二章 相關(guān)理論基礎(chǔ)17-29
• 2.1 GPU概述17-22
• 2.1.1 GPU體系架構(gòu)17-19
• 2.1.2 與多核CPU的區(qū)別19-20
• 2.1.3 與超級計(jì)算機(jī)的區(qū)別20-22
• 2.1.4 與分布式集群的區(qū)別22
• 2.2 CUDA簡介22-26
• 2.2.1 Kernel函數(shù)23-24
• 2.2.2 線程結(jié)構(gòu)24-25
• 2.2.3 CUDA存儲(chǔ)模型25-26
• 2.3 NVIDIA Nsight簡介26-28
• 2.4 本章小結(jié)28-29
• 第三章 基于GPU的快速排序法的并行實(shí)現(xiàn)29-37
• 3.1 快速排序法簡介29-30
• 3.2 串行快速排序及其樞軸元素的選擇30-31
• 3.2.1 串行快速排序法30-31
• 3.2.2 樞軸元素選取31
• 3.3 并行快速排序31-36
• 3.3.1 傳統(tǒng)并行快速排序31-32
• 3.3.2 基于GPU的并行快速排序32-36
• 3.4 本章小結(jié)36-37
• 第四章 GPU下基于R-Tree索引的K-近鄰連接算法37-57
• 4.1 K-近鄰連接算法簡介37-38
• 4.2 KNNJ算法主要流程38-39
• 4.3 基于GPU的R-Tree索引的建立39-49
• 4.3.1 R-Tree節(jié)點(diǎn)的距離定義40-41
• 4.3.2 并行計(jì)算模型41
• 4.3.3 GPU下R-Tree索引的快速構(gòu)建41-49
• 4.4 基于GPU的并行KNNJ查詢49-56
• 4.4.1 KNNJ并行求距離49-50
• 4.4.2 KNNJ并行距離排序50
• 4.4.3 基于R-Tree索引的KNNJ查詢50-52
• 4.4.4 基于擴(kuò)展框的剪枝策略52-55
• 4.4.5 GPU下基于R-Tree索引的KNNJ查詢55-56
• 4.5 本章小結(jié)56-57
• 第五章 實(shí)驗(yàn)仿真及結(jié)果分析57-66
• 5.1 實(shí)驗(yàn)環(huán)境配置57-59
• 5.1.1 實(shí)驗(yàn)平臺(tái)的搭建57-58
• 5.1.2 實(shí)驗(yàn)數(shù)據(jù)集介紹58-59
• 5.2 實(shí)驗(yàn)對比方案59
• 5.3 實(shí)驗(yàn)結(jié)果分析59-65
• 5.3.1 數(shù)據(jù)規(guī)模對快速排序法的影響60
• 5.3.2 節(jié)點(diǎn)數(shù)對索引建立的影響60-61
• 5.3.3 數(shù)據(jù)規(guī)模對索引建立的影響61-62
• 5.3.4 K值大小對KNNJ查詢的影響62-63
• 5.3.5 索引節(jié)點(diǎn)數(shù)對KNNJ查詢的影響63-64
• 5.3.6 數(shù)據(jù)規(guī)模對KNNJ查詢的影響64-65
• 5.4 本章小結(jié)65-66
• 第六章 總結(jié)與展望66-67
• 6.1 本文主要工作總結(jié)66
• 6.2 下一階段工作展望66-67
• 參考文獻(xiàn)67-70
• 致謝70-71
• 在學(xué)期間的研究成果及發(fā)表的學(xué)術(shù)論文71

，

本文編號(hào)：1031333