• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

CSAPP实验四——cache lab实验(一)

互联网 diligentman 1周前 (02-19) 8次浏览

在学完《深入理解计算机系统(CSAPP)》第六章有关存储器层次结构方面的知识后,就可以着手做cache lab的实验了。实验分为两个部分,这篇博客只聊聊自己在做第一部分的一点心得。思路部分也是参考了网上其他大神的想法,如果有写的不对的地方,欢迎大家在评论区指出。

cache lab的第一个实验是写一个程序模拟高速缓存的行为。需要注意的是这个程序仅仅需要模拟判断命中、替换算法和牺牲行的驱逐三个功能,不需要考虑缓存里块中存储的所需要读写的数据到底是什么。最后呈现的方式也是读取一系列内存读取的指令,给出命中、不命中和驱逐次数。

压缩文件中包含了一个csim-ref的可执行文件,我们写的程序csim功能上需要与这个csim-ref基本类似,至少对于相同内存读写时命中、不命中和驱逐次数三个数值相同。所以我们不妨看看csim-ref的基本情况。

根据压缩包里提供的帮助文档,可以知道在控制台输入的参数格式如下:
CSAPP实验四——cache lab实验(一)
其中加上参数v后,会把每一条指令是什么类型(L, M, S),读写内存大小和是否命中是否驱逐的信息逐行逐指令一一显示。而如果不加参数v只会显示做完所有指令后统计的命中、不命中和驱逐次数的和。

再来看指令的格式
CSAPP实验四——cache lab实验(一)
I表示读指令,在这个实验中不需要考虑。L表示加载、S表示存储,由于这个实验只需要模拟命中和驱逐次数这些,与内存块内数值是什么并没有关系,所以可以将L和S看成同一个对缓存的操作。M表示修改,对应一个加载一个存储,所以可以看成两个操作

理清思路后就可以着手码代码了。

1. 前期准备

首先定义相应结构体类型,回忆书上讲的内容,我们知道缓存可以看成一个很大的数组,数组中是由一个个组构成,组是由行来构成的,行是由标识位、有效位和块来组成。

这里由于实验我们不关心块的具体内容,所以可以在行中省去块的部分。同时每个行需要一个用来表示替换算法LRU优先级的数值,表示在没有空行时如果不命中需要优先替换组内的哪一行。在这里我定义这个数值为LRUcount,当这个数值越大则其越容易被替换,被访问后或被替换后这一行的数值被重置为0。

//行
typedef struct{
    int valid;   //一行的有效位(1表示有效)
    int tag;	 //一行的标识位
    int LRUcount;    //LRU替换优先级(越大替换优先级越高)	
}Line;

//组
typedef struct{
    Line* lines;  
}Set;

//缓存
typedef struct{
    Set* sets;
    int numset;    //组数
    int numline;   //行数
}Sim_cache;

接着写从控制台得到对应的s, E, b等选项参数的输入,参考了其他博客调用的是Linux C下的getopt()函数。需要包含头文件<getopt.h>。虽然<getopt.h>也是包含在<unistd.h>头文件中,但是我在make时一直报“隐式函数声明错误”的问题,于是索性直接include<getopt.h>本身了。

getopt()函数原型如下:
int getopt(int argc,char * const argv[ ],const char * optstring);

其中第三个参数传入的字符串就是命令行输入参数对应的格式。有冒号的表示该选项需要参数,全域变量optarg 即会指向此额外参数。这样就可以得到s, E, b这些数值。
关于getopt()函数的详细解释可以参考链接

void getOpt(int argc, char** argv, int *verbose, int *s, int *E, int *b){
    char ch;
    while( (ch=getopt(argc, argv, "hvs:E:b:t:") )!= -1 ){
		switch(ch){
	    	case 'h' : printHelpMenu(); break;
	    	case 'v' : *verbose = 1; break;
	    	case 's' : *s = atoi(optarg); break;
	    	case 'E' : *E = atoi(optarg); break;
	    	case 'b' : *b = atoi(optarg); break;
	    	case 't' : tracename = (char*)optarg; break;
	    	default : printHelpMenu(); exit(0);
		}
    }
}

依葫芦画瓢,模仿csim-ref的参考文档写出csim相应的打印帮助信息函数。

void printHelpMenu(){
    printf("Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>n");
    printf("Options:n");
    printf("  -h         Print this help message.n");
    printf("  -v         Optional verbose flag.n");
    printf("  -s <num>   Number of set index bits.n");
    printf("  -E <num>   Number of lines per set.n");
    printf("  -b <num>   Number of block offset bits.n");
    printf("  -t <file>  Trace file.nn");
    printf("Examples:n");
    printf("  linux>  ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.tracen");
    printf("  linux>  ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.tracenn");
}

2. 核心功能

核心功能之间的逻辑关系和实现见下图
CSAPP实验四——cache lab实验(一)
其中红色的标注judgeHit(), judgeFull(), Eviction()和updateLRU()分别是实现相应功能的四个函数。整个逻辑关系还需要用updateCache()一个大函数来整合。

//判断是否命中
int judgeHit(Sim_cache* sim_cache, int set_idx, int curTag){
    int nl = sim_cache->numline;
    for(int i=0; i< nl ; i++){
		if(sim_cache->sets[set_idx].lines[i].valid == 1  && sim_cache->sets[set_idx].lines[i].tag == curTag){
	    //表示命中了,只需要更新LRU数值
	    updateLRU(sim_cache, set_idx, i);
	    return 1;
		}
    }
    return 0;
} 


//判断这一组行是否满了(都满了返回-1)
int judgeFull(Sim_cache* sim_cache, int set_idx){
    /*如果这一组中有行未满,则返回行号,如果行都被占用了则返回-1*/
    int nl = sim_cache->numline;
    for(int i=0; i < nl; i++){
	    if (sim_cache->sets[set_idx].lines[i].valid == 0 )
	    return i;
    }
    return -1;
}

//组内行都满了则寻找需要被替换的行
int Eviction(Sim_cache* sim_cache, int set_idx){
    /*找到组内LRU最大的行,返回行号*/
    int replace_line=0; 
    int maxLRU = -1; 
    int nl = sim_cache->numline;
    for(int i=0; i < nl; i++){
		if (sim_cache->sets[set_idx].lines[i].LRUcount > maxLRU ){
	    	maxLRU = sim_cache->sets[set_idx].lines[i].LRUcount;
	    	replace_line = i;
		}
    }
    return replace_line;   
}

//更新LRU的数值
void updateLRU(Sim_cache *sim_cache, int set_idx, int line_idx){
    /*LRU越大表示下次越有可能覆盖它,最小为0(表示刚刚访问)*/
    int nl = sim_cache->numline;
    for(int i=0; i < nl; i++){
		sim_cache->sets[set_idx].lines[i].LRUcount ++ ; //这一组其他的行都LRU都增1   
    }
    sim_cache->sets[set_idx].lines[line_idx].LRUcount = 0;       
}

//整合上面四个函数,实现每次读写缓存的操作
void updateCache(Sim_cache* sim_cache, int set_idx, int curTag, int verbose){
    //整合一系列操作(判断命中,未命中判断是否需要进行行的替换)
    if(judgeHit(sim_cache, set_idx, curTag)){   //命中后操作
		hitcount++;
		if(verbose)  printf("hit  ");   
    }else{  
		misscount++;
		if(verbose)  printf("miss  ");
		//未命中先判断是否有空行
		int replace_line = judgeFull(sim_cache, set_idx);
		if(replace_line != -1){
	    	sim_cache->sets[set_idx].lines[replace_line].valid = 1;
	    	sim_cache->sets[set_idx].lines[replace_line].tag = curTag;
	    	updateLRU(sim_cache, set_idx, replace_line);
		}else{
	    	evictioncount++;
	    	if(verbose)  printf("eviction  ");
	    	replace_line = Eviction(sim_cache, set_idx);
	    	sim_cache->sets[set_idx].lines[replace_line].valid = 1;
	    	sim_cache->sets[set_idx].lines[replace_line].tag = curTag;
	    	updateLRU(sim_cache, set_idx, replace_line);	    
		}
    }
}

每次进行读写操作时都改变组内所有行的LRU的数值大小,LRU越大表示下次越有可能覆盖它,刚刚访问行的LRU设置为0,其余未被访问的LRU都增1。

3. 收尾部分

核心功能做完,还有一些其他的零散的一些工作。首先是缓存的初始化。需要动态开辟相应的空间,这个空间是根据输入的s, E, b三个数的数值来决定的。

void initCache(int s, int E, int b, Sim_cache* sim_cache){
    if(s<=0 || E<=0 ) exit(0);
    //初始化sim_cache部分
    sim_cache-> numset = 2<<s;  //2^s次方组
    sim_cache-> numline = E;
    sim_cache->sets = (Set*) malloc(sizeof(Set) * sim_cache->numset);
    if(!sim_cache->sets)   exit(0);
    //初始化set部分
    for(int i=0; i< sim_cache-> numset; i++){
		sim_cache->sets[i].lines = (Line*)malloc(sizeof(Line) * sim_cache->numline);
		//初始化line部分
		for(int j=0; j<E; j++){
	    	sim_cache->sets[i].lines[j].valid = 0;
	    	sim_cache->sets[i].lines[j].LRUcount = 0;
		}
    }
}

其次由于核心函数中比较的标识位Tag和组号set_idx是由指令的地址得到的,需要有两个转换函数。

int getTag(int addr, int s, int b){
    addr = (unsigned) addr;
    return addr >> (s+b);
}

int getSet(int addr, int s, int b){
    int set = addr >> b;
    int mask = (1 << s)-1;
    return mask & set;
}

最后就是main函数啦,涉及到从文件读的操作,以及初始化initCache()和updateCache()函数的调用。

int main(int argc, char** argv)
{
    int s=0, E=0, b=0,verbose=0;    
    char option;
    Sim_cache sim_cache;
    unsigned long long addr;
    int size;
    getOpt(argc, argv, &verbose, &s, &E, &b);  //读控制台输入
    initCache(s, E, b, &sim_cache);  //初始化cache
    printf("%s" ,tracename);
    FILE * pFile = fopen (tracename,"r"); 
    while(fscanf(pFile, " %c %llx,%d" , &option, &addr, &size)>0){
		if(option=='I') continue;
		int set_idx = getSet(addr,s,b);
		int curTag = getTag(addr,s,b);
		if(option=='L' || option=='S')
	    	updateCache(&sim_cache, set_idx, curTag, verbose);
		if(option=='M'){
	    	updateCache(&sim_cache, set_idx, curTag, verbose);
	    	updateCache(&sim_cache, set_idx, curTag, verbose);
		}
		if(verbose==1) printf("n");	
    }
    //fclose(pFile); 
    printSummary(hitcount, misscount, evictioncount);
    return 0;
}

最后make以下程序,得到的结果与csim-ref结果一样,cache lab第一个实验就算做完啦。
CSAPP实验四——cache lab实验(一)


程序员灯塔
转载请注明原文链接:CSAPP实验四——cache lab实验(一)
喜欢 (0)