高斯消去法(LU分解)SSE并行化研究报告 带源代码

一、         问题描述

题目：高斯消去法（LU分解）串行算法如下面伪代码所示，计算模式如图1所示（第k步时第k行的除法运算，和后续行减去第k行的运算）。设计实现SSE算法，加速计算过程。提交研究报告（问题描述、SSE算法设计与实现、实验及结果分析）和源码（只将程序文件和工程文件提交，不要将编译出的目标文件和可执行文件也打包提交）。

1.procedure LU (A)

2. begin

3.    for k := 1 to n do

4.           for j := k+1 to n do

5.                  A[k, j] := A[k, j]/A[k, k];

6            A[k, k] := 1.0;

7.           endfor;

8.           for i := k + 1 to n do

9.                  for j := k + 1 to n do

10.                       A[i, j] := A[i, j] - A[i,k] × A[k, j ];

11.         endfor;

12.         A[i, k] := 0;

13.  endfor;

14.endfor;

15. end LU

综合以上分析一下，作业的目的就是找到上面的算法可以并行执行的部分，将这部分用SSE实现，并且测试所用时间，再改变问题规模，观察随着问题规模的变化，所用时间与串行时间比例的变化。最后分析一下判断并行算法的性能是否足够好。

二、         SSE算法设计和实现

算法设计：

分析此算法，首先外层循环无法并行化，因为在不同的循环中，相同位置的元素都会改变。内部的将对角线元素变为1和下面元素变为0都是可以并发执行的。由此获得解题思路。但是在实际操作的工程中发现并行运行时间有时候要比串行运行时间多，所以又进行了部分并行（只对置零操作进行并行）,发现有时候要比全部并行的效果好。

实现：

1）          基本串行算法：

voidbasic_change() {//基本的串行算法

     for (int k =0; k < MAX; k++)

     {

         for (int j =k; j < MAX; j++)

              A[k][j] /= A[k][k];

         A[k][k] = 1;

         for (int i =k + 1; i < MAX; i++)

          {

              for (int j =k + 1; j < MAX; j++)

                   A[ i][j] = A[ i][j] - A[ i][k] *A[k][j];

              A[ i][k] = 0;

         }

     }

}

2）          并行算法：

voidpara_change_impr() {//并行算法

     __m128 t1,t2, t3;

     for (int k =0; k < MAX; k++)

     {

//此处需要并行处理

         int off= (MAX - k - 1) % 4;

         for (int j =k + 1; j < k + 1 + off; j++)

              A[k][j] /= A[k][k];

         t2=_mm_loadu_ps(A[k] + k);

         for (int j =k + 1 + off; j < MAX; j += 4)

         {

              t1 =_mm_loadu_ps(A[k] + j);

              t1 =_mm_div_ps(t1,t2);

              _mm_store_ss(A[k] + j, t1);

         }

         A[k][k] = 1;

         for (int i =k + 1; i < MAX; i++)

         {

              //此处不再以1位单位而是以4为单位进行循环

              for (int j =k + 1; j < k + 1 + off; j++)

                   A[ i][j] = A[ i][j] - A[ i][k] *A[k][j];

              for (int j =k + 1 + off; j < MAX; j += 4)

              {

                   t2 =_mm_loadu_ps(A[ i] + k);

                   t3 =_mm_loadu_ps(A[k] + j);

                   t1 =_mm_loadu_ps(A[ i] + j);

                   t2 =_mm_mul_ps(t2, t3);

                   t1 =_mm_sub_ps(t1, t2);

                   _mm_store_ss(A[ i] + j, t1);

              }

              A[ i][k] = 0;

         }

     }

}

3）          部分并行：

voidpara_change() {//并行算法

     __m128 t1,t2, t3;

     for (int k =0; k < MAX; k++)

     {

         for (int j =k + 1; j < MAX; j++)

              A[k][j] /= A[k][k];

         A[k][k] = 1;

         //此处需要并行处理

         for (int i =k + 1; i < MAX; i++)

         {

              //此处不再以1位单位而是以4为单位进行循环

              int off= (MAX - k - 1) % 4;

              for (int j =k + 1; j < k + 1 + off; j++)

                   A[ i][j] = A[ i][j] - A[ i][k] *A[k][j];

              for (int j =k + 1 + off; j < MAX; j += 4)

              {

                   t2 =_mm_loadu_ps(A[ i] + k);

                   t3 =_mm_loadu_ps(A[k] + j);

                   t1 =_mm_loadu_ps(A[ i] + j);

                   t2 =_mm_mul_ps(t2, t3);

                   t1 =_mm_sub_ps(t1, t2);

                   _mm_store_ss(A[ i] + j, t1);

              }

              A[ i][k] = 0;

         }

     }

}

三、         实验及结果分析

根据实验数据绘制以下图表：

从图表中可以明显看出来，在运算的数据较少的时候，并行算法和串行算法的速率几乎没有区别，串行算法甚至比并行算法快。但是随着数据量的增长，可以明显看到并行速度要比串行的速度快很多。注意其中的数据量为512和1024的位置，要比之前快的还要明显。尤其是数据量为1000和1024的对比。说明当数据量为4的整数倍的时候，SSE并行算法发挥的用更大一些。

这张图中看的更明显一些。在数据量为512的时候，速率比要比在1000的时候高。当数据量为1024的时候，只是比1000多了24个数据，但是速率明显的提升了。

从图中可以看出，在数据量为1000左右的时候，部分并行是要快于全部并行的。

总结：

此并行算法对串行算法进行了性能上的优化。在数据量越来越多的时候，优化的效果也越来越好。并且当数据量为4的整数倍的时候，优化效果尤其明显。