CS:APP配套實驗4：Cache Lab筆記

終於看完第六章Cache了，Cache是非常重要的部分，作為存儲器層次結構中的重要一環，在cpu和主存之間起到緩衝作用，也是編寫代碼優化性能時候必須要關注的點。

本章的實驗，有兩部分，part A是用C語言來模擬一個Cache的功能，有助於對Cache的理解。part B是通過優化改進矩陣轉置演算法，最小化Cache miss的次數。

1. part A

part A比較簡單，就是一個C語言的模擬，不是真的寫一個Cache，功能比較簡易。

有如下要求，運行時有6個參數，需要處理命令行參數。有兩種方法，一種如下：

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

直接處理main函數的參數，第一個是命令行參數的個數，第二個是每個參數，不過都是字元串類型，如下代碼處理參數：

int s,S,E,b;nFILE *fp;nfor(int i=1;i<argc;){n //printf("%s",argv[i]);nt if(argv[i][0]==-){nttif(argv[i][1] == s){nttti++;nttts = change2number(argv[i]);ntttS = (1<<s);nttti++;ntt}nttelse if(argv[i][1] == E){nttti++;ntttE = change2number(argv[i]);nttti++;ntt}nttelse if(argv[i][1] == b){nttti++;ntttb = change2number(argv[i]);nttti++;ntt}nttelse if(argv[i][1] == t){nttti++;ntttfp = fopen(argv[i],"r");nt ti++;ntt}nt}n}n

第二種方式是用getopt方法，需要頭文件getopt.h，這個方法網上都是用這個的，所以我就不用了。這個方法比我上面的簡單好寫點。

然後是模擬演算法實現，先處理讀入的文件，每一行的操作指令，address，size都處理出來。

接著就是對於每條指令，模擬Cache的操作，我這邊寫的不太優美，沒寫結構體，就開了幾個數組。因為是模擬 ，很多東西可以不用實現，只有幾個數組是有用的。

只需要開有效位，標記位，以及最近使用時間三個數組即可，然後對於三種操作，load，store，modify，也很簡單，根本不需要單獨實現三個函數。

load就是載入一個數據，如果不在Cache中就miss，然後放進Cache（可能需要移除一個），store也是相同操作，所以這倆個就是一樣的。modify就是load+store，執行兩次同一個函數就行了，但是因為load之後，數據肯定在Cache中，所以直接輸出hit就行了。

這樣就大大簡化了這個題目。代碼不夠優美，不過還是貼一下：

#include "cachelab.h"n#include <string.h>n#include <stdio.h>n#include <stdlib.h>n#include <getopt.h>n#include <unistd.h>nnint miss,hit,evictions;nchar input[50];nlong change2number(char *ss){ntint len=strlen(ss);ntlong ret=0;ntfor(int i=0;i<len;i++){nttret=ret*10+(ss[i]-0);nt}ntreturn ret;n}nnint hexnumber(char c){ntif(c>=0&&c<=9) return c-0;ntif(c>=a&&c<=f) return c-a+10;ntif(c>=A&&c<=F) return c-A+10;ntreturn 0;n}nnvoid op_load(int index,int ttab,ntttint S,int E, int *vaild,ntttlong *tab,int *recenttime,int count){nntfor(int i=index*E;i<(index+1)*E;i++){nttif(vaild[i]&&tab[i]==ttab){ntttprintf("%s hitn",input);nttthit++;ntttrecenttime[i]=count;ntttreturn;ntt}nt}ntfor(int i=index*E;i<(index+1)*E;i++){nttif(!vaild[i]){ntttvaild[i]=1;nttttab[i]=ttab;ntttprintf("%s missn",input);ntttmiss++;ntttrecenttime[i]=count;ntttreturn;ntt}nt}ntint flag=0;ntint maxn=1e9;ntfor(int i=index*E;i<(index+1)*E;i++){nttif(recenttime[i]<maxn){ntttmaxn=recenttime[i];ntttflag=i;ntt}nt}ntprintf("%s miss evictionn",input);ntmiss++;evictions++;nttab[flag]=ttab;ntrecenttime[flag]=count;n}nnnint main(int argc, char* argv[]){ntint s,S,E,b;ntFILE *fp;ntfor(int i=1;i<argc;){ntt//printf("%s",argv[i]);nttif(argv[i][0]==-){ntttif(argv[i][1] == s){ntttti++;ntttts = change2number(argv[i]);nttttS = (1<<s);ntttti++;nttt}ntttelse if(argv[i][1] == E){ntttti++;nttttE = change2number(argv[i]);ntttti++;nttt}ntttelse if(argv[i][1] == b){ntttti++;nttttb = change2number(argv[i]);ntttti++;nttt}ntttelse if(argv[i][1] == t){ntttti++;nttttfp = fopen(argv[i],"r");ntttti++;nttt}ntt}nt}ntmiss=0,hit=0,evictions=0;nt//printf("%d %d %dn",s,E,b);ntint *vaild = (int *)malloc(sizeof(int)*S*E);ntlong *tab = (long *)malloc(sizeof(long)*S*E);ntint *recenttime = (int *)malloc(sizeof(int)*S*E);ntfor(int i=0;i<S*E;i++){nttvaild[i] = 0;ntttab[i] = 0;nttrecenttime[i] = 0;nt}ntint count=0;ntwhile(fgets(input, 100,fp)){ntt//printf("%s",input);nttcount++;nttint len=strlen(input)-1;nttinput[len]=0;nttint op;nttint dou=0;nttint size=0;nttlong address = 0;nttfor(int i=0;i<len;i++){ntttif(input[i]==I) op=0;ntttelse if(input[i]==L) op=1;ntttelse if(input[i] == M) op=2;ntttelse if(input[i] == S) op=3;ntttelse if(input[i]== ) continue;ntttelse if(input[i] == ,) dou=1;ntttelse{nttttif(!dou){ntttttaddress = address*16+hexnumber(input[i]);ntttt}nttttelse size = size*10+(input[i]-0);nttt}ntt}nttint offset = 0;nttint indexgroup = 0;nttfor(int i=0;i<b;i++){ntttoffset=offset*2+(address&1);ntttaddress>>=1;ntt}nttfor(int i=0;i<s;i++){ntttindexgroup = indexgroup*2 + (address&1);ntttaddress>>=1;ntt}nttif(op==1||op==3) op_load(indexgroup, address, S, E, vaild, tab, recenttime,count);nttif(op==2){ntttop_load(indexgroup, address, S, E, vaild, tab, recenttime,count);ntttprintf("hitn");nttthit++;ntt}nt}n printSummary(hit, miss, evictions);n return 0;n}n

最後要提的一點是這個題目，必須解決所有的warning，不然編譯時warning就會變成error。

2. part B

part B是優化矩陣轉置演算法，使用分塊的方法，讓Cache的miss次數越少越好

題目給的Cache大小只有 1024B，s=5，E=1，b=5。給的數據大小分別是32×32,64×64,61×67

然後只能只用12個int變數

32×32

第一題要求miss次數在300以下，首先觀察，Cache的一個塊只有32B，也就是只能容納8個int。這個Cache可以容納這個matrix的前8行。分塊的話，肯定是取8×8的比較合適。先讀取A的一行，然後放入B的一列。12個int變數，4個用來循環，其餘8個用來存A中塊的一行。

對於在對角線上的塊，A中每讀一行，會有一次miss，也就是miss次數是讀取操作的1/8，對於B數組的話，第一次讀取這行會產生一次miss，之後對於第i行，只有A中讀到第i行的時候，會被移除出Cache，然後存的時候會產生一次miss。可以粗略計算為miss次數是讀取次數的1/4。

對於不在對角線上的塊，做轉置的時候，A還是1/8的miss率，B的每行在Cache中和A的行不衝突 ，所以也是1/8的miss率，我們計算下最後大概多少次miss呢？

大概是

最後跑出來的答案是287，非常接近。

64×64

這題比較難，因為大小和前面變化了，並且次數卡的比較緊，必須1300次以下。

首先考慮Cache中只能放4行A中的行，如果再用8×8的塊，前面4行可以填入，後面4行會在Cache中發生衝突，導致miss次數增加。

如果只用4×4的塊呢？那麼每次Cache中放入8個int，我們卻只用4個，浪費嚴重，我用這個方法最少也只能做到1677次miss。

有一種很巧妙的方法，就是還用8×8的塊來做，題目說A數組不能變換，但是說B數組可以任意操作啊。我們必須要一步到位嘛？可否考慮先把數字移動到B中，然後在B中自己做變化。

考慮用同樣的miss次數，把更多的數據移動到B中，但是不一定是正確的位置，然後再用同樣的miss次數，把A中部分數據移動到B中時，完成把B中前面位置錯誤數據的糾正。

如圖：

畫的線的分割是讀入到Cache中的行以及寫入到B中的順序。（第二步有些畫錯了，A左下角應該是按列取數據）

1.先考慮把A的上半部分存入到B，但是為了考慮Cache不衝突，所以把右上角的4×4的區域也存在B的右上角。對於在對角線上的塊，A的miss率是1/8，B的左上角部分miss率是1/2。對於不在對角線上的塊，A的miss率還是1/8，B左上角部分的miss率為1/4.

2. 接下來這步是減少miss率的關鍵，把A左下角的一列4個數據讀出，B右上角的一行4個數據讀出，都用int變數暫存，然後把前四個填入B右上角行中，後四個填入B的左下角行中。

因為從B右上角讀取的時候，把塊放入了Cache，然後從A往B中填的時候，就不會出現miss操作。

來計算一下miss率，對於在對角線上的塊，從A左下角讀取miss率為1，B的右上角的操作miss率為1/4，B的左下角miss率為1/4。對於不在對角線的快，A的miss率為1/4，B右上角miss率為0，左下角miss率為1/4。

3. 最後一步就是把A的右下角填入B的右下角，對於在對角線上的塊，A的miss率為1/4，B的miss率為1/2.不在對角線上的塊，A，B的miss率都為0.

最後我們來計算下miss的次數吧，計算出來近似是1280次，實際我們代碼跑出來是1219次 。

61×67

不規則的matrix，本質也是用分塊來優化Cache的讀寫，但是不能找到比較顯然的規律看出來間隔多少可以填滿一個Cache，但是由於要求比較松，我們可以嘗試一些分塊的大小，直接進行轉置操作。嘗試到16左右 ，可以小於2000次miss。

三個題的代碼如下：

char transpose_submit_desc[] = "Transpose submission";nvoid transpose_submit(int M, int N, int A[N][M], int B[M][N])n{ n int a1,a2,a3,a4,a5,a6,a7,a8;n int i,j,k,h;n if(N==32){n for(i=0;i<4;i++){n for(j=0;j<4;j++){n for(k=i*8;k<(i+1)*8;k++){n h=j*8;n a1=A[k][h];a2=A[k][h+1];a3=A[k][h+2];a4=A[k][h+3];n a5=A[k][h+4];a6=A[k][h+5];a7=A[k][h+6];a8=A[k][h+7];nn B[h][k]=a1;B[h+1][k]=a2;B[h+2][k]=a3;B[h+3][k]=a4;n B[h+4][k]=a5;B[h+5][k]=a6;B[h+6][k]=a7;B[h+7][k]=a8;n }n }n }n }n else if(N==64){n for(i=0;i<64;i+=8){n for(j=0;j<64;j+=8){n for(k=j;k<j+4;++k){n a1=A[k][i];a2=A[k][i+1];a3=A[k][i+2];a4=A[k][i+3];n a5=A[k][i+4];a6=A[k][i+5];a7=A[k][i+6];a8=A[k][i+7];nn B[i][k]=a1;B[i][k+4]=a5;B[i+1][k]=a2;B[i+1][k+4]=a6;n B[i+2][k]=a3;B[i+2][k+4]=a7;B[i+3][k]=a4;B[i+3][k+4]=a8; n }n for(k=i;k<i+4;++k){n a1=B[k][j+4];a2=B[k][j+5];a3=B[k][j+6];a4=B[k][j+7];n a5=A[j+4][k];a6=A[j+5][k];a7=A[j+6][k];a8=A[j+7][k];nn B[k][j+4]=a5;B[k][j+5]=a6;B[k][j+6]=a7;B[k][j+7]=a8;n B[k+4][j]=a1;B[k+4][j+1]=a2;B[k+4][j+2]=a3;B[k+4][j+3]=a4;n }n for(k=i+4;k<i+8;++k){n a1=A[j+4][k];a2=A[j+5][k];a3=A[j+6][k];a4=A[j+7][k];nn B[k][j+4]=a1;B[k][j+5]=a2;B[k][j+6]=a3;B[k][j+7]=a4;n }n }n }n }n else{n for(i=0;i<N;i+=16){n for(j=0;j<M;j+=16){n for(k=i;k<i+16&&k<N;k++){n for(h=j;h<j+16&&h<M;h++){n B[h][k]=A[k][h];n }n }n }n }n }n}n

3. 總結

part A比較簡單，主要是模擬出Cache的功能。part B比較有難度，思考了很久，同時在做出來之後，還通過定量的計算miss次數，和實驗結果接近，讓我對Cache理解更深了。Cache這套理論非常重要，要在以後編程中編寫對Cache友好的代碼，我還有很多路需要走。