本文關(guān)鍵詞： 拓?fù)湓靺^(qū) 空間索引 緩沖區(qū)分析　出處：《中國(guó)地質(zhì)大學(xué)》2013年碩士論文　論文類(lèi)型：學(xué)位論文

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

【參考文獻(xiàn)】

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

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

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

3 王多強(qiáng),劉金根,李慶華,睢海燕;并行查詢(xún)中的索引并行化技術(shù)[J];華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年01期

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

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

6 何軍;王飆;;多核處理器的結(jié)構(gòu)設(shè)計(jì)研究[J];計(jì)算機(jī)工程;2007年16期

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

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

9 毋河海;關(guān)于GIS緩沖區(qū)的建立問(wèn)題[J];武漢測(cè)繪科技大學(xué)學(xué)報(bào);1997年04期

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

，

本文編號(hào)：1479413