孫玉強(qiáng), 李銀銀, 顧玉宛

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

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

孫玉強(qiáng), 李銀銀, 顧玉宛

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

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

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

0 引言

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

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

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

1 研究背景

1.1 最短路徑概述

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

1.2 MapReduce模型

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

1.3 GPU

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

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

2.1 雙重并行計(jì)算的提出

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

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

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

2.2 MapReduce和GPU并行模型

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

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

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

前期處理過程：

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

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

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

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

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

圖3 MapReduce和GPU雙重并行處理機(jī)制

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

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

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

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

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

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

表1 運(yùn)行時(shí)間對(duì)比表

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

4 結(jié)論

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

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

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

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

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

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

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

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

[8] 張 凱,秦 勃,劉其成.基于GPU-Hadoop的并行計(jì)算框架研究與實(shí)現(xiàn)[J].計(jì)算機(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。

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

1671-4598(2017)03-0195-02

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

TP393

A