《高性能矩阵乘法优秀课件.ppt》由会员分享，可在线阅读，更多相关《高性能矩阵乘法优秀课件.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、高性能矩阵乘法第1页，本讲稿共27页2022/11/302并行算法优化研究相对于传统面向对象串行算法的并行算法优化研究相对于传统面向对象串行算法的4个挑战：个挑战：同步：两个或者多个线程协调其行为的过程通信：与线程之间交换数据相关的带宽和延迟问题负载均衡：多个线程之间工作量分布的情况，给各个线程（执行核）分配均匀的工作可扩展性：衡量在性能更加强劲的系统上运行软件时能否有效利用更多线程的指标，观察应用程序在更高级的平台上运行4核到8核线性增长第2页，本讲稿共27页2022/11/303多线程（核）设计主要分解模式多线程（核）设计主要分解模式任务分解：对程序根据其执行的功能进行分解的过程数据分解：
2、将应用程序根据各任务所处理的数据而非按任务的天然特性来进行分解数据流分解：研究数据在诸任务之间如何流动，根据任务之间的数据流关系对问题进行分解模式分解方式任务级并行模式任务分解DivideandConquer任务/数据分解几何分解模式数据分解流水线模式数据流分解波峰（wavefront）模式数据流分解第3页，本讲稿共27页2022/11/304多线程（核）设计主要分解模式多线程（核）设计主要分解模式任务分解：对程序根据其执行的功能进行分解的过程数据分解：将应用程序根据各任务所处理的数据而非按任务的天然特性来进行分解数据流分解：研究数据在诸任务之间如何流动，根据任务之间的数据流关系对问题进行分解
3、分解方式设计说明任务分解不同的程序行为采用不同的线程实现常用于GUI应用程序数据分解多个线程对不同的数据块执行相同的操作常用于音频、图像处理和科学计算应用程序数据流分解一个线程的输出作为另一个线程的输入尤其应注意尽量消除启动和排空延迟第4页，本讲稿共27页2022/11/305矩阵乘法算法探讨矩阵乘法算法探讨矩阵乘法算法探讨矩阵乘法算法探讨在工程科学计算中，矩阵乘积是最基本的运算典型的n阶稠密方阵乘积算法的时间复杂度是O(n3)。目前对大型矩阵乘积运算的处理主要是采用分治思想，将矩阵分布在多个节点上，但每个结点上的小矩阵仍要立方级乘法次数。基于分之思想的两种划分策略：条形划分和块状（棋盘）划分
4、的6种常见分布式矩阵乘法并行算法。第5页，本讲稿共27页2022/11/306基于不同划分策略的矩阵乘法算法探讨基于不同划分策略的矩阵乘法算法探讨基于不同划分策略的矩阵乘法算法探讨基于不同划分策略的矩阵乘法算法探讨1 1、条形（、条形（、条形（、条形（stripedpartitioningstripedpartitioning）划分的矩阵乘法并行算法）划分的矩阵乘法并行算法）划分的矩阵乘法并行算法）划分的矩阵乘法并行算法行条划分列条划分两两组合：行列、行行、列列、列行第6页，本讲稿共27页2022/11/307基于不同划分策略的矩阵乘法算法探讨基于不同划分策略的矩阵乘法算法探讨基于不同划分策略
5、的矩阵乘法算法探讨基于不同划分策略的矩阵乘法算法探讨2 2、块状划分、块状划分、块状划分、块状划分(checkerboardpartitioning)(checkerboardpartitioning)的矩阵乘法并行算法的矩阵乘法并行算法的矩阵乘法并行算法的矩阵乘法并行算法称为棋盘划分第7页，本讲稿共27页CannonDescriptionforimplementationofMPIprogramtocomputeMatrixMatrixMultiplicationusingblockcheckerboardpartitioningandCannonAlgorithm2022/11/308第8
6、页，本讲稿共27页CannonObjectiveObjective Computingthematrix-matrixmultiplicationonSMPSystem.UseblockcheckerboardpartitioningofthematricesandCannonsAlgorithm.AssumptionAssumptionSizeofthesquarematricesp=q2andthesizeofsquarematricesAandBisevenlydivisiblebyq.Itisassumedthatthenumberofblocksareequaltothenumber
7、ofprocessors.2022/11/309第9页，本讲稿共27页CannonCannonsalgorithmisbasedoncartesianvirtualtopologyAandBaresquarematricesofsizenandCbetheoutputmatrix.Thesematricesaredivedintoblocksorsubmatricestoperformmatrix-matrixoperationsinparallelnxnmatrixAcanberegardedasqxqarrayofblocksAi,j(0=iq,0=jq)suchthateachblock
8、isan(n/q)x(n/q)submatrixWeusepprocessorstoimplementtheblockversionofmatrixmultiplicationinparallelbychoosingqasasquarerootofpandcomputeadistinctblockCi,joneachprocessor.2022/11/3010第10页，本讲稿共27页传统并行传统并行2022/11/3011第11页，本讲稿共27页传统并行传统并行ThematricesAandBarepartitionedintopblocks,A i,j andBi,j(0=iq,0=jq)o
9、fsize(n/qxn/q)oneachprocess.Theseblocksaremappedontoaqxqlogicalmeshofprocesses.TheprocessesarelabeledfromP0,0toPq-1,q-1.2022/11/3012第12页，本讲稿共27页传统并行传统并行ProcessPi,jinitiallystoreblockmatricesAi,jandBi,jandcomputesblockCi,jofresultmatrix.TocomputesubmatrixCi,j,weneedallsubmatrices,Ai,kandBk,j(0=kq).To
10、acquirealltherequiredblocks,anall-to-allbroadcastofmatrixAi,jsisperformedineachrowandsimilarlyineachcolumnofmatrixBi,js.MPIcollectivecommunicationisusedtoperformthisoperations.2022/11/3013第13页，本讲稿共27页传统并行传统并行AfterPi,jacquires,Ai,0,Ai,1,Ai,2,Ai,q-1andB0,j,B1,j,B2,j,Bq-1,j,itperformstheserialblockmatr
11、ixtomatrixmultiplicationandaccumulatesthepartialblockmatrixCi,jofmatrixC.ToobtaintheresultantproductmatrixC,processeswithrank0gathersalltheblockmatricesbyusingMPI_Gathercollectivecommunicationoperation.2022/11/3014第14页，本讲稿共27页Cannonpprocessorsarrangedinqxqsquaregridofprocessorsandtheinputmatrices.Aa
12、ndBaredistributedamongtheprocessesincheckerboardfashion.ItresultsinconstructingpblockmatricesofAandB.Itusesonlypoint-to-pointcommunicationforcircularlyshiftingblocksofmatrixAandmatrixBamongpprocesses.2022/11/3015第15页，本讲稿共27页Cannon-initalThealgorithmproceedsinqstages.Thefirststepinthisalgorithmistope
13、rforminitialalignmentoftheblockmatrixAandblockmatrixB.TheblocksofmatrixAarecircularlyshiftedtotheipositionstoleftintherowofthesquaregridofprocesses,whereiistherownumberoftheprocessinthemesh.TheblocksofmatrixBarecircularlyshiftedjpositionsupwards,wherejisthecolumnnumberoftheprocessintheprocessesmesh.
14、2022/11/3016第16页，本讲稿共27页Cannon-inital2022/11/3017第17页，本讲稿共27页Cannon-runningThealgorithmperformsthefollowingstepsineachstage:1.MultiplytheblockofmatrixAandmatrixBandaddtheresultantmatrixtogettheblockmatrixC,whichisinitiallysettozero.2.CircularlyshifttheblocksofmatrixAtoleftintherowsoftheprocessesandt
15、heblocksofmatrixBupwardsinthecolumnsofthesquaregridofprocessesinawraparoundmanner.2022/11/3018第18页，本讲稿共27页Cannon-running2022/11/3019第19页，本讲稿共27页Cannon-running2022/11/3020第20页，本讲稿共27页书中书中Cannon-bug2022/11/3021MPI_SendandMPI_Recvisnotusedforpoint-to-pointcommunicationbecauseifalltheprocessescallMPI_Se
16、ndorMPI_Recvindifferentorderthe deadlockeddeadlockedsituationmayarise.Howtofix?指派一个缓冲区，使用MPI_Irecv/MPI_Isend非阻塞式通讯函数，MPI_wait.MPI_Sendrecv.第21页，本讲稿共27页2022/11/3022Cannon-bug死锁的问题问题来源于main_shift()这个函数中MPI函数的使用。在Cannon-mpi代码的main_shift()模块中，文献中算法使用的是MPI的阻塞通信阻塞通信函数:MPI_Send/MPI_Recv,这就使得Cannon算法在执行循环左移
17、和循环上移时，矩阵规模超过共享buff的容量时出现循环等待循环等待的死锁死锁状况。在曙光4000集群系统上，该算法的发生死锁的矩阵下限规模是200200的浮点型矩阵。第22页，本讲稿共27页2022/11/3023Cannon-bug原始（阻塞式）的原始（阻塞式）的原始（阻塞式）的原始（阻塞式）的main_shiftmain_shift模块：模块：模块：模块：voidmain_shift()/*将分块b左移位*/MPI_Send(a,dl2,MPI_FLOAT,get_index(my_row,my_col-1,sp),1,MPI_COMM_WORLD);MPI_Recv(a,dl2,MPI_
18、FLOAT,get_index(my_row,my_col+1,sp),1,MPI_COMM_WORLD,&status);/*将分块b上移位*/MPI_Send(b,dl2,MPI_FLOAT,get_index(my_row-1,my_col,sp),1,MPI_COMM_WORLD);MPI_Recv(b,dl2,MPI_FLOAT,get_index(my_row+1,my_col,sp),1,MPI_COMM_WORLD,&status);第23页，本讲稿共27页2022/11/3024Cannon-bug改进（非阻塞式）的改进（非阻塞式）的改进（非阻塞式）的改进（非阻塞式）的mai
19、n_shiftmain_shift模块模块模块模块ci*dl+j+=ai*dl+k*bj*dl+k;/改进了的Cannon按行存取/*将分块a左移位*/MPI_Isend(a,dl2,MPI_FLOAT,get_index(my_row,my_col-1,sp),1,MPI_COMM_WORLD,&myrequest_s);MPI_Irecv(buf,dl2,MPI_FLOAT,get_index(my_row,my_col+1,sp),1,MPI_COMM_WORLD,&myrequest_r);MPI_Wait(&myrequest_s,&status);MPI_Wait(&myreque
20、st_r,&status);memcpy(a,buf,sizeof(float)*dl2);/*将分块b上移位*/MPI_Isend(b,dl2,MPI_FLOAT,get_index(my_row-1,my_col,sp),1,MPI_COMM_WORLD,&myrequest_s);MPI_Irecv(buf,dl2,MPI_FLOAT,get_index(my_row+1,my_col,sp),1,MPI_COMM_WORLD,&myrequest_r);MPI_Wait(&myrequest_s,&status);MPI_Wait(&myrequest_r,&status);memcp
21、y(b,buf,sizeof(float)*dl2);第24页，本讲稿共27页2022/11/3025Cannon-bugCannon-bugMPI_Irecv仅仅初始化接受操作,在与之对应的MPI_Wait函数的调用返回之前，将不能访问bufferMPI_Irecv函数返回时，handle指向一个MPI_Request对象，它代表了一个已近初始化了的通信操作。这个函数并不返回一个指向MPI_Status对象的指针，因为实际的接受操作并未完成。MPI_Wait会一直阻塞，直至参数handle所关联的操作完成，对发送来说，此时就可以向缓冲区写入新的值。而对接收来说，便可以从缓冲区读取消息，而st
22、atus所指向的MPI_Status对象包含了所接收消息的信息。新增加buf的目的就是防止在a还未发送出去的时候就recv内容至a中导致信息的错误，只有在MPI_Wait返回以后，再调用mencpy将buf的内容写回a中，完成更新。第25页，本讲稿共27页2022/11/3026CannonCannon乘法乘法乘法乘法mpimpi代码主要模块代码主要模块代码主要模块代码主要模块intget_index(introw,intcol,intsp)/处理器逻辑阵列坐标至rank号的转换voidrandom_A_B()/随机生成矩阵A/Bvoidscatter_A_B()/rank=0的处理器向外分发
23、A,B的相关块voidinit_alignment()/矩阵A/B初始对齐Voidmain_shift()/分块矩阵左移和上移，并计算分块c这个模块就是我改造该算法的重点部位这个模块就是我改造该算法的重点部位voidcollect_c()/rank=0的处理器从其余处理器收集分块矩阵cvoidprint(float*m,char*str)/打印矩阵intmain(intargc,chat*argv)/主过程，cannon算法，矩阵相乘第26页，本讲稿共27页2022/11/3027Cannon-reviewCannon-review循环移位对齐左移上移分而治之的并行计算思想任务划分数据划分精简通讯All-to-AllPoint-to-Point第27页，本讲稿共27页