何 群,楊宜舟,郭甲騰，吳立新，劉善軍

(1.東北大學(xué)資源與土木工程學(xué)院，遼寧 沈陽 110004; 2.中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南 長沙 410012)

2013年以來，每年僅中國產(chǎn)生的數(shù)據(jù)總量就達(dá)到ZB級(jí)，相當(dāng)于2009年全球的數(shù)據(jù)總量，而其中具有空間屬性的數(shù)據(jù)大約有80%[1]。地籍?dāng)?shù)據(jù)是一種典型性、復(fù)雜性的空間數(shù)據(jù)，其在數(shù)據(jù)海量性環(huán)境下的質(zhì)量控制是亟待解決的問題，而地籍?dāng)?shù)據(jù)拓?fù)涞囊恢滦允瞧浜诵膯栴}[2-3]。雖然近年計(jì)算機(jī)的計(jì)算能力迅速提高，尤其是多核計(jì)算機(jī)和并行計(jì)算機(jī)開始普及，但地籍?dāng)?shù)據(jù)本身的空間復(fù)雜性，使得傳統(tǒng)串行環(huán)境下的空間拓?fù)錂z查方法難以充分利用這些先進(jìn)的計(jì)算資源，已遠(yuǎn)不能滿足實(shí)際應(yīng)用中地籍?dāng)?shù)據(jù)拓?fù)湟恢滦詸z查效率的需求[4]。現(xiàn)有的并行技術(shù)、分布式技術(shù)、云技術(shù)正在與GIS理論進(jìn)行著深度融合[5]，在柵格方面進(jìn)行的數(shù)據(jù)并行算法研究[5-6]較多，但在矢量方面關(guān)于并行拓?fù)滟|(zhì)量檢查的研究較少[7-9]。

本文在分析拓?fù)潢P(guān)系計(jì)算特點(diǎn)的基礎(chǔ)上，結(jié)合四叉樹和R樹的多級(jí)多重并行空間索引(Q&R索引)，解決了矢量地理對(duì)象數(shù)據(jù)的快速定位(數(shù)據(jù)過濾)和空間分割問題；同時(shí)提出一種基于Q&R索引實(shí)現(xiàn)拓?fù)溆?jì)算過程中任務(wù)調(diào)度的方法，從數(shù)據(jù)層實(shí)現(xiàn)空間拓?fù)潢P(guān)系計(jì)算的并行化。

1 拓?fù)潢P(guān)系原理與高性能計(jì)算模式

1.1 拓?fù)潢P(guān)系基本原理

拓?fù)潢P(guān)系是GIS的重要特征，表達(dá)空間目標(biāo)之間的在空間上相鄰程度的一種定性關(guān)系。現(xiàn)有空間拓?fù)潢P(guān)系的描述模型主要有3種[9]：基于點(diǎn)集理論的描述模型(4-交模型與9-交模型)、基于RCC理論的描述模型、基于Voronoi圖的9-交模型。相較于RCC理論描述模型和Voronoi圖，9-交模型適用幾何對(duì)象廣泛且有相對(duì)較高的計(jì)算效率，更加適用于研發(fā)拓?fù)潢P(guān)系計(jì)算的高性能算法(見表1)。

表1 三類拓?fù)潢P(guān)系描述模型的比較[9]

1.2 高性能計(jì)算模式

現(xiàn)有空間高性能計(jì)算環(huán)境主要分為并行計(jì)算、分布式計(jì)算、集群計(jì)算與云計(jì)算等，其共同點(diǎn)在于通過并行化算法充分利用更多的計(jì)算資源，以實(shí)現(xiàn)空間數(shù)據(jù)和空間分析的高效計(jì)算，而區(qū)別在于其計(jì)算模式不同[9-12]。不同于其他高性能計(jì)算，云計(jì)算是未來的發(fā)展趨勢(shì)，其特征在于空間計(jì)算資源的彈性化供給[11-13]。云計(jì)算通過虛擬化技術(shù)和資源管理技術(shù)為用戶提供多種虛擬的高性能計(jì)算環(huán)境(如圖1所示)，如并行計(jì)算環(huán)境、分布式計(jì)算環(huán)境等。

圖1 云計(jì)算平臺(tái)

據(jù)上所述，本文主要研究拓?fù)潢P(guān)系的并行化方法，以期在云平臺(tái)下虛擬并行環(huán)境或集群環(huán)境下高效運(yùn)行。本文采用單程序多數(shù)據(jù)(single program multiple data，SPMD)[14]模式設(shè)計(jì)拓?fù)溆?jì)算并行算法，基本思路為：通過空間數(shù)據(jù)集劃分方法，將空間數(shù)據(jù)分配至不同進(jìn)程；在空間索引支持下，各進(jìn)程對(duì)不同的空間數(shù)據(jù)集進(jìn)行協(xié)同并行計(jì)算。

2 拓?fù)潢P(guān)系并行計(jì)算策略

2.1 拓?fù)潢P(guān)系檢查計(jì)算特點(diǎn)分析

拓?fù)潢P(guān)系的基礎(chǔ)算法屬于計(jì)算幾何方法的一部分，其粒度最小的算子可歸納為節(jié)點(diǎn)間關(guān)系計(jì)算、點(diǎn)與線間關(guān)系計(jì)算，而拓?fù)潢P(guān)系檢查計(jì)算是在某些約束條件下進(jìn)行點(diǎn)與點(diǎn)之間或點(diǎn)組與點(diǎn)組之間的計(jì)算。矢量數(shù)據(jù)基本要素有點(diǎn)(Pi)、線(Li)、面(Poi)，而以上數(shù)據(jù)都是由點(diǎn)要素構(gòu)成，即Poi={L1,L2,…,Lm}，Li={P1,P2,…,Pn}。點(diǎn)是矢量數(shù)據(jù)中最簡(jiǎn)單、最結(jié)構(gòu)化的要素，假定點(diǎn)每次參與計(jì)算的計(jì)算量為Cp，則矢量目標(biāo)之間的關(guān)系計(jì)算，如線、線求交，屬于“乘積”型幾何計(jì)算，其計(jì)算量Cp為

(1)

2.2 拓?fù)潢P(guān)系并行化分析

根據(jù)矢量目標(biāo)之間拓?fù)潢P(guān)系的層次化計(jì)算關(guān)系(如圖2所示)，分析拓?fù)潢P(guān)系計(jì)算的層次關(guān)系，可知其特點(diǎn)為：①對(duì)于某一矢量目標(biāo)，需判斷其與矢量目標(biāo)集中的其他所有對(duì)象是否相交；②只進(jìn)一步計(jì)算與其相交的矢量目標(biāo)間的精細(xì)拓?fù)潢P(guān)系。

圖2 空間拓?fù)潢P(guān)系之間的聯(lián)系與計(jì)算層次

分析特點(diǎn)①可知：矢量目標(biāo)之間一般先通過MBR(minimum bounding rectangle)的相交計(jì)算，過濾掉大部分相離的矢量目標(biāo)集；若采用復(fù)雜度最高的MBR直接過濾法，過濾耗時(shí)將急劇增加，嚴(yán)重制約著拓?fù)溆?jì)算的效率。因此，要實(shí)現(xiàn)高效拓?fù)潢P(guān)系并行計(jì)算，首先需要研究一種高效過濾非相交的矢量目標(biāo)算法。

分析特點(diǎn)②可知：拓?fù)潢P(guān)系計(jì)算中的矢量目標(biāo)可分解為約束條件下的點(diǎn)點(diǎn)拓?fù)溆?jì)算集或點(diǎn)線拓?fù)溆?jì)算集，若將計(jì)算集分治計(jì)算會(huì)破壞矢量目標(biāo)數(shù)據(jù)的完整性。因此，需要從數(shù)據(jù)集上設(shè)計(jì)一種拓?fù)潢P(guān)系的并行化方法，既顧及矢量目標(biāo)數(shù)據(jù)的完整性，又提升拓?fù)潢P(guān)系并行計(jì)算的效率。

由上述分析可知：通過功能劃分實(shí)現(xiàn)拓?fù)潢P(guān)系的并行化會(huì)破壞矢量目標(biāo)的數(shù)據(jù)完整性，而通過數(shù)據(jù)劃分實(shí)現(xiàn)拓?fù)溆?jì)算并行化具有較高的可行性。數(shù)據(jù)劃分的約束條件有：①將空間索引與數(shù)據(jù)劃分相融合，提高相離矢量目標(biāo)集(命中相交矢量目標(biāo)集)的過濾效率，從數(shù)據(jù)劃分方法上實(shí)現(xiàn)拓?fù)潢P(guān)系計(jì)算量劃分均衡(任務(wù)均衡)；②任務(wù)均衡通過計(jì)算量模型“乘積”相等實(shí)現(xiàn)，即與任一矢量目標(biāo)集A有相交關(guān)系的各節(jié)點(diǎn)中矢量目標(biāo)集合Sn(1

2.3 數(shù)據(jù)劃分方案

根據(jù)以上分析，對(duì)于計(jì)算量屬于“乘積”方式的空間拓?fù)溆?jì)算，在數(shù)據(jù)劃分后仍保持各節(jié)點(diǎn)的計(jì)算量C近似相等，則各節(jié)點(diǎn)中要素集的點(diǎn)總數(shù)需近似相等，且需從各層數(shù)據(jù)的空間分布及參與計(jì)算的概率考慮，各層檢索與矢量目標(biāo)集A可發(fā)生相交計(jì)算的要素集點(diǎn)數(shù)需要近似相等。因此，需要結(jié)合基于四叉樹(Q樹)數(shù)據(jù)初步劃分和顧及“乘積”計(jì)算量的再次劃分(再次劃分后建立R樹)，即在劃分?jǐn)?shù)據(jù)的過程中，不僅從數(shù)據(jù)層實(shí)現(xiàn)了負(fù)載(任務(wù))均衡，并且構(gòu)建的Q&R并行索引也極大提高了數(shù)據(jù)篩選的效率，特別是在海量數(shù)據(jù)的環(huán)境下更能發(fā)揮出Q&R并行索引優(yōu)勢(shì)，提升并行拓?fù)溆?jì)算的效率。

首先，通過Q樹葉子節(jié)點(diǎn)對(duì)矢量目標(biāo)集進(jìn)行初始范圍劃分，將空間數(shù)據(jù)集V分割為數(shù)據(jù)塊集S{dS1,dS2,…,dSm},Q樹各葉子節(jié)點(diǎn)包含對(duì)應(yīng)的數(shù)據(jù)塊dSn；其次，將各葉子節(jié)點(diǎn)中矢量目標(biāo)數(shù)據(jù)塊dSn進(jìn)一步劃分為dS{dSnc1,dSnc2,…,dSncp}，分配至各計(jì)算節(jié)點(diǎn)(將Q樹各葉子節(jié)點(diǎn)切片為p個(gè)葉子節(jié)點(diǎn)，即將Q樹切為p個(gè)深度相同的Q樹)，使各計(jì)算節(jié)點(diǎn)位置相同的Q樹葉子節(jié)點(diǎn)的Cp近似相等，并對(duì)dS集合建立R樹索引，進(jìn)一步提升數(shù)據(jù)篩選的效率(如圖3所示)。

2.4 拓?fù)潢P(guān)系并行計(jì)算

拓?fù)潢P(guān)系計(jì)算分為兩種情況：①空間數(shù)據(jù)集A與空間數(shù)據(jù)集B的空間拓?fù)溆?jì)算，篩選出符合拓?fù)浼s束條件c(c為相離、相接、疊加、包含或穿越)的空間數(shù)據(jù)C；②空間數(shù)據(jù)集A中各空間數(shù)據(jù)之間的拓?fù)潢P(guān)系，可理解為空間數(shù)據(jù)集A與空間數(shù)據(jù)集A的空間拓?fù)溆?jì)算。因此，兩種情況可采用相同的并行方式。具體步驟如下(設(shè)并行程序運(yùn)行的進(jìn)程數(shù)為P)：

圖3 數(shù)據(jù)劃分過程

(1) 根據(jù)本文的數(shù)據(jù)劃分方法對(duì)空間數(shù)據(jù)集A進(jìn)行劃分，并建立Q&R并行索引(包含P個(gè)Q&R索引)。

(2) 根據(jù)本文的四叉樹劃分(Q樹深度為m)方法對(duì)空間數(shù)據(jù)集B進(jìn)行劃分，劃分后數(shù)據(jù)塊為S1,S2,…,Sm×m。

(3) 各進(jìn)程讀取空間數(shù)據(jù)塊Sn(10,則為S(p+1)→Sm×m→S(p)。

(4) 各進(jìn)程讀取數(shù)據(jù)塊Sn中空間目標(biāo)oi的MBR，在該節(jié)點(diǎn)對(duì)應(yīng)的Q&R索引中檢索與其進(jìn)行拓?fù)溆?jì)算的數(shù)據(jù)集di，oi與di采用V-9I模型進(jìn)行拓?fù)溆?jì)算(如圖4所示)。

(5) 重復(fù)步驟(4)直至數(shù)據(jù)塊Sn中所有空間目標(biāo)都計(jì)算完畢。

(6) 重復(fù)步驟(3)—(5)直至各進(jìn)程中所有空間數(shù)據(jù)塊(S1,S2,…,Sm×m)都參與計(jì)算各節(jié)點(diǎn)Q&R索引對(duì)應(yīng)的空間數(shù)據(jù)集完畢。

(7) 收集各進(jìn)程拓?fù)溆?jì)算中符合約束條件的結(jié)果。

3 應(yīng)用試驗(yàn)分析

本文基于消息傳遞接口模式的并行框架，采用C++語言實(shí)現(xiàn)跨平臺(tái)的并行算法開發(fā)，實(shí)現(xiàn)并行算法在不同的硬件環(huán)境下(如單機(jī)、集群和云環(huán)境)運(yùn)行。

圖4 拓?fù)潢P(guān)系并行計(jì)算流程

3.1 應(yīng)用環(huán)境

空間拓?fù)洳⑿杏?jì)算中間件部署在云平臺(tái)下的虛擬集群中，為實(shí)際應(yīng)用提供服務(wù)。該環(huán)境由5個(gè)虛擬計(jì)算節(jié)點(diǎn)及1個(gè)虛擬存儲(chǔ)節(jié)點(diǎn)(4 TB)構(gòu)成，集群中各節(jié)點(diǎn)的操作系統(tǒng)是Redhat 5.04(64位)，消息傳遞采用OpenMPI并行庫，節(jié)點(diǎn)間采用高速交換機(jī)進(jìn)行通信，見表2。

表2 云環(huán)境下的虛擬集群

3.2 應(yīng)用數(shù)據(jù)

本試驗(yàn)有兩組應(yīng)用數(shù)據(jù)：①矢量目標(biāo)集1為國內(nèi)某地區(qū)的5.6萬塊宗地；②矢量目標(biāo)集2為某地區(qū)70萬塊宗地，其中第1組試驗(yàn)數(shù)據(jù)用于正確性驗(yàn)證， 參照對(duì)象ArcGIS；第2組數(shù)據(jù)相比第1組數(shù)據(jù)提升了一個(gè)數(shù)量級(jí)，在單節(jié)點(diǎn)環(huán)境下已超出ArcGIS的計(jì)算能力，用于驗(yàn)證本文提出拓?fù)潢P(guān)系計(jì)算方法的并行性能。

3.3 商業(yè)軟件對(duì)比分析

采用第1組宗地?cái)?shù)據(jù)進(jìn)行宗地多邊形的重疊檢查，共有9處重疊區(qū)域，其與ArcGIS計(jì)算結(jié)果一致(如圖5所示)。在相同的硬件環(huán)境下，多次運(yùn)行ArcGIS拓?fù)溆?jì)算工具的平均耗時(shí)為51 s，而本文并行拓?fù)溆?jì)算的多次運(yùn)行平均耗時(shí)為15 s，相比ArcGIS拓?fù)溆?jì)算效率提升了3倍。

圖5 宗地?cái)?shù)據(jù)重疊檢查運(yùn)行結(jié)果

3.4 均衡性分析與加速效果

如表3所示，在相同計(jì)算環(huán)境、不同進(jìn)程數(shù)時(shí)宗地重疊拓?fù)錂z查的耗時(shí)最壞差率不超過6.5%，表明本文并行算法可實(shí)現(xiàn)地籍?dāng)?shù)據(jù)中的宗地拓?fù)浏B加質(zhì)量檢查的負(fù)載基本均衡與任務(wù)基本均衡。隨著進(jìn)程數(shù)的增多、各個(gè)進(jìn)程計(jì)算量的減少，計(jì)算耗時(shí)降低、耗時(shí)差率越大，反之則表明計(jì)算的數(shù)據(jù)量越大、耗時(shí)差率越小，耗時(shí)差率與數(shù)據(jù)量的大小呈負(fù)相關(guān)性，即在大數(shù)據(jù)環(huán)境下，應(yīng)用本文方法實(shí)現(xiàn)矢量算法并行計(jì)算，可更有效解決負(fù)載均衡與任務(wù)均衡。

表3 不同進(jìn)程數(shù)條件下各進(jìn)程時(shí)間消耗

由矢量拓?fù)潢P(guān)系并行計(jì)算加速比、并行效率(如圖6所示)可見：加速比與進(jìn)程數(shù)呈線性正相關(guān)，在12個(gè)進(jìn)程時(shí)加速比達(dá)到9.5倍，拓?fù)洳⑿兴惴ǖ挠?jì)算效率穩(wěn)定在80%(斜率約為0.8)。

3.5 數(shù)據(jù)劃分時(shí)間分析

數(shù)據(jù)劃分時(shí)間與拓?fù)潢P(guān)系計(jì)算的時(shí)間對(duì)比見表4。通過對(duì)數(shù)據(jù)層劃分并建立Q&R并行索引實(shí)現(xiàn)拓?fù)潢P(guān)系計(jì)算的并行化，所耗費(fèi)的時(shí)間遠(yuǎn)小于任務(wù)執(zhí)行總時(shí)間(輸入、計(jì)算與輸出總時(shí)間)。由此可知，基于空間索引的數(shù)據(jù)劃分與數(shù)據(jù)調(diào)度方法，可有效實(shí)現(xiàn)拓?fù)潢P(guān)系計(jì)算的并行化。

表4 不同進(jìn)程數(shù)條件下數(shù)據(jù)劃分與任務(wù)總時(shí)間比率

圖6 拓?fù)潢P(guān)系并行算法的加速比和并行效率

4 結(jié) 論

本文針對(duì)云環(huán)境下地籍?dāng)?shù)據(jù)拓?fù)潢P(guān)系質(zhì)量檢查算法并行化進(jìn)行了研究與探索，通過引入Q&R并行空間索引實(shí)現(xiàn)了拓?fù)溆?jì)算前的數(shù)據(jù)劃分和拓?fù)溆?jì)算過程中的數(shù)據(jù)過濾，基本解決了拓?fù)溆?jì)算任務(wù)均衡和負(fù)載均衡，并且提升了拓?fù)洳⑿杏?jì)算的效率，使其并行效率達(dá)到80%?；趶?fù)雜度較高的地籍(宗地)數(shù)據(jù)，對(duì)拓?fù)洳⑿兴惴ㄟM(jìn)行了應(yīng)用測(cè)試，驗(yàn)證了本文方法的可行性與優(yōu)勢(shì)性，也為其他矢量數(shù)據(jù)計(jì)算分析的并行化研究提供了參考和思路。本文空間拓?fù)洳⑿兴惴ㄖС衷破脚_(tái)下的虛擬化集群部署與運(yùn)行，包括單機(jī)多核、集群等多種高性能環(huán)境，但在不同環(huán)境中仍需要考慮網(wǎng)絡(luò)通信、存儲(chǔ)和計(jì)算對(duì)空間并行算法的影響，可作為后續(xù)的研究方向。