基于高性能計算平臺的地理信息系統(tǒng)算法調(diào)度引擎的研究

薛晨曦++陳犖++李軍

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

關(guān)鍵詞： MapReduce； 地理信息系統(tǒng)； Spark； 地理計算

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

0 引 言

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

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

1 關(guān)鍵技術(shù)平臺簡介

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

1.1 MPI

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

1.2 Hadoop

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

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

1.3 Spark

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

2 地理信息系統(tǒng)算法調(diào)度引擎架構(gòu)

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

地理信息系統(tǒng)算法調(diào)度引擎結(jié)構(gòu)的原理主要是通過Spark和原有的MPI對底層經(jīng)過注冊的地理計算算法和空間分析算法進行調(diào)度，通過計算流程執(zhí)行優(yōu)化器優(yōu)化，交由計算流程模型執(zhí)行器進行執(zhí)行，從而實現(xiàn)整個地理計算算法的調(diào)度。但是由于Spark沒有設計自己的文件系統(tǒng)，因此需要借用Hadoop的HDFS作為文件系統(tǒng)。

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

3.1 實驗環(huán)境

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

軟件環(huán)境：原配置部署MPI的地理信息系統(tǒng)，Spark，Hadoop以及所需要的環(huán)境。

實驗預設條件：在相同配置環(huán)境下部署不同的算法調(diào)度平臺。各平臺下代碼按照未做優(yōu)化和最佳優(yōu)化區(qū)別分開。

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

3.2.1 實驗內(nèi)容

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

3.2.2 實驗方法

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

BEGIN

1.double x1 //定義起始區(qū)間

2.double x2 //定義結(jié)束區(qū)間

3.double dx //定義步長

4.for（x=x1；x

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

6.輸出面積y

END

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

將代碼轉(zhuǎn)化為Spark使用的Scala語言之后，有效代碼僅為5行。將此代碼進行循環(huán)優(yōu)化之后也只有7行。

3.2.3 實驗結(jié)果

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

表1 MPI和Spark運行效率比較

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

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

3.3.1 實驗內(nèi)容

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

3.3.2 實驗方法

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

BEGIN

1.im=im.resize（8，8） //將圖片轉(zhuǎn)化為8×8

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

//將圖片轉(zhuǎn)化為灰度圖片

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 實驗結(jié)果

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

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

3.4 實驗結(jié)果分析

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

4 結(jié) 語

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

參考文獻

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

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

[3] 都志輝.高性能計算之并行編程技術(shù)：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大數(shù)據(jù)處理技術(shù)、應用與性能優(yōu)化[M].北京：機械工業(yè)出版社，2014.

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

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

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

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