Cachelab

CacheLab，对应为CSAPP的第六章。 本实验分为两个部分 PartA：你需要保证自己清楚Cache机制的情况下，通过C代码手搓一个模拟Cache，要求行为与参考程序一致。 PartB：你的程序会接收三种不同规格的矩阵，你需要优化代码，使得各个矩阵转置过程中cache的miss数低于一定程度才能得分。

PartA : Cache的程序模拟

由于是对高速缓存的实现,这里我不想废笔墨告诉你告诉缓存相关知识,详细看书关于告诉缓存结构论述,地址的切分以及LRU替换算法 所以我们先来看看这个测试的结构 将tar压缩包解压,得到下面这个实验所需材料。 下面是一些比较重要的文件/文件夹

/trace      //测试用元数据
csim.c      //我们要编辑的源文件
csim-ref    //参考程序
driver.py   //自动评分程序

输入的指令

在trace文件夹内就是程序测试用的元数据，也就是我们程序要读取的输入 格式为指令 地址 所需字节 这里指令分为三种

L 7e12dd58 1   //LOAD指令，从内存读取数据
S 3d615387 1   //SAVE指令，向内存写入数据
M 3daee234 1   //MODOFY指令，相当于先LOAD，后SAVE

输入的命令行参数

同样，我们在使用csim-ref这个程序的时候，需要读取输入。

./csim-ref
./csim-ref: Missing required command line argument
Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>
Options:
  -h         Print this help message.
  -v         Optional verbose flag.
  -s <num>   Number of set index bits.
  -E <num>   Number of lines per set.
  -b <num>   Number of block offset bits.
  -t <file>  Trace file.

Examples:
  linux>  ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace
  linux>  ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace

可以看到我们的程序要能够处理最基本的四个参数。-s,-E,-b,-t

输出与行为

本处的参考程序通过命令函参数初始设置高速缓存，然后读取trace文件开始执行文件内指令。

API设计

这里我们将整个程序的API,设计如下 由于地址,为64位地址,常规int存不下,必须显式指定64位数据类型存储

/* 命中/未命中/驱逐 计数器 */
static int hits = 0;
static int misses = 0;
static int evictions = 0;

/* 定义缓存数据结构 */
typedef struct{
    int valid; //有效位
    uint64_t tag; //标志位
    int last_used; //上次使用时间
}
typedef Cache_line* Cache_set;
typedef Cache_set* Cache;

/* 定义计时器 */
static int timer = 0;

/* 处理函数 */
static void addr_ana(uint64_t addr , uint64_t* Set_index , uint64_t* tag);
static uint64_t LRU(uint64_t Set_index,Cache my_cache);
static void access_cache(uint64_t addr,Cache my_cache);
Cache init_cache(uint64_t S,uint64_t E,uint64_t B);
void free_cache(uint64_t S,uint64_t E,Cache my_cache);
void run_instruction(char* line,Cache my_cache);

main函数内输入处理与函数执行

main函数内主要完成两件事

• 处理命令行输入的string型参数，转换为实际数值处理
• 处理文件路径打开相应文件，读取指令
• 执行相应的函数

总体设计如图

int main(int argc,char *argv[]){
    int verbose = 0;
    char* trace_file = NULL;
    int opt;

    /* 使用getopt处理输入的参数 */
    while((opt = getopt(argc,argv,"hvs:E:b:t:")) != -1){
        switch(opt){
            case 's': s=atoi(optarg);break;
            case 'E': E = atoi(optarg);break;
            case 'b': b=atoi(optarg);break;
            case 't': trace_file = optarg; break;
            case 'v': verbose = 1;break;
            default:
                fprintf(stderr,"Usage: .....");
                exit(1);
        }
    }

    /* 打开trace文件 */
    FILE *fp = fopen(trace_file,"r");
    if(!fp){
        printf("fopen");
        exit(1);
    }

    /* 初始化cache */
    uint64_t S = (uint64_t)1 << s;
    uint64_t B = (uint64_t)1 << b;
    Cache my_cache = init_cache(S,E,B);

    /* 读取，执行指令 */
    char line[100];
    while(fgets(line,sizeof(line),fp)){
        run_instruction(line,my_cache);
    }

    /* 释放cache */
    free_cache()

    /* 程序指定输出 */
    printSummary(hits, misses, evictions);

}

init_cache实现

init_cache的实现如下。 由于我们将Cache定义为一个“二维数组”。 通过malloc函数,先是在函数内创建一个cache_set的数组 随后在第一层循环内给各cache_set创建cache_line数组 通过两层循环，初始化各个缓存行。 将各缓存行的valid设置为0，tag设置为0，last_used设置为0

Cache init_cache(uint64_t S,uint64_t E,uint64_t B){

    //Step1 build set
    Cache my_cache = (Cache)malloc(S * sizeof(Cache_set));
    //Step2 init set
    for(int i=0;i< S ;i++){
        my_cache[i] = (Cache_set)malloc(E * sizeof(Cache_line));
        for(int j=0;j < E;j++){
            my_cache[i][j].valid = 0;
            my_cache[i][j].tag = 0;
            my_cache[i][j].last_used = timer;
        }
    }
    return my_cache;
}

run_instruction的实现

由于输入的是字符串,我们需要对字符串进行解析,得到指令类型以及地址 通过sscanf来格式化输入操作. 这里我们要知道一个点,LOAD指令与SAVE指令本质都是对于CACHE的一次访问操作,是否命中的策略是一样的,而MODIFY指令相当于一次LOAD,一次SAVE 所以switch语句下就是指定不同命令访问几次cache.

void run_instruction(char* line,Cache my_cache){
    char c = 0;
    uint64_t addr = 0;
    sscanf(line," %c %lx",&c,&addr);
    switch(c){
        case 'L':access_cache(addr,my_cache);break;
        case 'S':access_cache(addr,my_cache);break;
        case 'M':access_cache(addr,my_cache);
                 access_cache(addr,my_cache);
                 break;
        default:break;
    }
}

access_cache的实现

接下来是较为复杂的access_cache函数实现 它接收地址,缓存的输入,然后访问缓存,如果存在则hit++. 如果不在,则miss++,然后执行LRU,然后找到该段进行替换.如果替换的行的valid !=0,则evictions ++

而这里按顺序完成这几件事

• 令timer++
• 执行地址解析函数得到cache_set的索引以及tag的值
• 遍历cache_set内的cache_line,如果tag相同,表明命中,更新hits后返回
• 如果未命中,则更新misses.然后执行LRU替换策略,如果被替换的cache_line的valid非0,那么更新evictions

tatic void access_cache(uint64_t addr,Cache my_cache){
    timer++;
    uint64_t si = 0, li = 0,tag = 0;
    addr_ana(addr,&si,&tag);
    for(li=0 ; li<E ; li++){
        if(my_cache[si][li].valid != 0 && my_cache[si][li].tag == tag)
        {
            hits++;
            my_cache[si][li].last_used = timer;
            return;
        }
    }
    misses++;
    li = LRU(si,my_cache);
    if(my_cache[si][li].valid != 0) evictions++; 
    my_cache[si][li].valid = 1;
    my_cache[si][li].tag = tag;
    my_cache[si][li].last_used = timer;
}

addr_ana的实现

这里我们需要对二进制地址进行切分得到cache_set索引以及tag的值.通过位操作可以轻易做到

static void addr_ana(uint64_t addr , uint64_t* Set_index , uint64_t* tag){
    addr = addr >> b;
    uint64_t mask = ((uint64_t)1 << s) -1;
    *Set_index = addr & mask;
    *tag = sddr >> s;
}

LRU的实现

static uint64_t LRU(uint64_t Set_index,Cache my_cache){
    int min_time = my_cache[Set_index][0]; 
    for(int li = 1;li < E ;li++){
                
    }
}