2016计算机体系结构实验指导书 中南大学
发布时间：2017-01-08 14:15:24
计算机系统（体系）结构实验指导书
1. 上机实验要求及规范
计算机体系结构是计算机专业学生的一门专业课程，本课程是计算机专业一门重要的专
业课，着重讲述计算机系统的软、硬件界面。对于学生从事计算机系统的研制、使用和维护
有重要意义。本课程概念多、内容涉及面广、系统性强。通过本课程的学习，学生应能从软
件、硬件功能分配的角度去了解、分析和研究计算机系统，建立起对计算机系统的全面认识，
树立全面地、发展地看问题的观点，从而加深对各种类型体系结构的了解，牢固地树立起整
机系统的概念。
本课程的学习应注重理论与实践相结合，因此实验教学是教学环节中必不可少的重要内
容。通过实验教学的学习，使学生熟练掌握有关计算机体系结构的基本概念、基本原理和基
本思想，掌握对计算机体系结构和组成进行分析和计算的方法。
实验部分包括四个实验，包括有完整的源程序例题，介绍了一些设计数据结构题目所需
的的知识和技巧。在实验题中，既有简单容易的验证题，即验证已经给出的源程序，或者扩
充已经给出的源程序，也有需独立思考设计的综合实验题。
计算机体系结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。上机
实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具
有一定的积极性。但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严
格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。
拿到一个题目，一般不要急于编程。按照面向过程的程序设计思路（关于面向对象的训练将
在其它后继课程中进行），正确的方法是：首先理解问题，明确给定的条件和要求解决的问
题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。
一、实验报告的基本要求：
一般性、较小规模的上机实验题，必须遵循下列要求。养成良好的习惯。
姓名 班级 学号 日期 题目
i. 问题描述
ii. 设计简要描述
iii. 程序清单（带有必要的注释）
iv. 结果分析（原始图示，测试数据与运行记录，分析正确性；）
v. 调试报告：
实验者必须重视最后这两个环节，否则等同于没有完成实验任务。这里可以体现个人特
色、或创造性思维。具体内容包括：测试数据与运行记录；调试中遇到的主要问题，自己是
如何解决的；经验和体会等。
二、实验习报告的提高要求：
阶段性、较大规模的上机实验题，应该遵循下列要求。养成科学的习惯。
（1）问题描述
（2）需求和规格说明
（3）描述问题，简述题目要解决的问题是什么。规定软件做什么。原题条件不足时补全。
（4）概要设计：功能模块的划分,ADT
（5）详细设计：每部分模块的设计，含数据结构的设计，算法的描述（流程图或PDL）
a.设计思想：存储结构（题目中限定的要描述）；主要算法基本思想。
b.设计表示：每个函数的头和规格说明；列出每个函数所调用和被调用的函数，也
可以通过调用关系图表达。
（6）实现注释：各项功能的实现程度、在完成基本要求的基础上还有什么功能。
（7）用户手册：即使用说明书。
（8）调试报告：调试过程中遇到的主要问题是如何解决的；设计的回顾、讨论和分析；
时间复杂度、空间复杂度分析；改进设想；经验和体会等。
实验 1 对指令操作码进行霍夫曼编码
一、实验目的
1． 了解和掌握指令编码的基本要求和基本原理
二、实验内容
1. 使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果
以及对指令码的长度进行评价。与扩展操作码和等长编码进行比较。
问题描述以及问题分析：
我们举例说明此问题，例如：
有一组指令的操作码共分七类，它们出现概率如
下表所示：
P1 P2 P3 P4 P5 P6 P7
0.45 0.30 0.15 0.05 0.03 0.01 0.01
对此组指令进行 HUFFMAN 编码正如下图所示：
0.45
0.30
0.15
0.05
0.03
0.01
0.01
0 1
0.02
0 1`
0.05
0 1
0.10
0 1
0.25
0 1
0.55
0 1
1.00
图 1
最后得到的 HUFFMAN 编码如下表所示：
P1
P2P3
P4
P5
P6
P7
0 10 110
1110 11110 111110 111111
1
2
3
4
5
6
6
最短编码长度为：
H=0.45*1+0.30*2+0.15*3+0.05*4+0.03*5+0.01*6+0.01*6=-1.95.
要对指令的操作码进行 HUFFMAN 编码，只要根据指令的各类操作码的出现概率构造
HUFFMAN 树再进行 HUFFAM 编码。此过程的难点构造 HUFFMAN 树，进行 HUFFAM 编
码只要对你所生成的 HUFFMAN 树进行中序遍历即可完成编码工作。
三、实例
观察上图 1，不难看出构造 HUFFMAN 树所要做的工作：1、先对各指令操作码的出现
概率进行排序，构造一个有序链表。2、再取出两个最小的概率节点相加，生成一个生的节
点加入到链表中，同时从两表中删除此两个节点。3、在对链表进行排序，链表是否只有一
个节点，是则 HUFFAN 树构造完毕，否则继续做 2 的操作。为此设计一个工作链表（链表
的元素时类，此类的功能相当结构。）、HUFFMAN 树节点、HUFFMAN 编码表节点。具体
如下：
//huff_man tree point;
class huff_p{
public:
huff_p* r_child; //大概率的节点,即右子节点；
huff_p* l_child; //小概率的节点,即左子节点；
char op_mask[3]; //指令标号；
float p; //指令使用概率；
};
//work link point
class f_min_p{
public:
f_min_p* next;
char op_mask[3]; //指令标号；
float p; //指令使用概率；
huff_p* huf_p;
};
/huff_man code point
class huff_code{
public:
huff_code*next;
float p;
char op_mask[3];
char code[N]; //huffman 编码；
};
函数说明：
f_min_p* input_instruct_set();//输入指令集子模块；
huff_p* creat_huffman_tree(f_min_p* head);//构造 huffman 树;
f_min_p* fin_min(f_min_p* h); //在工作链表中寻找最小概率节点函数。
f_min_p* del_min(f_min_p* h,f_min_p* p);//在工作链表中删除最小概率节点函数。
void insert_n(f_min_p* h,f_min_p* p);// 在工作链表中插入两个最小概率节点生成的节点函
数。
huff_p* creat_huffp(f_min_p* p);//生成 HUFFMAN 节点。
void creat_huffman_code(huff_p* h1,huff_code* h);//生成 huffman 编码;
void r_find(huff_p* p1,char code[],int i,huff_code* h);
//遍历 HUFFMAN 树生成指令操作码的 HUFFMAN 编码。
void output_huffman(huff_code* head);//输出 huffman 编码;
void cal_sort_length(huff_code* head);//计算指令用 huffman 编码的平均编码字长
程序清单及注释：
#include
#include
#define N 8
//find two min program;
//huff_man tree pont;
class huff_p{
public:
huff_p* r_child; //大概率的节点；
huff_p* l_child; //小概率的节点；
char op_mask[3]; //指令标号；
float p; //指令使用概率；
};
class f_min_p{
public:
f_min_p* next;
char op_mask[3]; //指令标号；
float p; //指令使用概率；
huff_p* huf_p;
};
//huff_man code
class huff_code{
public:
huff_code*next;
float p;
char op_mask[3];
char code[N]; //huffman 编码；
};
f_min_p* input_instruct_set();//输入指令集子模块；
huff_p* creat_huffman_tree(f_min_p* head);//构造 huffman 树;
f_min_p* fin_min(f_min_p* h);
f_min_p* del_min(f_min_p* h,f_min_p* p);
void insert_n(f_min_p* h,f_min_p* p);
huff_p* creat_huffp(f_min_p* p);
void creat_huffman_code(huff_p* h1,huff_code* h);//生成 huffman 编码;
void r_find(huff_p* p1,char code[],int i,huff_code* h);
void output_huffman(huff_code* head);//输出 huffman 编码;
void cal_sort_length(huff_code* head);//计算指令用 huffman 编码的平均编码字长
void main()
{
f_min_p *h,*h1;
huff_p *root;
huff_code*head,*pl;
int
h=input_instruct_set();
/*
p1=h;
while(p1)
{
cout<
p1=p1->next;
}
*/
h1=h;
root=creat_huffman_tree(h1);
head=new huff_code;
head->next=NULL;
creat_huffman_code(root,head);
output_huffman(head);
cal_sort_length(head);
pl=head->next;
while(pl)
{
delete head;
head=pl;
pl=pl->next;
}
}
f_min_p* input_instruct_set()
{
f_min_p* head;
f_min_p* h;
h=newf_min_p;
h->next=NULL;
h->huf_p=NULL;
head=h;
int n;
cout<<"请输入指令数:";
cin>>n;
cout<<"请输入指令标号：";
cin>>h->op_mask;
cout<<"请输入指令的使用概率：";
cin>>h->p;
int
f_min_p* point;
f_min_p* p1=head;
for(;i
{
point=new f_min_p;
cout<<"请输入指令标号：";
cin>>point->op_mask;
point->op_mask[2]='\0';
cout<<"请输入指令的使用概率：";
cin>>point->p;
point->huf_p=NULL;
point->next=p1->next;
p1->next=point;
p1=point;
}
return head;
}
huff_p* creat_huffman_tree(f_min_p* h)
{
f_min_p *h1,*min1,*min2,*comb;
huff_p* head,*rd,*ld,*parent;
h1=h;
min1=fin_min(h1);
ld=creat_huffp(min1);
h1=del_min(h1,min1);
if(h1->next)
min2=fin_min(h1);
else
min2=h1;
rd=creat_huffp(min2);
comb=new f_min_p;
comb->next=NULL;
comb->p=rd->p+ld->p;
comb->op_mask[0]='\0';
comb->op_mask[1]='\0';
parent=creat_huffp(comb);
insert_n(h1,comb);
if(h1->next!=NULL)
h1=del_min(h1,min2);
parent->l_child=ld;
parent->r_child=rd;
comb->huf_p=parent;
head=parent;
int i=0;
cout<
while(h1->next!=NULL)
{
min1=fin_min(h1);
if(min1->huf_p==NULL)
{
ld=creat_huffp(min1);
}
else
{
ld=min1->huf_p;
}
h1=del_min(h1,min1);
if(h1->next)
min2=fin_min(h1);
else
min2=h1;
if(min2->huf_p==NULL)
{
}
else
{
}
rd=creat_huffp(min2);
rd=min2->huf_p;
comb=new f_min_p;
comb->next=NULL;
comb->p=rd->p+ld->p;
comb->op_mask[0]='\0';
comb->op_mask[1]='\0';
parent=creat_huffp(comb);
if(h1!=NULL)
insert_n(h1,comb);
if(h1->next!=NULL)
h1=del_min(h1,min2);
parent->l_child=ld;
parent->r_child=rd;
comb->huf_p=parent;
head=parent;
cout<<++i<
if(h1->next==NULL)break;
}
delete comb;
return head;
}
f_min_p* fin_min(f_min_p* h)
{
f_min_p *h1,*p1;
h1=h;
p1=h1;
float min=h1->p;
h1=h1->next;
while(h1)
{
if(min>(h1->p))
{
min=h1->p;
p1=h1;
}
h1=h1->next;
}
return p1;
}
f_min_p* del_min( f_min_p *h,f_min_p *p)
{
f_min_p *p1,*p2;
p1=h;
p2=h;
if(h==p)
{
h=h->next;
delete p;
}
else
{
while(p1->next!=NULL)
{
p1=p1->next;
if(p1==p)
{
p2->next=p1->next;
delete
break;
}
p2=p1;
}
}
return h;
}
void insert_n(f_min_p *h,f_min_p *p1)
{
p1->next=h->next;
h->next=p1;
}
huff_p* creat_huffp(f_min_p* d)
{
huff_p* p1;
p1=newhuff_p;
p1->l_child=NULL;
p1->r_child=NULL;
p1->p=d->p;
p1->op_mask[0]=d->op_mask[0];
p1->op_mask[1]=d->op_mask[1];
return p1;
}
void r_find(huff_p* p1,char code[],int i,huff_code* h)
{
if(p1->l_child)
{
code[i]='1';
r_find(p1->l_child,code,i+1,h);
}
if(p1->op_mask[0]!='\0')
{
huff_code* p2=new huff_code;
p2->op_mask[0]=p1->op_mask[0];
p2->op_mask[1]=p1->op_mask[1];
p1->op_mask[2]='\0';
p2->p=p1->p;
for(int j=0;j
{
p2->code[j]=code[j];
}
p2->code[j]='\0';
p2->next=h->next;
h->next=p2;
}
if(p1->r_child)
{
code[i]='0';
r_find(p1->r_child,code,i+1,h);
}
delete
}
void creat_huffman_code(huff_p* h1,huff_code* h)
{
int
char code[N];
r_find(h1,code,i,h);
}
void output_huffman(huff_code* head)
{
huff_code* h=head->next;
cout<<"OP:"<<"--概率--"<<' '<<"--编码--"<
cout<<"---------------------------------"<
while(h)
{
}
h->op_mask[2]='\0';
cout<
h=h->next;
}
cout<<"---------------------------------"<
cout<
void cal_sort_length(huff_code* head)
{
huff_code *h=head->next;
double j=0;
floatone_length=0;
floatper_length=0;
floatext_length=0;//按 1-2-3-5 扩展编码的最小长度为。
while(h)
{
float length=0;
int i=0;
while(h->code[i]!='\0')
{
length++;
i++;
}
one_length=h->p*length;
per_length=per_length+one_length;
h=h->next;
j++;
}
int
huff_code *p2=head->next;
float* p_a=new float[i1];
//sort 指令概率
int
while(p2)
{
p_a[i0++]=p2->p;
p2=p2->next;
}
floatmax,temp;
l;int
for(int s=0;s
{
max=p_a[s];
l=s;
for(int k=s+1;k
{
if(max
{
max=p_a[k];l=k;
}
}
temp=p_a[s];
p_a[s]=max;
p_a[l]=temp;
}
//计算 1-2-3-5 扩展编码的最短平均长度
float* code_len=new float[i1];
code_len[0]=1;
code_len[1]=2;
code_len[2]=3;
code_len[3]=5;
for(int i=4;i
l=0;
while(l
{
ext_length=ext_length+code_len[l]*p_a[l];
l++;
}
//计算等长编码平均长度；
double q_length=log10(j)/log10(2);
cout<<"此指令集操作码 huffman 编码的平均长度为："<
cout<<"等长编码的平均长度为："<
cout<<"按 1-2-3-5 的扩展编码的最短平均编码长度为："<
cout<
cout<
if(q_length>per_length)
{
cout<<"可见 HUFFMAN 编码的平均长度要比等长编码的平均长度短"<
}
else
{
cout<<"huffman 编码有问题请仔细查看算法，以及输入的指令集的概率之和是否大
于 1。"<
}
{
if(ext_length>per_length)
cout<<"可见 HUFFMAN 编码的平均长度要比 1-2-3-5 扩展编码的最短平均长度短
"<
}
else
{
cout<<"huffman 编码有问题请仔细查看算法，以及输入的指令集的概率之和是否大
于 1。"<
}
}
实验 2 使用 LRU 方法更新 Cache
一、实验目的
了解和掌握寄存器分配和内存分配的有关技术。
二、实验内容
程序 1
Cache 更新
结合数据结构的相关知识，使用 LRU 的策略，对一组访问序列进行内部的
LRU 置换算法是选择最近最久未使用的页面予以置换。该算法赋予每个页面一个访问
字段，用来记录一个页面自上次被访问以来经历的时间 T，当须淘汰一个页面时，选择现有
页面中 T 值最大的，即最近最久没有访问的页面。这是一个比较合理的置换算法。
举例说明此问题，例如：
有一个 CACHE 采用组相连映象方式。每组有四块，为了实现 LRU 置换算法，在快表
中为每块设置一个 2 位计数器。我们假设访问序列为“1,1,2,4,3,5,2,1,6,7,1,3”。在访问 CACHE
的过程中，块的装入，置换及命中时，具体情况如下表所示：
1
Cache 块 0 1
Cache 块 1
Cache 块 2
Cache 块 3
1
1
2
1
2
4
1
2
4
3
1
2
4
3
5
5
2
4
3
2
5
2
4
3
1
5
2
1
3
6
5
2
1
6
7
7
2
1
6
1
7
2
1
6
3
7
3
1
6
装
入
三、实例
命
中
装
入
装
入
装
入
置
换
命
中
置
换
置
换
置
换
命
中
置
换
此程序中最重要的算法当然是 LRU 置换算法，：
// cache 更新算法,LRU
void up_cache()
{
int i=0;
while(i
{
int j=0;
//满么?
while(j
{
if((cache[j].state==false)&&(walk_sort[i]!=cache[j].value))
{
cout<<"cache 有空闲块,不考虑是否要置换."<
cout<
cache[j].value=walk_sort[i++];
cache[j].state=true;
cache[j].count=0;
int kk=0;
for (x=0;x
cout<<"cache 块"<
cout<
//更新其它 cache 块没使用时间
while(kk
{
if(kk!=j&&cache[kk].value!=(-1))
cache[kk].count++;
kk++;
}
delay();
break;
}
if(cache[j].value==walk_sort[i])
{
cout<
cout<
for (x=0;x
cout<<"cache 块"<
cout<
int kk=0;
i++;
cache[j].count=0;
//更新其它 cache 块没使用时间
while(kk
{
if(kk!=j&&cache[kk].value!=(-1))
cache[kk].count++;
kk++;
}
}
j++;
}
if(j==m)
{
cout<<"cache 已经满了,考虑是否置换."<
cout<
int k=0;
while(k
{
if(cache[k].value==walk_sort[i])
{
cout<
cout<
for (x=0;x
cout<<"cache 块"<
i++;
cache[k].count=0;
int kk=0;
//更新其它 cache 块没使用时间
while(kk
{
if(kk!=k)
cache[kk].count++;
kk++;
}
break;
}
k++;
}
if(k==m)//考虑置换那一块.
{
int ii=0;
int t=0;//要替换的 cache 块号.
int max=cache[ii].count;
ii++;
while(ii
{
if(cache[ii].count>max)
{
max=cache[ii].count;
t=ii;
}
ii++;
}
//置换
cout<
cache[t].value=walk_sort[i++];
cache[t].count=0;
for (x=0;x
cout<<"cache 块"<
int kk=0;
//更新其它 cache 块没使用时间
while(kk
{
if(kk!=t)
cache[kk].count++;
kk++;
}
delay();
}
}
}
}
一、实验目的
实验 3 通道处理过程模拟
通过模拟实现通道处理过程，掌握通道技术。
二、实验内容
程序 1
结合数据结构的相关知识,编写通道处理过程模拟程序。
1 通道完成一次数据输入输出的过程需三步（如图一所示）：
(1) 在用户程序中使用访管指令进入管理程序，由 CPU 通过管理程序组织一个通道程序，
并启
动通道；
(2) 通道处理机执行通道程序，完成指定的数据输入输出工作；
(3) 通道程序结束后第二次调用管理程序对输入输出请求进行处理每完成一次输入输出工
作， CPU 只需要两次调用管理程序，大大减少了对用户程序的打扰。
图一 通道程序，管理程序和用户程序的执行时间关系
2 通道的主要功能（如图二所示）：
（1）接受 CPU 发来的指令，选择一台指定的外围设备与通道相连接
（2）执行 CPU 为通道组织的通道程序
（3）管理外围设备的有关地址
（4）管理主存缓冲区的地址
（5）控制外围设备与主存缓冲区间数据交换的个数
（6）指定传送工作结束时要进行的操作
（7）检查外围设备的工作状态，是正常或故障
（8）在数据传输过程中完成必要的格式的变换
二、实例
1．传输方式为内存到设备,采用字节多路方式,设备分时复用通道的工作算法。
void memoryToDevice(char** mem) {
char** memory;
memory =mem;
for(int fence = 0 ;fence < MaxDevCap; fence++)
for(int i = 0;i < actDeviceNum ; i++)
{
if(fence < device[i].actCap)
{
device[i].data[fence] = memory[i][fence];
}
printDevice();
}
printDevice();
}
2.CPU 处理不同的中断的算法。
void run()
{
while(true)
{
if(channalManager.interrupt == NONE)
{
cout<<"The cpu is doing some thing..."<
cout<<"The cpu is doing some thing..."<
break;
}
if(channalManager.interrupt == INIT)
{
cout<<"CPU is interrupted"<
device..."<
}
cout<<"This is a I/0 Init
break;
instruction,The channalManager is init the
if(channalManager.interrupt == FINISH)
{ cout<<"CPU is interrupted"<
cout<<"This is a I/0 Finish instruction,The channalManager is close the
device..."<
break;
}
}
}
3. 测试数据及运行结果
a.初始化内存块中需要传输的数据:
char* memory[3];
memory[0] = "love";
memory[1] = "channel";
memory[2] = "architecture";
b.设备中的内容为空：
c．字节多路通道程序分时为不同的设备服务：
d．通道程序执行完毕，CPU 中断后关闭设备，继续执行用户程序。
实验 4 单功能流水线调度机构模拟
一、实验目的
结合数据结构的相关知识,编写流水线调度模拟程序
二、实验内容
程序 1 通过模拟单功能流水线调度过程，掌握流水线技术，学会计算流水线的吞吐率、
加速比、效率。
1 流水线的表示法有三种：
连接图、时空图、预约表。对于线性流水线，主要考虑前二种。
2 流水线的主要特点：
在流水线的每一个功能部件的后面都要有一个缓冲器，称为锁存器、闸门寄存器等，
它的作用是保存本流水段的执行结果。各流水段的时间应尽量相等，否则回引起阻塞、
断流等。只有连续提供同类任务才能充分发挥流水线的效率。在流水线的每一个流水线
段中都要设置一个流水锁存器。流水线需要有“装入时间”和“排空时间”。只有流水线完
全充满时，整个流水线的效率才能得到充分发挥。
三、实例
1．存储时空图的数据结构及相关变量。
# define SPACE 4 /*功能部件数目*/
# define TIME INUM+(SPACE-1) /*存储不同时间段各个功能部件内指令值*/
# define INUM 5 /*需要流水处理的浮点加指令数目*/
int ts[SPACE][TIME] = {0};/*初始化时空图*/
int time = 1;/*记录运行时候时间周期*/
2．流水线中各条指令状态转换的算法实现。
void pipeline(int ts[SPACE][TIME])
{
int
记录处理的指令号*/
int tempTime=0;/*记录时间轴的变化*/
for(int s=SPACE-1;s>=0;s--)
{
tempSpace=1;
for(int t=tempTime;t
ts[s][t]=tempSpace++;
tempTime++;
}
}
测试数据及运行结果
本实验选取四段单功能流水线浮点加作为测试的例子。
选取 5 条指令作为测试任务，并计算流水线的吞吐率、加速比和效率。
程序初始化后界面如下：
ED：求阶差 EA：对阶MA：尾数加 NL：规格化
程序执行完毕后的运行界面如下：
相关推荐
世界各大化妆品品牌介绍
新春团拜会活动主持词XX新春团拜会主持词
一个人孤独伤感的说说心情短语，句句扎心，看过心都碎了-心情短语
外贸公司及产品英语介绍
银行法人结算客户经理述职报告范文
项目要求
放射科医德医风个人工作总结
七年级英语Unit6 学案
一个人孤独伤感的说说心情短语，句句扎心，看过心都碎了
纪委办纪检监察调研法规工作计划
