并行计算-多媒体课件-并行算法设计与分析-ch12 Matrix Operations.ppt

《并行计算-多媒体课件-并行算法设计与分析-ch12 Matrix Operations.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ParallelAlgorithmsChapter12MatrixOperations2021/7/25Y.XuCopyrightUSTC主要内容12.1矩阵的划分12.2矩阵转置12.3矩阵向量乘法12.4矩阵乘法2021/7/25Y.XuCopyrightUSTC12.1矩阵的划分划分方法带状划分(stripedpartitioning):onedimensional,roworcolumn,blockorcyclic棋盘划分(checkerboardpartitioning):twodimensional,blockorcyclic2021/7/

2、25Y.XuCopyrightUSTC12.1矩阵的划分12.1.1带状划分16×16阶矩阵，p=4列块带状划分行循环带状划分2021/7/25Y.XuCopyrightUSTC12.1矩阵的划分12.1.2棋盘划分8×8阶矩阵，p=16块棋盘划分循环棋盘划分2021/7/25Y.XuCopyrightUSTC主要内容12.1矩阵的划分12.2矩阵转置12.3矩阵向量乘法12.4矩阵乘法2021/7/25Y.XuCopyrightUSTC12.2矩阵转置A=(aij)n×n,A的转置矩阵AT=(aji)n×n12.2.1棋盘划分的矩阵转置(以下仅讨论网

3、孔和超立方情形)1.网孔连接Case1:p=n2。CommunicationstepsFinalconfiguration2021/7/25Y.XuCopyrightUSTC12.2矩阵转置Case2:p

4、块矩阵的元素处于同一处理器；③进行同一处理器的内部转置。-示例:见下图-运行时间:12.2矩阵转置2021/7/25Y.XuCopyrightUSTC12.2矩阵转置67452301141512131011892021/7/25Y.XuCopyrightUSTC12.2矩阵转置12.2.2带状划分的矩阵转置-划分:An×n分成p个(n/p)×n大小的带-算法:①Pi有p-1个(n/p)×(n/p)大小子块发送到另外p-1个处理器中;②每个处理器本地交换相应的元素-时间分析(留作思考)2021/7/25Y.XuCopyrightUSTC主要内容12.1矩

5、阵的划分12.2矩阵转置12.3矩阵向量乘法12.4矩阵乘法2021/7/25Y.XuCopyrightUSTC12.3矩阵向量乘法求Y=AX串行算法计算时间t(n)=O(n2)2021/7/25Y.XuCopyrightUSTC12.3矩阵向量乘法12.3.1带状划分的矩阵-向量乘法-划分(行带状划分):Pi存放xi和ai,0,ai,1,…,ai,n-1,并输出yi-算法:对p=n情形①每个Pi向其他处理器播送xi(多到多播送)；②每个Pi计算Σxj*ai,j,；注:对p

6、网孔连接的计算时间2021/7/25Y.XuCopyrightUSTC12.3矩阵向量乘法-示例2021/7/25Y.XuCopyrightUSTC12.3矩阵向量乘法12.3.2棋盘划分的矩阵-向量乘法-划分(块棋盘划分):Pij存放ai,j,xi置入Pi,i中-算法:对p=n2情形①每个Pi,i向Pj,i播送xi(一到多播送)；②按行方向进行乘-加与积累运算，最后一列Pi,n-1收集的结果为yi；注:对p

7、的通讯时间:.按列一到多播送时间:.按行单点积累的时间:2021/7/25Y.XuCopyrightUSTC12.3矩阵向量乘法-示例2021/7/25Y.XuCopyrightUSTC12.3矩阵向量乘法带状与棋盘划分的比较-网孔上带状划分的运行时间-网孔上棋盘划分的运行时间棋盘划分要比带状划分快。2021/7/25Y.XuCopyrightUSTC主要内容12.1矩阵的划分12.2矩阵转置12.3矩阵向量乘法12.4矩阵乘法2021/7/25Y.XuCopyrightUSTC12.4矩阵乘法-1.乘法定义-4.Fox算法-2.实现方法-5.Syst

8、olic算法-3.Cannon算法-6.DNS算法2021/7/25Y.XuCopyright