CSAPP Lab4: Cache

一、准备

• 解压：tar xvf cachelab-handout.tar
• 主要修改 csim.c 和 trans.c这两个文件
• valgrind --log-fd=1 --tool=lackey -v --trace-mem=yes ls -l，执行 ls -l命令并对该命令按照内存访问发生的顺序捕获内存跟踪，并打印到stdout
  • [space]operation address,size
  • operation包含 I、L、M、S，I表示指令加载、L表示数据加载、S表示数据存储、M表示数据修改

二、A部分，模拟高速缓存

在csim.c中实现一个缓存模拟器，以valgrind内存跟踪作为输入，模拟缓存内存的命中/未命中行为，并输出命中、未命中、缓存替换的总数，缓存替换算法使用LRU。采用立即写回，因此M之后立马S。

自己实现的缓存模拟器的行为可以参考实验目录中提供的csim-ref，包含以下参数选项：

• -h： Optional help flag that prints usage info
• -v：Optional verbose flag that displays trace info
• -s < s>: Number of set index bits (S = 2^s
  is the number of sets)
• -E : Associativity (number of lines per set)
• -b < b>: Number of block bits (B = 2^b
  is the block size)
• -t < tracefile>: Name of the valgrind trace to replay

注意:

• 忽略vargrind程序中 I 开头的输出，只关注数据的缓存性能
• 程序结尾：printSummary(hit_count, miss_count, eviction_count);

步骤：

• 定义缓存结构体
• 接收vargrind的输入
• 数据要访问时，先检查缓存有没有
• 有的话，缓存命中，命中数加一
• 否则，寻找缓存是否空闲，放入缓存
• 否则，寻找最长未使用的数据，将其替换
• 时间计数加一

#include 
#include 
#include 
#include 
#include 
#include "cachelab.h"


struct cache_line{
    int valid;//有效位，表示该缓存是否有效
    unsigned tag;//标记位，用于匹配缓存
    int time;//时间统计
};

//s表示组的幂，E表示每个组有多少行，b表示每个行有多少字节，S表示十进制有多少个组
struct cache_meta{
    int s;
    int S;
    int E;
    int b;
    int hit;
    int miss;
    int replace;
};

char *filepath;
//int s, E, b, S;
//int hit, miss, replace;

struct cache_line **cache;//缓存

void useag(){
    printf("-s:Number of set index bits (S = 2^s is the number of sets)\n");
    printf("-E:Associativity (number of lines per set)\n");
    printf("-b:Number of block bits (B = 2^b is the block size)\n");
    printf("-t: Name of the valgrind trace to replay\n");
}

//初始化缓存
void init_cache(struct cache_meta *meta){
    cache = (struct cache_line **)malloc(sizeof(struct cache_line *) * meta->S);
    
    int i, j;
    for(i = 0;i < meta->S; i++){
        cache[i] = (struct cache_line *)malloc(sizeof(struct cache_line) * meta->E);
    }

    for(i = 0; i < meta->S; i++){
        for(j = 0; j < meta->E; j++){
            cache[i][j].valid = 0;
            cache[i][j].tag = 0xffffffff;
            cache[i][j].time = 0;
        }
    }
}
//释放缓存
void uint_cache(struct cache_meta *meta){
    int i;
    for(i = 0; i < meta->S; i++){
        free(cache[i]);
    }
    free(cache);
}

//地址组成，E，s，b
//使用组相联
void lru(struct cache_meta *meta, unsigned addr){
    unsigned addr_s;
    unsigned addr_E;
    int i;
    int max_time_nused = 0;
    int nused_index = 0;

    addr_s = (addr >> meta->b) & ((-1U) >> (32 - meta->s));//取出地址的s部分，即前s位;
    addr_E = (addr >> (meta->b + meta->s));
    if(addr_s > meta->S){
        printf("group err,input:%d,set:%d,addr:%d\n",addr_s,meta->S, addr);
        return;
    }
    
    for(i = 0; i < meta->E; i++){
        //缓存命中
        if(cache[addr_s][i].tag == addr_E){
            cache[addr_s][i].time = 0;
            meta->hit++;
            return;
        }
    }
    //未命中，寻找可用空间
    for(i = 0; i < meta->E; i++){
        if(!cache[addr_s][i].valid){
            cache[addr_s][i].valid = 1;
            cache[addr_s][i].tag = addr_E;
            cache[addr_s][i].time = 0;
            meta->miss++;
            return;
        }
    }
    //没有空间了，从该组中选择一行替换
    for(i = 0; i < meta->E; i++){
        if(cache[addr_s][i].time > max_time_nused){
            max_time_nused = cache[addr_s][i].time;
            nused_index = i;
        }
    }
    cache[addr_s][nused_index].tag = addr_E;
    cache[addr_s][nused_index].time = 0;
    meta->miss++;
    meta->replace++;
}

void lru_add_time(struct cache_meta *meta){
    int i, j;
    for(i = 0; i < meta->S; i++){
        for(j = 0; j < meta->E; j++){
            if(cache[i][j].valid == 1){
                cache[i][j].time++;
            }
        }
    }
}

int main(int argc, char *argv[])
{
    int opt;
    struct cache_meta meta = {0};
    char op;
    unsigned addr;
    int size;
    //解析命令行
    while((opt = getopt(argc, argv, "s:E:b:t:h")) != -1){
        switch (opt)
        {
            case 's':
                meta.s = atoi(optarg);
                break;
            case 'E':
                meta.E = atoi(optarg);
                break;
            case 'b':
                meta.b = atoi(optarg);
                break;
            case 't':
                filepath = optarg;
                break;
            case 'h':
                useag();
                break;
            default:
                printf("please input the -h args, loop up the help!");
                return 0;
        }
    }
    if(meta.s == 0){
        printf("param s is 0, exit!\n");
        return 0;
    }
    meta.S = 1<<meta.s;

    init_cache(&meta);
    //读取输入
    FILE *file = fopen(filepath, "r");
    if(!file){
        printf("cannot open file:%s\n",filepath);
        return 0;
    }

    while(fscanf(file, "%c %x,%d", &op, &addr, &size) > 0){
        switch (op)
        {
            case 'L':
                lru(&meta, addr);
                break;
            case 'M':
                lru(&meta, addr);
            case 'S':
                lru(&meta, addr);
                break;
        }
        lru_add_time(&meta);
    }

    uint_cache(&meta);
    fclose(file);
    printSummary(meta.hit, meta.miss, meta.replace);
    return 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
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188

使用./test-csim验证功能的正确性。

三、B部分，优化缓存性能

要求：

• 对矩阵转置进行优化，减少缓存不命中的次数
• 设置s = 5，E = 1，b = 5
• 在trans.c中进行编码，最多可以定义12个int型的局部变量
• 转置函数不能修改数组A，但可以修改数组B
• 不能使用malloc等函数
• 三种规格的矩阵：32 * 32, 64 * 64, 61 *67

//todo