一、         問(wèn)題描述

題目：高斯消去法（LU分解）串行算法如下面?zhèn)未�碼所示，計(jì)算模式如圖1所示（第k步時(shí)第k行的除法運(yùn)算，和后續(xù)行減去第k行的運(yùn)算）。設(shè)計(jì)實(shí)現(xiàn)SSE算法，加速計(jì)算過(guò)程。提交研究報(bào)告（問(wèn)題描述、SSE算法設(shè)計(jì)與實(shí)現(xiàn)、實(shí)驗(yàn)及結(jié)果分析）和源碼（只將程序文件和工程文件提交，不要將編譯出的目標(biāo)文件和可執(zhí)行文件也打包提交）。

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

綜合以上分析一下，作業(yè)的目的就是找到上面的算法可以并行執(zhí)行的部分，將這部分用SSE實(shí)現(xiàn)，并且測(cè)試所用時(shí)間，再改變問(wèn)題規(guī)模，觀察隨著問(wèn)題規(guī)模的變化，所用時(shí)間與串行時(shí)間比例的變化。最后分析一下判斷并行算法的性能是否足夠好。

二、         SSE算法設(shè)計(jì)和實(shí)現(xiàn)

算法設(shè)計(jì)：

分析此算法，首先外層循環(huán)無(wú)法并行化，因?yàn)樵诓煌�的循環(huán)中，相同位置的元素都會(huì)改變。內(nèi)部的將對(duì)角線元素變?yōu)?和下面元素變?yōu)?都是可以并發(fā)執(zhí)行的。由此獲得解題思路。但是在實(shí)際操作的工程中發(fā)現(xiàn)并行運(yùn)行時(shí)間有時(shí)候要比串行運(yùn)行時(shí)間多，所以又進(jìn)行了部分并行（只對(duì)置零操作進(jìn)行并行）,發(fā)現(xiàn)有時(shí)候要比全部并行的效果好。

實(shí)現(xiàn)：

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為單位進(jìn)行循環(huán)

              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為單位進(jìn)行循環(huán)

              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;

         }

     }

}

三、         實(shí)驗(yàn)及結(jié)果分析

根據(jù)實(shí)驗(yàn)數(shù)據(jù)繪制以下圖表：

從圖表中可以明顯看出來(lái)，在運(yùn)算的數(shù)據(jù)較少的時(shí)候，并行算法和串行算法的速率幾乎沒(méi)有區(qū)別，串行算法甚至比并行算法快。但是隨著數(shù)據(jù)量的增長(zhǎng)，可以明顯看到并行速度要比串行的速度快很多。注意其中的數(shù)據(jù)量為512和1024的位置，要比之前快的還要明顯。尤其是數(shù)據(jù)量為1000和1024的對(duì)比。說(shuō)明當(dāng)數(shù)據(jù)量為4的整數(shù)倍的時(shí)候，SSE并行算法發(fā)揮的用更大一些。

這張圖中看的更明顯一些。在數(shù)據(jù)量為512的時(shí)候，速率比要比在1000的時(shí)候高。當(dāng)數(shù)據(jù)量為1024的時(shí)候，只是比1000多了24個(gè)數(shù)據(jù)，但是速率明顯的提升了。

從圖中可以看出，在數(shù)據(jù)量為1000左右的時(shí)候，部分并行是要快于全部并行的。

總結(jié)：

此并行算法對(duì)串行算法進(jìn)行了性能上的優(yōu)化。在數(shù)據(jù)量越來(lái)越多的時(shí)候，優(yōu)化的效果也越來(lái)越好。并且當(dāng)數(shù)據(jù)量為4的整數(shù)倍的時(shí)候，優(yōu)化效果尤其明顯。