范俊甫,馬 廷,周成虎,季 民,周玉科,許 濤,3

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

幾何部件緩沖區(qū)域合并的Buffer算法及其并行優(yōu)化方法

范俊甫1,2,3,馬 廷2,周成虎2,季 民4,周玉科2,許 濤2,3

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

在介紹一種基于幾何部件緩沖區(qū)域合并的矢量數(shù)據(jù)緩沖區(qū)生成算法的基礎(chǔ)上,采用數(shù)據(jù)并行思想和MPI編程模型對(duì)緩沖區(qū)算法的并行化實(shí)現(xiàn)和優(yōu)化方法開展研究。試驗(yàn)結(jié)果顯示,與ArcGIS Buffer工具相比:①當(dāng)緩沖區(qū)結(jié)果多邊形不合并時(shí),雖然串行緩沖區(qū)算法的時(shí)間開銷較高,但可輕易通過并行方式實(shí)現(xiàn)加速;②當(dāng)緩沖區(qū)結(jié)果合并時(shí),本文算法要明顯優(yōu)于ArcGIS Buffer工具,并且經(jīng)過優(yōu)化的并行緩沖區(qū)算法表現(xiàn)出更高的計(jì)算效率和更大規(guī)模的數(shù)據(jù)處理能力。因此,基于幾何部件緩沖區(qū)域合并的Buffer算法具備一定的實(shí)用價(jià)值,本文提出的按節(jié)點(diǎn)數(shù)量的任務(wù)分解方法和進(jìn)程間結(jié)果樹狀歸并策略是對(duì)緩沖區(qū)算法進(jìn)行并行優(yōu)化的有效途徑,對(duì)GIS中其他矢量分析算法的并行化及相關(guān)優(yōu)化工作也具有一定的借鑒意義。

并行算法;緩沖區(qū);消息傳遞接口;任務(wù)分解;樹狀歸并

1 引 言

空間數(shù)據(jù)規(guī)模的快速膨脹給現(xiàn)有的計(jì)算資源和傳統(tǒng)的地學(xué)計(jì)算方法帶來了前所未有的壓力,高性能計(jì)算已成為解決海量空間數(shù)據(jù)分析、處理以及大規(guī)?？臻g可視化的重要手段[1-2]。集群環(huán)境下基于消息傳遞接口(message passing interface, MPI)的并行計(jì)算模式得到了充分的重視和發(fā)展,已有的并行化空間分析算法大多基于該架構(gòu)實(shí)現(xiàn)。數(shù)據(jù)劃分和任務(wù)分解是實(shí)現(xiàn)并行計(jì)算的兩種主要模式[3],目前高性能空間分析算法的研究仍然以數(shù)據(jù)并行方式為主[4]。許多學(xué)者對(duì)帶有拓?fù)潢P(guān)系的空間分析并行算法的任務(wù)劃分進(jìn)行了研究[5-7],本文選擇基于更利于實(shí)現(xiàn)并行任務(wù)分解的OGC簡(jiǎn)單要素模型開展對(duì)緩沖區(qū)算法開發(fā)和優(yōu)化的研究。

緩沖區(qū)處理的是一類鄰近度問題,代表了一種影響范圍或服務(wù)范圍,是地圖信息檢索與綜合處理和GIS空間分析的重要功能[8-9]。以往針對(duì)緩沖區(qū)分析算法的研究多面向緩沖區(qū)域的生成算法展開,例如文獻(xiàn)[9]提出了雙線生成的幾何算法模型和針對(duì)自相交問題的關(guān)系處理模型。文獻(xiàn)[11]詳細(xì)描述了線段集合的非對(duì)稱緩沖區(qū)生成算法,文獻(xiàn)[12]基于文獻(xiàn)[11]的線段緩沖區(qū)生成算法,實(shí)現(xiàn)了采用掃描線思想和向量代數(shù)的緩沖區(qū)生成和結(jié)果多邊形融合算法。文獻(xiàn)[13]提出了一種基于緩沖曲線和邊約束三角網(wǎng)輔助的矢量緩沖區(qū)生成算法。文獻(xiàn)[14]基于“條帶掃描”思想實(shí)現(xiàn)了復(fù)雜線目標(biāo)緩沖區(qū)的構(gòu)建和效率優(yōu)化。雖然上述基于矢量計(jì)算方法的緩沖區(qū)生成算法可以得到較為精確的結(jié)果,但是需要諸多復(fù)雜的計(jì)算和空間關(guān)系判斷,實(shí)現(xiàn)過程較為復(fù)雜。文獻(xiàn)[15]提出了基于膨脹算法的緩沖區(qū)生成算法,其本質(zhì)是利用柵格化的思想簡(jiǎn)化矢量緩沖區(qū)生成的過程,但該算法不可避免地帶來誤差。緩沖區(qū)分析算法同樣面臨大數(shù)據(jù)量背景下的效率提升問題。文獻(xiàn)[16]在網(wǎng)格環(huán)境下利用分布式并行計(jì)算來加速緩沖區(qū)分析算法,但網(wǎng)格計(jì)算注重于異構(gòu)計(jì)算環(huán)境下的分布式處理,且難以達(dá)到高性能計(jì)算的目的。

幾何部件緩沖區(qū)域合并的本質(zhì)是多邊形合并,基于多邊形裁剪算法實(shí)現(xiàn)。目前公認(rèn)的能在有限時(shí)間內(nèi)完成任意多邊形裁剪問題的有效算法主要有Vatti算法[17]和Greiner-Hormann算法[19]等。Vatti算法是對(duì)文獻(xiàn)[20—21]所提出多邊形裁剪算法的重大改進(jìn),本文基于Vatti算法實(shí)現(xiàn)多邊形合并操作。目前一些商業(yè)GIS軟件的緩沖區(qū)分析工具的計(jì)算效率難以讓人滿意,且MPI環(huán)境下緩沖區(qū)算法的并行化及優(yōu)化方法的研究較少,因此大數(shù)據(jù)量應(yīng)用背景下的并行緩沖區(qū)算法及其優(yōu)化方法值得深入研究。

本文組織結(jié)構(gòu)為:首先給出基于幾何部件緩沖區(qū)域合并的Buffer串行算法,進(jìn)而比較該算法與ArcGIS Buffer工具在緩沖區(qū)結(jié)果多邊形合并與不合并兩種條件下的效率差異;其次基于數(shù)據(jù)并行的思想實(shí)現(xiàn)緩沖區(qū)分析的并行算法并分析其加速性能表現(xiàn);最后通過分析并行緩沖區(qū)分析算法的執(zhí)行過程,指出并行算法可能存在的性能瓶頸并提出對(duì)應(yīng)的優(yōu)化方案并進(jìn)行試驗(yàn)驗(yàn)證。

2 基于幾何部件緩沖區(qū)域合并的Buffer算法

2.1 幾何對(duì)象緩沖區(qū)構(gòu)造方法

矢量緩沖區(qū)生成算法包括平行線生成、構(gòu)環(huán)和空間關(guān)系處理3個(gè)步驟,其中構(gòu)環(huán)和空間關(guān)系處理過程包含大量的復(fù)雜數(shù)值計(jì)算,如交點(diǎn)計(jì)算、向量和夾角計(jì)算,自相交處理等,涉及多種特殊情況,實(shí)現(xiàn)較為困難。本文將成熟的多邊形裁剪算法引入矢量緩沖區(qū)的生成過程,用來代替復(fù)雜的構(gòu)環(huán)和空間關(guān)系處理等過程,實(shí)現(xiàn)對(duì)緩沖區(qū)生成算法的簡(jiǎn)化處理。單側(cè)緩沖區(qū)生成較為簡(jiǎn)單,且非對(duì)稱緩沖區(qū)可采用雙側(cè)區(qū)分處理、端點(diǎn)圓弧圓心平移的方法實(shí)現(xiàn),因此本研究?jī)H討論最為典型的雙側(cè)、對(duì)稱緩沖區(qū)的生成方法。下面分別描述點(diǎn)、線和多邊形3種基本幾何對(duì)象的緩沖區(qū)構(gòu)造方法,如圖1所示。

圖1 點(diǎn)、線、多邊形的緩沖區(qū)構(gòu)建Fig.1 Buffer zone construction of point,line and polygon

2.1.1 點(diǎn)

如圖1(a)所示,點(diǎn)P0以r為半徑的緩沖區(qū)域構(gòu)造方法為:以P0為圓心以r為半徑繪制首尾相連的圓環(huán)。實(shí)際僅需計(jì)算圓環(huán)落在以P0為原點(diǎn)的直角坐標(biāo)系第一象限內(nèi)的點(diǎn),其他象限內(nèi)點(diǎn)的坐標(biāo)均可由對(duì)稱性計(jì)算得到。求出圓環(huán)上所有點(diǎn)的坐標(biāo)后,順時(shí)針依次連接即構(gòu)成閉合的環(huán),即為點(diǎn)P0以r為半徑的緩沖區(qū)域。增加點(diǎn)數(shù)量對(duì)圓環(huán)進(jìn)行加密即可得到更為平滑的緩沖區(qū)邊界。對(duì)于由多個(gè)單點(diǎn)部件構(gòu)成的多點(diǎn)幾何對(duì)象,構(gòu)成它的每個(gè)點(diǎn)均按照單點(diǎn)幾何對(duì)象緩沖區(qū)的生成規(guī)則構(gòu)建各自的緩沖區(qū)域,結(jié)果可能將出現(xiàn)重疊,通過調(diào)用多邊形合并操作實(shí)現(xiàn)重疊區(qū)域的融合,得到合并后的多點(diǎn)幾何對(duì)象的緩沖區(qū)圖形。

2.1.2 線

線類型的幾何對(duì)象可看作是一組首尾相連的線段組,每條線段由兩個(gè)點(diǎn)部件構(gòu)成:起點(diǎn)和終點(diǎn)。如圖1(b)所示,折線L由L0、L1和L23條線段構(gòu)成,L的緩沖區(qū)由構(gòu)成它的每條線段的緩沖區(qū)通過多邊形合并操作得到。而線段的緩沖區(qū)生成過程包括3個(gè)步驟,以線段L0為例進(jìn)行說明:首先是求L0兩側(cè)距離為r的平行線Lleft和Lright;然后分別以L0起點(diǎn)P0和終點(diǎn)P1為圓心做半圓弧Cs和Ce;最后順次連接左側(cè)平行線Lleft、起點(diǎn)半圓弧Cs、右側(cè)平行線Lright和終點(diǎn)半圓弧Ce,得到線段L0的半徑為r的緩沖區(qū)域。

由于折線的緩沖區(qū)由構(gòu)成折線所有線段的緩沖區(qū)多邊形合并而來,而線段緩沖區(qū)為兩端均為半圓形的多邊形,因此相連線段的緩沖區(qū)多邊形在公共點(diǎn)處同為圓心重合的半圓形,因此當(dāng)相連線段不共線時(shí)將在沿著折線方向的折點(diǎn)反角一側(cè)形成弧形邊界。如圖1(b)所示,沿L0→L1→L2方向的P1左側(cè)和P2右側(cè)均為弧形邊界。由多條折線部件構(gòu)成的幾何對(duì)象稱為多線,只需將構(gòu)成多線的每條折線的緩沖區(qū)結(jié)果合并即可得到多線幾何對(duì)象的緩沖區(qū)。

2.1.3 多邊形

多邊形可看作由一組首尾閉合的折線包圍而成的面狀區(qū)域,閉合的折線稱為環(huán),根據(jù)構(gòu)成環(huán)的點(diǎn)的走向不同分為內(nèi)環(huán)和外環(huán)。簡(jiǎn)單多邊形指的是僅包含一個(gè)外環(huán)和若干個(gè)內(nèi)環(huán)的多邊形,包含了多個(gè)外環(huán)的多邊形稱為多多邊形,同樣,多多邊形的緩沖區(qū)域可由構(gòu)成它的每個(gè)簡(jiǎn)單多邊形的緩沖區(qū)合并得到?；趲缀尾考彌_區(qū)域合并的簡(jiǎn)單多邊形的緩沖區(qū)生成過程由分解、構(gòu)環(huán)、合并和剔除4個(gè)步驟組成。首先是對(duì)輸入多邊形的環(huán)進(jìn)行分解,得到一組折線,然后對(duì)每條折線按照?qǐng)D1(b)所示方法構(gòu)造獨(dú)立的緩沖區(qū)多邊形,再將折線緩沖區(qū)合并,最后對(duì)新生成的環(huán)進(jìn)行選擇性剔除。雙側(cè)緩沖區(qū)生成的剔除規(guī)則為:保留外環(huán)生成的外環(huán)和內(nèi)環(huán)生成的內(nèi)環(huán),其他均刪除。

如圖1(c)所示,輸入多邊形由外環(huán)R0和內(nèi)環(huán)R1構(gòu)成,分別將其在起點(diǎn)/終點(diǎn)處打斷后按照折線緩沖區(qū)生成方法構(gòu)建緩沖區(qū)域,得到R′0、R″0、R′1、R″1共4個(gè)環(huán),按照上述規(guī)則,保留外環(huán)R0生成的外環(huán)R′0和內(nèi)環(huán)R1生成的內(nèi)環(huán)R″1,刪除R″0和R′1,最后生成得到僅包含了環(huán)R′0和R″1的結(jié)果多邊形。在構(gòu)建內(nèi)環(huán)的內(nèi)側(cè)緩沖區(qū)時(shí)若合并后的緩沖區(qū)多邊形的內(nèi)環(huán)消失,說明緩沖區(qū)半徑超過了內(nèi)環(huán)可容納的緩沖范圍,此時(shí)將內(nèi)環(huán)生成的所有環(huán)丟棄,多邊形的緩沖區(qū)邊界同樣會(huì)出現(xiàn)弧形邊界部分。

2.2 串行算法性能分析

基于幾何部件緩沖區(qū)域合并的矢量數(shù)據(jù)緩沖區(qū)生成算法在處理線狀幾何對(duì)象時(shí)最為典型。為分析不同數(shù)據(jù)量下該算法的串行性能表現(xiàn),本文基于不同規(guī)模的真實(shí)路網(wǎng)線狀數(shù)據(jù)集開展了相關(guān)試驗(yàn),試驗(yàn)數(shù)據(jù)如圖2所示。緩沖區(qū)多邊形生成完成后的合并過程中,本文采用R樹空間索引[22]實(shí)現(xiàn)相交多邊形的預(yù)篩選來過濾掉不相交的多邊形,這種考慮到幾何要素間空間關(guān)系的預(yù)篩選策略能有效減少多邊形合并操作的調(diào)用次數(shù),提高算法效率。

圖2 試驗(yàn)數(shù)據(jù)及緩沖區(qū)結(jié)果實(shí)例Fig.2 Sample of experimental data and buffer results

本研究中試驗(yàn)平臺(tái)為Dell OPTIPLEX 990計(jì)算機(jī),配備主頻為3.4 GHz的Intel i7-2600 4核8線程CPU,4 G內(nèi)存,操作系統(tǒng)為Fedora Linux 15(運(yùn)行MPI程序)/Windows 7(運(yùn)行ArcGIS程序),本文在相同硬件平臺(tái)上與ArcGIS 9.3/10.1SP1版本下的串行Buffer工具進(jìn)行了對(duì)比,試驗(yàn)結(jié)果列于表1中。

表1 串行緩沖區(qū)生成算法時(shí)間開銷對(duì)比Tab.1 Time costs comparison of serial buffer algorithms

由表1可知,當(dāng)相交的緩沖區(qū)結(jié)果多邊形不合并時(shí),本文的緩沖區(qū)算法效率不及ArcGIS Buffer工具,效率平均相差0.7～1倍。但是當(dāng)合并相交的緩沖區(qū)結(jié)果多邊形時(shí),Arc GIS 10.1 SP1版本花費(fèi)了超過10 h卻未得到結(jié)果,而其9.3版本雖然能得到結(jié)果,但時(shí)間開銷比本文的緩沖區(qū)分析算法要多得多,且本文算法所體現(xiàn)出的性能優(yōu)勢(shì)隨數(shù)據(jù)量的增加而更加顯著。因此,本文認(rèn)為基于幾何部件緩沖區(qū)域合并的Buffer算法不僅可用,而且能有效解決目前商業(yè)GIS軟件中緩沖區(qū)分析合并過程中的嚴(yán)重性能瓶頸。

3 基于MPI的并行緩沖區(qū)生成算法

3.1 并行算法的邏輯流程

高性能計(jì)算技術(shù)是解決緩沖區(qū)分析中遇到的海量數(shù)據(jù)處理難題的有力工具,但必須對(duì)其實(shí)現(xiàn)和優(yōu)化方法進(jìn)行研究。并行緩沖區(qū)分析算法的邏輯流程包括了4個(gè)主要環(huán)節(jié),分別是任務(wù)劃分、并行構(gòu)建緩沖區(qū)、緩沖區(qū)多邊形合并和結(jié)果數(shù)據(jù)輸出,上述4個(gè)環(huán)節(jié)分別對(duì)應(yīng)分解、計(jì)算、合并和輸出4個(gè)步驟。

3.2 并行算法性能

本文按照上述邏輯流程設(shè)計(jì)并實(shí)現(xiàn)了基于MPI編程模型及數(shù)據(jù)并行思想的并行緩沖區(qū)分析算法,并采用與圖4類似的多組線狀真實(shí)路網(wǎng)數(shù)據(jù)開展試驗(yàn),結(jié)果在表2中列出。

表2 并行緩沖區(qū)生成時(shí)間開銷試驗(yàn)結(jié)果Tab.2 Time costs of polygon dissolving based parallel buffer algorithm

由表2可知,基于MPI和多邊形合并的并行緩沖區(qū)算法可以得到一定的并行加速,且當(dāng)緩沖區(qū)結(jié)果多邊形不需合并時(shí),采用4個(gè)進(jìn)程得到了與ArcGIS相近的計(jì)算效率,但其加速比并不理想,當(dāng)進(jìn)程數(shù)增多時(shí)并行計(jì)算效率甚至出現(xiàn)了下降趨勢(shì),這說明并行緩沖區(qū)算法存在進(jìn)一步優(yōu)化的空間,應(yīng)分析其性能瓶頸并加以優(yōu)化消除。

3.3 并行緩沖區(qū)算法瓶頸分析

實(shí)現(xiàn)高性能計(jì)算的一個(gè)無(wú)法回避的問題是如何平衡各個(gè)并行任務(wù)間的負(fù)載,因?yàn)橹挥羞_(dá)到了負(fù)載平衡才能使所有的計(jì)算任務(wù)在相近的時(shí)間內(nèi)完成,這對(duì)在基于MPI實(shí)現(xiàn)的集群并行計(jì)算環(huán)境中運(yùn)行的并行緩沖區(qū)算法尤為重要,因?yàn)橹挥惺孤氏韧瓿捎?jì)算任務(wù)的MPI進(jìn)程的合并操作的啟動(dòng)前等待時(shí)間最短,集群系統(tǒng)的綜合利用率才能得到提升。本文開展了兩次按照要素序列(feature ID,FID)進(jìn)行數(shù)據(jù)分割以實(shí)現(xiàn)并行任務(wù)分配的并行緩沖區(qū)分析試驗(yàn),并統(tǒng)計(jì)了速度相差最大的兩個(gè)進(jìn)程的分步時(shí)間開銷,試驗(yàn)結(jié)果在表 3中列出。

表3 序列劃分條件下的并行進(jìn)程間時(shí)間開銷差異Tab.3 Differences of time costs between processes of parallel buffer algorithm with data partition by FIDs

由表3可知,雖然基于要素序列的任務(wù)劃分方法能夠?qū)崿F(xiàn)不同MPI進(jìn)程間要素個(gè)數(shù)的平均分配,但是不同進(jìn)程間的矢量要素所包含的節(jié)點(diǎn)數(shù)量可能差異巨大,而基于Vatti算法實(shí)現(xiàn)的多邊形合并操作對(duì)節(jié)點(diǎn)數(shù)量敏感,基于該算法實(shí)現(xiàn)的緩沖區(qū)算法必然受其影響,這導(dǎo)致了進(jìn)程間任務(wù)負(fù)載的不均衡,直接后果是不同進(jìn)程間計(jì)算時(shí)間存在較大差異,最慢的進(jìn)程時(shí)間開銷約是最快者的2.2倍,最慢者的合并時(shí)間約是最快者的11.6倍。因此,數(shù)據(jù)分割不合理易帶來不均衡的任務(wù)負(fù)載,從而造成MPI并行算法潛在的性能瓶頸,對(duì)數(shù)據(jù)并行模式下的并行任務(wù)的均勻分解是實(shí)現(xiàn)MPI進(jìn)程間負(fù)載均衡的前提條件,也是對(duì)并行算法進(jìn)行優(yōu)化的重要方向。

此外,不同進(jìn)程的計(jì)算時(shí)間存在差異,在無(wú)法達(dá)到負(fù)載平衡時(shí)尤為明顯,這導(dǎo)致先計(jì)算完畢的進(jìn)程需要等待其他未完成的進(jìn)程,如果進(jìn)程間結(jié)果歸并的任務(wù)被分配給單一進(jìn)程統(tǒng)一執(zhí)行,該進(jìn)程需要等待其他所有進(jìn)程全部執(zhí)行完畢后才能繼續(xù)結(jié)果歸并的任務(wù),這顯然降低了并行系統(tǒng)的利用率,帶來性能瓶頸。根據(jù)最大限度降低MPI進(jìn)程間的互相等待時(shí)間的基本原則,需要重新設(shè)計(jì)MPI進(jìn)程間結(jié)果集合的歸并策略。

4 并行緩沖區(qū)算法優(yōu)化

4.1 并行任務(wù)分解

要素序列分割方法能保證分配到每個(gè)計(jì)算節(jié)點(diǎn)上的要素?cái)?shù)量大致相等,但卻無(wú)法保證各個(gè)計(jì)算節(jié)點(diǎn)負(fù)擔(dān)的計(jì)算量的均衡。針對(duì)并行矢量緩沖區(qū)結(jié)果合并算子對(duì)多邊形點(diǎn)數(shù)敏感的特點(diǎn),本文提出基于點(diǎn)數(shù)統(tǒng)計(jì)的并行任務(wù)數(shù)據(jù)分解方法。該方法以幾何對(duì)象所包含的節(jié)點(diǎn)數(shù)作為數(shù)據(jù)分組的依據(jù),假設(shè)一組輸入數(shù)據(jù)共包含N個(gè)節(jié)點(diǎn),并行環(huán)境中有n個(gè)MPI進(jìn)程,則預(yù)期每個(gè)進(jìn)程將被分配到一組共包含P個(gè)節(jié)點(diǎn)的矢量要素,P約為N/n,分配到每個(gè)進(jìn)程上的要素?cái)?shù)量不再固定。在MPI進(jìn)程數(shù)恒定為4,且算法其他特征保持一致的前提下,本文對(duì)7組不同數(shù)據(jù)量的路網(wǎng)數(shù)據(jù)分別進(jìn)行了基于要素序列分割以及點(diǎn)數(shù)分割的緩沖區(qū)分析試驗(yàn),結(jié)果在表4中列出。

表4 基于點(diǎn)數(shù)任務(wù)分解優(yōu)化的并行緩沖區(qū)算法試驗(yàn)結(jié)果Tab.4 Results of optimization derived from method of data partition by point number

表4中,TFIDs為按要素序列分割的并行算法總時(shí)間;Tpoints為按照點(diǎn)數(shù)分割的并行算法總時(shí)間;TDP為按點(diǎn)數(shù)分割數(shù)據(jù)的數(shù)據(jù)劃分過程所花費(fèi)的時(shí)間,已包含在Tpoints中。試驗(yàn)結(jié)果表明,點(diǎn)數(shù)分割方法平均以約0.43%的時(shí)間開銷代價(jià)獲得了高于10%的性能提升,因此該方法能夠提升并行矢量緩沖區(qū)算法的計(jì)算效率。

4.2 MPI進(jìn)程間“樹狀”歸并優(yōu)化

當(dāng)多個(gè)并行執(zhí)行的MPI進(jìn)程執(zhí)行完畢后,不同進(jìn)程生成的結(jié)果多邊形集合同樣需要進(jìn)行相交判斷和合并,一種直接的處理方式是將所有結(jié)果全部交由單一進(jìn)程實(shí)現(xiàn)合并和輸出,其執(zhí)行流程如圖3所示,該策略的顯著缺點(diǎn)是負(fù)責(zé)合并輸出的進(jìn)程必須等待所有進(jìn)程全部執(zhí)行完畢后才能最終開始執(zhí)行并完成合并輸出的操作。

圖3 緩沖區(qū)分析結(jié)果的單一進(jìn)程合并流程(4個(gè)MPI進(jìn)程)Fig.3 Single-process merging flow of buffer results (4 MPI processes)

結(jié)合多邊形合并過程中所采用的分治策略,本研究中為進(jìn)程間結(jié)果集合的歸并設(shè)計(jì)了一種新的策略,通過最大限度縮短進(jìn)程間等待時(shí)間來實(shí)現(xiàn)算法加速,本文稱其為MPI進(jìn)程間“樹狀”歸并優(yōu)化策略,其流程如圖4所示。

以圖4中的4個(gè)MPI進(jìn)程為例進(jìn)行說明:規(guī)定第1個(gè)進(jìn)程和第2個(gè)進(jìn)程歸并,結(jié)果由第1個(gè)進(jìn)程保持和處理,第3和第4歸并,結(jié)果由第3個(gè)進(jìn)程保持和處理,然后第1個(gè)和第3個(gè)進(jìn)程將前兩次歸并的結(jié)果再次歸并,依次類推。這樣通過為多個(gè)MPI并行進(jìn)程預(yù)先規(guī)劃出一條“樹狀”歸并路徑可降低MPI程序開發(fā)的難度。本文實(shí)現(xiàn)了具有上述結(jié)果歸并流程的并行緩沖區(qū)算法,為與單一進(jìn)程歸并模式的并行緩沖區(qū)算法進(jìn)行對(duì)比,在保持算法其他特征一致的前提下,采用7組不同數(shù)據(jù)量的路網(wǎng)數(shù)據(jù)開展了相關(guān)試驗(yàn),結(jié)果在表5中列出。

圖4 緩沖區(qū)分析結(jié)果的“樹狀”歸并合并流程(4個(gè)MPI進(jìn)程)Fig.4 Tree-like merging flow of buffer results(4 MPI processes)

表5 “樹狀”歸并優(yōu)化后的并行緩沖區(qū)分析算法試驗(yàn)結(jié)果Tab.5 Time costs of parallel buffer algorithm optimized by tree-like merge strategy between MPI processes

由表5可知,MPI進(jìn)程間結(jié)果“樹狀”歸并優(yōu)化可為并行緩沖區(qū)分析算法帶來平均約46.6%的效率提升,4個(gè)MPI進(jìn)程下的并行加速比從1.411提升至2.708,優(yōu)化效果顯著。因此,MPI進(jìn)程間多邊形集合的“樹狀”歸并方法對(duì)并行緩沖區(qū)分析算法具有明顯的優(yōu)化效果。

5 結(jié) 論

本文在描述一種可用的基于幾何部件緩沖區(qū)域合并思想的矢量緩沖區(qū)生成算法的基礎(chǔ)上,基于MPI并行編程模型實(shí)現(xiàn)了并行緩沖區(qū)生成算法,并詳細(xì)分析了可能導(dǎo)致其效率低下的兩處性能瓶頸,分別提出了優(yōu)化解決方案:針對(duì)并行任務(wù)負(fù)載均衡問題的按節(jié)點(diǎn)數(shù)量進(jìn)行并行任務(wù)分割的方法和MPI進(jìn)程間結(jié)果集合的“樹狀”歸并方法。試驗(yàn)結(jié)果表明,點(diǎn)數(shù)分割方法平均以約0.43%的時(shí)間開銷代價(jià)獲得了高于10%的性能提升;MPI進(jìn)程間結(jié)果集合的“樹狀”歸并優(yōu)化可為并行緩沖區(qū)分析算法帶來平均約46.6%的效率提升,4個(gè)MPI進(jìn)程下的并行加速比從1.411提升至2.708,優(yōu)化效果顯著。因此,基于幾何部件緩沖區(qū)域合并的矢量數(shù)據(jù)緩沖區(qū)生成算法具有一定的實(shí)用價(jià)值,兩種優(yōu)化方法能有效改善緩沖區(qū)分析算法的性能表現(xiàn),是對(duì)緩沖區(qū)分析算法進(jìn)行并行化和優(yōu)化改進(jìn)的有效途徑。

此外,MPI進(jìn)程間結(jié)果集合的歸并模式可以采用更為合理的“先完成先歸并”的自適應(yīng)方式,將有可能獲得更為優(yōu)秀的并行優(yōu)化效果,但這將導(dǎo)致編程復(fù)雜度大大提高,是下一步的研究方向。

[1] TURTONI,OPENSHAW S.High-performance Computing and Geography:Developments,Issues,and Case Studies [J].Environment and Planning:A,1998,30:1839-1856.[2] CLARKE K C.Geocomputation’s Future at the Extremes: High Performance Computing and Nanoclients[J].Parallel Computing,2003,29(10):1281-1295.

[3] GRAMA A,GUPTA A,KARYPIS G,et al.Introduction to Parallel Computing[M].Boston:Addison Wesley, 2003:85-142.

[4] WANG Jiechen,WANG Bao,HU Wei,et al.Review on Parallel Spatial Analysis Algorithms[J].Geography and Geo-Information Science,2011,27(6):1-5.(王結(jié)臣,王豹,胡瑋,等.并行空間分析算法研究進(jìn)展及評(píng)述[J].地理與地理信息科學(xué),2011,27(6):1-5.)

[5] SLOAN T M,MINETERM J,DOWERS S,et al.Partitioning of Vector-topological Data for Parallel GIS Operations: Assessment and Performance Analysis[C]∥Proceedings of Euro-Par′99 Parallel Processing,Lecture Notes in Computer Science.Delft:[s.n.],1999:691-694.

[6] MINETERM J,DOWERS S.Parallel Processing for Geographical Applications:A Layered Approach[J].Journal of Geographical Systems,1999,1(1):61-74.

[7] DARLING G J,SLOAN T M,MULHOLLAND C.The Input,Preparation and Distribution of Data for Parallel GIS Operations[C]∥Proceedings of Euro-Par 2000, Lecture Notes in Computer Science.Ischia:[s.n.],2000: 500-505.

[8] MINETER M J.A Software Framework to Create Vectortopology in Parallel GIS Operations[J].International Journal of Geographical Information Science,2003,17 (3):203-222.

[9] WU Hehai.Problem of Buffer Zone Construction in GIS[J].Journalof Wuhan Technical University of Surveying and Mapping,1997,22(4):358-366.(毋河海.關(guān)于GIS緩沖區(qū)的建立問題[J].武漢測(cè)繪科技大學(xué)學(xué)報(bào),1997,22(4): 358-366.)

[10] ESRI.Buffer-GIS Dictionary[EB/OL].[2013-03-01].http:∥support.esri.com/en/knowledgebase/GISDictionary/term/ buffer.

[11] ZALIK B,ZADRAVEC M,CLAPWORTHY G.Construction of a Non-symmetric Geometric Buffer from a Set of Linesegments[J].Computers&Geosciences,2003,29(1): 53-63.

[12] BHATIAS,VIRAV,CHOKSI D,et al.An Algorithm for Generating Geometric Buffers for Vector Feature Layers[J].Geo-spatial Information Science,2013,16 (2):130-138.

[13] WU Huayi,GONG Jianya,LI Deren.Buffer Curve and Buffer Generation Algorithm in Aid of Edge-constrained Triangle Network[J].Acta Geodaetica et Cartograohica Sinica,1999,28(4):356-359.(吳華意,龔健雅,李德仁.緩沖曲線和邊約束三角網(wǎng)輔助的緩沖區(qū)生成算法[J].測(cè)繪學(xué)報(bào),1999,28(4):356-359.)

[14] ZHU Huang,AI Tinghua,WANG Hong.The Buffer Construction of Line Object Based on the Geometric Scan Idea[J].Acta Geodaetica et Cartographica Sinica,2006, 35(2):171-176.(朱熀,艾廷華,王洪.基于條帶掃描思想的線目標(biāo)緩沖區(qū)快速構(gòu)建[J].測(cè)繪學(xué)報(bào),2006,35 (2):171-176.)

[15] LI Ke,DU Lin.An Algorithm of Buffer Zones Based on Algorithm of Dilation[J].Journal of Institute of Surveying and Mapping,2005,22(3):229-231.(李科,杜林.基于膨脹算法的緩沖區(qū)分析的設(shè)計(jì)與實(shí)現(xiàn)[J].測(cè)繪學(xué)院學(xué)報(bào), 2005,22(3):229-231.)

[16] YAO Yiqiang,GAO Jinsong,MENG Lingkui,et al.Parallel Computing of Buffer Analysis Based on Grid Computing [J].Geospatial Information,2007,5(1):98-101.(姚藝強(qiáng),高勁松,孟令奎,等.網(wǎng)格環(huán)境下緩沖區(qū)分析的并行計(jì)算[J].地理空間信息,2007,5(1):98-101.)

[17] VATTIB R.A Generic Solution to Polygon Clipping[J].Communications of the ACM,1992,35(7):56-63.

[18] MURTA A.A Generic Polygon Clipping Library[EB/OL].[2012-12-20].http:∥www.cs.man.ac.uk/～toby/alan/ software/gpc.html.

[19] GREINER G,HORMAN N K.Efficient Clipping of Arbitrary Polygons[J].ACM Transactions on Graphics,1998,17 (2):71-83.

[20] SUTHERLAND I E,HODGMAN G W.Reentrant Polygon Clipping[J].Communications of the ACM,1974,17(1): 32-42.

[21] WEILER K,ATHERTON P.Hidden Surface Removal Using Polygon Area Sorting[C]∥Proceedings of the SIGGRAPH’77.New York:ACM Press,1977:214-222.

[22] GUTTMAN A.R-Trees:A Dynamic Index Structure for Spatial Searching[C]∥Proceedings of ACM SIGMOD Conference on Management of Data.New York:ACM Press,1984:47-57.

(責(zé)任編輯:宋啟凡)

Research on a Buffer Algorithm Based on Region-merging of Buffered Geometry Components and Its Parallel Optimization

FAN Junfu1,2,3,MA Ting2,ZHOU Chenghu2,JI Min4,ZHOU Yuke2,XU Tao2,3
1.School of Architectural Engineering,Shandong University of Technology,Zibo 255049,China;2.State Key Laboratory of Resources and Environmental Information System,Institute of Geographic and Nature Resources Research, Chinese Academy of Sciences,Beijing 100101,China;3.University of Chinese Academy of Sciences,Beijing 100049,China;4.College of Geomatics,Shandong University of Science and Technology,Qingdao 266510,China

The double-sided parallel line method and the geometry rasterization-based dilation method have been extensively used for buffer generation in spatial analysis.The former involves a series of complex numerical operations and may not be suitable for parallelized computation;the latter inevitably introduces precision problems and computation complexity.A parallel buffer construction algorithm was proposed based on region-merging of buffered geometry components in association with the message passing interface(MPI)parallel programming model.Several optimization strategies were studied for the parallel buffer algorithm.The performances of both serial and parallel buffer algorithms were comparably analyzed.Three performance bottlenecks which significantly impact the algorithm efficiency were identified:area merging operation,task load balance strategy and MPIinter-process results merging methods.Corresponding optimization approaches involving tree-like area and inter-process results merging and the parallel task partition based on vertex number oriented parallel task partition strategy were suggested to overcome these bottlenecks.Several experiments were carried out to examine the performance efficiency of the optimized parallel algorithm.The estimation results suggested that our method could provide high performance and processing ability for buffer construction in a parallel environment.Our method could provide insights into the parallelization of spatial analysis algorithm.

parallel algorithm;buffer;MPI;task partition;tree-like merging

FAN Junfu(1985—),male,PhD candidate,majors in the high-performance geo-spatial analysis algorithms.

P208

A

1001-1595(2014)09-0969-07

國(guó)家科技支撐計(jì)劃(2011BAH06B03;2011BAH24B10);中國(guó)科學(xué)院重點(diǎn)部署項(xiàng)目(KZZD-EW-07)

2013-08-08

范俊甫(1985—),男,博士生,研究方向?yàn)楦咝阅芸臻g分析算法。

E-mail:fanjf＠lreis.ac.cn

FAN Junfu,MA Ting,ZHOU Chenghu,et al.Research on a Buffer Algorithm Based on Region-merging of Buffered Geometry Components and Its Parallel Optimization[J].Acta Geodaetica et Cartographica Sinica,2014,43(9):969-975.(范俊甫,馬廷,周成虎,等.幾何部件緩沖區(qū)域合并的Buffer算法及其并行優(yōu)化方法[J].測(cè)繪學(xué)報(bào),2014,43(9):969-975.)

10.13485/j.cnki.11-2089.2014.0122

修回日期:2014-05-06