1 下载

相关的 Handout 点击这里下载。

下载后将文件上传到 Linux 服务器,然后使用命令 tar xvf cachelab-handout.tar 解压。在解压后的诸多文件里,csim.ctrans.c 这两个文件是本实验涉及到修改的。

执行下面的命令可以进行编译:

linux> make clean
linux> make

2 介绍

这个实验将帮助你理解缓存对你的 C 程序的影响。

这个实验包括两部分。第一部分要求写一个 200 ~ 300 行的 C 程序,来模拟缓存的行为。在第二部分,你将会优化一个小的矩阵转置函数,来减少缓存不命中。

2.1 Reference Trace Files

解压后的文件中,traces 子文件夹包括一些 reference trace files。在 Part A 中,这些文件可以帮助你评估你代码的正确性。

这些 trace files 是由 Valgrind 生成的。例如,输入命令:

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

来捕获执行 ls -l 时的每一次 memory accesses 。并将相关信息打印到 stdout。格式如下:

I 0400d7d4, 8
M 0421c7f0, 4
L 04f6b868, 8
S 7ff0005c8,8
[空格]operation address,size

operation 指明了 memory access 的类型:

  1. “I” 是指令 load。
  2. “L” 是数据 load。
  3. “S” 是数据 store。
  4. “M” 是数据 modify(即数据 load + 数据 store)。

“I” 前面是不能有空格的。其余 3 种情况通常会有空格。

address 指明了一个 64 bit - 16 进制的内存地址。

size 指明了当前 memory access 操作的字节数。

2.2 Part A:Writing a Cache Simulator

在编写的 csim.c 中,将会以 trace 文件作为输入,来模拟在这个 trace 文件上的 hit/miss 行为。最后输出全部的 hit/miss/eviction。

实验文件夹中提供了可执行的缓存模拟器二进制文件,叫做csim-ref。它使用了 LRU 置换策略,来选择淘汰哪个 Cache Line

这个模拟器需要以下参数:

Usage: ./csim-ref [-hv] -s <s> -E <E> -b <b> -t <tracefile>
  1. -h: Optional help flag that prints usage info
  2. -v: Optional verbose flag that displays trace info
  3. -s: Number of set index bits
  4. -E: Associativity (number of lines per set)
  5. -b: Number of block bits
  6. -t: 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

如果想要显示详细的 memory access 信息,可以加上 -v(该 Part 是不强制要求实现 -v 参数功能的)。

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 的任务就是在 csim.c 中编写相应的 C 代码,使用相同的命令行参数,输出的内容也要和上面相同。

csim.c 几乎是空的,要想完成这个 Part,可以参考下面的几条规则:

  1. 编译 csim.c 文件的时候不能有警告。
  2. csim.c 对于任意的 -s-E-b 参数都应该能正常运行。
  3. 在编写时,需要使用 malloc 函数来分配空间。执行 man malloc 来查看该函数的相关手册。
  4. 这个实验里,我们关注的是数据的缓存性能。所以请忽略指令的相关内容(即以 I 开头的行)
  5. 在 main 函数最后,需要调用这个函数 printSummary(hit_count, miss_count, eviction_count)

2.3 Part A 的评估

linux> ./csim -s 1 -E 1 -b 1 -t traces/yi2.trace
linux> ./csim -s 4 -E 2 -b 4 -t traces/yi.trace
linux> ./csim -s 2 -E 1 -b 4 -t traces/dave.trace
linux> ./csim -s 2 -E 1 -b 3 -t traces/trans.trace
linux> ./csim -s 2 -E 2 -b 3 -t traces/trans.trace
linux> ./csim -s 2 -E 4 -b 3 -t traces/trans.trace
linux> ./csim -s 5 -E 1 -b 5 -t traces/trans.trace
linux> ./csim -s 5 -E 1 -b 5 -t traces/long.trace

执行上面 8 条命令来对你写的 csim.c 进行评估。

你可以使用参考的模拟器 csim-ref 来获得每个测试项正确的答案。

2.4 开始 Part A

本部分实验中,提供了自动测试的程序 test-csim,通过这个运行这个程序可以查看我们获得的分数。

运行test-csim

在开始 Part A 之前注意以下几点:

  1. 开始可以尝试 Debug 一些小文件,例如 traces/dave.trace.
  2. 建议在自己实现的模拟器里也支持 -v 功能
  3. 建议使用 getopt() 函数来获得命令行参数
#include <getopt.h>
#include <stdlib.h>
#include <unistd.h>

在代码中引入这 3 个头文件即可,man 3 getopt 查看手册。

  1. 每次数据 load (L) 或者 store (S) 最多造成一次缓存不命中,因此数据 modify(M)最多造成两次命中,或者一次命中、一次不命中和一次可能的 eviction

解题思路:

使用 getopt() 函数来接受命令行的输入。输入分两类:一类是 trace 文件;另一类是 -s -E -b 参数。

需要一个结构体来模拟 cache line。使用 -s -E -b 参数来组织 cache line。举一个例子:

如果程序接受 ./csim -s 2 -E 1 -b 4 -t traces/dave.trace 输入。dave.trace 文件如下:

 L 10,4 
 S 18,4
 L 20,4
 S 28,4
 S 50,4

以第一行为例,处理器要求读取内存起始位置为 0x10,一共 4 个字节。 首先解析 0x10 地址,由 -s -b 的参数值和内存地址为 64 bit 可知,内存地址 3 个域划分如下:

address field 划分图

由 -s -b -E 的参数值和上面计算出的 Tag 的位数(t = m − (s + b)),可以大致画出 Cache 的结构如下:

该参数下的 Cache 结构

接下来就可以根据书中的相应规则来判断 Load 操作是否 Cache Hit 了(对应 store 规则会有些许区别)。这个判断是整个程序的核心,下面以完整的程序为例:

#include "cachelab.h"
#include "getopt.h"
#include "stdlib.h"
#include "unistd.h"
#include "string.h"
#include "stdio.h"
#include "stdint.h"
#include "math.h"
#include "time.h"

typedef struct operation_result
{
  int miss_count;
  int hit_count;
  int eviction_count;

} operation_result;

typedef struct process_address_result
{
  int s;
  int S;
  int t;
  int T;
} process_address_result;

// 描述 cache line 的结构
typedef struct cache_line_sim
{
  int valid;
  int T;
  // 每次 cache hit 都要更新这个时间戳
  clock_t time;
  // 由于我们只考虑 hit 或 miss 的情况,所以结构体内不需要 block
  // char[32] cache_block;
} cache_line_sim;

// 描述 cache set 的结构
typedef struct cache_set_sim
{
  cache_line_sim *cache_line;
  int E;

} cache_set_sim;

// 描述整个 cache 的结构
typedef struct cache_sim
{
  cache_set_sim *cache_set;
  int S;

} cache_sim;

operation_result *process_trace_file(cache_sim *cache, FILE *fp, int t, int b);

void load_operation(operation_result *result, cache_sim *cache, process_address_result *address_result);

void store_operation(operation_result *result, cache_sim *cache, process_address_result *address_result);

cache_sim *cache_sim_orgnized(int s, int E);

int main(int argc, char *argv[])
{

  cache_sim *cache;

  operation_result *result = malloc(sizeof(operation_result));
  // -s
  int s;
  // -E
  int E;
  // -b
  int b;
  // 指定命令行参数 -s -b 下,address 中 Tag 所占的 bit 数
  // m s b 决定了 t,s E b t 决定了整个 cache
  int t;
  char *trace_file_path;
  int opt;
  FILE *fp;
  while ((opt = getopt(argc, argv, "vs:E:b:t:")) != -1)
  {
    switch (opt)
    {
    case 's':
      s = atoi(optarg);
      break;
    case 'E':
      E = atoi(optarg);
      break;
    case 'b':
      b = atoi(optarg);
      break;
    case 't':
      trace_file_path = optarg;
      break;
    default:
      break;
    }
  }
  t = 64 - s - b;
  //  以只读模式打开文件
  fp = fopen(trace_file_path, "r");
  cache = cache_sim_orgnized(s, E);
  result = process_trace_file(cache, fp, t, b);
  printSummary(result->hit_count, result->miss_count, result->eviction_count);
  free(cache);
  free(result);
  return 0;
}

void load_operation(operation_result *operation_result, cache_sim *cache, process_address_result *address_result)
{
  cache_set_sim cache_set;
  cache_line_sim cache_line;
  int E = cache->cache_set->E;
  int i;
  int hit_flag = 0;
  int eviction_flag = 1;
  // TODO [] 是否相当于对指针做 * 运算了?
  // TODO = 是否会将内存中的值加载进 cache_set 变量对应的寄存器?
  cache_set = cache->cache_set[address_result->S];

  for (i = 0; i < E; i++)
  {
    cache_line = cache_set.cache_line[i];
    if (cache_line.valid == 1 && cache_line.T == address_result->T)
    {
      // load hit
      operation_result->hit_count++;
      cache_line.time = clock();
      hit_flag = 1;
      break;
    }
  }

  // 如果每个 cache line 都没找到的话,就说明 cahche miss
  if (hit_flag == 0)
  {
    operation_result->miss_count++;
    // cache must fetch block that contains the word from memory
    // 如果有空的 cache line,直接将取的 block 放进去
    for (i = 0; i < E; i++)
    {
      cache_line = cache_set.cache_line[i];
      if (cache_line.valid == 0)
      {
        cache_line.valid = 1;
        cache_line.T = address_result->T;
        cache_line.time = clock();
        eviction_flag = 0;
        break;
      }
    }

    if (eviction_flag == 1)
    {
      // 如果空的 cache line,则使用时间戳对比,选择时间戳最大的置换掉,并计数
      int LRU_line_index = 0;
      for (i = 1; i < E; i++)
      {
        if (cache_set.cache_line[i - 1].time < cache_set.cache_line[i].time)
        {
          LRU_line_index = i;
        }
      }
      // 置换第 LRU_line_index 行 cache line
      cache_set.cache_line[LRU_line_index].T = address_result->T;
      cache_set.cache_line[LRU_line_index].valid = 1;
      cache_set.cache_line[LRU_line_index].time = clock();
      operation_result->eviction_count++;
    }
  }
}

void store_operation(operation_result *operation_result, cache_sim *cache, process_address_result *address_result)
{
  // data store 的情况有些复杂,请看下面的分析:
  // data store 也即 write,详细规则可见 6.4.5 Issues with Writes,下面贴出书中关键的几句话
  // Suppose we write a word w that is already cached(a write hit)
  // After the cache updates its copy of w in cache, what does it do about updating the copy of w in the next lower level of the hierarchy?
  // 可见 data store 首先是要更新对应 cache,然后再 updating the copy of w in the next lower level of the hierarchy
  // 更新下一层有两种方法 1. write-through(立刻 Update 下一层)   2. write-back(稍后 Update 下一层)
  //
  // Another issue is how to deal with write misses
  // 如果 write miss 了,必然说明 write 所携带地址所在的 block 没有被 cache,则必然也就不必 updates its copy of w in cache 了
  // 直接 write next lower level,更新下一层也有两种方法 1. write-allocate 2. no-write-allocate
  // 通过再次阅读 6.4.5 节,得出了一个结论:只要 cache hit(No matter load or store),cache 中的数据要么和 next level 一样,要么比 next level 新。

  // 开始执行,先判断 write miss or write hit
  cache_set_sim cache_set;
  cache_line_sim cache_line;
  int E = cache->cache_set->E;
  int i;
  int hit_flag = 0;
  // TODO [] 是否相当于对指针做 * 运算了?
  // TODO = 是否会将内存中的值加载进 cache_set 变量对应的寄存器?
  cache_set = cache->cache_set[address_result->S];
  for (i = 0; i < E; i++)
  {
    cache_line = cache_set.cache_line[i];
    if (cache_line.valid == 1 && cache_line.T == address_result->T)
    {
      // store hit
      // 一个完整的缓存在 store hit 后,应该还会更新缓存相应的数据,且采用 write-through 或者 write-back 更新下一级的相应数据
      // 但是由于本实验的特殊性,就省略了这个步骤
      operation_result->hit_count++;
      cache_line.time = clock();
      hit_flag = 1;
      break;
    }
  }
  if (hit_flag == 0)
  {
    // store miss
    operation_result->miss_count++;
    // 同上省略更新相应数据的步骤
  }
}

operation_result *process_trace_file(cache_sim *cache, FILE *fp, int t, int b)
{

  operation_result *operation_result = malloc(sizeof(operation_result));
  process_address_result *address_result = malloc(sizeof(process_address_result));

  char *trace_line_buffer = trace_line_buffer = malloc(sizeof(char) * 255);

  char operation;
  unsigned long address;
  int byte;
  // 遍历 trace 文件的每一行
  while (fscanf(fp, " %c %lx,%d", &operation, &address, &byte) != EOF)
  {
    if (operation == 'I')
    {
      continue;
    }
    // 处理 address,此时已经把字符串中的地址当做十六进制保存了
    //  | --Tag-- | --Set-- | --Block-- |
    address_result->t = t;
    address_result->T = address >> (64 - t);
    address_result->s = 64 - b - t;
    address_result->S = (address << t) >> (b + t);
    switch (operation)
    {
    case 'L':
      load_operation(operation_result, cache, address_result);
      break;
    case 'S':
      store_operation(operation_result, cache, address_result);
      break;
    case 'M':
      load_operation(operation_result, cache, address_result);
      store_operation(operation_result, cache, address_result);
      break;
    default:
      break;
    }
  }
  return operation_result;
}

cache_sim *cache_sim_orgnized(int s, int E)
{
  // cache_sim *cache = (cache_sim *)malloc(sizeof(cache_line_sim) * E * pow(2, s));
  int S = pow(2, s);
  cache_sim *cache;
  cache_line_sim *cache_line;
  int i;
  for (i = 0; i < S; i++)
  {
    // 将每个 set 指向 这组 cache line 的首地址
    int j;
    for (j = 0; j < E; j++)
    {
      cache_line = (cache_line_sim *)malloc(sizeof(cache_line_sim));
      // 为 cache 的 cache line 赋上响应的地址值
      // TODO 如何将一个地址,赋值给一个变量,目前只知道这个的首变量,但是要赋值给首变量后面的某个变量,数组不能满足要求
      cache->cache_set[i].cache_line[j] = cache_line;
      if (i == 0 && j == 0)
      {
        cache = (cache_sim *)cache_line;
      }
      if (j == 0)
      {
        cache->cache_set[i] = (cache_set_sim *)cache_line;
      }
    }
  }
  // 运行到此处出现 Segmentation Fault
  // (gdb) print *cache
  // $3 = {cache_set = 0x0, S = 0}
  // 说明分配模拟 cache 的内存有点问题,返回上面重新组织 cache 的内存
  cache->cache_set->E = E;
  cache->S = S;
  return cache;
}

./csim-ref -s 2 -E 1 -b 4 -t traces/dave.trace的输出