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

《计算机系统体系结构实验指导书》由会员分享，可在线阅读，更多相关《计算机系统体系结构实验指导书（23页珍藏版）》请在装配图网上搜索。

1、计算机系统（体系）结构实验指导书1. 上机实验要求及规范计算机体系结构是计算机专业学生的一门专业课程，本课程是计算机专业一门重要的专业课，着重讲述计算机系统的软、硬件界面。对于学生从事计算机系统的研制、使用和维护有重要意义。本课程概念多、内容涉及面广、系统性强。通过本课程的学习，学生应能从软件、硬件功能分配的角度去了解、分析和研究计算机系统，建立起对计算机系统的全面认识，树立全面地、发展地看问题的观点，从而加深对各种类型体系结构的了解，牢固地树立起整机系统的概念。本课程的学习应注重理论与实践相结合，因此实验教学是教学环节中必不可少的重要内容。通过实验教学的学习，使学生熟练掌握有关计算机体系结构

2、的基本概念、基本原理和基本思想，掌握对计算机体系结构和组成进行分析和计算的方法。实验部分包括四个实验，包括有完整的源程序例题，介绍了一些设计数据结构题目所需的的知识和技巧。在实验题中，既有简单容易的验证题，即验证已经给出的源程序，或者扩充已经给出的源程序，也有需独立思考设计的综合实验题。计算机体系结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性。但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的

3、能力。拿到一个题目，一般不要急于编程。按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），正确的方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。一、实验报告的基本要求：一般性、较小规模的上机实验题，必须遵循下列要求。养成良好的习惯。姓名 班级 学号 日期 题目i.问题描述ii.设计简要描述iii.程序清单（带有必要的注释）iv.结果分析（原始图示，测试数据与运行记录，分析正确性；）v.调试报告：实验者必须重视最后这两个环节，否则等同于没有完成实验任务。这里可以体现个人特色、或创造性思维。具体内容包括：测试数

4、据与运行记录；调试中遇到的主要问题，自己是如何解决的；经验和体会等。二、实验习报告的提高要求：阶段性、较大规模的上机实验题，应该遵循下列要求。养成科学的习惯。（1）问题描述（2）需求和规格说明（3）描述问题，简述题目要解决的问题是什么。规定软件做什么。原题条件不足时补全。（4）概要设计：功能模块的划分,ADT（5）详细设计：每部分模块的设计，含数据结构的设计，算法的描述（流程图或PDL） a.设计思想：存储结构（题目中限定的要描述）；主要算法基本思想。b.设计表示：每个函数的头和规格说明；列出每个函数所调用和被调用的函数，也可以通过调用关系图表达。（6）实现注释：各项功能的实现程度、在完成基本

5、要求的基础上还有什么功能。（7）用户手册：即使用说明书。（8）调试报告：调试过程中遇到的主要问题是如何解决的；设计的回顾、讨论和分析；时间复杂度、空间复杂度分析；改进设想；经验和体会等。23实验 1 对指令操作码进行霍夫曼编码一、实验目的1 了解和掌握指令编码的基本要求和基本原理二、实验内容1.使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。与扩展操作码和等长编码进行比较。问题描述以及问题分析：我们举例说明此问题，例如：有一组指令的操作码共分七类，它们出现概率如下表所示：P1P2P3P4P5P6P70.45 0.30 0.15 0.05 0.

6、03 0.01 0.01对此组指令进行 HUFFMAN 编码正如下图所示：0.45 0.30 0.150.050.030.010.01 0 1 0.02 0 1 0.05 0 1 0.10 0 1 0.25 0 1 0.55 0 1 1.00 图 1 最后得到的 HUFFMAN 编码如下表所示：P1P2P3P4P5P6P70 10 1101110111101111101111111234566最短编码长度为： 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 编码，只要根据指令的各类操作码的出

7、现概率构造HUFFMAN 树再进行 HUFFAM 编码。此过程的难点构造 HUFFMAN 树，进行 HUFFAM 编码只要对你所生成的 HUFFMAN 树进行中序遍历即可完成编码工作。三、实例观察上图 1，不难看出构造 HUFFMAN 树所要做的工作：1、先对各指令操作码的出现概率进行排序，构造一个有序链表。2、再取出两个最小的概率节点相加，生成一个生的节点加入到链表中，同时从两表中删除此两个节点。3、在对链表进行排序，链表是否只有一个节点，是则 HUFFAN 树构造完毕，否则继续做 2 的操作。为此设计一个工作链表（链表的元素时类，此类的功能相当结构。）、HUFFMAN 树节点、HUFFMA

8、N 编码表节点。具体如下：/huff_man tree point;class huff_p public: huff_p* r_child; /大概率的节点,即右子节点； huff_p* l_child; /小概率的节点,即左子节点； char op_mask3; /指令标号； float p; /指令使用概率；;/work link pointclass f_min_ppublic:f_min_p* next; char op_mask3; /指令标号；float p; /指令使用概率；huff_p* huf_p;/huff_man code pointclass huff_codepub

9、lic:huff_code*next;float p;char op_mask3; char codeN; /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);/在工作链表中删除最小概率节点函数。void insert_n(f_min_p* h,f_

10、min_p* p);/ 在工作链表中插入两个最小概率节点生成的节点函数。huff_p* creat_huffp(f_min_p* p);/生成 HUFFMAN 节点。void creat_huffman_code(huff_p* h1,huff_code* h);/生成 huffman 编码;void r_find(huff_p* p1,char code,int i,huff_code* h);/遍历 HUFFMAN 树生成指令操作码的 HUFFMAN 编码。void output_huffman(huff_code* head);/输出 huffman 编码;void cal_sort_l

11、ength(huff_code* head);/计算指令用 huffman 编码的平均编码字长程序清单及注释：#include#include #define N 8/find two min program;/huff_man tree pont;class huff_p public: 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

12、p; /指令使用概率；huff_p* huf_p;/huff_man codeclass huff_codepublic:huff_code*next;float p;char op_mask3; char codeN; /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);void insert_

13、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(huff_p* p1,char code,int i,huff_code* h);void output_huffman(huff_code* head);/输出 huffman 编码;void cal_sort_length(huff_code* head);/计算指令用 huffman 编码的平均编码字长void main()f

14、_min_p *h,*h1; huff_p *root;huff_code*head,*pl;inth=input_instruct_set();/*p1=h;while(p1)coutpnext;*/ h1=h; root=creat_huffman_tree(h1); head=new huff_code;head-next=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

15、;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; int n; coutn;couth-op_mask;couth-p;intf_min_p* point;f_min_p* p1=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

16、;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=del_min(h1,min1); if(h1-next) min2=fin_min(h1); else min2=h1; rd=creat_huffp(min2); comb=new f_min_p; comb-next=NULL; comb-p=rd-p

17、+ld-p; comb-op_mask0=0; comb-op_mask1=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; int i=0; coutinext!=NULL) min1=fin_min(h1); if(min1-huf_p=NULL) ld=creat_huffp(min1); else ld=min1-huf_p;

18、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=new f_min_p; comb-next=NULL; comb-p=rd-p+ld-p; comb-op_mask0=0; comb-op_mask1=0; parent=creat_huffp(comb); if(h1!=NULL)insert_n(h1,comb); if(h1-next!=NULL)h1=del_min(h1,m

19、in2);parent-l_child=ld;parent-r_child=rd; comb-huf_p=parent;head=parent; cout+inext=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(min(h1-p) min=h1-p;p1=h1; h1=h1-next; return p1; f_min_p* del_min( f_min_p *h,f

20、_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;deletebreak; p2=p1; return h; void insert_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=N

21、ULL;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_mask0=p1-op_mask0;p2-op_mask1=p1-op_mask1;p1-op_mask2=0;p2-p=p1-p;for(int

22、 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); deletevoid creat_huffman_code(huff_p* h1,huff_code* h)intchar codeN; r_find(h1,code,i,h);void output_huffman(huff_code* head)huff_code* h=head-next;coutOP:-概率- -编码-endl; cout-op_mask2=0;cou

23、top_mask:p codenext;cout-endl;coutnext; double j=0;floatone_length=0;floatper_length=0;floatext_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_length=per_length+one_length;h=h-next;j+;int huff_code *p2=head-next; float* p_a=new fl

24、oati1;/sort 指令概率intwhile(p2)p_ai0+=p2-p;p2=p2-next;floatmax,temp;l;int 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;/计算 1-2-3-5 扩展编码的最短平均长度 float* code_len=new floati1;code_len0=1;code_len1=2;code_len2=3;code_len3=5;for(int i=4;ij;i+)

25、code_leni=5; l=0; while(li1)ext_length=ext_length+code_lenl*p_al;l+; /计算等长编码平均长度； double q_length=log10(j)/log10(2); cout此指令集操作码 huffman 编码的平均长度为：per_lengthendl; cout等长编码的平均长度为：q_lengthendl;cout按 1-2-3-5 的扩展编码的最短平均编码长度为：ext_length;coutendl;coutper_length)cout可见 HUFFMAN 编码的平均长度要比等长编码的平均长度短endl;elseco

26、uthuffman 编码有问题请仔细查看算法，以及输入的指令集的概率之和是否大于 1。per_length)cout可见 HUFFMAN 编码的平均长度要比 1-2-3-5 扩展编码的最短平均长度短endl;elsecouthuffman 编码有问题请仔细查看算法，以及输入的指令集的概率之和是否大于 1。endl;实验 2 使用 LRU 方法更新 Cache一、实验目的了解和掌握寄存器分配和内存分配的有关技术。二、实验内容程序 1Cache 更新结合数据结构的相关知识，使用LRU的策略，对一组访问序列进行内部的LRU置换算法是选择最近最久未使用的页面予以置换。该算法赋予每个页面一个访问字段，用

27、来记录一个页面自上次被访问以来经历的时间 T，当须淘汰一个页面时，选择现有页面中 T 值最大的，即最近最久没有访问的页面。这是一个比较合理的置换算法。举例说明此问题，例如：有一个 CACHE 采用组相连映象方式。每组有四块，为了实现 LRU 置换算法，在快表中为每块设置一个 2 位计数器。我们假设访问序列为“1,1,2,4,3,5,2,1,6,7,1,3”。在访问 CACHE的过程中，块的装入，置换及命中时，具体情况如下表所示：1Cache 块 01Cache 块 1Cache 块 2Cache 块 31121241243124355243252431521365216772161721637

28、316装入三、实例命中装入装入装入置换命中置换置换置换命中置换此程序中最重要的算法当然是 LRU 置换算法，：/ cache 更新算法,LRUvoid up_cache() int i=0; while(in) int j=0; /满么? while(jm) if(cachej.state=false)&(walk_sorti!=cachej.value) coutcache 有空闲块,不考虑是否要置换.endl; coutwalk_sorti被调入 cache.endl; cachej.value=walk_sorti+; cachej.state=true; cachej.count=0;

29、 int kk=0; for (x=0;xm;x+) coutcache 块x: cachex.valueendl; coutendl; /更新其它 cache 块没使用时间 while(kkm) if(kk!=j&cachekk.value!=(-1) cachekk.count+; kk+; delay(); break; if(cachej.value=walk_sorti) coutendl; coutwalk_sorti命中!endl;for (x=0;xm;x+) coutcache 块x: cachex.valueendl; coutendl; int kk=0; i+; cac

30、hej.count=0; /更新其它 cache 块没使用时间 while(kkm) if(kk!=j&cachekk.value!=(-1) cachekk.count+; kk+; j+; if(j=m) coutcache 已经满了,考虑是否置换.endl; coutendl; int k=0; while(km) if(cachek.value=walk_sorti) coutendl; coutwalk_sorti命中!endl; for (x=0;xm;x+) coutcache 块x: cachex.valueendl; i+; cachek.count=0; int kk=0;

31、 /更新其它 cache 块没使用时间 while(kkm) if(kk!=k) cachekk.count+; kk+; break; k+; if(k=m)/考虑置换那一块. int ii=0; int t=0;/要替换的 cache 块号. int max=cacheii.count; ii+; while(iimax) max=cacheii.count; t=ii; ii+; /置换 coutcachet.value被walk_sorti在 cache 的t号块置换.endl; cachet.value=walk_sorti+; cachet.count=0; for (x=0;xm

32、;x+) coutcache 块x: cachex.valueendl; int kk=0; /更新其它 cache 块没使用时间 while(kkm) if(kk!=t) cachekk.count+; kk+; delay(); 一、实验目的实验 3 通道处理过程模拟通过模拟实现通道处理过程，掌握通道技术。二、实验内容程序 1结合数据结构的相关知识,编写通道处理过程模拟程序。1通道完成一次数据输入输出的过程需三步（如图一所示）：(1)在用户程序中使用访管指令进入管理程序，由CPU通过管理程序组织一个通道程序，并启动通道；(2)通道处理机执行通道程序，完成指定的数据输入输出工作；(3)通道程

33、序结束后第二次调用管理程序对输入输出请求进行处理每完成一次输入输出工作，CPU 只需要两次调用管理程序，大大减少了对用户程序的打扰。图一通道程序，管理程序和用户程序的执行时间关系2通道的主要功能（如图二所示）：（1）接受 CPU 发来的指令，选择一台指定的外围设备与通道相连接（2）执行 CPU 为通道组织的通道程序（3）管理外围设备的有关地址（4）管理主存缓冲区的地址（5）控制外围设备与主存缓冲区间数据交换的个数（6）指定传送工作结束时要进行的操作（7）检查外围设备的工作状态，是正常或故障（8）在数据传输过程中完成必要的格式的变换二、实例 1传输方式为内存到设备,采用字节多路方式,设备分时复用

34、通道的工作算法。void memoryToDevice(char* mem) char* memory;memory =mem;for(int fence = 0 ;fence MaxDevCap; fence+)for(int i = 0;i actDeviceNum ; i+) if(fence devicei.actCap) devicei.datafence = memoryifence; printDevice(); printDevice();2.CPU 处理不同的中断的算法。void run()while(true) if(channalManager.interrupt = N

35、ONE) coutThe cpu is doing some thing.endl;coutThe cpu is doing some thing.endl;break; if(channalManager.interrupt = INIT) coutCPU is interruptedendl;device.endl; coutThis is a I/0 Initbreak; instruction,The channalManager is init theif(channalManager.interrupt = FINISH)coutCPU is interruptedendl;coutThis is a I/0 Finish instruction,The channalManager is close thedevice.=0;s-)tempSpace=1;for(int t=tempTime;tTIME;t+)tsst=tempSpace+;tempTime+;测试数据及运行结果本实验选取四段单功能流水线浮点加作为测试的例子。选取 5 条指令作为测试任务，并计算流水线的吞吐率、加速比和效率。程序初始化后界面如下：ED：求阶差 EA：对阶MA：尾数加 NL：规格化程序执行完毕后的运行界面如下：