深入理解计算机系统-Cache_lab

Cache_lab

本文对应CMU给出的几个lab中的cache lab的部分解答,代码我托管在github。由于本人能力有限而且懒,所以只写了这个lab的PartA,PartB的1和3,留了一个PartB的第二题,我觉得太麻烦了= =

PartA

我花了一个半小时弄清楚partA的题目在让我做什么东西,然后又花了一个小时弄懂getopt()这个函数怎么用,然后一个晚自习就过去了= =。这次就已经恐怖成这样了,真不知道后面的malloc的lab该成何体统。

题目
天顶洞人版本:

In Part A, you will write a cache simulator in csim.c that takes a valgrind memory trace as input, simulates the hit/miss behavior of a cache memory on this trace, and outputs the total number of hits, misses, and evictions.

正常人版本:
根据之前书里面提到的高速缓存器的内容,根据给定的s,e,b值,模拟出一个高速缓存器对一系列的指令(load,store,modify)中产生的miss,hit和eviction。
提示

  • load和store其实都是将内容里面的东西载入缓存,所以其实可以看成是一个东西。modify其实就是先load再store的过程,而且是连续的,所以store的那个过程肯定是hit的~因为load已经把那个数据放到缓存里了。
  • 使用getopt函数获得命令行的参数内容,这里给出一个使用实例:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int main(int argc, char** argv){
    int opt, x,y;
    /* looping over arguments */
    while(-1 != (opt = getopt(argc, argv, “x:y:"))){
    /* determine which argument it’s processing */
    switch(opt) {
    case 'x':
    x = atoi(optarg);
    break;
    case ‘y':
    y = atoi(optarg);
    break;
    default:
    printf(“wrong argument\n");
    break;
    }
    }
    }
  • 这里的eviction出现碰撞的替换策略使用的是LRU(Least Recently Used),也就是替换最久之前被使用的那一行,我想的模拟方法是采用一个计数器curr_pc,每次读取一个指令计数器加一,每使用到一行缓存或者把数据load进缓存时就更新其curr_pc,这样每次出现碰撞的时候只需要看那一组里谁的curr_pc最小就行了。

实现

  • 首先是构建数据结构:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    typedef struct cacheLine{
    int valid_bit;
    int tag;
    int LRU;
    }cache_line;

    typedef struct cache_set{
    cache_line* cache_lines;
    }cache_set;

    typedef struct cache{
    int size;
    int lines;
    int line_size;
    cache_set* cache_sets;
    }cache;
  • 初始化cache

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void init_cache(){
    //printf("start init the cache\n");
    int temp=0,i=0;
    sim_cache.size=1<<s;
    sim_cache.lines=E;
    sim_cache.line_size=1<<b;
    sim_cache.cache_sets=(cache_set*)malloc(sizeof(cache_set)*(1<<s));
    for(temp=0;temp<(1<<s);temp++){
    sim_cache.cache_sets[temp].cache_lines=(cache_line*)malloc(sizeof(cache_line)*E);
    for(i=0;i<E;i++){
    init_cache_line(&sim_cache.cache_sets[temp].cache_lines[i]);
    }
    }
    //printf("init finished\n");
    return;
    }
  • 获得b,E,s,v的值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    while(-1 != (opt1 = getopt(argc, argv, "hvs:E:b:t:"))){
    /* determine which argument it’s processing */
    switch(opt1) {
    case 'v':
    isVerbose=1;
    break;
    case 's':
    s=atoi(optarg);
    break;
    case 'E':
    E=atoi(optarg);
    break;
    case 'b':
    b=atoi(optarg);
    break;
    case 't':
    strcpy(fileName,optarg);
    break;
    case 'h':
    default:
    helpMenuPrint();
    exit(0);
    }
    }
  • 处理指令

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    void process_file(){
    char opt[10];
    int address,data_size;
    init_cache();
    //printf("file name is %s\n",fileName);
    FILE* tracefile=fopen(fileName,"r");
    //printf("start_processing_file\n");
    while(fscanf(tracefile,"%s %x,%d",opt,&address,&data_size)!=EOF){
    //printf("opt:%s\n",opt);
    if(isVerbose==1){
    printf("%s %x,%d",opt,address,data_size);
    }
    if(strcmp(opt,"I")==0){
    continue;
    }
    if(strcmp(opt,"L")==0){
    //printf("L\n");
    loadData(address,data_size);
    }
    if(strcmp(opt,"S")==0){
    //printf("S\n");
    storeData(address,data_size);
    }
    if(strcmp(opt,"M")==0){ //Modify data
    //printf("M\n");
    modifyData(address,data_size);
    }
    if(isVerbose==1){
    printf("\n");
    }
    curr_pc+=1;
    }
    }
  • 最重要的模拟缓存的处理机制

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    cache_line* load_cache(int tag_num,int set_num){
    cache_line* cache_set_instance=sim_cache.cache_sets[set_num].cache_lines;
    int i=0;
    cache_line* empty_line=NULL;
    for(i=0;i<E;i++){
    if(cache_set_instance[i].valid_bit==0){
    empty_line=&cache_set_instance[i];
    break;
    }
    }
    if(empty_line){
    empty_line->valid_bit=1;
    //printf("use empty cache in set %d, E index %d\n",set_num,i);
    return empty_line;
    }
    else{
    int LRU_min=0x7fffffff,LRU_min_index=0;
    //printf("sum_evition+1\n");
    is_Evict=1;
    sum_eviction+=1;
    for(i=0;i<E;i++){
    if(cache_set_instance[i].LRU<LRU_min){
    LRU_min=cache_set_instance[i].LRU;
    LRU_min_index=i;
    }
    }
    //printf("use eviction in set %d, E index %d\n",set_num,LRU_min_index);
    return &cache_set_instance[LRU_min_index];
    }
    }

    void loadData(int address,int dataSize){
    //printf("start load data\n");
    int set_num=(address>>b)&((1<<s)-1);
    int tag_num=(address>>(s+b));
    cache_line* cache_set_instance=sim_cache.cache_sets[set_num].cache_lines;
    int i=0;
    cache_line* final_cache=NULL;
    bool isfind=false;
    for(i=0;i<E;i++){
    if(cache_set_instance[i].valid_bit==1&&cache_set_instance[i].tag==tag_num){
    final_cache=&cache_set_instance[i];
    isfind=true;
    break;
    }
    }
    if(isfind){
    //***********curr_PC not defined
    final_cache->LRU=curr_pc;
    if(isVerbose==1){
    printf(" hit");
    }
    sum_hit+=1;
    //printf("hit at cache set %d, E index %d\n",set_num,tag_num);
    //printf("sum_hit +1\n");
    }
    else{
    is_Evict=0;
    cache_line* new_cache_line=load_cache(tag_num,set_num);
    new_cache_line->LRU=curr_pc;
    new_cache_line->tag=tag_num;
    if(isVerbose==1){
    printf(" miss");
    }
    if(is_Evict&&isVerbose){
    printf(" eviction");
    }
    sum_miss+=1;
    //printf("sum_miss +1\n");
    }
    //printf("load data finished\n");
    }

    void storeData(int address,int dataSize){
    //printf("start store data\n");
    loadData(address,dataSize);
    //printf("store data finished\n");
    }

    void modifyData(int address,int dataSize){
    //printf("start modify data\n");
    loadData(address,dataSize);
    storeData(address,dataSize);
    //printf("modify data finished\n");
    }

ps其实这里只要写出一个load的模拟就行了,store直接调用load,modify直接调用load和store。

结果

PartB

这部分要求利用程序的局部性构造矩阵转制算法,分别转制32*32,64*64,61*67的三种矩阵。在给定的高速缓存下,尽可能多的hit以及尽可能少的miss。

writeup里给出了一个对我们转制算法非常有用的提示:

Blocking is a useful technique for reducing cache misses. See http://csapp.cs.cmu.edu/public/waside/waside-blocking.pdf for more information.

也就是分块技术,通过对矩阵进行分块转制,从而避免了缓存在A,B两个矩阵之间的冲突现象。

由于我比较懒,而且看64*64的转制比较繁琐又有点难,就没有做了,不过网上应该有很多解答的,我这里只考虑第一个和第三个矩阵的转制。

32*32

由于给的高速缓存是32组,每组1行,每行32个字节,那么其实这个高速缓存的内部大小可以存256个int,为了避免不必要的冲突不命中,我们将A,B矩阵分为16块,每块有64个int,分别进行转制,一旦每个块都被载入缓存中(冷不命中)后,就不会存在不命中的情况。所有就很大程度的减少了转制的miss。根据这个想法我们可以写出如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
int i,j,k,l,m;
if(M==32){
for(i=0;i<M;i+=8){
for(j=0;j<N;j+=8){
for(k=0;k<8;k++){
for(l=0;l<8;l++){
B[i+k][j+l]=A[j+l][i+k];
}
}
}
}
}
}

但是其实这样运行一下你会发现实际上有314次miss,比我们💯要求多了14次miss,那么这里的优化在哪里呢?如果我们仔细考虑一下的话,对角线上的元素还是会产生冲突不命中的,因为A,B矩阵上对角线上的元素都会映射到同一块缓存上,为了避免这个问题,我们考虑的方式是对于每一行/列首先处理对角线上的元素,然后向两边扩散,同时,读A矩阵是按照列的方向读取,从而保证了在B缓存了对角线对应行的数据后,A接下来的缓存访问都不会冲突不命中的情况,也就是保证B矩阵缓存的那一行会完整的保留到该行处理结束而不会被eviction。这样我们就会减少约4*8次miss。即在所有的冷不命中后,之后都是hit。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
int i,j,k,l,m;
if(M==32){
for(i=0;i<M;i+=8){
for(j=0;j<N;j+=8){
for(k=0;k<8;k++){
for(l=k;l>=0;l--){
B[i+k][j+l]=A[j+l][i+k];
}
for(m=k+1;m<8;m++){
B[i+k][j+m]=A[j+m][i+k];
}
}
}
}
}
}

`6464`**

听说这个很难,我放弃= =

61*67

这个很假,其实只要改一下我们的block大小,然后直接转制就满分了= =

1
2
3
4
5
6
7
8
9
10
11
12
13
if(M==61){
for(i=0;i<M;i+=16){
for(j=0;j<N;j+=16){
for(k=0;k<16;k++){
for(l=0;l<16;l++){
if(i+l<M&&j+k<N){
B[i+l][j+k]=A[j+k][i+l];
}
}
}
}
}
}

结果

Summary

总体来说我感觉做的很马虎,但是还是把这个lab给搞掉了,对cache的理解也加深了很多,这学期计算机系统结构有cache的内容,大概可以睡觉了😂

Reference

[1] Intro to Computer Systems: Assignments-CMU
[2] 深入理解计算机系统CacheLab-PartB实验报告-码龙的窝
[3] Ethan-Yan27/CSAPP-Labs-github