国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

行列塊不同劃分機制下矩陣向量相乘的并行計算方法

2015-10-19 13:49賀雨晴張楠李云東
電腦知識與技術 2015年20期
關鍵詞:劃分

賀雨晴 張楠 李云東

摘要:矩陣運算是工程數(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個進程間劃分的情況。將計算機進程編號為。則每一個進程都會存儲1xn維矩陣。進程會存儲。并且負責計算。向量C的存儲方法與B相同。

考慮P(p維矩陣,每個進程的矩陣要與向量B相乘,所得的向量C與向量B的乘法類似。所得到的向量即為所求。通信時間為O(),計算時間為O()。

2.2按列劃分矩陣

按列進行劃分是對每一行進行劃分然后發(fā)送到每個進程上。我們考慮維矩陣A在n個進程間劃分的情況。將計算機進程編號為-1。對于矩陣的第一行,進行劃分,進程接收到元素的為,每一行劃分后,進程接收到的元素為。進程做的計算為,每一個進程都會得到一個向量,將每一個向量所對應的元素相加,即得到最終的向量。

2.3按塊劃分矩陣

假設等于n,將矩陣劃分成不同的矩陣塊,每一個矩陣塊上的矩陣為維。將劃分的矩陣塊發(fā)送到每一個進程,進程上進行維矩陣與的乘法運算。然后將計算同一行的矩陣塊的進程結果相加,于同一列矩陣塊相組合,得到最終的結果。

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.

猜你喜歡
劃分
礦井水文地質(zhì)的劃分及對防治水工作的建議
法律視角下的惡意刷單之損失責任劃分
法律視角下的惡意刷單之損失責任劃分
VR新聞及對媒體融合轉型的啟示
花崗巖風化帶的劃分及工程評價
關于東北地區(qū)民族文化區(qū)劃分的探討
線性時間選擇問題的教學探討
全概率公式的應用
劃分格及其應用
小組合作學習模式在高中信息技術教學中的運用