雙重并行環(huán)境下最短路徑的研究

孫玉強, 李銀銀, 顧玉宛

(常州大學(xué) 信息科學(xué)與工程學(xué)院, 江蘇 常州 213164)

雙重并行環(huán)境下最短路徑的研究

孫玉強, 李銀銀, 顧玉宛

(常州大學(xué) 信息科學(xué)與工程學(xué)院, 江蘇 常州 213164)

并行問題和最短路徑問題已成為一個熱點研究課題，傳統(tǒng)的最短路徑算法已不能滿足數(shù)據(jù)爆炸式增長的處理需求，尤其當(dāng)網(wǎng)絡(luò)規(guī)模很大時，所需的計算時間和存儲空間也大大的增加;MapReduce模型的出現(xiàn)，帶來了一種新的解決方法來解決最短路徑;GPU具有強大的并行計算能力和存儲帶寬，與CPU相比具有明顯的優(yōu)勢;通過研究MapReduce模型和GPU執(zhí)行過程的分析，指出單獨基于MapReduce模型的最短路徑并行方法存在的問題，降低了系統(tǒng)的性能;論文的創(chuàng)新點是結(jié)合MapReduce和GPU形成雙并行模型，并行預(yù)處理數(shù)據(jù)，針對最短路徑中的數(shù)據(jù)傳輸和同步開銷，增加數(shù)據(jù)動態(tài)處理器;最后實驗從并行算法的性能評價指標平均加速比進行比較，結(jié)果表明，雙重并行環(huán)境下的最短路徑的計算,提高了加速比。

最短路徑；并行計算；MapReduce；GPU；數(shù)據(jù)動態(tài)處理器

0 引言

最短路徑問題是數(shù)學(xué)界和計算機科學(xué)中的一個重要的研究課題，在數(shù)學(xué)建模的基礎(chǔ)上，解決了城市規(guī)劃、物流、交通管理、數(shù)字導(dǎo)航等領(lǐng)域的實際問題[1]。并行計算為最短路徑提供了一種新的解決方案，尤其是在動態(tài)網(wǎng)絡(luò)中最短路徑的處理中。

MapReduce模型可以解決計算機的存儲容量和數(shù)據(jù)的爆炸性增長的計算能力缺乏之間的矛盾，因為MapReduce本身具有封裝數(shù)據(jù)分區(qū)、負載均衡、容錯處理等細節(jié)，用戶只需要將實際應(yīng)用中的問題分為幾個問題，它們是可并行操作的子問題[2]，從而可有效降低解決問題的難度。

與CPU不同，GPU具有特殊的硬件結(jié)構(gòu)，計算能力和處理能力是CPU十倍甚至幾十倍，處理器帶寬更高，功耗更低，因此，使用GPU加速MapReduce計算得到了廣泛的關(guān)注。

1 研究背景

1.1 最短路徑概述

給出最短路徑的加權(quán)有向圖G=(V，E，W)，其中V是頂點集和邊集E，W是權(quán)重集，每一個邊的權(quán)重是非負實數(shù)[3]；V的頂點，稱為源，計算最短路徑從源到所有其他點的長度，其中長度是指邊的權(quán)重的和；按照現(xiàn)實情況，邊的權(quán)重可以通過時間、距離、成本、損失等來表示，并且是最小值[4]。

1.2 MapReduce模型

在該模型中，有兩個過程，Map和Reduce。在Map階段，將初始輸入數(shù)據(jù)轉(zhuǎn)化為鍵-值對，然后將數(shù)據(jù)分布到集群中的所有計算節(jié)點進行并行處理，得到中間結(jié)果集[5]；而Reduce階段將對那些具有同一的中間結(jié)果進行處理，以獲得終極的輸出記錄。

1.3 GPU

GPU設(shè)計用于高度密集型的并行計算，具有強大浮點計算能力，高帶寬、隱藏的延遲和高性能的多處理器陣列的存儲系統(tǒng)，主要用于大量線程的計算。

2 雙重并行環(huán)境下最短路徑的設(shè)計

2.1 雙重并行計算的提出

GPU和MapReduce結(jié)合的原因如下：

(1)目前，對GPU和MapReduce并行計算單獨的研究一直無法滿足需求，GPU具有更好的數(shù)據(jù)寬度和并行計算的能力，GPU比CPU閑置的時間更多，GPU使用得當(dāng)，它可以減少CPU的占用時間，而且可以使得過度空閑的GPU可以被充分利用。

(2)MapReduce模型需要大量的CPU、存儲器、高性能的寬帶網(wǎng)絡(luò)，MapReduce模型的Map和Reduce操作，有時往往需要頻頻的CPU計算[6]，當(dāng)有大量的并行計算任務(wù)的時候，甚至高達100%的占用率，有必要平衡，GPU參與系統(tǒng)的計算能力。

2.2 MapReduce和GPU并行模型

圖1顯示了基于GPU的MapReduce并行模型圖。CPU首先讀取硬盤或存儲的數(shù)據(jù)文件，并將其分塊，然后調(diào)用GPU的計算，在GPU中進行Map操作的每個數(shù)據(jù)塊，并開始啟動Map任務(wù)[5]；Map任務(wù)將產(chǎn)生多個中間鍵-值對，然后GPU開始排序操作，中間鍵-值對按關(guān)鍵字排序；隨后CPU把已排序的中間鍵-值重新分塊，每一塊遞給GPU計算部分中的Reduce操作，然后開始Reduce任務(wù)。最后，得到Reduce任務(wù)的多個輸出記錄，并開始合并操作，得到最終的輸出值給CPU調(diào)用[7]。

圖1 基于GPU的MapReduce并行模型圖

2.3 MapReduce和GPU雙重并行最短路徑實現(xiàn)

前期處理過程：

預(yù)處理是初級階段，負責(zé)初始數(shù)據(jù)和節(jié)點之間的數(shù)據(jù)的初始分派。用戶需要初始化系統(tǒng)，并根據(jù)應(yīng)用程序的具體特點，設(shè)置合適的環(huán)境變量和不同的流程，如設(shè)置工作節(jié)點、鍵-值對的數(shù)據(jù)類型、GPU的線程塊兒的大小、完成所需的工作環(huán)節(jié)(map、reduce)、輸出位置和方式[5]。之后初始的數(shù)據(jù)將被系統(tǒng)分成相同的大小，適于在GPU計算的數(shù)據(jù)塊，這些塊被分布到集群中的所有節(jié)點。

圖2所示是基于Mapreduce的最短路徑流程圖。其中有兩個子階段降低了系統(tǒng)的性能。一個是中間結(jié)果寫到磁盤的map階段，主要目的是提高系統(tǒng)的可靠性，但是以犧牲系統(tǒng)性能為代價，因為對象的建立、銷毀、垃圾回收等，會花很多時間。

圖2 基于Mapreduce的最短路徑流程圖

另一個階段是將map的結(jié)果通過網(wǎng)絡(luò)傳送給Reduce節(jié)點的過程，混合排序操作，中間結(jié)果傳輸期間的網(wǎng)絡(luò)和同步成本是降低系統(tǒng)性能的一個重要因素。

針對上述問題進行改進，圖3顯示了MapReduce和GPU的雙并行處理機制，GPU嵌入Hadoop，結(jié)合GPU和多核心CPU資源。在實現(xiàn)時，或因為CPU和GPU的數(shù)據(jù)傳輸和同步開銷太大，不能發(fā)揮GPU的優(yōu)點。為此添加數(shù)據(jù)動態(tài)處理器，有了動態(tài)數(shù)據(jù)處理器，能夠?qū)崟r監(jiān)測計算節(jié)點GPU內(nèi)存，數(shù)據(jù)的動態(tài)分解與組合，確保GPU計算最適合的數(shù)據(jù)，GPU速度優(yōu)化。

圖3 MapReduce和GPU雙重并行處理機制

GPU完成大規(guī)模數(shù)據(jù)的并行計算任務(wù)，其他GPU代替不了CPU執(zhí)行的非計算任務(wù)仍由CPU完成，如對硬盤的訪問，訪問物理地址，讀取和寫入文件。

當(dāng)用戶程序調(diào)用Map函數(shù)時，讀取本地文件(key-value形式)，產(chǎn)生輸出結(jié)果后，數(shù)據(jù)分片函數(shù)將輸出記錄分割成幾個不同的塊，具體過程如下：

首先，任務(wù)通過MapReduce機制分發(fā)，將數(shù)據(jù)傳輸?shù)焦ぷ鞴?jié)點，實現(xiàn)第一級多節(jié)點并行，然后基于節(jié)點的配置每個節(jié)點使用GPU等并行方式實現(xiàn)第二級并行，工作節(jié)點基于任務(wù)的大小和當(dāng)前節(jié)點的GPU性能將數(shù)據(jù)發(fā)送到數(shù)據(jù)動態(tài)處理器。動態(tài)數(shù)據(jù)處理器分割或組合數(shù)據(jù)以創(chuàng)建滿足GPU功能(確保高速、全負載GPU操作)的數(shù)據(jù)塊，數(shù)據(jù)被發(fā)送到GPU處理[8]。最后，GPU計算結(jié)果被傳輸?shù)街鳈C內(nèi)存進行后續(xù)處理，這種多級的處理機制可顯示GPU的計算能力。

與Map階段不同，Reduce階段具有同一的中間鍵-值對記錄在一起，最后，按照用戶的需要，合并或存儲結(jié)果，并且被系統(tǒng)最終清理。

3 實驗結(jié)果

前面介紹了MapReduce和GPU雙并行模型及處理機制和最短路徑的實現(xiàn)，下面進行實驗測試。實驗使用兩臺普通服務(wù)器、一臺D-Link百兆交換機組成的集群上，在運行調(diào)試之前，需要執(zhí)行以下步驟：首先通過CUDA開發(fā)工具編譯map函數(shù)，將C語言文件編譯為DLL庫文件，然后通過使用java語言調(diào)用本地庫文件的JNI方法來編譯系統(tǒng)框架，配置環(huán)境基本上是一樣的。測試結(jié)果如表1所示。實驗數(shù)據(jù)顯示了從10 000個結(jié)點到105個結(jié)點，再到106及107個結(jié)點求解最短路徑所用的時間。

表1 運行時間對比表

相比上述實驗結(jié)果，在計算最短路徑時，結(jié)點相同的情況下，MapReduce和GPU雙重并行條件下最短路徑的計算比MapReduce計算或普通的并行計算速度更快，所用的時間明顯減少，GPU加速的MapReduce模型，充分發(fā)揮優(yōu)勢，在結(jié)點增加時，平均加速比也有所增加，即雙重并行條件下的最短路徑的計算，提高了大規(guī)模數(shù)據(jù)并行處理的優(yōu)勢。

4 結(jié)論

本文利用GPU來加速MapReduce構(gòu)成雙并行模型，說明將GPU和MapReduce二者相結(jié)合的原因，將GPU應(yīng)用到MapReduce過程中，實現(xiàn)多層次并行，研究了雙重并行環(huán)境下最短路徑的實現(xiàn)，加入了預(yù)處理和數(shù)據(jù)動態(tài)處理器。最后通過實驗進行驗證，結(jié)果表明，雙重并行環(huán)境下最短路徑的計算具有雙重并行的效果。

[1] 張凌潔,趙英.基于GPU的并行APSP問題的研究[J].電子設(shè)計工程,2012,20(17):15-18.

[2] 鈕 亮,張寶友.MapReduce求解物流配送單源最短路徑研究[J].電子技術(shù)應(yīng)用,2014,40(3):123-125.

[3] 楊 玲,李仁發(fā),唐 卓.基于MapReduce的單源最短路徑算法研究[J]. 微計算機信息, 2011(12):97-99.

[4] 王曉東.算法設(shè)計與分析[M].北京：清華大學(xué)出版社,2003.

[5] 郭釔汝.基于GPU集群系統(tǒng)的MapReduce編程模型研究[D].濟南：山東大學(xué),2014.

[6] 曾青華,袁家斌.基于MapReduce和GPU雙重并行計算的云計算模型[J].計算機與數(shù)字工程, 2013,41(3):333-336.

[7] 瞿李峰. 基于GPGPU的MapReduce高性能并行計算模型研究與應(yīng)用[D]. 桂林：桂林理工大學(xué), 2009.

[8] 張 凱,秦 勃,劉其成.基于GPU-Hadoop的并行計算框架研究與實現(xiàn)[J].計算機應(yīng)用研究,2014, 31(8):2548-2550.

Research on Shortest Path in Dual Parallel Environment

Sun Yuqiang, Li Yinyin, Gu Yuwan

(School of Information Science & Engineering,Changzhou University, Changzhou 213164, China)

Parallel problem and shortest path problem has become a hot research topic, traditional shortest path algorithm cannot meet the demand of the explosive growth of the data processing, especially when the network size is large, the computation time and storage space required is greatly increased.The emergence of MapReduce model, brings a new solution to solve the shortest path. GPU has powerful parallel computing capability and storage bandwidth, and CPU has obvious advantages.By studying MapReduce model and GPU implementation process analysis, pointed out the shortest path parallel method based on MapReduce model alone existing problems, and reduce the performance of the system.The innovation of this paper is combine MapReduce and GPU to form double parallel model, parallel preprocessing data, the data transfer and synchronization overhead for the shortest patht,increase data dynamic processor. Compared with the average speedup of performance evaluation index of parallel algorithm, the results show that the computation of the shortest path in double parallel environment improves the speedup.

shortest path; parallel computing; MapReduce; GPU; data dynamic processor

2016-10-14；

2016-11-17。

孫玉強(1956-),男，博士，教授,主要從事并行計算方向的研究。

1671-4598(2017)03-0195-02

10.16526/j.cnki.11-4762/tp.2017.03.053

TP393

A