基于數(shù)據(jù)分治與雙層索引的并行點(diǎn)面疊加分析方法研究

周 玉 科,周 成 虎，馬 廷，高 錫 章，范 俊 甫，許 濤，季 民

(1.中國(guó)科學(xué)院地理科學(xué)與資源研究所，資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100101；2.山東理工大學(xué)建筑工程學(xué)院，山東 淄博 255049；3.山東科技大學(xué)測(cè)繪工程學(xué)院，山東 青島 266510)

?

基于數(shù)據(jù)分治與雙層索引的并行點(diǎn)面疊加分析方法研究

周 玉 科1,周 成 虎1，馬 廷1，高 錫 章1，范 俊 甫2，許 濤1，季 民3

(1.中國(guó)科學(xué)院地理科學(xué)與資源研究所，資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 100101；2.山東理工大學(xué)建筑工程學(xué)院，山東 淄博 255049；3.山東科技大學(xué)測(cè)繪工程學(xué)院，山東 青島 266510)

地圖疊加分析是一種計(jì)算密集型算法，并行化計(jì)算是加快算法執(zhí)行速度的一種有效方法。該文研究分布式環(huán)境下的點(diǎn)面圖層并行化疊加分析方法與實(shí)現(xiàn)。首先根據(jù)點(diǎn)面疊加的特點(diǎn)設(shè)置并行數(shù)據(jù)分解的方式，基于分治法分解空間數(shù)據(jù)，在并行系統(tǒng)下將地理要素分而治之。然后引入雙層索引的并行疊加機(jī)制，一是對(duì)面圖層根據(jù)Hilbert空間索引的排序方式分發(fā)數(shù)據(jù)，二是對(duì)點(diǎn)圖層建立四叉樹索引，對(duì)每一個(gè)進(jìn)行相交運(yùn)算的多邊形進(jìn)行快速過濾和求交。最后在Linux集群系統(tǒng)下實(shí)現(xiàn)該并行算法，其一利用MPI分布式計(jì)算環(huán)境實(shí)現(xiàn)在整體計(jì)算框架下的消息通訊模式的并行，其二在每個(gè)子節(jié)點(diǎn)中實(shí)現(xiàn)基于多核OpenMP工具的本地并行化。結(jié)果表明，利用雙層空間索引分治的方法可實(shí)現(xiàn)并行數(shù)據(jù)分塊，各子節(jié)點(diǎn)實(shí)現(xiàn)獨(dú)立計(jì)算，減少并行系統(tǒng)中的I/O沖突，并行加速比明顯。該方法對(duì)矢量地圖運(yùn)算的并行化進(jìn)行了有益的嘗試，為大數(shù)據(jù)時(shí)代的空間數(shù)據(jù)分析提供一種有效的途徑。

地圖疊加分析；并行計(jì)算；空間索引；MPI；OpenMP

0 引言

地圖疊加分析(Map Overlay)是GIS空間分析中最基礎(chǔ)、使用最頻繁的一種操作[1]，指同一地域范圍的兩個(gè)或多個(gè)地圖圖層在同樣空間參考系下進(jìn)行疊加，獲取具有新屬性的空間區(qū)域并最終生成一個(gè)新的圖層，圖層要素屬性由疊加運(yùn)算符決定，其本質(zhì)過程是一系列計(jì)算幾何布爾操作和屬性傳遞過程的集合。圖層疊加中幾何對(duì)象之間的操作已被證明為時(shí)間復(fù)雜度最少為O(nlogn)的操作[2]，因此涉及全幅地圖圖層的疊加分析屬于計(jì)算密集型操作。點(diǎn)與多邊形圖層的疊加分析是其中基本的操作類型之一，其實(shí)質(zhì)是點(diǎn)包含問題(單點(diǎn)或復(fù)雜對(duì)象組成點(diǎn))。

隨著數(shù)據(jù)規(guī)模的日益膨脹、實(shí)時(shí)性應(yīng)用的增加，對(duì)地圖疊加分析功能在計(jì)算效率、性能、處理能力等方面的要求也越來(lái)越高。并行計(jì)算技術(shù)從20世紀(jì)70年代隨著計(jì)算機(jī)體系架構(gòu)的進(jìn)步和成熟發(fā)展起來(lái)，由于并行技術(shù)發(fā)展時(shí)間不長(zhǎng)，因此GIS的核心空間分析功能的并行化仍然處在迅速發(fā)展時(shí)期[3,4]。近年來(lái)，并行計(jì)算機(jī)的強(qiáng)大硬件加速特性和新的并發(fā)設(shè)計(jì)思想為解決復(fù)雜度日益增加的地學(xué)問題和海量級(jí)別的數(shù)據(jù)處理問題提供了新的解決方案，同時(shí)也為地圖疊加分析提供了理論和實(shí)踐基礎(chǔ)。點(diǎn)面疊加分析是地圖疊加分析中的一種基本操作，輸出結(jié)果判斷點(diǎn)被多邊形包含關(guān)系[5,6]。已有學(xué)者利用各種并行計(jì)算工具對(duì)地圖并行疊加分析進(jìn)行探索，如利用GPU加速[7]和集群并行方法[8,9]。本文利用并行計(jì)算的基礎(chǔ)理論方法，重點(diǎn)研究在并行化地圖疊加分析中的靜態(tài)負(fù)載均衡方法，以數(shù)據(jù)并行為主線，利用Hilbert空間索引分解地理數(shù)據(jù)，達(dá)到各任務(wù)節(jié)點(diǎn)計(jì)算量基本平衡，各個(gè)節(jié)點(diǎn)再次進(jìn)行細(xì)粒度并行判斷包含關(guān)系。

1 雙層索引方法與分治并行策略

1.1 并行疊加特征預(yù)分析

本文針對(duì)點(diǎn)圖層與面圖層的疊加分析，運(yùn)算對(duì)象之間屬于多對(duì)多的關(guān)系，因此研究對(duì)象的粒度應(yīng)該從點(diǎn)與邊的關(guān)系上升到點(diǎn)集合與多邊形集合之間的關(guān)系、點(diǎn)集內(nèi)部的空間分布特征關(guān)系和多邊形集合之間的空間近鄰關(guān)系。傳統(tǒng)的并行算法設(shè)計(jì)考慮每個(gè)原子級(jí)別的操作并保證每個(gè)節(jié)點(diǎn)處理時(shí)間大致相同。如果按照傳統(tǒng)設(shè)計(jì)方法將點(diǎn)和多邊形相交降低維度將增加數(shù)據(jù)組織和計(jì)算的復(fù)雜度。假設(shè)點(diǎn)和多邊形數(shù)量均為n，采用直接求交方法的時(shí)間復(fù)雜度為O(n2)；如果將多邊形以邊為粒度進(jìn)行分解，假設(shè)每個(gè)多邊形最少有m條邊，則計(jì)算的時(shí)間復(fù)雜度會(huì)上升到O(mn2)。為更好地提升圖層直接疊加效率，仍然從減少不必要耗時(shí)操作的原則出發(fā)，使用混合雙層索引分解的方法對(duì)點(diǎn)面圖層疊加進(jìn)行預(yù)處理，以數(shù)據(jù)分治的方式實(shí)現(xiàn)并行。

圖層粒度級(jí)別的多邊形疊加分析更適合以面向?qū)ο蟮男问浇M織，根據(jù)并行計(jì)算的原理并行粒度越大獲得的加速比越大。從點(diǎn)圖層考察，點(diǎn)數(shù)據(jù)分布具有不規(guī)則性和不平衡性，因此必須加以約束減少疊加分析過程中不必要的包含測(cè)試。從GIS空間查詢分析的基本過程考察(圖1)，疊加分析算法可以獲得并行加速的階段主要在數(shù)據(jù)輸入輸出、過濾階段和圖元對(duì)象的精確幾何計(jì)算過程。

圖1 單對(duì)象關(guān)系和圖層多對(duì)象關(guān)系

Fig.1 Single object relationship and layer multi-object relationship

幾何圖形過濾階段的加速是點(diǎn)面疊加分析的關(guān)鍵步驟[10]，圖層級(jí)別的點(diǎn)與多邊形疊加分析并行化的基礎(chǔ)仍然是數(shù)據(jù)域分解和并發(fā)調(diào)度。本文的快速過濾是基于幾何圖形MBR的空間索引機(jī)制，MBR是包圍圖元且平行于X、Y軸的最小外接矩形在索引結(jié)構(gòu)中用來(lái)代表真實(shí)幾何元素。首先需要考慮疊加圖層的特性，點(diǎn)圖層的元素?zé)o外包矩形或者以計(jì)算機(jī)默認(rèn)容差為寬度(長(zhǎng)度)設(shè)定的小方格，在空間查詢中小方格的相交計(jì)算明顯會(huì)增加計(jì)算量。因此對(duì)于點(diǎn)圖層采用四叉樹索引的機(jī)制，其生成規(guī)則為當(dāng)每個(gè)單元格只有一個(gè)點(diǎn)時(shí)不再繼續(xù)遞歸劃分。因?yàn)閱卧袷仟?dú)占的，所以點(diǎn)圖層的索引沒有冗余節(jié)點(diǎn)。

按照二叉樹表示二維點(diǎn)數(shù)據(jù)的方法，該研究在此基礎(chǔ)上進(jìn)行修改對(duì)點(diǎn)圖層構(gòu)建四叉樹索引。點(diǎn)四叉樹與四叉樹具有同樣的特點(diǎn)，但是當(dāng)對(duì)于次分區(qū)的中心總是在一個(gè)點(diǎn)時(shí)，點(diǎn)四叉樹被視為一個(gè)真樹(true tree)，樹的形態(tài)根據(jù)排序后的數(shù)據(jù)而定。對(duì)分布較規(guī)律的二維點(diǎn)的查詢具有較高的效率，通常的運(yùn)行時(shí)間復(fù)雜度在O(logn)之內(nèi)，基于點(diǎn)四叉樹構(gòu)造空間索引的時(shí)間復(fù)雜度為O((n/2)logn)。

1.2 雙層索引的多級(jí)并行方法

在并行點(diǎn)面疊加分析中設(shè)置主動(dòng)圖層和被動(dòng)圖層的概念。主動(dòng)圖層作為切割對(duì)象，被動(dòng)圖層作為被切割對(duì)象。因?yàn)榈貓D系統(tǒng)是按照層次結(jié)構(gòu)進(jìn)行組織，有學(xué)者[11]已證明以點(diǎn)為基礎(chǔ)要素的地圖圖形系統(tǒng)和以地圖符號(hào)為基礎(chǔ)單元的地圖符號(hào)系統(tǒng)屬于布爾代數(shù)系，因此也說(shuō)明地圖圖層系統(tǒng)也可以應(yīng)用于計(jì)算機(jī)處理器內(nèi)的邏輯運(yùn)算。雖然邏輯上兩個(gè)圖層疊加都是相互作用的布爾操作，容易直觀地認(rèn)為不存在疊加的順序問題，但是既然涉及電子計(jì)算機(jī)的運(yùn)算邏輯，其運(yùn)算效率便與順序存在一定的關(guān)系。例如，最樸素的點(diǎn)面圖層疊加分析方法是對(duì)兩個(gè)圖層內(nèi)的要素建立兩層循環(huán)進(jìn)行直接求交。從計(jì)算機(jī)內(nèi)存使用和程序設(shè)計(jì)的策略衡量，對(duì)于嵌套的多層循環(huán)，外部循環(huán)量需要盡量大于內(nèi)部循環(huán)量。因此在并行點(diǎn)面疊加的數(shù)據(jù)分解中以多邊形圖層作為主動(dòng)圖層進(jìn)行包含查詢。

從空間分布特點(diǎn)考慮，點(diǎn)數(shù)據(jù)圖層具有聚集特性，適宜采用四叉樹索引的方式。另外由于多邊形數(shù)據(jù)的復(fù)雜性要高于點(diǎn)數(shù)據(jù)的復(fù)雜性，其空間分布不規(guī)則，根據(jù)空間數(shù)據(jù)域分解的方法，多邊形圖層的并行分解也需要考慮空間聚類特性，以保證各節(jié)點(diǎn)計(jì)算的負(fù)載均衡，因此對(duì)多邊形圖層建立基于Hilbert曲線排序的索引結(jié)構(gòu)。首先使用MPI偽代碼的形式對(duì)并行點(diǎn)面疊加進(jìn)行描述(表1)。

表1 點(diǎn)面疊加的MPI偽代碼

Table 1 MPI pseudo code for point-polygon overlay

1．initializeMPI2．if(masterprocess){3． buildHilbertsortindexforpolygonlayer4． broadcasttheHilbertinternalinformationtoslavenode5．}else{6． mapthenumberofpointsinfeaturelayertoanarray7． getthenumberoftotalpoints8． buildquadtreeforpoints9． calculatetheindexofpoints10． receivethespecificHilbertinternalinformationaboutpolygon11． getpolygonbetweenHilbertinternalfromlocalspatialdatabase12． Loop{13． calculatepolygoncontainpoint}14． mpi＿sendresultpointtomasternode15． }16．finalizeMPI

圖層級(jí)別點(diǎn)面并行疊加分析的具體步驟如下：

(1)建立索引。首先數(shù)據(jù)分配采用全冗余的機(jī)制，主節(jié)點(diǎn)和子節(jié)點(diǎn)存儲(chǔ)相同的矢量數(shù)據(jù)。主節(jié)點(diǎn)主要負(fù)責(zé)數(shù)據(jù)信息的一致性維護(hù)、中間結(jié)果回收。主節(jié)點(diǎn)對(duì)面圖層分別建立基于內(nèi)存的Hilbert空間索引，各子節(jié)點(diǎn)對(duì)所存儲(chǔ)的點(diǎn)數(shù)據(jù)建立基于內(nèi)存的四叉樹索引。從索引結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)位置可將其分為內(nèi)存式和外存式兩種[12]，訪問計(jì)算機(jī)的內(nèi)、外存儲(chǔ)器一次所耗費(fèi)的時(shí)間分別為30～40 ns和8～10 ms，因此研究采用高效的內(nèi)存索引。在點(diǎn)面圖層的并行疊加算法中空間索引有兩個(gè)重要作用：一是空間數(shù)據(jù)域分解的需要，達(dá)到數(shù)據(jù)的分治和計(jì)算的負(fù)載均衡；二是幾何對(duì)象進(jìn)行相交判斷時(shí)快速確定相交粗集，減少不必要的真實(shí)求交操作。兩種方式中索引的功能都是空間查詢，并且使用次數(shù)較少、周期較短，因此采用內(nèi)存索引的方式能夠達(dá)到快速高效的目的。

(2)多邊形分配。數(shù)據(jù)處理階段主節(jié)點(diǎn)對(duì)運(yùn)算數(shù)據(jù)進(jìn)行內(nèi)存式空間索引，以多邊形圖層為主動(dòng)查詢圖層，各節(jié)點(diǎn)進(jìn)行數(shù)據(jù)本地化。有兩種策略實(shí)現(xiàn)數(shù)據(jù)本地化，一種是分析前在每個(gè)節(jié)點(diǎn)預(yù)部署一份相同的數(shù)據(jù)，另一種是通過掛載共享文件系統(tǒng)實(shí)現(xiàn)數(shù)據(jù)協(xié)同訪問。主節(jié)點(diǎn)將多邊形圖層按照Hilbert編碼排列順序，并將劃分好的序列片段發(fā)送到各子節(jié)點(diǎn)。本研究采用Hilbert曲線既可以保持多邊形的空間鄰近性，又能夠避免多邊形的分配存在冗余情況(圖2)。在不考慮多邊形鄰近性的情況下，使用多邊形要素FID劃分同樣能夠達(dá)到分治的效果，但許多地圖被編輯后(刪除、插入)，F(xiàn)ID會(huì)出現(xiàn)不連續(xù)現(xiàn)象，無(wú)法保證數(shù)據(jù)分發(fā)的成功率，所以方法選擇空間和數(shù)列上均連續(xù)的Hilbert曲線編碼進(jìn)行多邊形分配。排序劃分好的數(shù)組采用MPI_Send命令發(fā)送到指定子節(jié)點(diǎn)，各子節(jié)點(diǎn)接受后作為數(shù)據(jù)讀取時(shí)的過濾條件只抓取部分?jǐn)?shù)據(jù)。

圖2 多邊形索引分發(fā)方法

Fig.2 Index and distribution method of polygon

(3)索引層快速過濾。在主節(jié)點(diǎn)將多邊形的索引標(biāo)識(shí)平均分配到各子節(jié)點(diǎn)以后，子節(jié)點(diǎn)開始實(shí)際的疊加運(yùn)算。首先各個(gè)節(jié)點(diǎn)加載本地?cái)?shù)據(jù)，點(diǎn)圖層作為被動(dòng)圖層需全部加載，同時(shí)需對(duì)其建立基于內(nèi)存的四叉樹索引(圖3)。多邊形圖層按照主節(jié)點(diǎn)分配的標(biāo)識(shí)提取圖層中的部分多邊形。索引層的快速過濾在多邊形的MBR和點(diǎn)四叉樹之間直接進(jìn)行雙層循環(huán)，快速查詢與MBR相交的四叉樹節(jié)點(diǎn)。按照疊加順序的分析，多邊形MBR作為外層循環(huán)，點(diǎn)四叉樹作為內(nèi)部循環(huán)，其中矩形間的碰撞檢測(cè)如圖4所示。多邊形MBR首先會(huì)與高層次的樹節(jié)點(diǎn)求交，然后依次遍歷該層次下面的子節(jié)點(diǎn)，以發(fā)現(xiàn)相交的底層葉子節(jié)點(diǎn)為終止條件。這些葉子節(jié)點(diǎn)被提交，并準(zhǔn)備做下一步的精確包含測(cè)試。

圖3 中國(guó)城市四叉樹索引

Fig.3 Quadtree index for cities in China

圖4 MBR查詢點(diǎn)圖層四叉樹示例

Fig.4 Query quadtree using MBR

圖4中矩形查詢的過程分為：1)查詢框與Level1節(jié)點(diǎn)相交，但是Level1中并不包含具體點(diǎn)對(duì)象。2)查詢框與Level2中節(jié)點(diǎn)相交，同樣Level1中也不包含點(diǎn)對(duì)象，但是其子節(jié)點(diǎn)需要進(jìn)一步檢測(cè)。3)查詢框與Level3中的4個(gè)索引節(jié)點(diǎn)相交，并且包含一個(gè)點(diǎn)對(duì)象，將該點(diǎn)追加到輸出列表。右上的Level2節(jié)點(diǎn)沒有分裂生成Level3節(jié)點(diǎn)，因此不必進(jìn)一步查詢。4)進(jìn)一步查詢發(fā)現(xiàn)查詢框與6個(gè)Level4的節(jié)點(diǎn)相交，并在其中一個(gè)節(jié)點(diǎn)發(fā)現(xiàn)另一個(gè)點(diǎn)。因?yàn)閯偘l(fā)現(xiàn)的點(diǎn)在網(wǎng)格邊上，所以被劃歸為L(zhǎng)evel3層次的點(diǎn)。

查詢實(shí)驗(yàn)共探測(cè)到2個(gè)點(diǎn)，其中一個(gè)在Level1線上，雖然該點(diǎn)沒有與查詢框明顯碰撞，但是仍然需要返回。實(shí)際運(yùn)算中有大量點(diǎn)的情況下該判斷方法作為規(guī)則執(zhí)行。以上四叉樹查詢結(jié)果是多邊形MBR所包含的點(diǎn)，如果不使用四叉樹空間索引查詢，可以利用MBR快速排斥達(dá)到同樣的效果(圖4)，但是查詢效率相對(duì)較低。四叉樹查詢的計(jì)算復(fù)雜度為O(logn)，而MBR直接過濾方法的計(jì)算復(fù)雜度為O(n)，因此采用效率較高的索引查詢方式。

(4)精確包含測(cè)試。在以上預(yù)處理工作的基礎(chǔ)上，多邊形MBR外的點(diǎn)已經(jīng)被過濾掉，本階段將進(jìn)行逐步求精的工作。精確求交過程既可以直接利用典型的winding-number包含算法實(shí)現(xiàn)，也可以采用本文設(shè)計(jì)的多核并行方法進(jìn)一步加速疊加過程。當(dāng)集群中存在大規(guī)模的并行節(jié)點(diǎn)時(shí)，因?yàn)楣?jié)點(diǎn)間的通訊量呈平方級(jí)別的增長(zhǎng)，所以隨著計(jì)算中間結(jié)果的通信增加帶寬將成為瓶頸。一種增加程序效率線性的方法是用MPI/OpenMP混合編寫并行部分。本算法設(shè)計(jì)的基本原則是MPI負(fù)責(zé)粗粒度的并行代碼，OpenMP負(fù)責(zé)細(xì)粒度迭代部分的并行。設(shè)計(jì)思路是每個(gè)節(jié)點(diǎn)分配1～2個(gè)MPI進(jìn)程后，每個(gè)MPI進(jìn)程執(zhí)行多個(gè)OpenMP線程。OpenMP部分由于不需要進(jìn)程間通信，直接通過內(nèi)存共享方式交換信息，因此可以顯著減少程序所需通訊的信息。

結(jié)合以上多核算法與MPI算法，混合編程模式下的點(diǎn)面包含并行算法設(shè)計(jì)過程如下：1)使用初始化函數(shù)MPI_Init()啟動(dòng)MPI程序；2)在MPI任務(wù)內(nèi)啟動(dòng)OpenMP并行程序；3)主進(jìn)程或者M(jìn)PI子進(jìn)程串行執(zhí)行；4)MPI的進(jìn)程標(biāo)記被所有OpenMP線程共享；5)串行和并行區(qū)域調(diào)用MPI庫(kù)；6)使用MPI_Finize()終止MPI程序。

本文的點(diǎn)面圖層并行疊加分析方法中MPI主要負(fù)責(zé)分發(fā)多邊形要素的標(biāo)記id，然后啟動(dòng)子節(jié)點(diǎn)程序載入數(shù)據(jù)并開始計(jì)算。子節(jié)點(diǎn)對(duì)點(diǎn)圖層建立四叉樹索引、外包矩形查詢過濾過程無(wú)法并行化。最后階段的精確包含測(cè)試可以是并行算法也可以是串行算法，將被封裝成一個(gè)函數(shù)供該過程調(diào)用。單個(gè)多邊形對(duì)象的并行測(cè)試方法中含有大量的同步操作和數(shù)據(jù)調(diào)度，因此為保證算法的整體穩(wěn)定性，在圖層級(jí)別的并行時(shí)采用串行的測(cè)試方法。

(5)結(jié)果回收和輸出。子節(jié)點(diǎn)將真正包含測(cè)試后的結(jié)果發(fā)送給主節(jié)點(diǎn)，主節(jié)點(diǎn)負(fù)責(zé)接收并寫入新圖層。子節(jié)點(diǎn)不必發(fā)送真實(shí)的點(diǎn)要素?cái)?shù)據(jù)，只需要發(fā)送包含點(diǎn)的fid標(biāo)記數(shù)組。主節(jié)點(diǎn)接受后在本地圖層抽取數(shù)據(jù)，減少數(shù)據(jù)的傳輸和消息接收的排隊(duì)周期。各子節(jié)點(diǎn)均采用阻塞式發(fā)送，在確保主節(jié)點(diǎn)正確接收數(shù)據(jù)后返回消息。子節(jié)點(diǎn)發(fā)送中間結(jié)果說(shuō)明本地計(jì)算已經(jīng)完成，不需要考慮通信和計(jì)算的重疊問題，因此阻塞形式比較適合該情況。非阻塞形式的MPI通信可以實(shí)現(xiàn)計(jì)算與通信的重疊，但是在復(fù)雜計(jì)算中無(wú)法保證執(zhí)行情況的正確反饋[13]。

2 實(shí)驗(yàn)與分析

2.1 多核并行實(shí)驗(yàn)

首先采用多核并行的方式進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)為全國(guó)土地利用圖(圖5)和POI興趣點(diǎn)(表2)。圖6為全國(guó)土地利用圖與全國(guó)POI點(diǎn)并行疊加加速效果，從統(tǒng)計(jì)圖可以看出其中并發(fā)線程間的動(dòng)態(tài)調(diào)度方法加速效果明顯優(yōu)于靜態(tài)調(diào)度方法。數(shù)據(jù)量增加引起單線程運(yùn)行時(shí)間增加到6.9 s，在線程數(shù)達(dá)到8時(shí)，實(shí)際最大加速比為5.0，在一定程度上可以驗(yàn)證“并行數(shù)據(jù)粒度越大加速比越大”的正確性。在線程數(shù)大于4時(shí)，動(dòng)態(tài)調(diào)度策略的加速比呈現(xiàn)明顯上升趨勢(shì)，說(shuō)明多線程并發(fā)的點(diǎn)面疊加可以獲得較好的加速效果。

圖5 疊加多邊形(土地利用分類數(shù)據(jù))

Fig.5 Overlay polygon data

表2 疊加數(shù)據(jù)特征

Table 2 Features of overlay data

數(shù)據(jù)源名稱數(shù)據(jù)類型要素?cái)?shù)量線段數(shù)量點(diǎn)數(shù)量土地利用圖多邊形15615648894886547全國(guó)導(dǎo)航POI點(diǎn)點(diǎn)463142083142

圖6 多核并行加速實(shí)驗(yàn)計(jì)算時(shí)間

Fig.6 Computing time for multi-core paralleling computing test

2.2 MPI并行實(shí)驗(yàn)

按照上文MPI形式的并行點(diǎn)面疊加算法設(shè)計(jì)，在IBM高性能集群中對(duì)該算法進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為6臺(tái)機(jī)架式服務(wù)器，所有機(jī)器操作系統(tǒng)均為Redhat6.2(Linux Kernel2.6.40)，其中一臺(tái)4*6核機(jī)器作為主節(jié)點(diǎn)，其他節(jié)點(diǎn)作為子節(jié)點(diǎn)。空間數(shù)據(jù)存儲(chǔ)策略為每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)全局的矢量數(shù)據(jù)庫(kù)，主節(jié)點(diǎn)發(fā)送主動(dòng)疊加圖層的分解信息，各節(jié)點(diǎn)獨(dú)立進(jìn)行主動(dòng)圖層(多邊形)數(shù)據(jù)抽取，然后并行的對(duì)點(diǎn)圖層實(shí)現(xiàn)包含測(cè)試。

MPI并行點(diǎn)面包含疊加實(shí)驗(yàn)以數(shù)據(jù)量較大的土地利用圖和全國(guó)POI點(diǎn)為處理對(duì)象，分別采用1～12個(gè)進(jìn)程測(cè)試并行加速情況。測(cè)試實(shí)驗(yàn)效果如圖7所示，從中分析不同進(jìn)程的加速情況可以看出，在計(jì)算進(jìn)程不超過總體物理節(jié)點(diǎn)數(shù)量6時(shí)加速效果比較明顯，原因是在輪詢式的進(jìn)程任務(wù)分配情況下每個(gè)物理節(jié)點(diǎn)最多只運(yùn)行一個(gè)進(jìn)程，不存在同節(jié)點(diǎn)間進(jìn)程的重疊，因此對(duì)本地?cái)?shù)據(jù)庫(kù)訪問和CPU的消耗都比較小。MPI單進(jìn)程時(shí)計(jì)算用時(shí)為5 382 ms，在12個(gè)進(jìn)程時(shí)用時(shí)為893 ms，加速比從1上升到6.0。從1個(gè)進(jìn)程到2個(gè)進(jìn)程時(shí)的加速效果最高，變化范圍為1～1.62。從加速比的統(tǒng)計(jì)圖可看出多機(jī)多進(jìn)程情況下基本可以達(dá)到疊加的線性加速(圖8)。

圖7 MPI并行點(diǎn)面疊加實(shí)驗(yàn)計(jì)算耗時(shí)情況

Fig.7 Computing time for MPI test

圖8 MPI并行點(diǎn)面疊加實(shí)驗(yàn)加速比情況

Fig.8 Speedup for MPI test

對(duì)比單機(jī)多核與多機(jī)器集群的并行方式可以發(fā)現(xiàn)，單機(jī)環(huán)境下開啟多核計(jì)算得到的加速效率低于集群環(huán)境下多節(jié)點(diǎn)并行計(jì)算的加速效率。除單機(jī)CPU計(jì)算核心數(shù)量的限制外，OpenMP多核編程的共享內(nèi)存方式對(duì)于粗粒度的并行對(duì)象讀寫沖突情況較多；另外重要的一點(diǎn)是單機(jī)環(huán)境下的數(shù)據(jù)集中式存儲(chǔ)方式本身對(duì)并行計(jì)算的算法有較大限制，主線程啟動(dòng)的多個(gè)子線程無(wú)法同時(shí)在同一塊物理磁盤上進(jìn)行數(shù)據(jù)讀寫操作，導(dǎo)致數(shù)據(jù)并發(fā)訪問成為瓶頸，而集群環(huán)境下的多節(jié)點(diǎn)分布式存儲(chǔ)方式則可以有效地避免該問題，提高了執(zhí)行效率(圖9)。從加速效率上對(duì)比，MPI集群并行情況下的加速效率與多核并行情況下的動(dòng)態(tài)負(fù)載策略基本相同，但是二者加速效率均明顯高于OpenMP靜態(tài)調(diào)度策略。從并行運(yùn)行的時(shí)間分析，MPI并行時(shí)間少于多核并行策略，并且數(shù)據(jù)量越大加速效果越明顯。

圖9 MPI并行點(diǎn)面疊加實(shí)驗(yàn)加速效率

Fig.9 Speedup efficient for MPI test

3 結(jié)論

本文研究了分布式環(huán)境下點(diǎn)面疊加分析的在的并行化方法與實(shí)現(xiàn)。采用Hilbert空間索引的方式進(jìn)行多邊形數(shù)據(jù)的分發(fā)，各個(gè)計(jì)算節(jié)點(diǎn)經(jīng)過快速四叉樹和MBR過濾后進(jìn)行點(diǎn)面疊加分析。雙層索引以空間排序作為數(shù)據(jù)分解的依據(jù)，提高了各計(jì)算節(jié)點(diǎn)的運(yùn)算效率(減少多邊形與點(diǎn)的無(wú)效疊加)。分析實(shí)驗(yàn)結(jié)果可以得出針對(duì)點(diǎn)面疊加并行運(yùn)算的結(jié)論：多核并行疊加和MPI集群疊加方法均可以有效地加速點(diǎn)面包含測(cè)試操作，不同規(guī)模和形式的處理數(shù)據(jù)應(yīng)選擇不同的策略：在點(diǎn)與面圖層要素?cái)?shù)量較大時(shí)，適宜采用MPI消息傳遞形式的集群并行策略，數(shù)據(jù)量較小時(shí)采用多核并行的策略，并且調(diào)度策略使用動(dòng)態(tài)調(diào)度時(shí)加速效果較好。因?yàn)樵跀?shù)據(jù)量比較小時(shí)，MPI需要主節(jié)點(diǎn)進(jìn)行集群環(huán)境的初始化、數(shù)據(jù)的預(yù)分解處理和分解信息分發(fā)，對(duì)于數(shù)據(jù)量較小的點(diǎn)面疊加這些初始化過程占用時(shí)間比例較大，只有數(shù)據(jù)量達(dá)到一定的規(guī)模集群才能夠充分發(fā)揮計(jì)算功能。該方法可以實(shí)現(xiàn)并行計(jì)算中的數(shù)據(jù)負(fù)載均衡，減少數(shù)據(jù)沖突，并行加速效果明顯，可以作為一種地學(xué)并行計(jì)算模式探討其他空間分析方法的并行化。

[1] KRIEGEL H P,BRINKHOFF T,SCHNEIDER R.An efficient map overlay algorithm based on spatial access methods and computational geometry[C].Proc.Int.Workshop on DBMS′s for Geographical Applications,1991.

[2] DING Y,DENSHAM P J.Spatial strategies for parallel spatial modelling[J].International Journal of Geographical Information Systems,1996,10(6):669-698.

[3] 吳立新,楊宜舟,秦承志,等.面向新型硬件構(gòu)架的新一代GIS基礎(chǔ)并行算法研究[J].地理與地理信息科學(xué),2013,29(4):1-8.

[4] 王結(jié)臣,王豹,胡瑋,等.并行空間分析算法研究進(jìn)展及評(píng)述[J].地理與地理信息科學(xué),2011,27(6):1-5.

[5] 謝忠,葉梓,吳亮.簡(jiǎn)單要素模型下多邊形疊置分析算法[J].地理與地理信息科學(xué),2007,23(3):19-23.

[6] 張樹清,張策,楊典華,等.簡(jiǎn)單要素模型下的多邊形對(duì)象疊加并行運(yùn)算策略研究[J].地理與地理信息科學(xué),2013,29(4):43-43.

[7] 趙斯思,周成虎.GPU加速的多邊形疊加分析[J].地理科學(xué)進(jìn)展,2013,32(1):114-120.

[8] 范俊甫,馬廷,周成虎,等.分治法在GIS多邊形快速合并算法中的應(yīng)用及效率提升評(píng)價(jià)模型[J].地球信息科學(xué)學(xué)報(bào),2014,16(2):158-164.

[9] 周玉科,馬廷,周成虎,等.MySQL集群與MPI的并行空間分析系統(tǒng)設(shè)計(jì)與實(shí)驗(yàn)[J].地球信息科學(xué)學(xué)報(bào),2012,14(4):448-453.

[10] 朱效民,趙紅超,方金云.魯棒高效的矢量地圖疊加分析算法[J].遙感學(xué)報(bào),2012,16(3):448-465.

[11] 鐘業(yè)勛,朱重光,魏文展.地圖空間認(rèn)知的數(shù)學(xué)原理[J].測(cè)繪科學(xué),2005,30(5):11-12.

[12] 張明波,陸鋒,申排偉,等.R樹家族的演變和發(fā)展[J].計(jì)算機(jī)學(xué)報(bào),2005,28(3):289-300.

[13] 胡曉力,田有先.多粒度并行計(jì)算集群研究與應(yīng)用[J].電力學(xué)報(bào),2008,22(4):436-438.

A Double-Index and Data Divide-Conquer Based Parallel Point-Polygon Overlay Method

ZHOU Yu-ke1,ZHOU Cheng-hu1,MA Ting1,GAO Xi-zhang1,FAN Jun-fu2,XU Tao1,JI Min3

(1.LREIS,InstituteofGeographicSciencesandNaturalResourcesResearch,CAS,Beijing100101; 2.SchoolofArchitecturalEngineering,ShandongUniversityofTechnology,Zibo255049; 3.CollegeofGeomatics,ShandongUniversityofScienceandTechnology,Qingdao266510,China)

Map overlay analysis is a computing intense algorithm,so it is straightforward that parallel computing algorithms can speed up the executing efficiency.The paper aims to study the method and implement of the parallel point-polygon overlay analysis in a distributed computing environment.Firstly,according to the characteristic of point-polygon overlay analysis,spatial data decomposition method is designed to make parallel available on the basis of spatial index.Then geographical data is processed by using the divide-conquer method on a parallel computing system.In this parallel point-polygon overlay method,double layer index mechanism is applied in order to accelerate the query process in geometry overlay step.On the one hand,the polygon layer is indexed and sorted by Hilbert space-filling curve,and then the data can be distributed to every computing node.On the other hand,point layer is indexed by quad-tree structure in order to speed up the query and filter process executed by every polygon.Finally,this parallel method is implemented on a Linux based cluster system.Coarse-grained task is paralleled using the MPI cluster-computing tool,and on every computing node the fine-grained task is paralleled using the OpenMP multi-core paralleling computing tool.The results show that this parallel point-polygon overlay method is able to reduce the I/O conflicts and every node is independent in computing process,from which apparent speedup is obtained.This work can give a new insight in map overlay analysis,meanwhile it provides a meaningful way for computing pattern of GIS data in the big data era.

map overlay;parallel computing;spatial index;MPI;OpenMP

2014-08-13；

2014-10-27

中國(guó)科學(xué)院重點(diǎn)部署項(xiàng)目(KZZD-EW-07)；山東科技大學(xué)科研創(chuàng)新團(tuán)隊(duì)支持計(jì)劃項(xiàng)目(2011KYTD103)

周玉科(1984—)，男，博士后，從事高性能地學(xué)計(jì)算、空間分析研究。E-mail:zyk@lreis.ac.cn

10.3969/j.issn.1672-0504.2015.02.001

P208

A

1672-0504(2015)02-0001-06