多核研究性課題實驗報告

遼寧師范大學(xué)計算機與信息技術(shù)學(xué)院綜合性實驗報告課程名稱：多核并行程序設(shè)計實驗題目：基于主成分分析的并行程序設(shè)計學(xué)生姓名：孫蕾專業(yè)：計算機科學(xué)與技術(shù)學(xué)號：20101118050005實驗日期：2012年11月25日實驗成績：實驗?zāi)康耐ㄟ^對主成分分析法進行研究，了解主成分分析在生產(chǎn)生活中的重要應(yīng)用性。在此基礎(chǔ)上找到算法，給出計算對稱矩陣特征值的串行算法，并在此基礎(chǔ)上利用多核程序設(shè)計將其并行化，以優(yōu)化運行速度。通過本實驗了解并行程序設(shè)計原理并達到基本能應(yīng)用的水平。實驗內(nèi)容對主成分分析法進行學(xué)習(xí)，明白其原理以及在現(xiàn)實生活中的應(yīng)用方面和實際意義。按照對主成分分析的理解找到計算特征值的算法并完成串行程序。在串行程序的基礎(chǔ)上應(yīng)用多核程序設(shè)計的原理將程序并行化，分別對串行程序和并行程序計算運行時間，計算加速比，加深多核程序設(shè)計的理解?？偨Y(jié)研究中的問題以及克服方法，心得和體會。實驗過程（含結(jié)果抓圖）串行程序代碼及結(jié)果抓圖#include<iostream.h>#include<stdlib.h>#include<math.h>#include<iomanip.h>//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//classMatrix定義矩陣類constintMax_xy=20; //矩陣的最大維數(shù)classMatrix{ private: doubledata[Max_xy][Max_xy]; unsignedx,y; //x,y;public: Matrix(); //默認(rèn)構(gòu)造函數(shù) Matrix(constMatrix&source); //拷貝構(gòu)造函數(shù) voidcreat(); //輸入矩陣 voidinit(); voidtranspose(); //矩陣轉(zhuǎn)置 voidshow(); //輸入此矩陣 doublemode()const; //求一維矩陣的長度 voidcheck_shiduichen(); //檢查是否為是對稱矩陣 voidcreat_unit(unsignedi); //生成i行單位矩陣 voidset_x(unsignedxx); //設(shè)置行數(shù) voidset_y(unsignedyy); //設(shè)置列數(shù) unsignedget_x(); //得到行數(shù) unsignedget_y(); //得到列數(shù) voidshucheng(doublechangshu); //數(shù)乘運算 voidsetdata(unsignedi,unsignedj,doublesource); //定位輸入數(shù)據(jù) doublegetdata(unsignedi,unsignedj); //定位得到數(shù)據(jù) voidsturm(); //求特征值 unsignedsturm_s(doublem); //計算sturm系列的同好數(shù) 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//===================================================================//--------------------默認(rèn)構(gòu)造函數(shù)Matrix::Matrix() { init();} //----------------------------拷貝構(gòu)造函數(shù)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; }//------------------------------矩陣轉(zhuǎn)置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維數(shù)不相等,不能相加!"; 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維數(shù)不相等,不能相減!"; 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行數(shù):"; cin>>x; cout<<"列數(shù):"; 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]的數(shù)據(jù)存到temp_lie[Max_xy]; temp_lie_x[lenth]=source.data[lenth+i+1][i]; for(k=0,s=0;k<lenth;k++) //j為臨時變量的個數(shù). 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的轉(zhuǎn)置 Matrixzhuanzhi_x_y(x_y); //拷貝構(gòu)造函數(shù) 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) //設(shè)置行數(shù){ x=xx;}voidMatrix::set_y(unsignedyy) //設(shè)置列數(shù){ y=yy;}unsignedMatrix::get_x() //得到行數(shù){ returnx;}unsignedMatrix::get_y() //得到列數(shù){ returny;}doubleMatrix::getdata(unsignedi,unsignedj) //定位得到數(shù)據(jù){ 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) //數(shù)乘運算{ 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<<"輸o?入¨?的ì?矩?陣¨?為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;}串行運行結(jié)果：2.并行程序代碼及結(jié)果抓圖//bingxing.cpp:定義控制臺應(yīng)用程序的入口點////c.cpp:定義控制臺應(yīng)用程序的入口點//#include"stdafx.h"#include<iostream>#include<stdlib.h>#include<math.h>#include<iomanip>#include<omp.h>usingnamespacestd;//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//classMatrix定?§義°?矩?陣¨?類¤¨¤constintMax_xy=20; //矩?陣¨?的ì?最á?大?¨?維?數(shù)oyclassMatrix{ private: doubledata[Max_xy][Max_xy]; unsignedx,y; //x,y;public: Matrix(); //默?認(rèn)¨?構(gòu)1造¨?函?￥數(shù)oy Matrix(constMatrix&source); //拷?貝à??構(gòu)1造¨?函?￥數(shù)oy voidcreat(); //輸o?入¨?矩?陣¨? voidinit(); voidtranspose(); //矩?陣¨?轉(zhuǎn)áa置? voidshow(); //輸o?入¨?此??矩?陣¨? doublemode()const; //求¨?一°?維?矩?陣¨?的ì?長?è度¨¨ voidcheck_shiduichen(); //檢¨?查¨|是o?否¤?為a是o?對?稱?矩?陣¨? voidcreat_unit(unsignedi); //生|¨2成¨|i行D單ì￡¤位?矩?陣¨? voidset_x(unsignedxx); //設(shè)|¨¨置?行D數(shù)oy voidset_y(unsignedyy); //設(shè)|¨¨置?列￠D數(shù)oy unsignedget_x(); //得ì?到ì?行D數(shù)oy unsignedget_y(); //得ì?到ì?列￠D數(shù)oy voidshucheng(doublechangshu); //數(shù)oy乘?運?算? voidsetdata(unsignedi,unsignedj,doublesource); //定?§位?輸o?入¨?數(shù)oy據(jù)Y doublegetdata(unsignedi,unsignedj); //定?§位?得ì?到ì?數(shù)oy據(jù)Y voidsturm(); //求¨?特??征??值|ì unsignedsturm_s(doublem); //計?算?sturm系|ì列￠D的ì?同a?好?數(shù)oy 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); //重?載?輸o?出? friendvoidHouseholder(Matrix&source); //用??Householde矩?陣¨?將?實o|ì對?稱?矩?陣¨?化?￥為a三¨y對?角?矩?陣¨?};Matrixtemp_Matrix; //全¨?局?變à?量￠?Matrix//===================================================================//--------------------默?認(rèn)¨?構(gòu)1造¨?函?￥數(shù)oyMatrix::Matrix() { init();} //----------------------------拷?貝à??構(gòu)1造¨?函?￥數(shù)oyMatrix::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];}//------------------------------------------初?始o(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; }//------------------------------矩?陣¨?轉(zhuǎn)á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不?是o?一°?維?的ì?!"; 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維?數(shù)oy不?相¨¤等쨨,不?能¨1相¨¤加¨?!"; 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維?數(shù)oy不?相¨¤等쨨,不?能¨1相¨¤減?!"; 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兩￠?個?矩?陣¨?相¨¤乘?錯?¨a誤¨?."; 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;}//-------------------------------------------輸o?入¨?矩?陣¨?voidMatrix::creat() { cout<<"輸o?如¨?行D列￠D式o?:"; cout<<"\n行D數(shù)oy:"; cin>>x; cout<<"列￠D數(shù)oy:"; cin>>y; for(unsignedi=0;i<x;i++) { cout<<"輸o?入¨?第ì¨2"<<i+1<<"行D:"; for(unsignedj=0;j<y;j++) cin>>data[i][j]; }}//----------------------------------------------輸o?出?矩?陣¨?voidMatrix::show(){ unsignedi,j; cout<<"\n\n矩?陣¨?表à¨a示o?如¨?下?:"; 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實o|ì對?稱?矩?陣¨?voidHouseholder(Matrix&source){ for(i=0;i<source.x-2;i++) { #pragmaompparallelforprivate(k) for(k=0;k<Max_xy;k++) { //初?始o(jì)?化?￥為a0 temp_lie_x[k]=0; temp_lie_y[k]=0; temp[k]=0; } for(lenth=0;lenth+i+1<source.x;lenth++) //提?¨￠取¨?第ì¨2data[i+1][i]到ì?data[x-1][i]的ì?數(shù)oy據(jù)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臨￠¨′時o?à變à?量￠?的ì?個?數(shù)oy. 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++) //假¨′如¨?以°?上|?兩￠?個?向¨°量￠?相¨¤等쨨則¨°退a?出?,則¨°跳??出?以°?進?行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的ì?轉(zhuǎn)áa置? Matrixzhuanzhi_x_y(x_y); //拷?貝à??構(gòu)1造¨?函?￥數(shù)oy 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;}//------------------------------------檢¨?查¨|是o?否¤?為a實o|ì對?稱?矩?陣¨?voidMatrix::check_shiduichen(){ if(x!=y) { cout<<"\n\n不?是o?是o?對?稱?矩?陣¨?(行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不?是o?實o|ì對?稱?矩?陣¨?!(不?對?稱?!)\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) //設(shè)|¨¨置?行D數(shù)oy{ x=xx;}voidMatrix::set_y(unsignedyy) //設(shè)|¨¨置?列￠D數(shù)oy{ y=yy;}unsignedMatrix::get_x() //得ì?到ì?行D數(shù)oy{ returnx;}unsignedMatrix::get_y() //得ì?到ì?列￠D數(shù)oy{ returny;}doubleMatrix::getdata(unsignedi,unsignedj) //定?§位?得ì?到ì?數(shù)oy據(jù)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) //生|¨2成¨|i行D單ì￡¤位?矩?陣¨?{ init(); x=y=lenth; for(unsignedi=0;i<lenth;i++) data[i][i]=1;}voidMatrix::shucheng(doublechangshu) //數(shù)oy乘?運?算?加¨?入¨?并?é行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