如何編程模擬計(jì)算機(jī)中的高速緩存

1. 實(shí)驗(yàn)要求

2. 編程

2.1 讀取文件

2.2 高速緩存定義結(jié)構(gòu)體

2.3 初始化Cache

2.4 解析輸入的指令

2.5 LRU策略

2.6 更新高速緩存Cache

2.7 完整代碼

3. 測(cè)試結(jié)果

1. 實(shí)驗(yàn)要求

??1.編程模擬Cahce的命中，不命中，替換等行為。

??2.編寫的程序必須對(duì)任意s，E和b正確工作。

??3.本實(shí)驗(yàn)不涉及真實(shí)的數(shù)據(jù)讀寫，不需要考慮block的細(xì)節(jié)，每行只有一個(gè)block。

??4.編寫的程序要能讀取指定文件內(nèi)的指令，根據(jù)不同的指令完成不同的動(dòng)作，下面為指令內(nèi)容示例。

?

I?0400d7d4,8??????#
M?0421c7f0,4??????#?修改access cache，?即讀寫access cache兩次，0421c7f0：修改的地址，8：修改的長(zhǎng)度
L?04f6b868,8??????#?讀access cache，04f6b868：讀取的地址，8：讀取長(zhǎng)度
S?7ff0005c8,8?????#?寫access cache，0421c7f0：寫的地址，8：寫的長(zhǎng)度

?

2. 編程

??考慮模擬一個(gè)Cache的行為需要用到哪些變量？

計(jì)算機(jī)中的高速緩存模型

??Cache有組數(shù)S、一組包含的行數(shù)E，存儲(chǔ)塊的字節(jié)大小B，Cache的容量C=S×E×B。

??地址的構(gòu)成：標(biāo)識(shí)位t、組索引s、塊偏移b（前面說(shuō)了，不需要管塊偏移）。

??下面我們開(kāi)始編寫代碼。

2.1 讀取文件

??getopt()該函數(shù)能夠幫助程序分析C語(yǔ)言命令行程序輸入的參數(shù)。

?

int?getopt(int?argc,char?*?const?argv[?],const?char?*?optstring);

?

??重點(diǎn)說(shuō)下getopt()函數(shù)。前兩個(gè)形參是main函數(shù)傳入的參數(shù)，即我們輸入的命令行，第三個(gè)形參是 optstring“選項(xiàng)字符串”，即標(biāo)識(shí)哪些字母表示了操作。

??如"acd::e"，字母后帶一個(gè)冒號(hào)（例中的a、b）表明這個(gè)操作帶參數(shù)，字母后的內(nèi)容需要讀取，存放到它內(nèi)部變量 extern char * optarg中。

??字母不帶冒號(hào)（例中的c、e）表明該操作不帶參數(shù)，后面輸入的內(nèi)容仍看作操作符處理。字母后帶兩個(gè)冒號(hào)（例中的d）表明該操作后參數(shù)是可選的，但是要求如果帶參數(shù)時(shí)參數(shù)與操作符不能有空格，如-d123是對(duì)的，而-d 123會(huì)報(bào)錯(cuò)。當(dāng)讀取了全部的輸入的命令后 getopt（）返回-1。

?

while((opt?=?getopt(argc,argv,"sb"))?!=-1){???????????//解析命令行參數(shù)
??switch(opt){
??case?'s':
???s=atoi(optarg);
???break;
??case?'E':
???E=atoi(optarg);
???break;
??case?'b':
???b=atoi(optarg);
???break;
??case?'t':
???filepath?=?optarg;
???break;
??}
?}

?

?? fscanf函數(shù)，該函數(shù)能夠幫助用戶處理文本文件中輸入的格式化數(shù)據(jù)。

?

int?fscanf(FILE?*stream,?char?*format[,argument...]);

?

??stream-這是指向 FILE 對(duì)象的指針，該 FILE 對(duì)象標(biāo)識(shí)了流。

??format-這是 C 字符串，包含了以下各項(xiàng)中的一個(gè)或多個(gè)：空格字符、非空格字符和format 說(shuō)明符。

2.2 高速緩存定義結(jié)構(gòu)體

??實(shí)驗(yàn)要求中說(shuō)明了，不需要處理b，只需認(rèn)為每行中有一個(gè)block。因此cache_line結(jié)構(gòu)體中包括有效位，標(biāo)記位，時(shí)間戳三個(gè)變量就夠了。stamp記錄的是block 的使用時(shí)間，每被使用一次，block++。因此，stamp越大表明該block越是最近被使用。具體代碼如下。

?

typedef?struct{
?int?valid_bits;
?unsigned??tag;
?int?stamp;
}cache_line;

?

2.3 初始化Cache

??定義一個(gè)Cache[S] [E]大小的二維數(shù)組。這樣Cache就模擬好了。

?

void?init(){
?cache?=?(cache_line**)malloc(sizeof(cache_line*)*S);?????????????//malloc開(kāi)辟空間
?for(int?i=0;i

	?

	2.4 解析輸入的指令

	??先分析每個(gè)輸入的指令應(yīng)該被如何操作。如果是I，則不是數(shù)據(jù)操作，直接忽略。如果是L或者S，則需要進(jìn)行一次hit-miss-eviction檢測(cè)，如果是M，則相當(dāng)于先L再S，需要進(jìn)行兩次hit-miss-eviction檢測(cè)。然后考慮hit-miss- eviction檢測(cè)細(xì)節(jié)。

	?
?while(fscanf(file,"?%c?%x,%d",&operation,&address,&size)>0){
??switch(operation){
???case?'L':
????update(address);
????break;
???case?'M':
????update(address);
???case?'S':
????update(address);
????break;
??}
??time();
?}


	?

	??首先需要對(duì)讀取的地進(jìn)有分析，低b位表示 block偏移，本實(shí)驗(yàn)中不需要計(jì)算block偏移。中間s位是 set index位，表示對(duì)那個(gè)行操作。其余t位是tag位。用于標(biāo)明對(duì)應(yīng)的line是否有效。我們需要對(duì)得到的地址進(jìn)行如下操作，解析出t和s。

	?
?unsigned?s_address?=(address>>b)?&?((0xffffffff)>>(32-s));????????????????//索引位
?unsigned?t_address?=?address>>(s+b);?????????????????????????????????????//標(biāo)記位


	?

	2.5 LRU策略

	??替換策略使用的是LRU的緩存替換策略。如果該set存滿了，我每次要找到stamp最小的替換。為了方便，我把stamp初始化為0，之后每個(gè)操作+1. 當(dāng)stamp= 0的時(shí)候就代表不valid。

	?
void?time(){
?for(int?i=0;i?max_stamp){
???max_stamp?=?cache[s_address][i].stamp;
???max_i?=?i;
??}
?}


	?

	2.6 更新高速緩存Cache

	??Cache的容量有限，當(dāng)滿的時(shí)候需要替換行，先遍歷當(dāng)前組，判斷它滿了沒(méi)有，如何判斷是否滿，可以遍歷所有的行，只要有一個(gè)有效位為0，（有效位的作用是說(shuō)明該行是否存儲(chǔ)了數(shù)據(jù)，通俗的理解就是是否為空）則該組未滿。

	?
for(int?i=0;i

	?

	2.7 完整代碼

	?
/*
?*?@Description:?編程模擬Cache
?*?@Version:?V1.0
?*?@Autor:?嵌入式與Linux那些事
?*?@Date:?2021-1-1?2012
?*?@LastEditors:?嵌入式與Linux那些事
?*?@LastEditTime:?2021-1-1?2258
?*/
#include?"cachelab.h"
#include?
#include?
#include?
#include?
#include?
typedef?struct{
?int?valid_bits;
?unsigned??tag;
?int?stamp;
}cache_line;
char*?filepath?=?NULL;
int?s,E,b,S;??????????????????????????//?s?表示組?,E表示行,每一行有?2^b位?,S?=?2^s?組
int?hit=0,miss=0,eviction=0;
cache_line**?cache?=?NULL;

void?init(){
?cache?=?(cache_line**)malloc(sizeof(cache_line*)*S);?????????????//malloc開(kāi)辟空間
?for(int?i=0;i>b)?&?((0xffffffff)>>(32-s));???????????//從地址分解出索引位
?unsigned?t_address?=?address>>(s+b);?????????????????????????????????//從地址分解出標(biāo)記位
?//判斷tag為是否相等，是否命中
????for(int?i=0;itag?==t_address){
???cache[s_address][i].stamp?=?0;???????//被使用了
???hit++;
???return;
??}
?}
????//更新高速緩存cache
?for(int?i=0;i?max_stamp){
???max_stamp?=?cache[s_address][i].stamp;
???max_i?=?i;
??}
?}
?eviction++;
?miss++;
?cache[s_address][max_i].tag?=?t_address;
?cache[s_address][max_i].stamp?=?0;?
}
//更新stamp
void?time(){
?for(int?i=0;i0){
??switch(operation){
???case?'L':
????update(address);
????break;
???case?'M':
????update(address);
???case?'S':
????update(address);
????break;
??}
??time();
?}
?for(int?i=0;i

	?

	3. 測(cè)試結(jié)果

	HNU的自動(dòng)評(píng)分系統(tǒng)會(huì)測(cè)試我們編寫的代碼是否可以通過(guò)所有的測(cè)試用例，和Reference simulator的對(duì)比表明，結(jié)果完全相同。測(cè)試通過(guò)！

	image-20201231160527635

	?

	?

	　　審核編輯：湯梓紅

	?