一、         問題描述

題目：高斯消去法（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的整數倍的時候，優化效果尤其明顯。