面向多核架構(gòu)的GIS 并行算法實(shí)驗(yàn)?zāi)M環(huán)境的開發(fā)與實(shí)踐教學(xué)

陳占龍+馮齊奇+吳亮+趙雷

摘 要 以VLSI為代表的現(xiàn)代半導(dǎo)體工藝技術(shù)單方面的進(jìn)步已經(jīng)很難滿足微處理器性能發(fā)展的需求，以“橫向擴(kuò)展”為特征的多核處理器成為了主流發(fā)展方向。多核時(shí)代到來的結(jié)果是軟件開發(fā)者必須找出新的開發(fā)軟件的方法，以多核架構(gòu)為基礎(chǔ)的并行處理技術(shù)的快速發(fā)展對(duì)空間信息數(shù)據(jù)的并行存取與處理具有重要的借鑒意義。“培養(yǎng)掌握3S工程理論和技術(shù)的信息軟件技術(shù)開發(fā)人才”為地理信息系統(tǒng)和信息工程專業(yè)人才培養(yǎng)的目標(biāo)之一，其目的在于使學(xué)生在校期間能接觸全球最前沿的技術(shù)，接受最新科研方法的訓(xùn)練。

關(guān)鍵詞 GIS 空間運(yùn)算 并行模擬 教學(xué)實(shí)踐

中圖分類號(hào)：G424 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.16400/j.cnki.kjdkz.2015.12.060

Abstract In VLSI as the representative of modern semiconductor technology advances unilateral microprocessor performance has been difficult to meet the needs of development in order to "scale" is characterized by multi-core processors become the mainstream of development. The results of multi-core era is the software developers must find new methods to develop software， rapid development of multi-core architecture based on parallel processing technology has important reference for parallel access to data and processing spatial information. One of the goals for the GIS and Information Engineering Personnel Training "training to master 3S engineering theory and technology information software technology development talent"， which aims to enable students at the school have access the world's most cutting-edge technology， accepted the latest research methods training.

Key words GIS spatial operators； parallel simulation； teaching practice

0序言

多核并行空間計(jì)算是一門動(dòng)手能力和理論要求都很強(qiáng)的課程，國(guó)內(nèi)外對(duì)于多核并行GIS的運(yùn)行環(huán)境展開了廣泛研究。英聯(lián)邦科學(xué)與工業(yè)研究組織（CSIRO）的Abel和新加坡國(guó)立大學(xué)的Ooi等人首先研究了分布式空間數(shù)據(jù)庫的空間連接查詢處理問題，提出了一種空間半連接查詢處理算法，構(gòu)建了分布式GIS的運(yùn)行環(huán)境。新加坡國(guó)立大學(xué)的Tan等人又將上述算法擴(kuò)展到多維索引結(jié)構(gòu)。韓國(guó)Yonsei大學(xué)的Kang等人基于“子圖劃分，任務(wù)分治”的思想在并行計(jì)算環(huán)境下優(yōu)化了海量空間數(shù)據(jù)的傳輸。泰國(guó)電子計(jì)算技術(shù)中心的Apirak Panatkool等人對(duì)網(wǎng)格上分布式的GIS服務(wù)進(jìn)行了研究，提出基于計(jì)算網(wǎng)格模型的分布式模式。馬里蘭大學(xué)的Tanin等人基于SAND平臺(tái)研究了在集中式中介模型和對(duì)等式中介模型下的GIS系統(tǒng)，能夠利用閑散的結(jié)點(diǎn)資源響應(yīng)更多的用戶查詢請(qǐng)求。德國(guó)不來梅大學(xué)計(jì)算技術(shù)研究中心的V gele等人討論了對(duì)等網(wǎng)絡(luò)環(huán)境下使用元數(shù)據(jù)對(duì)空間信息進(jìn)行獲取的模擬環(huán)境。奧地利薩爾茲堡研究機(jī)構(gòu)的Alenka Krek等人則提出了對(duì)等協(xié)同計(jì)算GIS的概念，并給出了三種對(duì)等協(xié)同計(jì)算GIS的分類。在國(guó)內(nèi)相關(guān)學(xué)者進(jìn)行了研究，2006年北京大學(xué)方裕教授等人則顧及空間數(shù)據(jù)的特殊性，建立了并行協(xié)同GIS平臺(tái)運(yùn)行環(huán)境。中科院地理科學(xué)與資源研究所資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室的沈占鋒、駱劍承等實(shí)現(xiàn)了當(dāng)前在GIS領(lǐng)域的并行中間件運(yùn)行環(huán)境。

這些研究為面向多核架構(gòu)的GIS并行實(shí)驗(yàn)?zāi)M環(huán)境的開發(fā)提供了理論基礎(chǔ)和實(shí)踐參照，但目前國(guó)內(nèi)外商用的GIS軟件由于系統(tǒng)結(jié)構(gòu)復(fù)雜，安裝繁瑣，價(jià)格昂貴，最重要是現(xiàn)有的GIS軟件平臺(tái)缺乏對(duì)多核架構(gòu)的有力支撐，在這些運(yùn)行環(huán)境中很難體現(xiàn)多核并行GIS空間信息理論，使得教學(xué)理論內(nèi)容與實(shí)驗(yàn)教學(xué)很難有機(jī)結(jié)合，學(xué)生在做實(shí)驗(yàn)時(shí)難以理解。因此，研制面向多核架構(gòu)的GIS并行實(shí)驗(yàn)?zāi)M運(yùn)行環(huán)境，提高學(xué)生對(duì)并行GIS的理解，加強(qiáng)學(xué)生實(shí)驗(yàn)時(shí)的動(dòng)手能力，節(jié)約教學(xué)軟件資金，具有重要意義。

1并行模擬環(huán)境目標(biāo)

在地理信息系統(tǒng)和信息工程專業(yè)本科生中進(jìn)行多核架構(gòu)及編程技術(shù)的課程建設(shè)，使得學(xué)生在硬件、軟件方面能夠更好地了解多核思想及編程技術(shù)，更好地適應(yīng)高新技術(shù)飛速發(fā)展的需要。當(dāng)今世界各國(guó)存在一個(gè)普遍現(xiàn)象，即大學(xué)里培養(yǎng)的科技人才不能適應(yīng)科技創(chuàng)新型社會(huì)的需要，而且，兩者之間的差距日益擴(kuò)大，形成“畢業(yè)鴻溝”。其根本原因在于學(xué)生在校期間無法接觸到全球最前沿的技術(shù)，接受不到最新科研方法的訓(xùn)練。要改變這個(gè)現(xiàn)狀，其中關(guān)鍵途徑之一就是讓年輕人通過感受最新技術(shù)成果而樹立創(chuàng)新意識(shí)，通過參與最新技術(shù)的應(yīng)用研發(fā)而提高創(chuàng)新能力。“面向多核架構(gòu)的GIS 并行實(shí)驗(yàn)?zāi)M環(huán)境”的建設(shè)是歷史的必然；另一方面，高校的社會(huì)責(zé)任之一就是為社會(huì)輸送更多的復(fù)合型人才與專業(yè)技術(shù)人才，由于學(xué)生就業(yè)有“滯后性”的特點(diǎn)，而教學(xué)設(shè)計(jì)必須具有“前瞻性”，是故“多核并行空間計(jì)算”相關(guān)課程的開展也是現(xiàn)實(shí)的必然。“面向多核架構(gòu)的GIS 并行實(shí)驗(yàn)?zāi)M環(huán)境”的研制，作為地理信息系統(tǒng)和信息工程專業(yè)的“地理信息系統(tǒng)”、“并行計(jì)算”、“高性能計(jì)算”等課程的實(shí)驗(yàn)平臺(tái)運(yùn)行環(huán)境，讓學(xué)生在校期間接觸最前沿的高性能計(jì)算技術(shù)，接受新的科研方法的訓(xùn)練，使學(xué)生通過感受最新技術(shù)成果而樹立創(chuàng)新意識(shí)，通過參與最新技術(shù)的應(yīng)用研發(fā)而提高創(chuàng)新能力。

2 GIS并行算法庫模塊

該模擬環(huán)境系統(tǒng)分為多任務(wù)并行系統(tǒng)、空間運(yùn)算處理系統(tǒng)、并行空間運(yùn)算處理系統(tǒng)共三個(gè)子系統(tǒng)，其中并行空間運(yùn)算處理系統(tǒng)由多任務(wù)并行系統(tǒng)和空間運(yùn)算處理系統(tǒng)共同完成，我們將以三個(gè)動(dòng)態(tài)庫的形式提供用戶，各系統(tǒng)的職責(zé)：（1）多任務(wù)并行系統(tǒng)：根據(jù)用戶傳入的任務(wù)進(jìn)行任務(wù)分解和調(diào)度，使任務(wù)能得以高效并行的執(zhí)行；（2）空間運(yùn)算處理系統(tǒng)：采用OGC抽象規(guī)范提供的開源GEOS庫，包含了全部空間運(yùn)算方法實(shí)現(xiàn)；（3）并行空間運(yùn)算處理系統(tǒng)：將多任務(wù)并行系統(tǒng)與空間運(yùn)算處理系統(tǒng)結(jié)合，并行系統(tǒng)傳入的任務(wù)是空間運(yùn)算，將多個(gè)空間運(yùn)算任務(wù)并行去處理。

本系統(tǒng)采用過程驅(qū)動(dòng)控制和多線程并發(fā)控制。首先用戶傳入需要處理的空間數(shù)據(jù)，選擇空間運(yùn)算操作，程序?qū)⑦@些空間運(yùn)算操作和空間數(shù)據(jù)操作傳入多任務(wù)并行系統(tǒng)，根據(jù)依賴關(guān)系分配原則，系統(tǒng)分配線程以及每個(gè)線程中的任務(wù)。然后并行執(zhí)行線程中的任務(wù)，即執(zhí)行空間運(yùn)算處理系統(tǒng)。最后輸出結(jié)果。

3并行實(shí)驗(yàn)?zāi)M環(huán)境

3.1 實(shí)驗(yàn)數(shù)據(jù)

數(shù)據(jù)采用MapGIS K9地圖編輯器創(chuàng)建的簡(jiǎn)單要素模型，數(shù)據(jù)量從10000到100000共十組數(shù)據(jù)。首先創(chuàng)建一個(gè)簡(jiǎn)單要素，然后通過陣列復(fù)制獲得大量的簡(jiǎn)單要素。如圖1為10000個(gè)簡(jiǎn)單要素區(qū)的數(shù)據(jù)。

3.2 實(shí)驗(yàn)指標(biāo)

并行程序的性能可以通過下面3個(gè)指標(biāo)來評(píng)價(jià)。

（1）時(shí)間指標(biāo)。并行程序的直接目的就是要使程序花費(fèi)的時(shí)間性能得到提升。在理論情況下，并行程序的總時(shí)間滿足下面公式：

并行程序總時(shí)間 = 。

但是實(shí)際運(yùn)用中是做不到的，實(shí)際的并行程序總時(shí)間一般符合下列不等式：

并行程序總時(shí)間≥。

（2）加速比指標(biāo)。為了更好地描述并行程序計(jì)算的性能，通常采用加速比指標(biāo)來進(jìn)行度量。加速比公式為：

=

加速比通常都小于CPU核心數(shù)，只有極少數(shù)并行算法如并行順序搜索可以獲得超線性加速比。因此，并行性能較好的程序加速比一般要求向CPU核心數(shù)靠近；而且加速比越大，程序性能越好。

加速比是多核并行編程中需要考慮的非常重要的性能指標(biāo)，影響加速比的主要因素包括：串行計(jì)算、CPU饑餓問題和線程間的負(fù)載平衡問題等

（3）粒度指標(biāo)。選擇適合應(yīng)用的粒度是實(shí)現(xiàn)出色并行性能的關(guān)鍵之一。粒度是指并行任務(wù)的實(shí)際工作量。如果選擇的粒度太細(xì)，則程序的并行性能會(huì)因?yàn)榫€程切換、通信開銷等因素增加而受到很大影響；如果選擇的粒度太粗，則程序的并行性能會(huì)因?yàn)樨?fù)載不均衡等因素而受到影響。為了能夠?qū)崿F(xiàn)最佳的并行性能，編程者應(yīng)選擇合適的并行任務(wù)粒度（通常粒度越大越好），盡量減小線程切換、通信開銷和負(fù)載不均衡等因素的影響。

3.3 實(shí)驗(yàn)結(jié)果與分析

目前，編程者選擇合適的并行任務(wù)粒度的方法是從邏輯上將需要執(zhí)行的任務(wù)分解成盡量多的并行任務(wù)，或者在并行任務(wù)內(nèi)根據(jù)執(zhí)行順序和共享數(shù)據(jù)決定必要的通信。由于分解任務(wù)、任務(wù)分配和線程切換等會(huì)產(chǎn)生一些額外的開銷，編程者分解任務(wù)后還需要整合分解的任務(wù)，以減小額外的開銷，提高程序性能，這樣才能得到最佳的并行任務(wù)粒度。在本次實(shí)驗(yàn)中，將從上面3個(gè)指標(biāo)來分析實(shí)驗(yàn)結(jié)果，以更好地理解并行程序的性能提升。

在本次實(shí)驗(yàn)中，分別在串行、2線程、4線程和8線程下測(cè)試了10000到100000十組數(shù)據(jù)，并將結(jié)果通過圖表的形式表現(xiàn)出來。由于空間運(yùn)算操作較多，這里選取其中幾個(gè)做詳細(xì)介紹。

選取半徑20，弧段數(shù)12，冒端模式2對(duì)數(shù)據(jù)做緩沖區(qū)buffer分析，如圖2是10000的數(shù)據(jù)通過緩沖區(qū)Buffer分析后得到的新的簡(jiǎn)單要素區(qū)，實(shí)驗(yàn)結(jié)果證明并行程序的正確性。

經(jīng)過多次實(shí)驗(yàn)后，得出了從10000到100000十組數(shù)據(jù)經(jīng)過并行緩沖區(qū)分析后所用的時(shí)間和加速比圖表，如圖2所示。

4 總結(jié)

通過本次實(shí)驗(yàn)，可以總結(jié)如下結(jié)論：（1）基于OpenMP并行化解決方案的多任務(wù)調(diào)度算法能夠較好地解決GIS中空間運(yùn)算并行運(yùn)行。2線程的加速比能達(dá)到1.5以上，4線程和8線程的加速比能達(dá)到2.0以上。（2）影響程序并行性能的因素包括：并行任務(wù)粒度，任務(wù)分解與調(diào)度策略、負(fù)載均衡、硬件配置、軟件算法等。（3）程序并行的線程數(shù)選擇并不是越多越好。選擇合適的線程數(shù)需要考慮的主要因素包括：硬件配置和并行任務(wù)粒度，盡量選擇不超過硬件能同時(shí)運(yùn)行的線程數(shù)且并行任務(wù)粒度大小合適的線程數(shù)作為程序并行的線程數(shù)。（4）在合適的線程數(shù)選擇范圍內(nèi)，并行性能會(huì)隨著線程數(shù)的增加而增加。

本文論述了基于OpenMP并行化解決方案的空間運(yùn)算的多任務(wù)調(diào)度算法的設(shè)計(jì)與實(shí)現(xiàn)，結(jié)合GEOS庫提供的空間運(yùn)算算法進(jìn)行了多次實(shí)驗(yàn)，并取得了不錯(cuò)的并行加速效果，本文采用的是OpenMP并行化解決方案，下一步將融合其他優(yōu)秀的并行化解決方案，如：TBB并行化解決方案等，進(jìn)一步提高并行空間分析算法的效率。

基金項(xiàng)目：中國(guó)地質(zhì)大學(xué)（ 武漢） 校級(jí)B 類教學(xué)研究項(xiàng)目：基于項(xiàng)目的“雙創(chuàng)型”人才培養(yǎng)模式探索——以信息工程專業(yè)為例；中國(guó)地質(zhì)大學(xué)（ 武漢） 實(shí)驗(yàn)技術(shù)研究項(xiàng)目研究項(xiàng)目：面向多核架構(gòu)的GIS并行實(shí)驗(yàn)?zāi)M環(huán)境開發(fā)

參考文獻(xiàn)

[1] 俞艷，袁艷斌，黃解軍.GIS拔尖創(chuàng)新人才培養(yǎng)課程體系設(shè)計(jì)[J].地理空間信息，2015.4（13）：2.

[2] 楊志恒.GIS空間分析研究進(jìn)展綜述[J].安徽農(nóng)業(yè)科學(xué)，2012.40（8）：2.

[3] 魏巍巍.空間分析的概念與前沿應(yīng)用[J].產(chǎn)業(yè)與科技論壇，2015.14（12）：3.