并行计算实验指导(5)免费版new

《并行计算实验指导(5)免费版new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.支持免费共享2.6矩阵运算矩阵运算是数值计算中最重要的一类运算,特别是在线性代数和数值分析中,它是一种最基本的运算。本章讨论的矩阵运算包括矩阵转置、矩阵向量相乘、矩阵乘法、矩阵分解以及方阵求逆等。在讨论并行矩阵算法时分三步进行：①算法描述及其串行算法；②算法的并行化及其实现算法框架以及简单的算法分析；③算法实现的MPI源程序，以利于读者实践操作。2.1矩阵转置2.1.1矩阵转置及其串行算法对于一个n阶方阵A=[aij]，将其每一下三角元素aij(i>j)沿主对角线与其对称元素aji互换就构成了转置矩阵AT。假设一对数据的交换时间为一个单位时间，则下述矩阵转置(MatrixTra

2、nsposing)算法18.1的运行时间为(n2-n)/2=O(n2)。算法18.1单处理器上矩阵转置算法输入：矩阵An×n输出：矩阵An×n的转置ATn×nBeginfori=2tondoforj=1toi-1do交换a[i,j]和a[j,i]endforendforEnd图2.1子块转置1.1.1矩阵转置并行算法此处主要讨论网孔上的块棋盘划分(Block-CheckerBoardPartitioning，又称为块状划分)的矩阵转置算法，它对循环棋盘划分(Cyclic-CheckerBoardPartitioning)也同样适用。另外，超立方上块棋盘划分的矩阵转置算法可参见文献[

3、1]。实现矩阵的转置时，若处理器个数为p，且它们的编号依次是0,1,…,p-1，则将n阶矩阵A分成p个大小为m×m的子块，。p个子块组成一个的子块阵列。记其中第i行第j列的子块为Aij，它含有A的第(i-1)m+1至第im行中的第(j-1)m+1至第jm列的所有元素。对每一处理器按行主方式赋以二维下标，记编号为i的处理器的二维下标为(v,u)，其中，，将A的子块存入下标为(v,u)表示的对应处理器中。这样，转置过程分两步进行：第一步，子块转置，具体过程如图2.1所示；第二步，处理器内部局部转置。为了避免对应子块交换数据时处理器发生死锁，可令下三角子块先向与之对应的上三角子块发送数据

4、，然后从上三角子块接收数据；上三角子块先将数据存放在缓冲区buffer中，然后从与之对应的下三角子块接收数据；最后再将缓冲区中的数据发送给下三角子块。具体并行算法框架描述如下：算法18.2网孔上的矩阵转置算法输入：矩阵An×n输出：矩阵An×n的转置ATn×nBegin对所有处理器my_rank(my_rank=0,…,p-1)同时执行如下的算法:(1)计算子块的行号v=my_rank/sqrt(p),计算子块的列号u=my_rankmodsqrt(p)(2)if(u

5、所在的处理器中发来的子块else/*对存放上三角块的处理器*/(2.3)将所存的子块在缓冲区buffer中做备份(2.4)接收其对角块所在的处理器中发来的子块(2.5)将buffer中所存的子块发送到其对角块所在的处理器中endif(3)fori=1tomdo/*处理器内部局部转置*/forj=1toido交换a[i,j]和a[j,i]endforendforEnd若记ts为发送启动时间,tw为单位数据传输时间，th为处理器间的延迟时间，则第一步由于每个子块有n2/p个元素，又由于通信过程中为了避免死锁，错开下三角子块与上三角子块的发送顺序，因此子块的交换时间为；第二步，假定一对数

6、据的交换时间为一个单位时间，则局部转置时间为。因此所需的并行计算时间。MPI源程序请参见所附光盘。1.1矩阵-向量乘法1.1.1矩阵-向量乘法及其串行算法矩阵-向量乘法(Matrix-VectorMultiplication)是将一个n×n阶方阵A=[aij]乘以n×1的向量B=[b1,b2,…,bn]T得到一个具有n个元素的列向量C=[c1,c2,…,cn]T。假设一次乘法和加法运算时间为一个单位时间，则下述矩阵向量乘法算法18.3的时间复杂度为O(n2)。算法18.3单处理器上矩阵-向量乘算法输入：An×n，Bn×1输出：Cn×1Beginfori=0ton-1doc[i]=0

7、forj=0ton-1doc[i]=c[i]+a[i,j]*b[j]endforendforEnd1.1.2矩阵-向量乘法的并行算法矩阵-向量乘法同样可以有带状划分(StripedPartitioning)和棋盘划分(CheckerBoardPartitioning)两种并行算法。以下仅讨论行带状划分矩阵-向量乘法,列带状划分矩阵-向量乘法是类似的。设处理器个数为p，对矩阵A按行划分为p块，每块含有连续的m行向量，，这些行块依次记为A0,A1,…,Ap-1，分别存放在