雙重并行環境下最短路徑的研究

孫玉強, 李銀銀, 顧玉宛

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

雙重并行環境下最短路徑的研究

孫玉強, 李銀銀, 顧玉宛

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

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

最短路徑；并行計算；MapReduce；GPU；數據動態處理器

0 引言

最短路徑問題是數學界和計算機科學中的一個重要的研究課題，在數學建模的基礎上，解決了城市規劃、物流、交通管理、數字導航等領域的實際問題[1]。并行計算為最短路徑提供了一種新的解決方案，尤其是在動態網絡中最短路徑的處理中。

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

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

1 研究背景

1.1 最短路徑概述

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

1.2 MapReduce模型

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

1.3 GPU

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

2 雙重并行環境下最短路徑的設計

2.1 雙重并行計算的提出

GPU和MapReduce結合的原因如下：

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

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

2.2 MapReduce和GPU并行模型

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

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

2.3 MapReduce和GPU雙重并行最短路徑實現

前期處理過程：

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

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

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

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

針對上述問題進行改進，圖3顯示了MapReduce和GPU的雙并行處理機制，GPU嵌入Hadoop，結合GPU和多核心CPU資源。在實現時，或因為CPU和GPU的數據傳輸和同步開銷太大，不能發揮GPU的優點。為此添加數據動態處理器，有了動態數據處理器，能夠實時監測計算節點GPU內存，數據的動態分解與組合，確保GPU計算最適合的數據，GPU速度優化。

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

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

當用戶程序調用Map函數時，讀取本地文件(key-value形式)，產生輸出結果后，數據分片函數將輸出記錄分割成幾個不同的塊，具體過程如下：

首先，任務通過MapReduce機制分發，將數據傳輸到工作節點，實現第一級多節點并行，然后基于節點的配置每個節點使用GPU等并行方式實現第二級并行，工作節點基于任務的大小和當前節點的GPU性能將數據發送到數據動態處理器。動態數據處理器分割或組合數據以創建滿足GPU功能(確保高速、全負載GPU操作)的數據塊，數據被發送到GPU處理[8]。最后，GPU計算結果被傳輸到主機內存進行后續處理，這種多級的處理機制可顯示GPU的計算能力。

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

3 實驗結果

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

表1 運行時間對比表

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

4 結論

本文利用GPU來加速MapReduce構成雙并行模型，說明將GPU和MapReduce二者相結合的原因，將GPU應用到MapReduce過程中，實現多層次并行，研究了雙重并行環境下最短路徑的實現，加入了預處理和數據動態處理器。最后通過實驗進行驗證，結果表明，雙重并行環境下最短路徑的計算具有雙重并行的效果。

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

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

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

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

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

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

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

[8] 張 凱,秦 勃,劉其成.基于GPU-Hadoop的并行計算框架研究與實現[J].計算機應用研究,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