Pwn进你的心
0%

CSapp-Cache Lab

Posted on Edited on In 17k 16 mins.

Cache Lab

本实验室将帮助您了解：缓存内存对C语言性能的影响

实验室由两部分组成：

  • 在第一部分中，您将编写一个小型C程序（大约200-300行），该程序模拟缓存的行为
  • 在第二部分中，您将优化一个小的矩阵转置函数，目标是最小化缓存未命中的数量

缓存机制

Cache简析

CPU在执行时，需要的指令和数据通过内存总线和系统总线由内存传送到寄存器，再由寄存器送入ALU

SRAM的速度介于DRAM(主存)和CPU之间，我们把接下来可能会用到的数据放在SRAM(Cache)中，当CPU需要数据时先去查Cache，如果Cache中有(hit)，就不用再去访问主存了，这样就节省了时间

Cache结构

Cache共有S组，每组E行，每行包括一个有效位(valid bit)，一个标签和B比特数据：

我们可以将高速缓存存储器视为：

  • 有S个高速缓存的：组
  • 每个数组包含E个高速：缓存行
  • 每个行的组成：B字节的数据块 + 各种指示位

高速缓存的结构可以用元组（S,E,B,m）来描述，高速缓存的大小（或容量）C指的是所有块的大小的和，所以：C = S×E×B

每个高速缓存存储器有m位，可以组成 2的m次幂 个不同的地址，每个数据块由以下三部分构成

  • 有效位：有效位为 v 位，v 一般为1，指明这个行是否包含有效信息
  • 标记位：标记位为 t 位，指明这个行是否包含有效信息
  • 组索引：组索引为 s 位，表示为无符号数作为组的索引
  • 块偏移：块偏移为 b 位，指明CPU请求的内容在数字块中的偏移

Cache逻辑

数据总是以块为单位，在高速缓存和主存之间来回复制

如果我们的程序请求一个数据字，这个数据字存储在编号为10的块中，将分以下几种情况考虑：

  • 冷不命中：高速缓存中为空
  • 缓存不命中：高速缓存中有数据块，但没有数据块10
  • 冲突不命中：高速缓存中有数据，将内存中的数据块放置到高速缓存中时，发生了冲突
  • 缓存命中：高速缓存中有数据块10，直接返回CPU

当一条加载指令指示CPU从主存地址A中读取一个字w时，会将该主存地址A发送到高速缓存中，则高速缓存会根据以下步骤判断地址A是否命中：

  • 组选择：根据地址划分，将中间的 s位 表示为无符号数作为组的索引，可得到该地址对应的组
  • 行匹配：根据地址划分，可得到 t位 的标记位（由于组内的任意一行都可以包含任意映射到该组的数据块，所以就要线性搜索组中的每一行），判断是否有和标志位匹配且设置了有效位的行 ，如果存在，则缓存命中，否则缓冲不命中
  • 字选择：如果找到了对应的高速缓存行，则可以将 b位 表示为无符号数作为块偏移量 ，得到对应位置的字

当高速缓存命中时：会很快抽取出字w，并将其返回给CPU

如果缓存不命中时：CPU会进行等待，高速缓存会向主存请求包含字w的数据块，当请求的块从主存到达时，高速缓存会将这个块保存到它的一个高速缓存行中，然后从被存储的块中抽取出字w，将其返回给CPU

Cache映射

（S，E，B，m）=（4，1，2，4）

假设某个Cache有：4个组，每个组1行，每个块2字节，地址m为4位：

因为地址为4位，所以地址空间可以分为16个区域，编号为 地址0 ~ 地址15

每个块的大小为2字节，所以两个内存区域可以组成一个块，通过 标记位（Tag） 和 索引位（Index）可以唯一确定每一个块，共有8个块

但是 Cache 只有4个组（每个组只有1行），所以可能会有两个块被映射到同一个组，比如：块0和块4被都被映射到了set0，而块1和块5都被映射到了set1

也就是说，块和组可能不是一一对应的，这就导致了冲突不命中

PS：为什么不采用高位来作为组索引位（s位）：

直接映射高速缓存

根据 cache 每个组中行数的不同，cache 被分为不同的类型，当行数为 1 时（E==1），这种 cache 被称为直接映射

假设有 S 组，每组由1行组成，缓存块为8字节

组选择

CPU发出地址要取数据字，高速缓存将该地址分解为三部分：标记位，组索引，块偏移

上图程序的 组索引（s位）为 “0x1” ，所以索引第2个组

行匹配

然后，检查地址中的 标记位 与缓存行中的 标记位 是否匹配：

  • 如果匹配，将进行下一步字选择
  • 如果不匹配，则表示未命中（高速缓存必须从内存中重新取数据块，在行中覆盖此块）

字选择

上图程序的 块偏移（b位）为 “0x4” ，所以索引标记为“0x4”的块，返回给CPU

​ // 字选择的操作是为了确定目标数据的起始地址

模拟演示

假设，内存地址为4字节，S=4组，E=1行/组，B=2字节/块，其结构图如下所示：

我们模拟CPU要从高速缓存中读取地址为“0,1,7,8,0”的数据：

地址 二进制 是否命中
0 [0000]（t=0，s=00，b=0） 否
1 [0001]（t=0，s=00，b=1） 是
7 [0111]（t=0，s=11，b=1） 否
8 [1000]（t=1，s=00，b=0） 否
0 [0000]（t=0，s=00，b=0） 否

第一步，读地址0的数据：标记位为 0，索引位为 “00”，偏移位为 “0”，块号为 0

缓存行中没有数据，组0 的有效位为 0，地址0 的标记位和 组0 的标记位不匹配，因此，未命中，然后，高速缓存从内存中取出块0，块1（共2字节）并存储在 组0 中

第二步，读地址1的数据：标记位为 0，索引位为 “00”，偏移位为 “1”，块号为 1

缓存行中已有数据数据，组0 的有效位为 1，地址1 的标记位和 组0 的标记位匹配，因此，命中，具体如下图所示

第三步，读地址7的数据：标记位为 0，索引位为 “11”，偏移位为 “1”，块号为 3

缓存行中有数据，组3 的有效位为 0，地址7 的标记位 和 组0 的标记位不匹配，因此，未命中，然后，高速缓存从内存中取出块6，块7（共2字节）并存储在组3中

第四步，读地址8的数据：标记位为 1，索引位为 “00”，偏移位为 “0”，块号为 4

缓存行中有数据，组0 的有效位为 1，地址的标记位 和 组0 的标记位不匹配，因此，未命中，然后，高速缓存从内存中取出块8，块9（共2字节）并存储在组0中

第五步，读地址0的数据：标记位为 0，索引位为 “00”，偏移位为 “0”，块号为 0

缓存行中有数据，组0 的有效位为 1，地址的标记位 和 组0 的标记位不匹配，因此，未命中，然后，高速缓存从内存中取出块0，块1（共2字节）并存储在组0中

总而言之：先通过索引位定位正确的组，然后对比标记位判断是否命中：

局部性原理

  • 时间局部性：最近访问的数据可能在不久的将来会再次访问
  • 空间局部性：位置相近的数据常常在相近的时间内被访问

根据局部性原理，我们可以把计算机存储系统组织成一个存储山，越靠近山顶，速度越快，但造价越昂贵，越靠近山底，速度越越慢，但造价越便宜

上一层作为下一层的缓冲，保存下一层中的一部分数据

局部性的影响因素

变量 sum 在每次循环中被引用一次，说明它具有良好的时间局部性，它只有一个空间，所以没有空间局部性

变量 v 读取的顺序和在内存中存储的顺序是一致的，说明它具有良好的空间局部性，但是每次循环只访问变量 v 中的一个数据，因此它的时间局部性很差

空间局部性的影响因数：步长

从 a[0] [0] 到 a[0] [1] Address 增加了“4”，所以步长为“4”

从 a[0] [0] 到 a[0] [1] Address 增加了“12”，所以步长为“12”

对比步长得知：第一个程序比第二个程序更具效率

时间局部性的影响因数：分块

分块技术可以提高时间局部性，具体的分块安排需要对照Cache的规格

分块技术的核心其实是为了每一行Cache被充分地使用：

1
2
3
4
5
6
7
8
9
10
int A[N][M];
int B[M][N];
int tmp;

for (i = 0; i < N; i++) {
    for (j = 0; j < M; j++) {
        tmp = A[i][j];
        B[j][i] = tmp;
    }
}

假设Cache每行有32字节，每组1行，那么内存第一次循环时，会把 A[0] [0] ~ A[0] [7] 放入第1组，把 B[0] [0] ~ B[0] [7] 放入第2组

当第二次循环获取 A[0] [1] 时可以命中，但获取 B[][][1] [0] 时不会命中，并且把 B[1] [0] ~ B[1] [7] 放入第3组

以此类推，当Cache空间不够时，就可能覆盖前面的内容，导致数组B永远也不可能命中了

但是如果可以把 N * M 的大矩阵分为小矩阵，使其可以存储下当前小矩阵中所有的 数组B 的值，就可以在多次不命中后再次命中

实验文件介绍

  • csim.c：实验PartA写在此处
  • trans.c：实验PartB写在此处
  • csim-ref：一个对照文件
  • test-csim：PartA的检查程序，使用它可以得到实验的分散
  • traces：装有每次对内存进行的操作
1
linux> valgrind --log-fd=1 --tool=lackey -v --trace-mem=yes ls -l
1
2
3
4
5
6
7
8
9
10
11
12
13
14
I  04ead900,3
I  04ead903,3
I  04ead906,5
I  04ead838,3
I  04ead83b,3
I  04ead83e,5
 L 1ffefff968,8
I  04ead843,3
I  04ead846,3
I  04ead849,5
 L 1ffefff960,8
I  04ead84e,3
I  04ead851,3
......

根据 trace 文件中记载的每一次对内存的操作，分析格式为: 

1
[空格][操作类型][空格][内存地址][逗号][大小]

操作类型有以下三种：

  • L：从内存中读取（1次控制cache）
  • S：向内存中存储（1次控制cache）
  • M：对内存进行修改（2次控制cache）

然后实验给我们提供了一个程序csim-ref，我们要做的就是写出一个和它功能一样的程序

PartA Cache simulator

参考模拟器采用以下命令行参数： 

1
2
3
4
5
6
7
Usage: ./csim-ref [-hv] -s <s> -E <E> -b <b> -t <tracefile>
• -h：可选的帮助标志，用于打印使用情况信息
• -v：显示跟踪信息的可选详细标志
• -s <s>：设置的索引位数（S = 2s是设置的数量）
• -E <E>：关联性（每组行数）
• -b <b>：块位数（B = 2b是块大小）
• -t <tracefile>：要重播的valgrind跟踪的名称

开始实验前要先了解一个函数：getopt

1
getopts [option[:]] [DESCPRITION] VARIABLE
  • option：表示为某个脚本可以使用的选项
  • VARIABLE：表示将某个选项保存在变量VARIABLE中

定义结构体

cache_line结构体中包括：有效位，标记位，时间戳

1
2
3
4
5
typedef struct{
	int valid_bits; // 有效位
	unsigned  tag; // 标记位
	int stamp; // 时间戳
}cache_line;

这个结构体将会被当成指针使用

初始化Cache

1
2
3
4
5
6
7
8
9
10
11
12
void init(){
	cache = (cache_line**)malloc(sizeof(cache_line*)*S); // 申请S个组 
	for(int i=0;i<S;i++) 
		*(cache+i) = (cache_line*)malloc(sizeof(cache_line)*E); // 申请E个行
	for(int i=0;i<S;i++){
		for(int j=0;j<E;j++){
			cache[i][j].valid_bits = 0; // 初始化有效位为'0'
			cache[i][j].tag = -1; // 初始化标记位为'-1'(正常情况下tag不会为负)
			cache[i][j].stamp = 0; // 初始化时间戳为'0'
		}	
	}
}
  • 先申请大小为 “sizeof ( cache_line ) S” 的空间，代表S个组
  • 再申请S个大小为 “sizeof ( cache_line ) * E” 的空间，代表每个组中有E个行
  • 把 申请的E空间首地址 赋值给 申请的S空间 的各个单元

结构体类型的指针：作为数组使用时，分配更大的空间（类比 int 和 char 类型的数组）

解析输入的指令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void parse_trace()
{
	FILE* file=fopen(filepath,"r");
	if(file == NULL){     
		printf("Open file wrong");		
		exit(-1);
	}
	char operation;
	unsigned address;
	int size;	
	while(fscanf(file," %c %x,%d",&operation,&address,&size)>0){
		switch(operation){
			case 'L':
				update(address); // 一次操作cache
				break;
			case 'M':
				update(address); // 两次操作cache
			case 'S':
				update(address); // 一次操作cache
				break;
		}
		time(); // 操作时间
	}
    for(int i=0;i<S;i++)              
		free(*(cache+i));
	free(cache);
	fclose(file);	 
}

用 fscanf 读入 trace 文件的指令来进行操作，分别对“L”，“M”，“S”进行操作（这里并不用细分它们的功能，只需要模拟它们对 cache 的使用就可以了）

Cache的命中判断+添加+代替

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void update(unsigned address){
    
    // 获取s位和t位 
	unsigned s_address =(address>>b) & ((0xffffffff)>>(32-s)); //获取s位
	unsigned t_address = address>>(s+b); // 获取t位
    
	// 判断tag为是否相等，是否命中
    for(int i=0;i<E;i++){
		if((*(cache+s_address)+i)->tag ==t_address){
			cache[s_address][i].stamp = 0; // 重置时间戳
			hit++; // 命中计数器+1
			return;
		}
	}
    /* "*(cache+s_address)"表示对应的组，后续对组中的所以行进行遍历操作，判断命中 */
    
    // 添加高速缓存cache
	for(int i=0;i<E;i++){
		if(cache[s_address][i].valid_bits == 0){
			cache[s_address][i].tag = t_address;
			cache[s_address][i].valid_bits = 1; // 重置时有效为'1'
			cache[s_address][i].stamp = 0; // 重置时间戳
			miss++; // 不命中计数器+1
			return;
		}
	}
    /* 未命中时，程序会获取空闲的cache(没有分配数据)，否则进入"代替模块" */
    
    // 暴力实现LRU策略(cache代替)
	int max_stamp=0;
	int max_i;
	for(int i=0;i<E;i++){
		if(cache[s_address][i].stamp > max_stamp){
			max_stamp = cache[s_address][i].stamp;
			max_i = i;
		}
	}
	eviction++;
	miss++;
	cache[s_address][max_i].tag = t_address;
	cache[s_address][max_i].stamp = 0;	
}

LRU策略

LRU 缓存淘汰算法就是一种常用策略。 LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的

如果该SET存满了，我每次要找到 TIMESTAMP（时间戳）最小的替换

本程序中采用了 stamp ，有所不同：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void time(){ // 所有可用的cache(已分配数据的)，stamp+1
	for(int i=0;i<S;i++){
		for(int j=0;j<E;j++){
			if(cache[i][j].valid_bits == 1)
				cache[i][j].stamp++;		
		}	
	}
}

	// 暴力实现LRU策略(cache代替)
	for(int i=0;i<E;i++){
		if(cache[s_address][i].stamp > max_stamp){
			max_stamp = cache[s_address][i].stamp;
			max_i = i;
		}
	}
	eviction++; // 驱逐计数器+1
	miss++; // 不命中计数器+1
	cache[s_address][max_i].tag = t_address;
	cache[s_address][max_i].stamp = 0;

在time中，会使所有已分配数据的 cache 的“cache->stamp”持续增加，而命中和更新都可以重置时间戳，那些长时间未被使用的 cache 的 stamp 更大，更应该被替换掉

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include "cachelab.h"
#include <getopt.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include <stddef.h>

typedef struct {
	int valid_bits;
	unsigned tag;
	int stamp;
}cache_line;

char* filepath = NULL;
int s, E, b, S;
int hit = 0;
int miss = 0;
int eviction = 0;
cache_line** cache = NULL;

void init();
void update(unsigned address);
void time();
void parse_trace();

void init()
{
	cache = (cache_line**)malloc(sizeof(cache_line*) * S);
	for (int i = 0; i < S; i++)
		*(cache + i) = (cache_line*)malloc(sizeof(cache_line) * E);
	for (int i = 0; i < S; i++)
		for (int j = 0; j < E; j++)
		{
			cache[i][j].valid_bits = 0;
			cache[i][j].tag = -1;
			cache[i][j].stamp = 0;
		}
}

void update(unsigned address)
{
	unsigned s_address = (address >> b) & ((0xffffffff) >> (32 - s));
	unsigned t_address = address >> (s + b);
	for (int i = 0; i < E; i++) {
		if ((*(cache + s_address) + i)->tag == t_address){
			cache[s_address][i].stamp = 0;
			hit++;
			return;
		}
	}
		
	for (int i = 0; i < E; i++) {
		if (cache[s_address][i].valid_bits == 0) {
			cache[s_address][i].tag = t_address;
			cache[s_address][i].valid_bits = 1;
			cache[s_address][i].stamp = 0;
			miss++;
			return;
		}
	}

	int max_stamp = 0;
	int max_i;
	for (int i = 0; i < E; i++) {
		if (cache[s_address][i].stamp > max_stamp) {
			max_stamp = cache[s_address][i].stamp;
			max_i = i;
		}
	}
	eviction++;
	miss++;
	cache[s_address][max_i].tag = t_address;
	cache[s_address][max_i].stamp = 0;
}

void time() {
	for (int i = 0; i < S; i++) {
		for (int j = 0; j < E; j++) {
			if (cache[i][j].valid_bits == 1) {
				cache[i][j].stamp++;
			}
		}
	}
}

void parse_trace() {
	FILE* file = fopen(filepath, "r");
	if (file == NULL)
	{
		printf("Open file wrong");
		exit(-1);
	}
	char operation;
	unsigned address;
	int size;
	while (fscanf(file, " %c %x,%d", &operation, &address, &size) > 0) {
		switch (operation) {
		case 'L':
			update(address);
			break;
		case 'M':
			update(address);
		case 'S':
			update(address);
			break;
		}
		time();
	}
	for (int i = 0; i < S; i++) {
		free(*(cache + i));
	}
	free(cache);
	fclose(file);
}

int main(int argc, char* argv[]) {
	int opt;
	while ((opt = getopt(argc, argv, "s: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':
			filepath = optarg;
			break;
		}
	}
	S = 1 << s;

	init();
	parse_trace();

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

PartB Efficient Matrix Transpose

在 trans.c 中为提供了一个示例转置函数，用于计算转置N×M矩阵A并将结果存储在M×N矩阵B中： 

1
2
3
4
5
6
7
8
9
10
11
void trans(int M, int N, int A[N][M], int B[M][N])
{
    int i, j, tmp;

    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            tmp = A[i][j];
            B[j][i] = tmp;
        }
    }    
}

示例的转置函数是正确的，但是效率很低，因为访问模式会导致相对许多缓存未命中

在B部分中，我们将在 trans.c 中编写一个 矩阵转置函数（ transpose_submit ），该函数将尽可能降低高速缓存未命中率

判分程序最终会检查矩阵转置函数在以下三种大小的矩阵上的表现：

  • 32 * 32，miss<300 得8分，miss>600不得分
  • 64 * 64，miss<1300 得8分，miss>2000不得分
  • 61 * 67，miss<2000 得10分，miss>3000不得分

在PartB中提供得Cache规格：S = 5，E = 1，b = 5（32组，每组1行，每行32字节）

32 * 32

先看看 trans.c 中提供的那个函数的 cache 使用情况

矩阵A的步长为“1”，所以空间局部性良好，而矩阵B的步长为“32”，空间局部性较差，并且无论我们怎么调整循环顺序，都无法改变，所以无法从空间局部性的角度来减少不命中次数

每行32字节，意味着每行可以获取8个数组单位（int类型）

组(时间顺序) 元素
第1个 (第1轮) A [0] [0] ~ A [0] [7]
第2个 B [0] [0] ~ B [0] [7]
第3个 B [1] [0] ~ B [1] [7]
…… ……
第8个 B [6] [0] ~ B [6] [7]
第9个 B [7] [0] ~ B [7] [7]
第10个 (第2轮) A [0] [8] ~ A [0] [15]
第11个 B [8] [0] ~ B [8] [7]
第12个 B [9] [0] ~ B [9] [7]
…… ……
第28个 (第4轮) A [0] [24] ~ A [0] [31]
第29个 B [24] [0] ~ B [24] [7]
第30个 B [25] [0] ~ B [25] [7]
第31个 B [26] [0] ~ B [26] [7]
第32个 B [27] [0] ~ B [27] [7]

注意：为了理解方便，此时没有考虑“两个块映射到同一个组”这种情况，后续会进行分析

当读取 B[28] [0] 时，就会使 “A [0] [0] ~ A [0] [7]” 被代替，从而导致 A[1] [0] 不命中，那么后续的操作会不断替代前面的缓存，cache 利用率大大下降

如果把 32 32 的矩阵分为 16 个 8 8 的矩阵：

每次只会先在解决一个小矩阵，才开始运算下面一个小矩阵

第1轮 A[0] [0] 和 B[0] [0]，A[0] [1] 和 B[1] [0]，A[0] [2] 和 B[2] [0] …… A[0] [7] 和 B[7] [0]

第2轮 A[1] [0] 和 B[0] [1]，A[1] [1] 和 B[1] [1]，A[1] [2] 和 B[2] [1] …… A[1] [7] 和 B[7] [1]

第3轮 A[2] [0] 和 B[0] [2]，A[2] [1] 和 B[1] [2]，A[2] [2] 和 B[2] [2] …… A[2] [7] 和 B[7] [2]

…………..

第9轮 A[0] [8] 和 B[8] [0]，A[0] [9] 和 B[9] [0]，A[0] [10] 和 B[10] [0] …… A[0] [15] 和 B[15] [0]

组(时间顺序) 元素
第1个 (第1轮) (大1轮) A [0] [0] ~ A [0] [7]
第2个 B [0] [0] ~ B [0] [7]
第3个 B [1] [0] ~ B [1] [7]
…… ……
第8个 B [6] [0] ~ B [6] [7]
第9个 B [7] [0] ~ B [7] [7]
第10个 (第2轮) A [1] [0] ~ A [1] [7]
第11个 (第3轮) A [2] [0] ~ A [2] [7]
第12个 (第4轮) A [3] [0] ~ A [3] [7]
…… ……
第16个 (第8轮) A [7] [0] ~ A [7] [7]
第17个 (第9轮) (大2轮) A [0] [8] ~ A [0] [15]
第18个 B [8] [0] ~ B [8] [7]
第19个 B [9] [0] ~ B [9] [7]
…… ……

从第二轮开始，后续几轮所需要的 B数组 的值，都可以在 第2~9个 cache 中获取

写出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void transpose_submit(int M, int N, int A[N][M], int B[M][N])
{
    if (M == 32 && N == 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];
                    }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
➜  [/home/ywhkkx/cachelab-handout] ./test-trans -M 32 -N 32

Function 0 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 0 (Transpose submission): hits:1710, misses:343, evictions:311

Function 1 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 1 (Simple row-wise scan transpose): hits:870, misses:1183, evictions:1151

Summary for official submission (func 0): correctness=1 misses=343

TEST_TRANS_RESULTS=1:343

发现 miss 在 300 以上，还不是满分

理论上是可以到达满分的，但是上述操作是在没有考虑“两个块映射到同一个组”的前提下进行的，那么两个块可能映射到同一个组中吗？

我们有32个组，每个组有32字节：

1
2
In [1]: 32*32
Out[1]: 1024

在每个 8 * 8 的小矩阵中，每个单元4字节，同一时期只需要同时映射2个小矩阵

1
2
In [2]: 8*8*2*4
Out[2]: 512

理论上来说Cache可以存储的字节数 远大于 两个小矩阵所需要的字节数，Cache没有必要把两个块映射到同一个组中

但是Cache会以整个 32 * 32 的空间进行映射，为了让 32 个组可以覆盖这个空间，Cache只能让多个数据块映射到同一个组中，一但映射完成，“Cache的各个组”和“各个空间位置”的对应关系就固定了

比如：数组A和数组B中，对应位置的块就会被分配到同一个组中，当进行 对角线的引用 时，一定会发生缓存的冲突不命中，并且，由于A和B的元素时一个一个处理的，必定会造成反复多次的冲突不命中（A第一个元素读miss，B第一个元素存miss，A读第二个元素miss）

解决方法：通过变量一次性读出A的一整行，再存入B 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
if (M == 32 && N == 32)
{
	int i, j, k, v1, v2, v3, v4, v5, v6, v7, v8;
	for (i = 0; i < 32; i += 8)
		for (j = 0; j < 32; j += 8)
			for (k = i; k < (i + 8); ++k)
			{
				v1 = A[k][j];
				v2 = A[k][j + 1];
				v3 = A[k][j + 2];
				v4 = A[k][j + 3];
				v5 = A[k][j + 4];
				v6 = A[k][j + 5];
				v7 = A[k][j + 6];
				v8 = A[k][j + 7];
				B[j][k] = v1;
				B[j + 1][k] = v2;
				B[j + 2][k] = v3;
				B[j + 3][k] = v4;
				B[j + 4][k] = v5;
				B[j + 5][k] = v6;
				B[j + 6][k] = v7;
				B[j + 7][k] = v8;
			}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
➜  [/home/ywhkkx/cachelab-handout] ./test-trans -M 32 -N 32

Function 0 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 0 (Transpose submission): hits:1766, misses:287, evictions:255

Function 1 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 1 (Simple row-wise scan transpose): hits:870, misses:1183, evictions:1151

Summary for official submission (func 0): correctness=1 misses=287

TEST_TRANS_RESULTS=1:287

64 * 64

这里同样使用分块技术进行优化，需要注意的是，当矩阵大小变为 64x64 时，矩阵中的每一行需要8 个高速缓存行进行保存，所以我们只能设置块大小为 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
else if (M == 64 && N == 64)
{
       int l, k, i, j;
	int a0, a1, a2, a3, a4, a5, a6, a7;
       for (i = 0; i < N; i += 8) {
           for (j = 0; j < M; j += 8) {
               for (k = i; k < i + 4; k++) {
                   a0 = A[k][j];
                   a1 = A[k][j + 1];
                   a2 = A[k][j + 2];
                   a3 = A[k][j + 3];
                   a4 = A[k][j + 4];
                   a5 = A[k][j + 5];
                   a6 = A[k][j + 6];
                   a7 = A[k][j + 7];

                   B[j][k] = a0;
                   B[j + 1][k] = a1;
                   B[j + 2][k] = a2;
                   B[j + 3][k] = a3;

                   B[j][k + 4] = a4;
                   B[j + 1][k + 4] = a5;
                   B[j + 2][k + 4] = a6;
                   B[j + 3][k + 4] = a7;
               }
               for (l = j + 4; l < j + 8; l++) {

                   a4 = A[i + 4][l - 4]; // A left-down col
                   a5 = A[i + 5][l - 4];
                   a6 = A[i + 6][l - 4];
                   a7 = A[i + 7][l - 4];

                   a0 = B[l - 4][i + 4]; // B right-above line
                   a1 = B[l - 4][i + 5];
                   a2 = B[l - 4][i + 6];
                   a3 = B[l - 4][i + 7];

                   B[l - 4][i + 4] = a4; // set B right-above line 
                   B[l - 4][i + 5] = a5;
                   B[l - 4][i + 6] = a6;
                   B[l - 4][i + 7] = a7;

                   B[l][i] = a0;         // set B left-down col
                   B[l][i + 1] = a1;
                   B[l][i + 2] = a2;
                   B[l][i + 3] = a3;

                   B[l][i + 4] = A[i + 4][l];
                   B[l][i + 5] = A[i + 5][l];
                   B[l][i + 6] = A[i + 6][l];
                   B[l][i + 7] = A[i + 7][l];
               }
           }
       }
}

​ // 讲真我这里看不懂，先挂着以后慢慢看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
➜  [/home/ywhkkx/cachelab-handout] ./test-trans -M 64 -N 64

Function 0 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 0 (Transpose submission): hits:9074, misses:1171, evictions:1139

Function 1 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 1 (Simple row-wise scan transpose): hits:3474, misses:4723, evictions:4691

Summary for official submission (func 0): correctness=1 misses=1171

TEST_TRANS_RESULTS=1:1171

61 * 67

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
else if (M == 61)
{
    int i, j, v1, v2, v3, v4, v5, v6, v7, v8;
    int n = N / 8 * 8;
    int m = M / 8 * 8;
    for (j = 0; j < m; j += 8)
        for (i = 0; i < n; ++i)
        {
            v1 = A[i][j];
            v2 = A[i][j + 1];
            v3 = A[i][j + 2];
            v4 = A[i][j + 3];
            v5 = A[i][j + 4];
            v6 = A[i][j + 5];
            v7 = A[i][j + 6];
            v8 = A[i][j + 7];

            B[j][i] = v1;
            B[j + 1][i] = v2;
            B[j + 2][i] = v3;
            B[j + 3][i] = v4;
            B[j + 4][i] = v5;
            B[j + 5][i] = v6;
            B[j + 6][i] = v7;
            B[j + 7][i] = v8;
        }
    for (i = n; i < N; ++i)
        for (j = m; j < M; ++j)
        {
            v1 = A[i][j];
            B[j][i] = v1;
        }
    for (i = 0; i < N; ++i)
        for (j = m; j < M; ++j)
        {
            v1 = A[i][j];
            B[j][i] = v1;
        }
    for (i = n; i < N; ++i)
        for (j = 0; j < M; ++j)
        {
            v1 = A[i][j];
            B[j][i] = v1;
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
➜  [/home/ywhkkx/cachelab-handout] ./test-trans -M 61 -N 67

Function 0 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 0 (Transpose submission): hits:6334, misses:1905, evictions:1873

Function 1 (2 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 1 (Simple row-wise scan transpose): hits:3756, misses:4423, evictions:4391

Summary for official submission (func 0): correctness=1 misses=1905

TEST_TRANS_RESULTS=1:1905

整体打分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
➜  [/home/ywhkkx/cachelab-handout] ./driver.py             
Part A: Testing cache simulator
Running ./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


Part B: Testing transpose function
Running ./test-trans -M 32 -N 32
Running ./test-trans -M 64 -N 64
Running ./test-trans -M 61 -N 67

Cache Lab summary:
                        Points   Max pts      Misses
Csim correctness          27.0        27
Trans perf 32x32           8.0         8         287
Trans perf 64x64           8.0         8        1171
Trans perf 61x67          10.0        10        1905
          Total points    53.0        53

这个 Lab 真的做吐了……