CSAPP Lab4 Cache Lab
CSAPP Lab4 Cache Lab: Understanding Cache Memories
https://www.zybuluo.com/SovietPower/note/1795924
參考：
https://www.jianshu.com/p/e68dd8305e9c
得分測試：
Linux> make
Linux> python driver.py
得分截圖：
Part 1
要求：模擬一個組相連高速緩存。只需給出每次操作是否命中、是否發生驅逐即可。
組相連高速緩存有\(S=2^s\)組，每組\(E\)行，每行\(1\)個有效位，\(t\)個標記位，\(B=2^b\)數據位。
地址：\(t\)個標記位，\(s\)個組索引位，\(b\)個塊偏移位。
每次模擬即可。
代碼還可以優化的地方（但也沒必要）：s,b,t,verbose,cache等確實可以定義為局部變量并作為函數參數傳遞；Cache結構體應有自己的s,b,t，而不是全局的。
測試得分：
Linux> make
linux> ./test-csim
自測：
> csim(.exe) -v -s 4 -E 1 -b 4 -t traces/yi.trace
L 10,1 miss
M 20,1 miss hit
...
M 12,1 miss eviction hit
hits:4 misses:5 evictions:3
代碼：
#include "cachelab.h"
#include <stdio.h>
#include <getopt.h>
#include <stdlib.h>
#include <unistd.h>
typedef unsigned long long ull;
const char *Usage="Usage: ./csim-ref [-hv] -s <s> -E <E> -b <b> -t <tracefile>";
const char *Error="Wrong augment.";
typedef struct
{
int valid, tm;
ull tag;
}CacheLine; //緩存行
typedef CacheLine* CacheSet; //緩存組
typedef CacheSet* Cache; //組相連高速緩存
int s,S,E,b,B;
int verbose;
int hits=0, misses=0, evictions=0;
Cache cache;
FILE *fp=NULL; //<tracefile>
void Read(int argc, char* argv[])
{
for(int opt; ~(opt=getopt(argc, argv, "hvs:E:b:t:")); )
{
switch(opt)
{
case 'h': //Optional help flag that prints usage info
fprintf(stdout, Usage, argv[0]);
exit(0);
case 'v': //Optional verbose flag that displays trace info
verbose=1;
break;
case 's': //Number of set index bits (S = 2^s is the number of sets)
s=atoi(optarg), S=1<<s;
break;
case 'E': //Associativity (number of lines per set)
E=atoi(optarg);
break;
case 'b': //Number of block bits (B = 2^b is the block size)
b=atoi(optarg), B=1<<b;
break;
case 't': //-t <tracefile>: Name of the valgrind trace to replay
fp=fopen(optarg,"r");
break;
default:
fprintf(stdout, Error, argv[0]);
exit(1);
}
}
}
void Init()
{
cache=(Cache)malloc(sizeof(CacheSet)*S);
if(cache==NULL) exit(1);
for(int i=0; i<S; ++i)
{
cache[i]=(CacheSet)calloc(E,sizeof(CacheLine)); //calloc會初始化分配的內容為0，malloc不會
if(cache[i]==NULL) exit(1);
}
}
void Load(int set_id,ull tag)
{
static int TIME=0;
++TIME; //time stamp
int empty=-1, eviction=-1;
CacheSet set=cache[set_id];
for(int i=0; i<E; ++i)
{
if(set[i].valid)
{
if(set[i].tag==tag)
{
++hits, set[i].tm=TIME;
if(verbose) printf(" hit");
return;
}
if(eviction==-1 || set[i].tm<set[eviction].tm)
eviction=i;
}
else empty=i;
}
++misses;
if(~empty)
{
set[empty].valid=1, set[empty].tag=tag;
set[empty].tm=TIME;
if(verbose) printf(" miss");
}
else
{
++evictions;
set[eviction].tag=tag;
set[eviction].tm=TIME;
if(verbose) printf(" miss eviction");
}
}
void Store(int set_id,ull tag)
{
Load(set_id,tag);
}
void Simulater()
{
char opt;
ull add;
int size;
while(~fscanf(fp," %c %llx,%d",&opt,&add,&size)) //%I64x
{
if(opt=='I') continue;
int set_id=(add>>b)&(S-1); ull tag=add>>(s+b);
if(verbose) printf("%c %llx,%d",opt,add,size);
switch(opt)
{
case 'L':
Load(set_id, tag);
break;
case 'S':
Store(set_id, tag);
break;
case 'M':
Load(set_id, tag), Store(set_id, tag);
break;
}
if(verbose) putchar('\n');
}
}
// void printSummary(int a,int b,int c)
// {
// printf("hits:%d misses:%d evictions:%d\n",a,b,c);
// }
int main(int argc, char* argv[])
{
Read(argc,argv);
Init();
Simulater();
printSummary(hits,misses,evictions);
fclose(fp);
for(int i=0; i<S; ++i) free(cache[i]);
free(cache); //Always free what you malloc, otherwise may get memory leak
return 0;
}
Part 2
要求：給定一個\(S=5,E=1,B=5\)的直接映射緩存，即有\(32\)組，每組一行能存\(32\)字節/\(8\)個int。分別對\(32\times 32\)、\(64\times 64\)、\(67\times 61\)的矩陣轉置函數做修改，使得其miss數盡量小。
三個函數允許的最大miss數分別為：\(600\)、\(2000\)、\(3000\)，滿分為小于\(300\)、\(1300\)、\(2000\)。
此外表現分要求：
- 每次最多使用12個局部int變量。
- 不能定義數組。
- 不能改變A矩陣，但B矩陣可以任意修改。
在trans.c中修改。
若要測試例如\(34\times 12\)的矩陣轉置可以使用：
Linux> ./test-trans -M 12 -N 34
自測：
Linux> make
Linux> ./test-trans -M <M> -N <N>
查看錯誤信息：
Linux> ./tracegen -M 64 -N 64 -F 0
2.1 32×32
做法1
先看一下分組情況：
第一行：\(0\sim 3\)組
第二行：\(4\sim 7\)組
第三行：\(8\sim 11\)組
...
第八行：\(28\sim 31\)組
轉置時，A是讀同一行，所以miss會很?。欢鴮需要逐列操作，miss的多少主要取決于B，所以主要關注B。
一般的轉置中，B依次寫\(1,2,3,...,8,9,10,...,32\)行，依次占用第\(0,4,8,...,28,0,4,...,28\)組?？梢园l現如果只讓B寫八行的第一列，再寫這八行的下一列直至寫完前八列，就不會發生miss/eviction（當然第一列會miss）。
至于A的影響，只是在分塊矩陣的主對角線上時，B每寫一列（八行）會與A沖突一次，導致兩次miss。（注意要先存一下A這行的八個元素，才能寫B的這一列，否則A要多miss一次）
結果分析：
對于主對角線上的四個\(8\times 8\)矩陣，miss數為\(2\times 8+7=23\)次；非主對角線上的子矩陣，因為A,B用到的內存組錯開了，所以只有\(8+8=16\)次miss。
所以總miss數約為\(23\times 4+16\times 12=284\)，實測\(287\)。
做法2
考慮能否消除做法1中主對角線上，額外的\(7\)次miss。這\(7\)次miss，是因為A,B是 分別按行列 交叉讀寫的，所以總會有\(7\)次的覆蓋。
那么我們A,B全都按行讀寫，就不會有這\(7\)次覆蓋了，每次的一整行都能hit。
注意到緩存可以存下A或B的整個\(8\times 8\)矩陣，不能修改A，但可以修改B。
所以我們把A一行一行賦值給B，是\(16\)次miss；然后再對B的\(8\times 8\)矩陣做轉置，額外miss數就是0了（全部在緩存中，全部都hit）。
即先按行復制后整個轉置。
這樣總miss數為\(16\times 16=256\)，實測\(259\)。
代碼：
//Sol1: 287
// for(i=0; i<N; i+=8)
// for(j=0; j<M; j+=8)
// for(k=i; k<i+8; ++k)
// {
// v0=A[k][j], v1=A[k][j+1], v2=A[k][j+2], v3=A[k][j+3],
// v4=A[k][j+4], v5=A[k][j+5], v6=A[k][j+6], v7=A[k][j+7];
//
// B[j][k]=v0, B[j+1][k]=v1, B[j+2][k]=v2, B[j+3][k]=v3,
// B[j+4][k]=v4, B[j+5][k]=v5, B[j+6][k]=v6, B[j+7][k]=v7;
// }
// return;
//Sol2: 259
for(i=0; i<N; i+=8)
for(j=0; j<M; j+=8)
{
for(k=i, l=j; k<i+8; ++k, ++l)
{
v0=A[k][j], v1=A[k][j+1], v2=A[k][j+2], v3=A[k][j+3],
v4=A[k][j+4], v5=A[k][j+5], v6=A[k][j+6], v7=A[k][j+7];
B[l][i]=v0, B[l][i+1]=v1, B[l][i+2]=v2, B[l][i+3]=v3,
B[l][i+4]=v4, B[l][i+5]=v5, B[l][i+6]=v6, B[l][i+7]=v7;
}
for(k=0; k<8; ++k)//第j行 第i列（偏移量i,j記得加）
for(l=k+1; l<8; ++l)//對于B，行的編號就都加j，列的編號就都加i
v0=B[k+j][l+i], B[k+j][l+i]=B[l+j][k+i], B[l+j][k+i]=v0;
}
2.2 64×64
看一下分組情況：
第一行：\(0\sim 7\)組
第二行：\(8\sim 15\)組
第三行：\(16\sim 23\)組
第四行：\(24\sim 31\)組
第五行：\(0\sim 7\)組...
顯然還按\(8\times 8\)分組不利于B的按列寫。如果換成\(4\times 4\)分組，B的每列寫不會沖突，但緩存中每行的利用率只有一半（能得一點點分）。
考慮綜合兩種分法，整體采用\(8\times 8\)分組，按行的操作每次處理八個，按列的操作每次處理四個（但注意這四行中的前八列都可以用）。
參考上面鏈接中的做法及圖片：
對每個\(8\times 8\)矩陣，分成四個\(4\times 4\)矩陣，然后做四步：
- 對A的前四行，前四個數分別存到B的前四列中，后四個數分別存到B的后四列中。
- 讀A的后四行的第一列、第五列元素，并保存。
- 將2.中A的后四行的第一列，放到B當前第一行的后四個元素中（并保存之前這里的四個元素）；將2.中A的后四行的第五列，放到B第五行的后四列去。
- 將3.中存下的，原先B第一行的后四個元素，放到B第五行的前四列去。
- \(2,3,4\)步對不同列重復做共四次，就可以實現轉置了。
這個做法充分利用了，同一行能讀\(8\)個數、最多同時存\(4\)整行的性質，以及轉置的特點。
總結就是，前四行可以直接按列賦值給B，然后對后四行，左下角部分的每一列放到右上角部分的每一行、右上角的每一行放到左下角部分的每一行、右下角的列轉成行位置，就可以實現轉置，而且這種方法對內存的利用率很高、miss少。
結果分析：
對于上面的四步，若子矩陣不在主對角線上，則A,B的讀寫不會相互影響，則：
- miss數為\(4+4=8\)。
- miss數為\(4\)。
- miss數為\(0+1=1\)。
- miss數為\(0\)。
- 三次重復后的\(2,3,4\)步miss數共\(0+3+0=3\)。
總miss數約為\((8+4+1+3)\times 64=1024\)
若子矩陣在主對角線上，1.中miss數會加\(3\)，每次的3.會多\(4\)（寫B的被A驅逐的前四行）+\(3\)（讀A的被B驅逐的五六七行）=\(7\)次，所以共多\((3+7)*8=80\)次。
所以總miss數為\(1104\)次，實測\(1107\)次。
1.中多的\(3*8\)次miss可以像2.1中，先復制后轉置的方法消除。
代碼：
for(i=0; i<N; i+=8)
for(j=0; j<M; j+=8)
{
for(k=i; k<i+4; ++k)
{
v0=A[k][j+0], v1=A[k][j+1], v2=A[k][j+2], v3=A[k][j+3],
v4=A[k][j+4], v5=A[k][j+5], v6=A[k][j+6], v7=A[k][j+7];
B[j][k]=v0, B[j+1][k]=v1, B[j+2][k]=v2, B[j+3][k]=v3,
B[j][k+4]=v4, B[j+1][k+4]=v5, B[j+2][k+4]=v6, B[j+3][k+4]=v7;
}
for(k=j; k<j+4; ++k)
{
v0=A[i+4][k], v4=A[i+4][k+4],
v1=A[i+5][k], v5=A[i+5][k+4],
v2=A[i+6][k], v6=A[i+6][k+4],
v3=A[i+7][k], v7=A[i+7][k+4],
tmp=B[k][i+4], B[k][i+4]=v0, v0=tmp;
tmp=B[k][i+5], B[k][i+5]=v1, v1=tmp;
tmp=B[k][i+6], B[k][i+6]=v2, v2=tmp;
tmp=B[k][i+7], B[k][i+7]=v3, v3=tmp;
B[k+4][i+0]=v0, B[k+4][i+1]=v1, B[k+4][i+2]=v2, B[k+4][i+3]=v3,
B[k+4][i+4]=v4, B[k+4][i+5]=v5, B[k+4][i+6]=v6, B[k+4][i+7]=v7;
}
}
2.3 67×61
類似2.1，每行是\(61\)個，所以依舊利用Cache能存B的\(8\)行的性質，對B每\(8\)行處理一次，每次處理所有行的這八個元素的A->B賦值。
因為限制為\(2000\)足夠大，比較容易過。實測\(1761\)。
不過\(16\times 16\)分塊，暴力轉置也能恰好不超過\(2000\)。
代碼：
for(j=0; j<56; j+=8)
for(i=0; i<67; ++i)
{
v0=A[i][j], v1=A[i][j+1], v2=A[i][j+2], v3=A[i][j+3],
v4=A[i][j+4], v5=A[i][j+5], v6=A[i][j+6], v7=A[i][j+7];
B[j][i]=v0, B[j+1][i]=v1, B[j+2][i]=v2, B[j+3][i]=v3,
B[j+4][i]=v4, B[j+5][i]=v5, B[j+6][i]=v6, B[j+7][i]=v7;
}
for(i=0; i<64; ++i)//右上
for(j=56; j<61; ++j)
B[j][i]=A[i][j];
for(i=64; i<67; ++i)//右下
for(j=56; j<61; ++j)
B[j][i]=A[i][j];
別來無恙 你在心上
------------------------------------------------------------------------------------------------------------------------
浙公網安備 33010602011771號