课程论文_LU分解的OpenMP实现

1、并行算法实践要求学生在KD60实验平台上设计并行算法并实现。实验平台由一块处理板、一块监控板和一块背板等组成。处理板逻辑结构如图1所示。处理板承载4个处理单元，每个处理单元包括一个龙芯3号四核CPU、2GB DDR2内存、RTL8110千兆以太网卡芯片、BIOS Flash、串口收发芯片以及电源变换电路等。四个龙芯3号处理器通过HT总线实现互连。监控电路检测4个处理单元的状态，并实现对其控制。 图1 处理板逻辑结构实验平台的系统软件以开源软件为主（见图2），具有兼容性强、易维护、易升级、易使用等特点。处理单元操作系统为Debian GNU/Linux无盘系统，采用稳定高效的2.6.27内核。图

2、2 软件系统结构要求选修并行算法实践同学在下面表1中选一个题目，（1）阐述基本原理（包括对算法改进和优化方法）；(2)根据KD60实验平台设计实验方法和步骤（包括主要调试过程要求拷屏）。(3) 数据及结果分析：根据不同的实验内容，记录具体的实验数据或程序运行结果（要求拷屏）。实验数据量较大时，最好制成表格形式。附上程序功能、模块说明、完整源代码，源代码中尽量多带注释；(4)分析和总结：对程序与算法性能改进结论，总结和体会。表1 并行算法实践题目 序号题目名称基本方法和内容要求1LU分解的Open MP实现编写LU分解的Open MP程序2KMP算法的Open MP实现编写KMP算法的OpenM

3、P程序3高斯消元法解线性方程组的Open MP实现编写高斯消元法解线性方程组的OpenMP程序4高斯消元法解线性方程组的MPI实现编写高斯消元法解线性方程组的MPI程序5高斯-塞德尔迭代解线性方程组的MPI实现编写高斯-塞德尔迭代解线性方程组的MPI程序6Cannon乘法的MPI实现编写Cannon乘法的MPI程序7LU分解的MPI实现编写LU分解的MPI程序8随机串匹配算法的MPI实现编写随机串匹配算法的MPI程序9单源最短路径Dijkstra 算法的MPI实现编写单源最短路径Dijkstra算法的MPI程序10快速排序算法的MPI实现编写快速排序算法的MPI程序11KMP串匹配的MPI实现

4、编写KMP串匹配算法的MPI程序一、 实验课程名称：并行算法实践二、 实验项目名称：LU分解的Open MP实现三、 实验目的：理解多核程序的设计思想，学习使用OpenMP编写并行程序。四、 必修或选修：选修五、 实验平台：硬件平台：龙芯3A教学仪器软件平台：Debian GNU/Linux 2.6.27无盘系统，GCC 4.3编译环境六、 实验原理：（阐述基本原理，也包括对算法改进和优化方法）对于一个n阶非奇异方阵A=aij，对A进行LU分解是求一个主对角元素全为1的下三角方阵L=lij与上三角方阵U=uij，使A=LU。例如对于一个3×3的矩阵，就有设A的各阶主子行列式皆非零，U

5、和L的元素可由下面的递推式求出： aij(1)=aij aij(k+1)=aij(k)-likukj 在计算过程中，首先计算出U的第一行元素，然后算出L的第一列元素，修改相应A的元素；再算出U的第二行，L的第二列，直至算出unn为止。若一次乘法和加法运算或一次除法运算时间为一个单位时间，则下述LU分解的串行算法时间复杂度为= 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制导语句对非数据相关且非操作相关的for循环语句并行化。多核处理器上矩阵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七、 实验内容及步骤: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为矩阵行数int nthreads,tid;int createfile() /创建A矩阵数据文件 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矩阵数据文件 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); /设置OpenMP线程数量 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循环并行制导语句 for (i=k+1; i<n; i+) Aik=Aik/Akk;#pragma omp for /for循环并

12、行制导语句 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矩阵数据文件，则调用

14、createfile()函数，以随机数创建一个 createfile(); fout=fopen(outfile,"w"); /初始化 init(); /矩阵分解 ts = omp_get_wtime(); factorize(); te = omp_get_wtime(); printf("time = %f sn", te - ts); /输出LU分解所用时间 /输出结果 output(); fclose(fin); fclose(fout); return 0; 2.下载并安装SecureCRT（可在或自行上网搜索下载）3. 主机名192.168.

15、150.218，用户名kd60，密码kd604.进入后，以ssh root192.168.60.80登陆龙芯实验平台KD60，密码kd60。5.编译命令gcc lu.c o lu -fopenmp6.运行命令./lu ,即可得到实验结果。八、 实验数据及结果：本实验对1000阶矩阵进行LU分解。当把线程个数设置为4时，即#define NUM_OF_THREADS 4运行时间为11.566771秒。当把线程个数设置为2时，即#define NUM_OF_THREADS 2运行时间为22.170146秒。当把线程个数设置为1时，即#define NUM_OF_THREADS 1程序实际上变成串行程序，运行时间为45.148058秒。当把线程个数设置为8时，即#define NUM_OF_THREADS 8由于龙芯3A处理器只有4核，线程数量超过4时，实际上将不再完全是并行执行，反而会带来一定的线程切换开销。运行时间竟长达194.894202秒。根据以上实验数据，计算得加速比如下：线程数1248运行时间（s）45.14805822.17014611.566771194.894202加速比1x2.03x3.90x0.23x九、 实验结论分析及总结：1.实验结论分析：由于龙芯3A实验平台采用四核的龙芯3A处理器，因此Op