【摘要】：矢量數(shù)據(jù)作為GIS的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)之一，與柵格數(shù)據(jù)相比具有存儲量小、圖形顯示精度高、有利于拓?fù)潢P(guān)系分析等優(yōu)點。但由于其數(shù)據(jù)結(jié)構(gòu)較為復(fù)雜，導(dǎo)致面向矢量數(shù)據(jù)并行化存取與處理的相關(guān)操作方法研究較為困難。特別是矢量數(shù)據(jù)的無結(jié)構(gòu)化特點，與GPU利用數(shù)組結(jié)構(gòu)存儲數(shù)據(jù)之間存在較大差異，難以充分發(fā)揮GPU眾核高度并行執(zhí)行的優(yōu)勢。因此，本文將系統(tǒng)地研究基于GPU的矢量數(shù)據(jù)存取操作方法、程序設(shè)計架構(gòu)、數(shù)據(jù)結(jié)構(gòu)、高效并行空間分析算法以及空間索引等內(nèi)容。 為適應(yīng)GPU不能利用內(nèi)核程序動態(tài)分配存儲空間，只能依賴有限的總線帶寬從CPU端發(fā)送和接收數(shù)據(jù)的編程特點，本文以CSV格式文件為例，，設(shè)計與實現(xiàn)了面向矢量數(shù)據(jù)的并行計算框架。主要思想是首先在CPU端對空間數(shù)據(jù)進(jìn)行預(yù)處理操作，然后根據(jù)空間對象的幾何坐標(biāo)大小分配GPU端存儲空間，最后以空間對象為單位逐個拷貝至GPU端。 本文采用分層設(shè)計思想構(gòu)建基于GPU的空間分析方法，共包含存儲、空間算子、存取策略、空間分析操作四部分。該方法具有較好的可擴展性，當(dāng)某一層發(fā)生變化時，其它層僅需較小的修改即可實現(xiàn)，從而降低了各功能模塊間耦合度。 本文針對空間分析中的空間數(shù)據(jù)排序、空間關(guān)系分析等常見技術(shù)，在分析其并行性特點的基礎(chǔ)上，結(jié)合面向GPU流處理器進(jìn)行空間數(shù)據(jù)并行處理問題，以典型的疊加分析、靜態(tài)R-樹空間索引算法為例，提出了新的數(shù)據(jù)結(jié)構(gòu)以及相關(guān)算法。并采用最大化并行執(zhí)行、優(yōu)化存儲器使用等策略提高空間數(shù)據(jù)分析性能，力圖為其它并行空間分析方法的優(yōu)化提供借鑒。實驗結(jié)果表明，與傳統(tǒng)的基于CPU的算法相比，在一般的計算環(huán)境下基于GPU的算法能夠獲得較好的加速比。
[Abstract]:Vector data is one of the basic data structures of GIS. Compared with raster data, vector data has the advantages of less storage, higher precision of graphic display and more favorable to the analysis of topological relations. However, due to the complexity of its data structure, it is difficult to study the related operation methods for parallel access and processing of vector data. Especially, the unstructured feature of vector data is different from that of GPU using array structure to store data, so it is difficult to give full play to the advantage of high parallel execution of GPU multi-kernel. Therefore, this paper will systematically study the vector data access operation method based on GPU, programming architecture, data structure, efficient parallel spatial analysis algorithm and spatial index, and so on. In order to adapt to the programming characteristics that GPU can not dynamically allocate storage space by using kernel program, it can only rely on limited bus bandwidth to send and receive data from CPU. This paper takes the CSV format file as an example. A parallel computing framework for vector data is designed and implemented. The main idea is to preprocess the spatial data at the CPU end, then allocate the storage space of the GPU terminal according to the geometric coordinate size of the spatial object, and copy to the GPU terminal one by one with the spatial object as the unit. In this paper, a spatial analysis method based on GPU is constructed with the idea of hierarchical design. It includes four parts: storage, spatial operator, access strategy and spatial analysis operation. The method has good scalability. When one layer changes, other layers can be implemented only with small modifications, thus reducing the degree of coupling among the functional modules. In this paper, based on the analysis of the parallelism of spatial data sequencing and spatial relation analysis, the parallel processing problem of spatial data for GPU stream processor is analyzed, and the typical superposition analysis is used. Static R- tree spatial indexing algorithm is used as an example, and a new data structure and related algorithms are proposed. Strategies such as maximizing parallel execution and optimizing memory usage are adopted to improve the performance of spatial data analysis and to provide reference for the optimization of other parallel spatial analysis methods. The experimental results show that compared with the traditional algorithm based on CPU, the algorithm based on GPU can get a better speedup in general computing environment.
【學(xué)位授予單位】：中國科學(xué)院研究生院（東北地理與農(nóng)業(yè)生態(tài)研究所）
【學(xué)位級別】：博士
【學(xué)位授予年份】：2014
【分類號】：TP391.41;P208

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 梁浩;吳敏君;;兩類典型GIS空間索引技術(shù)的分析與評價[J];安陽工學(xué)院學(xué)報;2006年02期

2 孔云峰;秦耀辰;喬家君;秦奮;;高校地理學(xué)科空間分析課程設(shè)置研究[J];測繪科學(xué);2007年03期

3 史文中,郭薇,彭奕彰;一種面向地理信息系統(tǒng)的空間索引方法[J];測繪學(xué)報;2001年02期

4 閻超德,趙學(xué)勝;GIS空間索引方法述評[J];地理與地理信息科學(xué);2004年04期

5 張傳明;潘懋;;基于格網(wǎng)索引的GIS矢量數(shù)據(jù)拓?fù)渲亟ㄑ芯縖J];地理與地理信息科學(xué);2006年04期

6 謝忠;葉梓;吳亮;;簡單要素模型下多邊形疊置分析算法[J];地理與地理信息科學(xué);2007年03期

7 趙園春;李成名;趙春宇;;基于R樹的分布式并行空間索引機制研究[J];地理與地理信息科學(xué);2007年06期

8 王結(jié)臣;王豹;胡瑋;張輝;;并行空間分析算法研究進(jìn)展及評述[J];地理與地理信息科學(xué);2011年06期

9 陳彥光;羅靜;;地學(xué)計算的研究進(jìn)展與問題分析[J];地理科學(xué)進(jìn)展;2009年04期

10 趙斯思;周成虎;;GPU加速的多邊形疊加分析[J];地理科學(xué)進(jìn)展;2013年01期

相關(guān)博士學(xué)位論文 前10條

1 張澤寶;空間數(shù)據(jù)庫的索引技術(shù)研究[D];哈爾濱工程大學(xué);2009年

2 劉潤濤;基于序的空間數(shù)據(jù)索引及查詢算法研究[D];哈爾濱理工大學(xué);2009年

3 龍柏;并行計算平臺上的數(shù)據(jù)索引技術(shù)研究[D];中國科學(xué)技術(shù)大學(xué);2011年

4 馬安國;高效能GPGPU體系結(jié)構(gòu)關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2011年

5 唐滔;面向CPU-GPU異構(gòu)并行系統(tǒng)的編程模型與編譯優(yōu)化關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2012年

6 黃健美;高維數(shù)據(jù)索引及其查詢處理技術(shù)研究[D];東北大學(xué);2009年

7 謝炯;無縫時空的多域集成時空數(shù)據(jù)模型研究[D];浙江大學(xué);2005年

8 林偉華;多重近似空間索引及其相關(guān)檢索技術(shù)研究[D];華中科技大學(xué);2009年

9 白洪濤;基于GPU的高性能并行算法研究[D];吉林大學(xué);2010年

10 鄧亞丹;面向共享Cache多核處理器的數(shù)據(jù)庫查詢執(zhí)行優(yōu)化技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2009年

本文編號：2245891