本文關鍵詞： 拓撲造區(qū) 空間索引 緩沖區(qū)分析　出處：《中國地質大學》2013年碩士論文　論文類型：學位論文

【摘要】：隨著GPS等技術的發(fā)展,數(shù)據(jù)量呈現(xiàn)冪指數(shù)的增長,大規(guī)模的計算應用推動了并行計算機的發(fā)展。但是目前并行計算機仍然主要是在實驗室中,只有很少的應用在實際的工程當中,尤其是在GIS中,并行計算機更是沒有凸顯出它的多核處理器的并行計算優(yōu)勢,因此,充分利用多核處理器計算機的計算能力,加速GIS軟件的執(zhí)行速度,成為并行GIS中亟須解決的一個關鍵問題。 未來,GIS的并行化將是GIS發(fā)展的趨勢,在并行G1S中,提高并行計算機的實際應用效率,縮小計算機實際的應用性能與機器峰值性能之間的差距,本文以多核處理器為目標平臺,研究基于數(shù)據(jù)并行的程序的關鍵技術,主要研究工作為基于數(shù)據(jù)并行的理論基礎,對空間分析中最常用的空間索引,拓撲造區(qū)以及緩沖區(qū)分析進行研究,實現(xiàn)其并行化,以提高并行應用程序的實際性能。本文針對數(shù)據(jù)并行模型和空間分析技術研究,可以充分發(fā)揮并行計算機的優(yōu)勢,有效的提高空間分析的性能,具有重要的學術和應用價值。具體來說,本文的主要研究內容概括如下： (1)研究空間索引的并行化。本文研究空間分析中最常用的空間索引R樹索引,并對其進行并行化,在多核系統(tǒng)上,實現(xiàn)基于OpenMP的R樹并行。 R樹是一個類似于B樹的平衡樹,其最常用的構建方法是逐結點插入法。本文提出了對于R樹進行批量插入算法,并且對其進行并行化,以充分利用現(xiàn)在計算機硬件相比原來單核計算機的優(yōu)勢。從而提高算法的運行效率。對于查詢和刪除操作,同樣適用并行操作。本文對R樹索引測試重點是在多核處理器的環(huán)境下并行R樹與串行R樹的構建和插入進行性能比較,采用的mapgis格式的數(shù)據(jù),得出在數(shù)據(jù)量較小時,插入和批量構建算法都十分迅速,但是在數(shù)據(jù)量比較大時,批量建立已經(jīng)顯示出優(yōu)勢,在實驗的數(shù)據(jù)中,批量插入算法和傳統(tǒng)的插入算法效率已經(jīng)相差到10倍,在并行插入和串行插入時,同樣是隨著數(shù)據(jù)量的增大,并行插入的優(yōu)勢已經(jīng)越來越明顯,在實驗數(shù)據(jù)中差距離9倍。在多核處理器環(huán)境下,并行R樹的建立對于數(shù)據(jù)量較大時具有比串行R樹的建立具有更大的優(yōu)勢,能夠提高空間分析的性能。 (2)研究拓撲造區(qū)的并行化。本文研究空間分析中線拓撲造區(qū)的常用算法,然后根據(jù)計算機圖形學中翼邊結構的特點,提出基于數(shù)據(jù)并行化的拓撲造區(qū)算法,并對其進行實驗,進行串行拓撲造區(qū)和并行拓撲造區(qū)進行分析。 矢量數(shù)據(jù)拓撲造區(qū)是空間分析中一個非�；A且重要的操作,即矢量數(shù)據(jù)拓撲造區(qū)是對一平面內的一個或者多個線對象所組成的集合進行處理,形成閉合的多邊形的過程。在實際應用中,往往會對一個線文件或者對一個線文件中的部分線來進行拓撲造區(qū)。本文該部分首先介紹拓撲造區(qū)的準備工作,然后再研究矢量線數(shù)據(jù)拓撲造區(qū)的串行化以及在多核處理器環(huán)境下的并行化,來提高拓撲造區(qū)的加I速比。本文對利用PMR四叉樹對并行線拓撲造區(qū)進行研究,根據(jù)多核處理器的環(huán)境特性,實現(xiàn)拓撲造區(qū)的并行化算法,提高多核處理器共享存儲系統(tǒng)的性能。實驗表明在多核環(huán)境下,在數(shù)據(jù)量較小時并行并沒有顯示出優(yōu)勢,但是在數(shù)據(jù)量比較大時,并行算法的優(yōu)勢會變得越來越明顯；線程數(shù)設置也不是越多越好,選擇過于高于核數(shù)的線程數(shù),由于各個線程之間的通信,往往會降低效率,因此線程數(shù)設置為核數(shù)的2倍左右最為適宜。 (3)研究緩沖區(qū)分析的并行化。本文研究空間分析中矢量折線進行不等半徑的緩沖區(qū)分析,并提出基于數(shù)據(jù)并行化的不等半徑的緩沖區(qū)分析,然后對其進行實驗,進行矢量線數(shù)據(jù)不等半徑緩沖區(qū)分析的并行算法和串行算法的對比分析。 研究矢量數(shù)據(jù)不等半徑buffer分析的串行化,并研究其在多核處理器環(huán)境下的并行化,來提高不等半徑buffer分析的速度。采用基于平面圖模型的來串行線矢量要素的不等半徑buffer分析,并利用visual Studio環(huán)境下的C++實現(xiàn),接著根據(jù)多核處理器的環(huán)境特性,實現(xiàn)不等半徑buffer分析的并行化算法,提高多核處理器共享存儲系統(tǒng)的性能。最后通過實驗來驗證矢量buffer分析和光柵法buffer分析的精確性,檢驗并行矢量數(shù)據(jù)不等半徑buffer的性能,比較串行和并行兩個版本的計算速度。這與數(shù)據(jù)量和劃分區(qū)域的情況有關系,如果數(shù)據(jù)量很小,對其進行分割和線程之間的消息傳輸所占用的時間增加,如果大部分區(qū)域需要重復計算,那么其計算時間不但不會減少,而且占用了更多的空間。而相反,如果數(shù)據(jù)量比較大,且分割時劃分比較適當,重復計算的要素不是很多,那么效率就會相對較高。
[Abstract]:......
【學位授予單位】：中國地質大學
【學位級別】：碩士
【學位授予年份】：2013
【分類號】：TP338.6;P208

【參考文獻】

相關期刊論文 前10條

1 趙園春;李成名;趙春宇;;并行R樹空間索引中葉節(jié)點大小的確定方法研究[J];測繪科學;2008年04期

2 周艷;朱慶;張葉廷;;基于Hilbert曲線層次分解的空間數(shù)據(jù)劃分方法[J];地理與地理信息科學;2007年04期

3 王多強,劉金根,李慶華,睢海燕;并行查詢中的索引并行化技術[J];華中科技大學學報(自然科學版);2003年01期

4 王結臣;芮一康;李永全;;一種基于矢量邊界追蹤的緩沖區(qū)生成方法[J];計算機工程與應用;2007年33期

5 賈婷;魏祖寬;唐曙光;金在弘;;一種面向并行空間查詢的數(shù)據(jù)劃分方法[J];計算機科學;2010年08期

6 何軍;王飆;;多核處理器的結構設計研究[J];計算機工程;2007年16期

7 張明波,陸鋒,申排偉,程昌秀;R樹家族的演變和發(fā)展[J];計算機學報;2005年03期

8 吳艷娜,湯易,施寅;GIS中基于柵格轉換的緩沖區(qū)生成算法[J];鐵路計算機應用;2002年04期

9 毋河海;關于GIS緩沖區(qū)的建立問題[J];武漢測繪科技大學學報;1997年04期

10 鄭燕玲;;空間數(shù)據(jù)庫的分塊多級索引機制的研究[J];微計算機信息;2009年21期

，

本文編號：1479413