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

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

關鍵詞 GIS 空間運算 并行模擬 教學實踐

中圖分類號：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序言

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

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

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

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

2 GIS并行算法庫模塊

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

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

3并行實驗模擬環(huán)境

3.1 實驗數據

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

3.2 實驗指標

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

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

并行程序總時間 = 。

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

并行程序總時間≥。

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

=

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

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

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

3.3 實驗結果與分析

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

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

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

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

4 總結

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

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

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

參考文獻

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

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

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