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

福建农林大学计算机与信息学院
计算机类课程设计

课程名称：
计算机系统结构课程设计
设计题目：
单功能非线性流水线最佳调度程序
姓 名：

系：
计算机
专 业：
计算机科学与技术
年 级：

学 号：

指导教师：

职 称：

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.0
4. 设计内容
4.1 设计原理
非线性流水线无冲突调度的目标是找出平均允许启动距离最小的启动循环。按照这样的启动循环向流水线的 输 入 端 输 入 任 务， 所 有 功 能 段 在 任 何 时 刻 都 没 有 冲 突 ， 而 且流水线的工作效率最高。在进行这一工作时 ， 首先要进行的就是 画 出 无 冲 突 调 度 方 案 的 状 态 图， 求 得 所 有 的 调 度 方 案 ， 再 找出平均允许启动距离最小的调度方案。

4.2总体方案设计

4.3 程序设计
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<string>
using namespace std;
const int inf=100000;

int mat[20][20];
int tmp_ban[20];
int ban[20];
int int_ban;
int point[105];
int edge[105][105];
int pn;

double opt_dis;
int dis[20];
int dn, pre;
bool has[20];
struct optimal
{
int rn;
int road[20];
}op[20];
int opn;

void search(int id)
{
int i, 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)
{
double tmp=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--;
}
}

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,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));
int maxd=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);
if (maxd>(k-j))
maxd=maxd;
else 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));
int id;
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]);
if(j<edge[i][id])
edge[i][id]=j;

}
else tmp/=2;
}
//初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接
edge[i][0]=maxd+1;
}

//寻找启动距离最小的等间隔调度
int min_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");
return 0;
}

4.4 程序的调试和运行结果

5. 总结
在设计的过程中，由于自己以前学习不太深入，不得不去复习需要用到的指针、结构体、有向图的邻接表等数据结构里的知识！通过复习，与同学交流，逐步完成了此次课程的设计！
这次课程设计，使我对单功能非线性流水线有了一定的了解，为以后更好地学习与流水线相关的各方面知识奠定了一定的基础！

参考文献：
[1] 郑芹 非线性流水线的无冲突调度的分析. 福建电脑. 2005,03：1-2。
[2] 李学干等 . 计算机系统结构 (第四版). 西安 西安电子科技大学出版社
[3] 军师 .非线性流水线计算机调度问题的研究. 电脑开发与应用 1995，04
[4] 张代远.原理及其在非线性流水线调度中的应用.算机工程与应用 2006，,16
[5] .