苑 野 ， 于永澔

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

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

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

1 MPI編程技術(shù)

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

1.1 MPI基本概念

1.1.1 進程組(process group)

MPI程序全部進程集合的一個有序子集.進程組中的進程被賦予一個惟一的序號(rank)，用于標識該進程.

1.1.2 通信器(communicator)

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

1.1.3 進程序號(rank)

MPI程序中用于標識進程組或通信器中一個進程的唯一編號，同一個進程在不同的進程組或通信器中可以有不同的序號.MPI_PROC_NULL代表空進程.

1.1.4 消息(message)

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

1.1.5 MPI對象

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

1.1.6 MPI連接器(handles)

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

1.2 點對點通信

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

1.3 聚合通信

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

2 矩陣乘法并行算法

集群上矩陣乘法并行算法采用了行列劃分方法、SPMD計算模型和基于MPI消息傳遞的并行處理技術(shù).假設(shè)A為m*k階矩陣，B為k*n階矩陣，C為m*n階矩陣，計算問題C=A*B.令m=m`*p、n=n`*p，矩陣A=[A0tA1t…Ap-1t]，矩陣B=[B0B1…Bp-1]，矩陣A第i行的每個元素與矩陣B第j列的各元素分別相乘，并將乘積相加到矩陣C的第i行第j列的一個元素Ci,j，此時C=(Ci,j)=(AiBj).將j=0，1…，p-1存放在Pi中，使用p個處理機，每次每個處理機計算出一個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個處理器進行n*n矩陣乘法時，并行時間的復(fù)雜性為O(n).廣播算法決定通信開銷進而支配通信時間，n*n矩陣通過獨立的消息分發(fā)到n2個從處理器上，每個從處理器向主處理器返回C的一個元素.其通信時間tcomm=n2(2tstartup+(2n+1)tdata)，其中tstartup是數(shù)據(jù)傳送的延遲或啟動時間，tdata是數(shù)據(jù)傳輸返回時間[8].

3 實驗驗證

本文的硬件測試環(huán)境是8個節(jié)點組成的集群系統(tǒng)，采用Infiniband高速網(wǎng)絡(luò)互聯(lián)，每個節(jié)點配有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.

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

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

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

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

矩陣大小 并行執(zhí)行時間 2 節(jié)點 4 節(jié)點 8 節(jié)點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 矩陣并行程序運行時間

圖2 不同矩陣規(guī)模下運行時間比較

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

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

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

4 結(jié) 語

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

參考文獻：

[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] 陸鑫達. 并行程序設(shè)計[M]. 北京: 機械工業(yè)出版社, 2006.

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