Gauss―Seidel迭代法求解线性方程组的并行化研究.docVIP

Gauss―Seidel迭代法求解线性方程组的并行化研究 　　【摘 要】Gauss-Seidel迭代法在工程计算中具有广泛应用。高维矩阵对线性方程组的求解效率提出了新的要求。本文提出了两种模式下的Gauss-Seidel并行计算方法，并对比了在不同矩阵维数下的加速效率，得到了具有较高加速比的并行迭代方法。 　　【关键词】Gauss-Seidel；迭代法；并行；MPI；矩阵运算 　　1 问题背景与提出 　　在实际工程应用中经常需要用到求解维数较高的线性代数方程组，对于线性代数方程组的求解方法可以分成两类：直接法和迭代法，其中直接法得到的是方程组的真解，其求解过程为通过有限步四则运算，常用的实现方式是Gauss消去方法和矩阵的三角分解方法，这种计算方式在求解过程中会产生大量的非零元素，存储量和计算量均比较大，因此常用于求解低阶、稠密线性方程组。对于高维线性方程组，可以采用并行运算的方式进一步提高计算效率，Gauss-Seidel迭代法具有收敛速度快、计算稳定性好等优点，是求解高维线性方程组的常用方法，因此本文将对Gauss-Seidel迭代法的并行化进行研究，期望获取较高的运行效率和加速比。 　　2 Gauss-Seidel迭代法的并行算法描述 　　任务分配模式一：连续等分矩阵法 　　在《并行算法的设计与分析》一书中给出了一种矩阵分配的算法，设矩阵的阶为N，采用m个线程进行计算，则将矩阵等分成m块，每一块分到的任务量为N/m，每一个线程计算完自己的分量之后立刻向其他的线程进行广播。 　　由于Gauss-Seidel迭代法中，对于右端项的计算和中间项的计算是不需要用到下一次迭代值的，因此在这一阶段各个线程工作量相同，同时完成，问题的关键在于首项的计算，顺序等分矩阵时，以四个线程为例，在计算左端项的时候，各个线程的工作次序如下图所示。其中不同的颜色代表不同线程的任务，每个线程依次计算分给自己的一个子块，每计算完一个分量后立刻沿上方箭头所指方向进行广播。 　　任务分配模式二：离散等分矩阵法 　　为了改进任务分配模式一中的缺陷，进一步提高计算的并行程度，同时保持任务的均衡性，笔者对模式一中的任务分配方式作出了一定程度的改进，设线程数为m，则将矩阵以每m行作为一个单位，顺序分配给m个线程，前一个线程完成自己的计算任务之后，立刻将计算结果广播给其余的m个线程，同时开始下一个矩阵块中自己应完成的任务，直到最后将自己所应完成的N/m个分量计算完毕。任务分配模式见左图，其中不同的颜色代表不同的线程的计算任务，每个块右端的箭头表示变量的广播方向。 　　这样划分任务，每个线程的工作量没有发生变化，但是第一个达到终点的线程和最后一个达到终点的线程的时间相差仅为m个分量的计算时间。假设矩阵的阶为10000，采用4个线程进行计算（m=4），那么第一个线程和最后一个线程到达终点的时间差为m=4个分量的计算时间。反观第一种任务分配模式，假设第一个线程计算完自己的N/m=10000/4=2500个分量，则需要再经过计算2500、5000、7500个分量的时间之后二、三、四号线程才能到达终点，并且随着矩阵阶的增大，这个时间差异还会继续增大。 　　根据上面的分析，在理论上模式二具有更优的时间性能。笔者也进行了实验，从实际操作上证明了模式二具有更优的时间性能。因此选择模式二作为并行化的基本算法，基本并行算法步骤可以描述如下： 　　（一）末项/中间项计算的并行化 　　（二）首项的并行计算 　　首项是下三角矩阵与本次迭代的结果相乘，因此不易实现并行化，但是借鉴并行计算中的流水线作业思想，可以采用步进和广播的方法进行并行化。假设核数为4，则首项的并行化可以设计如下： 　　2.2 基于MPI的多核并行算法的设计 　　采用任务分配模式二，采用MPI的并行算法可以描述如下： 　　int N：矩阵的阶数 　　int numProcs：用于计算的进程数量 　　int m：每个进程所分得的任务量，m=N/numProcs 　　int myID：标识本进程的进程号 　　int task：记录本次循环中本线程计算的未知量下标 　　double A[m][numProcs]：每个进程单独 　　保存属于自己的矩阵分块 　　double x_old[N]：double类型的N维数组，用于保存本次迭代分量的数值 　　double sum[N]：保存迭代分量计算过程中的累加结果； 　　double x_diff：相邻两次迭代运算中的误差，定义为：x_diff=（_1≤i≤N）|x_i^（（k+1） ）-x_i^（（k） ） | 　　bool x_status[N]：标识每个迭代分量是否完成本次迭代 　　算法描述： 　　//进入并行域