北郵 大三下 計算機系統(tǒng)結(jié)構(gòu)-非線性流水線無沖突調(diào)度-實驗報告

09211311班 Page 課程名稱：計算機系統(tǒng)結(jié)構(gòu) 實驗名稱：代碼優(yōu)化實驗班級：09211311姓名：schnee 學號：日 期：2012年4月20日目錄TOC\o"1-2"\h\z\u1. 實驗要求 32. 實驗準備 32.1. 非線性流水線（NonlinearPipelining） 32.2. 非線性流水線的沖突 32.3. 無沖突調(diào)度方法 33. 實現(xiàn)代碼 44. 實驗結(jié)果和分析 84.1. 測試一：PPT例題測試 84.2. 測試二：對應(yīng)于同一個流水線的兩個不同預(yù)約表，測試是否結(jié)果一致 95. 實驗心得和總結(jié) 10實驗?zāi)康膶W習簡單編譯優(yōu)化方法，觀察采用編譯優(yōu)化方法所帶來的性能的提高。實驗原理采用靜態(tài)調(diào)度方法重排指令序列，減少相關(guān)，優(yōu)化程序。實現(xiàn)代碼#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) { //輸入預(yù)約表 printf("請輸入流水線預(yù)約表的時間和功能段大小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; } //由沖突向量構(gòu)造有向狀態(tài)圖 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; } // 狀態(tài)圖// 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':''); //尋找啟動距離最小的等間隔調(diào)度 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("啟動距離最小的等間隔調(diào)度為：%d\n\n",min_equ_dis); //尋找最佳調(diào)度，即最小平均間隔拍數(shù) 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("最優(yōu)調(diào)度的平均啟動距離為：%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;}實驗結(jié)果和分析測試一：PPT例題測試預(yù)約表：實驗結(jié)果截圖：測試二：對應(yīng)于同一個流水線的兩個不同預(yù)約表，測試是否結(jié)果一致預(yù)約表一：預(yù)約表二：運行結(jié)果對比截圖：比較分析： 即使對于同一個流水線，預(yù)約表不同，所求出的最優(yōu)調(diào)度也不一定相同。實驗心得和總結(jié)通過這次實際上機編程實驗，我把課上內(nèi)容重新復(fù)習了一遍，并且對非線性流水線無沖突調(diào)度算法有了更深刻的認識，通過編程過程的調(diào)試，更正了之前對該算法的一些理解錯誤的地方。比如即使是新的狀態(tài)在繼續(xù)求新一輪新狀態(tài)時也是和最初始的狀態(tài)取按位或，而不是和當前所求的狀態(tài)按位或。這個問題我一開始理解錯了，導(dǎo)致求出來的狀態(tài)圖出現(xiàn)錯誤，重新思考并理解算法，才把這個誤區(qū)