计算机体系结构实验报告

1、计算机体系结构F南大学计算机体系结构实验报告学生姓名信息科学与工程学院专业班级1.实验内容.2.实验1 :对指令操作码进行霍夫曼编码2.1实验目的2.2实验内容2.3实验结果3.实验2 :使用3.1实验目的3.2实验内容3.3实验结果LRU方法更新Cache .444 4.总结.5.代码附录.第3页共12页计算机体系结构计算机体系结构第14页共12页1.实验内容实验1对指令操作码进行霍夫曼编码实验2 使用LRU方法更新Cache2.实验1 :对指令操作码进行霍夫曼编码2.1实验目的了解和掌握指令编码的基本要求和基本原理2.2实验内容使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后

2、的编码结果以及 对指令码的长度进行评价。与扩展操作码和等长编码进行比较。要对指令的操作码进行HUFFMAN 树再进行HUFFMAN 编码，只要根据指令的各类操作码的出现概率构造HUFFAM 编码。此过程的难点构造HUFFMAN 树，进行 HUFFAM 编码只要对你所生成 的HUFFMAN 树进行中序遍历即可完成编码工作。2.3实验结果Ml 3-mh Inn 3nH- 丰 m L* 二 r dm -.14 JliJ- lif axax.xaa 卽郭酿第卵 一 F1 * I IM n n - -二亠i s 1- 1吃桁生雄塑旺础腐珂旧平均忆変力二上琵翊宓魏豁跖衞”2Pr-nr-f： aa rr-l

3、-hmif-fl H r-vrcit innFf-s-E ATI V ko-V to cont nu-.3. 实验2 :使用LRU方法更新Cache3.1实验目的了解和掌握寄存器分配和内存分配的有关技术。3.2实验内容Cache更新：结合数据结构的相关知识，使用LRU的策略，对一组访问序列进行内部的LRU置换算法是选择最近最久未使用的页面予以置换。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间T,当须淘汰一个页面时，选择现有页面中T值最大的，即最近最久没有访问的页面。这是一个比较合理的置换算法。3.3实验结果为为 执 J 伶聲1,耶e.75weaHeKCU.t lU

4、fi C Iht = LJ.bKl CTcSi 於hy hr# tJ tMCtirtiltr4. 总结实验一是曾在学习数字通信原理课程时编写的，当时只有简单的排序后编码的功能，学习了数据结构后，我往里面加入了树的结构，使编码后的结果更加清晰明了了。学习了计算机体系结构之后，我又往里面加入了求编码长度的功能。通过这个程序，我更加了解哈夫曼编码的知识了。实验二是写出LRU算法，这个相对来说比较简单，因为在学习操作系统原理时接触过FIFO等等算法并且编程实现了，难点在于输出结果的排版，一开始我想输出一个表格，这样更符合书上关于此算法的内容，但是出现了各种不对齐的问题，最后只好让它直接输出结果。通过这

5、几次实验，我发现了自身的不足，比如没有很好的书写习惯，考虑问题不周到，对于计算机体系结构课程中知识的理解不够深入等。但在编程的过程中我体验到了一分耕耘一分收获的喜悦；多次调试后程序成功运行了，那时候的欢乐是我以前无法想象的。果然,学习任何一门课程，只要学得用心，都可以从中体会到学习的快乐。今后我的进步，想必都是从这一点一点敲入编译器的代码中获得的。5. 代码附录实验1#in clude#in cludeusing n ames pace std;#defi ne N 8class huff_ ppublic:huff_p* r_child; II大概率的节点；huff_p* l_child;

6、II小概率的节点；char op_mask3; II 指令标号；float p; II指令使用概率；;class f_min_ppublic:f_min_P* n ext;char op_mask3; II 指令标号；float p; II指令使用概率； huff_ p* huf_ p;class huff_codepublic:huff_code* n ext;float p;char op_mask3;char codeN; IIhuffman 编码；;f_min_p* input_instruct_set();II 输入指令集子模块；huff_p* creat_huffman_tree(

7、f_min_p* head);II 构造 huffman 树;f_min_p* fin_min(f_min_p* h);f_min_p* del_ min(f_min_p* h,f_ min_p* p);void in sert_ 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);II 生成 huffman 编码;void r_fin d(huff_ p* p 1,char code,i nt i,huff_code* h);v

8、oid output_hufman(huff_code* head);/ 输出 huffman 编码;void cal_sort_length(huff_code* head);/ 计算指令用 huffman 编码的平均编码字长 int mai n() f_min_p *h,*h1;huff_ p *root;huff_code* head,* pl;int i=0;h=input_in struct_set();h1=h;root=creat_huffma n_tree(h1);head=new huff_code;head- next=NULL;creat_huffma n_code(ro

9、ot,head);out pu t_huffma n( head);cal_sort_le ngth(head);pl=head-n ext;while( pl)delete head;head=pl;pl=p l-n ext;f_min_p* input_in struct_set()f_min_P* head;f_min_P* h;h=new f_min_p;h- next=NULL;h-huf_ p=NULL;head=h;int n;coutn;H.cout h-op_mask;cout h-p;int i=0;f_min_p* point;f_min_P* P 1=head;for(

10、;i n-1;i+) point=new f_min_p;H.coutpoin t- op _mask;H.p oi nt-op_mask2=0;coutpoint-p;poi nt-huf_p=NULL; point-n ext=p1-n ext; p1-n ext=point; p1=poin t; return head; huff_ p* creat_huffma n_tree(f_min _p* h) f_min _p *h1,*mi n1,*mi n2,*comb; huff_ p* head,*rd,*ld,* parent;h1=h;min 1=fi n_min( h1); l

11、d=creat_huffp (min 1); h1=del_mi n(h1,mi n1); if(h1- next) min 2=fi n_min( h1);elsemin 2=h1; rd=creat_huffp (min 2); comb=new f_min _p; comb-n ext=NULL; comb-p=rd-p+ld-p; comb-op_mask0=0; comb-op_mask1=0; parn t=creat_huffp(comb); in sert_ n( h1,comb); if(h1- next!=NULL) h1=del_mi n(h1,mi n2); paren

12、 t-l_child=ld; paren t-r_child=rd; comb-huf_ p=parent; head=parent;int i=0;while(h1- next!=NULL) min 1=fi n_min( h1);if(mi n1-huf_p=NULL) ld=creat_huffp (min 1); else ld=min 1-huf_ p; h1=del_mi n(h1,mi n1); if(h1- next) min 2=fi n_min( h1);elsemin 2=h1;if(mi n2-huf_p=NULL) rd=creat_huffp (min 2);els

13、erd=min 2-huf_ p; comb=new f_min_p; comb-n ext=NULL; comb-p=rd-p+ld-p; comb-op_mask0=0; comb-op_mask1=0;paren t=creat_huffp(comb);if(h1!=NULL)in sert_ n( h1,comb);if(h1- next!=NULL) h1=del_mi n(h1,mi n2);paren t-l_child=ld;paren t-r_child=rd; comb-huf_ p=parent; head=parent;if(h1- next=NULL)break; d

14、elete 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(mi n(h1- p) min=h1- p;p1=h1;h1=h1- next;return p 1;f_min_p* del_ min( f_min _p *h,f_min _p *p) f_min_p *p 1,* p2;p1=h;p2=h;if(h=p) h=h-n ext;delete p;elsewhile( p1- next!=NULL

15、)p1=p1-n ext;if(p 1=p)p2-n ext=p1-n ext;delete p;break;p2=p1；return h;void in sert_ n(f_min_p *h,f_ min_p *p 1)p1-n ext=h-n ext;h-n ext =p 1;huff_ p* creat_huffp(f_ min_p* d)huff_ p* p1;p1=new huff_ p;p1-l_child=NULL;p1-r_child=NULL;p1-p=d-p;P 1- op _mask0=d- op _mask0;P 1- op _mask1=d- op _mask1;re

16、turn p 1;void r_fin d(huff_ p* p 1,char code,i nt i,huff_code* h) if(p 1-l_child)codei=1;r_fin d( p1-l_child,code,i+1,h);if(P 1-op_mask0!=0)huff_code* p2=new huff_code;p 2- op _mask0 =p 1- op _mask0;p 2- op _mask1=p 1- op _mask1;p1-op_mask2=0;p2-p=p1-p;int j;for( j=0;jcodej=codej;p2-codej=0;p2-n ext

17、=h-n ext;h-n ext =p 2;if(P 1-r_child)codei=0;r_fin d( p1-r_child,code,i+1,h);delete p1;void creat_huffma n_code(huff_ p* h1,huff_code* h) int i=0;char codeN;r_fin d(h1,code,i,h);void out pu t_huffma n( huff_code* head)huff_code* h=head-n ext;coute ndl;cout标号:-概率- -编码-endl;coutop_mask2=0;endl;cout op

18、 _mask: p coden ext; coutcoutn ext;double j=0;float one_len gth=0;float p er_le ngth=0;float ext_length=0;/按1-2-3-5扩展编码的最小长度为。 while(h)float le ngth=0;int i=0;while(h-codei!=0)len gth+;i+;on e_le ngth=h-p *le ngth;p er_le ngth=p er_le ngth+one_len gth; /12h=h-n ext;j+;int i1=i nt(j);huff_code *p 2=h

19、ead-n ext; float* p_a=new floati1; int i0=0;while( p2)p_ai0+=p2- p; p2=p 2- next; float max,te mp; int l;for(i nt s=0;si1;s+)max=p _as;l=s;for(i nt k=s+1;ki1;k+) if(maxp_ak) max=p _ak;l=k; temp=p _as;p_as=max; p_al=tem p; float* code_le n=new floati1;code_le n0=1;code_le n1=2; code_le n2=3;code_le n

20、3=5;for(i nt i=4;ij;i+)code_le ni=5;while(li1)ext_le ngth=ext_le ngth+code_le nl* p_al;double q_le ngth=log10(j)/log10(2);cout此指令集操作码 huffman编码的平均长度为 per_lengthendl;cout等长编码的平均长度为 q_lengthendl;cout按1-2-3-5的扩展编码的最短平均编码长度为ext_length;coute ndl;coute ndl;实验2#in clude #in clude#defi ne M 4#defi ne N 12#defi ne Myprintf printf(|-+-+-+-+-|n) typ edef struct p ageint num;int time;Page;Page bM;int cMN;int queue100;int K;/*记录页面号*/*记录调入内存时间*/*页面逻辑结构，结构为方便算法实现设计/*内存单元数*/*暂保存内存当前的状态：缓冲区/*记录调入队列*/*调入队列计数变量*/*/*/void lnit(P age *b,i nt cMN)int i,j;for(i=0;iN;i+)bi. nu m=-1;bi.time=N-i-1;for(i=