Cache Lab

介绍

本实验有两个部分，Part A 要求我们模拟一个 cache 行为，正确地模拟每次操作（如 load、store、modify） cache 的响应（hit、miss、eviction）。Part B 要求我们用尽可能少的 cache 的 miss 实现矩阵的转置，充分利用 cache。

实验说明：地址

Part A

在本实验中，需要完成 csim.c 文件，使之编译后实现类似功能：

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

要求我们的程序可以手动设置 cache 的 set 数、line 数、block 大小，读取指定的文件内容进行操作，指令类似如下：

I 0400d7d4,8
M 0421c7f0,4
L 04f6b868,8
S 7ff0005c8,8

每行代表一个操作，格式:

• [space]operation address,size
• I 代表 instruction load,
• L 代表 data load,
• S 代表 data store,
• M 代表 data modify (i.e., a data load followed by a data store)

回顾一下 cahce 具体结构：

具体如下：

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

typedef unsigned long int uint64_t;

typedef struct {
    int valid;
    int lru;
    uint64_t tag;
}cacheLine;

typedef cacheLine* cacheSet;
typedef cacheSet* Cache;

const char* usage = "Usage: %s [-hv] -s <s> -E <E> -b <b> -t <tracefile>\n";

int verbose = 0; //verbose flag 
int s;  //number of set index bits 
int E;  //number of lines per set
int b;  //number of block bits
FILE* fp = NULL;
Cache cache;

int hits = 0;
int misses = 0;
int evictions = 0;

void parseArgument(int argc, char* argv[]);
int visitCache(uint64_t address);
int simulate();

int main(int argc, char* argv[])
{
    parseArgument(argc, argv);
    simulate();
    printSummary(hits, misses, evictions);
    return 0;
}

void parseArgument(int argc, char* argv[])
{
    int opt;
    while ((opt = getopt(argc, argv, "hvs:E:b:t:")) != -1)
    {
        switch(opt)
        {
            case 'h':
                fprintf(stdout, usage, argv[0]);
                exit(1);
            case 'v':
                verbose = 1;
                break;
            case 's':
                s = atoi(optarg);
                break;
            case 'E':
                E = atoi(optarg);
                break;
            case 'b':
                b = atoi(optarg);
                break;
            case 't':
                fp = fopen(optarg, "r");
                break;
            default:
                fprintf(stdout, usage, argv[0]);
                exit(1);
        }
    }
}

int simulate()
{
    int S = pow(2, s);
    cache = (Cache)malloc(sizeof(cacheSet) * S);
    if (cache == NULL) return -1;
    for (int i = 0; i < S; i++)
    {
        cache[i] = (cacheSet)calloc(E, sizeof(cacheLine));
        if (cache[i] == NULL) return -1;
    }

    char buf[20];
    char operation;
    uint64_t address;
    int size;

    while (fgets(buf, sizeof(buf), fp) != NULL)
    {
        int ret;

        if (buf[0] == 'I') //ignore instruction cache accesses
        {
            continue;
        }
        else
        {
            sscanf(buf, " %c %lx,%d", &operation, &address, &size);

            switch (operation)
            {
                case 'S':
                    ret = visitCache(address);
                    break;
                case 'L':
                    ret = visitCache(address);
                    break;
                case 'M':
                    ret = visitCache(address);
                    hits++;
                    break;
            }

            if (verbose)
            {
                switch(ret)
                {
                    case 0:
                        printf("%c %lx,%d hit\n", operation, address, size);
                        break;
                    case 1:
                        printf("%c %lx,%d miss\n", operation, address, size);
                        break;
                    case 2:
                        printf("%c %lx,%d miss eviction\n", operation, address, size);
                        break;
                }
            }
        }
    }

    for (int i = 0; i < S; i++)
        free(cache[i]);
    free(cache);
    fclose(fp);
    return 0;
}

/*return value
      0             cache hit
      1             cache miss
      2             cache miss, eviction
*/
int visitCache(uint64_t address)
{
    uint64_t tag = address >> (s + b);
    unsigned int setIndex = address >> b & ((1 << s) - 1);

    int evict = 0;
    int empty = -1;
    cacheSet cacheset = cache[setIndex];

    for (int i = 0; i < E; i++)
    {
        if (cacheset[i].valid)
        {
            if (cacheset[i].tag == tag)
            {
                hits++;
                cacheset[i].lru = 1;
                return 0;
            }

            cacheset[i].lru++;
            if (cacheset[evict].lru <= cacheset[i].lru) // =是必须的,why?
            {
                evict = i;
            }
        }
        else
        {
            empty = i;
        }
    }

    //cache miss
    misses++;

    if (empty != -1)
    {
        cacheset[empty].valid = 1;
        cacheset[empty].tag = tag;
        cacheset[empty].lru = 1;
        return 1;
    }
    else
    {
        cacheset[evict].tag = tag;
        cacheset[evict].lru = 1;
        evictions++;
        return 2;
    }
}

Part B

参考

总结