高性能矩阵乘法PPT课件

《高性能矩阵乘法PPT课件》由会员分享，可在线阅读，更多相关《高性能矩阵乘法PPT课件（27页珍藏版）》请在装配图网上搜索。

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

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

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

4、3-147 称为棋盘划分 Description for implementation of MPI program to compute Matrix Matrix Multiplication using block checkerboard partitioning and Cannon Algorithm 2023-3-148 Computing the matrix-matrix multiplication on SMP System.Use block checkerboard partitioning of the matrices and Cannons Algorithm.

5、Size of the square matrices p=q2 and the size of square matrices A and B is evenly divisible by q.It is assumed that the number of blocks are equal to the number of processors.2023-3-149 Cannons algorithm is based on cartesian virtual topologyA and B are square matrices of size n and C be the output

6、 matrix.These matrices are dived into blocks or submatrices to perform matrix-matrix operations in paralleln x n matrix A can be regarded as q x q array of blocks Ai,j(0=i q,0=j q)such that each block is an(n/q)x(n/q)submatrixWe use p processors to implement the block version of matrix multiplicatio

7、n in parallel by choosing q as a square root of p and compute a distinct block Ci,j on each processor.2023-3-1410 2023-3-1411 The matrices A and B are partitioned into p blocks,A i,j and B i,j(0=i q,0=j q)of size (n/q x n/q)on each process.These blocks are mapped onto a q x q logical mesh of process

8、es.The processes are labeled from P0,0 to Pq-1,q-1.2023-3-1412 Process Pi,j initially store block matrices Ai,j and Bi,j and computes block Ci,j of result matrix.To compute submatrix Ci,j,we need all submatrices,Ai,k and Bk,j(0=k q).To acquire all the required blocks,an all-to-all broadcast of matri

9、x Ai,j s is performed in each row and similarly in each column of matrix Bi,js.MPI collective communication is used to perform this operations.2023-3-1413 After Pi,j acquires,A i,0,A i,1,A i,2,A i,q-1 and B0,j,B1,j,B2,j,Bq-1,j,it performs the serial block matrix to matrix multiplication and accumula

10、tes the partial block matrix Ci,j of matrix C.To obtain the resultant product matrix C,processes with rank 0 gathers all the block matrices by using MPI_Gather collective communication operation.2023-3-1414 p processors arranged in q x q square grid of processors and the input matrices.A and B are d

11、istributed among the processes in checkerboard fashion.It results in constructing p block matrices of A and B.It uses only point-to-point communication for circularly shifting blocks of matrix A and matrix B among p processes.2023-3-1415 The algorithm proceeds in q stages.The first step in this algo

12、rithm is to perform initial alignment of the block matrix A and block matrix B.The blocks of matrix A are circularly shifted to the i positions to left in the row of the square grid of processes,where i is the row number of the process in the mesh.The blocks of matrix B are circularly shifted j posi

13、tions upwards,where j is the column number of the process in the processes mesh.2023-3-14162023-3-1417 The algorithm performs the following steps in each stage:1.Multiply the block of matrix A and matrix B and add the resultant matrix to get the block matrix C,which is initially set to zero.2.Circul

14、arly shift the blocks of matrix A to left in the rows of the processes and the blocks of matrix B upwards in the columns of the square grid of processes in a wrap around manner.2023-3-14182023-3-14192023-3-14202023-3-1421 MPI_Send and MPI_Recv is not used for point-to-point communicationbecause if a

15、ll the processes call MPI_Send or MPI_Recv in different order thesituation may arise.How to fix?指派一个缓冲区，使用MPI_Irecv/MPI_Isend 非阻塞式通讯函数，MPI_wait.MPI_Sendrecv.2023-3-1422死锁的问题问题来源于main_shift()这个函数中MPI函数的使用。在Cannon-mpi代码的main_shift()模块中，文献中算法使用的是MPI的阻塞通信阻塞通信函数:MPI_Send/MPI_Recv,这就使得Cannon算法在执行循环左移和循环上移

16、时，矩阵规模超过共享buff的容量时出现循环等待循环等待的死锁死锁状况。在曙光4000集群系统上，该算法的发生死锁的矩阵下限规模是200200的浮点型矩阵。2023-3-1423 void main_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_FLOAT,get_index(my_row,my_col+1,sp),1,MPI_COMM_WORLD,&status);/*将分块b上移位*/MPI_Send(b,dl2,MP

17、I_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);2023-3-1424 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(bu

18、f,dl2,MPI_FLOAT,get_index(my_row,my_col+1,sp),1,MPI_COMM_WORLD,&myrequest_r);MPI_Wait(&myrequest_s,&status);MPI_Wait(&myrequest_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

19、_index(my_row+1,my_col,sp),1,MPI_COMM_WORLD,&myrequest_r);MPI_Wait(&myrequest_s,&status);MPI_Wait(&myrequest_r,&status);memcpy(b,buf,sizeof(float)*dl2);2023-3-1425MPI_Irecv仅仅初始化接受操作,在与之对应的MPI_Wait函数的调用返回之前，将不能访问bufferMPI_Irecv函数返回时，handle指向一个MPI_Request对象，它代表了一个已近初始化了的通信操作。这个函数并不返回一个指向MPI_Status对象的指

20、针，因为实际的接受操作并未完成。MPI_Wait会一直阻塞，直至参数handle所关联的操作完成，对发送来说，此时就可以向缓冲区写入新的值。而对接收来 说，便可以从缓冲区读取消息，而status所指向的MPI_Status对象包含了所接收消息的信息。新增加buf的目的就是防止在a还未发送出去的时候就recv内容至a中导致信息的错误，只有在MPI_Wait返回以后，再调用mencpy将buf的内容写回a中，完成更新。2023-3-1426int get_index(int row,int col,int sp)/处理器逻辑阵列坐标至rank号的转换 void random_A_B()/随机生成矩

21、阵A/Bvoid scatter_A_B()/rank=0的处理器向外分发A,B的相关块void init_alignment()/矩阵A/B初始对齐Void main_shift()/分块矩阵左移和上移，并计算分块c这个模块就是我改造该算法的重点部这个模块就是我改造该算法的重点部位位 void collect_c()/rank=0的处理器从其余处理器收集分块矩阵c void print(float*m,char*str)/打印矩阵 int main(int argc,chat*argv)/主过程，cannon算法，矩阵相乘2023-3-1427 循环移位对齐 左移 上移 分而治之的并行计算思想 任务划分 数据划分 精简通讯 All-to-All Point-to-Point