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

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

2013年以來，每年僅中國產(chǎn)生的數(shù)據(jù)總量就達到ZB級，相當(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ù)拓撲的一致性是其核心問題[2-3]。雖然近年計算機的計算能力迅速提高，尤其是多核計算機和并行計算機開始普及，但地籍?dāng)?shù)據(jù)本身的空間復(fù)雜性，使得傳統(tǒng)串行環(huán)境下的空間拓撲檢查方法難以充分利用這些先進的計算資源，已遠不能滿足實際應(yīng)用中地籍?dāng)?shù)據(jù)拓撲一致性檢查效率的需求[4]?，F(xiàn)有的并行技術(shù)、分布式技術(shù)、云技術(shù)正在與GIS理論進行著深度融合[5]，在柵格方面進行的數(shù)據(jù)并行算法研究[5-6]較多，但在矢量方面關(guān)于并行拓撲質(zhì)量檢查的研究較少[7-9]。

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

1 拓撲關(guān)系原理與高性能計算模式

1.1 拓撲關(guān)系基本原理

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

表1 三類拓撲關(guān)系描述模型的比較[9]

1.2 高性能計算模式

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

圖1 云計算平臺

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

2 拓撲關(guān)系并行計算策略

2.1 拓撲關(guān)系檢查計算特點分析

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

(1)

2.2 拓撲關(guān)系并行化分析

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

圖2 空間拓撲關(guān)系之間的聯(lián)系與計算層次

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

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

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

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

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

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

2.4 拓撲關(guān)系并行計算

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

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

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

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

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

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

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

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

(7) 收集各進程拓撲計算中符合約束條件的結(jié)果。

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

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

圖4 拓撲關(guān)系并行計算流程

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

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

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

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

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

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

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

圖5 宗地數(shù)據(jù)重疊檢查運行結(jié)果

3.4 均衡性分析與加速效果

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

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

由矢量拓撲關(guān)系并行計算加速比、并行效率(如圖6所示)可見：加速比與進程數(shù)呈線性正相關(guān)，在12個進程時加速比達到9.5倍，拓撲并行算法的計算效率穩(wěn)定在80%(斜率約為0.8)。

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

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

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

圖6 拓撲關(guān)系并行算法的加速比和并行效率

4 結(jié) 論

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