行列塊不同劃分機(jī)制下矩陣向量相乘的并行計(jì)算方法
2015-10-19 13:49:18賀雨晴張楠李云東
電腦知識(shí)與技術(shù) 2015年20期
賀雨晴 張楠 李云東
摘要：矩陣運(yùn)算是工程數(shù)值計(jì)算中一種常見的運(yùn)算方式。大量的高維矩陣運(yùn)算對(duì)數(shù)學(xué)計(jì)算提出了新的要求。該文提出了三種模式下的矩陣劃分并行計(jì)算，分別是按行，按列，按塊劃分。運(yùn)用MPI并行計(jì)算技術(shù)，比較出了適合工程上計(jì)算的模式，得到了按行劃分算法的優(yōu)勢(shì)。
關(guān)鍵詞：劃分，矩陣運(yùn)算，并行，MPI
中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 并行計(jì)算簡(jiǎn)介
并行計(jì)算（Parallel Computing）是指同時(shí)使用多種計(jì)算資源解決計(jì)算問題的過程，是提高計(jì)算機(jī)系統(tǒng)計(jì)算速度和處理能力的一種有效手段。它的基本思想是用多個(gè)處理器來協(xié)同求解同一問題，即將被求解的問題分解成若干個(gè)部分，各部分均由一個(gè)獨(dú)立的處理機(jī)來并行計(jì)算?，F(xiàn)實(shí)社會(huì)中，越來越多的數(shù)據(jù)信息需要計(jì)算機(jī)處理，串行計(jì)算機(jī)程序技術(shù)已經(jīng)不能滿足人們的需求，并行計(jì)算會(huì)越來越受到人們的青睞。
1.2矩陣向量相乘
矩陣向量相乘是數(shù)學(xué)以及工程中經(jīng)常遇到的一種計(jì)算方式。矩陣計(jì)算因其維數(shù)增大而造成的計(jì)算量增大是計(jì)算科學(xué)中需要進(jìn)一步解決的問題。利用并行計(jì)算方法，將矩陣向量進(jìn)行分發(fā)，使每個(gè)進(jìn)程同時(shí)進(jìn)行計(jì)算，將會(huì)大大減少計(jì)算的時(shí)間，提高計(jì)算效率。
2并行矩陣向量相乘原理
矩陣并行計(jì)算時(shí)，將矩陣進(jìn)行按行、列、塊三種方式進(jìn)行劃分，矩陣和向量按進(jìn)程個(gè)數(shù)進(jìn)行分發(fā)，接收矩陣和向量的進(jìn)程做相應(yīng)的運(yùn)算，最后將結(jié)果進(jìn)行規(guī)約綜合。本文只討論進(jìn)程個(gè)數(shù)恰能完全將矩陣向量平均分配的情況。
2.1按行劃分矩陣
矩陣向量相乘時(shí)，我們考慮nxn維矩陣A在n個(gè)進(jìn)程間劃分的情況。將計(jì)算機(jī)進(jìn)程編號(hào)為
考慮P（p
2.2按列劃分矩陣
按列進(jìn)行劃分是對(duì)每一行進(jìn)行劃分然后發(fā)送到每個(gè)進(jìn)程上。我們考慮
2.3按塊劃分矩陣
假設(shè)
3 并行算法的實(shí)現(xiàn)
程序設(shè)計(jì)流程圖：
圖1
3.1按行劃分矩陣向量相乘
程序要點(diǎn)：
1） 主進(jìn)程調(diào)用MPI_Send將向量發(fā)給各個(gè)進(jìn)程；
2） 其余進(jìn)程調(diào)用 MPI_Recv 接收主進(jìn)程發(fā)送的向量；
3） 各進(jìn)程調(diào)用 MPI_Scatter 按行共享主進(jìn)程中的矩陣；
4） 各個(gè)進(jìn)程進(jìn)行矩陣向量相乘；
5） 各進(jìn)程調(diào)用MPI_Gather將所得向量各個(gè)分量聚集到主進(jìn)程上，得到最終計(jì)算結(jié)果。
3.1.1 按行劃分的算法實(shí)現(xiàn)
實(shí)現(xiàn)按行劃分的矩陣向量乘法的程序關(guā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）； //計(jì)算 MatrixMul（localA，EverCorNumLine，n，localX，localR）； MPI_Gather（localR，EverCorNumLine，MPI_INT，R，EverCorNumLine，MPI_INT，0，MPI_COMM_WORLD）； 3.2按列劃分矩陣向量相乘 程序要點(diǎn)： 1） 主進(jìn)程按列劃分矩陣及向量，記錄自身計(jì)算所需矩陣分量及向量分量并 調(diào)用MPI_Send將各矩陣分量及向量分量發(fā)給相應(yīng)進(jìn)程 2） 其余進(jìn)程調(diào)用 MPI_Recv 接收主進(jìn)程發(fā)送的矩陣分量及向量分量 3） 各個(gè)進(jìn)程進(jìn)行矩陣向量相乘 4） 主進(jìn)程以外的其余進(jìn)程調(diào)用MPI_Send將計(jì)算結(jié)果發(fā)給主進(jìn)程 5） 主進(jìn)程調(diào)用 MPI_Recv 接收各向量并與自身結(jié)果進(jìn)行運(yùn)算，得到最終計(jì)算結(jié)果。 3.1.2 按列劃分的算法實(shí)現(xiàn) 實(shí)現(xiàn)按列劃分的矩陣向量乘法的程序關(guā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）； } //計(jì)算 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按塊劃分矩陣向量相乘
程序要點(diǎn)：
1） 主進(jìn)程按塊劃分矩陣及向量，記錄自身計(jì)算所需矩陣分量及向量分量并調(diào)用MPI_Send將各矩陣分量及向量分量發(fā)給相應(yīng)進(jìn)程；
2） 其余進(jìn)程調(diào)用 MPI_Recv 接收主進(jìn)程發(fā)送的矩陣分量及向量分量；
3） 各個(gè)進(jìn)程進(jìn)行矩陣向量相乘；
4） 主進(jìn)程以外的其余進(jìn)程調(diào)用MPI_Send將計(jì)算結(jié)果發(fā)給主進(jìn)程；
5） 主進(jìn)程調(diào)用 MPI_Recv 接收各向量并將全部結(jié)果整合進(jìn)行運(yùn)算，得到最終計(jì)算結(jié)果。
3.3.1 按塊劃分的算法實(shí)現(xiàn)
實(shí)現(xiàn)按塊劃分的矩陣向量乘法的程序關(guā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）； } //計(jì)算 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 程序運(yùn)行結(jié)果分析與討論 進(jìn)行上機(jī)實(shí)驗(yàn)，開發(fā)環(huán)境為Microsoft Visual Studio 2010（旗艦版），最終計(jì)算結(jié)果如下： 表1 256維計(jì)算結(jié)果 [＼&串行時(shí)間/s＼&4核行時(shí)間/s（效率）＼&16核行時(shí)間/s（效率）＼&64核行時(shí)間/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維計(jì)算結(jié)果 [＼&串行時(shí)間/s＼&4核行時(shí)間/s（效率）＼&16核行時(shí)間/s（效率）＼&64核行時(shí)間/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維計(jì)算結(jié)果 [＼&串行時(shí)間/s＼&4核行時(shí)間/s（效率）＼&16核行時(shí)間/s（效率）＼&64核行時(shí)間/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維計(jì)算結(jié)果 [＼&串行時(shí)間/s＼&4核行時(shí)間/s（效率）＼&16核行時(shí)間/s（效率）＼&64核行時(shí)間/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維計(jì)算結(jié)果 [＼&串行時(shí)間/s＼&4核行時(shí)間/s（效率）＼&16核行時(shí)間/s（效率）＼&64核行時(shí)間/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 按列劃分加速比增長(zhǎng)關(guān)系 圖2 按行劃分加速比增長(zhǎng)關(guān)系 圖3 按塊劃分加速比增長(zhǎng)關(guān)系圖 5結(jié)論 通過對(duì)上述圖表分析，我們可得到以下結(jié)論： 隨著維數(shù)的增長(zhǎng)，三種劃分方式加速比和效率都逐漸增長(zhǎng)，但所用的核數(shù)較少時(shí)，加速比和效率較為明顯，因?yàn)閿?shù)據(jù)的分發(fā)需要耗費(fèi)一定量時(shí)間，當(dāng)核數(shù)目較多時(shí)，分發(fā)矩陣需要的時(shí)間將會(huì)增大。 三種分發(fā)方式中，隨著維數(shù)的增高，按行劃分是最有效的方法。按列劃分在分發(fā)時(shí)需要分發(fā)的次數(shù)為維數(shù)的倍數(shù)，分發(fā)的時(shí)間將大大增加。按塊劃分需要將矩陣進(jìn)行塊劃分。然后再進(jìn)行分發(fā)，和列劃分一樣，也是增大了時(shí)間的消耗。 在工程計(jì)算中，當(dāng)矩陣維數(shù)較大時(shí)，可以采取按行劃分的方式大大增加計(jì)算速度，而當(dāng)矩陣維數(shù)較小時(shí)，建議使用串行算法。 參考文獻(xiàn)： [1] 朱建偉，劉榮.多線程并行快速求解e 值的六種方法[J].現(xiàn)代計(jì)算機(jī)，2013（6）. [2] 多核系列教材編寫組.多核程序設(shè)計(jì)[M]. 北京. 清華大學(xué)出版社，2007. [3] 帕切克.并行程序設(shè)計(jì)導(dǎo)論[M].鄧倩妮，譯.北京機(jī)械工業(yè)出版社，2012.
