PC9 中科大 并行计算 教学ppt课件.ppt

《PC9 中科大 并行计算 教学ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、并行计算中国科学技术大学计算机科学与技术系国家高性能计算中心(合肥)2004年12月2021/7/281现代密码学理论与实践之五第三篇并行数值算法第八章基本通讯操作第九章稠密矩阵运算第十章线性方程组的求解第十一章快速傅里叶变换2021/7/282现代密码学理论与实践之五第九章稠密矩阵运算9.1矩阵的划分9.2矩阵转置9.3矩阵-向量乘法9.4矩阵乘法2021/7/283现代密码学理论与实践之五9.1矩阵的划分9.1.1带状划分9.1.2棋盘划分2021/7/284现代密码学理论与实践之五带状划分16×16阶矩阵，

2、p=4列块带状划分行循环带状划分带状划分示例：p＝3，27×27矩阵的3种带状划分9.1矩阵的划分9.1.1带状划分9.1.2棋盘划分2021/7/287现代密码学理论与实践之五棋盘划分8×8阶矩阵，p=16块棋盘划分循环棋盘划分棋盘划分示例：p＝4，16×16矩阵的3种棋盘划分第九章稠密矩阵运算9.1矩阵的划分9.2矩阵转置9.3矩阵-向量乘法9.4矩阵乘法2021/7/2810现代密码学理论与实践之五9.2矩阵转置9.2.1棋盘划分的矩阵转置9.2.2带状划分的矩阵转置2021/7/2811现代密码学理论与实

3、践之五棋盘划分的矩阵转置网孔连接情形1:p=n2。通讯步转置后棋盘划分的矩阵转置情形2:p

4、n×n分成p个(n/p)×n大小的带算法:①Pi有p-1个(n/p)×(n/p)大小子块发送到另外p-1个处理器中;②每个处理器本地交换相应的元素第九章稠密矩阵运算9.1矩阵的划分9.2矩阵转置9.3矩阵-向量乘法9.4矩阵乘法2021/7/2818现代密码学理论与实践之五9.3矩阵-向量乘法9.3.1带状划分的矩阵-向量乘法9.3.2棋盘划分的矩阵-向量乘法2021/7/2819现代密码学理论与实践之五带状划分的矩阵-向量乘法划分(行带状划分):Pi存放xi和ai,0,ai,1,…,ai,n-1,并输出yi算法

5、:对p=n情形①每个Pi向其他处理器播送xi(多到多播送)；②每个Pi计算；注:对p

6、累运算，最后一列Pi,n-1收集的结果为yi；注:对p

7、.4矩阵乘法9.4.1简单并行分块乘法9.4.2Cannon乘法9.4.3Fox乘法9.4.4Systolic乘法9.4.5DNS乘法2021/7/2827现代密码学理论与实践之五矩阵乘法符号及定义jiABCA中元素的第1下标与B中元素的第2下标相一致（对准）矩阵乘法并行实现方法计算结构：二维阵列空间对准(元素已加载到阵列中）Cannon’s,Fox’s，DNS时间对准(元素未加载到阵列中）SystolicA0,0B0,0A1,0B1,0A2,0B2,0A3,0B3,0A0,1B0,1A1,1B1,1A2,1B2

8、,1A3,1B3,1A0,2B0,2A1,2B1,2A2,2B2,2A3,2B3,2A0,3B0,3A1,3B1,3A2,3B2,3A3,3B3,3简单并行分块乘法分块:A、B和C分成的方块阵Ai,j、Bi,j和Ci,j,大小均为p个处理器编号为,Pi,j存放Ai,j、Bi,j和Ci,j。算法:①通讯:每行处理器进行A矩阵块的多到多播送(得到Ai,k,k=0~)每列处理器