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

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

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

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

中圖分類號：G424 文獻標識碼：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序言

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

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

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

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

2 GIS并行算法庫模塊

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

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

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

3.1 實驗數(shù)據(jù)

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

3.2 實驗指標

并行程序的性能可以通過下面3個指標來評價。

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

并行程序總時間 = 。

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

并行程序總時間≥。

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

=

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

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

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

3.3 實驗結(jié)果與分析

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

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

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

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

4 總結(jié)

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

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

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

參考文獻

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

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

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