多核研究性课题实验报告

辽宁师范大学计算机与信息技术学院综合性实验报告课程名称：多核并行程序设计实验题目：基于主成分分析的并行程序设计学生姓名：孙蕾专业：计算机科学与技术学号：20101118050005实验日期：2012年11月25日实验成绩：实验目的通过对主成分分析法进行研究，了解主成分分析在生产生活中的重要应用性。在此基础上找到算法，给出计算对称矩阵特征值的串行算法，并在此基础上利用多核程序设计将其并行化，以优化运行速度。通过本实验了解并行程序设计原理并达到基本能应用的水平。实验内容对主成分分析法进行学习，明白其原理以及在现实生活中的应用方面和实际意义。按照对主成分分析的理解找到计算特征值的算法并完成串行程序。在串行程序的基础上应用多核程序设计的原理将程序并行化，分别对串行程序和并行程序计算运行时间，计算加速比，加深多核程序设计的理解。总结研究中的问题以及克服方法，心得和体会。实验过程（含结果抓图）串行程序代码及结果抓图#include<iostream.h>#include<stdlib.h>#include<math.h>#include<iomanip.h>//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//classMatrix定义矩阵类constintMax_xy=20; //矩阵的最大维数classMatrix{ private: doubledata[Max_xy][Max_xy]; unsignedx,y; //x,y;public: Matrix(); //默认构造函数 Matrix(constMatrix&source); //拷贝构造函数 voidcreat(); //输入矩阵 voidinit(); voidtranspose(); //矩阵转置 voidshow(); //输入此矩阵 doublemode()const; //求一维矩阵的长度 voidcheck_shiduichen(); //检查是否为是对称矩阵 voidcreat_unit(unsignedi); //生成i行单位矩阵 voidset_x(unsignedxx); //设置行数 voidset_y(unsignedyy); //设置列数 unsignedget_x(); //得到行数 unsignedget_y(); //得到列数 voidshucheng(doublechangshu); //数乘运算 voidsetdata(unsignedi,unsignedj,doublesource); //定位输入数据 doublegetdata(unsignedi,unsignedj); //定位得到数据 voidsturm(); //求特征值 unsignedsturm_s(doublem); //计算sturm系列的同好数 Matrixoperator=(constMatrix&right); friendMatrix&operator+(constMatrix&left,constMatrix&right); //重载+号 friendMatrix&operator-(constMatrix&left,constMatrix&right); //重载-号 friendMatrix&operator*(constMatrix&left,constMatrix&right); //重载乘号 friendostream&operator<<(ostream&os,constMatrix&source); //重载输出 friendvoidHouseholder(Matrix&source); //用Householde矩阵将实对称矩阵化为三对角矩阵};Matrixtemp_Matrix; //全局变量Matrix//===================================================================//--------------------默认构造函数Matrix::Matrix() { init();} //----------------------------拷贝构造函数Matrix::Matrix(constMatrix&source) { init(); x=source.x; y=source.y; for(unsignedi=0;i<x;i++) for(unsignedj=0;j<y;j++) data[i][j]=source.data[i][j];}//------------------------------------------初始化矩阵元素voidMatrix::init(){ x=y=0; for(unsignedi=0;i<Max_xy;i++) for(unsignedj=0;j<Max_xy;j++) data[i][j]=0; }//------------------------------矩阵转置voidMatrix::transpose() { doubletemp;intt; for(unsignedi=0;i<Max_xy;i++) for(unsignedj=0;j<=i;j++) { temp=data[i][j]; data[i][j]=data[j][i]; data[j][i]=temp; } t=x; x=y; y=t;}//--------------------------------------求一维矩阵的长度 doubleMatrix::mode() const { doubles=0; unsignedi,j; if(x==1) for(i=0,j=0;j<y;j++) s+=data[i][j]*data[i][j]; elseif(y==1) for(i=0,j=0;i<x;i++) s+=data[i][j]*data[i][j]; else { cout<<"\n不是一维的!"; exit(0); } s=sqrt(s); return(s);}//----------------------------------------重载=号MatrixMatrix::operator=(constMatrix&source){ x=source.x; y=source.y; for(unsignedi=0;i<x;i++) for(unsignedj=0;j<y;j++) data[i][j]=source.data[i][j]; return*this; }//-------------------------------------------重载+号Matrix&operator+(constMatrix&left,constMatrix&right){ if(left.x!=right.x||left.y!=right.y) { cout<<"\n维数不相等,不能相加!"; exit(0); } for(unsignedi=0;i<left.x;i++) for(unsignedj=0;j<left.y;j++) temp_Matrix.data[i][j]=right.data[i][j]+left.data[i][j]; temp_Matrix.x=right.x; temp_Matrix.y=right.y; returntemp_Matrix;}//---------------------------------------------重载+号Matrix&operator-(constMatrix&left,constMatrix&right) { if(left.x!=right.x||left.y!=right.y) { cout<<"\n维数不相等,不能相减!"; exit(0); } for(unsignedi=0;i<left.x;i++) for(unsignedj=0;j<left.y;j++) temp_Matrix.data[i][j]=left.data[i][j]-right.data[i][j]; temp_Matrix.x=right.x; temp_Matrix.y=right.y; returntemp_Matrix;}//----------------------------------------重载乘号Matrix&operator*(constMatrix&left,constMatrix&right) { if(left.y!=right.x) { cout<<"\n两个矩阵相乘错误."; exit(0); } temp_Matrix.init(); unsignedi,j,k; for(i=0;i<left.x;i++) for(j=0;j<right.y;j++) for(k=0;k<left.y;k++) temp_Matrix.data[i][j]+=left.data[i][k]*right.data[k][j]; temp_Matrix.x=left.x; temp_Matrix.y=right.y; returntemp_Matrix;}//-------------------------------------------输入矩阵voidMatrix::creat() { cout<<"输如行列式:"; cout<<"\n行数:"; cin>>x; cout<<"列数:"; cin>>y; for(unsignedi=0;i<x;i++) { cout<<"输入第"<<i+1<<"行:"; for(unsignedj=0;j<y;j++) cin>>data[i][j]; }}//----------------------------------------------输出矩阵voidMatrix::show(){ unsignedi,j; cout<<"\n\n矩阵表示如下:"; for(i=0;i<x;i++) { cout<<endl; for(j=0;j<y;j++) cout<<setw(7)<<setiosflags(ios::left)<<data[i][j]; }}//----------------------------------用Householder矩阵化为实对称矩阵voidHouseholder(Matrix&source){ unsignedi,lenth,k,m,n,flag; doubletemp_lie_x[Max_xy],temp_lie_y[Max_xy],temp[Max_xy]; doubles; for(i=0;i<source.x-2;i++) { for(k=0;k<Max_xy;k++) { //初始化为0 temp_lie_x[k]=0; temp_lie_y[k]=0; temp[k]=0; } for(lenth=0;lenth+i+1<source.x;lenth++) //提取第data[i+1][i]到data[x-1][i]的数据存到temp_lie[Max_xy]; temp_lie_x[lenth]=source.data[lenth+i+1][i]; for(k=0,s=0;k<lenth;k++) //j为临时变量的个数. s+=temp_lie_x[k]*temp_lie_x[k]; s=sqrt(s); temp_lie_y[0]=-s; for(k=1;k<lenth;k++) temp_lie_y[k]=0; for(k=0;k<lenth;k++) temp[k]=temp_lie_x[k]-temp_lie_y[k]; for(k=0,flag=0;k<lenth;k++) //假如以上两个向量相等则退出,则跳出以进行下一次变换 if(temp[k]!=0) { flag=1; break; } if(flag==0) continue; Matrixpart_h,I,x_y; //定义Matrix变量 I.creat_unit(lenth); x_y.x=lenth,x_y.y=1; //对x_y赋值 for(k=0;k<lenth;k++) x_y.data[k][0]=temp[k]; //求x_y的转置 Matrixzhuanzhi_x_y(x_y); //拷贝构造函数 zhuanzhi_x_y.transpose(); s=2.0/(x_y.mode()*x_y.mode()); x_y.shucheng(s); temp_Matrix=x_y*zhuanzhi_x_y; part_h=I-x_y*zhuanzhi_x_y; MatrixH; H.creat_unit(source.x); for(m=i+1;m<source.x;m++) for(n=i+1;n<source.y;n++) H.data[m][n]=part_h.data[m-i-1][n-i-1]; //得到最后的Householder矩阵 source=source*H; source=H*source; } for(i=0;i<source.x;i++) for(k=0;k<source.y;k++) if(fabs(source.data[i][k])<1e-13) source.data[i][k]=0;}//------------------------------------检查是否为实对称矩阵voidMatrix::check_shiduichen(){ if(x!=y) { cout<<"\n\n不是是对称矩阵(行列不相等)\n\n"; exit(0); } for(unsignedi=0;i<x;i++) for(unsignedj=0;j<y;j++) { if(data[i][j]!=data[j][i]) { cout<<"\n\n不是实对称矩阵!(不对称!)\n\n"; exit(0); } }}ostream&operator<<(ostream&os,constMatrix&source){ unsignedi,j; for(i=0;i<source.x;i++) { os<<"\n"; for(j=0;j<source.y;j++) os<<setw(10)<<setiosflags(ios::left)<<source.data[i][j]<<"\t"; } os<<endl; returnos;}voidMatrix::set_x(unsignedxx) //设置行数{ x=xx;}voidMatrix::set_y(unsignedyy) //设置列数{ y=yy;}unsignedMatrix::get_x() //得到行数{ returnx;}unsignedMatrix::get_y() //得到列数{ returny;}doubleMatrix::getdata(unsignedi,unsignedj) //定位得到数据{ returndata[i][j];}voidMatrix::setdata(unsignedi,unsignedj,doublesource){ data[i][j]=source; if(x<i) x=i; if(y<j) y=j;}voidMatrix::creat_unit(unsignedlenth) //生成i行单位矩阵{ init(); x=y=lenth; for(unsignedi=0;i<lenth;i++) data[i][i]=1;}voidMatrix::shucheng(doublechangshu) //数乘运算{ unsignedi,j; for(i=0;i<x;i++) for(j=0;j<y;j++) data[i][j]*=changshu;}voidMatrix::sturm(){ doubles,r,maxhang,a,b;unsignedi,j,m; for(i=0,maxhang=0;i<x;i++) { for(s=0,j=0;j<y;j++) s+=fabs(data[i][j]); if(s>maxhang) maxhang=s; } a=-maxhang; b=maxhang; m=sturm_s(a)-sturm_s(b); for(i=1;i<=m;i++) { a=-maxhang; b=maxhang; do { r=0.5*(a+b); if(sturm_s(r)>=i) a=r; else b=r; } while(fabs(a-b)>1e-11); cout<<"\n特征值"<<i<<":"<<setiosflags(ios::left)<<setw(10)<<setprecision(10) <<setiosflags(ios::fixed)<<0.5*(a+b); }}unsignedMatrix::sturm_s(doubler){ doublep[Max_xy+1]; inttemp[Max_xy+1]; unsignedm,i; p[0]=1; p[1]=data[0][0]-r; for(i=2;i<=x;i++) p[i]=(data[i-1][i-1]-r)*p[i-1]-data[i-2][i-1]*data[i-2][i-1]*p[i-2]; temp[0]=1; for(i=1;i<=x;i++) if(p[i]>1e-14) temp[i]=1; elseif(p[i]<-1e-14) temp[i]=-1; else temp[i]=temp[i-1]; for(i=1,m=0;i<=x;i++) if(temp[i]+temp[i-1]!=0) m++; returnm;}int_tmain(intargc,_TCHAR*argv[]){ doublebegin,end,time; begin=(double)clock()/(double)CLK_TCK; Matrixa; a.creat(); cout<<"输º?入¨?的Ì?矩?阵¨®为a:"; cout<<a; a.check_shiduichen(); Householder(a); cout<<"用Householder化¡为实对称矩阵为a:"; cout<<a; a.sturm(); cout<<endl; end=(double)clock()/(double)CLK_TCK;time=end-begin; cout<<"时间是："; cout<<time; return0;}串行运行结果：2.并行程序代码及结果抓图//bingxing.cpp:定义控制台应用程序的入口点////c.cpp:定义控制台应用程序的入口点//#include"stdafx.h"#include<iostream>#include<stdlib.h>#include<math.h>#include<iomanip>#include<omp.h>usingnamespacestd;//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//classMatrix定¡§义°?矩?阵¨®类¤¨¤constintMax_xy=20; //矩?阵¨®的Ì?最Á?大䨮维?数ºyclassMatrix{ private: doubledata[Max_xy][Max_xy]; unsignedx,y; //x,y;public: Matrix(); //默?认¨?构1造¨¬函¡¥数ºy Matrix(constMatrix&source); //拷?贝À¡ä构1造¨¬函¡¥数ºy voidcreat(); //输º?入¨?矩?阵¨® voidinit(); voidtranspose(); //矩?阵¨®转Áa置? voidshow(); //输º?入¨?此ä?矩?阵¨® doublemode()const; //求¨®一°?维?矩?阵¨®的Ì?长¡è度¨¨ voidcheck_shiduichen(); //检¨¬查¨¦是º?否¤?为a是º?对?称?矩?阵¨® voidcreat_unit(unsignedi); //生¦¨²成¨¦i行D单Ì£¤位?矩?阵¨® voidset_x(unsignedxx); //设¦¨¨置?行D数ºy voidset_y(unsignedyy); //设¦¨¨置?列¢D数ºy unsignedget_x(); //得Ì?到Ì?行D数ºy unsignedget_y(); //得Ì?到Ì?列¢D数ºy voidshucheng(doublechangshu); //数ºy乘?运?算? voidsetdata(unsignedi,unsignedj,doublesource); //定¡§位?输º?入¨?数ºy据Y doublegetdata(unsignedi,unsignedj); //定¡§位?得Ì?到Ì?数ºy据Y voidsturm(); //求¨®特¬?征¡Â值¦Ì unsignedsturm_s(doublem); //计?算?sturm系¦Ì列¢D的Ì?同ª?好?数ºy Matrixoperator=(constMatrix&right); friendMatrix&operator+(constMatrix&left,constMatrix&right); //重?载?+号? friendMatrix&operator-(constMatrix&left,constMatrix&right); //重?载?-号? friendMatrix&operator*(constMatrix&left,constMatrix&right); //重?载?乘?号? friendostream&operator<<(ostream&os,constMatrix&source); //重?载?输º?出? friendvoidHouseholder(Matrix&source); //用®?Householde矩?阵¨®将?实º¦Ì对?称?矩?阵¨®化¡¥为a三¨y对?角?矩?阵¨®};Matrixtemp_Matrix; //全¨?局?变À?量¢?Matrix//===================================================================//--------------------默?认¨?构1造¨¬函¡¥数ºyMatrix::Matrix() { init();} //----------------------------拷?贝À¡ä构1造¨¬函¡¥数ºyMatrix::Matrix(constMatrix&source) { init(); x=source.x; y=source.y; for(unsignedi=0;i<x;i++) for(unsignedj=0;j<y;j++) data[i][j]=source.data[i][j];}//------------------------------------------初?始º?化¡¥矩?阵¨®元a素?voidMatrix::init(){ x=y=0; for(unsignedi=0;i<Max_xy;i++) for(unsignedj=0;j<Max_xy;j++) data[i][j]=0; }//------------------------------矩?阵¨®转Áa置?voidMatrix::transpose() { doubletemp;intt; for(unsignedi=0;i<Max_xy;i++) for(unsignedj=0;j<=i;j++) { temp=data[i][j]; data[i][j]=data[j][i]; data[j][i]=temp; } t=x; x=y; y=t;}//--------------------------------------求¨®一°?维?矩?阵¨®的Ì?长¡è度¨¨ doubleMatrix::mode() const { doubles=0; unsignedi,j; if(x==1) for(i=0,j=0;j<y;j++) s+=data[i][j]*data[i][j]; elseif(y==1) for(i=0,j=0;i<x;i++) s+=data[i][j]*data[i][j]; else { cout<<"\n不?是º?一°?维?的Ì?!"; exit(0); } s=sqrt(s); return(s);}//----------------------------------------重?载?=号?MatrixMatrix::operator=(constMatrix&source){ x=source.x; y=source.y; for(unsignedi=0;i<x;i++) for(unsignedj=0;j<y;j++) data[i][j]=source.data[i][j]; return*this; }//-------------------------------------------重?载?+号?Matrix&operator+(constMatrix&left,constMatrix&right){intj; if(left.x!=right.x||left.y!=right.y) { cout<<"\n维?数ºy不?相¨¤等̨¨,不?能¨¹相¨¤加¨®!"; exit(0); } for(unsignedi=0;i<left.x;i++) #pragmaompparallelforprivate(j) for(j=0;j<left.y;j++) temp_Matrix.data[i][j]=right.data[i][j]+left.data[i][j]; temp_Matrix.x=right.x; temp_Matrix.y=right.y; returntemp_Matrix;}//---------------------------------------------重?载?-号?Matrix&operator-(constMatrix&left,constMatrix&right) { if(left.x!=right.x||left.y!=right.y) { cout<<"\n维?数ºy不?相¨¤等̨¨,不?能¨¹相¨¤减?!"; exit(0); } for(unsignedi=0;i<left.x;i++) for(unsignedj=0;j<left.y;j++) temp_Matrix.data[i][j]=left.data[i][j]-right.data[i][j]; temp_Matrix.x=right.x; temp_Matrix.y=right.y; returntemp_Matrix;}//----------------------------------------重?载?乘?号?Matrix&operator*(constMatrix&left,constMatrix&right) { if(left.y!=right.x) { cout<<"\n两¢?个?矩?阵¨®相¨¤乘?错䨪误¨®."; exit(0); } temp_Matrix.init(); unsignedi,j,k; for(i=0;i<left.x;i++) for(j=0;j<right.y;j++) for(k=0;k<left.y;k++) temp_Matrix.data[i][j]+=left.data[i][k]*right.data[k][j]; temp_Matrix.x=left.x; temp_Matrix.y=right.y; returntemp_Matrix;}//-------------------------------------------输º?入¨?矩?阵¨®voidMatrix::creat() { cout<<"输º?如¨?行D列¢D式º?:"; cout<<"\n行D数ºy:"; cin>>x; cout<<"列¢D数ºy:"; cin>>y; for(unsignedi=0;i<x;i++) { cout<<"输º?入¨?第̨²"<<i+1<<"行D:"; for(unsignedj=0;j<y;j++) cin>>data[i][j]; }}//----------------------------------------------输º?出?矩?阵¨®voidMatrix::show(){ unsignedi,j; cout<<"\n\n矩?阵¨®表À¨ª示º?如¨?下?:"; for(i=0;i<x;i++) { cout<<endl; for(j=0;j<y;j++) cout<<setw(7)<<setiosflags(ios::left)<<data[i][j]; }}//----------------------------------用®?Householder矩?阵¨®化¡¥为a实º¦Ì对?称?矩?阵¨®voidHouseholder(Matrix&source){ for(i=0;i<source.x-2;i++) { #pragmaompparallelforprivate(k) for(k=0;k<Max_xy;k++) { //初?始º?化¡¥为a0 temp_lie_x[k]=0; temp_lie_y[k]=0; temp[k]=0; } for(lenth=0;lenth+i+1<source.x;lenth++) //提¬¨¢取¨?第̨²data[i+1][i]到Ì?data[x-1][i]的Ì?数ºy据Y存ä?到Ì?temp_lie[Max_xy]; temp_lie_x[lenth]=source.data[lenth+i+1][i]; for(k=0,s=0;k<lenth;k++) //j为a临¢¨´时º¡À变À?量¢?的Ì?个?数ºy. s+=temp_lie_x[k]*temp_lie_x[k]; s=sqrt(s); temp_lie_y[0]=-s; for(k=1;k<lenth;k++) temp_lie_y[k]=0; for(k=0;k<lenth;k++) temp[k]=temp_lie_x[k]-temp_lie_y[k]; for(k=0,flag=0;k<lenth;k++) //假¨´如¨?以°?上¦?两¢?个?向¨°量¢?相¨¤等̨¨则¨°退ª?出?,则¨°跳¬?出?以°?进?行D下?一°?次ä?变À?换? if(temp[k]!=0) { flag=1; break; } if(flag==0) continue; Matrixpart_h,I,x_y; //定¡§义°?Matrix变À?量¢? I.creat_unit(lenth); x_y.x=lenth,x_y.y=1; //对?x_y赋3值¦Ì for(k=0;k<lenth;k++) x_y.data[k][0]=temp[k]; //求¨®x_y的Ì?转Áa置? Matrixzhuanzhi_x_y(x_y); //拷?贝À¡ä构1造¨¬函¡¥数ºy zhuanzhi_x_y.transpose(); s=2.0/(x_y.mode()*x_y.mode()); x_y.shucheng(s); temp_Matrix=x_y*zhuanzhi_x_y; part_h=I-x_y*zhuanzhi_x_y; MatrixH; H.creat_unit(source.x); for(m=i+1;m<source.x;m++) for(n=i+1;n<source.y;n++) H.data[m][n]=part_h.data[m-i-1][n-i-1]; //得Ì?到Ì?最Á?后¨®的Ì?Householder矩?阵¨® source=source*H; source=H*source; } for(i=0;i<source.x;i++) for(k=0;k<source.y;k++) if(fabs(source.data[i][k])<1e-13) source.data[i][k]=0;}//------------------------------------检¨¬查¨¦是º?否¤?为a实º¦Ì对?称?矩?阵¨®voidMatrix::check_shiduichen(){ if(x!=y) { cout<<"\n\n不?是º?是º?对?称?矩?阵¨®(行D列¢D不?相¨¤等̨¨)\n\n"; exit(0); } for(unsignedi=0;i<x;i++) for(unsignedj=0;j<y;j++) { if(data[i][j]!=data[j][i]) { cout<<"\n\n不?是º?实º¦Ì对?称?矩?阵¨®!(不?对?称?!)\n\n"; exit(0); } }}ostream&operator<<(ostream&os,constMatrix&source){ unsignedi,j; for(i=0;i<source.x;i++) { os<<"\n"; for(j=0;j<source.y;j++) os<<setw(10)<<setiosflags(ios::left)<<source.data[i][j]<<"\t"; } os<<endl; returnos;}voidMatrix::set_x(unsignedxx) //设¦¨¨置?行D数ºy{ x=xx;}voidMatrix::set_y(unsignedyy) //设¦¨¨置?列¢D数ºy{ y=yy;}unsignedMatrix::get_x() //得Ì?到Ì?行D数ºy{ returnx;}unsignedMatrix::get_y() //得Ì?到Ì?列¢D数ºy{ returny;}doubleMatrix::getdata(unsignedi,unsignedj) //定¡§位?得Ì?到Ì?数ºy据Y{ returndata[i][j];}voidMatrix::setdata(unsignedi,unsignedj,doublesource){ data[i][j]=source; if(x<i) x=i; if(y<j) y=j;}voidMatrix::creat_unit(unsignedlenth) //生¦¨²成¨¦i行D单Ì£¤位?矩?阵¨®{ init(); x=y=lenth; for(unsignedi=0;i<lenth;i++) data[i][i]=1;}voidMatrix::shucheng(doublechangshu) //数ºy乘?运?算?加¨®入¨?并¡é行D语®?句?{inti,j; omp_set_num_threads(3); #pragmaompparallelfor for(i=0;i<x;i++) for(j=0;j<y;j++) data[i][j]*=changshu;}voidMatrix::sturm(){ doubles,r,maxhang,a,b;unsignedi,j,m; for(i=0,maxhang=0;i