Cannon乘法地MPI实现

实用文案 《并行算法实践》 要求学生在 KD60 实验平台上设计并行算法并实现。实验平 台由一块处理板、一块监控板和一块背板等组成。 处理板逻辑结构如图 1 所示。处理板承载 4 个处理单元， 每个处理单元包括 一个龙芯 3 号四核 CPU、 2GB DDR2 内存、 RTL8110 千兆以太网卡芯片、 BIOS Flash、 串口收发芯片以及电源变换电路等。 四个龙芯 3 号处理器通过 HT 总线实现互连。 监控电路检测 4 个处理单元的状态，并实现对其控制。 图 1 处理板逻辑结构 实验平台的系统软件以开源软件为主（见图 2） ，具有兼容性强、易维护、 易升级、易使用等特点。处理单元操作系统为 Debian GNU/Linux 无盘系统，采 用稳定高效的 2.6.27 内核。 图 2软件系统结构 要求选修《并行算法实践》同学在下面表 1 中选一个题目， （1）阐述基本原 理（包括对算法改进和优化方法） ；(2)根据 KD60 实验平台设计实验方法和步骤 （包括主要调试过程要求拷屏） 。(3) 数据及结果分析：根据不同的实验内容， 记录具体的实验数据或程序运行结果（要求拷屏） 。实验数据量较大时，最好制 成表格形式。附上程序功能、模块说明、完整源代码，源代码中尽量多带注释； (4)分析和总结：对程序与算法性能改进结论，总结和体会。 标准文档 实用文案 表 1《并行算法实践》题目 序号序号 1 2 3 4 5 6 7 8 9 10 11 图 2软件系统结构 题目名称题目名称 LU 分解的 Open MP 实现 KMP 算法的 Open MP 实现 高斯消元法解线性方程组的 Open MP 实现 高斯消元法解线性方程组的 MPI 实现 高斯-塞德尔迭代解线性方程组 的 MPI 实现 Cannon 乘法的 MPI 实现 LU 分解的 MPI 实现 随机串匹配算法的 MPI 实现 单源最短路径 Dijkstra 算法的 MPI 实现 快速排序算法的 MPI 实现 KMP 串匹配的 MPI 实现 基本方法和内容要求基本方法和内容要求 编写 LU 分解的 Open MP 程序 编写 KMP 算法的 OpenMP 程序 编写高斯消元法解线性方程组的OpenMP 程序 编写高斯消元法解线性方程组的 MPI 程 序 编写高斯-塞德尔迭代解线性方程组 的 MPI 程序 编写 Cannon 乘法的 MPI 程序 编写 LU 分解的 MPI 程序 编写随机串匹配算法的 MPI 程序 编写单源最短路径Dijkstra 算法的 MPI 程序 编写快速排序算法的 MPI 程序 编写 KMP 串匹配算法的 MPI 程序 标准文档 实用文案 CannonCannon 乘法的乘法的 MPIMPI 实现及性能分析实现及性能分析 摘要：摘要：cannon 算法是矩阵的并行乘法，属于数值并行算法MPI 编程实现一篇，其中关于 数值并行算法 MPI 编程由于要处理的数据量巨大， 程序循环次数多，对于串行而言，处理时 间将非常长，将其并行化非常必要。本文将矩阵数据进行棋盘划分成多个子矩阵， 再分别指 派给多个处理器，使个处理器并行运算。 关键字关键字：cannon 乘法 并行计算数据划分 一、Cannon 乘法的 MPI 实现基本原理 Cannon 乘法属于数值并行算法MPI 编程实现一篇，其中关于数值并行算法MPI 编程由于要 处理的数据量巨大，程序循环次数多，对于串行而言，处理时间将非常长， 使其并行化的一 般方法有：1）数据相关分析 2）数据划分和处理器指派 3）循环重构 对原有程序并行化，首先要分析计算程序中所有语句间的依赖关系， 这称之为相关分析。 本 项目 Cannon 乘法的 mpi 实现，是矩阵运算，阶往往都很高，而且行列之间数据依赖关系也 不强，所以就对矩阵进行划分， 然后指派给不同的处理器进行处理。 最常用的矩阵划分有带 状划分和块状划分。 1． 带状划分方法 带状划分又叫行列划分，就是将矩阵整行或整列地分成若干组，各组指派给一个处理 器。也可以将若干行或列指派给一个处理器，而且这些行和列可以是连续的，也可以 是等间距的，前者称为块带状的，后者称为循环带状的。 2.块状划分方法 块状划分又叫棋盘划分， 就是将矩阵划分成若干个子矩阵， 每个子矩阵指派给一个处理 器，此时任意处理器均不含整行或整列。 和带状划分类似，棋盘划分也可分为块棋盘划 分和循环棋盘划分。棋盘划分比带状划分可开发更高的并行度，Cannon 乘法的 mpi 实 现也正是基于棋盘划分的并行实现。 循环重构是指在数据分解之后， 相应地将串行程序循环部分进行重构， 以实现这种划分所确 定的并行计算，主要方法有1）循环交换 2）拉伸法 3）分裂法 4）轮转法 5）并列法 在 三种程序并行化的方法中， 数据相关分析和循环重构目的都是挖掘语句间的并行性， 而数据 划分和处理器指派则重在策略，宏观上挖掘并行性。 Cannon 算法是一种存储有效的算法，设矩阵A nn 和Bnn相乘。为了使两矩阵下标满足 相乘的要求，和带状的并行分块乘法不同， 不是仅仅让 B 矩阵的各列块循环移动， 而是有目 的地让 A 的各行块以及 B 的各列块皆施行循环移位，从而实现对C 的子块的计算。将矩阵A 和B分成p个方块Aij和Bij，(0  i, j p 1)，每块大小为n/ pn/p，并将它们分配 给p p个处理器(P00,P01,., P p 1p 1 )。 开始时处理器P ij存放块 Aij和Bij， 并负责 标准文档 实用文案 计算块Cij，然后算法开始执行： ⑴将块Aij向左循环移动i步；将块Bij向上循环移动j步； ⑵Pij执行乘加运算后将块Aij向左循环移动 1 步，块Bij向上循环移动 1 步； ⑶重复第⑵步，总共执行p次乘加运算和p次块Aij和Bij的循环单步移位。 二、Cannon 乘法的 MPI 实现内容和步骤 实验涉及内容主要有： 1）数据划分和指派处理器 最常用的矩阵数据划分有带状划分和块状划分。棋盘划分比带状划分可开发更高的并行度， Cannon 乘法的 mpi 实现也正是基于棋盘划分的并行实现。设有P 个处理器，将矩阵A和B 分成p个方块Aij和Bij，(0  i, j  p p个处理器(P00,P01,., P p 1)，每块大小为n/ pn/p，并将它们分配给 p 1p 1 )。 2） 子矩阵的循环移动 处理器Pij存放块Aij和Bij，并负责计算块Cij，在使 A 矩阵的左右循环移动和B 矩阵的上下 循环移动时，为了避免在通信过程中发生死锁，奇数号及偶数号处理器的收发顺序被错开， 使偶数号处理器先发送后接收；而奇数号处理器先将子矩阵块存于缓冲区Buffer 中，然后 接收编号在其后面的处理器所发送的子矩阵块， 最后再将缓冲区中子矩阵块发送给编号在其 前面的处理器。基本算法如下： Begin (1)if (j=0) then /*最左端的子块*/ (1.1)将所存的 A 的子块发送到同行最右端子块所在的处理器中 (1.2)接收其右邻处理器中发来的A 的子块 end if (2)if ((j= sqrt