Cannon乘法的MPI实现

《Cannon乘法的MPI实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、专业资料《并行算法实践》要求学生在KD60实验平台上设计并行算法并实现。实验平台由一块处理板、一块监控板和一块背板等组成。处理板逻辑结构如图1所示。处理板承载4个处理单元，每个处理单元包括一个龙芯3号四核CPU、2GBDDR2内存、RTL8110千兆以太网卡芯片、BIOSFlash、串口收发芯片以及电源变换电路等。四个龙芯3号处理器通过HT总线实现互连。监控电路检测4个处理单元的状态，并实现对其控制。图1处理板逻辑结构实验平台的系统软件以开源软件为主（见图2），具有兼容性强、易维护、易升级、易使用等特点。处理单元操作系统为DebianGNU/Linux无盘系统，采用稳定高效的2.6.2

2、7内核。图2软件系统结构要求选修《并行算法实践》同学在下面表1中选一个题目，（1）阐述基本原理（包括对算法改进和优化方法）；(2)根据KD60实验平台设计实验方法和步骤（包括主要调试过程要求拷屏）。(3)数据及结果分析：根据不同的实验内容，记录具体的实验数据或程序运行结果（要求拷屏）。实验数据量较大时，最好制成表格形式。附上程序功能、模块说明、完整源代码，源代码中尽量多带注释；(4)分析和总结：对程序与算法性能改进结论，总结和体会。word完美格式专业资料表1《并行算法实践》题目序号题目名称基本方法和内容要求1LU分解的OpenMP实现编写LU分解的OpenMP程序2KMP算法的Ope

3、nMP实现编写KMP算法的OpenMP程序3高斯消元法解线性方程组的OpenMP实现编写高斯消元法解线性方程组的OpenMP程序4高斯消元法解线性方程组的MPI实现编写高斯消元法解线性方程组的MPI程序5高斯-塞德尔迭代解线性方程组的MPI实现编写高斯-塞德尔迭代解线性方程组的MPI程序6Cannon乘法的MPI实现编写Cannon乘法的MPI程序7LU分解的MPI实现编写LU分解的MPI程序8随机串匹配算法的MPI实现编写随机串匹配算法的MPI程序9单源最短路径Dijkstra算法的MPI实现编写单源最短路径Dijkstra算法的MPI程序10快速排序算法的MPI实现编写快速排序算法

4、的MPI程序11KMP串匹配的MPI实现编写KMP串匹配算法的MPI程序图2软件系统结构word完美格式专业资料Cannon乘法的MPI实现及性能分析摘要：cannon算法是矩阵的并行乘法，属于数值并行算法MPI编程实现一篇，其中关于数值并行算法MPI编程由于要处理的数据量巨大，程序循环次数多，对于串行而言，处理时间将非常长，将其并行化非常必要。本文将矩阵数据进行棋盘划分成多个子矩阵，再分别指派给多个处理器，使个处理器并行运算。关键字：cannon乘法并行计算数据划分一、Cannon乘法的MPI实现基本原理Cannon乘法属于数值并行算法MPI编程实现一篇，其中关于数值并行算法MPI编

5、程由于要处理的数据量巨大，程序循环次数多，对于串行而言，处理时间将非常长，使其并行化的一般方法有：1）数据相关分析2）数据划分和处理器指派3）循环重构对原有程序并行化，首先要分析计算程序中所有语句间的依赖关系，这称之为相关分析。本项目Cannon乘法的mpi实现，是矩阵运算，阶往往都很高，而且行列之间数据依赖关系也不强，所以就对矩阵进行划分，然后指派给不同的处理器进行处理。最常用的矩阵划分有带状划分和块状划分。1．带状划分方法带状划分又叫行列划分，就是将矩阵整行或整列地分成若干组，各组指派给一个处理器。也可以将若干行或列指派给一个处理器，而且这些行和列可以是连续的，也可以是等间距的，前

6、者称为块带状的，后者称为循环带状的。2.块状划分方法块状划分又叫棋盘划分，就是将矩阵划分成若干个子矩阵，每个子矩阵指派给一个处理器，此时任意处理器均不含整行或整列。和带状划分类似，棋盘划分也可分为块棋盘划分和循环棋盘划分。棋盘划分比带状划分可开发更高的并行度，Cannon乘法的mpi实现也正是基于棋盘划分的并行实现。循环重构是指在数据分解之后，相应地将串行程序循环部分进行重构，以实现这种划分所确定的并行计算，主要方法有1）循环交换2）拉伸法3）分裂法4）轮转法5）并列法在三种程序并行化的方法中，数据相关分析和循环重构目的都是挖掘语句间的并行性，而数据划分和处理器指派则重在策略，宏观上挖

7、掘并行性。Cannon算法是一种存储有效的算法，设矩阵和相乘。为了使两矩阵下标满足相乘的要求，和带状的并行分块乘法不同，不是仅仅让B矩阵的各列块循环移动，而是有目的地让A的各行块以及B的各列块皆施行循环移位，从而实现对C的子块的计算。将矩阵A和B分成p个方块Aij和Bij，，每块大小为，并将它们分配给个处理器。开始时处理器Pij存放块Aij和Bijword完美格式专业资料，并负责计算块Cij，然后算法开始执行：⑴将块Aij向左循环移动i步；将