中南大学 计算机体系结构实验报告.docx
- 文档编号:18381045
- 上传时间:2023-08-16
- 格式:DOCX
- 页数:29
- 大小:112.77KB
中南大学 计算机体系结构实验报告.docx
《中南大学 计算机体系结构实验报告.docx》由会员分享,可在线阅读,更多相关《中南大学 计算机体系结构实验报告.docx(29页珍藏版)》请在冰点文库上搜索。
中南大学计算机体系结构实验报告
CENTRALSOUTHUNIVERSITY
计算机体系结构实验报告
学生姓名
班级
学号
指导教师穆帅
实验时间2014年11月
目录
实验1对指令操作码进行霍夫曼编码----------------2
实验2使用LRU方法更新Cache------------------------14
实验3单功能流水线调度机构模拟-------------------18
实验总结------------------------------------------------------21
参考文献------------------------------------------------------21
实验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编码正如下图所示:
最后得到的HUFFMAN编码如下表所示:
P1
P2
P3
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_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);//在工作链表中删除最小概率节点函数。
voidinservoidinsert_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;
inti=0;
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;
inti=0;
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) { rd=creat_huffp(min2); } else { 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; deletep; 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); } deletep1; } voidcreat_huffman_code(huff_p*h1,huff_code*h) { inti=0; 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++; } inti1=int(j); huff_code*p2=head->next; float*p_a=newfloat[i1]; //sort指令概率 inti0=0; while(p2) { p_a[i0++]=p2->p; p2=p2->next; } floatmax,temp; intl; 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。 "< } } 4、实验结果及分析 实验2使用LRU方法更新Cache 一、实验目的 了解和掌握寄存器分配和内存分配的有关技术。 二、实验内容 程序1结合数据结构的相关知识,使用LRU的策略,对一组访问序列进行内部的Cache更新 LRU置换算法是选择最近最久未使用的页面予以置换。 该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来经历的时间T,当须淘汰一个页面时,选择现有页面中T值最大的,即最近最久没有访问的页面。 这是一个比较合理的置换算法。 举例说明此问题,例如: 有一个CACHE采用组相连映象方式。 每组有四块,为了实现LRU置换算法,在快表中为每块设置一个2位计数器。 我们假设访问序列为“1,1,2,4,3,5,2,1,6,7,1,3”。 在访问CACHE的过程中,块的装入,置换及命中时,具体情况如下表所示: 三、实例 程序清单及注释: #include #include #defineM4 #defineN30 #defineMyprintfprintf("|---+---+---+---+---+---+---+---+---+---+---+---|\n") typedefstructpage {intnum;/*记录页面号*/ inttime;/*记录调入内存时间*/ }Page;/*页面逻辑结构,结构为方便算法实现设计*/ Pageb[M];/*内存单元数*/ intc[M][N];/*暂保存内存当前的状态: 缓冲区*/ intqueue[100];/*记录调入队列*/ intK;/*调入队列计数变量*/ /*初始化内存单元、缓冲区*/ voidInit(Page*b,intc[M][N]) {inti,j; for(i=0;i {b[i].num=-1; b[i].time=N-i-1; } for(i=0;i for(j=0;j c[i][j]=-1; } /*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/ intGetMax(Page*b) {inti; intmax=-1; inttag=0; for(i=0;i {if(b[i].time>max) { max=b[i].time; tag=i; } } returntag; } /*判断页面是否已在内存中*/ intEquation(intfold,Page*b) {inti; for(i=0;i {if(fold==b[i].num) returni; } return-1; } /*LRU核心部分*/ voidLru(intfold,Page*b) {inti; intval; val=Equation(fold,b); if(val>=0) {b[val].time=0; for(i=0;i if(i! =va
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中南大学 计算机体系结构实验报告 中南 大学 计算机体系结构 实验 报告