Cache-Lab

注意:如果使用WSL访问Windows文件的话,会遇到严重的磁盘IO问题,可能根本跑不出结果(就像DataLab的最后一问一样),所以最好把文件放到WSL的文件系统里,或者干脆物理机安装Linux然后在Linux下做😂

Part A: Writing a Cache Simulator

写这道题前最好先看看WriteUp和习题课的ppt
里面有挺详细的提示

这道题其实不难,但由于我太久没写c语言了,调试了半天Segmentation fault错误…

在内存中,cache被分成了S(S=2^s)个组(Set),一个Set有E行(Associaty),就像一个二维数组.
一个word(块)有b个字节,正好把一个地址分成了三部分:tag,set_index,block_offset

在查找cache时,先根据set_index找到对应的Set,然后遍历Set中的每一行,如果tag相同,则命中,否则miss

如果miss,则需要把数据从内存中读取到cache中,如果Set中的每一行都被占用了,则需要把最早的数据替换掉,这就是eviction

其中,这道题使用的缓存替换算法是LRU(Least Recently Used),即最近最少使用,也就是说,每次替换掉最早使用的数据

所以,在每一个缓存行都需要记录一个time,每次访问时,更新time,然后替换掉time最小的数据
读取命令行参数可以使用getopt,具体使用方法看ppt

注意,这道题并不是要我们实现一个缓存,只是模拟缓存的行为,统计hit,miss,eviction的次数,所以不需要存入数据

我的代码:

#include "cachelab.h"
#include <unistd.h>
#include <getopt.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int h = 0, v = 0, s = 0, E = 0, b = 0, S = 0;//为了方便就直接写成全局变量了
int hit,
    miss,
    eviction;
char file[1000];
int time = 0; // 时间计数
typedef struct
{
    int valid;
    int tag;
    int time;
} cache_line, *cache_set, **cache; // 缓存

cache Cac;

void printUsage();            // 打印命令行参数的用法
void getconfig();             // 读取命令行参数
void initCache();             // 为cache分配内存
void readfile();              // 读输入文件并调用VisitCache
int visitcache(unsigned int); // 模拟访问cache,并记录数据

int main(int argc, char **argv)
{
    getconfig(argc, argv);
    initCache();
    readfile();

    printSummary(hit, miss, eviction);
    return 0;
}

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

void getconfig(int argc, char **argv) // 详见PPT
{
    int opt;
    /* looping over arguments */
    while (-1 != (opt = getopt(argc, argv, "hvs:E:b:t:")))
    {
        /* determine which argument it’s processing */
        switch (opt)
        {
        case 'h':
            printUsage();
            exit(EXIT_FAILURE);
            break;
        case 'v':
            v = 1;
            break;
        case 's':
            s = atoi(optarg);
            S = 1 << s;
            break;
        case 'E':
        case 'e':
            E = atoi(optarg);
            break;
        case 'b':
            b = atoi(optarg);
            break;
        case 't':
            strcpy(file, optarg);
            break;
        default:
            printf("Wrong Argument!\n");
            printUsage();
            exit(EXIT_FAILURE);
            break;
        }
    }
    if (S <= 0 || s <= 0 || E <= 0 || b <= 0 || file == NULL)
    {
        printf("ERROR!");
        exit(EXIT_FAILURE);
    }
}
void initCache()
{
    Cac = malloc(sizeof(cache_set) * S);
    if (Cac == NULL)
    {
        printf("Mem_ERROR!");
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i < S; i++)
    {
        Cac[i] = malloc(sizeof(cache_line) * E);
        if (Cac[i] == NULL)
        {
            printf("Mem_ERROR!");
            exit(EXIT_FAILURE);
        }
        for (int j = 0; j < E; j++)
        {
            Cac[i][j].time = 0;
            Cac[i][j].tag = 0;
            Cac[i][j].valid = 0;
        }
    }
}
/*
void readfile();
输入文件的格式是
[space]operation address,size
比如   I 0400d7d4,8
“I”---instruction load===可以忽略
“L”---data load,
“S”---data store
“M”---data modify=====注意要访问两次内存!!!首先是读取然后写入

*/
void readfile()
{
    FILE *fp = fopen(file, "r");
    if (fp == NULL)
    {
        printf("FILE_ERROR!");
        exit(EXIT_FAILURE);
    }
    char identifier;
    unsigned address;
    int size;
    while (fscanf(fp, " %c %x,%d\n", &identifier, &address, &size) > 0)
    {
        if (v == 1)
            printf("%c %x,%d ", identifier, address, size);
        switch (identifier)
        {
        case 'I':
            break;
        case 'M':
            visitcache(address);
            visitcache(address); // M指的是Data Modify,要访问两次内存,一次读取一次写入
            break;
        case 'L':
            visitcache(address);
            break;
        case 'S':
            visitcache(address);
            break;
        }
    }
}

/*
int visitcache(unsigned int address);
地址被分为tag-setIndex-blockOffset三部分
其中setIndex有s位,blockOffset有b位
通过位运算来求tag,set_index
*/
int visitcache(unsigned int address)
{
    time++;
    int tag = address >> (s + b);
    int set_index = (address >> b) & (((unsigned)-1) >> (8 * sizeof(unsigned) - s));
    int pos = 0;
    for (pos = 0; pos < E; pos++)
    {
        if (Cac[set_index][pos].tag == tag && Cac[set_index][pos].valid == 1)
        {
            hit++;
            Cac[set_index][pos].time = time;
            if (v == 1)
                printf("hit");
            return 0;
        }
    }
    for (pos = 0; pos < E; pos++)
    {
        if (Cac[set_index][pos].valid == 0)
        {
            miss++;
            Cac[set_index][pos].tag = tag;
            Cac[set_index][pos].valid = 1;
            Cac[set_index][pos].time = time;
            if (v == 1)
                printf("miss");
            return 1;
        }
    }
    pos = 0;
    for (int i = 0; i < E; i++)
    {
        if (Cac[set_index][i].time < Cac[set_index][pos].time)
            pos = i;
    }
    miss++;
    eviction++;
    Cac[set_index][pos].tag = tag;
    Cac[set_index][pos].time = time;
    if (v == 1)
        printf("miss eviction");
    return 2;
}

Part B: Optimizing Matrix Transpose

如果使用WSL访问Windows文件的话,会遇到严重的磁盘IO问题,所以最好把文件放到WSL的文件系统里

32x32

这道题的目的是优化矩阵转置的性能,使用了分块的方法,每次转置一个8*8的小矩阵,这样可以利用缓存的局部性,减少缓存的miss

if (M == 32)
{
    int i, j, m, n;
    for (i = 0; i < N; i += 8)
        for (j = 0; j < M; j += 8)
            for (m = i; m < i + 8; ++m)
                for (n = j; n < j + 8; ++n)
                {
                    B[n][m] = A[m][n];
                }
}

编译运行,发现miss依旧有344,达不到要求,还有什么可以优化的呢?

我看见WriteUP里面说到了会把各个函数内存访问情况写进trace.fi2文件中,用csim-ref把内存访问情况输出到out.txt里./csim-ref -v -s 5 -E 1 -b 5 -t trace.f1 >out.txt

通过观察,我们可以找到A,B数组的地址(在我的机器上分别是405120和445120),当它在对角线上时,似乎是被映射到同一个Cache Set中的,才导致了大量的 miss eviction.

改进如下:

char transpose_submit_desc[] = "Transpose submission";
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    if (M == 32)
    {
        int i, j, m, tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7, tmp8;
        for (i = 0; i < N; i += 8)
            for (j = 0; j < M; j += 8)
                for (m = 0; m < 8; ++m)
                {
                    tmp1 = A[i][j + m];
                    tmp2 = A[i + 1][j + m];
                    tmp3 = A[i + 2][j + m];
                    tmp4 = A[i + 3][j + m];
                    tmp5 = A[i + 4][j + m];
                    tmp6 = A[i + 5][j + m];
                    tmp7 = A[i + 6][j + m];
                    tmp8 = A[i + 7][j + m];
                    B[j + m][i] = tmp1;
                    B[j + m][i + 1] = tmp2;
                    B[j + m][i + 2] = tmp3;
                    B[j + m][i + 3] = tmp4;
                    B[j + m][i + 4] = tmp5;
                    B[j + m][i + 5] = tmp6;
                    B[j + m][i + 6] = tmp7;
                    B[j + m][i + 7] = tmp8;
                }
    }
}

64x64

如果直接套用32x32矩阵的代码,结果是hits:3585, misses:4612, evictions:4580,远远超出了要求,有点离谱的是,miss数量是32x32矩阵的整整16倍!🤔

仔细一想,现在是64x64的矩阵,这样的话cache就只能存下矩阵的四行了,所以如果采用8x8的分块,会导致每一个块的前四行与后四行被映射到同一个cache中,在写入的时候产生miss

仔细观察,发现确实是这样,每8个load指令接着的store指令都是产生miss;

那就试试4x4分块咯;结果是hits:6545, misses:1652, evictions:1620,misses下降到了1652,离目标1300还有一点小差距

未完待续…,剩下的就有时间再写了

参考了知乎大佬的文章