计算机体系结构实验指导书 中南大学.docx
- 文档编号:14058147
- 上传时间:2023-06-20
- 格式:DOCX
- 页数:40
- 大小:35.44KB
计算机体系结构实验指导书 中南大学.docx
《计算机体系结构实验指导书 中南大学.docx》由会员分享,可在线阅读,更多相关《计算机体系结构实验指导书 中南大学.docx(40页珍藏版)》请在冰点文库上搜索。
计算机体系结构实验指导书中南大学
计算机系统(体系)结构实验指导书
1.上机实验要求及规范
计算机体系结构是计算机专业学生的一门专业课程,本课程是计算机专业一门重要的专
业课,着重讲述计算机系统的软、硬件界面。
对于学生从事计算机系统的研制、使用和维护
有重要意义。
本课程概念多、内容涉及面广、系统性强。
通过本课程的学习,学生应能从软
件、硬件功能分配的角度去了解、分析和研究计算机系统,建立起对计算机系统的全面认识,
树立全面地、发展地看问题的观点,从而加深对各种类型体系结构的了解,牢固地树立起整
机系统的概念。
本课程的学习应注重理论与实践相结合,因此实验教学是教学环节中必不可少的重要内
容。
通过实验教学的学习,使学生熟练掌握有关计算机体系结构的基本概念、基本原理和基
本思想,掌握对计算机体系结构和组成进行分析和计算的方法。
实验部分包括四个实验,包括有完整的源程序例题,介绍了一些设计数据结构题目所需
的的知识和技巧。
在实验题中,既有简单容易的验证题,即验证已经给出的源程序,或者扩
充已经给出的源程序,也有需独立思考设计的综合实验题。
计算机体系结构课程具有比较强的理论性,同时也具有较强的可应用性和实践性。
上机
实验是一个重要的教学环节。
一般情况下学生能够重视实验环节,对于编写程序上机练习具
有一定的积极性。
但是容易忽略实验的总结,忽略实验报告的撰写。
对于一名大学生必须严
格训练分析总结能力、书面表达能力。
需要逐步培养书写科学实验报告以及科技论文的能力。
拿到一个题目,一般不要急于编程。
按照面向过程的程序设计思路(关于面向对象的训练将
在其它后继课程中进行),正确的方法是:
首先理解问题,明确给定的条件和要求解决的问
题,然后按照自顶向下,逐步求精,分而治之的策略,逐一地解决子问题。
一、实验报告的基本要求:
一般性、较小规模的上机实验题,必须遵循下列要求。
养成良好的习惯。
姓名班级学号日期题目
i.问题描述
ii.设计简要描述
iii.程序清单(带有必要的注释)
iv.结果分析(原始图示,测试数据与运行记录,分析正确性;)
v.调试报告:
实验者必须重视最后这两个环节,否则等同于没有完成实验任务。
这里可以体现个人特
色、或创造性思维。
具体内容包括:
测试数据与运行记录;调试中遇到的主要问题,自己是
如何解决的;经验和体会等。
二、实验习报告的提高要求:
阶段性、较大规模的上机实验题,应该遵循下列要求。
养成科学的习惯。
(1)问题描述
(2)需求和规格说明
(3)描述问题,简述题目要解决的问题是什么。
规定软件做什么。
原题条件不足时补全。
(4)概要设计:
功能模块的划分,ADT
(5)详细设计:
每部分模块的设计,含数据结构的设计,算法的描述(流程图或PDL)
a.设计思想:
存储结构(题目中限定的要描述);主要算法基本思想。
b.设计表示:
每个函数的头和规格说明;列出每个函数所调用和被调用的函数,也
可以通过调用关系图表达。
(6)实现注释:
各项功能的实现程度、在完成基本要求的基础上还有什么功能。
(7)用户手册:
即使用说明书。
(8)调试报告:
调试过程中遇到的主要问题是如何解决的;设计的回顾、讨论和分析;
时间复杂度、空间复杂度分析;改进设想;经验和体会等。
实验1对指令操作码进行霍夫曼编码
一、实验目的
1.了解和掌握指令编码的基本要求和基本原理
二、实验内容
1.使用编程工具编写一个程序,对一组指令进行霍夫曼编码,并输出最后的编码结果
以及对指令码的长度进行评价。
与扩展操作码和等长编码进行比较。
问题描述以及问题分析:
我们举例说明此问题,例如:
有一组指令的操作码共分七类,它们出现概率如
下表所示:
P1P2P3P4P5P6P7
0.450.300.150.050.030.010.01
对此组指令进行HUFFMAN编码正如下图所示:
0.45
0.30
0.15
0.05
0.03
0.01
0.01
01
0.02
01`
0.05
01
0.10
01
0.25
01
0.55
01
1.00
图1
最后得到的HUFFMAN编码如下表所示:
P1
P2
P3
P4
P5
P6
P7
010110
111011110111110111111
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_mantreepoint;
classhuff_p{
public:
huff_p*r_child;//大概率的节点,即右子节点;
huff_p*l_child;//小概率的节点,即左子节点;
charop_mask[3];//指令标号;
floatp;//指令使用概率;
};
//worklinkpoint
classf_min_p{
public:
f_min_p*next;
charop_mask[3];//指令标号;
floatp;//指令使用概率;
huff_p*huf_p;
};
/huff_mancodepoint
classhuff_code{
public:
huff_code*next;
floatp;
charop_mask[3];
charcode[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);//在工作链表中删除最小概率节点函数。
voidinsert_n(f_min_p*h,f_min_p*p);//在工作链表中插入两个最小概率节点生成的节点函
数。
huff_p*creat_huffp(f_min_p*p);//生成HUFFMAN节点。
voidcreat_huffman_code(huff_p*h1,huff_code*h);//生成huffman编码;
voidr_find(huff_p*p1,charcode[],inti,huff_code*h);
//遍历HUFFMAN树生成指令操作码的HUFFMAN编码。
voidoutput_huffman(huff_code*head);//输出huffman编码;
voidcal_sort_length(huff_code*head);//计算指令用huffman编码的平均编码字长
程序清单及注释:
#include
#include
#defineN8
//findtwominprogram;
//huff_mantreepont;
classhuff_p{
public:
huff_p*r_child;//大概率的节点;
huff_p*l_child;//小概率的节点;
charop_mask[3];//指令标号;
floatp;//指令使用概率;
};
classf_min_p{
public:
f_min_p*next;
charop_mask[3];//指令标号;
floatp;//指令使用概率;
huff_p*huf_p;
};
//huff_mancode
classhuff_code{
public:
huff_code*next;
floatp;
charop_mask[3];
charcode[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);
voidinsert_n(f_min_p*h,f_min_p*p);
huff_p*creat_huffp(f_min_p*p);
voidcreat_huffman_code(huff_p*h1,huff_code*h);//生成huffman编码;
voidr_find(huff_p*p1,charcode[],inti,huff_code*h);
voidoutput_huffman(huff_code*head);//输出huffman编码;
voidcal_sort_length(huff_code*head);//计算指令用huffman编码的平均编码字长
voidmain()
{
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=newhuff_code;
head->next=NULL;
creat_huffman_code(root,head);
output_huffman(head);
cal_sort_length(head);
pl=head->next;
while(pl)
{
deletehead;
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;
intn;
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=newf_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; } returnhead; } 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=newf_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; inti=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=newf_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; } deletecomb; returnhead; } f_min_p*fin_min(f_min_p*h) { f_min_p*h1,*p1; h1=h; p1=h1; floatmin=h1->p; h1=h1->next; while(h1) { if(min>(h1->p)) { min=h1->p; p1=h1; } h1=h1->next; } returnp1; } 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; deletep; } else { while(p1->next! =NULL) { p1=p1->next; if(p1==p) { p2->next=p1->next; delete break; } p2=p1; } } returnh; } voidinsert_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]; returnp1; } voidr_find(huff_p*p1,charcode[],inti,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=newhuff_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(intj=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 } voidcreat_huffman_code(huff_p*h1,huff_code*h) { int charcode[N]; r_find(h1,code,i,h); } voidoutput_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< voidcal_sort_length(huff_code*head) { huff_code*h=head->next; doublej=0; floatone_length=0; floatper_length=0; floatext_length=0;//按1-2-3-5扩展编码的最小长度为。 while(h) { floatlength=0; inti=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=newfloat[i1]; //sort指令概率 int while(p2) { p_a[i0++]=p2->p; p2=p2->next; } floatmax,temp; l;int for(ints=0;s { max=p_a[s]; l=s; for(intk=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=newfloat[i1]; code_len[0]=1; code_len[1]=2; code_len[2]=3; code_len[3]=5; for(inti=4;i l=0; while(l { ext_length=ext_length+code_len[l]*p_a[l]; l++; } //计算等长编码平均长度; doubleq_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置换算法是选择最近最久未使用的页面予以置换。 该算法赋予每个页面一个访问 字段,用来记录一个页面自上次被访问以
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机体系结构实验指导书 中南大学 计算机体系结构 实验 指导书 中南 大学
![提示](https://static.bingdoc.com/images/bang_tan.gif)