計算機體系結(jié)構(gòu)實驗報告

1、計算機體系結(jié)構(gòu)中南大學(xué)計算機體系結(jié)構(gòu)實驗報告學(xué)生姓名 學(xué) 院 信息科學(xué)與工程學(xué)院 專業(yè)班級 完成時間 2015年10月27日 目 錄1.實驗內(nèi)容22.實驗1：對指令操作碼進(jìn)行霍夫曼編碼32.1 實驗?zāi)康?2.2 實驗內(nèi)容32.3 實驗結(jié)果33.實驗2 ：使用 LRU 方法更新 Cache33.1 實驗?zāi)康?3.2 實驗內(nèi)容43.3 實驗結(jié)果44. 總結(jié)45. 代碼附錄5計算機體系結(jié)構(gòu)1.實驗內(nèi)容實驗 1 對指令操作碼進(jìn)行霍夫曼編碼實驗 2 使用 LRU 方法更新 Cache2.實驗1：對指令操作碼進(jìn)行霍夫曼編碼 2.1 實驗?zāi)康牧私夂驼莆罩噶罹幋a的基本要求和基本原理2.2 實驗內(nèi)容 使用編程工

2、具編寫一個程序，對一組指令進(jìn)行霍夫曼編碼，并輸出最后的編碼結(jié)果以及對指令碼的長度進(jìn)行評價。與擴(kuò)展操作碼和等長編碼進(jìn)行比較。要對指令的操作碼進(jìn)行 HUFFMAN 編碼，只要根據(jù)指令的各類操作碼的出現(xiàn)概率構(gòu)造HUFFMAN 樹再進(jìn)行 HUFFAM 編碼。此過程的難點構(gòu)造 HUFFMAN 樹，進(jìn)行 HUFFAM編碼只要對你所生成的 HUFFMAN 樹進(jìn)行中序遍歷即可完成編碼工作。2.3 實驗結(jié)果 3.實驗2 ：使用 LRU 方法更新 Cache3.1 實驗?zāi)康?了解和掌握寄存器分配和內(nèi)存分配的有關(guān)技術(shù)。3.2 實驗內(nèi)容Cache 更新：結(jié)合數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識，使用LRU的策略，對一組訪問序列進(jìn)行內(nèi)部

3、的LRU置換算法是選擇最近最久未使用的頁面予以置換。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來經(jīng)歷的時間 T，當(dāng)須淘汰一個頁面時，選擇現(xiàn)有頁面中 T 值最大的，即最近最久沒有訪問的頁面。這是一個比較合理的置換算法。3.3 實驗結(jié)果4. 總結(jié) 實驗一是曾在學(xué)習(xí)數(shù)字通信原理課程時編寫的，當(dāng)時只有簡單的排序后編碼的功能，學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)后，我往里面加入了樹的結(jié)構(gòu)，使編碼后的結(jié)果更加清晰明了了。學(xué)習(xí)了計算機體系結(jié)構(gòu)之后，我又往里面加入了求編碼長度的功能。通過這個程序，我更加了解哈夫曼編碼的知識了。實驗二是寫出LRU算法，這個相對來說比較簡單，因為在學(xué)習(xí)操作系統(tǒng)原理時接觸過FIFO等

4、等算法并且編程實現(xiàn)了，難點在于輸出結(jié)果的排版，一開始我想輸出一個表格，這樣更符合書上關(guān)于此算法的內(nèi)容，但是出現(xiàn)了各種不對齊的問題，最后只好讓它直接輸出結(jié)果。 通過這幾次實驗，我發(fā)現(xiàn)了自身的不足，比如沒有很好的書寫習(xí)慣，考慮問題不周到，對于計算機體系結(jié)構(gòu)課程中知識的理解不夠深入等。但在編程的過程中我體驗到了一分耕耘一分收獲的喜悅；多次調(diào)試后程序成功運行了，那時候的歡樂是我以前無法想象的。果然，學(xué)習(xí)任何一門課程，只要學(xué)得用心，都可以從中體會到學(xué)習(xí)的快樂。今后我的進(jìn)步，想必都是從這一點一點敲入編譯器的代碼中獲得的。5. 代碼附錄實驗1#include#includeusing namespace s

5、td;#define N 8class huff_ppublic:huff_p* r_child; /大概率的節(jié)點；huff_p* l_child; /小概率的節(jié)點；char op_mask3; /指令標(biāo)號；float p; /指令使用概率；;class f_min_ppublic:f_min_p* next;char op_mask3; /指令標(biāo)號；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);/構(gòu)造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標(biāo)號:-概率- -編碼-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擴(kuò)展編碼的最小長度為。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的擴(kuò)展編碼的最短平均編碼長度為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; /*記錄調(diào)入內(nèi)存時間*/Page; /* 頁面邏輯結(jié)構(gòu)，結(jié)構(gòu)為方便算法實現(xiàn)設(shè)計*/Page bM; /*內(nèi)存單元數(shù)*/int cMN; /*暫保存內(nèi)存當(dāng)前的狀態(tài)：緩沖區(qū)*/int queue100; /*記錄調(diào)入隊列*/int K; /*調(diào)入隊列計數(shù)變量*/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)