課程論文_LU分解的OpenMP實(shí)現(xiàn)

1、并行算法實(shí)踐要求學(xué)生在KD60實(shí)驗(yàn)平臺(tái)上設(shè)計(jì)并行算法并實(shí)現(xiàn)。實(shí)驗(yàn)平臺(tái)由一塊處理板、一塊監(jiān)控板和一塊背板等組成。處理板邏輯結(jié)構(gòu)如圖1所示。處理板承載4個(gè)處理單元，每個(gè)處理單元包括一個(gè)龍芯3號(hào)四核CPU、2GB DDR2內(nèi)存、RTL8110千兆以太網(wǎng)卡芯片、BIOS Flash、串口收發(fā)芯片以及電源變換電路等。四個(gè)龍芯3號(hào)處理器通過HT總線實(shí)現(xiàn)互連。監(jiān)控電路檢測4個(gè)處理單元的狀態(tài)，并實(shí)現(xiàn)對其控制。 圖1 處理板邏輯結(jié)構(gòu)實(shí)驗(yàn)平臺(tái)的系統(tǒng)軟件以開源軟件為主（見圖2），具有兼容性強(qiáng)、易維護(hù)、易升級(jí)、易使用等特點(diǎn)。處理單元操作系統(tǒng)為Debian GNU/Linux無盤系統(tǒng)，采用穩(wěn)定高效的2.6.27內(nèi)核。圖

2、2 軟件系統(tǒng)結(jié)構(gòu)要求選修并行算法實(shí)踐同學(xué)在下面表1中選一個(gè)題目，（1）闡述基本原理（包括對算法改進(jìn)和優(yōu)化方法）；(2)根據(jù)KD60實(shí)驗(yàn)平臺(tái)設(shè)計(jì)實(shí)驗(yàn)方法和步驟（包括主要調(diào)試過程要求拷屏）。(3) 數(shù)據(jù)及結(jié)果分析：根據(jù)不同的實(shí)驗(yàn)內(nèi)容，記錄具體的實(shí)驗(yàn)數(shù)據(jù)或程序運(yùn)行結(jié)果（要求拷屏）。實(shí)驗(yàn)數(shù)據(jù)量較大時(shí)，最好制成表格形式。附上程序功能、模塊說明、完整源代碼，源代碼中盡量多帶注釋；(4)分析和總結(jié)：對程序與算法性能改進(jìn)結(jié)論，總結(jié)和體會(huì)。表1 并行算法實(shí)踐題目 序號(hào)題目名稱基本方法和內(nèi)容要求1LU分解的Open MP實(shí)現(xiàn)編寫LU分解的Open MP程序2KMP算法的Open MP實(shí)現(xiàn)編寫KMP算法的OpenM

3、P程序3高斯消元法解線性方程組的Open MP實(shí)現(xiàn)編寫高斯消元法解線性方程組的OpenMP程序4高斯消元法解線性方程組的MPI實(shí)現(xiàn)編寫高斯消元法解線性方程組的MPI程序5高斯-塞德爾迭代解線性方程組的MPI實(shí)現(xiàn)編寫高斯-塞德爾迭代解線性方程組的MPI程序6Cannon乘法的MPI實(shí)現(xiàn)編寫Cannon乘法的MPI程序7LU分解的MPI實(shí)現(xiàn)編寫LU分解的MPI程序8隨機(jī)串匹配算法的MPI實(shí)現(xiàn)編寫隨機(jī)串匹配算法的MPI程序9單源最短路徑Dijkstra 算法的MPI實(shí)現(xiàn)編寫單源最短路徑Dijkstra算法的MPI程序10快速排序算法的MPI實(shí)現(xiàn)編寫快速排序算法的MPI程序11KMP串匹配的MPI實(shí)現(xiàn)

4、編寫KMP串匹配算法的MPI程序一、 實(shí)驗(yàn)課程名稱：并行算法實(shí)踐二、 實(shí)驗(yàn)項(xiàng)目名稱：LU分解的Open MP實(shí)現(xiàn)三、 實(shí)驗(yàn)?zāi)康模豪斫舛嗪顺绦虻脑O(shè)計(jì)思想，學(xué)習(xí)使用OpenMP編寫并行程序。四、 必修或選修：選修五、 實(shí)驗(yàn)平臺(tái)：硬件平臺(tái)：龍芯3A教學(xué)儀器軟件平臺(tái)：Debian GNU/Linux 2.6.27無盤系統(tǒng)，GCC 4.3編譯環(huán)境六、 實(shí)驗(yàn)原理：（闡述基本原理，也包括對算法改進(jìn)和優(yōu)化方法）對于一個(gè)n階非奇異方陣A=aij，對A進(jìn)行LU分解是求一個(gè)主對角元素全為1的下三角方陣L=lij與上三角方陣U=uij，使A=LU。例如對于一個(gè)3×3的矩陣，就有設(shè)A的各階主子行列式皆非零，U

5、和L的元素可由下面的遞推式求出： aij(1)=aij aij(k+1)=aij(k)-likukj 在計(jì)算過程中，首先計(jì)算出U的第一行元素，然后算出L的第一列元素，修改相應(yīng)A的元素；再算出U的第二行，L的第二列，直至算出unn為止。若一次乘法和加法運(yùn)算或一次除法運(yùn)算時(shí)間為一個(gè)單位時(shí)間，則下述LU分解的串行算法時(shí)間復(fù)雜度為= O(n3)。單處理器上矩陣LU分解串行算法輸入：矩陣An×n輸出：下三角矩陣Ln×n,上三角矩陣 Un×nBegin(1)for k=1 to n do(1.1)for i=k+1 to n doai,k=ai,k/ak,kend for (

6、1.2)for i=k+1 to n dofor j=k+1 to n doai,j=ai,j-ai,k*ak,j end forend forend for(2)for i=1 to n do(2.1)for j=1 to n doif (j<i) then li,j=ai,jelse ui,j=ai,j end ifend for(2.2)li,i=1end forEndLU分解的OpenMP并行算法主要是用pragma omp for制導(dǎo)語句對非數(shù)據(jù)相關(guān)且非操作相關(guān)的for循環(huán)語句并行化。多核處理器上矩陣LU分解OpenMP并行算法Begin#pragma omp parallel

7、 shared(A) private(tid,i,j,k)(1)for k=1 to n do#pragma omp for(1.1)for i=k+1 to n doai,k=ai,k/ak,kend for #pragma omp for (1.2)for i=k+1 to n dofor j=k+1 to n doai,j=ai,j-ai,k*ak,j end forend for end for(2)for i=1 to n do(2.1)for j=1 to n doif (j<i) then li,j=ai,jelse ui,j=ai,j end ifend for(2.2)

8、li,i=1end forEnd七、 實(shí)驗(yàn)內(nèi)容及步驟:1.編寫程序源代碼：lu.c#include <stdio.h>#include <stdlib.h>#include <math.h>#include <sys/time.h>#include <omp.h>#define MaxN 1010#define infile "LU.in"#define outfile "LU.out"#define NUM_OF_THREADS 2FILE *fin,*fout; /fin為輸入文件 fout

9、為輸出文件double AMaxNMaxN; /A為原矩陣double LMaxNMaxN,UMaxNMaxN; /L和U 為分解后的矩陣int n; /n為矩陣行數(shù)int nthreads,tid;int createfile() /創(chuàng)建A矩陣數(shù)據(jù)文件 int i=0,j=0; n=1000; srand(unsigned)time(NULL); FILE *f; f=fopen(infile,"w"); fprintf(f,"%d ",n); for(i=0;i<n;i+) for(j=0;j<n;j+) fprintf(f,"

10、%d ",rand()%1000); fprintf(f,"%c",'n'); fclose(f); printf("Finished!n"); return 0;int init() /初始化，讀取A矩陣數(shù)據(jù)文件 int i,j; fscanf(fin,"%d",&n); for (i=0; i<n; i+) for (j=0; j<n; j+) fscanf(fin,"%lf",&Aij); omp_set_num_threads(NUM_OF_THREAD

11、S); /設(shè)置OpenMP線程數(shù)量 for (i=0; i<n; i+) for (j=0; j<n; j+) Lij=0; Uij=0; for (i=0; i<n; i+) Lii=1; return 0;int factorize() int i,j,k;#pragma omp parallel shared(A) private(tid,i,j,k) for (k=0; k<n; k+) #pragma omp for /for循環(huán)并行制導(dǎo)語句 for (i=k+1; i<n; i+) Aik=Aik/Akk;#pragma omp for /for循環(huán)并

12、行制導(dǎo)語句 for (i=k+1; i<n; i+) for (j=k+1; j<n; j+) Aij=Aij-Aik*Akj; for (i=0; i<n; i+) for (j=0; j<n; j+) if (i<=j) Uij=Aij; else Lij=Aij; return 0;int output() int i,j; /輸出L矩陣 fprintf(fout,"Matrix L:n"); for (i=0; i<n; i+) for (j=0; j<n; j+) fprintf(fout,"%.10lf%c&q

13、uot;,Lij,(j=n-1)?'n':' '); /輸出U矩陣 fprintf(fout,"Matrix U:n"); for (i=0; i<n; i+) for (j=0; j<n; j+) fprintf(fout,"%.10lf%c",Uij,(j=n-1)?'n':' '); return 0;int main() double ts,te; while(fin=fopen(infile,"r")=NULL) /如果檢測不到A矩陣數(shù)據(jù)文件，則調(diào)用

14、createfile()函數(shù)，以隨機(jī)數(shù)創(chuàng)建一個(gè) createfile(); fout=fopen(outfile,"w"); /初始化 init(); /矩陣分解 ts = omp_get_wtime(); factorize(); te = omp_get_wtime(); printf("time = %f sn", te - ts); /輸出LU分解所用時(shí)間 /輸出結(jié)果 output(); fclose(fin); fclose(fout); return 0; 2.下載并安裝SecureCRT（可在或自行上網(wǎng)搜索下載）3. 主機(jī)名192.168.

15、150.218，用戶名kd60，密碼kd604.進(jìn)入后，以ssh root192.168.60.80登陸龍芯實(shí)驗(yàn)平臺(tái)KD60，密碼kd60。5.編譯命令gcc lu.c o lu -fopenmp6.運(yùn)行命令./lu ,即可得到實(shí)驗(yàn)結(jié)果。八、 實(shí)驗(yàn)數(shù)據(jù)及結(jié)果：本實(shí)驗(yàn)對1000階矩陣進(jìn)行LU分解。當(dāng)把線程個(gè)數(shù)設(shè)置為4時(shí)，即#define NUM_OF_THREADS 4運(yùn)行時(shí)間為11.566771秒。當(dāng)把線程個(gè)數(shù)設(shè)置為2時(shí)，即#define NUM_OF_THREADS 2運(yùn)行時(shí)間為22.170146秒。當(dāng)把線程個(gè)數(shù)設(shè)置為1時(shí)，即#define NUM_OF_THREADS 1程序?qū)嶋H上變成串行程序，運(yùn)行時(shí)間為45.148058秒。當(dāng)把線程個(gè)數(shù)設(shè)置為8時(shí)，即#define NUM_OF_THREADS 8由于龍芯3A處理器只有4核，線程數(shù)量超過4時(shí)，實(shí)際上將不再完全是并行執(zhí)行，反而會(huì)帶來一定的線程切換開銷。運(yùn)行時(shí)間竟長達(dá)194.894202秒。根據(jù)以上實(shí)驗(yàn)數(shù)據(jù)，計(jì)算得加速比如下：線程數(shù)1248運(yùn)行時(shí)間（s）45.14805822.17014611.566771194.894202加速比1x2.03x3.90x0.23x九、 實(shí)驗(yàn)結(jié)論分析及總結(jié)：1.實(shí)驗(yàn)結(jié)論分析：由于龍芯3A實(shí)驗(yàn)平臺(tái)采用四核的龍芯3A處理器，因此Op