中科大多核并行计算课件.ppt

现代密码学理论与实践之五 第三篇 并行数值算法 第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换  第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法 9.3.3 矩阵-向量的脉动乘法 9.4 矩阵乘法 矩阵-向量乘法 求Y=AX 串行算法计算时间t(n)=O(n2) 第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法 9.3.3 矩阵-向量的脉动乘法 9.4 矩阵乘法 带状划分的矩阵-向量乘法（1） 划分(行带状划分): Pi存放xi和ai,0,ai,1,…,ai,n-1, 并输出yi 算法: 对p=n情形 ①每个Pi将其向量元素向其他处理器播送xi(多到多播送)； ②每个Pi做相应计算； 注: 对pn情形,算法中Pi要播送X中相应的n/p个分量 (1)超立方连接的计算时间 (2)网孔连接的计算时间 带状划分的矩阵-向量乘法（2） 示例 第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法 9.3.3 矩阵-向量的脉动乘法 9.4 矩阵乘法 棋盘划分的矩阵-向量乘法（1） 划分(块棋盘划分): Pij存放ai,j, xi置入Pi,i中 算法: 对p=n2情形 ①每个Pi,i将其向量元素向Pj,i播送xi(一到多播送)； ②按行方向进行乘-加与积累运算，最后一列Pi,n-1收集的结果为yi； 注: 对pn2情形,p个处理器排成 的二维网孔， 算法中Pi,i向Pj,i播送X中相应的 个分量 (1)网孔连接的计算时间Tp(CT): .X中相应分量置入Pi,i的通讯时间: .按列一到多播送时间: .按行单点积累的时间: 棋盘划分的矩阵-向量乘法（2） 示例 带状与棋盘划分比较 以网孔链接为例 网孔上带状划分的运行时间 网孔上棋盘划分的运行时间 棋盘划分要比带状划分快。 第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.3.1 带状划分的矩阵-向量乘法 9.3.2 棋盘划分的矩阵-向量乘法 9.3.3 矩阵-向量的脉动乘法 9.4 矩阵乘法 矩阵-向量乘法的脉动算法（1） 示例 矩阵-向量乘法的脉动算法（2） 示例 第九章 稠密矩阵运算 9.1 矩阵的划分 9.2 矩阵转置 9.3 矩阵-向量乘法 9.4 矩阵乘法 9.4.1 简单并行分块乘法 9.4.2 Cannon乘法 9.4.3 Fox乘法 9.4.4 Systolic乘法  9.4.5 DNS乘法 矩阵乘法符号及定义 矩阵乘法并行实现方法 计算结构：二维阵列 空间对准(元素已加载到阵列中） Cannon’s , Fox’s，DNS 时间对准(元素未加载到阵列中） Systolic 简单并行分块乘法（1） 分块: A、B和C分成 的方块阵Ai,j、Bi,j和Ci,j, 大小均为 p个处理器编号为 , Pi,j存放Ai,j、Bi,j和Ci,j。 算法: ①通讯:每行处理器进行A矩阵块的多到多播送(得到Ai,k, k=0~ ) 每列处理器进行B矩阵块的多到多播送(得到Bk,j, k=0~ ) ②乘-加运算: Pi,j做 运行时间 (1)超立方连接： ①的时间 ②的时间 简单并行分块乘法（2） 运行时间 (1)超立方连接： (2)二维环绕网孔连接： ①的时间