一種矩陣相乘的并行算法實(shí)現(xiàn)與性能評(píng)測(cè)

苑 野 ， 于永澔

(哈爾濱工業(yè)大學(xué) 基礎(chǔ)與交叉科學(xué)研究院, 哈爾濱150080)

隨著多核處理器技術(shù)、高速網(wǎng)絡(luò)和分布式計(jì)算技術(shù)的發(fā)展，集群系統(tǒng)已經(jīng)成為高性能計(jì)算領(lǐng)域最重要的計(jì)算平臺(tái)[1].集群系統(tǒng)具有性能價(jià)格比高、可擴(kuò)展性好、高可用性、高利用率和易用性好等特點(diǎn).MPI(Message Passing Interface)[2]是面向并行編程環(huán)境下的一種基于消息傳遞的標(biāo)準(zhǔn)函數(shù)庫(kù)，被廣泛應(yīng)用于分布式存儲(chǔ)的可擴(kuò)展的并行計(jì)算機(jī)(Scalable Parallel Computers)和工作站集群(Networks of Workstations).MPI具有較高的通信性能、程序可移植性好、可擴(kuò)展性好、程序代碼實(shí)現(xiàn)靈活及高效統(tǒng)一的編程環(huán)境等特點(diǎn).由于集群系統(tǒng)具有典型的分布式存儲(chǔ)特征， 因此MPI編程模型已經(jīng)成為目前集群系統(tǒng)上主流的并行程序設(shè)計(jì)環(huán)境.

矩陣計(jì)算主要應(yīng)用于科學(xué)與工程計(jì)算領(lǐng)域，是科學(xué)計(jì)算的核心問(wèn)題.而矩陣相乘是矩陣計(jì)算最基本的運(yùn)算.用傳統(tǒng)的串行算法庫(kù)進(jìn)行矩陣相乘運(yùn)算[3-4]會(huì)受到矩陣規(guī)模、單機(jī)硬件性能(CPU速度、內(nèi)存大小、存儲(chǔ)器空間)等方面的限制.對(duì)串行算法進(jìn)行并行化處理，使其達(dá)到更高的運(yùn)算性能，是解決上述限制的最有效途徑.人們采用了各種方法對(duì)矩陣相乘進(jìn)行并行化處理，并取得了一定的進(jìn)展，主要包括基于順序矩陣直接相乘算法(行列劃分方法)、基于遞歸實(shí)現(xiàn)的塊矩陣相乘方法、基于二維網(wǎng)格實(shí)現(xiàn)的矩陣相乘算法(Cannon算法、脈動(dòng)陣列算法)和Strassen算法等.行列劃分算法是經(jīng)典的矩陣相乘算法中的一種，以其并行時(shí)間復(fù)雜性優(yōu)良、代碼簡(jiǎn)單且易于實(shí)現(xiàn)等優(yōu)勢(shì)使該方法備受研究者的重視.本文在集群環(huán)境下，使用SPMD計(jì)算模型及MPI消息傳遞技術(shù)對(duì)矩陣相乘的行列劃分方法進(jìn)行了并行化算法實(shí)現(xiàn)，并定量的對(duì)該并行算法的性能進(jìn)行了測(cè)試，實(shí)驗(yàn)表明此并行算法在一定矩陣規(guī)模下具有較好的加速性能及效率，優(yōu)于傳統(tǒng)的串行算法.

1 MPI編程技術(shù)

MPI是一種消息傳遞編程模型[5]，并已經(jīng)成為這種編程模型事實(shí)上的標(biāo)準(zhǔn).它不是一種編程語(yǔ)言，而是一個(gè)并行函數(shù)庫(kù).MPI標(biāo)準(zhǔn)函數(shù)庫(kù)為C語(yǔ)言和FORTRAN語(yǔ)言提供了通用的并行程序編程接口.一個(gè)MPI系統(tǒng)通常由一組函數(shù)庫(kù)、頭文件和相應(yīng)的運(yùn)行、調(diào)試環(huán)境組成.MPI并行程序通過(guò)調(diào)用MPI庫(kù)中的函數(shù)來(lái)完成消息傳遞.

1.1 MPI基本概念

1.1.1 進(jìn)程組(process group)

MPI程序全部進(jìn)程集合的一個(gè)有序子集.進(jìn)程組中的進(jìn)程被賦予一個(gè)惟一的序號(hào)(rank)，用于標(biāo)識(shí)該進(jìn)程.

1.1.2 通信器(communicator)

由一個(gè)進(jìn)程組和一個(gè)標(biāo)識(shí)構(gòu)成.在該進(jìn)程組中，進(jìn)程間可以相互通信.MPI程序中的所有通信必須在通信器中進(jìn)行.默認(rèn)的通信器是MPI_COMM_WORLD，所有啟動(dòng)的MPI進(jìn)程通過(guò)調(diào)用函數(shù)MPI_Init()包含在通信器中，每個(gè)進(jìn)程通過(guò)函數(shù)MPI_Comm_size()獲取通信器中的初始MPI進(jìn)程個(gè)數(shù).通信器可分為在同一進(jìn)程組內(nèi)通信的域內(nèi)通信器和在不同進(jìn)程組進(jìn)程間通信的域間通信器.

1.1.3 進(jìn)程序號(hào)(rank)

MPI程序中用于標(biāo)識(shí)進(jìn)程組或通信器中一個(gè)進(jìn)程的唯一編號(hào)，同一個(gè)進(jìn)程在不同的進(jìn)程組或通信器中可以有不同的序號(hào).MPI_PROC_NULL代表空進(jìn)程.

1.1.4 消息(message)

包括數(shù)據(jù)(data)和信封(envelope)兩部分.數(shù)據(jù)包含用戶將要傳遞的內(nèi)容，信封由接收進(jìn)程序號(hào)/發(fā)送進(jìn)程序號(hào)、消息標(biāo)號(hào)和通信器三部分組成.消息被封裝在“信封”中，然后經(jīng)緩沖區(qū)向網(wǎng)絡(luò)傳輸層打包發(fā)送.

1.1.5 MPI對(duì)象

MPI系統(tǒng)內(nèi)部定義的數(shù)據(jù)結(jié)構(gòu)，包括數(shù)據(jù)類型、通信器(MPI_Comm)、通信請(qǐng)求(MPI_Request)等，它們對(duì)用戶不透明.

1.1.6 MPI連接器(handles)

連接MPI對(duì)象的具體變量，用戶可以通過(guò)它訪問(wèn)和參與相應(yīng)的MPI對(duì)象的具體操作.

1.2 點(diǎn)對(duì)點(diǎn)通信

點(diǎn)對(duì)點(diǎn)通信是指在一對(duì)進(jìn)程之間進(jìn)行的消息收發(fā)操作，是MPI中最基本的通信模式.MPI提供阻塞型(blocking)和非阻塞型(non blocking)兩種類型的點(diǎn)對(duì)點(diǎn)通信函數(shù).阻塞型函數(shù)是指一個(gè)例程需等待操作完成才返回，返回后用戶可以重新使用調(diào)用中所占用的資源.非阻塞型函數(shù)是指一個(gè)例程不必等待操作完成便可以返回，返回后用戶不可重用所占用的資源.根據(jù)以上兩類通信函數(shù)的不同特點(diǎn)，MPI提供了四種不同的通信模式，分別是標(biāo)準(zhǔn)模式(standard mode)、緩沖模式(buffered mode)、同步模式(synchronous mode)和就緒模式(ready mode).

1.3 聚合通信

聚合通信是指在一個(gè)通信器內(nèi)的所有進(jìn)程同時(shí)調(diào)用同一個(gè)聚合通信函數(shù)而進(jìn)行的通信.聚合通信包括障礙同步(MPI_Barrier)、廣播(MPI_Bcast)、數(shù)據(jù)收集(MPI_Gather)、數(shù)據(jù)發(fā)散(MPI_Scatter)、數(shù)據(jù)轉(zhuǎn)置(MPI_Alltoall)和規(guī)約(MPI_Reduce).

2 矩陣乘法并行算法

集群上矩陣乘法并行算法采用了行列劃分方法、SPMD計(jì)算模型和基于MPI消息傳遞的并行處理技術(shù).假設(shè)A為m*k階矩陣，B為k*n階矩陣，C為m*n階矩陣，計(jì)算問(wèn)題C=A*B.令m=m`*p、n=n`*p，矩陣A=[A0tA1t…Ap-1t]，矩陣B=[B0B1…Bp-1]，矩陣A第i行的每個(gè)元素與矩陣B第j列的各元素分別相乘，并將乘積相加到矩陣C的第i行第j列的一個(gè)元素Ci,j，此時(shí)C=(Ci,j)=(AiBj).將j=0，1…，p-1存放在Pi中，使用p個(gè)處理機(jī)，每次每個(gè)處理機(jī)計(jì)算出一個(gè)Ci,j，需要p次完成.具體算法[6-7]如下：

begin

Mp1≡myid+1 mod p，mm1≡myid-1 mod p

for i=0 to p-1 do

l≡i+myid mod p

Cl=AB

If i≠p-1，send(B,mm1),recv(B,mp1)

endfor

endfor

在p=n2個(gè)處理器進(jìn)行n*n矩陣乘法時(shí)，并行時(shí)間的復(fù)雜性為O(n).廣播算法決定通信開(kāi)銷進(jìn)而支配通信時(shí)間，n*n矩陣通過(guò)獨(dú)立的消息分發(fā)到n2個(gè)從處理器上，每個(gè)從處理器向主處理器返回C的一個(gè)元素.其通信時(shí)間tcomm=n2(2tstartup+(2n+1)tdata)，其中tstartup是數(shù)據(jù)傳送的延遲或啟動(dòng)時(shí)間，tdata是數(shù)據(jù)傳輸返回時(shí)間[8].

3 實(shí)驗(yàn)驗(yàn)證

本文的硬件測(cè)試環(huán)境是8個(gè)節(jié)點(diǎn)組成的集群系統(tǒng)，采用Infiniband高速網(wǎng)絡(luò)互聯(lián)，每個(gè)節(jié)點(diǎn)配有1顆Intel Xeon 2.5 G處理器，32 G內(nèi)存，1 T SAS磁盤，GPFS共享文件系統(tǒng)，軟件環(huán)境是Red Hat Linux操作系統(tǒng)，編譯器為Intel C++ 13.0.1，MPI的版本為Intel MPI 4.1.

加速比和效率是衡量多處理機(jī)和單處理機(jī)系統(tǒng)相對(duì)性能的重要指標(biāo).把串行應(yīng)用程序在單處理機(jī)上的執(zhí)行時(shí)間和該程序并行化后在多處理機(jī)上的執(zhí)行時(shí)間的比值定義為加速比，它是并行算法可擴(kuò)展性的重要參數(shù).將加速比與CPU個(gè)數(shù)之間的比值定義為效率，它反映了在某一時(shí)間段內(nèi)，一個(gè)處理器真正用于計(jì)算的時(shí)間.設(shè)矩陣大小分別為1 200×1 200、4 000×4 000，8 000×8 000，各做5次實(shí)驗(yàn)，將5次計(jì)算時(shí)間的平均值作為執(zhí)行時(shí)間.表1為單處理機(jī)系統(tǒng)的串行程序執(zhí)行時(shí)間.表2為多處理機(jī)系統(tǒng)的并行程序執(zhí)行時(shí)間.圖1為矩陣并行程序運(yùn)行時(shí)間變化.圖2為不同矩陣規(guī)模下運(yùn)行時(shí)間比較.

表1單處理機(jī)的串行執(zhí)行時(shí)間

矩陣大小串行執(zhí)行時(shí)間1 200×1 2000.411 1214 000×4 0001.124 6448 000×8 0003.280 423

表2多處理機(jī)并行程序執(zhí)行時(shí)間

矩陣大小 并行執(zhí)行時(shí)間 2 節(jié)點(diǎn) 4 節(jié)點(diǎn) 8 節(jié)點(diǎn)1 200×1 200 0.244 172 0.147 231 0.276 6124 000×4 000 0.579 226 1.100 790 0.592 2958 000×8 000 2.228 761 1.129 427 0.576 136

圖1 矩陣并行程序運(yùn)行時(shí)間

圖2 不同矩陣規(guī)模下運(yùn)行時(shí)間比較

如圖1所示，可以看到在所有矩陣的多節(jié)點(diǎn)測(cè)試中，并行程序的運(yùn)行時(shí)間隨著矩陣規(guī)模不斷變大時(shí)，其運(yùn)行時(shí)間基本保持不斷的增加.然而在節(jié)點(diǎn)較多(如node=8時(shí))的并行環(huán)境下運(yùn)行時(shí)，其并行程序運(yùn)行時(shí)間隨矩陣規(guī)模變化不明顯.如在矩陣為4 000×4 000、8 000×8 000下，運(yùn)行時(shí)間基本保持不變.這主要是因?yàn)樵诔绦虻膱?zhí)行時(shí)間中，絕大部分的時(shí)間用于數(shù)據(jù)的通信而非用于真正的計(jì)算.由圖2可知，在矩陣規(guī)模很大時(shí)(當(dāng)矩陣為8 000×8 000)，其運(yùn)行時(shí)間隨著節(jié)點(diǎn)數(shù)的增加而不斷減少.其原因是用于計(jì)算的時(shí)間占了絕大部分，數(shù)據(jù)通信時(shí)間大量減少，并行計(jì)算的優(yōu)勢(shì)得到了體現(xiàn).表3為多處理機(jī)并行算法的加速比和效率.圖3為不同矩陣規(guī)模下加速比比較，圖4為不同矩陣規(guī)模下并行效率比較.圖5為矩陣規(guī)模在8 000階下的加速比.

表3多處理機(jī)并行算法的加速比和效率

矩陣大小 2 節(jié)點(diǎn) 4 節(jié)點(diǎn) 8 節(jié)點(diǎn)加速比 效率加速比 效率加速比效率1 200×1 2001.680.842.790.701.480.194 000×4 0001.940.971.020.261.900.248 000×8 0001.470.742.900.735.690.71

圖3 不同矩陣規(guī)模下加速比比較

圖4 不同矩陣規(guī)模下并行效率比較

圖5 矩陣規(guī)模在8 000階下的加速比

如圖3～5可知，該并行算法的在不同矩陣規(guī)模下，其加速比均大于1，這說(shuō)明此算法與傳統(tǒng)的串行算法相比具有較高的加速性能.當(dāng)矩陣規(guī)模較小時(shí)(如矩陣為1 200×1 200時(shí))，其加速比隨著節(jié)點(diǎn)數(shù)的增加表現(xiàn)為先迅速變大，然后逐漸變小.并行效率呈現(xiàn)逐漸下降的趨勢(shì).在node=4時(shí)獲得最大加速比2.79，此時(shí)的效率為70%.當(dāng)矩陣的規(guī)模較大時(shí)(如矩陣為8 000×8 000)，其加速比幾乎表現(xiàn)為線性增加，在node=8時(shí)獲得最大加速比5.69，而并行效率幾乎保持不變，基本維持的在72%左右.這說(shuō)明此種并行算法在矩陣規(guī)模較大的條件下，加速效果明顯，效率較高.

4 結(jié) 語(yǔ)

本文對(duì)集群計(jì)算環(huán)境下矩陣相乘問(wèn)題應(yīng)用SPMD計(jì)算模型和基于MPI消息傳遞技術(shù)實(shí)現(xiàn)了其并行算法，并通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法的有效性.與傳統(tǒng)的串行算法相比，結(jié)果證明此算法在一定的矩陣規(guī)模下具有較好的加速性能及效率.

參考文獻(xiàn)：

[1] CHAI L, LAI P, JIN H,etal. Designing an efficient kernel-level and user-level hybrid approach for mpi intra-node communication on muti-core systems[C]//ICPP’08:Proceedings of the 2008 37th International Conference on Parallel Processing，Washington DC: IEEE Computer Society, 2008.

[2] MPI: A Message-Passing Interface Standard[S].

[3] BLACKFORD L S, DEMMEL J, J DONGARRA,etal. An update set of basic linear algebra subprograms(BLAS)[J]. ACM Transactions on Mathematical Software，2002, 28(2): 135-151.

[4] COHN H, KLEINBERG R, SZEGEDY B,etal. Group-theoretic algorithms for matrix multiplication[C]//Proceedings of the 46th Annual Symposium on Foundations of Computer Science, 23-25 ，2005.

[5] MCQUILLAN J M, D WALDEN C. Some considerations for a high performance message-based interprocess communication system [J]. SIGOPS Oper.Syst.Rev., 1975, 9: 77-86.

[6] 張林波, 遲學(xué)斌. 并行算法導(dǎo)論[M]. 北京: 清華大學(xué)出版社，2006.

[7] 陸鑫達(dá). 并行程序設(shè)計(jì)[M]. 北京: 機(jī)械工業(yè)出版社, 2006.

[8] 徐紅波，胡 文，潘海為，等.高維空間范圍查詢并行算法研究[J].哈爾濱商業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，29(1)：73-75，111.