《高性能矩阵乘法》PPT课件

《《高性能矩阵乘法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/9/171高性能矩阵乘法夏霏xiafei@mail.ustc.edu.cn2021/9/172并行算法优化研究相对于传统面向对象串行算法的4个挑战：同步：两个或者多个线程协调其行为的过程通信：与线程之间交换数据相关的带宽和延迟问题负载均衡：多个线程之间工作量分布的情况，给各个线程（执行核）分配均匀的工作可扩展性：衡量在性能更加强劲的系统上运行软件时能否有效利用更多线程的指标，观察应用程序在更高级的平台上运行4核到8核线性增长2021/9/173多线程（核）设计主要分解模式任务分解：对程序根据其执行的功能进行分解的过程数据分解

2、：将应用程序根据各任务所处理的数据而非按任务的天然特性来进行分解数据流分解：研究数据在诸任务之间如何流动，根据任务之间的数据流关系对问题进行分解模式分解方式任务级并行模式任务分解DivideandConquer任务/数据分解几何分解模式数据分解流水线模式数据流分解波峰（wavefront）模式数据流分解2021/9/174多线程（核）设计主要分解模式任务分解：对程序根据其执行的功能进行分解的过程数据分解：将应用程序根据各任务所处理的数据而非按任务的天然特性来进行分解数据流分解：研究数据在诸任务之间如何流动，根据任务之间的数据流关系对问

3、题进行分解分解方式设计说明任务分解不同的程序行为采用不同的线程实现常用于GUI应用程序数据分解多个线程对不同的数据块执行相同的操作常用于音频、图像处理和科学计算应用程序数据流分解一个线程的输出作为另一个线程的输入尤其应注意尽量消除启动和排空延迟2021/9/175矩阵乘法算法探讨在工程科学计算中，矩阵乘积是最基本的运算典型的n阶稠密方阵乘积算法的时间复杂度是O(n3)。目前对大型矩阵乘积运算的处理主要是采用分治思想，将矩阵分布在多个节点上，但每个结点上的小矩阵仍要立方级乘法次数。基于分之思想的两种划分策略：条形划分和块状（棋盘）划分的

4、6种常见分布式矩阵乘法并行算法。2021/9/176基于不同划分策略的矩阵乘法算法探讨1、条形（stripedpartitioning）划分的矩阵乘法并行算法行条划分列条划分两两组合：行列、行行、列列、列行2021/9/177基于不同划分策略的矩阵乘法算法探讨2、块状划分(checkerboardpartitioning)的矩阵乘法并行算法称为棋盘划分CannonDescriptionforimplementationofMPIprogramtocomputeMatrixMatrixMultiplicationusingblockch

5、eckerboardpartitioningandCannonAlgorithm2021/9/178CannonObjectiveComputingthematrix-matrixmultiplicationonSMPSystem.UseblockcheckerboardpartitioningofthematricesandCannon'sAlgorithm.AssumptionSizeofthesquarematricesp=q2andthesizeofsquarematricesAandBisevenlydivisiblebyq

6、. Itisassumedthatthenumberofblocksareequaltothenumberofprocessors.2021/9/179CannonCannon'salgorithmisbasedoncartesianvirtualtopologyAandBaresquarematricesofsizenandCbetheoutput matrix.Thesematricesaredivedintoblocksorsubmatricestoperformmatrix-matrixoperationsinparallel

7、nxnmatrixAcanberegardedasqxqarrayofblocksAi,j(0<=i

8、11传统并行ThematricesAandBarepartitionedintopblocks,Ai,jandBi,j(0<=i