Aione's blog

一起快乐摸鱼吧🐳

  1. 1. cache simulatro
  2. 2. optimize matrix
    1. 2.1. 32x32
    2. 2.2. 64x64
  3. 3. ref

最近把csapp的cachae lab写完了,记录一下。

lab主要有两个部分,一个是 cache simulator,另一个是矩阵转置的缓存优化。

cache simulatro

核心逻辑还是很简单的,主要是如何实现 LRU 的问题。
基本上用时间优先队列就完事了,最后操作的放到最前面。

核心代码如下

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
int state = EVICT;
for (; index < c_size->entry_num; index++) {
if (!(cache_set + index)->valid) {
state = MISS;
break;
} else {
if ((cache_set + index)->tag == addr->tag) {
state = HIT;
break;
}
}
}

//use priority queue to handle the state
//put the least uses cache entry in to bottom
switch (state) {
case HIT:
for (int i = index; i > 0; i--) {
(cache_set + i)->tag = (cache_set + i - 1)->tag;
(cache_set + i)->valid = (cache_set + i - 1)->valid;
}
//put the cache into the head of the queue.
cache_set->tag = addr->tag;
tmp_sum->hits++;
break;
case MISS:
for (int i = index; i > 0; i--) {
(cache_set + i)->tag = (cache_set + i - 1)->tag;
(cache_set + i)->valid = (cache_set + i - 1)->valid;
}
cache_set->tag = addr->tag;
cache_set->valid = 1;
// printf(RED"[*] fill set %ld, line %d with tag %ld\n"NONE,
// addr->set,index,(cache_set+index)->tag);
tmp_sum->misses++;
break;
case EVICT:
for (int i = c_size->entry_num - 1; i > 0; i--) {
(cache_set + i)->tag = (cache_set + i - 1)->tag;
printf(RED"[*] change tag from %ld to %ld\n"NONE,
(cache_set+i)->tag,(cache_set+i-1)->tag);
}
cache_set->tag = addr->tag;
cache_set->valid = 1;
tmp_sum->misses++;
tmp_sum->evicts++;
break;
}

optimize matrix

题目给了一个 E=1,b=5,s=5 的缓存,我们要利用缓存优化矩阵转置代码。

tag set block
54 5 5
2^54 32 32

size of cache line: 32 bytes

total size: 32*32 bytes

int num: 32*8 = 256

32x32

32x32 的优化如下,主要注意一个缓存行可以装下八个整数。

而 C 语言里的矩阵又是按照行存储的,也就是说,当我们读第一个整数的时候,同一行后面的 7 个整数也会被读入到缓存行里,当下一次访问同一行的时候就会缓存命中。

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){
int i,j,k,a1,a2,a3,a4,a5,a6,a7,a8;
for(i=0;i<M;i+=8){
for(j=0;j<N;j+=8){
for(k=i;k<i+8;k++){
a1 = A[k][j+0];
a2 = A[k][j+1];
a3 = A[k][j+2];
a4 = A[k][j+3];
a5 = A[k][j+4];
a6 = A[k][j+5];
a7 = A[k][j+6];
a8 = A[k][j+7];
B[j+0][k] = a1;
B[j+1][k] = a2;
B[j+2][k] = a3;
B[j+3][k] = a4;
B[j+4][k] = a5;
B[j+5][k] = a6;
B[j+6][k] = a7;
B[j+7][k] = a8;
}
}
}
}

64x64

8x8

ref

Cache Lab 解题报告

Author : Aione
本文使用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议
Link to this article : https://aione.me/2019/10/22/CSAPP-cache-lab/

This article was last updated on days ago, and the information described in the article may have changed.