Part A
这一部分是要实现一个cache模拟器，需要记录命中次数，不命中次数和替换次数，通过这个可以让我们更加了解cache的运行方式，同时也可以更加了解LRU的替换策略。
这一部分需要了解的两个函数getopt() 和 fscanf() 在开头的ppt中有讲解。
先上代码
#include "cachelab.h"#include <unistd.h>#include <getopt.h>#include <stdlib.h>#include <stdio.h>#include <string.h>int h, v, s, S, E, b, B; //定义全局变量方便调用char t[200];int hits, misses, evictions;long stempnow = 0;typedef struct{int valid; //有效位int tag; //标记位long LRU_stemp; //LRU替换的标记} cacheline, *cache_set, **_cache;_cache cache;//这一部分是为了实现-v下的回显，最终的测试并不要求这个typedef int result_tag;#define MISS 0#define HIT 1#define EVICTION 2void printUsage(); //-h打印使用方法void init_cache(); //初始化cachevoid close_cache(); //free掉cachevoid printverbose(char oper, unsigned int address, int size, char *opresult); //-v下打印回显void do_trace(); //解析trace并以此执行result_tag access_cache(char oper, unsigned int address, int size); //访问cacheint main(int argc, char **argv){int opt;while (-1 != (opt = (getopt(argc, argv, "hvs:E:b:t:")))){switch (opt){case 'h':h = 1;printUsage();break;case 'v':v = 1;break;case 's':s = atoi(optarg);break;case 'E':E = atoi(optarg);break;case 'b':b = atoi(optarg);break;case 't':strcpy(t, optarg);break;default:printUsage();break;}}if (s <= 0 || E <= 0 || b <= 0 || t == NULL) // 如果选项参数不合格就退出return -1;S = 1 << s;B = 1 << b;init_cache();do_trace();close_cache();printSummary(hits, misses, evictions);return 0;}void printUsage(){printf("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");}void init_cache(){cache = (_cache)malloc(sizeof(cache_set) * S);int i, j;for (i = 0; i < S; i++){cache[i] = (cache_set)malloc(sizeof(cacheline) * E);for (j = 0; j < E; j++){cache[i][j].tag = 0;cache[i][j].valid = 0;cache[i][j].LRU_stemp = 0;}}}void close_cache(){int i;for (i = 0; i < S; i++)free(cache[i]);free(cache);}void printverbose(char oper, unsigned int address, int size, char *opresult){printf("%c %x,%d %s", oper, address, size, opresult);}void do_trace(){FILE *fp = fopen(t, "r"); // 读取文件if (fp == NULL){printf("open error");exit(-1);}char operation; // 命令开头的 I L M Sunsigned int address; // 地址参数int size; // 大小while (fscanf(fp, " %c %xu,%d", &operation, &address, &size) > 0){size = 1;result_tag r;switch (operation){case 'I':break;case 'L':r = access_cache(operation, address, size);if (v){if (r == HIT)printverbose(operation, address, size, "hit");else if (r == MISS)printverbose(operation, address, size, "miss");else if (r == EVICTION)printverbose(operation, address, size, "miss eviction");}break;case 'S':r = access_cache(operation, address, size);if (v){if (r == HIT)printverbose(operation, address, size, "hit");else if (r == MISS)printverbose(operation, address, size, "miss");else if (r == EVICTION)printverbose(operation, address, size, "miss eviction");}break;case 'M':r = access_cache(operation, address, size);hits++; //M的第二次一定命中if (v){if (r == HIT)printverbose(operation, address, size, "hit hit");else if (r == MISS)printverbose(operation, address, size, "miss hit");else if (r == EVICTION)printverbose(operation, address, size, "miss eviction hit");}break;}}fclose(fp);}result_tag access_cache(char oper, unsigned int address, int size){int access_tag, access_set;int tag_mask, set_mask;set_mask = ((1 << (b + s)) - 1) - ((1 << b) - 1); //组号掩码access_set = ((set_mask & address) >> b) % S; //组号tag_mask = -1 << (b + s); //tag的掩码access_tag = tag_mask & address; //tag值int i;for (i = 0; i < E; i++){if (cache[access_set][i].valid && cache[access_set][i].tag == access_tag) //命中{hits++;cache[access_set][i].LRU_stemp = stempnow++;return HIT;}}for (i = 0; i < E; i++){if (!cache[access_set][i].valid) //未命中找到空行{cache[access_set][i].valid = 1;cache[access_set][i].tag = access_tag;cache[access_set][i].LRU_stemp = stempnow++;misses++;return MISS;}}//未命中且需要进行行替换//寻找时间戳最小（最少最近使用）的行int eviction_line = 0;long maxstemp = ~((long)1 << 63);for (i = 0; i < E; i++){if (cache[access_set][i].LRU_stemp < maxstemp){eviction_line = i;maxstemp = cache[access_set][i].LRU_stemp;}}//行替换cache[access_set][eviction_line].valid = 1;cache[access_set][eviction_line].tag = access_tag;cache[access_set][eviction_line].LRU_stemp = stempnow++;misses++;evictions++;return EVICTION;}
为了实现LRU的替换策略，我的方法是维持一个stempnow的自建时间戳，每次对行有更新时就讲这个时间戳记录进去，同时时间戳自加1，这样替换时就只需要寻找时间戳最小的那一行替换就行。
这一部分总体上不难，主要困难在于理解cache的工作方式和设计如何去提取出组号与tag值。
Part B
这一部分需要我们实现矩阵的转置，要求尽可能地利用cache，即减少miss，总共有三道题。
32*32
我们首先看一下示例的蛮力法
miss高达1183，远大于300的目标。
我们知道的是cache 大小为 s=5,E=1,b=5,即32组_1行_32字节，共256个int。
所以我们需要对矩阵进行分块，我们在转置的过程中尽量让块小于cache大小，因为cache可以装256个int，所以块大小定为8*8。
（这一步的代码没保存，就不贴了）
结果是
仍没达到要求。
下一步我选择每次把每一行的8个数一次性读取，然后再一次性存到矩阵B中，这样可以进一步减少cache的替换，从而减少miss。
if (M == 32){int i, j, block_i;int t0, t1, t2, t3, t4, t5, t6, t7;for (i = 0; i < N; i += 8){for (j = 0; j < M; j += 8){for (block_i = 0; block_i < 8; block_i++){t0 = A[i + block_i][j + 0];t1 = A[i + block_i][j + 1];t2 = A[i + block_i][j + 2];t3 = A[i + block_i][j + 3];t4 = A[i + block_i][j + 4];t5 = A[i + block_i][j + 5];t6 = A[i + block_i][j + 6];t7 = A[i + block_i][j + 7];B[j + 0][i + block_i] = t0;B[j + 1][i + block_i] = t1;B[j + 2][i + block_i] = t2;B[j + 3][i + block_i] = t3;B[j + 4][i + block_i] = t4;B[j + 5][i + block_i] = t5;B[j + 6][i + block_i] = t6;B[j + 7][i + block_i] = t7;}}}}
64*64
这是最难的一部分，因为整个cache只能存储数组的四行，所以如果按照8_8分块的话仍然有很高的冲突，然而这一题要求有十分严苛，只能1300，所以需要更精细的方法，先按照8_8分块，在块内在按照44划分，同时不追求一次到位，而要求最高的cache重复访问，详细解析可以参考这篇博客
*代码：
else if (N == 64)
{
for (int i = 0; i < N; i += 8)
{
for (int j = 0; j < M; j += 8)
{
for (int k = i; k < i + 4; ++k)
{
/* 读取1 2，暂时放在左下角1 2 */
int temp_value0 = A[k][j];
int temp_value1 = A[k][j + 1];
int temp_value2 = A[k][j + 2];
int temp_value3 = A[k][j + 3];
int temp_value4 = A[k][j + 4];
int temp_value5 = A[k][j + 5];
int temp_value6 = A[k][j + 6];
int temp_value7 = A[k][j + 7];
B[j][k] = temp_value0;
B[j + 1][k] = temp_value1;
B[j + 2][k] = temp_value2;
B[j + 3][k] = temp_value3;
/* 逆序放置 */
B[j][k + 4] = temp_value7;
B[j + 1][k + 4] = temp_value6;
B[j + 2][k + 4] = temp_value5;
B[j + 3][k + 4] = temp_value4;
}
for (int l = 0; l < 4; ++l)
{
/* 按列读取 */
int temp_value0 = A[i + 4][j + 3 - l];
int temp_value1 = A[i + 5][j + 3 - l];
int temp_value2 = A[i + 6][j + 3 - l];
int temp_value3 = A[i + 7][j + 3 - l];
int temp_value4 = A[i + 4][j + 4 + l];
int temp_value5 = A[i + 5][j + 4 + l];
int temp_value6 = A[i + 6][j + 4 + l];
int temp_value7 = A[i + 7][j + 4 + l];
/* 从下向上按行转换2到3 */
B[j + 4 + l][i] = B[j + 3 - l][i + 4];
B[j + 4 + l][i + 1] = B[j + 3 - l][i + 5];
B[j + 4 + l][i + 2] = B[j + 3 - l][i + 6];
B[j + 4 + l][i + 3] = B[j + 3 - l][i + 7];
/* 将3 4放到正确的位置 */
B[j + 3 - l][i + 4] = temp_value0;
B[j + 3 - l][i + 5] = temp_value1;
B[j + 3 - l][i + 6] = temp_value2;
B[j + 3 - l][i + 7] = temp_value3;
B[j + 4 + l][i + 4] = temp_value4;
B[j + 4 + l][i + 5] = temp_value5;
B[j + 4 + l][i + 6] = temp_value6;
B[j + 4 + l][i + 7] = temp_value7;
}
}
}
}
结果
像这样进行专门的优化，确实可以极大地提高cache的利用率，从而提高程序的效率，但是其缺点也很明显，只能针对专门的矩阵进行优化，不具有普适性，就像我们即将看到的第三题。
61*67
这一题由于矩阵没有什么特别的规律，所以不清楚在cache的映射情况，因此我们只能一步步地尝试分块的大小，最终发现大约在14*14时可以满足题目要求。
else
{ //没有什么特征，只能试块大小，在14的时候misses为1996，通过了
int block_size = 14;
int i, j, bl_i, bl_j;
for (i = 0; i < N; i += block_size)
for (j = 0; j < M; j += block_size)
for (bl_i = 0; bl_i < block_size && bl_i + i < N; bl_i++)
for (bl_j = 0; bl_j < block_size && bl_j + j < M; bl_j++)
B[j + bl_j][i + bl_i] = A[i + bl_i][j + bl_j];
}
满分合影
完整代码
若有收获，就点个赞吧
0 人点赞
