|
高斯消去法SSE并行化研究報告 一、 問題描述 題目：高斯消去法（LU分解）串行算法如下面?zhèn)未a所示，計算模式如圖1所示（第k步時第k行的除法運算，和后續(xù)行減去第k行的運算）。設(shè)計實現(xiàn)SSE算法，加速計算過程。提交研究報告（問題描述、SSE算法設(shè)計與實現(xià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實現(xiàn)，并且測試所用時間，再改變問題規(guī)模，觀察隨著問題規(guī)模的變化，所用時間與串行時間比例的變化。最后分析一下判斷并行算法的性能是否足夠好。 二、 SSE算法設(shè)計和實現(xiàn) 算法設(shè)計： 分析此算法，首先外層循環(huán)無法并行化，因為在不同的循環(huán)中，相同位置的元素都會改變。內(nèi)部的將對角線元素變?yōu)?和下面元素變?yōu)?都是可以并發(fā)執(zhí)行的。由此獲得解題思路。但是在實際操作的工程中發(fā)現(xiàn)并行運行時間有時候要比串行運行時間多，所以又進行了部分并行（只對置零操作進行并行）,發(fā)現(xiàn)有時候要比全部并行的效果好。 實現(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為單位進行循環(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為單位進行循環(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; } } } 三、 實驗及結(jié)果分析 注：實驗結(jié)果為每次運行5次程序取平均值 根據(jù)實驗數(shù)據(jù)繪制以下圖表： 從圖表中可以明顯看出來，在運算的數(shù)據(jù)較少的時候，并行算法和串行算法的速率幾乎沒有區(qū)別，串行算法甚至比并行算法快。但是隨著數(shù)據(jù)量的增長，可以明顯看到并行速度要比串行的速度快很多。注意其中的數(shù)據(jù)量為512和1024的位置，要比之前快的還要明顯。尤其是數(shù)據(jù)量為1000和1024的對比。說明當(dāng)數(shù)據(jù)量為4的整數(shù)倍的時候，SSE并行算法發(fā)揮的用更大一些。 這張圖中看的更明顯一些。在數(shù)據(jù)量為512的時候，速率比要比在1000的時候高。當(dāng)數(shù)據(jù)量為1024的時候，只是比1000多了24個數(shù)據(jù)，但是速率明顯的提升了。 從圖中可以看出，在數(shù)據(jù)量為1000左右的時候，部分并行是要快于全部并行的。 總結(jié)： 此并行算法對串行算法進行了性能上的優(yōu)化。在數(shù)據(jù)量越來越多的時候，優(yōu)化的效果也越來越好。并且當(dāng)數(shù)據(jù)量為4的整數(shù)倍的時候，優(yōu)化效果尤其明顯。 附加： 在做完實驗之后，我在想并行算法中，如果先處理大部分數(shù)據(jù)，之后處理小于4個的數(shù)據(jù)，效率會不會有變化，所以添加了以下實驗： 觀察可以看到，除了在數(shù)據(jù)過小的時候結(jié)果有一些偏差以外，其他情況兩種并行算法的方式都是差不多的。但同時可以看出來先處理大部分數(shù)據(jù)再處理小部分數(shù)據(jù)要快一些。 在全部完成后，使用codeblock重復(fù)以上實驗步驟，使用了-O2加速（因為-O3本身采取的就是SSE方式，所以采用了-O2加速）。 得到如下實驗結(jié)果： 得到以下圖表： 從表格和圖表中可以看出，在數(shù)據(jù)較小的時候，由于并行本身的花銷，串行算法要優(yōu)于并行算法。隨著數(shù)據(jù)量的增加，串行算法的運行時間線性增加，但并行算法的固定開銷卻是穩(wěn)定在一定范圍內(nèi)的，甚至在數(shù)據(jù)量達到一定規(guī)模的時候，這個開銷可以忽略。所以時間比越來越大，最后甚至大于三倍。再看部分并行和全部并行。在數(shù)據(jù)量處于中間范圍的時候，可以看出部分并行要比全部并行的加速比大，推測還是并行開銷的問題。當(dāng)數(shù)據(jù)量逐漸增加的時候，在圖中可以看出在數(shù)據(jù)量大于1000的時候，全部并行的加速比要大于部分并行的加速比。以后可以根據(jù)數(shù)據(jù)規(guī)模選擇并行程度。 | 
