薛晨曦++陳犖++李軍

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

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

中圖分類(lèi)號(hào)： TN958?34； TP391.4 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）22?0044?04

0 引 言

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

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

1 關(guān)鍵技術(shù)平臺(tái)簡(jiǎn)介

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

1.1 MPI

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

1.2 Hadoop

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

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

1.3 Spark

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

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

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

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

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

3.1 實(shí)驗(yàn)環(huán)境

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

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

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

3.2 實(shí)驗(yàn)一：對(duì)MPI和Spark的性能進(jìn)行比較

3.2.1 實(shí)驗(yàn)內(nèi)容

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

3.2.2 實(shí)驗(yàn)方法

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

BEGIN

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

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

3.double dx //定義步長(zhǎng)

4.for（x=x1；x

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

6.輸出面積y

END

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

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

3.2.3 實(shí)驗(yàn)結(jié)果

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

表1 MPI和Spark運(yùn)行效率比較

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

3.3 實(shí)驗(yàn)二：對(duì)Spark和Hadoop進(jìn)行比較

3.3.1 實(shí)驗(yàn)內(nèi)容

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

3.3.2 實(shí)驗(yàn)方法

假設(shè)有N張地圖上截取的部分地區(qū)圖片，為了判斷其相似度，可以利用感知哈希算法[9] 將圖片轉(zhuǎn)化為8×8大小的圖片，并且設(shè)置為灰度圖片，計(jì)算各個(gè)圖片的哈希值，從而求出圖片的漢明距離，通過(guò)漢明距離判斷圖片的近似度。相關(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（）））， //計(jì)算圖片的哈希值

6.dis=hamming（hashx，hashy）

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

END

3.3.3 實(shí)驗(yàn)結(jié)果

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

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

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

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

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

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

[3] 都志輝.高性能計(jì)算之并行編程技術(shù)：MPI并行程序設(shè)計(jì)[M].北京：清華大學(xué)出版社，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īng)用與性能優(yōu)化[M].北京：機(jī)械工業(yè)出版社，2014.

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

[9] 丁凱孟，朱長(zhǎng)青.一種用于遙感影像完整性認(rèn)證的感知哈希算法[J].東南大學(xué)學(xué)報(bào)：自然科學(xué)版，2014（4）：723?727.

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

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