计算机体系结构实验报告

1、计算机体系结构中南大学计算机体系结构实验报告学生姓名 学 院 信息科学与工程学院 专业班级 完成时间 2015年10月27日 目 录1.实验内容22.实验1：对指令操作码进行霍夫曼编码32.1 实验目的32.2 实验内容32.3 实验结果33.实验2 ：使用 LRU 方法更新 Cache33.1 实验目的33.2 实验内容43.3 实验结果44. 总结45. 代码附录5计算机体系结构1.实验内容实验 1 对指令操作码进行霍夫曼编码实验 2 使用 LRU 方法更新 Cache2.实验1：对指令操作码进行霍夫曼编码 2.1 实验目的了解和掌握指令编码的基本要求和基本原理2.2 实验内容 使用编程工

2、具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。与扩展操作码和等长编码进行比较。要对指令的操作码进行 HUFFMAN 编码，只要根据指令的各类操作码的出现概率构造HUFFMAN 树再进行 HUFFAM 编码。此过程的难点构造 HUFFMAN 树，进行 HUFFAM编码只要对你所生成的 HUFFMAN 树进行中序遍历即可完成编码工作。2.3 实验结果 3.实验2 ：使用 LRU 方法更新 Cache3.1 实验目的 了解和掌握寄存器分配和内存分配的有关技术。3.2 实验内容Cache 更新：结合数据结构的相关知识，使用LRU的策略，对一组访问序列进行内部

3、的LRU置换算法是选择最近最久未使用的页面予以置换。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来经历的时间 T，当须淘汰一个页面时，选择现有页面中 T 值最大的，即最近最久没有访问的页面。这是一个比较合理的置换算法。3.3 实验结果4. 总结 实验一是曾在学习数字通信原理课程时编写的，当时只有简单的排序后编码的功能，学习了数据结构后，我往里面加入了树的结构，使编码后的结果更加清晰明了了。学习了计算机体系结构之后，我又往里面加入了求编码长度的功能。通过这个程序，我更加了解哈夫曼编码的知识了。实验二是写出LRU算法，这个相对来说比较简单，因为在学习操作系统原理时接触过FIFO等

4、等算法并且编程实现了，难点在于输出结果的排版，一开始我想输出一个表格，这样更符合书上关于此算法的内容，但是出现了各种不对齐的问题，最后只好让它直接输出结果。 通过这几次实验，我发现了自身的不足，比如没有很好的书写习惯，考虑问题不周到，对于计算机体系结构课程中知识的理解不够深入等。但在编程的过程中我体验到了一分耕耘一分收获的喜悦；多次调试后程序成功运行了，那时候的欢乐是我以前无法想象的。果然，学习任何一门课程，只要学得用心，都可以从中体会到学习的快乐。今后我的进步，想必都是从这一点一点敲入编译器的代码中获得的。5. 代码附录实验1#include#includeusing namespace s

5、td;#define N 8class huff_ppublic:huff_p* r_child; /大概率的节点；huff_p* l_child; /小概率的节点；char op_mask3; /指令标号；float p; /指令使用概率；;class f_min_ppublic:f_min_p* next;char op_mask3; /指令标号；float p; /指令使用概率；huff_p* huf_p;class huff_codepublic:huff_code* next;float p;char op_mask3;char codeN; /huffman 编码；;f_min_p

6、* 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(h

7、uff_p* p1,char code,int i,huff_code* h);void output_huffman(huff_code* head);/输出huffman编码;void cal_sort_length(huff_code* head);/计算指令用huffman编码的平均编码字长int main()f_min_p *h,*h1;huff_p *root;huff_code* head,*pl;int i=0;h=input_instruct_set();h1=h;root=creat_huffman_tree(h1);head=new huff_code;head-next

8、=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=new f_min_p;h-next=NULL;h-huf_p=NULL;head=h;int n;coutn;couth-op_mask;couth-p;int i=0;f_min_p* point;f_min_p* p1

9、=head;for(;in-1;i+)point=new f_min_p;coutpoint-op_mask;point-op_mask2=0;coutpoint-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=de

10、l_min(h1,min1);if(h1-next)min2=fin_min(h1);elsemin2=h1;rd=creat_huffp(min2);comb=new f_min_p;comb-next=NULL;comb-p=rd-p+ld-p;comb-op_mask0=0;comb-op_mask1=0;parnt=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=paren

11、t;int i=0;while(h1-next!=NULL)min1=fin_min(h1);if(min1-huf_p=NULL)ld=creat_huffp(min1);elseld=min1-huf_p;h1=del_min(h1,min1);if(h1-next)min2=fin_min(h1);elsemin2=h1;if(min2-huf_p=NULL)rd=creat_huffp(min2);elserd=min2-huf_p;comb=new f_min_p;comb-next=NULL;comb-p=rd-p+ld-p;comb-op_mask0=0;comb-op_mask

12、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;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

13、(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;elsewhile(p1-next!=NULL)p1=p1-next;if(p1=p)p2-next=p1-next;delete p;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* crea

14、t_huffp(f_min_p* d)huff_p* p1;p1=new huff_p;p1-l_child=NULL;p1-r_child=NULL;p1-p=d-p;p1-op_mask0=d-op_mask0;p1-op_mask1=d-op_mask1;return p1;void r_find(huff_p* p1,char code,int i,huff_code* h)if(p1-l_child)codei=1;r_find(p1-l_child,code,i+1,h);if(p1-op_mask0!=0)huff_code* p2=new huff_code;p2-op_mas

15、k0=p1-op_mask0;p2-op_mask1=p1-op_mask1;p1-op_mask2=0;p2-p=p1-p;int j;for( j=0;jcodej=codej;p2-codej=0;p2-next=h-next;h-next=p2;if(p1-r_child)codei=0;r_find(p1-r_child,code,i+1,h);delete p1;void creat_huffman_code(huff_p* h1,huff_code* h)int i=0;char codeN;r_find(h1,code,i,h);void output_huffman(huff

16、_code* head)huff_code* h=head-next;coutendl;cout标号:-概率- -编码-endl;cout-op_mask2=0;coutop_mask: p codenext;cout-endl;coutnext;double j=0;float one_length=0;float per_length=0;float ext_length=0;/按1-2-3-5扩展编码的最小长度为。while(h)float length=0;int i=0;while(h-codei!=0)length+;i+;one_length=h-p*length;per_len

17、gth=per_length+one_length; /12 h=h-next;j+;int i1=int(j);huff_code *p2=head-next;float* p_a=new floati1;int i0=0;while(p2)p_ai0+=p2-p;p2=p2-next;float max,temp;int l;for(int s=0;si1;s+)max=p_as;l=s;for(int k=s+1;ki1;k+)if(maxp_ak)max=p_ak;l=k;temp=p_as;p_as=max;p_al=temp;float* code_len=new floati1;

18、code_len0=1;code_len1=2;code_len2=3;code_len3=5;for(int i=4;ij;i+)code_leni=5;while(li1)ext_length=ext_length+code_lenl*p_al;double q_length=log10(j)/log10(2);cout此指令集操作码huffman编码的平均长度为per_lengthendl;cout等长编码的平均长度为q_lengthendl;cout按1-2-3-5的扩展编码的最短平均编码长度为ext_length;coutendl;coutendl;实验2#include#inclu

19、de#define M 4#define N 12#define Myprintf printf(|-+-+-+-+-+-+-+-+-+-+-+-|n)typedef struct page int num; /*记录页面号*/ int time; /*记录调入内存时间*/Page; /* 页面逻辑结构，结构为方便算法实现设计*/Page bM; /*内存单元数*/int cMN; /*暂保存内存当前的状态：缓冲区*/int queue100; /*记录调入队列*/int K; /*调入队列计数变量*/void Init(Page *b,int cMN) int i,j; for(i=0;iN;i+) bi.num=-1; bi.time=N-i-1; for(i=0;iM;i+) for(j=0;jN;j+) cij=-1;int GetMax(Page *b) int i; int max=-1; int tag=0; for(i=0;imax)