魯　金，馬　可，高　劍

(西安電子工程研究所，西安　710100)

?

基于MPI的卷積計算并行實現(xiàn)

魯金，馬可，高劍

(西安電子工程研究所，西安710100)

針對傳統(tǒng)的卷積并行計算模型中，存在著大量的消息傳遞，負(fù)載不均衡等問題;提出一種新的基于MPI同步模型的并行卷積算法;該模型采用消息傳遞的方式進(jìn)行進(jìn)程間的通信，同時有效平衡負(fù)載，避免大量的消息傳遞;通過分析該模型的加速比和效率，實驗結(jié)果表明，此方法顯著提高了并行效率和長序列的運(yùn)算速度，充分發(fā)揮了節(jié)點間分布式存儲和多核并行處理的優(yōu)勢，是一種有效可行的并行策略。

卷積計算；并行；消息傳遞接口；負(fù)載平衡

0　引言

近年來，受到程工藝的限制，單核處理器的性能已接近極限，通過提高單處理器的時鐘頻率來提高計算機(jī)性能的方法越來越難以達(dá)到良好的效果。因此，多核技術(shù)成為CPU制造商顯著提高處理器的性能的共同解決方案[1-2]。多核設(shè)備為應(yīng)用程序提供了并行計算的硬件平臺，使計算機(jī)的計算速度得到了巨大提高。而另一方面，在數(shù)字信號處理領(lǐng)域中，要處理的數(shù)據(jù)量越來越龐大，實時性的要求也越來越高，，將并行處理的思想運(yùn)用在信號處理中，構(gòu)建一個具有并行性的系統(tǒng)，必將是一個未來發(fā)展的趨勢。

卷積計算作為信號與系統(tǒng)時域分析的一種重要方法。在科學(xué)計算領(lǐng)域中起著重要的作用[3]，廣泛應(yīng)用于通信，航空航天，生物醫(yī)學(xué)工程，雷達(dá)信號處理等工程領(lǐng)域。因此，將并行化的思想應(yīng)用在卷積計算中，從而大大加快卷積計算的速度，提高卷積計算的效率，具有重要的研究意義。

1　MPI并行

并行計算是指在并行系統(tǒng)上，將一個大的任務(wù)分解為多個小的子任務(wù)，分配給不同計算單元上，各個計算單元之間相互協(xié)同，并行地執(zhí)行各個子任務(wù)，最后匯合同步，從而達(dá)到加速求解任務(wù)的目的。

消息傳遞接口MPI[4](message passing interface，MPI)是目前最流行的并行編程模型。它并不是一種新的編程語言，而是一個可以被C、C++和Fortran等程序調(diào)用的函數(shù)庫。不僅具有易移植、高效率等多種優(yōu)點，而且可以廣泛應(yīng)用于分布式系統(tǒng)中。在MPI程序中，運(yùn)行在一個核上的程序稱為一個進(jìn)程。兩個進(jìn)程可以通過調(diào)用函數(shù)來進(jìn)行通信：一個進(jìn)程調(diào)用發(fā)送函數(shù)，另一個調(diào)用接收函數(shù)。將消息傳遞的實現(xiàn)稱為消息傳遞接口，即MPI。

MPI有多種免費(fèi)的、高效的實現(xiàn)版本，包括MPICH，LAM和MPI/Pro等，其中MPICH是目前最主流的一種版本，大多并行計算機(jī)廠商都提供對它的支持。

2　卷積計算的并行模型

假設(shè)x(n)是長度為N1的序列，h(n)是長度為N2的序列，則由x(n)和h(n)卷積所得的結(jié)果y(n)可表示為：

(1)

為了能更直觀地理解卷積公式，如圖1所示，固定h(n)序列不動，將x(n)序列以x(0)作對折，y(0)等于h(0)和x(0)的乘積，然后將x(n)序列往右平移一位，再作乘積相加，對應(yīng)y(1)，并以此類推，求的y(2)，y(3)，y(4)… 。

圖1　卷積計算

2.1傳統(tǒng)基于y(n)分配的MPI模型

圖4　矩陣分割

傳統(tǒng)的基于MPI卷積計算的并行方法是根據(jù)y(n)來分配任務(wù)，如圖2所示，基本思想如下：

1)把x(n), h(n)分別廣播給N個進(jìn)程，主進(jìn)程申請N1+N2-1個存儲空間，用以存放計算結(jié)果y(n)；

2)為每個進(jìn)程申請ceil((N1+N2-1)/N)個存儲空間temp(ceil為向上取整)；

3)以循環(huán)分配的方式劃分每個進(jìn)程的任務(wù)y(k)如圖1所示，第k個處理器只計算y(k)，y(k+N)，y(k+2N)，y(k+3N)…，并通過如上計算公式將計算結(jié)果按順序放在該進(jìn)程申請的存儲空間temp中；

圖5　矩陣分割

4)通過MPI_Barrier同步；

5)通過循環(huán)(N1+N2-1)/N次，利用MPI_Gather[5-6]依次把temp中的數(shù)據(jù)搬移到主進(jìn)程y中。

圖2　每個進(jìn)程的任務(wù)分配

雖然傳統(tǒng)的卷積并行計算相對于普通的串行計算在一定情況下的速度有一定提升，但也存在一些不足：1.負(fù)載不均衡，每個y(n)的計算量不同，如y(0)只需一次乘法計算，y(1)需要兩次乘法和一次加法計算，而y(3)需要3次乘法和兩次加法計算，這會增加單個進(jìn)程的空閑時間；2.進(jìn)程間通信量大，進(jìn)程間的通信嚴(yán)重影響執(zhí)行的效率[7]。整個計算過程中，除了初始化時的廣播外，還有(N1+N2-1)/N次的聚集(gather)操作，花費(fèi)了大量的額外開銷。

2.2基于矩陣分割的MPI模型

為了解決上述傳統(tǒng)卷積并行計算存在的一些不足，本文提出一種基于矩陣分割的MPI模型。為了便于分析，我們建立一個由N1個x(n)序列和N2個h(n)序列組成的N1*N2矩陣模型，如圖3：可以直觀的看出，卷積結(jié)果y(k)正好等于第k條斜對角線的所有元素相加。這樣，就把求卷積的過程轉(zhuǎn)化為求斜對角線上的元素，并相加。

圖3　矩陣分割

以并行方式在求矩陣斜對角線元素的和時，本文按圖4方式劃分并行任務(wù)，即按列將整個N1*N2矩陣等分成N個子塊(N為進(jìn)程的個數(shù))，不能等分的向上取整(如：列數(shù)N2=100，進(jìn)程數(shù)N=8，則前7個子塊每塊連續(xù)分配13列，第8塊分配最后9列)。然后將每一塊分配給N個進(jìn)程，每個進(jìn)程求解對應(yīng)子塊的斜對角線元素的和，如圖5所示。最后通過集合通信的方式將每個子塊已經(jīng)求的結(jié)果作歸約[8]計算。從而就求出了整個矩陣斜對角線元素的和，即卷積的最終結(jié)果。整個計算流程如圖6所示，具體步驟如下：

1)將x(n)廣播給N個進(jìn)程；

2)將h(n)按塊等分成N塊(不能等分的向上取整)，再將每一塊依次廣播給N個進(jìn)程；

3)為每個進(jìn)程申請N1+N2-1個存儲空間y，并初始化為0；

4)每個進(jìn)程計算對應(yīng)的子塊中斜對角線元素的和，并賦值給對應(yīng)的y(n)，如圖3所示。

5)通過MPI_Reduce將每個進(jìn)程的y(n)相加，最后的結(jié)果就是x(n)和h(n)的卷積和y(n)。

可以看到，在整個計算過程中，每個進(jìn)程的獨立性較強(qiáng)，僅在最后作數(shù)據(jù)歸約計算的時候又一次集合通信，大大降低了進(jìn)程間的通信量。另外，當(dāng)N2能被N整除時，每個進(jìn)程的任務(wù)負(fù)載完全相同。這也大大減少了進(jìn)程為了同步而等待所消耗的開銷。

圖6　并行卷積計算流程圖

3　實驗性能分析

為了測試這種編程模型的性能，將其對串行模型、傳統(tǒng)的MPI并行模型進(jìn)行模擬數(shù)值實驗，實驗環(huán)境是：CPU：intel i7@3.4 GHz；內(nèi)存4．00 GB；操作系統(tǒng)：linux Fedora 17；MPI函數(shù)庫：MPICH2。在固定處理器數(shù)目的條件下(P=8)選取不同的序列長度作等長卷積，對本文基于矩陣分割的MPI算法和傳統(tǒng)基于y(n)分配的MPI算法、普通串行算法在執(zhí)行時間方面進(jìn)行了實驗測試，運(yùn)行時間如圖7所示。

由圖6的實驗數(shù)據(jù)可知，隨著卷積序列長度的增大，尤其當(dāng)序列長度大于1 024點以后，基于矩陣分配的MPI算法有明顯的效率提升，充分證明該模型具有很高的可行性。

4　結(jié)束語

通過對不同長度作卷積計算的測試，實驗表明，本文提出的基于矩陣分割的MPI算法具有更高的執(zhí)行效率，計算時間

圖7　卷積計算效率對比

大大縮短，更加充分發(fā)揮節(jié)點間分布式存儲和多核并行計算的優(yōu)勢。在多核處理器環(huán)境下該模型可以有效提高并行計算性能，是一種高效可行的并行編程策略。但當(dāng)序列長度大到一定的值時，在時域上作卷積并行計算效果并不明顯，這時應(yīng)該考慮轉(zhuǎn)化到頻域中再作并行FFT的計算。

[1]Michael J.Quin. Parallel Programming in C with MPI and OpenMP[M]. 北京:清華大學(xué)出版社, 2005.

[2]Calvin Lin, Lawrence Snyder. 并行程序設(shè)計原理[M]. 北京: 機(jī)械工業(yè)出版社, 2009.

[3]章隆兵，吳少剛，蔡飛. PC機(jī)群上共享存儲與消息傳遞的比較[J]. 軟件學(xué)報，2004(6)：842-849.

[4]Peter S.Pacheco. 并行程序設(shè)計導(dǎo)論[M]. 北京: 機(jī)械工業(yè)出版社, 2013.

[5]Fayez Gebali. Mahafza. 算法與并行計算[M]. 北京: 清華大學(xué)出版社, 2012.

[6]Snir M, Otto S, HussLederman S, Walker D, Songarra J, MPI: The Complete Reference,[M]. London: MIT Press, 1996.

[7]曹振南．高性能計算的性能評測與性能優(yōu)化[D]．北京：北京科技大學(xué)，2003.

[8]鐘光清，鄭靈翔. 一種基于循環(huán)并行模式的多核優(yōu)化方法[J], 廈門大學(xué)學(xué)報(自然科學(xué)版), 2010(6)：789-792.

Implementation of Parallel Convolution Based on MPI

Lu Jin, Ma Ke, Gao Jian

(Xi’an Electronic Engineering Research Institute, Xi’an710100,China)

Convolution computing plays an important role in scientific computing. There exist massive message passing, load-unbalancing in traditional MPI model. Concerning this question, a new parallel convolution based on MPI model was proposed in this paper. This model prevents massive message passing, and keeps load-balancing. By analyzing the speedup ratio and efficiency, the experimental result shows that the new MPI parallel programming obviously promotes parallel efficiency and large-scale sequence’s speed, which exerts the advantages of distributional memory between nodes and parallel computing. It is an effective and feasible parallel strategy.

convolution computing; parallel; MPI; load-balancing

2015-08-05；

2015-09-11。

武器裝備預(yù)先研究資助項目(40405040301)。

魯金(1988-)，男，浙江杭州人，碩士，工程師，主要從事并行計算在現(xiàn)代雷達(dá)中的應(yīng)用方向的研究。

1671-4598(2016)01-0292-03

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

TP311

A