多核研究性课题实验报告
辽宁师范大学计算机与信息技术学院
综合性实验报告
课程名称:实验题目:学生姓名:专业: 学号: 实验日期:
实验成绩:
多核并行程序设计 基于主成分分析的并行程序设计 孙蕾 计算机科学与技术 [1**********]005 2012年11月25日
一、实验目的
通过对主成分分析法进行研究,了解主成分分析在生产生活中的重要应用性。在此基础上找到算法,给出计算对称矩阵特征值的串行算法,并在此基础上利用多核程序设计将其并行化,以优化运行速度。通过本实验了解并行程序设计原理并达到基本能应用的水平。
二、实验内容 1. 对主成分分析法进行学习,明白其原理以及在现实生活中的应用方面和
实际意义。
2. 按照对主成分分析的理解找到计算特征值的算法并完成串行程序。 3. 在串行程序的基础上应用多核程序设计的原理将程序并行化,分别对串
行程序和并行程序计算运行时间,计算加速比,加深多核程序设计的理解。
4. 总结研究中的问题以及克服方法,心得和体会。
三、实验过程(含结果抓图) 1. 串行程序代码及结果抓图
#include #include #include #include
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //class Matrix定义矩阵类
const int Max_xy=20; //矩阵的最大维数 class Matrix { private: double data[Max_xy][Max_xy]; unsigned x,y; //x,y; public: Matrix(); //默认构造函数 Matrix(const Matrix & source); //拷贝构造函数 void creat(); //输入矩阵 void init(); void transpose(); //矩阵转置
void show(); //输入此矩阵 double mode() const; //求一维矩阵的长度 void check_shiduichen(); //检查是否为是对称矩阵 void creat_unit(unsigned i); //生成i 行单位矩阵 void set_x(unsigned xx); //设置行数 void set_y(unsigned yy); //设置列数 unsigned get_x(); //得到行数 unsigned get_y(); //得到列数 void shucheng(double changshu); //数乘运算 void setdata(unsigned i,unsigned j,double source); //定位输入数据 double getdata(unsigned i,unsigned j); //定位得到数据 void sturm(); //求特征值 unsigned sturm_s(double m); //计算sturm 系列的同好数 Matrix operator = (const Matrix & right); friend Matrix & operator + (const Matrix & left,const Matrix & right); //重载+号 friend Matrix & operator - (const Matrix & left,const Matrix & right); //重载-号 friend Matrix & operator * (const Matrix & left,const Matrix & right); //重载乘号 friend ostream& operator
Matrix temp_Matrix; //全局变量Matrix
//===================================================================
//--------------------默认构造函数 Matrix::Matrix() { init(); }
//----------------------------拷贝构造函数 Matrix::Matrix(const Matrix & source) { init(); x=source.x; y=source.y; for(unsigned i=0;i
}
//------------------------------------------初始化矩阵元素 void Matrix::init() { x=y=0; for(unsigned i=0;i
//------------------------------矩阵转置 void Matrix::transpose() { double temp;int t; for(unsigned i=0;i
//--------------------------------------求一维矩阵的长度 double Matrix::mode() const { double s=0; unsigned i,j; if(x==1) for(i=0,j=0;j
} s=sqrt(s); return (s); }
//----------------------------------------重载=号
Matrix Matrix::operator = (const Matrix & source) { x=source.x; y=source.y; for(unsigned i=0;i
//-------------------------------------------重载+号
Matrix & operator + (const Matrix & left,const Matrix & right) { if(left.x!=right.x || left.y!=right.y) { cout
//---------------------------------------------重载+号
Matrix & operator - (const Matrix & left,const Matrix & right) { if(left.x!=right.x || left.y!=right.y) { cout
temp_Matrix.data[i][j]=left.data[i][j] - right.data[i][j]; temp_Matrix.x=right.x; temp_Matrix.y=right.y; return temp_Matrix; }
//----------------------------------------重载乘号
Matrix & operator * (const Matrix & left,const Matrix & right) { if(left.y!=right.x) { cout
//-------------------------------------------输入矩阵 void Matrix::creat() { cout>x; cout>y; for(unsigned i=0;i>data[i][j]; } }
//----------------------------------------------输出矩阵 void Matrix::show() { unsigned i,j; cout
//----------------------------------用Householder 矩阵化为实对称矩阵 void Householder(Matrix & source) { unsigned i,lenth,k,m,n,flag; double temp_lie_x[Max_xy],temp_lie_y[Max_xy],temp[Max_xy]; double s; for(i=0;i
for(k=0,flag=0;k
//得到最后的Householder
//------------------------------------检查是否为实对称矩阵 void Matrix::check_shiduichen() { if(x!=y) { cout
ostream & operator
void Matrix::set_x(unsigned xx) //设置行数 { x=xx; }
void Matrix::set_y(unsigned yy) //设置列数 { y=yy; }
unsigned Matrix::get_x() //得到行数 { return x; }
unsigned Matrix::get_y() //得到列数 { return y; }
double Matrix::getdata(unsigned i,unsigned j) //定位得到数据 { return data[i][j]; }
void Matrix::setdata(unsigned i,unsigned j,double source) { data[i][j]=source; if(x
void Matrix::creat_unit(unsigned lenth) //生成i 行单位矩阵 { init(); x=y=lenth; for(unsigned i=0;i
void Matrix::shucheng(double changshu) //数乘运算 { unsigned i,j; for(i=0;i
void Matrix::sturm() { double s,r,maxhang,a,b;unsigned i,j,m; for(i=0,maxhang=0;imaxhang) maxhang=s; } a=-maxhang; b=maxhang; m=sturm_s(a)-sturm_s(b); for(i=1;i=i) a=r; else b=r; } while(fabs(a-b)>1e-11); cout
unsigned Matrix::sturm_s(double r) { double p[Max_xy+1]; int temp[Max_xy+1]; unsigned m,i; p[0]=1; p[1]=data[0][0]-r; for(i=2;i1e-14) temp[i]=1;
else if(p[i]
int _tmain(int argc, _TCHAR* argv[]) { double begin,end,time; begin=(double)clock()/(double)CLK_TCK; Matrix a; a.creat(); cout串行运行结果:
2. 并行程序代码及结果抓图
// bingxing.cpp : 定义控制台应用程序的入口点
//
// c.cpp : 定义控制台应用程序的入口点 //
#include "stdafx.h" #include #include #include #include #include using namespace std;
//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //class Matrix定¡§义°? 矩? 阵¨类¤¨¤
const int Max_xy=20;//矩? 阵¨的Ì? 最Á?大ä¨维? 数ºy class Matrix {
double data[Max_xy][Max_xy]; unsigned x,y; Matrix();
//x,y;
private :
public :
//默? 认¨? 构1造¨¬函¡¥数ºy
Matrix(const Matrix & source);
//拷? 贝À¡ä构1造¨¬函¡¥数ºy
};
void creat(); void init();
//输º? 入¨? 矩? 阵¨ //矩? 阵¨转Áa置? //输º? 入¨? 此ä? 矩? 阵¨
//求¨一°? 维? 矩? 阵¨的Ì? 长¡è度¨¨
void transpose(); void show();
double mode() const ;
void check_shiduichen(); void creat_unit(unsigned i); void set_x(unsigned xx); void set_y(unsigned yy); unsigned get_x(); unsigned get_y();
//检¨¬查¨¦是º? 否¤? 为a 是º? 对? 称? 矩? 阵¨ //生¦¨²成¨¦i 行D 单Ì£¤位? 矩? 阵¨ //设¦¨¨置? 行D 数ºy //设¦¨¨置? 列¢D 数ºy
//得Ì? 到Ì? 行D 数ºy //得Ì? 到Ì? 列¢D 数ºy //数ºy 乘? 运? 算?
//定¡§位? 输º? 入¨? 数ºy 据Y //定¡§位? 得Ì? 到Ì? 数ºy 据Y
//计? 算?sturm 系¦Ì列¢D 的Ì? 同ª? 好? 数ºy
void shucheng(double changshu);
void setdata(unsigned i,unsigned j,double source); double getdata(unsigned i,unsigned j); void sturm();
unsigned sturm_s(double m);
//求¨特¬? 征¡Â值¦Ì
Matrix operator = (const Matrix & right);
friend Matrix & operator + (const Matrix & left,const Matrix & right); //重? 载?+号? friend Matrix & operator - (const Matrix & left,const Matrix & right); //重? 载?-号? friend Matrix & operator * (const Matrix & left,const Matrix & right); //重? 载? 乘? 号? friend ostream& operator
//重? 载? 输º? 出?
//用?Householde矩? 阵¨将? 实º¦Ì
对? 称? 矩? 阵¨化¡¥为a 三¨y 对? 角? 矩? 阵¨
Matrix temp_Matrix;
//全¨? 局? 变À?量¢?Matrix
//===================================================================
//--------------------默? 认¨? 构1造¨¬函¡¥数ºy Matrix::Matrix() { }
//----------------------------拷? 贝À¡ä构1造¨¬函¡¥数ºy Matrix::Matrix(const Matrix & source) {
init(); x=source.x; y=source.y;
init();
}
for (unsigned j=0;j
data[i][j]=source.data[i][j];
//------------------------------------------初? 始º? 化¡¥矩? 阵¨元a 素? void Matrix::init() { }
//------------------------------矩? 阵¨转Áa置? void Matrix::transpose() { }
//--------------------------------------求¨一°? 维? 矩? 阵¨的Ì? 长¡è度¨¨ double Matrix::mode() {
double s=0; unsigned i,j; if (x==1)
for (i=0,j=0;j
s+=data[i][j]*data[i][j];
const
double temp;int t;
for (unsigned i=0;i
for (unsigned j=0;j
temp=data[i][j]; data[i][j]=data[j][i]; data[j][i]=temp;
x=y=0;
for (unsigned i=0;i
for (unsigned j=0;j
data[i][j]=0;
else if (y==1)
for (i=0,j=0;i
s+=data[i][j]*data[i][j];
else
}
} s=sqrt(s); return (s);
cout
//----------------------------------------重? 载?=号? Matrix Matrix::operator = (const Matrix & source) { }
//-------------------------------------------重? 载?+号?
Matrix & operator + (const Matrix & left,const Matrix & right) { int j; }
//---------------------------------------------重? 载?-号?
Matrix & operator - (const Matrix & left,const Matrix & right) {
if (left.x!=right.x || left.y!=right.y) {
if (left.x!=right.x || left.y!=right.y) { }
for(unsigned i=0;i
#pragma omp parallel for private(j) for( j=0;j
temp_Matrix.data[i][j]=right.data[i][j] + left.data[i][j]; cout
x=source.x; y=source.y;
for (unsigned i=0;i
for (unsigned j=0;j
data[i][j]=source.data[i][j];
return *this ;
temp_Matrix.x=right.x; temp_Matrix.y=right.y; return temp_Matrix;
}
}
cout
for (unsigned i=0;i
for (unsigned j=0;j
temp_Matrix.data[i][j]=left.data[i][j] - right.data[i][j]; temp_Matrix.x=right.x; temp_Matrix.y=right.y; return temp_Matrix;
//----------------------------------------重? 载? 乘? 号?
Matrix & operator * (const Matrix & left,const Matrix & right) { }
//-------------------------------------------输º? 入¨? 矩? 阵¨ void Matrix::creat() {
cout>x;
cout>y;
for (unsigned i=0;i
cout
temp_Matrix.x=left.x; temp_Matrix.y=right.y; return temp_Matrix; if (left.y!=right.x) { }
temp_Matrix.init(); unsigned i,j,k; for (i=0;i
for (j=0;j
for (k=0;k
temp_Matrix.data[i][j]+=left.data[i][k] * right.data[k][j];
cout
}
}
for (unsigned j=0;j
cin>>data[i][j];
//----------------------------------------------输º? 出? 矩? 阵¨ void Matrix::show() { }
//----------------------------------用?Householder矩? 阵¨化¡¥为a 实º¦Ì对? 称? 矩? 阵¨ void Householder(Matrix & source) {
for (k=0;k
for(i=0;i
for(k=0;k
for (lenth=0;lenth+i+1
//提¬¨¢取¨? 第̨²data[i+1][i]到Ì?data[x-1][i]的Ì? 数ºy
//初? 始º? 化¡¥为a0 temp_lie_x[k]=0; temp_lie_y[k]=0; temp[k]=0;
unsigned i,j;
cout
cout
cout
#pragma omp parallel for private(k)
据Y 存ä? 到Ì?temp_lie[Max_xy];
temp_lie_x[lenth]=source.data[lenth+i+1][i];
//j为a 临¢¨´时º¡À变À?量¢? 的Ì? 个? 数ºy.
s+=temp_lie_x[k]*temp_lie_x[k]; for (k=0,s=0;k
temp_lie_y[k]=0;
}
//假¨´如¨? 以°? 上¦? 两¢? 个? 向¨°量¢? 相¨¤等̨¨则¨°退ª?
for (k=0,flag=0;k
if (temp[k]!=0) { } continue ;
flag=1; break ;
出?, 则¨°跳¬? 出? 以°? 进? 行D 下? 一°? 次ä? 变À?换?
if (flag==0)
Matrix part_h,I,x_y; //定¡§义°?Matrix 变À?量¢? I.creat_unit(lenth); x_y.x=lenth,x_y.y=1; //对?x_y赋3值¦Ì for (k=0;k
x_y.data[k][0]=temp[k];
//拷? 贝À¡ä构1造¨¬函¡¥数ºy
//求¨x_y的Ì? 转Áa置? Matrix zhuanzhi_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; Matrix H;
H.creat_unit(source.x); for (m=i+1;m
for (n=i+1;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
for (k=0;k
if (fabs(source.data[i][k])
source.data[i][k]=0;
}
//------------------------------------检¨¬查¨¦是º? 否¤? 为a 实º¦Ì对? 称? 矩? 阵¨ void Matrix::check_shiduichen() { }
ostream & operator
void Matrix::set_x(unsigned xx) { }
void Matrix::set_y(unsigned yy) {
//设¦¨¨置? 列¢D 数ºy
x=xx;
//设¦¨¨置? 行D 数ºy
unsigned i,j;
for (i=0;i
os
for (j=0;j
os
for (unsigned i=0;i
for (unsigned j=0;j
if (data[i][j]!=data[j][i]) { }
cout
if (x!=y) { }
cout
}
unsigned Matrix::get_x() { }
unsigned Matrix::get_y() { }
return y; return x;
//得Ì? 到Ì? 行D 数ºy
//得Ì? 到Ì? 列¢D 数ºy
double Matrix::getdata(unsigned i,unsigned j) { }
return data[i][j];
//定¡§位? 得Ì? 到Ì? 数ºy 据Y
void Matrix::setdata(unsigned i,unsigned j,double source) { }
void Matrix::creat_unit(unsigned lenth) { }
void Matrix::shucheng(double changshu) { int i,j;
omp_set_num_threads(3); #pragma omp parallel for for(i=0;i
for(j=0;j
//数ºy 乘? 运? 算? 加¨入¨? 并¡é行D 语?句?
init(); x=y=lenth;
for (unsigned i=0;i
data[i][i]=1;
//生¦¨²成¨¦i 行D 单Ì£¤位? 矩? 阵¨
data[i][j]=source; if (x
x=i; y=j;
}
data[i][j]*=changshu;
void Matrix::sturm() { }
unsigned Matrix::sturm_s(double r) {
double p[Max_xy+1]; int temp[Max_xy+1]; unsigned m,i; p[0]=1;
p[1]=data[0][0]-r; for (i=2;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]; double s,r,maxhang,a,b;unsigned i,j,m; for (i=0,maxhang=0;i
a=-maxhang; b=maxhang;
m=sturm_s(a)-sturm_s(b); for (i=1;i
a=-maxhang; b=maxhang; do { }
while (fabs(a-b)>1e-11);
cout
=i)
a=r; b=r; else
for ( s=0,j=0;j
s+=fabs(data[i][j]); maxhang=s; if (s>maxhang)
}
temp[0]=1; for (i=1;i
if (p[i]>1e-14) else
temp[i]=temp[i-1]; temp[i]=1; temp[i]=-1; else if (p[i]
for (i=1,m=0;i
if (temp[i]+temp[i-1]!=0)
m++;
return m;
int _tmain(int argc, _TCHAR* argv[]) { }
double begin,end,time;
begin=(double )clock()/(double )CLK_TCK; Matrix a; a.creat();
couta.check_shiduichen(); Householder(a);
coutend=(double )clock()/(double )CLK_TCK; cout
time=end-begin;
程序运行结果:
四、实验结果分析(运行过程中出现的问题、如何解决的;实验过程中的经验及教训)
并行化结果展示:3*3维矩阵 串行程序时间:t1=9.81ms 并行程序时间:t2=7.612ms 加速比=20.81ms/7.612=2.733 并行化结果展示:10*10维矩阵 串行程序时间:t1=144.581ms 并行程序时间:t2=109.699ms
加速比=144.581ms/109.699ms=1.317 并行化结果展示:15*15维矩阵 串行程序时间:t1=365.461ms 并行程序时间:t2=290.316ms
加速比=365.461ms/290.316ms=1.255 体现了并行的优越性。 遇到的问题及经验教训: 1. 在串行程序并行化的过程中由于对 openMP 的环境不熟悉以及对并行程
序设计了解不多,程序编译过程出现很多错误。后来通过查询资料知道了如何运用一些函数如何使用,环境如何配置,很快克服了,得到了正确的结果。
2. 在使用测试数据时,由于数据量大才能显示出并行技术的优越性,所以
开始的时候数据量小,后来加大了数据量,效果好很多。需要输入对称阵,因此一处输出错误就出现错误结果,以后将好好注意,算法上加以改正。