Cannon乘法的MPI实现

并行算法

5星 · 超过95%的资源需积分: 12 100 浏览量更新于2023-06-07 1 收藏 1.5MB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

《并行算法实践》要求学生在 KD60 实验平台上设计并行算法并实现。实验

平台由一块处理板、一块监控板和一块背板等组成。

处理板逻辑结构如图  所示。处理板承载  个处理单元，每个处理单元包

括一个龙芯  号四核 、 内存、 千兆以太网卡芯片、

、串口收发芯片以及电源变换电路等。四个龙芯  号处理器通过

 总线实现互连。监控电路检测  个处理单元的状态，并实现对其控制。

图 处理板逻辑结构

实验平台的系统软件以开源软件为主（见图 ），具有兼容性强、易维护、

易升级、易使用等特点。处理单元操作系统为  ! 无盘系统，

采用稳定高效的 "#"$ 内核。

图 软件系统结构

要求选修《并行算法实践》同学在下面表 1 中选一个题目，（1）阐述基本原

理（包括对算法改进和优化方法）；(2)根据 KD60 实验平台设计实验方法和步

骤（包括主要调试过程要求拷屏）。(3) 数据及结果分析：根据不同的实验内容，

记录具体的实验数据或程序运行结果（要求拷屏）。实验数据量较大时，最好制

成表格形式。附上程序功能、模块说明、完整源代码，源代码中尽量多带注释；

摘要：cannon 算法是矩阵的并行乘法，属于数值并行算法 MPI 编程实现一篇，其中关于

数值并行算法 MPI 编程由于要处理的数据量巨大，程序循环次数多，对于串行而言，处理

时间将非常长，将其并行化非常必要。本文将矩阵数据进行棋盘划分成多个子矩阵，再分

别指派给多个处理器，使个处理器并行运算。

关键字：cannon 乘法并行计算数据划分

一、+ 乘法的 MPI 实现基本原理

+ 乘法属于数值并行算法 MPI 编程实现一篇，其中关于数值并行算法 MPI 编程由于

要处理的数据量巨大，程序循环次数多，对于串行而言，处理时间将非常长，使其并行化

的一般方法有：1）数据相关分析 2）数据划分和处理器指派 3）循环重构

对原有程序并行化，首先要分析计算程序中所有语句间的依赖关系，这称之为相关分析。

本项目 + 乘法的 ,' 实现，是矩阵运算，阶往往都很高，而且行列之间数据依赖关

系也不强，所以就对矩阵进行划分，然后指派给不同的处理器进行处理。最常用的矩阵划

分有带状划分和块状划分。

．带状划分方法

带状划分又叫行列划分，就是将矩阵整行或整列地分成若干组，各组指派给一个处理

器。也可以将若干行或列指派给一个处理器，而且这些行和列可以是连续的，也可以

是等间距的，前者称为块带状的，后者称为循环带状的。

" 块状划分方法

块状划分又叫棋盘划分，就是将矩阵划分成若干个子矩阵，每个子矩阵指派给一个处

理器，此时任意处理器均不含整行或整列。和带状划分类似，棋盘划分也可分为块棋

盘划分和循环棋盘划分。棋盘划分比带状划分可开发更高的并行度，+ 乘法的

,' 实现也正是基于棋盘划分的并行实现。

循环重构是指在数据分解之后，相应地将串行程序循环部分进行重构，以实现这种划分所

确定的并行计算，主要方法有 ）循环交换 ）拉伸法 ）分裂法 ）轮转法 -）并列法

在三种程序并行化的方法中，数据相关分析和循环重构目的都是挖掘语句间的并行性，而

数据划分和处理器指派则重在策略，宏观上挖掘并行性。

Cannon 算法是一种存储有效的算法，设矩阵和相乘。为了使两矩阵下标满

足相乘的要求，和带状的并行分块乘法不同，不是仅仅让 B 矩阵的各列块循环移动，而是

有目的地让 A 的各行块以及 B 的各列块皆施行循环移位，从而实现对 C 的子块的计算。将

矩阵 A 和 B 分成 p 个方块 A

和 B

，，每块大小为

，并将它们分配给个处理器

。开始时处理器 P

存放块 A

和 B

，并负责计算块 C

，然后算

法开始执行：

⑴ 将块 A

向左循环移动 i 步；将块 B

向上循环移动 j 步；

⑵P

执行乘加运算后将块 A

向左循环移动 1 步，块 B

向上循环移动 1 步；

⑶ 重复第⑵步，总共执行次乘加运算和次块 A

和 B

的循环单步移位。

二、+ 乘法的 MPI 实现内容和步骤

实验涉及内容主要有：

）数据划分和指派处理器

最常用的矩阵数据划分有带状划分和块状划分。棋盘划分比带状划分可开发更高的并行度，

+ 乘法的 ,' 实现也正是基于棋盘划分的并行实现。设有  个处理器，将矩阵 A 和

B 分成 p 个方块 A

和 B

，，每块大小为

，并将它们分配给个处理器

。

）子矩阵的循环移动

处理器 P

存放块 A

和 B

，并负责计算块 C

，在使 . 矩阵的左右循环移动和  矩阵的上下

循环移动时，为了避免在通信过程中发生死锁，奇数号及偶数号处理器的收发顺序被错开，

使偶数号处理器先发送后接收；而奇数号处理器先将子矩阵块存于缓冲区  /0 中，然后

接收编号在其后面的处理器所发送的子矩阵块，最后再将缓冲区中子矩阵块发送给编号在

其前面的处理器。基本算法如下：

1

%&2%j3&45最左端的子块5

%"&将所存的 . 的子块发送到同行最右端子块所在的处理器中

%"&接收其右邻处理器中发来的 . 的子块

62

%&2%%j 3704%p&*&6%j,+63&&45最右端子块处理器且块列号

为偶数5

%"&将所存的 . 的子块发送到其左邻处理器中

%"&接收其同行最左端子块所在的处理器发来的 . 的子块

62

%&2%%j 3704%p&*&6%j,+68&&45最右端子块处理器且块列号

为奇数5

%"&将所存的 . 的子块在缓冲区  /0 中做备份

%"&接收其同行最左端子块所在的处理器发来的 . 的子块

%"&将在缓冲区  /0 中所存的 . 的子块发送到其左邻处理器中

62

%&2%%j 8704%p&*&6%j,+63&6%j 8&&45其余的偶数号处

理器5

%"&将所存的 . 的子块发送到其左邻处理器中

%"&接收其右邻处理器中发来的 . 的子块

62

%-&2%%j 8704%p&*&6%j,+63&6%j 8&&45其余的奇数号处

理器5

%-"&将所存的 . 的子块在缓冲区  /0 中做备份

%-"&接收其右邻处理器中发来的 . 的子块

%-"&将在缓冲区  /0 中所存的 . 的子块发送到其左邻处理器中

62

96

实验步骤

）登陆 )*#

剩余16页未读，继续阅读

nihate

粉丝: 1226
资源: 25

会员权益专享

Cannon乘法的MPI实现

MPI编程——分块矩阵乘法

Cannon[mpi并行实现及加速比（源程序）

矩阵相乘的MPI并行算法

MPI编程Strassen矩阵乘法并行实现

基于mpi实现矩阵乘法

pthread矩阵向量乘法和mpi矩阵向量乘法的区别

我如何使用mpi实现并行计算？

mpi矩阵乘法代码实现c++版本（打印矩阵并输出耗费时间）

用MPI设计实现矩阵-向量乘法

使用MPI实现快速排序

MPI矩阵乘法的两种实现方法

编写一个矩阵向量乘法的MPI编程代码

采用mpi实现树搜索代码实现

使用MPI实现冒泡排序

如何通过MPI实现服务器之间的通信

使用mpi实现hot potato实验

编写一个完整的矩阵向量乘法的MPI编程代码

MPI并行程序编写与调试（MPI矩阵-向量乘法）实验原理

MPI实现矩阵乘以矩阵的转秩

基于MPI实现梯形求积分

会员权益专享

最新资源