矩阵相乘 并行算法

《矩阵相乘 并行算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、并行处理技术课程设计分析报告课程设计题目矩阵相乘并行算法设计姓名廖杰学号M201372880专业计算机技术任课教师金海石宣化所在学院计算机科学与技术学院报告提交日期2014-01-13一、实验目的1、学习使用集群；2、掌握并行处理或分布计算的编程方法；3、学会以并行处理的思想分析问题。二、实验要求1、自行生成矩阵作为算法的输入；2、使用并行处理技术编程，例如：MPI、OpenMP、MR；3、矩阵大小至少为1000*1000；4、加速比越大成绩越高。三、实验内容3.1、矩阵的划分：对于矩阵相乘的并行算法，可以有三种：对矩阵按行划分、按列划分和棋盘式分块划分。和按行或列划

2、分相比，棋盘式划分可以开发出更高的并行度。对于一个n×n的方阵，棋盘划分最多可以使用n^2个处理器进行并行计算，但使用按行或列分解最多可以使用n个。对矩阵相乘采用棋盘式划分的算法通常称作Cannon算法。A）行列划分又叫带状划分（StripedPartitioning），就是将矩阵整行或者整列分成若干个组，每个组指派给一个处理器。下图所例为4个CPU，8×8矩阵的带状划分。在带状划分情况下，每个CPU将会均匀分配到2行(列)数据。8×8矩阵变成了一个1×4或4×1的分块矩阵，每个CPU所属的分块矩阵大小为8×2或2×8。B）棋盘划分就是将矩阵分成若干个子矩阵，每个子矩

3、阵指派给一个处理器，此时任一处理器均不包含整行或者整列。下图所示即为4个处理器情况下8×8矩阵的棋盘划分，其中处理器阵列为2×2，每个处理器分配到的子矩阵大小为4×4。矩阵划分成棋盘状可以和处理器连成二维网孔相对应。对于一个n×n维矩阵和p×p的二维处理器阵列，每个处理器均匀分配有（n/p）×(n/p)=n^2/p^2个元素。使用棋盘式划分的矩阵相乘算法一般有两种，Cannon算法和Summa算法。SUMMA算法能够计算m*l的A矩阵和l*n的B矩阵相乘（m、l、n可不相等），而cannon算法只能实现n*n的A矩阵和n*n的B矩阵相乘，具有很大的局限性。3.2、算法

4、原理A)行划分法假设是M*N，计算前，将矩阵N发送给所有从进程，然后将矩阵M分块，将M中数据按行分给各从进程，在从进程中计算M中部分行数据和N的乘积，最后将结果发送给主进程。这里为了方便，有多少进程，就将M分了多少块，除最后一块外的其他数据块大小都相等，最后一块是剩下的数据，大小大于等于其他数据块大小，因为矩阵行数不一定整除进程数。最后一块数据在主进程中计算，其他的在从进程中计算。定义两个矩阵M和N，N所有进程都需要，M可以只在主进程中定义。其他的变量视主进程和从进程需要按要求定义在合适的位置。代码参见附录部分。B)Cannon算法Cannon算法的基本思想可以如下表

5、示：假设两个矩阵A和B相乘，把A和B矩阵划分成p个方块，进程的编号从到，并在最初把子矩阵和分配给。虽然第i行的每个进程需要全部的个子矩阵，但我们还是能调度第i行个进程的计算，使得每个进程在任何时刻都是用不同的。每完成一次矩阵乘法，这些块在各进程之间被轮流使用，似的每次轮流之后每个进程都可以得到新的。对列使用同样的调度，则在任何时刻，任何进程至多拥有每个矩阵的一个块，在所有进程中，改算法需要的总内存量为。下图为此算法中不同进程上子矩阵乘法的调度过程。假如矩阵C=A*B,则C的的计算公式如下：进程P存储分块矩阵这一部分。块矩阵乘法要计算所有匹配的和，然而只有在主对角线的才

6、是匹配的。因此需要采用循环移动分块矩阵的方法来使每个进程都有一对可以直接相乘的匹配的块，具体方法如下：(1)将排第i行的块循环左移i个位置，将第列．块循环上移j个位置；(2)进程执行乘一加运算，然后将移动得到的块循环左移1个位置，将移动得到的块循环上移1个位置；(3)重复第2步(一1)次，每次移动后进程执行乘一加运算。经过以上操作后就可以得到矩阵C的解。代码请参见附录部分C)Summa算法SUMMA算法首先将A,B和C划分为相同大小的矩阵，对应放在mesh_r×mesh_c的二维mesh上。但SUMMA算法将矩阵乘法分解为一系列的秩nb修正,即各处理器中的A和B分别被

7、分解为nb大小的列块和行块进行相乘，前面所说的分块尺寸就是指nb的大小。算法中,广播实现为逻辑处理器行环或列环上的流水线传送,达到了计算与通信的重叠.具体描述如算法1所示。C=0fori=0tok-1stepnbdo　curcol=i×c/n　currow=i×r/m　ifmycol=currol向本行广播A从imod(k/c)列开始的nb列,存于A′　ifmyrow=currow向本列广播B从imod(k/r)行开始的nb行,存于B′　C=A′×B′endforSUMMA算法的核心思想是：各处理器收集来自同一行处理器中A矩阵子块的所有列和同一列处理