行列块不同划分机制下矩阵向量相乘的并行计算方法

贺雨晴　张楠　李云东

摘要：矩阵运算是工程数值计算中一种常见的运算方式。大量的高维矩阵运算对数学计算提出了新的要求。该文提出了三种模式下的矩阵划分并行计算，分别是按行，按列，按块划分。运用MPI并行计算技术，比较出了适合工程上计算的模式，得到了按行划分算法的优势。

关键词：划分，矩阵运算，并行，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）是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。现实社会中，越来越多的数据信息需要计算机处理，串行计算机程序技术已经不能满足人们的需求，并行计算会越来越受到人们的青睐。

1.2矩阵向量相乘

矩阵向量相乘是数学以及工程中经常遇到的一种计算方式。矩阵计算因其维数增大而造成的计算量增大是计算科学中需要进一步解决的问题。利用并行计算方法，将矩阵向量进行分发，使每个进程同时进行计算，将会大大减少计算的时间，提高计算效率。

2并行矩阵向量相乘原理

矩阵并行计算时，将矩阵进行按行、列、块三种方式进行划分，矩阵和向量按进程个数进行分发，接收矩阵和向量的进程做相应的运算，最后将结果进行规约综合。本文只讨论进程个数恰能完全将矩阵向量平均分配的情况。

2.1按行划分矩阵

矩阵向量相乘时，我们考虑nxn维矩阵A在n个进程间划分的情况。将计算机进程编号为。则每一个进程都会存储1xn维矩阵。进程会存储。并且负责计算。向量C的存储方法与B相同。

考虑P（p维矩阵，每个进程的矩阵要与向量B相乘，所得的向量C与向量B的乘法类似。所得到的向量即为所求。通信时间为O（），计算时间为O（）。

2.2按列划分矩阵

按列进行划分是对每一行进行划分然后发送到每个进程上。我们考虑维矩阵A在n个进程间划分的情况。将计算机进程编号为-1。对于矩阵的第一行，进行划分，进程接收到元素的为，每一行划分后，进程接收到的元素为。进程做的计算为，每一个进程都会得到一个向量，将每一个向量所对应的元素相加，即得到最终的向量。

2.3按块划分矩阵

假设等于n，将矩阵划分成不同的矩阵块，每一个矩阵块上的矩阵为维。将划分的矩阵块发送到每一个进程，进程上进行维矩阵与的乘法运算。然后将计算同一行的矩阵块的进程结果相加，于同一列矩阵块相组合，得到最终的结果。

3 并行算法的实现

程序设计流程图：

图1

3.1按行划分矩阵向量相乘

程序要点：

1） 主进程调用MPI_Send将向量发给各个进程；

2） 其余进程调用 MPI_Recv 接收主进程发送的向量；

3） 各进程调用 MPI_Scatter 按行共享主进程中的矩阵；

4） 各个进程进行矩阵向量相乘；

5） 各进程调用MPI_Gather将所得向量各个分量聚集到主进程上，得到最终计算结果。

3.1.1 按行划分的算法实现

实现按行划分的矩阵向量乘法的程序关键代码如下：

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）；

}}}

//接收数据

else

{MPI_Recv（localX，n，MPI_INT，0，1，MPI_COMM_WORLD，MPI_STATUS_IGNORE）； }

//分发矩阵

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） 主进程按列划分矩阵及向量，记录自身计算所需矩阵分量及向量分量并 调用MPI_Send将各矩阵分量及向量分量发给相应进程

2） 其余进程调用 MPI_Recv 接收主进程发送的矩阵分量及向量分量

3） 各个进程进行矩阵向量相乘

4） 主进程以外的其余进程调用MPI_Send将计算结果发给主进程

5） 主进程调用 MPI_Recv 接收各向量并与自身结果进行运算，得到最终计算结果。

3.1.2 按列划分的算法实现

实现按列划分的矩阵向量乘法的程序关键代码如下：

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； }}

//分发向量

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++；}}

//接收数据

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） 主进程按块划分矩阵及向量，记录自身计算所需矩阵分量及向量分量并调用MPI_Send将各矩阵分量及向量分量发给相应进程；

2） 其余进程调用 MPI_Recv 接收主进程发送的矩阵分量及向量分量；

3） 各个进程进行矩阵向量相乘；

4） 主进程以外的其余进程调用MPI_Send将计算结果发给主进程；

5） 主进程调用 MPI_Recv 接收各向量并将全部结果整合进行运算，得到最终计算结果。

3.3.1 按块划分的算法实现

实现按块划分的矩阵向量乘法的程序关键代码如下：

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； }

//分发向量

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++；}}}

//接收数据

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 程序运行结果分析与讨论

进行上机实验，开发环境为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结论

通过对上述图表分析，我们可得到以下结论：

随着维数的增长，三种划分方式加速比和效率都逐渐增长，但所用的核数较少时，加速比和效率较为明显，因为数据的分发需要耗费一定量时间，当核数目较多时，分发矩阵需要的时间将会增大。

三种分发方式中，随着维数的增高，按行划分是最有效的方法。按列划分在分发时需要分发的次数为维数的倍数，分发的时间将大大增加。按块划分需要将矩阵进行块划分。然后再进行分发，和列划分一样，也是增大了时间的消耗。

在工程计算中，当矩阵维数较大时，可以采取按行划分的方式大大增加计算速度，而当矩阵维数较小时，建议使用串行算法。

参考文献：

[1] 朱建伟，刘荣.多线程并行快速求解e 值的六种方法[J].现代计算机，2013（6）.

[2] 多核系列教材编写组.多核程序设计[M]. 北京. 清华大学出版社，2007.

[3] 帕切克.并行程序设计导论[M].邓倩妮，译.北京机械工业出版社，2012.