基础并行算法与开源软件.ppt

基础并行算法及其开源软件,计算力学研究所,算法是解题方法的精确描述，是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。并行算法（ParallelAlgorithm）是一些可同时执行的诸进程的集合，这些进程相互作用和协调动作从而达到给定问题的求解。并行算法可以分成数值计算和非数值计算的并行算法。并行数值算法就是求解诸如矩阵运算、多项式求值、求解线性方程组等数值计算问题的并行算法。,在科学与工程计算的许多问题中，数值计算问题，特别是矩阵相乘、求解线性方程组和矩阵特征值问题是最基本的内核。随着MPP(MassivelyParallelProcessing)并行计算机、机群以及消息传递并行环境（MPI等）的不断发展和完善，为了充分发挥分布式并行计算机的功效，掌握针对分布式并行计算机的并行数值计算方法变得越来越重要。这里着重考虑矩阵向量运算和求解线性方程组的多种并行算法。,第一节并行矩阵向量乘法,预备几个记号,内积,Saxpy,Gaxpy,串行矩阵向量乘法,称之为Gaxpy,常规方式是每次修正一个分量,Gaxpy：行型算法,例：,Gaxpy：列型算法,例：,Ax表示成为A的列向量的线性组合。,矩阵的划分,带状划分：将矩阵整行或整列地分成若干个组，每组指派给一个处理器。这些行列可以是连续的，也可以是等距相间的，前者称为块带状划分，后者称为循环带状划分。,nn的矩阵（0,1,n-1)，p个处理器(0,1,p-1),块带状划分：每个处理器均匀连续地分配有n/p行（列），其中第i个处理器上包含：,P0,P1,P2,P3,0123,4567,891011,12131415,以4个处理器，16列矩阵为例,假设n能被p整除,循环带状划分：每个处理器均匀相间地分配有n/p行（列），其中第i个处理器上包含：,以4个处理器，16列矩阵为例,棋盘划分：将方阵划分成若干个子方阵，每个子方阵指派给一个处理器，此时每个处理器均不包含整行或整列。棋盘划分也可分为块棋盘划分和循环棋盘划分。,nn的矩阵（0,1,n-1)，p个处理器（组成的二维处理器阵列），每个处理器均匀地分配有个矩阵元素。,块棋盘划分：,以16个处理器，88矩阵为例,循环棋盘划分：,行块带状划分的矩阵向量乘法,划分成p块，假设n能被p整除，第k块：（0kp-1),假设Ak，xk，yk存储再进程k上，分别存在局部存储器,在给定进程k上，每步计算中需要用到的子矩阵A的行标号始终不变，说明在每步计算时用到的A的块实际上都一直处于本进程上。而x的块位于不同的处理机上，需要进行数据通信。本处采用每计算一次将x的块在同列进程中循环上移一个位置的方式来实现这种数据通信。算法具体描述如下：,算法：,以p3，n3为例，yAx,第1步,第2步,第3步,P0,P1,P2,第二节并行矩阵矩阵乘法,串行矩阵矩阵乘法,矩阵乘法：ijk形式，标量描述,矩阵乘法中三个求和循环可任意排序，从而一共3！6种形式，如jki形式（标量描述）,这6种可能性（ijk,jik,ikj,jki,kij,kji）的任何一个都对应一内层运算，而且具有自己数据流动形式。例如ijk形式，内层运算是点积，数据用到的是A的行和B的列。,矩阵乘法：点积形式（ijk）,记,则上述算法可表示为,进一步可表示为,其中,或表示为,ijk形式的内部两层循环实质上是基于行的Gaxpy运算,矩阵乘法：Saxpy形式（jki）,假定A和C的列分划为,比较两边第j列，可知,一系列Saxpy运算,k循环实质上是一Gaxpy运算,得到如下算法,矩阵乘法：外积形式,考虑kji形式,记,则内部的两层循环是一个外积修正,可得到以下算法,可见其中的AB是p个外积之和。,并行矩阵矩阵乘法,假设,行列划分算法,将A和B矩阵分别划分为如下的行块子矩阵和列块子矩阵,算法中ClCmyid,l，AAmyid，B在处理器中每次循环向前移动一个处理器。mm1myid1pmodp。,初始状态，Ai、Bi和Cij(j=0,1,p-1)存放在Pi中。,为矩阵,将Cij的计算放在Pi上进行，这样在初始数据分布时，数据Ai已经在Pi上，但进程Pi上只有Bi，其它Bj处于其它进程上，需要对B的块进行循环移位的方式实现。由于使用p个处理器，每次每个处理器计算出一个Cij，计算C需要p次计算。Cij的计算是按对角线进行的，计算流程如下：,以p3，n3为例，CAB,第1步,第2步,第3步,P0,P1,P2,行行划分算法,初始状态，Aij、Bi和Ci(j=0,1,p-1)存放在Pi中。将Ci的计算放在Pi上进行，这样在初始数据分布时，数据Ai已经在Pi上，但进程Pi上只有Bi，其它Bj处于其它进程上，需要对B的块进行循环移位的方式实现。,以p3，n3为例，CAB,第1步,第2步,第3步,P0,P1,P2,与Saxpy形式、ikj形式对应,列列划分算法,初始状态，Aj、Bi,j和Cj(i=0,1,p-1)存放在Pj中。将Cj的计算放在Pj上进行，这样在初始数据分布时，数据Bj已经在Pj上，但进程Pi上只有Aj，其它Ai处于其它进程上，需要对A的块进行循环移位的方式实现。,以p3，n3为例，CAB,第1步,第2步,第3步,P0,P1,P2,与Saxpy形式、jki形式对应,列行划分算法,假设C按列存放,初始状态，Ai、Bi,j和Ci(i=0,1,p-1)存放在Pi中。将Cj的计算放在Pj上进行，这样在初始数据分布时，数据Ai和Bi都已经在Pi上，每次计算得到Cj的部分和，存储在Pj上，需要数据通信实现这种存储。,以p3，n3为例，CAB,第1步,第2步,第3步,P0,P1,P2,与外积形式、kji形式对应,第三节并行数值分析软件简介,ScaLAPACK：可扩展线性代数库,Aztec：并行迭代解法器库,PETSc：可移植可扩展科学计算工具箱,LAPACK：线性代数库,BLAS：基本线性代数子程序库,