矩阵相乘并行算法

并行处理技术 课程设计分析报告 课程设计题目 矩阵相乘并行算法设计 姓名 廖杰 学号 M ********* 专业 计算机技术 任课教师 金海 石宣化 所在学院 计算机科学与技术学院 报告提交日期 2014-01-13 一、实验目的 1、学习使用集群； 2、掌握并行处理或分布计算的编程方法； 3、学会以并行处理的思想分析问题。 二、实验要求 1、自行生成矩阵作为算法的输入； 2、使用并行处理技术编程，例如：MPI、OpenMP、MR； 3、矩阵大小至少为1000*1000； 4、加速比越大成绩越高。 三、实验内容 3.1、矩阵的划分： 对于矩阵相乘的并行算法，可以有三种：对矩阵按行划分、按列划分和棋盘式分块划分。和按行或列划分相比，棋盘式划分可以开发出更高的并行度。对于一个n×n 的方阵，棋盘划分最多可以使用n^2 个处理器进行并行计算，但使用按行或列分解最多可以使用n 个。对矩阵相乘采用棋盘式划分的算法通常称作Cannon 算法。 A）行列划分 又叫带状划分（Striped Partitioning），就是将矩阵整行或者整列分成若干个组，每个组指派给一个处理器。下图所例为4 个CPU，8×8 矩阵的带状划分。 在带状划分情况下，每个CPU 将会均匀分配到2 行(列)数据。8×8 矩阵变成了一个1×4 或4×1 的分块矩阵，每个CPU 所属的分块矩阵大小为 8×2 或 2×8。 B）棋盘划分 就是将矩阵分成若干个子矩阵，每个子矩阵指派给一个处理器，此时任一处理器均不包含整行或者整列。下图所示即为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、算法原理 A) 行划分法 假设是M*N，计算前，将矩阵N 发送给所有从进程，然后将矩阵M 分块，将M 中数据按行分给各从进程，在从进程中计算 M 中部分行数据和 N 的乘积，最后将结果发送给主进程。这里为了方便，有多少进程，就将M 分了多少块，除最后一块外的其他数据块大小都相等，最后一块是剩下的数据，大小大...