划分的矩阵乘法并行算法.ppt

* *  高性能矩阵乘法 夏霏 xiafei@mail.ustc.edu.cn  * * 并行算法优化研究相对于传统面向对象串行算法的4个挑战： 同步：两个或者多个线程协调其行为的过程 通信：与线程之间交换数据相关的带宽和延迟问题 负载均衡：多个线程之间工作量分布的情况，给各个线程（执行核）分配均匀的工作 可扩展性：衡量在性能更加强劲的系统上运行软件时能否有效利用更多线程的指标， 观察应用程序在更高级的平台上运行 4核到8核线性增长 * * 多线程（核）设计主要分解模式 任务分解： 对程序根据其执行的功能进行分解的过程 数据分解： 将应用程序根据各任务所处理的数据而非按任务的天然特性来进行分解 数据流分解： 研究数据在诸任务之间如何流动，根据任务之间的数据流关系对问题 进行分解 模式 分解方式 任务级并行模式 任务分解 Divide and Conquer 任务/数据分解 几何分解模式 数据分解 流水线模式 数据流分解 波峰（wavefront）模式 数据流分解 * * 多线程（核）设计主要分解模式 任务分解： 对程序根据其执行的功能进行分解的过程 数据分解： 将应用程序根据各任务所处理的数据而非按任务的天然特性来进行分解 数据流分解： 研究数据在诸任务之间如何流动，根据任务之间的数据流关系对问题 进行分解 分解方式 设计 说明 任务分解 不同的程序行为采用不同的线程实现 常用于GUI应用程序 数据分解 多个线程对不同的数据块执行相同的操作 常用于音频、图像处理和科学计算应用程序 数据流分解 一个线程的输出作为另一个线程的输入 尤其应注意尽量消除启动和排空延迟 * * 矩阵乘法算法探讨 在工程科学计算中，矩阵乘积是最基本的运算 典型的n阶稠密方阵乘积算法的时间复杂度是O(n3) 。 目前对大型矩阵乘积运算的处理主要是采用分治思想，将矩阵分布在多个节点上，但每个结点上的小矩阵仍要立方级乘法次数。 基于分之思想的两种划分策略：条形划分和块状（棋盘）划分的6种常见分布式矩阵乘法并行算法。 * * 基于不同划分策略的矩阵乘法算法探讨 1、条形（striped partitioning）划分的矩阵乘法并行算法 行条划分 列条划分 两两组合：行列、行行、列列、列行 * * 基于不同划分策略的矩阵乘法算法探讨 2、块状划分(checkerboard partitioning)的矩阵乘法并行算法 称为棋盘划分 Cannon Description for implementation of MPI program to compute Matrix Matrix Multiplication using block checkerboard partitioning and Cannon Algorithm * * Cannon Objective? Computing the matrix-matrix multiplication on SMP System. Use block checkerboard partitioning of the matrices and Cannons Algorithm.? Assumption 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. * * Cannon Cannons algorithm is based on cartesian virtual topology A and B are square matrices of size n and C be the output? matrix. These matrices are dived into blocks or submatrices to perform matrix-matrix operations in parallel n 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) submatrix We use p processors to implement t