中南大学计算机体系结构实验报告.doc

《中南大学计算机体系结构实验报告.doc》由会员分享，可在线阅读，更多相关《中南大学计算机体系结构实验报告.doc（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、优质文本计算机体系结构实验报告 学 院：信息科学与工程学院 专业班级： 高赛文的小仙女 指导老师： 雷向东 姓 名： igot7 目 录实验 1 对指令操作码进行霍夫曼编码3一、实验目的3二、实验内容3三、实验过程4四、实验结果15实验 2 使用 LRU 方法更新 Cache16一、实验目的16二、 实验内容16 三、实验过程16四、实验结果19实验 3 通道处理过程模拟21一、实验目的21二、实验内容21三、实验过程22四、实验结果23实验 4 单功能流水线调度机构模拟24一、实验目的24二、实验内容24三、实验过程24四、 运行结果25实验总结25实验 1 对指令操作码进行霍夫曼编码一、实

2、验目的1 了解和掌握指令编码的根本要求和根本原理二、实验内容1.使用编程工具编写一个程序，对一组指令进行霍夫曼编码，并输出最后的编码结果以及对指令码的长度进行评价。与扩展操作码和等长编码进行比拟。 问题描述以及问题分析： 我们举例说明此问题，例如：有一组指令的操作码共分七类，它们出现概率如下表所示：P1P2P3P4P5P6P70.45 0.30 0.15 0.05 0.03 0.01 0.01对此组指令进行 HUFFMAN 编码正如下列图所示： 最后得到的 HUFFMAN 编码如下表所示：最短编码长度为： H=0.45*1+0.30*2+0.15*3+0.05*4+0.03*5+0.01*6+

3、0.01*6=-1.95. 要对指令的操作码进行 HUFFMAN 编码，只要根据指令的各类操作码的出现概率构造HUFFMAN 树再进行HUFFAM 编码。此过程的难点构造 HUFFMAN 树，进行 HUFFAM 编码只要对你所生成的 HUFFMAN 树进行中序遍历即可完成编码工作。三、实验过程 观察上图 1，不难看出构造 HUFFMAN 树所要做的工作：1、先对各指令操作码的出现概率进行排序，构造一个有序链表。2、再取出两个最小的概率节点相加，生成一个生的节点参加到链表中，同时从两表中删除此两个节点。3、在对链表进行排序，链表是否只有一个节点，是那么 HUFFAN 树构造完毕，否那么继续做 2

4、 的操作。 为此设计一个工作链表链表的元素时类，此类的功能相当结构。、HUFFMAN 树节点、HUFFMAN 编码表节点。 具体如下：/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; /指令使用概

5、率；huff_p* huf_p;/huff_man code pointclass 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_m

6、in_p* p);/在工作链表中删除最小概率节点函数。void insert_n(f_min_p* h,f_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_h

7、uffman(huff_code* head);/输出 huffman 编码;void cal_sort_length(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_

8、min_ppublic:f_min_p* next; char op_mask3; /指令标号；float 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

9、);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(huff_p* p1,char code,int i,huff_code* h);void output_huffman(huff_code* head);/输出 huffman 编码;void cal_sort_length

10、(huff_code* head);/计算指令用 huffman 编码的平均编码字长void main()f_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)

11、; 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=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;coutp

12、oint-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=del_min(h1,min1); if(h1-next) min2=fin_min(h1); else min2=h1; rd=creat_hu

13、ffp(min2); 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); 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(min

14、1-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);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)

15、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+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

16、=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;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)h

17、uff_p* p1;p1=newhuff_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_mask0=p1-op_mask0;p2-o

18、p_mask1=p1-op_mask1;p1-op_mask2=0;p2-p=p1-p;for(int 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=

19、head-next;coutOP:-概率- -编码-endl; cout-endl;while(h)优质文本cout-endl;coutnext; floatone_enatper_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; floa

20、t* p_a=new floati1;/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_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

21、;i+)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;el

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

23、，用来记录一个页面自上次被访问以来经历的时间 T，当须淘汰一个页面时，选择现有页面中 T 值最大的，即最近最久没有访问的页面。这是一个比拟合理的置换算法。 举例说明此问题，例如： 有一个 CACHE 采用组相连映象方式。每组有四块，为了实现 LRU 置换算法，在快表中为每块设置一个 2 位计数器。我们假设访问序列为“1,1,2,4,3,5,2,1,6,7,1,3。在访问 CACHE的过程中，块的装入，置换及命中时，具体情况如下表所示：三、实验过程此程序中最重要的算法当然是 LRU 置换算法，：/ cache 更新算法,LRUvoid up_cache() int i=0; while(in)

24、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; int kk=0; for (x=0;xm;x+) coutcache 块x: cachex.valueendl; coutendl; /更新其它 cache 块没使用时间 while(kkm) if(kk!=

25、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+; cachej.count=0; /更新其它 cache 块没使用时间 while(kkm) if(kk!=j&cachekk.value!=(-1) cachekk.count+; kk+; j+; if(j=m) c

26、outcache 已经满了,考虑是否置换.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; /更新其它 cache 块没使用时间 while(kkm) if(kk!=k) cachekk.count+; kk+; break; k+; if(k=m)/考虑置换那一块. int ii=0; int t=

27、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;x+) coutcache 块x: cachex.valueendl; int kk=0; /更新其它 cache 块没使用时间 while(kkm) if(kk!=t) cachekk.count+; kk+;

28、 delay(); 四、实验结果 由实验结果可得，四个cache块的更新情况在与问题描述中所举的例子中的序列号一样的情况下页面的更新情况也一样的。程序是正确的。优质文本实验 3 通道处理过程模拟一、实验目的通过模拟实现通道处理过程，掌握通道技术。二、实验内容结合数据结构的相关知识,编写通道处理过程模拟程序。1通道完成一次数据输入输出的过程需三步如图一所示：(1)在用户程序中使用访管指令进入管理程序，由CPU通过管理程序组织一个通道程序，并启动通道。(2)通道处理机执行通道程序，完成指定的数据输入输出工作；(3)通道程序结束后第二次调用管理程序对输入输出请求进行处理每完成一次输入输出工作，CPU

29、 只需要两次调用管理程序，大大减少了对用户程序的打搅。 2通道的主要功能如图二所示：1接受 CPU 发来的指令，选择一台指定的外围设备与通道相连接2执行 CPU 为通道组织的通道程序3管理外围设备的有关地址4管理主存缓冲区的地址5控制外围设备与主存缓冲区间数据交换的个数6指定传送工作结束时要进行的操作7检查外围设备的工作状态，是正常或故障8在数据传输过程中完成必要的格式的变换三、实验过程 1传输方式为内存到设备,采用字节多路方式,设备分时复用通道的工作算法。void memoryToDevice(char* mem) char* memory;memory =mem;for(int fence

30、 = 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 = NONE) coutThe cpu is doing some thing.endl;coutThe cpu is doing some thing.end

31、l;break; if(channalManager.interrupt = INIT) coutCPU is interruptedendl; break;优质文本优质文本if(channalManager.interrupt = FINISH)coutCPU is interruptedendl;coutThis is a I/0 Finish instruction,The channalManager is close thedevice.endl;break; 四、实验结果a.初始化内存块中需要传输的数据: char* memory3;memory0 = love;memory1 =

32、 channel;memory2 = architecture; b.设备中的内容为空： c字节多路通道程序分时为不同的设备效劳： d通道程序执行完毕，CPU 中断后关闭设备，继续执行用户程序。实验 4 单功能流水线调度机构模拟一、实验目的 结合数据结构的相关知识,编写流水线调度模拟程序二、实验内容 通过模拟单功能流水线调度过程，掌握流水线技术，学会计算流水线的吞吐率、加速比、效率。 1流水线的表示法有三种： 连接图、时空图、预约表。对于线性流水线，主要考虑前二种。 2流水线的主要特点： 在流水线的每一个功能部件的后面都要有一个缓冲器，称为锁存器、闸门存放器等，它的作用是保存本流水段的执行结果

33、。各流水段的时间应尽量相等，否那么回引起阻塞、断流等。只有连续提供同类任务才能充分发挥流水线的效率。在流水线的每一个流水线段中都要设置一个流水锁存器。流水线需要有“装入时间和“排空时间。只有流水线完全充满时，整个流水线的效率才能得到充分发挥。三、实验过程1存储时空图的数据结构及相关变量。# define SPACE 4 /*功能部件数目*/# define TIME INUM+(SPACE-1) /*存储不同时间段各个功能部件内指令值*/# define INUM 5 /*需要流水处理的浮点加指令数目*/int tsSPACETIME = 0;/*初始化时空图*/ int time = 1;/*记录运行时候时间周期*/2流水线中各条指令状态转换的算法实现。void pipeline(int tsSPACETIME)优质文本 int 记录处理的指令号*/int tempTime=0;/*记录时间轴的变化*/for(int s=SPAC