文档介绍：基础并行算法及其开源软件计算力学研究所算法是解题方法的精确描述,是一组有穷的规则,它们规定了解决某一特定类型问题的一系列运算。并行算法( Parallel Algorithm )是一些可同时执行的诸进程的集合, 这些进程相互作用和协调动作从而达到给定问题的求解。并行算法可以分成数值计算和非数值计算的并行算法。并行数值算法就是求解诸如矩阵运算、多项式求值、求解线性方程组等数值计算问题的并行算法。在科学与工程计算的许多问题中,数值计算问题,特别是矩阵相乘、求解线性方程组和矩阵特征值问题是最基本的内核。随着 MPP(Massively Parallel Processing) 并行计算机、机群以及消息传递并行环境( MPI 等)的不断发展和完善,为了充分发挥分布式并行计算机的功效,掌握针对分布式并行计算机的并行数值计算方法变得越来越重要。这里着重考虑矩阵向量运算和求解线性方程组的多种并行算法。第一节并行矩阵-向量乘法?预备--几个记号内积 yxc T? Saxpy yax y?? Gaxpy y Ax y?? end ni for c)()( :1 0???? end iyiax iy ni for)()()( :1????串行矩阵-向量乘法 nmRA ?? nRx? mRy?y Ax y??假定计算称之为 Gaxpy miyxay i nj j iji:1, 1?????常规方式是每次修正一个分量 Gaxpy :行型算法 end end iyjxjiAiy nj for mi for)()(),()( :1 :1????例: ????????????????????????????????????8675 8473 82718 765 43 21 Gaxpy :列型算法 end end iyjxjiAiy mi for nj for)()(),()( :1 :1????例: ??????????????????????????????????????????????????????????6 4 285 3 17 8675 8473 82718 765 43 21 Ax 表示成为 A的列向量的线性组合。?矩阵的划分带状划分: 将矩阵整行或整列地分成若干个组,每组指派给一个处理器。这些行列可以是连续的,也可以是等距相间的,前者称为块带状划分,后者称为循环带状划分。 n×n的矩阵( 0,1, …,n-1) ,p个处理器(0,1, …,p-1) 块带状划分: 每个处理器均匀连续地分配有 n/p 行(列),其中第 i个处理器上包含: )10(1)1 )(/(,,1)/(,)/(??????piipnipnipn? P0 P1 P2 P3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 以4个处理器, 16 列矩阵为例假设 n能被 p整除循环带状划分: 每个处理器均匀相间地分配有 n/p 行(列),其中第 i个处理器上包含: )10()1/(,,2,,???????pippnipipii? P0 P1 P2 P3 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11 15 以4个处理器, 16 列矩阵为例棋盘划分: 将方阵划分成若干个子方阵,每个子方阵指派给一个处理器,此时每个处理器均不包含整行或整列。棋盘划分也可分为块棋盘划分和循环棋盘划分。 n×n的矩阵( 0,1, …,n-1) ,p个处理器(组成的二维处理器阵列), 每个处理器均匀地分配有个矩阵元素。块棋盘划分: pp?pnpnpn/)/()/( 2??以 16 个处理器, 8×8矩阵为例 P 00P 10P 20P 30 P 01P 02P 03 P 11P 21P 31 P 12P 13 P 22P 32 P 23P 33 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 P 00P 10P 20P 30 P 01P 02P 03 P 11P 21P 31 P 12P 13 P 22P 32 P 23P 33 0 4 1 5 2 6 3 7 0 4 1 5 2 6 3 7 循环棋盘划分: ?行块带状划分的矩阵向量乘法?? 1,1,0,?? pk kkkA AAA?划分成 p块,假设 n能被 p整除,第 k块:( 0≤ k ≤ p-1) ??????????????????????????????????????????????????? pnpnjpnpnkpnjpnpnkpnjpnpnk pnpnjpnkpnjpnkpnjpnk pnpnjpnkpnjpnkpnjpnkjka aa a aa a aaA //,//2/,//1/,// //,2/2/,2/1/,2/ //,1/2/,1