并行处理技术 课程设计分析报告 课程设计题目 矩阵相乘并行算法设计 姓名 廖杰 学号 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 分了多少块,除最后一块外的其他数据块大小都相等,最后一块是剩下的数据,大小大...