Solution
Part A
代码
#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>
#include "cachelab.h"
/* defines */
#define OPTSTRING "hvs:E:b:t:"
#define INF 2147483647
#define HELP_MESSAGE \
"Usage: ./csim [-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 -s 4 -E 1 -b 4 -t traces/yi.trace\n" \
" linux> ./csim -v -s 8 -E 2 -b 4 -t traces/yi.trace"
typedef struct Line {
int valid;
unsigned long tag;
int timeStamp;
} Line;
typedef struct Set {
Line *lines;
} Set;
int time = 0;
int newTimeStamp() {
time++;
return time;
}
struct Cache {
int s;
int E;
int b;
Set *sets;
} C;
int hitCount = 0;
int missCount = 0;
int evictionCount = 0;
/* enums */
enum OutputFlag : int { VERBOSE, SILENT } outputMode = SILENT;
/* M for miss, E for eviction, H for hit */
typedef enum : int {
M = 1 << 0,
E = 1 << 1,
H = 1 << 2,
} CheckFlag;
/* inits */
/* initialize the cache, use malloc */
void initCache(int s, int E, int b) {
C.s = s;
C.E = E;
C.b = b;
C.sets = (Set *)malloc(sizeof(Set) * ((size_t)1 << s));
for (unsigned long i = 0; i < (unsigned long)1 << s; i++) {
C.sets[i].lines = (Line *)malloc(sizeof(Line) * E);
for (int j = 0; j < E; j++) {
C.sets[i].lines[j].valid = 0;
C.sets[i].lines[j].tag = 0;
C.sets[i].lines[j].timeStamp = time;
}
}
}
/* outputs */
/* verbosely output the flag */
void verbosely(CheckFlag flag) {
if (flag & M) {
printf("miss ");
}
if (flag & E) {
printf("eviction ");
}
if (flag & H) {
printf("hit ");
}
}
/* processes */
/*
* process the flag
* add to the corresponding counter
*/
void processFlag(CheckFlag flag) {
hitCount += !!(flag & H);
missCount += !!(flag & M);
evictionCount += !!(flag & E);
if (outputMode == VERBOSE) {
verbosely(flag);
}
}
/* use bit tricks to get the set index of the address */
unsigned long getSetIndex(unsigned long address) {
return (address >> C.b) & (((unsigned long)1 << C.s) - 1);
}
/* use bit tricks to get the tag of the address */
unsigned long getTag(unsigned long address) {
return address >> (C.s + C.b);
}
/* process a load operation */
void processLoad(unsigned long address) {
unsigned long setIndex = getSetIndex(address);
unsigned long tag = getTag(address);
int lruId = 0, lruTimeStamp = INF;
for (int i = 0; i < C.E; i++) {
Line *l = &C.sets[setIndex].lines[i];
if (l->valid && l->tag == tag) {
l->timeStamp = newTimeStamp();
processFlag(H);
return;
}
if (lruTimeStamp > l->timeStamp) {
lruTimeStamp = l->timeStamp;
lruId = i;
}
}
CheckFlag flag = M;
Line *lruL = &C.sets[setIndex].lines[lruId];
if (lruL->valid) {
flag |= E;
}
lruL->valid = 1;
lruL->tag = tag;
lruL->timeStamp = newTimeStamp();
processFlag(flag);
}
/*
* process a store operation
* the same as load operation
*/
void processStore(unsigned long address) {
processLoad(address);
}
/*
* process a modify operation
* first load then modify
*/
void processModify(unsigned long address) {
processLoad(address);
processStore(address);
}
/* process a line in the trace file */
void processLine(char *line) {
if (line[0] != ' ') {
return;
}
char type;
unsigned long address;
int size;
if (sscanf(line, " %c %lx,%d", &type, &address, &size) != 3) {
printf("invalid line: %s\n", line);
exit(EXIT_FAILURE);
}
if (outputMode == VERBOSE) {
printf("%c %lx,%d ", type, address, size);
}
switch (type) {
case 'L':
processLoad(address);
break;
case 'S':
processStore(address);
break;
case 'M':
processModify(address);
break;
default:
printf("invalid type: %c\n", type);
exit(EXIT_FAILURE);
break;
}
if (outputMode == VERBOSE) {
puts("");
}
}
/* implement the function that is called by main */
void implement(int argc, char *argv[]) {
char opt;
FILE *fp;
int s, E, b;
while ((opt = getopt(argc, argv, OPTSTRING)) != -1) {
switch (opt) {
case 'h':
printf(HELP_MESSAGE);
exit(EXIT_SUCCESS);
break;
case 'v':
outputMode = VERBOSE;
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");
if (fp == NULL) {
printf("cannot open");
exit(EXIT_FAILURE);
}
break;
default:
break;
}
}
if (s == 0 || E == 0 || b == 0 || fp == NULL) {
printf("missing argument\n");
exit(EXIT_FAILURE);
}
initCache(s, E, b);
while (fp != NULL) {
char buf[100];
if (fgets(buf, sizeof(buf), fp) == NULL) {
break;
}
processLine(buf);
}
}
int main(int argc, char *argv[]) {
implement(argc, argv);
printSummary(hitCount, missCount, evictionCount);
return 0;
}
Defines
OPTSTRING
#define OPTSTRING "hvs:E:b:t:"
描述：
OPTSTRING 是用于解析命令行选项的字符串。它包含了可用选项的列表，每个选项由一个字母表示，后面可以跟随一个冒号表示该选项需要一个参数。
INF
#define INF 2147483647
描述：
INF 是一个表示正无穷大的常量。在程序中，它用于表示一个很大的时间戳值，用于标识最近的时间戳。
HELP_MESSAGE
#define HELP_MESSAGE \
"Usage: ./csim [-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 -s 4 -E 1 -b 4 -t traces/yi.trace\n" \
" linux> ./csim -v -s 8 -E 2 -b 4 -t traces/yi.trace"
描述：
HELP_MESSAGE 是程序的帮助消息字符串，用于显示程序的使用方法和可用选项，以及一些示例用法。
Line 结构体
typedef struct Line {
int valid;
unsigned long tag;
int timeStamp;
} Line;
描述：
Line 结构体表示缓存中的一行。它包含了有效位、标记和时间戳等属性，用于表示缓存中的一行数据。
成员变量：
valid：表示该行是否有效的标志。如果为 1，则表示该行有效；如果为 0，则表示该行无效。tag：表示该行对应的标记值，用于标识缓存中存储的数据所属的地址范围。timeStamp：表示该行的时间戳，用于记录该行最近一次被访问或修改的时间。
Set 结构体
typedef struct Set {
Line *lines;
} Set;
描述：
Set 结构体表示缓存中的一组。它包含了一组 Line 结构体的数组，用于表示缓存中的多行数据。
成员变量：
lines：表示一组缓存行的数组。每个元素都是一个Line结构体，用于表示缓存中的一行数据。
Cache 结构体
struct Cache {
int s;
int E;
int b;
Set *sets;
} C;
描述：
Cache 结构体表示整个缓存系统。它包含了缓存的一些基本参数以及一组 Set 结构体的数组，用于表示缓存中的多组数据。
成员变量：
s：表示缓存的组索引位数。E：表示每组的行数。b：表示块偏移位数。sets：表示缓存中的多组数据。每个元素都是一个Set结构体，用于表示缓存中的一组数据。
Function
initCache
void initCache(int s, int E, int b)
描述：
初始化缓存，分配内存并设置初始值。
参数：
s：缓存的组索引位数。E：每组的行数。b：块偏移位数。
verbosely
void verbosely(CheckFlag flag)
描述：
根据给定的标志以详细模式输出缓存操作信息。
参数：
flag：表示缓存操作类型的标志。
processFlag
void processFlag(CheckFlag flag)
描述：
处理缓存操作的标志，更新相应的计数器。
参数：
flag：表示缓存操作类型的标志。
getSetIndex
unsigned long getSetIndex(unsigned long address)
描述：
根据给定的内存地址计算并返回相应的组索引。
参数：
address：内存地址。
返回值：
返回计算得到的组索引。
getTag
unsigned long getTag(unsigned long address)
描述：
根据给定的内存地址计算并返回相应的标记。
参数：
address：内存地址。
返回值：
返回计算得到的标记。
processLoad
void processLoad(unsigned long address)
描述：
处理加载操作。
参数：
address：加载操作的内存地址。
processStore
void processStore(unsigned long address)
描述：
处理存储操作，在模拟冲突逻辑上和processLoad一致。
参数：
address：存储操作的内存地址。
processModify
void processModify(unsigned long address)
描述：
处理修改操作，在模拟冲突上相当于一次processLoad操作和processStore操作。
参数：
address：修改操作的内存地址。
processLine
void processLine(char *line)
描述：
逻辑步骤：
解析操作类型、地址和大小：
从输入的字符串中解析出操作类型、内存地址和大小。
操作类型可以是加载(L)、存储(S)或修改(M)。
内存地址表示操作所涉及的内存地址。
大小表示操作所涉及的内存大小。
执行相应的操作：
根据解析得到的操作类型，调用相应的处理函数执行操作。
- L: 调用 processLoad 函数处理加载操作。
- S: 调用 processStore 函数处理存储操作。
- M: 调用 processModify 函数处理修改操作。
参数：
line：跟踪文件中的一行文本。
implement
void implement(int argc, char *argv[])
描述：
实现主要逻辑，解析命令行参数并执行相应操作。
参数：
argc：命令行参数数量。argv：命令行参数数组。
main
int main(int argc, char *argv[])
描述：
程序的入口点，调用 implement 函数执行主要逻辑。
参数：
argc：命令行参数数量。argv：命令行参数数组。
LRU
时间戳的定义：
int time = 0;
time是一个全局变量，用于记录当前的时间戳值。- 初始值为 0，表示时间戳的初始时间。
更新时间戳的方法：
int newTimeStamp() {
time++;
return time;
}
newTimeStamp函数用于更新时间戳的值，并返回更新后的时间戳。- 每次调用
newTimeStamp函数，时间戳time的值会增加 1，表示时间的流逝。 - 在缓存行被访问时，会调用
newTimeStamp函数来更新该行的时间戳。
时间戳的使用：
在缓存行的结构体中，每个缓存行都有一个时间戳属性，用于记录该行最近一次被访问或修改的时间。在处理加载、存储和修改等操作时，会根据当前时间戳的值来更新相应缓存行的时间戳。
typedef struct Line {
int valid;
unsigned long tag;
int timeStamp;
} Line;
逻辑：
- 当加载、存储或修改操作需要访问缓存行时，会检查该行的时间戳，并将当前时间戳的值赋给该行。
- 这样，可以通过比较时间戳来确定缓存行的访问顺序，从而实现最近最少使用（LRU）策略或其他替换策略。
- 时间戳的更新保证了每次访问缓存行时都能更新该行的访问时间，从而维护了缓存行的访问顺序。
Part B
实验参数是$s=5,E=1,b=5$
给出的是一个直接映射缓存，有$2^5=32$组，每个块有$2^5=32$个字节，可以存$8$个int，也就是每次读取或存储会加载$8$个int大小的块
总共的存储大小合起来就是$32*8=256$个int
样例给出的暴力转置方式，对$B$数组以列模式进行访问，显然不满足良好的空间局部性
然而对于A数组的访问却是高效的one-step，在优化过程必须考虑综合A、B的访问时间
32x32
我们发现transpose这一操作不可避免地将$A$的行映射到$B$的列，如果简单地按“行-列”的访问模式对$A$进行操作，则一定会造成大量的访问冲突
考虑能否在连续访问$A$时是否能同时连续访问$B$，也就是每次尽量访问将$A$与$B$的不重叠的相对应部分
对矩阵进行分块。首先考虑不在对角线的情况，我们很容易想到一种分块方法：由于每个缓存块是$8$个int，我们干脆把块的大小设置成$8*8$。
对角线的话用临时变量一次读一行优化一下
实现一下：
for (int i = 0; i < N; i += 8) {
for (int j = 0; j < M; j += 8) {
for (int k = 0; k < 8; k++) {
int tmp0 = A[i + k][j];
int tmp1 = A[i + k][j + 1];
int tmp2 = A[i + k][j + 2];
int tmp3 = A[i + k][j + 3];
int tmp4 = A[i + k][j + 4];
int tmp5 = A[i + k][j + 5];
int tmp6 = A[i + k][j + 6];
int tmp7 = A[i + k][j + 7];
B[j][i + k] = tmp0;
B[j + 1][i + k] = tmp1;
B[j + 2][i + k] = tmp2;
B[j + 3][i + k] = tmp3;
B[j + 4][i + k] = tmp4;
B[j + 5][i + k] = tmp5;
B[j + 6][i + k] = tmp6;
B[j + 7][i + k] = tmp7;
}
}
}
得到不考虑对角线的情况：
Summary for official submission (func 0): correctness=1 misses=288
考虑继续分块，块大小必定小于$8$，因为一个地方最少要用两次（读，存），再乱搞misses肯定会增加，就不知道怎么搞了
参考了一下网上的博客，发现原来可以先把$A$复制到$B$的对应位置，然后再对$B$转置，这样行和列就不会冲突了，只需要读写一次
也就是：
#define swap(a, b) (a) ^= (b) ^= (a) ^= (b)
for (int i = 0; i < N; i += 8) {
for (int j = 0; j < M; j += 8) {
for (int k = 0; k < 8; k++) {
int tmp0 = A[i + k][j];
int tmp1 = A[i + k][j + 1];
int tmp2 = A[i + k][j + 2];
int tmp3 = A[i + k][j + 3];
int tmp4 = A[i + k][j + 4];
int tmp5 = A[i + k][j + 5];
int tmp6 = A[i + k][j + 6];
int tmp7 = A[i + k][j + 7];
B[j + k][i] = tmp0;
B[j + k][i + 1] = tmp1;
B[j + k][i + 2] = tmp2;
B[j + k][i + 3] = tmp3;
B[j + k][i + 4] = tmp4;
B[j + k][i + 5] = tmp5;
B[j + k][i + 6] = tmp6;
B[j + k][i + 7] = tmp7;
}
for (int k = 0; k < 8; k++) {
for (int l = k + 1; l < 8; l++) {
swap(B[j + k][i + l], B[j + l][i + k]);
}
}
}
}
结果：
Summary for official submission (func 0): correctness=1 misses=260
64x64
这里扩大了一倍行和列，之前本来存一个$88$的块到这里不可行了，因为每次往下走一行的偏置$+8$，原来是$48=32$刚好不冲突用完所有组，这里$8*8=64$肯定会发生冲突了
如果缩小分块的大小，比如采用$4*4$的块，由于每次只存$4$个，最后的还要读取和写入的冲突因为步长短了一倍而多一倍，还是和之前一样
这里关键的一点是考虑一行一行的冲突，行冲突并不会造成一个块的冲突，于是可以考虑每次按$88$分块，然后按照$44$的块大小进行转移操作后再transpose
思路是对于两个对应的$8*8$的块，分别处理前四行和后四行，因为前四行的后四列对应的位置在后四行，所以要先暂时存在不对应的位置。
这时候有个问题，如何在转移前四行的后四列的同时，只造成一次不命中，这里就是之前提到的行冲突的关键。因为$A$的前四行和$B$在不对应的位置上，不会造成冲突，造成冲突的只可能是$B$中转移的操作，故可以先把转移操作的对应元素的值存下来，然后先更新前四行后四列的位置。再用存下来的值更新后四行的前四列。这样就只会造成一次冲突。
注意这里前四行的对应方式不再是把整个行存列，而是分块把行存列
for (int i = 0; i < N; i += 8) {
for (int j = 0; j < M; j += 8) {
for (int k = 0; k < 4; k++) {
int tmp0 = A[i + k][j];
int tmp1 = A[i + k][j + 1];
int tmp2 = A[i + k][j + 2];
int tmp3 = A[i + k][j + 3];
int tmp4 = A[i + k][j + 4];
int tmp5 = A[i + k][j + 5];
int tmp6 = A[i + k][j + 6];
int tmp7 = A[i + k][j + 7];
B[j][i + k] = tmp0;
B[j + 1][i + k] = tmp1;
B[j + 2][i + k] = tmp2;
B[j + 3][i + k] = tmp3;
B[j][i + k + 4] = tmp4;
B[j + 1][i + k + 4] = tmp5;
B[j + 2][i + k + 4] = tmp6;
B[j + 3][i + k + 4] = tmp7;
}
for (int k = 4; k < 8; k++) {
int tmp0 = A[i + 4][j + k - 4];
int tmp1 = A[i + 5][j + k - 4];
int tmp2 = A[i + 6][j + k - 4];
int tmp3 = A[i + 7][j + k - 4];
int tmp4 = B[j + k - 4][i + 4];
int tmp5 = B[j + k - 4][i + 5];
int tmp6 = B[j + k - 4][i + 6];
int tmp7 = B[j + k - 4][i + 7];
B[j + k - 4][i + 4] = tmp0;
B[j + k - 4][i + 5] = tmp1;
B[j + k - 4][i + 6] = tmp2;
B[j + k - 4][i + 7] = tmp3;
B[j + k][i] = tmp4;
B[j + k][i + 1] = tmp5;
B[j + k][i + 2] = tmp6;
B[j + k][i + 3] = tmp7;
}
for (int k = 4; k < 8; k++) {
for (int l = 4; l < 8; l++) {
B[j + k][i + l] = A[i + l][j + k];
}
}
}
}
这里不考虑对角线的效率也很优秀了
结果：
Summary for official submission (func 0): correctness=1 misses=1220
61x67
这里因为行和列不能对齐块大小，所以计算非常麻烦，还是考虑分块，通过调节块的大小来找到最优解
块大小为$17$时可以通过
#define min(a, b) ((a) < (b) ? (a) : (b))
for (int i = 0; i < N; i += 17) {
for (int j = 0; j < M; j += 17) {
for (int k = 0; k < min(17, N - i); k++) {
for (int l = 0; l < min(17, M - j); l++) {
B[j + l][i + k] = A[i + k][j + l];
}
}
}
}
最后
运行 ./driver.py，得到结果：
Cache Lab summary:
Points Max pts Misses
Csim correctness 27.0 27
Trans perf 32x32 8.0 8 260
Trans perf 64x64 8.0 8 1220
Trans perf 61x67 10.0 10 1951
Total points 53.0 53