计算机系统结构课程设计-单功能非线性流水线最佳调度程序.docVIP

福建农林大学计算机与信息学院计算机类课程设计课程名称：计算机系统结构课程设计设计题目：单功能非线性流水线最佳调度程序姓 名：系：计算机专 业：计算机科学与技术年 级：学 号：指导教师：职 称：2012年 11 月 30 日 福建农林大学计算机与信息学院计算机类课程设计结果评定评价内容评价指标评分权值评定成绩工作态度工作努力，严格按照课程技能训练设计的要求去做，表现好；遵守纪律，工作作风严谨务实。20业务水平能按时优异地完成课程设计任务，能熟练地综合运用所学理论和专业知识，在技能训练中对某些技能、技术有新建议、有小革新、有创见。动手能力强，实干精神强，团结协作能力强，适应能力强。30设计报告质量报告或成果完整、正确，概念清楚，图纸表格齐全，文字通顺，排版打印符合要求。40工作量按期完成规定的任务，工作量饱满，难度较大。10成绩：指导教师签字：评定日期：9目 录1设计的目的1页2设计要求1页3主要仪器设备（软硬件环境）1页4设计内容1页4.1设计原理1页4.2总体方案设计2页4.3程序设计2页4.4程序的调试和运行结果9页5总结9页参考文献9页单功能非线性流水线最佳调度程序1. 设计的目的通过课程设计进一步了解计算机系统的设计及工作原理，进一步熟悉和掌握单功能非线性流水线最佳调度.利用所学知识完成相关程序的设计、运行和调试工作。2. 设计要求要求设计一个处理程序，输入非线性流水线各个功能段使用的时间(拍)，通过程序处理后输出正确的最佳调度方案。3. 主要仪器设备（软硬件环境）PC机、windows xp 、VC+ 6.04. 设计内容4.1 设计原理非线性流水线无冲突调度的目标是找出平均允许启动距离最小的启动循环。按照这样的启动循环向流水线的 输 入 端 输 入 任 务， 所 有 功 能 段 在 任 何 时 刻 都 没 有 冲 突 ， 而 且流水线的工作效率最高。在进行这一工作时 ， 首先要进行的就是 画 出 无 冲 突 调 度 方 案 的 状 态 图， 求 得 所 有 的 调 度 方 案 ， 再 找出平均允许启动距离最小的调度方案。4.2总体方案设计4.3 程序设计#include#include#include#includeusing namespace std;const int inf=100000;int mat2020; int tmp_ban20;int ban20;int int_ban;int point105;int edge105105;int pn;double opt_dis;int dis20;int dn, pre;bool has20;struct optimalint rn;int road20;op20;int opn;void search(int id)int i, j, k;for(i=0; ipn; i+)if(edgeidiinf)if(hasi=true & i!=pre)continue;disdn+=edgeidi;if(hasi=true)double tmp=0;for(j=0; jdn; j+)tmp+=disj;tmp/=dn;if(tmp=opt_dis)if(tmpopt_dis)opn=0, opt_dis=tmp;opopn.rn=dn;for(j=0; jdn; j+)opopn.roadj=disj;opn+;else hasi=true;search(i);hasi=false;dn-;int main()/freopen(in.txt, r, stdin);/freopen(out.txt, w, stdout);int m, n, i, j, k, tmp;while(1)/输入预约表printf(请输入流水线预约表的时间和功能段大小m和n(m,n15): );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, &matij);printf(n);/计算禁止向量memset(tmp_ban, 0, sizeof(tmp_ban); int maxd=0;for(i=1; i=n; i+)for(j=1; j=m; j+)if(matij=1)for(k=j+1; k(k-j)maxd=maxd;else maxd=k-j; tmp_bank-j=1;/计算冲突向量int_ban=0;tmp=1;for(i=1; i=maxd; i+)int_ban+=tmp*tmp_bani;tmp*=2;/由冲突向量构造有向状态图pn=1;point0=int_ban;memset(edge, 127, sizeof(edge);int id;for(i=0; ipn; i+)tmp=pointi;for(j=1; j=maxd; j+)if(tmp%2=0)tmp/=2;pointpn=tmp|point0;id=pn;for(k=0; kpn; k+)if(pointk=pointpn)id=k;break;if(k=pn) pn+;/edgeiid=min(j, edgeiid);if(jedgeiid)edgeiid=j;else tmp/=2;/初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接edgei0=maxd+1;/寻找启动距离最小的等间隔调度int min_equ_dis=maxd+1;for(i=0; ipn; i+)if(edgeiimin_equ_dis)min_equ_dis=edgeii;printf(启动距离最小的等间隔调度为： %dnn, min_equ_dis);/寻找最佳调度，即最小平均间隔拍数opt_dis=inf;opn=0;for(i=0; ipn; i+)memset(has, false, sizeof(has);dn=0;pre=i;hasi=true;search(i);printf(最优调度的平均启动距离为：%lfn, opt_dis);for(i=0; iopn; i+)printf(方法%d: , i+1); for(j=0; jopi.rn; j+)printf(%d , opi.roadj);printf(n);printf(n);system(pause);return 0; 4.4 程序的调试和运行结果5. 总结在设计的过程中，由于自己以前学习不太深入，不得不去复习需要用到的指针、结构体、有向图的邻接表等数据结构里的知识！通过复习，与同学交流，逐步完成了此次课程的设计！这次课程设计，使我对单功能非线性流水线有了一定的了解，为以后更好地学习与流水线相关的各方面知识奠定了一定的基础！参考文献：1 郑芹 非线性流水线的无冲突调度的分析. 福建电脑. 2005,03：1-2。2 李学干等 . 计算机系统结构 (第四版). 西安 西安电子科技大学出版社 3 军师 .非线性流水线计算机调度问题的研究. 电脑开发与应用 1995