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

魯　金，馬　可，高　劍

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

?

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

魯金，馬可，高劍

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

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

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

0　引言

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

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

1　MPI并行

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

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

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

2　卷積計(jì)算的并行模型

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

(1)

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

圖1　卷積計(jì)算

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

圖4　矩陣分割

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

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

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

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

圖5　矩陣分割

4)通過MPI_Barrier同步；

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

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

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

2.2基于矩陣分割的MPI模型

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

圖3　矩陣分割

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

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

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

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

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

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

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

圖6　并行卷積計(jì)算流程圖

3　實(shí)驗(yàn)性能分析

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

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

4　結(jié)束語

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

圖7　卷積計(jì)算效率對(duì)比

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

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

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

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

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

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

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

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

[8]鐘光清，鄭靈翔. 一種基于循環(huán)并行模式的多核優(yōu)化方法[J], 廈門大學(xué)學(xué)報(bào)(自然科學(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ù)先研究資助項(xiàng)目(40405040301)。

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

1671-4598(2016)01-0292-03

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

TP311

A