北邮 大三下 计算机系统结构-非线性流水线无冲突调度-实验报告

09211311班 Page 课程名称：计算机系统结构 实验名称：代码优化实验班级：09211311姓名：schnee 学号：日 期：2012年4月20日目录TOC\o"1-2"\h\z\u1. 实验要求 32. 实验准备 32.1. 非线性流水线（NonlinearPipelining） 32.2. 非线性流水线的冲突 32.3. 无冲突调度方法 33. 实现代码 44. 实验结果和分析 84.1. 测试一：PPT例题测试 84.2. 测试二：对应于同一个流水线的两个不同预约表，测试是否结果一致 95. 实验心得和总结 10实验目的学习简单编译优化方法，观察采用编译优化方法所带来的性能的提高。实验原理采用静态调度方法重排指令序列，减少相关，优化程序。实现代码#include<cstdio>#include<cstdlib>#include<algorithm>#include<string>usingnamespacestd;constintinf=100000;intmat[20][20];inttmp_ban[20];intban[20];intint_ban;intpoint[105];intedge[105][105];intpn;doubleopt_dis;intdis[20];intdn,pre;boolhas[20];structoptimal{ intrn; introad[20];}op[20];intopn;voidsearch(intid){ inti,j,k; for(i=0;i<pn;i++) if(edge[id][i]<inf) { if(has[i]==true&&i!=pre)continue; dis[dn++]=edge[id][i]; if(has[i]==true) { doubletmp=0; for(j=0;j<dn;j++) tmp+=dis[j]; tmp/=dn; if(tmp<=opt_dis) { if(tmp<opt_dis)opn=0,opt_dis=tmp; op[opn].rn=dn; for(j=0;j<dn;j++) op[opn].road[j]=dis[j]; opn++; } } else { has[i]=true; search(i); has[i]=false; } dn--; }}intmain(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); intm,n,i,j,k,tmp; while(1) { //输入预约表 printf("请输入流水线预约表的时间和功能段大小m和n(m,n<15):"); scanf("%d%d",&m,&n); if(m==0)break; printf("请在下表中输入0-空格或1-X：\n"); printf("功能段\时间"); for(i=1;i<=m;i++) printf("%d",i); printf("\n"); for(i=1;i<=n;i++) { printf("S%d",i); for(j=1;j<=m;j++) scanf("%d",&mat[i][j]); } printf("\n"); //计算禁止向量 memset(tmp_ban,0,sizeof(tmp_ban));intmaxd=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(mat[i][j]==1) for(k=j+1;k<=m;k++) if(mat[i][k]==1) { maxd=max(maxd,k-j); tmp_ban[k-j]=1; } //计算冲突向量 int_ban=0; tmp=1; for(i=1;i<=maxd;i++) { int_ban+=tmp*tmp_ban[i]; tmp*=2; } //由冲突向量构造有向状态图 pn=1; point[0]=int_ban; memset(edge,127,sizeof(edge)); intid; for(i=0;i<pn;i++) { tmp=point[i]; for(j=1;j<=maxd;j++) { if(tmp%2==0) { tmp/=2; point[pn]=tmp|point[0]; id=pn; for(k=0;k<pn;k++) if(point[k]==point[pn]) { id=k; break; } if(k==pn)pn++; edge[i][id]=min(j,edge[i][id]); } elsetmp/=2; } //初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接 edge[i][0]=maxd+1; } // 状态图// printf("pn===%dint_ban==%dmaxd===%d\n",pn,int_ban,maxd);// for(i=0;i<pn;i++)// for(j=0;j<pn;j++)// printf("%d%c",edge[i][j],(j==pn-1)?'\n':''); //寻找启动距离最小的等间隔调度 intmin_equ_dis=maxd+1; for(i=0;i<pn;i++) if(edge[i][i]<min_equ_dis) min_equ_dis=edge[i][i]; printf("启动距离最小的等间隔调度为：%d\n\n",min_equ_dis); //寻找最佳调度，即最小平均间隔拍数 opt_dis=inf; opn=0; for(i=0;i<pn;i++) { memset(has,false,sizeof(has)); dn=0; pre=i; has[i]=true; search(i); } printf("最优调度的平均启动距离为：%lf\n",opt_dis); for(i=0;i<opn;i++) { printf("方法%d:",i+1); for(j=0;j<op[i].rn;j++) printf("%d",op[i].road[j]); printf("\n"); } printf("\n"); } system("pause"); return0;}实验结果和分析测试一：PPT例题测试预约表：实验结果截图：测试二：对应于同一个流水线的两个不同预约表，测试是否结果一致预约表一：预约表二：运行结果对比截图：比较分析： 即使对于同一个流水线，预约表不同，所求出的最优调度也不一定相同。实验心得和总结通过这次实际上机编程实验，我把课上内容重新复习了一遍，并且对非线性流水线无冲突调度算法有了更深刻的认识，通过编程过程的调试，更正了之前对该算法的一些理解错误的地方。比如即使是新的状态在继续求新一轮新状态时也是和最初始的状态取按位或，而不是和当前所求的状态按位或。这个问题我一开始理解错了，导致求出来的状态图出现错误，重新思考并理解算法，才把这个误区