基于高性能計算平臺的地理信息系統算法調度引擎的研究

薛晨曦++陳犖++李軍

摘 要： 主要針對傳統模式下的地理信息系統算法調度引擎無法滿足用戶對于地理信息系統響應速度快的要求，研究并且提出了利用高性能的計算平臺進行地理信息系統中地理計算算法的調度，從而提高地理信息系統的性能。經過實驗表明：新的高性能計算平臺對于地理信息系統的算法調度有了一定提高，改善了地理信息系統的部分性能指標。

關鍵詞： MapReduce； 地理信息系統； Spark； 地理計算

中圖分類號： TN958?34； TP391.4 文獻標識碼： A 文章編號： 1004?373X（2015）22?0044?04

0 引 言

隨著地理信息系統（Geographic Information System，GIS）在大眾日常生活中應用場景越來越廣泛，基于地理信息系統開發的軟件不僅滿足了人們日常生活中對于路徑規劃，地標指引等需求，同時一些部門和城市建立了各具特色的綜合或者專業性GIS[1]。然而傳統的基于地理信息系統開發軟件，由于其平臺性能限制，已經逐漸難以滿足用戶的需要。隨著用戶設備的硬件配置、網絡情況的不斷提高，用戶對于長時間等待的容忍度漸漸地降低。因此，地理信息系統不僅需要更為精確智能的算法對用戶提供信息，同時也需要調度引擎更快地對地理計算算法和空間分析算法進行調度。以加快地理信息系統中的計算速度，從而減少用戶等待時間，提高用戶體驗。

在現有的地理信息系統中，算法調度引擎多基于MPI架構[2]，采用Touque/PBS進行算法調度。MPI架構存在著很多影響性能的問題，比如通信延遲比較大、負載不平衡，并且MPI本身編程模型復雜，可擴展性和容錯性差。本文主要將高性能的計算平臺引入地理信息系統中，實現地理信息算法和空間分析算法的快速調度，對地理信息系統算法調度引擎進行優化。

1 關鍵技術平臺簡介

谷歌在自己的論文中提出了MapReduce編程模型之后，很多從事數據處理的學者受到了巨大的啟發。Apache Software Foundation就利用這個模型，在2005年開發了一個分布式架構——Hadoop。Hadoop所采用的MapReduce技術為數據的快速運算提供了重要的幫助，而Hadoop的出現意味著傳統并行計算遇到了巨大的挑戰。伴隨著計算平臺的進一步發展，一些采取其他技術的高性能計算平臺也不斷涌現。本文主要針對Apache的Hadoop和UC Berkeley AMP Lab研發開源的Spark，在地理信息系統算法調度引擎中的應用進行討論。

1.1 MPI

消息傳遞接口（Message Passing Interface，MPI）是MPI的工作小組為了解決單個核心的計算機無法處理海量數據的計算而制定的并行計算標準[3]。其在20世紀90年代被提出之后，廣泛地應用在科學計算領域：在生物學、化學、計算機科學等領域上發揮著重要的作用。MPI也是目前最為成熟的并行計算平臺。目前MPI主要有MPICH以及OpenMPI兩個實現。這兩個實現分別定義了MPI的核心庫函數的語法規則，以便用戶利用C語言和C++語言編寫MPI的語句。這也決定了MPI的編程主要是面向過程的編程。MPI允許同一程序在一臺計算機上的多個進程一起運行，或者分布在多臺計算機的多個進程上一起運行。其中每個進程相對獨立，擁有各自的數據，在不發生通信的時候分別異步地處理數據。然后在需要互相訪問的時候，根據MPI標準規定的通信函數進行數據的遷移、同步計算等操作。

1.2 Hadoop

Hadoop是Apache Software Foundation公司所開源的一個分布式計算的項目。Hadoop讓用戶在無需了解整個分布式系統底層細節的前提下，便可以通過構建分布式集群來實現系統運算速度的優化。它支持用戶采用Java，Python，Ruby等語言進行編程。Hadoop除了采用谷歌公司提出的MapReduce技術來實現快速計算以外，Apache Software Foundation創新性地提出了Hadoop分布式文件系統（Hadoop Distributed File System，HDFS），對于海量數據的處理提供了便利。

HDFS[4]具有很高的容錯性，可以部署在多臺性能不高的硬件上。在分布式集群各個節點之間提供了很高的吞吐量用來進行數據的交換。MapReduce[5]利用“map”函數將一組雜亂無章的數值映射到一組新的數值對里面，并且指定其為“Reduce”函數，保證映射的數值正好對應數值組中。

1.3 Spark

Spark是美國UC Berkeley的AMP實驗室開源的一個項目，是Apache基金會的頂級項目。Spark基于Scala語言開發，支持用戶采用Java，Scala，Python等語言進行編程，具有良好的可拓展性。Spark比起傳統的計算平臺有了新的突破：Spark提出了一個叫做彈性分布式數據集（Resilient Distributed Datasets，RDD）的結構[6]。RDD是分布在一組節點中的只讀對象集合，通過這些支持數據內存駐留的彈性數據集，Spark避免了Hadoop在MapReduce過程中將處理結果寫回HDFS文件系統，減少了硬盤訪問次數，從而提高了迭代算法的運行效率，很好地適應了需要多次進行迭代的算法。RDD還可以實現在數據集的一部分丟失的情況下，對整個數據集進行重建，從而使整個系統具有了強大的容錯性。Spark不僅僅在數據處理上獲得廣泛應用，更是產生了一系列相關的生態系統[7]。比如Shark，Spark SQL，Spark Streaming，MLLib，GraphX等。這些相關組件配合Spark本身在數據庫支持、實時數據處理、圖計算等方面發揮了巨大作用。

2 地理信息系統算法調度引擎架構

為了驗證設想，將Spark配置在原有的地理信息系統[8]中。利用Spark平臺，對地理信息系統中原有地理計算的算法進行調度。配置Spark平臺之后的地理信息系統算法調度引擎的架構如圖1所示。

地理信息系統算法調度引擎結構的原理主要是通過Spark和原有的MPI對底層經過注冊的地理計算算法和空間分析算法進行調度，通過計算流程執行優化器優化，交由計算流程模型執行器進行執行，從而實現整個地理計算算法的調度。但是由于Spark沒有設計自己的文件系統，因此需要借用Hadoop的HDFS作為文件系統。

3 實驗與結果分析

3.1 實驗環境

硬件環境：本文采用一臺高性能PC和一臺Mac進行程序設計和測試，以及一個包含2臺服務器的集群作為主要環境進行實驗。PC的主要硬件配置為Intel Core i5 CPU，4 GB內存，64位Windows 7操作系統。利用虛擬機搭建更多的Datanode環境。

軟件環境：原配置部署MPI的地理信息系統，Spark，Hadoop以及所需要的環境。

實驗預設條件：在相同配置環境下部署不同的算法調度平臺。各平臺下代碼按照未做優化和最佳優化區別分開。

3.2 實驗一：對MPI和Spark的性能進行比較

3.2.1 實驗內容

為對比MPI和Spark在地理信息系統中作為算法調度引擎的性能，在配置好環境之后采用MPI和Spark分別進行一次同樣的地理計算。在本次實驗中，選取了對制定目標占地面積的計算作為任務，對比2次計算的結果。

3.2.2 實驗方法

假設有一塊地域，其面積可以用矩形法求定積分得出。求這塊區域面積的算法如下：

BEGIN

1.double x1 //定義起始區間

2.double x2 //定義結束區間

3.double dx //定義步長

4.for（x=x1；x

5.y = y+dx*x*x //細小矩形取其左側作為高

6.輸出面積y

END

將算法轉化為MPI使用的C語言之后，有效代碼共計12行。

將代碼轉化為Spark使用的Scala語言之后，有效代碼僅為5行。將此代碼進行循環優化之后也只有7行。

3.2.3 實驗結果

不同環境平臺下運行程序后的效率如表1所示。

表1 MPI和Spark運行效率比較

從表1可以看出，未經優化的Spark Scala代碼比MPI C的代碼簡潔很多。但是運行時間消耗太多。經過優化代碼之后，Spark Scala依然比MPI C代碼簡單一些，運行效率比未經優化的MPI C代碼要快一些。并且同MPI相比，Spark編程更為簡練，需要的代碼更少，可以縮短開發周期，并且Spark支持動態增加節點，在系統進行變化之后無需重新編程。

3.3 實驗二：對Spark和Hadoop進行比較

3.3.1 實驗內容

為了對比Spark同普通串行運行程序在地理信息系統算法引擎調度中的性能，在配置好相應環境之后在Spark平臺和串行運行分別做了1次相同的地理計算。在本次試驗中，選擇根據地圖圖片的哈希值求出地圖圖片之間的漢明距離，從而計算出地圖中地點的相似程度，并且對比2次計算結果。實驗數據為百度地圖上長沙市地圖的截圖，每張大小大概為40 KB。

3.3.2 實驗方法

假設有N張地圖上截取的部分地區圖片，為了判斷其相似度，可以利用感知哈希算法[9] 將圖片轉化為8×8大小的圖片，并且設置為灰度圖片，計算各個圖片的哈希值，從而求出圖片的漢明距離，通過漢明距離判斷圖片的近似度。相關代碼如下：

BEGIN

1.im=im.resize（8，8） //將圖片轉化為8×8

2.im=Image.ANTIALIAS）.convert（′L′）

//將圖片轉化為灰度圖片

3.avg=reduce（lambda x，y：x+y，im.getdata（））/64

4.return reduce（lambda x，（y，z）：x|（z<

5.enumerate（map（lambda i：0 if i

im.getdata（）））， //計算圖片的哈希值

6.dis=hamming（hashx，hashy）

//利用圖片的哈希值求漢明距離

END

3.3.3 實驗結果

不同環境平臺下運行程序的效率如表2所示，Spark平臺同串行運行程序效率趨勢圖如圖3所示。

從實驗結果可以看出，隨著地圖數據量的增大，Spark與串行運行程序的效率相比，在數據量為幾百KB時處于劣勢；在數據量為幾MB時效率相當；當數據量達到GB級別，Spark遠遠超出串行運行的效率。從表2也可以看出，在TB級別時Spark的效率將更加優于串行運行。

3.4 實驗結果分析

通過兩個實驗可以看出，采用Spark的地理信息系統算法調度引擎比傳統的地理信息系統算法調度引擎有著一定的優勢。雖然MPI可以通過深度優化代碼來減小差距，但是由于MPI本身編程復雜，在地理信息系統中優化全部地理計算算法工作量巨大，難以實現這樣層次的優化。并且MPI在系統發生變化之后必須要重新配置才可以運行，在可拓展性上有著巨大的缺陷。因此可以看出Spark在地理信息系統中的應用有著良好的效果。

4 結 語

本文通過實驗測試對比了Spark和MPI在地理信息系統算法調度中的性能，提出在地理信息系統的算法調度過程中應用Spark平臺技術，對地理信息系統的性能有了一定的提升，同時改良了系統的復雜程度，減小了工作人員維護系統的成本。同時縮短了一定的系統響應時間，提升了用戶體驗。在下一步的工作中，還需要解決在更大規模集群下運行Spark，并且利用Spark實現對地圖進行圖像金字塔算法[10]并處理地理計算的問題。

參考文獻

[1] 張廣瑩，張廣宇，黃昊.地理信息系統在智能交通系統中的應用[J].自動化技術與應用，2013（13）：30?33.

[2] 吳立新，楊宜舟，秦承志，等.面向新型硬件構架的新一代GIS基礎并行算法研究[J].地理與地理信息科學，2013，29（4）：1?8.

[3] 都志輝.高性能計算之并行編程技術：MPI并行程序設計[M].北京：清華大學出版社，2001.

[4] KALA K A， CHITHARANJAN K， KALA K A， et al. A review on hadoop?HDFS infrastructure extensions [J]. IEEE Conference on Information & Communication Technologies， 2013， 21（1）：132?137.

[5] Anon. MapReduce [DB/OL]. [2013?03?25]. http：//en.wikipedia.org/wiki/MapReduce.

[6] ZAHARIA M， CHOWDHURY M， DAS T， et al. Resilient distributed datasets： a fault?tolerant abstraction for in?memory cluster computing [J]. USENIX Symposium on Networked Systems Design and Implementation， 2011， 70（2）： 141?146.

[7] 高彥杰.Spark大數據處理技術、應用與性能優化[M].北京：機械工業出版社，2014.

[8] 林碧英，王艷萍.基于Hadoop的電力地理信息系統數據管理[J].計算機應用，2014，34（10）：2806?2811.

[9] 丁凱孟，朱長青.一種用于遙感影像完整性認證的感知哈希算法[J].東南大學學報：自然科學版，2014（4）：723?727.

[10] 姜代紅.基于影像金字塔的GIS地圖動態漫游算法[J].計算機工程與設計，2013，34（5）：1711?1715.

[11] 張華偉，張洪永，蔡一兵，等.基于OCI的GIS數據庫的開發與應用[J].現代電子技術，2010，33（15）：190?191.