深入理解计算机系统CacheLab-PartA实验报告

实验答案托管在我的GitHub上

考完试之后一直比较颓废，本来想看完《深入理解计算机系统》的第5章——优化程序性能之后就赶快来做实验的，后来发现无论是Cache Lab还是Performance Lab都需要第6章——存储器层次结构的知识。看了几天的书，又磨蹭了几天，终于把Cache Lab的Part A写完了，总结如下。

实验简介

Cache Lab - Understanding Cache Memories主要是有关缓存的实验，对应于书本的第6章：存储器层次结构。主要阐明了缓存对于C语言程序的性能影响。

本实验主要分为两个部分。第一个部分要求完成一个C语言程序用来模拟缓存的行为；而第二个部分要求优化一个小的矩阵变换函数，使其具有尽可能小的缓存不命中率。

关于本实验的具体介绍详见实验讲义。

实验介绍

实验讲义中的traces子文件夹下包含了一组reference trace files，用来作为评估Part A中缓存模拟器正确性的样例数据。这些文件是由valgrind生成的。

Valgrind是一个用于内存调试，内存泄露以及性能分析的软件。例如，我们输入如下的命令：

1	linux> valgrind --log-fd=1 --tool=lackey -v --trace-mem=yes ls -l

valgrind会在命令行中执行ls -l命令并且按照顺序记录该命令的每一次内存访问，并且将其输出到标准输出流中。

下面是一个valgrind的输出样例：

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

每一行的基本格式如下：

1	[空格]操作地址,大小

操作代表了内存访问的种类，'I'代表的是指令加载，'L'代表的是数据加载，'S'代表的是数据存储，'M'代表的是数据修改（如一条数据加载之后紧跟着数据存储）。在'I'之前永远没有空格，而其他的操作前必定有前置空格。
地址代表的是一个64位的16进制内存地址。
大小指明了该次内存访问涉及的字节数。

实验要求 - Part A

在Part A中你需要在csim.c中实现一个LRU驱逐机制的缓存模拟器，该模拟器接收valgrind的trace作为输入，模拟一个缓存在该情况下的命中/不命中情况，并且输出所有的命中，不命中以及驱逐的次数。

本实验已经提供了一个用来参考的缓存模拟器csim-ref，其使用方式以及输出如下：

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 = 2 s is the number of sets)
• -E <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

linux> ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace
hits:4 misses:5 evictions:3

linux> ./csim-ref -v -s 4 -E 1 -b 4 -t traces/yi.trace
L 10,1 miss
M 20,1 miss hit
L 22,1 hit
S 18,1 hit
L 110,1 miss eviction
L 210,1 miss eviction
M 12,1 miss eviction hit
hits:4 misses:5 evictions:3

对于Part A有以下的要求和限制：

所写的程序编译时不能有任何的警告
能应对不同s，E和b的缓存生成对应的结果，这要求使用malloc来为你的数据结构分配空间
不需要考虑指令加载的缓存情况
调用printSummary打印最终的结果
假定数据已经适当对齐，不会出现一次数据加载跨区块的情况。这样，你可以忽略trace中的大小

除此以外，实验的自学者讲义中还包含了一些提示，这里就不再赘述。

完成了Part A之后，可以用make clean && make进行编译，并且用./test-csim进行自动评分，总共有8组样例，共27分满分。

实验过程 - Part A

实验思路

整个模拟器在思路上可以进行如下的拆分：

1.命令行参数解析

由于该模拟器是命令行程序并且接受命令行参数，因此需要能对命令行参数进行解析和处理，这里推荐使用getopt进行参数的解析。并且根据不同的参数执行不同的控制流，并且处理一些基本的错误如参数缺失以及参数类型错误。

2.数据结构

这是整个模拟器最基本的部分。我们需要创建合适的数据结构来模拟缓存，该数据结构不仅要能模拟缓存的数据的实际组织方式（有效位，标志位以及行和块等等），还需要考虑到LRU的驱逐机制。

3.文件中内存访问记录的处理和解析

这个是模拟器中核心的部分。模拟器的功能就是从文件中接收内存访问记录，并且根据这些记录来模拟缓存的行为，操作我们所设计的缓存的数据结构。

实验代码

该代码仅供参考，很可能并不是一个非常好的解法。如果你也在面对同样的实验，请不要抄袭，毕竟抄袭是不会使你变得更强的:)

/* include necessary headers */
#include "cachelab.h"

#include "getopt.h"
#include "stdlib.h"
#include "unistd.h"

#include "string.h"

#include "stdio.h"

#include "stdint.h"

/* cache struct definition */
typedef struct CSim_Cache_Entry {
    char valid_bit;
    uint64_t tag_bit;
}CSim_Cache_Entry;

typedef struct CSim_Cache_Set{
    CSim_Cache_Entry * entries;
}CSim_Cache_Set;

typedef struct CSim_Cache {
    /* basic arguments */
    int block_offset;
    int set_number;
    int line_number;
    /* masks and offsets */
    int tag_offset;
    int set_offset;
    uint64_t tag_mask;
    uint64_t set_mask;
    /* cache */
    CSim_Cache_Set * sets;
}CSim_Cache;

/* simulation result definition */
typedef struct CSim_Cache_Result {
    int hit;
    int miss;
    int evict;
}CSim_Cache_Result;

/* operation type definition */
typedef enum CSIM_OPERATION_TYPE {
    CSIM_OPERATION_TYPE_NONE,
    CSIM_OPERATION_TYPE_MODIFY,
    CSIM_OPERATION_TYPE_LOAD,
    CSIM_OPERATION_TYPE_STORE,
}CSIM_OPERATION_TYPE;

/* operation result definition */
typedef enum CSIM_OPERATION_RESULT {
    CSIM_OPERATION_RESULT_MISS,
    CSIM_OPERATION_RESULT_HIT,
    CSIM_OPERATION_RESULT_MISS_EVICTION,
}CSIM_OPERATION_RESULT;

/* error definition */
typedef enum CSIM_ERROR {
    CSIM_OK = 0,
    CSIM_ERROR_INVALID_OPTION,
    CSIM_ERROR_MISSING_ARGUMENT,
    CSIM_ERROR_FILE_CANNOT_OPEN,
    CSIM_ERROR_OUT_OF_MEMORY,
}CSIM_ERROR;

/* macro definition for get a value given mask and offset */
#define csim_get_value(number, mask, offset) (((number) & (mask)) >> (offset))

/* function list */
/* message print functions */
void csim_print_help_info();
void csim_error_missing_argument();
void csim_error_file_cannot_open();
void csim_error_out_of_memory();
/* cache structure related functions */
CSim_Cache * csim_construct_cache(int set_number, int line_number, int block_offset);
void csim_deconstruct_cache(CSim_Cache ** pcache);
/* cache simulation function */
CSim_Cache_Result csim_parse_trace_file(CSim_Cache * cache, FILE * file_pointer, char verbose_flag);

/* global variable */
char * program_name = NULL;

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

void csim_error_missing_argument() {
    printf("%s: Missing required command line argument\n", program_name);
    csim_print_help_info();
}

void csim_error_file_cannot_open() {
    printf("%s: No such file or directory\n", program_name);
}

void csim_error_out_of_memory() {
    printf("%s: Out of memory\n", program_name);
}

CSim_Cache * csim_construct_cache(int set_number, int line_number, int block_offset) {
    /* memory allocation */
    CSim_Cache * cache = malloc(sizeof(CSim_Cache));
    if (cache == NULL) {
        csim_error_out_of_memory();
        exit(CSIM_ERROR_OUT_OF_MEMORY);
    }
    /* configure basic arguments */
    cache->set_number = set_number;
    cache->line_number = line_number;
    cache->block_offset = block_offset;
    /* caculate masks and offsets */
    cache->tag_mask = ((uint64_t)0xFFFFFFFFFFFFFFFF) << (block_offset + set_number);
    cache->tag_offset = block_offset + set_number;
    cache->set_mask = ((((((uint64_t)0xFFFFFFFFFFFFFFFF) << (64 - cache->tag_offset)) >> (64 - cache->tag_offset)) >> block_offset) << block_offset);
    cache->set_offset = block_offset;
    /* memory allocation for cache */
    cache->sets = calloc((1 << set_number), sizeof(CSim_Cache_Set));
    if (cache->sets == NULL) {
        csim_error_out_of_memory();
        exit(CSIM_ERROR_OUT_OF_MEMORY);
    }
    for (int index = 0 ; index < (1 << set_number) ; ++index) {
        (cache->sets)[index].entries = calloc(line_number, sizeof(CSim_Cache_Entry));
        if ((cache->sets)[index].entries == NULL) {
            csim_error_out_of_memory();
            exit(CSIM_ERROR_OUT_OF_MEMORY);
        }
    }
    return cache;
}

void csim_deconstruct_cache(CSim_Cache ** pcache) {
    /* release cache according to construct function */
    CSim_Cache * temp = *pcache;
    int set_number = temp->set_number;
    for (int index = 0 ; index < set_number ; ++index) {
        free((temp->sets)[index].entries);
    }
    free(temp->sets);
    free(temp);
    *pcache = NULL;
}

CSim_Cache_Result csim_parse_trace_file(CSim_Cache * cache, FILE * file_pointer, char verbose_flag) {
    /* file I/O related */
    char line[80];
    char * line_pointer = NULL;
    /* cache type and cache result */
    CSIM_OPERATION_TYPE type;
    CSIM_OPERATION_RESULT result;
    /* address and set index & tag bis from it */
    int address = 0;
    int set = 0, tag = 0;
    /* line number */
    int line_number = cache->line_number;
    /* simulation result */
    CSim_Cache_Result summary = {0, 0, 0};
    /* parsing process */
    while (fgets(line, 80, file_pointer), feof(file_pointer) == 0) {
        line_pointer = line;
        type = CSIM_OPERATION_TYPE_NONE;
        /* exclude instrction load */
        if (*line_pointer++ == ' ') {
            switch(*line_pointer++) {
                case 'L':
                    type = CSIM_OPERATION_TYPE_LOAD;
                    if (verbose_flag) {
                        putchar('L');
                    }
                    break;
                case 'S':
                    type = CSIM_OPERATION_TYPE_STORE;
                    if (verbose_flag) {
                        putchar('S');
                    }
                    break;
                case 'M':
                    type = CSIM_OPERATION_TYPE_MODIFY;
                    if (verbose_flag) {
                        putchar('M');
                    }
                    break;
                default:
                    type = CSIM_OPERATION_TYPE_NONE;
                    break;
            }
            result = CSIM_OPERATION_RESULT_MISS_EVICTION;
            sscanf(line_pointer, "%x", &address);
            if (verbose_flag) {
                while ((*line_pointer) != '\n') {
                    putchar(*line_pointer++);
                }
            }
            /* separate set and tag according to mask and offset */
            set = csim_get_value(address, cache->set_mask, cache->set_offset);
            tag = csim_get_value(address, cache->tag_mask, cache->tag_offset);
            /* determine the cache result */
            CSim_Cache_Entry * pentry = (cache->sets)[set].entries;
            int index;
            CSim_Cache_Entry temp;
            for (index = 0; index < line_number ; ++index) {
                if (!pentry[index].valid_bit) {
                    result = CSIM_OPERATION_RESULT_MISS;
                    break;
                }
                if (pentry[index].tag_bit == tag) {
                    result = CSIM_OPERATION_RESULT_HIT;
                    break;
                }
            }
            /* simulate according to the result of cache behavior */
            switch(result) {
                case CSIM_OPERATION_RESULT_MISS:
                    if (verbose_flag) {
                        printf(" miss");
                    }
                    pentry[index].valid_bit = 1;
                    pentry[index].tag_bit = tag;
                    summary.miss++;
                    break;
                case CSIM_OPERATION_RESULT_MISS_EVICTION:
                    if (verbose_flag) {
                        printf(" miss eviction");
                    }
                    pentry[0].tag_bit = tag;
                    temp = pentry[0];
                    for (index = 0 ; index < line_number - 1 ; ++index) {
                        pentry[index] = pentry[index + 1];
                    }
                    pentry[index] = temp;
                    summary.miss++;
                    summary.evict++;
                    break;
                case CSIM_OPERATION_RESULT_HIT:
                    if (verbose_flag) {
                        printf(" hit");
                    }
                    temp = pentry[index];
                    for ( ; (index < line_number - 1) && (pentry[index + 1].valid_bit) ; ++index) {
                        pentry[index] = pentry[index + 1];
                    }
                    pentry[index] = temp;
                    summary.hit++;
                    break;
            }
            if (type == CSIM_OPERATION_TYPE_MODIFY) {
                if (verbose_flag) {
                    printf(" hit");
                }
                summary.hit++;
            }
            if (verbose_flag) {
                putchar('\n');
            }
        }
    }
    return summary;
}

int main(int argc, char *argv[]) {
    /* variables for argument parsing */
    char h = 0, v = 0, s = 0, E = 0, b = 0, t = 0;
    int opt;
    /* cache arguments */
    int set_number = 0, line_number = 0, block_offset = 0;
    /* cache */
    CSim_Cache * cache = NULL;
    /* file path */
    char file_path[80];
    /* verbose flag */
    char verbose_flag = 0;
    /* summary */
    CSim_Cache_Result summary = {0, 0, 0};
    /* pre-operation */
    program_name = argv[0];
    /* argument parsing */
    while ((opt = getopt(argc, argv, "hvs:E:b:t:")) != -1) {
        switch(opt) {
            case 'h':
                h = 1;
                break;
            case 'v':
                v = 1;
                verbose_flag = 1;
                break;
            case 's':
                set_number = atoi(optarg);
                if (set_number == 0) {
                    csim_error_missing_argument();
                    return CSIM_ERROR_MISSING_ARGUMENT;
                }
                s = 1;
                break;
            case 'E':
                line_number = atoi(optarg);
                if (line_number == 0) {
                    csim_error_missing_argument();
                    return CSIM_ERROR_MISSING_ARGUMENT;
                }
                E = 1;
                break;
            case 'b':
                block_offset = atoi(optarg);
                if (block_offset == 0) {
                    csim_error_missing_argument();
                    return CSIM_ERROR_MISSING_ARGUMENT;
                }
                b = 1;
                break;
            case 't':
                t = 1;
                strcpy(file_path, optarg);
                break;
            default:
                csim_print_help_info();
                return CSIM_ERROR_INVALID_OPTION;
                break;
        }
    }
    if (h == 1) {
        csim_print_help_info();
        return CSIM_OK;
    }
    if (v == 1) {
        verbose_flag = 1;
    }
    if (!(s == 1 && E == 1 && b == 1 && t == 1)) {
        csim_error_missing_argument();
        return CSIM_ERROR_MISSING_ARGUMENT;
    }
    /* file processing */
    FILE * file_pointer = fopen(file_path, "r");
    if (file_pointer == NULL) {
        csim_error_file_cannot_open(file_path);
        return CSIM_ERROR_FILE_CANNOT_OPEN;
    }
    /* cache construction */
    cache = csim_construct_cache(set_number, line_number, block_offset);
    /* trace file parsing */
    summary = csim_parse_trace_file(cache, file_pointer, verbose_flag);
    /* summary */
    printSummary(summary.hit, summary.miss, summary.evict);
    /* post operations */
    csim_deconstruct_cache(&cache);
    fclose(file_pointer);
    return CSIM_OK;
}

实验结果

自动评分脚本给出的输出如下：

user@blackdragon ~/C/C/cachelab-handout> ./test-csim
                        Your simulator     Reference simulator
Points (s,E,b)    Hits  Misses  Evicts    Hits  Misses  Evicts
     3 (1,1,1)       9       8       6       9       8       6  traces/yi2.trace
     3 (4,2,4)       4       5       2       4       5       2  traces/yi.trace
     3 (2,1,4)       2       3       1       2       3       1  traces/dave.trace
     3 (2,1,3)     167      71      67     167      71      67  traces/trans.trace
     3 (2,2,3)     201      37      29     201      37      29  traces/trans.trace
     3 (2,4,3)     212      26      10     212      26      10  traces/trans.trace
     3 (5,1,5)     231       7       0     231       7       0  traces/trans.trace
     6 (5,1,5)  265189   21775   21743  265189   21775   21743  traces/long.trace
    27

TEST_CSIM_RESULTS=27

实验总结

由于在寒假的课程设计中已经使用过了命令行参数解析以及复杂的数据结构设计与实验，Part A总体上来说不是很难，我主要的精力花费在代码风格上，希望代码能尽量具有良好的架构以及可读性。

本部分中犯的错误有，直接根据s设置缓存的组数，而实际上的组数是2^s个。循环中由于手误导致出现死循环。没有搞清楚inline static关键字而导致的编译错误等等。存在知识的盲区也存在着粗心导致的错误，以后还需要更加注意。