2014计算机系统(体系)结构实验指导书

1计算机系统（体系）结构实验指导书1.上机实验要求及规范计算机体系结构是计算机专业学生的一门专业课程，本课程是计算机专业一门重要的专业课，着重讲述计算机系统的软、硬件界面。对于学生从事计算机系统的研制、使用和维护有重要意义。本课程概念多、内容涉及面广、系统性强。通过本课程的学习，学生应能从软件、硬件功能分配的角度去了解、分析和研究计算机系统，建立起对计算机系统的全面认识，树立全面地、发展地看问题的观点，从而加深对各种类型体系结构的了解，牢固地树立起整机系统的概念。本课程的学习应注重理论与实践相结合，因此实验教学是教学环节中必不可少的重要内容。通过实验教学的学习，使学生熟练掌握有关计算机体系结构的基本概念、基本原理和基本思想，掌握对计算机体系结构和组成进行分析和计算的方法。实验部分包括四个实验，包括有完整的源程序例题，介绍了一些设计数据结构题目所需的的知识和技巧。在实验题中，既有简单容易的验证题，即验证已经给出的源程序，或者扩充已经给出的源程序，也有需独立思考设计的综合实验题。计算机体系结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性。但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程。按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），正确的方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。一、实验报告的基本要求：一般性、较小规模的上机实验题，必须遵循下列要求。养成良好的习惯。姓名班级学号日期题目i.问题描述ii.设计简要描述iii.程序清单（带有必要的注释）iv.结果分析（原始图示，测试数据与运行记录，分析正确性；）v.调试报告：实验者必须重视最后这两个环节，否则等同于没有完成实验任务。这里可以体现个人特色、或创造性思维。具体内容包括：测试数据与运行记录；调试中遇到的主要问题，自己是如何解决的；经验和体会等。2二、实验习报告的提高要求：阶段性、较大规模的上机实验题，应该遵循下列要求。养成科学的习惯。（1）问题描述（2）需求和规格说明（3）描述问题，简述题目要解决的问题是什么。规定软件做什么。原题条件不足时补全。（4）概要设计：功能模块的划分,ADT（5）详细设计：每部分模块的设计，含数据结构的设计，算法的描述（流程图或PDL）a.设计思想：存储结构（题目中限定的要描述）；主要算法基本思想。b.设计表示：每个函数的头和规格说明；列出每个函数所调用和被调用的函数，也可以通过调用关系图表达。（6）实现注释：各项功能的实现程度、在完成基本要求的基础上还有什么功能。（7）用户手册：即使用说明书。（8）调试报告：调试过程中遇到的主要问题是如何解决的；设计的回顾、讨论和分析；时间复杂度、空间复杂度分析；改进设想；经验和体会等。3实验1对指令操作码进行霍夫曼编码一、实验目的1．了解和掌握指令编码的基本要求和基本原理二、实验内容1.使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。与扩展操作码和等长编码进行比较。问题描述以及问题分析：我们举例说明此问题，例如：有一组指令的操作码共分七类，它们出现概率如下表所示：P1P2P3P4P5P6P70.450.300.150.050.030.010.01对此组指令进行HUFFMAN编码正如下图所示：0.450.300.150.050.030.010.01010.0201`0.05010.10010.25010.55011.00图1最后得到的HUFFMAN编码如下表所示：P1P2P3P4P5P6P70101101110111101111101111111234566最短编码长度为：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树进行中序遍历即可完成编码工作。4三、实例观察上图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;//指令使用概率；};//worklinkpointclassf_min_p{public:f_min_p*next;charop_mask[3];//指令标号；floatp;//指令使用概率；huff_p*huf_p;};/huff_mancodepointclasshuff_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节点。5voidcreat_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编码的平均编码字长程序清单及注释：#includeiostream.h#includemath.h#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_mancodeclasshuff_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);6huff_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;inth=input_instruct_set();/*p1=h;while(p1){coutp1-p',';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;7f_min_p*h;h=newf_min_p;h-next=NULL;h-huf_p=NULL;head=h;intn;cout请输入指令数:;cinn;cout请输入指令标号：;cinh-op_mask;cout请输入指令的使用概率：;cinh-p;intf_min_p*point;f_min_p*p1=head;for(;in-1;i++){point=newf_min_p;cout请输入指令标号：;cinpoint-op_mask;point-op_mask[2]='\0';cout请输入指令的使用概率：;cinpoint-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)8min2=fin_min(h1);elsemin2=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;coutie