沈 婕，郭立帥，朱 偉，顧乃杰

1.南京師范大學(xué) 虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210046；2.南京師范大學(xué) 地理科學(xué)學(xué)院，江蘇 南京 210046；3.中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230027

1 引 言

隨著網(wǎng)絡(luò)地圖技術(shù)的發(fā)展及地圖應(yīng)急服務(wù)的需要，對(duì)實(shí)時(shí)在線多尺度地理信息服務(wù)的需求更加迫切，為了解決海量地理數(shù)據(jù)實(shí)時(shí)動(dòng)態(tài)的尺度變換，地圖綜合的效率需要進(jìn)一步提高。針對(duì)地圖綜合效率增益方法，學(xué)者們提出了建立空間數(shù)據(jù)索引［1］、構(gòu)建多尺度空間數(shù)據(jù)庫(kù)之間的鏈接［2－3］、采用漸進(jìn)式綜合策略等方法［4－5］，這些方法雖然能在一定程度上提高地圖綜合的執(zhí)行效率，但是傳統(tǒng)的硬件串行處理方式已經(jīng)達(dá)到了瓶頸。近年來(lái)，基于并行體系結(jié)構(gòu)的硬件資源層出不窮，并行軟件也不斷發(fā)展。在實(shí)際的并行機(jī)上設(shè)計(jì)并行程序時(shí)，絕大部分采用擴(kuò)展Fortran和C語(yǔ)言的辦法，目前主要有3種擴(kuò)展的辦法：庫(kù)函數(shù)法（MPI、PVM、Cray Craft）、新 語(yǔ) 言 結(jié) 構(gòu) 法（Fortran90、Cray Craft）和編譯制導(dǎo)法 （HPF、Cray Craft）。MPI是消息傳遞模型的一種，便于將串行程序擴(kuò)展為基于消息傳遞模型的并行程序，它遵守所有對(duì)庫(kù)函數(shù)／過程的調(diào)用規(guī)則，是為開發(fā)基于消息傳遞模型的并行程序而制定的工業(yè)標(biāo)準(zhǔn)，其目的是提高并行程序的可移植性和易用性，用戶必須顯式地通過發(fā)送和接受消息來(lái)實(shí)現(xiàn)處理器之間的數(shù)據(jù)交換。MPI具有移植性好、功能強(qiáng)大、效率高等多種優(yōu)點(diǎn)，幾乎所有的并行計(jì)算機(jī)廠商都提供對(duì)它的支持。本文探討MPI環(huán)境下等高線簡(jiǎn)化的并行計(jì)算問題。

并行計(jì)算在地學(xué)中的應(yīng)用主要有基于圖形處理器（GPU）的通用計(jì)算，如文獻(xiàn)［6］提出基于多叉樹搜索的并行蟻群算法；文獻(xiàn)［7］提出基于GPGPU的CUDA架構(gòu)快速影像匹配并行算法。此外，文獻(xiàn)［8］研究了OPEN MP并行計(jì)算在衛(wèi)星重力數(shù)據(jù)處理中的應(yīng)用，總之，并行計(jì)算在地圖綜合中的應(yīng)用還較少。線狀要素在地圖要素的圖形表達(dá)和GIS分析中發(fā)揮著重要的作用，線要素綜合也是地圖綜合中最重要的方面。等高線是普通地圖、數(shù)字線劃圖中重要的表達(dá)要素，面向大范圍場(chǎng)景下不同尺度的等高線實(shí)時(shí)表達(dá)，對(duì)于等高線綜合算法的效率提出了要求，本文選擇等高線作為地圖綜合并行計(jì)算的研究數(shù)據(jù)類型。簡(jiǎn)化是地圖綜合中最常用的操作，針對(duì)簡(jiǎn)化算法的研究已相對(duì)成熟，算法多達(dá)數(shù)十種，本文擬選取幾種典型的簡(jiǎn)化算法，采用不同數(shù)據(jù)量的等高線數(shù)據(jù)，基于MPI的不同并行計(jì)算方案，實(shí)現(xiàn)其簡(jiǎn)化并行計(jì)算?；诓⑿杏?jì)算效率的比較與分析，探討并行計(jì)算中不同簡(jiǎn)化算法對(duì)數(shù)據(jù)量、計(jì)算節(jié)點(diǎn)數(shù)、通信方式等的適宜性。通過這一研究，為基于MPI的等高線或其他要素地圖綜合及其他地學(xué)高性能計(jì)算研究提供借鑒。

2 線要素簡(jiǎn)化算法效率分析

算法時(shí)間復(fù)雜度是指算法的時(shí)間耗費(fèi)，是算法中所有語(yǔ)句的頻度之和，它是算法所求解問題規(guī)模n的函數(shù)，用T（n）表示。為了準(zhǔn)確地度量算法效率，需要解決兩個(gè)問題：一個(gè)是算法運(yùn)算次數(shù)與問題規(guī)模的關(guān)系；另一個(gè)是問題規(guī)模同為n的不同輸入實(shí)例，即考慮數(shù)據(jù)分布特征時(shí)，應(yīng)該怎樣計(jì)算其基本語(yǔ)句的運(yùn)算次數(shù)。本文在分析算法時(shí)間復(fù)雜度時(shí)，先寫出算法的偽代碼，然后找出其基本語(yǔ)句與問題規(guī)模的關(guān)系，進(jìn)而得到算法的時(shí)間復(fù)雜度。以Douglas－Peucker算法為例，進(jìn)行闡述。

2.1 Douglas－Peucker算法的思想

Douglas－Peucker算法的基本思想是：先擬定一個(gè)閾值D以控制簡(jiǎn)化的程度，生成一條連接矢量折線首尾節(jié)點(diǎn)的直線段，求出線上所有頂點(diǎn)到該直線段的垂直距離，并找到最大距離dmax，比較dmax與閾值D，若dmax＜D，則舍去折線上所有中間點(diǎn)；若dmax＞D，則以dmax對(duì)應(yīng)的點(diǎn)為界，把折線分為兩部分，再對(duì)這兩部分使用上述方法，直到始點(diǎn)和終點(diǎn)之間無(wú)點(diǎn)為止。

2.2 Douglas－Peucker算法的偽代碼

下面是使用遞歸實(shí)現(xiàn)DP算法的偽代碼，D為距離閾值，（i、j為線段的起始點(diǎn)與結(jié)束點(diǎn)）：① 尋找到線段pipj距離最遠(yuǎn)的點(diǎn)pk；② 判斷pk到pipj線段的距離與D的關(guān)系，如果大于D執(zhí)行第③ 步，否則執(zhí)行第④ 步；③ 將線段pipj分為pi到pk與pk到pj兩部分，分別使用Douglas－Peucker算法簡(jiǎn)化；④ 返回簡(jiǎn)化結(jié)果。

2.3 Douglas－Peucker算法的時(shí)間復(fù)雜度分析

上述代碼中第1步的時(shí)間復(fù)雜度為O（n），而整個(gè)算法是通過遞歸實(shí)現(xiàn)的，假設(shè)D＜dmax，線段的第m個(gè)點(diǎn)將其一分為二，m＞1時(shí)，算法執(zhí)行時(shí)間T（n）＝T（m）＋T（n－m＋1）＋O（n），在一定的數(shù)據(jù)特征下，可能會(huì)使得m＝n－m＋1，此時(shí)T（n）＝2T（n／2）＋O（n），由主定理［9］可得T（n）＝O（nlogn）；m＝1時(shí)，T（n）＝T（1）＋T（n－1）＋O（n），算法的時(shí)間復(fù)雜度為O（n2）。假設(shè)D＞dmax，算法的時(shí)間復(fù)雜度為O（n）。

2.4 Douglas－Peucker算法的約束參數(shù)對(duì)其效率的影響分析

Douglas－Peucker算法的約束參數(shù)為D（距離閾值），在Ifdistance（pk，pi，pj）＞D這一計(jì)算過程中，如果D永大于distance（pk，pi，pj），那么算法的執(zhí)行次數(shù)為n（問題規(guī)模），此時(shí)算法的時(shí)間復(fù)雜度為O（n）；如果D永小于distance（pk，pi，pj）就會(huì)導(dǎo)致m＝1，算法的時(shí)間復(fù)雜度為O（n2）。

本文依據(jù)上述方法分析了常用的8種線簡(jiǎn)化算法的時(shí)間復(fù)雜度及其約束參數(shù)對(duì)算法效率的影響，發(fā)現(xiàn)地圖綜合算法的效率影響因素不僅依賴問題規(guī)模n，還依賴于其約束參數(shù)［10］。約束參數(shù)對(duì)算法效率的影響與算法時(shí)間復(fù)雜度分析結(jié)果在量級(jí)上是一致的，這是地圖綜合算法時(shí)間復(fù)雜度分析的獨(dú)有特點(diǎn)。為了探究不同簡(jiǎn)化算法并行計(jì)算適宜性，本研究根據(jù)簡(jiǎn)化算法的時(shí)間復(fù)雜度將其分為線性與非線性兩類，擬選擇線性算法Li－Openshaw算法與Circle算法，非線性算法Douglas－Peucker算法與漸進(jìn)式簡(jiǎn)化算法進(jìn)行并行計(jì)算試驗(yàn)。綜上所述，8種簡(jiǎn)化算法分析結(jié)果如表1所示。

表1 考慮約束參數(shù)影響的簡(jiǎn)化算法時(shí)間復(fù)雜度Tab.1 Time complexity of simplifying algorithms considering the effect of constraints

3 基于MPI的等高線簡(jiǎn)化并行計(jì)算關(guān)鍵問題

主從模式和對(duì)等模式是MPI的兩種基本并行計(jì)算模式［11］。主從模式中，主節(jié)點(diǎn)管理其他計(jì)算節(jié)點(diǎn)［12］；對(duì)等模式中，各個(gè)節(jié)點(diǎn)地位相同。本文提出的等高線簡(jiǎn)化并行計(jì)算方法以數(shù)據(jù)劃分為基礎(chǔ)，更適合主從模式，主節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)劃分、發(fā)送與合并，計(jì)算節(jié)點(diǎn)負(fù)責(zé)等高線的簡(jiǎn)化計(jì)算。基于MPI的等高線簡(jiǎn)化并行計(jì)算由4個(gè)過程組成：數(shù)據(jù)劃分、通信、計(jì)算和數(shù)據(jù)合并，其流程如圖1所示。

圖1 基于MPI的等高線簡(jiǎn)化并行計(jì)算流程圖Fig.1 Flow chart of contour simplification parallel computing based on MPI

3.1 數(shù)據(jù)劃分與合并

已有的面向空間數(shù)據(jù)處理的并行計(jì)算方法大多采用規(guī)則格網(wǎng)劃分或條帶劃分［13－14］，由于地圖綜合以處理矢量數(shù)據(jù)為主，并要求綜合前后保持?jǐn)?shù)據(jù)的結(jié)構(gòu)特征與拓?fù)涮卣?，格網(wǎng)劃分和條帶劃分將破壞等高線這種閉合曲線的空間關(guān)系，數(shù)據(jù)合并時(shí)開銷太大，這種簡(jiǎn)單劃分方法不適合等高線數(shù)據(jù)。因此，基于矢量數(shù)據(jù)劃分的并行計(jì)算，數(shù)據(jù)劃分和合并必須統(tǒng)籌考慮負(fù)載均衡與數(shù)據(jù)分布特征對(duì)計(jì)算效率的影響。本文提出基于高程帶的數(shù)據(jù)劃分方法，基本思想是先根據(jù)總數(shù)據(jù)量及計(jì)算節(jié)點(diǎn)數(shù)目確定每個(gè)節(jié)點(diǎn)的數(shù)據(jù)量閾值，將高程相同的等高線合并為一個(gè)整體，作為劃分基本單元，然后比較其與各節(jié)點(diǎn)數(shù)據(jù)量閾值的關(guān)系，將單獨(dú)或相鄰的幾個(gè)高程帶劃分成獨(dú)立的數(shù)據(jù)塊，并且沒有打斷原有等高線，不同計(jì)算節(jié)點(diǎn)運(yùn)算后返回的等高線仍然是閉合曲線，這種劃分方法既保證了計(jì)算節(jié)點(diǎn)的負(fù)載均衡，又降低了數(shù)據(jù)合并的開銷。

3.2 通信方式

MPI提供了集合通信和點(diǎn)對(duì)點(diǎn)通信兩種方式［15］，集合通信要求傳輸數(shù)據(jù)量相同，但每條等高線數(shù)據(jù)量不同，因此本研究采用點(diǎn)對(duì)點(diǎn)通信。點(diǎn)對(duì)點(diǎn)通信可分為阻塞和非阻塞通信兩種類型［16］。阻塞通信發(fā)送目標(biāo)進(jìn)程立刻需要的數(shù)據(jù)，必須等到接收數(shù)據(jù)完成才能執(zhí)行下一步操作，非阻塞通信可以一邊發(fā)送數(shù)據(jù)一邊執(zhí)行計(jì)算，將計(jì)算與通信重疊。

本研究將比較阻塞和非阻塞通信對(duì)等高線簡(jiǎn)化并行計(jì)算效率的影響。等高線簡(jiǎn)化并行計(jì)算在這兩種通信方式下的流程如圖2所示，阻塞通信方式下，主節(jié)點(diǎn)依次發(fā)送等高線數(shù)據(jù)到各計(jì)算節(jié)點(diǎn)中，計(jì)算節(jié)點(diǎn)在接收數(shù)據(jù)完成后開始執(zhí)行簡(jiǎn)化計(jì)算，如圖2（a）所示。非阻塞通信方式下，節(jié)點(diǎn)每簡(jiǎn)化完一條等高線就立即發(fā)送，發(fā)送操作隨即返回，繼續(xù)處理下一條等高線，進(jìn)而將計(jì)算與通信重疊，如圖2（b）所示。

圖2 阻塞和非阻塞通信方式下等高線簡(jiǎn)化并行計(jì)算過程Fig.2 Contour simplification parallel computing process under blocking and non－blocking communication

3.3 計(jì)算過程

計(jì)算過程的執(zhí)行時(shí)間是所有計(jì)算節(jié)點(diǎn)簡(jiǎn)化計(jì)算執(zhí)行時(shí)間最長(zhǎng)的節(jié)點(diǎn)所用的計(jì)算時(shí)間。影響計(jì)算過程效率主要有3個(gè)因素：數(shù)據(jù)負(fù)載量、簡(jiǎn)化算法效率和處理任務(wù)提交順序。其中簡(jiǎn)化算法與數(shù)據(jù)負(fù)載量是確定因素，為了提高并行計(jì)算效率，應(yīng)該改進(jìn)處理任務(wù)的提交順序［17］。本研究根據(jù)劃分后數(shù)據(jù)塊的數(shù)據(jù)量進(jìn)行降序排序，然后依次發(fā)送，以達(dá)到數(shù)據(jù)量大的任務(wù)首先執(zhí)行，進(jìn)而縮短整個(gè)并行計(jì)算過程的處理時(shí)間。

4 試 驗(yàn)

本試驗(yàn)是在6臺(tái)計(jì)算機(jī)組成的小型集群系統(tǒng)中進(jìn)行，每臺(tái)計(jì)算機(jī)的配置為：Inter（R）Core（TM）Quad CPUQ8200＠2.33GHz四核，2GB內(nèi)存。編程環(huán)境為 Visual Studio 2010、GDAL1.4.2和MPICH 1.2.1。試驗(yàn)中使用的等高線數(shù)據(jù)來(lái)源于1∶100萬(wàn)中國(guó)陸地區(qū)域等高線數(shù)據(jù)，為了便于發(fā)現(xiàn)等高線簡(jiǎn)化并行計(jì)算效率與數(shù)據(jù)量的變化規(guī)律，對(duì)原始等高線數(shù)據(jù)進(jìn)行了簡(jiǎn)化和刪除處理，得到中國(guó)陸地區(qū)域的4份數(shù)據(jù)量基本呈等差分布的數(shù)據(jù)，測(cè)試數(shù)據(jù)的數(shù)據(jù)量如表2所示，均為shapefile格式。這4份數(shù)據(jù)覆蓋范圍是一致的，但是等高線數(shù)量、每條等高線中點(diǎn)的數(shù)量不同，由于全國(guó)范圍的等高線數(shù)據(jù)顯示過于密集，因此以測(cè)試數(shù)據(jù)4為示例，放大了測(cè)試數(shù)據(jù)4中的某一小塊區(qū)域，如圖3所示。

表2 測(cè)試數(shù)據(jù)的數(shù)據(jù)量Tab.2 The volume of the test data

4.1 約束參數(shù)及數(shù)據(jù)準(zhǔn)備

由第2節(jié)討論得知，算法的約束參數(shù)對(duì)算法效率有影響，本試驗(yàn)中等高線原始比例尺為1∶1 000 000，目標(biāo)比例尺為1∶4 000 000，選取等高距為500m，根據(jù)本試驗(yàn)的數(shù)據(jù)特征和綜合前后的比例尺，試驗(yàn)中各算法的約束參數(shù)計(jì)算公式如下（O＿Scale為源數(shù)據(jù)比例尺分母，P＿Scale為目標(biāo)比例尺分母，SVO為最小可視目標(biāo)的直徑）。

圖3 測(cè)試數(shù)據(jù)4的部分放大數(shù)據(jù)Fig.3 Test data 4and the enlarge of part data

漸進(jìn)式化簡(jiǎn)算法：areaTolerence＝0.000 4×0.000 6×pow（P＿Scale，2）／2。

Li－Openshaw 算 法：R＝ （1－O＿Scale／P＿Scale）×SVO×P＿Scale。

Douglas－Peucker算法：D＝0.000 2×P＿Scale。

圓算法：R＝length／（num－1）／2（length為線長(zhǎng)度，num為線中點(diǎn)的個(gè)數(shù)）。

本試驗(yàn)中，將在1、2、4、6個(gè)計(jì)算節(jié)點(diǎn)上執(zhí)行等高線簡(jiǎn)化并行計(jì)算，為了保證不同計(jì)算節(jié)點(diǎn)上負(fù)載均衡性，基于高程帶數(shù)據(jù)劃分思想，將等高線數(shù)據(jù)分配到不同計(jì)算節(jié)點(diǎn)上，如表3所示。

表3 參與計(jì)算的不同節(jié)點(diǎn)上高程帶劃分Tab.3 Elevation zones divided on different nodes involved in the calculation m

4.2 試驗(yàn)1：簡(jiǎn)化算法在串行環(huán)境下效率分析

在串行環(huán)境下，Douglas－Peucker算法和漸進(jìn)式簡(jiǎn)化算法的執(zhí)行時(shí)間與算法的迭代次數(shù)有關(guān)。雖然Li－OpenShaw和Circle算法都是線性算法，但其原理不同，Li－OpenShaw算法會(huì)產(chǎn)生新的數(shù)據(jù)點(diǎn)，而Circle算法是刪除數(shù)據(jù)中原始的點(diǎn)，其基本語(yǔ)句的復(fù)雜度不同。4個(gè)簡(jiǎn)化算法的串行執(zhí)行時(shí)間如圖4所示。

圖4 簡(jiǎn)化算法串行執(zhí)行時(shí)間Fig.4 Serial execution time of simplified algorithm

在當(dāng)前數(shù)據(jù)分布特征下，Circle算法執(zhí)行效率最高；Douglas－Peucker算法的效率較低；漸進(jìn)式簡(jiǎn)化算法在數(shù)據(jù)1時(shí)效率最高，其余數(shù)據(jù)情況下，與 Li－OpenShaw 算法效率相近［18］。通 過分析，可得到以下結(jié)論：

（1）算法時(shí)間復(fù)雜度量級(jí)相同，算法的約束參數(shù)、數(shù)據(jù)空間分布特征相近時(shí)，算法效率依賴于算法基本語(yǔ)句的復(fù)雜度。

（2）算法時(shí)間復(fù)雜度是度量算法在串行環(huán)境下效率的量級(jí)，但并不能代表算法執(zhí)行時(shí)的效率，特別是綜合算法，影響其執(zhí)行效率的還有算法的約束參數(shù)、數(shù)據(jù)空間分布特征等。

4.3 試驗(yàn)2：阻塞通信方式下簡(jiǎn)化算法的并行計(jì)算

阻塞通信方式的并行計(jì)算是最容易實(shí)現(xiàn)的并行計(jì)算方法。對(duì)于等高線簡(jiǎn)化并行計(jì)算，主節(jié)點(diǎn)依次將等高線數(shù)據(jù)發(fā)送到各計(jì)算節(jié)點(diǎn)，各個(gè)計(jì)算節(jié)點(diǎn)執(zhí)行簡(jiǎn)化操作，所有節(jié)點(diǎn)都處理完成之后按照阻塞通信方式將處理結(jié)果返回給主節(jié)點(diǎn)。測(cè)試數(shù)據(jù)的平均阻塞次數(shù)如表4所示，簡(jiǎn)化算法的加速比如圖5所示。

表4 測(cè)試數(shù)據(jù)阻塞次數(shù)統(tǒng)計(jì)表Tab.4 The blocked count of the test data

分析得到以下結(jié)論：

（1）計(jì)算節(jié)點(diǎn)數(shù)為2時(shí)，只有一個(gè)節(jié)點(diǎn)通信，相當(dāng)于無(wú)阻塞，算法效率高。

（2）隨著數(shù)據(jù)量和計(jì)算節(jié)點(diǎn)的增加，阻塞的次數(shù)也相應(yīng)的增加，算法等待的時(shí)間增加，算法效率降低。

圖5 阻塞通信方式簡(jiǎn)化算法加速比Fig.5 The speedup of the simplified algorithms under the blocking communication

4.4 試驗(yàn)3：不同通信方式下簡(jiǎn)化算法的并行效率分析

解決因數(shù)據(jù)量增加而阻塞通信次數(shù)增加的辦法是使用非阻塞通信，它不必等到通信操作完全完成便可返回。本次試驗(yàn)比較了Douglas－Peucker算法和漸進(jìn)式簡(jiǎn)化算法在不同通信方式下處理數(shù)據(jù)3和數(shù)據(jù)4的效率，如圖6所示。

圖6 不同通信方式下Douglas－Peucker算法和漸進(jìn)式簡(jiǎn)化算法的加速比Fig.6 Speedup of Douglas－Peucker and progessive simplification algorithm under different communications

綜合分析可得以下結(jié)論：

（1）算法并行計(jì)算效率不會(huì)隨著節(jié)點(diǎn)數(shù)增加而一直提高。測(cè)試數(shù)據(jù)為數(shù)據(jù)4時(shí)，兩個(gè)簡(jiǎn)化算法的加速比峰值都出現(xiàn)于節(jié)點(diǎn)數(shù)為4的情況下，說明此數(shù)據(jù)量下，使用4個(gè)節(jié)點(diǎn)并行計(jì)算效率最高。

（2）由圖5可知，在阻塞通信方式下，隨著節(jié)點(diǎn)數(shù)的增加，簡(jiǎn)化算法的效率在降低，甚至可能低于串行的效率。由圖6可知，在非阻塞通信方式下，Douglas－Peucker算法和漸進(jìn)式簡(jiǎn)化算法的加速比明顯高于阻塞通信方式下，算法執(zhí)行效率更高。在當(dāng)前數(shù)據(jù)分布特征下，對(duì)于本文所選簡(jiǎn)化算法，非阻塞通信方式優(yōu)于阻塞通信方式，更能提高簡(jiǎn)化算法并行計(jì)算的效率。

4.5 試驗(yàn)4：簡(jiǎn)化結(jié)果及其并行適宜性分析

本試驗(yàn)選擇了4種數(shù)據(jù)量的試驗(yàn)數(shù)據(jù)，其中數(shù)據(jù)4中的局部數(shù)據(jù)基于不同簡(jiǎn)化算法執(zhí)行并行計(jì)算后等高線如圖7所示，其中參與計(jì)算的節(jié)點(diǎn)數(shù)為兩個(gè)，黑色細(xì)線為簡(jiǎn)化前的等高線，紅色和黑色粗線為在不同節(jié)點(diǎn)上的簡(jiǎn)化結(jié)果。

圖7 數(shù)據(jù)4的局部數(shù)據(jù)在不同算法條件下的簡(jiǎn)化結(jié)果（粗線）Fig.7 Simplification results of data 4under the conditions of different algorithms（thick line）

此外，由試驗(yàn)2和試驗(yàn)3可知，非阻塞通信方式簡(jiǎn)化算法的并行效率明顯高于阻塞通信方式，因此本試驗(yàn)分析簡(jiǎn)化算法在非阻塞通信方式下的并行適宜性，圖8是4個(gè)簡(jiǎn)化算法在非阻塞通信方式下并行處理測(cè)試數(shù)據(jù)的加速比。通過對(duì)圖8結(jié)果進(jìn)行分析可以得出以下結(jié)論：

（1）算法并行化之后，其效率的變化是不確定的，串行效率高的算法并行效率不一定高。由圖4與圖8可知，在處理相同數(shù)據(jù)時(shí)，與其他算法相比，Douglas－Peucker算法的串行效率最低，但其并行計(jì)算加速比最大，原因是在通信環(huán)境、節(jié)點(diǎn)數(shù)、數(shù)據(jù)量等因素都相同時(shí)，并行計(jì)算的通信時(shí)間都相同，算法并行后的加速比與其串行執(zhí)行時(shí)間成正比，串行執(zhí)行時(shí)間越長(zhǎng)加速比越大。Circle算法和Li－Openshaw算法并行效率不隨節(jié)點(diǎn)數(shù)目增加而增加，隨著數(shù)據(jù)分塊數(shù)目和數(shù)據(jù)量的增加，通信開銷占用的比例增加，導(dǎo)致效率降低。

圖8 非阻塞通信方式下簡(jiǎn)化算法加速比Fig.8 Speedup of the simplification algorithm under non－blocking communication

（2）算法約束參數(shù)與數(shù)據(jù)的空間分布特征共同影響算法的并行計(jì)算過程，導(dǎo)致漸進(jìn)式算法加速比呈不規(guī)律變化。究其原因主要是數(shù)據(jù)分配方法雖然保證了計(jì)算節(jié)點(diǎn)上的負(fù)載均衡性，但是不同計(jì)算節(jié)點(diǎn)上的數(shù)據(jù)彎曲特征、轉(zhuǎn)折點(diǎn)數(shù)量等對(duì)漸進(jìn)式簡(jiǎn)化的約束參數(shù)產(chǎn)生了影響，導(dǎo)致不同計(jì)算節(jié)點(diǎn)上的計(jì)算任務(wù)不均衡，進(jìn)而導(dǎo)致算法加速比的不均衡。

綜上所述，簡(jiǎn)化算法并行效率受計(jì)算過程與通信過程兩方面影響，在分析簡(jiǎn)化算法的并行計(jì)算適宜性時(shí)，應(yīng)該綜合考慮算法的時(shí)間復(fù)雜度、約束參數(shù)、數(shù)據(jù)量、數(shù)據(jù)分布特征以及計(jì)算環(huán)境等多個(gè)因素。

5 結(jié) 論

當(dāng)前多核、集群等硬件資源不斷發(fā)展，并行計(jì)算在地圖綜合乃至地學(xué)計(jì)算過程中正逐漸得到重視。本文基于MPI進(jìn)行等高線簡(jiǎn)化算法的并行計(jì)算，探討了MPI環(huán)境下等高線并行計(jì)算需要解決的關(guān)鍵問題。在對(duì)簡(jiǎn)化算法效率分析的基礎(chǔ)上，選取4種典型的簡(jiǎn)化算法，利用數(shù)據(jù)量呈等差分布的等高線數(shù)據(jù)進(jìn)行等高線簡(jiǎn)化并行試驗(yàn)。試驗(yàn)表明，算法并行計(jì)算效率并不總是隨著節(jié)點(diǎn)數(shù)增加而提高，尤其是串行算法效率很高的算法；基于MPI的非阻塞通信方式相對(duì)于阻塞通信方式可以提高并行計(jì)算效率；不同的簡(jiǎn)化算法，其并行計(jì)算的最高加速比呈現(xiàn)于不同數(shù)量的計(jì)算節(jié)點(diǎn)上。

目前本研究提出的方法只是基于MPI的等高線簡(jiǎn)化并行計(jì)算，數(shù)據(jù)劃分方法采用的是基于高程帶的劃分方法，還沒有達(dá)到很好的負(fù)載均衡。而基于Linux的Pthread多線程模式、基于OpenMP與MPI的混合模式、MPI運(yùn)行時(shí)參數(shù)優(yōu)化、MPI進(jìn)程擺放優(yōu)化以及通信方式的優(yōu)化對(duì)于地圖綜合并行計(jì)算的性能優(yōu)化還有待于做進(jìn)一步的深入研究。動(dòng)態(tài)負(fù)載平衡、面向計(jì)算任務(wù)分解的并行計(jì)算、不同的并行計(jì)算環(huán)境等問題將是地圖綜合高性能計(jì)算所面臨的新問題，將在今后的研究中得到更深入的探討。

［1］ OOSTEROM V P，VRIES M D，MEIJERS M.Vario－scale Data Server in a Web Service Context［C］∥Proceedings of Workshop of the ICA Commission on Map Generalization and Multiple Representation.Vancouver：ICA，2006：1－14.

［2］ WANG Yanhui，LI Xiaojuan，GONG Huili.The Fundamental Issues of Multi－Scale Representation in the Geographic Elements［J］.Science in China，2006，36（z1）：38－44.（王艷慧，李小娟，宮輝力.地理要素多尺度表達(dá)的基本問題［J］.中國(guó)科學(xué)：E輯，2006，36（z1）：38－44.）

［3］ CECCONI A.Integration of Cartographic Generalization and Multi－scale Databases for Enhanced Web Mapping［D］.Zurich：Zurich University，2003.

［4］ GUO Qingsheng，HUANG Yuanlin，ZHENG Chunyan，et al.Spatial Reasoning and Incremental Map Generalization［M］.Wuhan：Wuhan University Press，2007：260－290.（郭慶勝，黃遠(yuǎn)林，鄭春燕，等.空間推理與漸進(jìn)式地圖綜合［M］.武漢：武漢大學(xué)出版社，2007：260－290.）

［5］ YANG B，PURVES R，WEIBEL R.Efficient Transmission of Vector Data over the Internet［J］.International Journal of Geographical Information Science，2007，21（1－2）：215－237.

［6］ ZHAO Yuan，ZHANG Xinchang，KANG Tingjun.A Parallel Ant Colony Optimization Algorithm for Site Location［J］.Acta Geodaetica et Cartographica Sinica，2010，39（3）：322－327.（趙元，張新長(zhǎng)，康停軍.并行蟻群算法及其在區(qū)位選址中的應(yīng)用［J］.測(cè)繪學(xué)報(bào)，2010，39（3）：322－327.）

［7］ XIAO Han，ZHANG Zuxun.Parallel Image Matching Algorithm Based on GPGPU［J］.Acta Geodaetica et Cartographica Sinica，2010，39（1）：46－51.（肖漢，張祖勛.基于 GP GPU的并行影像匹配算法［J］.測(cè)繪學(xué)報(bào)，2010，39（1）：46－51.）

［8］ ZOU Xiancai，LI Jiancheng，WANG Haihong，et al.Application of Parallel Computing with OpenMP in Data Processing for Satellite Gravity［J］.Acta Geodaetica et Cartographica Sinica，2010，39（6）：636－641.（鄒賢才，李建成，汪海洪，等.OpenMP并行計(jì)算在衛(wèi)星重力數(shù)據(jù)處理中的應(yīng)用［J］.測(cè)繪學(xué)報(bào)，2010，39（6）：636－641.）

［9］ QU Wanling，LIU Tian，WANG Hanpin，et al.Design and Analysis of Algorithms［M］.Beijing：Tsinghua University Press，2011：18－20.（屈婉玲，劉田，王捍貧，等.算法設(shè)計(jì)與分析［M］.北京：清華大學(xué)出版社，2011：18－20.）

［10］ ZHU Kunpeng.Quality Evaluation of Linear Features＇Simplification Algorithms［D］.Zhengzhou：Information Engineering University，2007.（朱鯤鵬.線要素化簡(jiǎn)質(zhì)量評(píng)估［D］.鄭州：信息工程大學(xué)，2007.）

［11］ CHEN Guoliang.Design and Analysis of Parallel Algorithms［M］.Beijing：Higher Education Press，2002.（陳國(guó)良.并行算法的設(shè)計(jì)與分析［M］.北京：高等教育出版社，2002.）

［12］ JIA Meili.Master－Slave Parallel Mind Evolutionary Computation Based on MPI［J］.Journal of North University of China（Natural Science Edition），2007，28（z1）：66－69.（賈美麗.基于MPI的主從式并行思維進(jìn)化計(jì)算［J］.中北大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，28（z1）：66－69.）

［13］ DAVY J R，DEW P M.A Note on Improving the Performance of Delaunay Triangulation ［M］.Tokyo：Springer Japan，1989：209－226.

［14］ QI Lin，SHEN Jie，GUO Lishuai，et al.Dynamic Strip Partitioning Method Oriented Parallel Computing for Construction of Delaunay Triangulation ［J］.Journal of Geo－Information Science，2012，14（1）：55－61.（齊琳，沈婕，郭立帥，等.面向D－TIN并行構(gòu)建的動(dòng)態(tài)條帶數(shù)據(jù)劃分方法與試驗(yàn)分析［J］.地球信息科學(xué)學(xué)報(bào)，2012，14（1）：55－61.）

［15］ LIU Zhiqiang，SONG Junqiang，LU Fengshun，et al.Optimizing Method for Improving the Performance of MPI Broadcast under Unbalanced Process Arrival Patterns［J］.Journal of Software，2011，22（10）：2509－2522.（劉志強(qiáng)，宋君強(qiáng)，盧鳳順，等.非平衡進(jìn)程到達(dá)模式下MPI廣播的 性 能 優(yōu) 化 方 法 ［J］.軟 件 學(xué) 報(bào)，2011，22（10）：2509－2522.）

［16］ DOU Zhihui.High Performance Computing for Parallel Programming Technology－MPI Parallel Program Design［M］.Beijing：Tsinghua University Press，2001.（都志輝.高性能計(jì)算之并行編程技術(shù)—MPI并行程序設(shè)計(jì)［M］.北京：清華大學(xué)出版社，2001.）

［17］ LIN Na.Research and Improvement of Submitting Job in MPICH ［D］.Shanghai：Fudan University，2006.（林娜.MPICH作業(yè)遞交方式的研究及改進(jìn)［D］.上海：復(fù)旦大學(xué)，2006.）

［18］ GUO Lishuai，SHEN Jie，ZHU Wei.Time Complexity Analysis of Line Simplification Algoritnms［J］.Journal of Geomatics Science and Technology，2012，29（3）：226－230.（郭立帥，沈婕，朱偉.線要素化簡(jiǎn)算法的時(shí)間復(fù)雜度分析［J］.測(cè)繪科學(xué)技術(shù)學(xué)報(bào)，2012，29（3）：226－230.）