賀雨晴 張楠 李云東
摘要:矩陣運算是工程數(shù)值計算中一種常見的運算方式。大量的高維矩陣運算對數(shù)學計算提出了新的要求。該文提出了三種模式下的矩陣劃分并行計算,分別是按行,按列,按塊劃分。運用MPI并行計算技術,比較出了適合工程上計算的模式,得到了按行劃分算法的優(yōu)勢。
關鍵詞:劃分,矩陣運算,并行,MPI
中圖分類號:TP393 文獻標識碼:A 文章編號:1009-3044(2015)20-0164-04
Parallel Computing Method of Matrix-vector Multiplication with Different Partition for Line,Column and Block
HE Yu-qing, ZHANG Nan, LI Yun-dong
(China University of Petroleum(East China), Qingdao 266580, China)
Abstract: Matrix operation is a common numerical methods in engineering.The high dimension matrix raise a claim for mathematics. There be three modes by which matrix is divided . according to the column, the block line. Using the MPI parallel computing technology, the classification algorithm of line edge is suitable for engineering calculation comparison with model.
Key words: divide; matrix multiplication; parallel; MPI
1 概述
1.1 并行計算簡介
并行計算(Parallel Computing)是指同時使用多種計算資源解決計算問題的過程,是提高計算機系統(tǒng)計算速度和處理能力的一種有效手段。它的基本思想是用多個處理器來協(xié)同求解同一問題,即將被求解的問題分解成若干個部分,各部分均由一個獨立的處理機來并行計算。現(xiàn)實社會中,越來越多的數(shù)據(jù)信息需要計算機處理,串行計算機程序技術已經(jīng)不能滿足人們的需求,并行計算會越來越受到人們的青睞。
1.2矩陣向量相乘
矩陣向量相乘是數(shù)學以及工程中經(jīng)常遇到的一種計算方式。矩陣計算因其維數(shù)增大而造成的計算量增大是計算科學中需要進一步解決的問題。利用并行計算方法,將矩陣向量進行分發(fā),使每個進程同時進行計算,將會大大減少計算的時間,提高計算效率。
2并行矩陣向量相乘原理
矩陣并行計算時,將矩陣進行按行、列、塊三種方式進行劃分,矩陣和向量按進程個數(shù)進行分發(fā),接收矩陣和向量的進程做相應的運算,最后將結果進行規(guī)約綜合。本文只討論進程個數(shù)恰能完全將矩陣向量平均分配的情況。
2.1按行劃分矩陣
矩陣向量相乘時,我們考慮nxn維矩陣A在n個進程間劃分的情況。將計算機進程編號為
考慮P(p
2.2按列劃分矩陣
按列進行劃分是對每一行進行劃分然后發(fā)送到每個進程上。我們考慮
2.3按塊劃分矩陣
假設
3 并行算法的實現(xiàn)
程序設計流程圖:
圖1
3.1按行劃分矩陣向量相乘
程序要點:
1) 主進程調(diào)用MPI_Send將向量發(fā)給各個進程;
2) 其余進程調(diào)用 MPI_Recv 接收主進程發(fā)送的向量;
3) 各進程調(diào)用 MPI_Scatter 按行共享主進程中的矩陣;
4) 各個進程進行矩陣向量相乘;
5) 各進程調(diào)用MPI_Gather將所得向量各個分量聚集到主進程上,得到最終計算結果。
3.1.1 按行劃分的算法實現(xiàn)
實現(xiàn)按行劃分的矩陣向量乘法的程序關鍵代碼如下:
if(rank==0)
{ for(sendto=0;sendto if(sendto==0){ copy(localX,X,n); } else{MPI_Send(X,n,MPI_INT,sendto,1,MPI_COMM_WORLD); }}} //接收數(shù)據(jù) else {MPI_Recv(localX,n,MPI_INT,0,1,MPI_COMM_WORLD,MPI_STATUS_IGNORE); } //分發(fā)矩陣 MPI_Scatter(A,localN,MPI_INT,localA,localN,MPI_INT,0,MPI_COMM_WORLD); //計算 MatrixMul(localA,EverCorNumLine,n,localX,localR); MPI_Gather(localR,EverCorNumLine,MPI_INT,R,EverCorNumLine,MPI_INT,0,MPI_COMM_WORLD); 3.2按列劃分矩陣向量相乘 程序要點: 1) 主進程按列劃分矩陣及向量,記錄自身計算所需矩陣分量及向量分量并 調(diào)用MPI_Send將各矩陣分量及向量分量發(fā)給相應進程 2) 其余進程調(diào)用 MPI_Recv 接收主進程發(fā)送的矩陣分量及向量分量 3) 各個進程進行矩陣向量相乘 4) 主進程以外的其余進程調(diào)用MPI_Send將計算結果發(fā)給主進程 5) 主進程調(diào)用 MPI_Recv 接收各向量并與自身結果進行運算,得到最終計算結果。 3.1.2 按列劃分的算法實現(xiàn) 實現(xiàn)按列劃分的矩陣向量乘法的程序關鍵代碼如下: if(rank==0) { for(i=0,sendto=0;i {if(sendto==0){ for(j=0;j< localn && k localA[k]=A[i]; }} else{ MPI_Send(A+i,localn,MPI_INT,sendto,0,MPI_COMM_WORLD); i+=localn; }} //分發(fā)向量 for(i=0,sendto=0;i if(sendto==0){ for(j=0;j< localn ;j++,i++){ localX[j]=X[i]; }} else{ MPI_Send(X+i,localn,MPI_INT,sendto,1,MPI_COMM_WORLD); i+=localn; } sendto++;}} //接收數(shù)據(jù) else {for(i=0;i MPI_Recv(localA+i,localn,MPI_INT,0,0,MPI_COMM_WORLD,MPI_STATUS_IGNORE); i+=localn; } MPI_Recv(localX,localn,MPI_INT,0,1,MPI_COMM_WORLD,MPI_STATUS_IGNORE); } //計算 MatrixMul(localA,n, localn ,localX,localR); if(rank==0) {int* recvR=new int[n]; for(int core=0,k=0;core {if(core==0)
copy(R,localR,n);
else{
MPI_Recv(recvR,n,MPI_INT,core,3,MPI_COMM_WORLD,MPI_STATUS_IGNORE);
addcopy(R,recvR,n); }}
free(recvR); }
else
{MPI_Send(localR,n,MPI_INT,0,3,MPI_COMM_WORLD); }
3.3按塊劃分矩陣向量相乘
程序要點:
1) 主進程按塊劃分矩陣及向量,記錄自身計算所需矩陣分量及向量分量并調(diào)用MPI_Send將各矩陣分量及向量分量發(fā)給相應進程;
2) 其余進程調(diào)用 MPI_Recv 接收主進程發(fā)送的矩陣分量及向量分量;
3) 各個進程進行矩陣向量相乘;
4) 主進程以外的其余進程調(diào)用MPI_Send將計算結果發(fā)給主進程;
5) 主進程調(diào)用 MPI_Recv 接收各向量并將全部結果整合進行運算,得到最終計算結果。
3.3.1 按塊劃分的算法實現(xiàn)
實現(xiàn)按塊劃分的矩陣向量乘法的程序關鍵代碼如下:
if(rank==0)
{ for(i=0;i if(sendto==0){ for(j=0;j< localn && k localA[k]=A[i]; }} else{ MPI_Send(A+i,localn,MPI_INT,sendto,0,MPI_COMM_WORLD); i+=localn; } sendto=(sendto+1)%size; } //分發(fā)向量 int s; for(s=0,sendto=0;s for(i=0;i if(sendto==0){ for(j=0;j< localn ;j++,i++){ localX[j]=X[i]; }} else{ MPI_Send(X+i,localn,MPI_INT,sendto,1,MPI_COMM_WORLD); i+=localn; } sendto++;}}} //接收數(shù)據(jù) else{ for(i=0;i MPI_Recv(localA+i,localn,MPI_INT,0,0,MPI_COMM_WORLD,MPI_STATUS_IGNORE); i+=localn; } MPI_Recv(localX,localn,MPI_INT,0,1,MPI_COMM_WORLD,MPI_STATUS_IGNORE); } //計算 MatrixMul(localA,localX,localR, localn ); if(rank==0) {int* recvR=new int [localn]; for(int s=0,core=0,k=0;s {for(k=0;k if(core==0) copy(R,localR, localn ); else{ MPI_Recv(recvR, localn ,MPI_INT,core,3,MPI_COMM_WORLD,MPI_STATUS_IGNORE); if(k==0) copy(R+s* localn ,recvR, localn ); else addcopy(R+s* localn ,recvR, localn ); }}} free(recvR); } else{MPI_Send(localR, localn ,MPI_INT,0,3,MPI_COMM_WORLD); } 4 程序運行結果分析與討論 進行上機實驗,開發(fā)環(huán)境為Microsoft Visual Studio 2010(旗艦版),最終計算結果如下: 表1 256維計算結果 [\&串行時間/s\&4核行時間/s(效率)\&16核行時間/s(效率)\&64核行時間/s(效率)\&行劃分\&0.001495\&0.001274(29.3%)\&0.093213(0.100%)\&0.204984(0.011%)\&列劃分\&0.001446\&0.004101(8.81%)\&0.441630(0.020%)\&1.734290(0.001%)\&塊劃分\&0.000898\&0.006152(3.65%)\&0.043074(0.130%)\&0.066883(0.021%)\&] 表2 512維計算結果 [\&串行時間/s\&4核行時間/s(效率)\&16核行時間/s(效率)\&64核行時間/s(效率)\&行劃分\&0.006131 \&0.004233 (36.2%)\&0.142088 (0.270%)\&0.405545 (0.024%)\&列劃分\&0.005633 \&0.004505 (31.2%)\&0.724691(0.049%)\&3.225060 (0.003%)\&塊劃分\&0.003389 \&0.005100(16.6%)\&0.166638(0.127%)\&0.309620(0.017%)\&]
表3 1024維計算結果
[\&串行時間/s\&4核行時間/s(效率)\&16核行時間/s(效率)\&64核行時間/s(效率)\&行劃分\&0.022572 \&0.015088 (37.4%)\&0.407754(0.346%)\&0.828063 (0.043%)\&列劃分\& 0.022426 \&0.019317 (29.0%)\&1.646941 (0.085%)\&5.767899 (0.006%)\&塊劃分\&0.013781 \&0.015392 (22.3%)\&0.146327 (0.588%)\&0.715611(0.030%)\&]
表4 2048維計算結果
[\&串行時間/s\&4核行時間/s(效率)\&16核行時間/s(效率)\&64核行時間/s(效率)\&行劃分\&0.088634 \&0.051404 (43.1%)\&0.847224(0.654%)\&1.453918 (0.095%)\&列劃分\& 0.086840\& 0.045623 (47.6%)\&3.689239(0.147%)\&10.493637(0.013%)\&塊劃分\&0.051793\&0.035837(36.1%)\&0.177838(1.82%)\&0.734577(0.11%)\&]
表5 4096維計算結果
[\&串行時間/s\&4核行時間/s(效率)\&16核行時間/s(效率)\&64核行時間/s(效率)\&行劃分\&0.208891 \&0.092929 (98.5%)\&0.280809(1.53%)\&1.021800(0.227%)\&列劃分\&0.336603 \&0.093898 (89.6%)\&4.368886 (0.482%)\&22.938396(0.023%)\&塊劃分\&0.370550 \&0.094089 (56.2%)\&1.510753 (4.65%)\&2.546774(0.319%)\&]
圖1 按列劃分加速比增長關系
圖2 按行劃分加速比增長關系
圖3 按塊劃分加速比增長關系圖
5結論
通過對上述圖表分析,我們可得到以下結論:
隨著維數(shù)的增長,三種劃分方式加速比和效率都逐漸增長,但所用的核數(shù)較少時,加速比和效率較為明顯,因為數(shù)據(jù)的分發(fā)需要耗費一定量時間,當核數(shù)目較多時,分發(fā)矩陣需要的時間將會增大。
三種分發(fā)方式中,隨著維數(shù)的增高,按行劃分是最有效的方法。按列劃分在分發(fā)時需要分發(fā)的次數(shù)為維數(shù)的倍數(shù),分發(fā)的時間將大大增加。按塊劃分需要將矩陣進行塊劃分。然后再進行分發(fā),和列劃分一樣,也是增大了時間的消耗。
在工程計算中,當矩陣維數(shù)較大時,可以采取按行劃分的方式大大增加計算速度,而當矩陣維數(shù)較小時,建議使用串行算法。
參考文獻:
[1] 朱建偉,劉榮.多線程并行快速求解e 值的六種方法[J].現(xiàn)代計算機,2013(6).
[2] 多核系列教材編寫組.多核程序設計[M]. 北京. 清華大學出版社,2007.
[3] 帕切克.并行程序設計導論[M].鄧倩妮,譯.北京機械工業(yè)出版社,2012.