CSAPP Lab -- Cache Lab

CSAPP Lab -- Cache Lab

在計算機存儲器體系中，Cache是CPU和主存之間的中間地帶，用來彌補CPU和主存速度差異，提升效率。（台灣那邊翻譯成快取，更恰當些）。Cache Lab分為Part A和Part B兩個部分。Part A是實現一個Cache模擬器，用來模擬程序運行過程中的cache訪問的結果。Part B是通過blocking技術來優化矩陣求逆運算，減少miss次數。

PART A

這個部分的目標，就是實現一個cache simulator，需要完成csim.c這個文件，然後通過./test-csim。Lab中已經提供了一個參考程序./csim-ref，通過運行這個程序，可以了解到我們應該實現的程序的大概樣子。

輸入的是一系列參數(-v -b -E -s -t):

? -h: Optional help flag that prints usage info? -v: Optional verbose flag that displays trace info? -s <s>: Number of set index bits (S = 2sis the number of sets)? -E <E>: Associativity (number of lines per set)? -b <b>: Number of block bits (B = 2bis the block size)? -t <tracefile>: Name of the valgrind trace to replay

-t參數給是用來測試的traces，內容格式是這樣:

I 0400d7d4,8M 0421c7f0,4L 04f6b868,8S 7ff0005c8,8

每行都是[space]operation address,size的格式。這些traces都是程序運行過程中對cache的訪問記錄，是使用valgrind工具來獲取得到的。trace中只有四種操作:

- I 表示load一條指令

- M 表示modify，也就是修改數據(先讀取，後寫入)

- L 表示load數據，就是讀取數據

- S 表示store數據，就是寫數據

所以，根據trace中的輸入，我們要處理每一條operation，然後給出緩存模擬的結果(miss、hit、eviction)。

因為這個lab並不需要我們真正地讀取或者寫入數據，只需要返回cache hit或者cache miss等各種情況即可，所以，我們不需要用到

在了解了lab背景後，就可以開始設計程序了。

整個程序的框架： 解析命令行參數 -> 讀取trace -> 初始化cache -> 逐行運行operation -> 輸出結果。

首先，設計數據結構，cache和operation:

typedef struct argumemts { int h; int v; int s; //number of set index bits. S = 2^s int E; //number of cache lines per set int b; //number of block bits. B = 2^b is the block size. char *t; //name of the valgrind trace to replay} Arguments;typedef struct cache_line { int valid_bit; int tag_bit; int times;} CacheLine;typedef CacheLine* CacheSet;typedef CacheSet* Cache;typedef struct operations { char op; long address; int size;} Operation;

對於operation，就根據題目中所給的命令行參數，把參數都裝在一個struct中就行了。

然後就是cache的設計，一個cache由若干cache set組成，而每個cache set又由若干cache line組成。實際上，相當於一個二維數組。所以，只需要設計好cache line就行了。

對於cache line，模擬實際cache line的設計，組成部分包括標誌位和有效位，但是丟棄了真正存儲數據的block（我們只需要實現模擬器，不需要真正存儲數據）。 因為cache採用的時LRU的替換原則，所以，當發生衝突的時候，替換掉的應該是緩存組中最長時間沒有使用的line。為了實現這個LRU原則，我們給每個cache line加上一個時間戳，用來記錄time，為發生eviction的時候的替換作準備。

在設計好了數據結構之後，我們就可以開始實現整個模擬器的邏輯了。

首先解析命令行參數，使用了getopt.h這個庫:

void get_args(Arguments *args, int argc, char **argv) { int opt; while (-1 != (opt = getopt(argc, argv, "hvs:E:b:t:"))) { switch (opt) { case h: args->h = 1; break; case v: args->v = 1; break; case s: args->s = atoi(optarg); break; case E: args->E = atoi(optarg); break; case b: args->b = atoi(optarg); break; case t: args->t = (char*)malloc(sizeof(char)*strlen(optarg)); strcpy(args->t, optarg); break; default: fprintf(stderr, "wrong argument
"); exit(0); break; } }}

解析好了參數，我們就初始化cache：

void init_cache(Cache *cache, Arguments *args) { int set_size = 1 << args->s, i, j; int num_lines = args->E; *cache = (CacheSet*)malloc(sizeof(CacheSet) * set_size); for (i = 0; i < set_size; ++i) { (*cache)[i] = (CacheLine*)malloc(sizeof(CacheLine) * num_lines); for (j = 0; j < num_lines; ++j) { (*cache)[i][j].valid_bit = 0; (*cache)[i][j].tag_bit = -1; (*cache)[i][j].times = 0; } }}

再就是讀取trace：

void parse_traces(Operation *operations, const char *filename) { FILE *fp = fopen(filename, "rt"); char op; long address; int size = -1, i = 0; while (fscanf(fp, "%c %lx,%d
", &op, &address, &size) != EOF) { if (size == -1) { continue; } operations[i].op = op; operations[i].size = size; operations[i++].address = address; } fclose(fp);}

到這裡，我們的準備工作就完成了，只剩下最核心的部分了。我們遍歷所有的operation，依次對於每個operation作出相應的操作。

operation總共有四種類型: I, M, S, L。其中I我們不處理(I時載入指令)，然後S和L實際上模擬的過程是一樣的，不管是讀還是寫，我們都是根據一個地址來訪問cache。所以我們統一用一個process函數來處理。而M不同，因為modify涉及到讀和寫，相當於調用兩次process函數。

去掉關於IO部分的一些代碼，遍歷operations來處理的部分:

for (int i = 0; i < num_op; ++i) { switch (operations[i].op) { case I: // not used in this lab. break; case M: process(&cache, &args, operations[i].address); process(&cache, &args, operations[i].address); break; case L: process(&cache, &args, operations[i].address); break; case S: process(&cache, &args, operations[i].address); break; default: printf("Error: invalid operation."); exit(0); } }

最後，我們來設計process函數。我們可以和回憶cache的運作方式。

對於一個address，在訪問cache的時候，它會被這樣解析:

這裡的10就是參數中的s，而4就是參數中的b。

所以，我們可以解析address，來分別得到標記位、緩存組索引和塊偏移。因為我們不需要進行真正的數據處理，所以不用管塊偏移。

然後，根據組索引找到相應的緩存組，遍歷這個緩存組，如果由cache line的tagbits和我們地址中的tag bits對上了號，那麼就是hit，列印"hit"，結束處理。

如果這一次沒有找到，那麼就說明我們是miss了，那麼就是列印"miss"，然後開始第二次遍歷，目的是為了尋找是否有空的cache line，如果有，就修改有關信息，然後結束。如果沒有，就說明我們是eviction，列印"eviction"。然後第三次遍歷，找到在這裡面待了最長時間的cache line，根據LRU替換原則，將其替換掉。

附上process函數代碼:

void process(Cache *cache, Arguments *args, int address) { address >>= args->b; int set_index = 0, i, tag_bits; long mask = 0xffffffffffffffff >> (64 - args->s); set_index = mask & address; address >>= args->s; tag_bits = address; CacheSet set = (*cache)[set_index]; for (i = 0; i < args->E; ++i) { if (set[i].valid_bit == 1) { set[i].times++; } } for (i = 0; i < args->E; ++i) { if (set[i].valid_bit == 1 && set[i].tag_bit == tag_bits) { printf("hit "); set[i].times = 0; ++hit_count; return; } } ++miss_count; printf("miss "); for (i = 0; i < args->E; ++i) { if (set[i].valid_bit == 0) { set[i].tag_bit = tag_bits; set[i].valid_bit = 1; set[i].times = 0; return; } } ++eviction_count; printf("eviction "); int max_index = 0, max_time = set[0].times; for (i = 0; i < args->E; ++i) { if (set[i].times > max_time) { max_index = i; max_time = set[i].times; } } set[max_index].tag_bit = tag_bits; set[max_index].times = 0;}

PART B

這個部分就是利用分塊(blocking)技術來加速矩陣逆轉運算，減少cache miss。總共有三個題，分別是32*32、64*64和61*67的矩陣。

32*32

通過閱讀csapp官網提供的ppt和關於block相關的資料，我們可以了解到分塊減少cache miss的大概原理，然後開始嘗試。

通過簡單測試，可以發現分塊size為8的時候，效果是最好的。而且，從理論上來分析，我們可以得到miss次數應該是:(32/8)(32/8)(8+8) = 256。但是，實驗結果並不是這樣，而是三百多次。

為了探究原因，可以使用PART A我們寫的模擬器來運行這個lab生成的trace(保存在trace.f0中)。然後，我們修改模擬器加上一些信息，列印出每次操作所選擇的cache set。這是前八行：

L 30a080,4 緩存組:4 標記位:c28 miss eviction S 34a080,4 緩存組:4 標記位:d28 miss eviction L 30a084,4 緩存組:4 標記位:c28 miss eviction S 34a100,4 緩存組:8 標記位:d28 miss L 30a088,4 緩存組:4 標記位:c28 hit S 34a180,4 緩存組:c 標記位:d28 miss L 30a08c,4 緩存組:4 標記位:c28 hit S 34a200,4 緩存組:10 標記位:d28 miss

分析這個，我們可以發現，在一些不應該miss的地方，出現了miss，而且都是eviction，也就是發生了衝突。這樣，就會在某些地方出現A和B的某個部分不停輪流佔據某一個cache line，就造成了很多的miss。

為了解決這個問題，我們可以用臨時變數來存儲一個行，這樣就可以提高效率，每次讓A依次讀完，而不會去和B搶佔一個cahce line。

for (i = 0; i < M; i+=8) { for (j = 0; j < N; j += 8) { for (k = i; k < i+8; ++k) { a = A[k][j]; b = A[k][j+1]; c = A[k][j+2]; d = A[k][j+3]; e = A[k][j+4]; f = A[k][j+5]; g = A[k][j+6]; h = A[k][j+7]; B[j][k] = a; B[j+1][k] = b; B[j+2][k] = c; B[j+3][k] = d; B[j+4][k] = e; B[j+5][k] = f; B[j+6][k] = g; B[j+7][k] = h; } }}

64*64

這次發現size為8的分塊不再有效，miss達到了四千多次。思考一下，假設A[0][0]的地址為0x0，所以分組為0。然後A[1][0]的地址是64*4*1，，組索引的計算是(address >> 5取最底5位)，所以，組索引應該是0x1000。然後繼續:

A[2][0] -- 64*4*2 >> 5 -- 0x10000

A[3][0] -- 64*4*3 >> 5 -- 0x11000

A[4][0] -- 64*4*4 >> 5 -- 0x100000

到這時候，可以發現A[4][0]的組索引又到了0，所以，如果size為8的分塊，會導致組內的衝突。

然後，我們可以嘗試更小的分組，size為4的分組，再結合前面使用臨時變數的方法，就可以把miss降到可以接受的水平。

for (i = 0; i < M; i+=4) { for (j = 0; j < N; j+=4) { for (k = i; k < i+4; ++k) { a = A[k][j]; b = A[k][j+1]; c = A[k][j+2]; d = A[k][j+3]; B[j][k] = a; B[j+1][k] = b; B[j+2][k] = c; B[j+3][k] = d; } } }

這個解還是不能拿到滿分，可以參考其他解決方法。

61*67

類似於前面，通過分析可以發現應該使用size為16的分塊，然後額外解決沒有處理到的那部分就行了。

for (i = 0; i+16 < N; i+=16) { for (j = 0; j+16 < M; j+=16) { for (k = i; k < i+16; ++k) { a = A[k][j]; b = A[k][j+1]; c = A[k][j+2]; d = A[k][j+3]; e = A[k][j+4]; f = A[k][j+5]; g = A[k][j+6]; h = A[k][j+7]; B[j][k] = a; B[j+1][k] = b; B[j+2][k] = c; B[j+3][k] = d; B[j+4][k] = e; B[j+5][k] = f; B[j+6][k] = g; B[j+7][k] = h; a = A[k][j+8]; b = A[k][j+9]; c = A[k][j+10]; d = A[k][j+11]; e = A[k][j+12]; f = A[k][j+13]; g = A[k][j+14]; h = A[k][j+15]; B[j+8][k] = a; B[j+9][k] = b; B[j+10][k] = c; B[j+11][k] = d; B[j+12][k] = e; B[j+13][k] = f; B[j+14][k] = g; B[j+15][k] = h; } } } for (k = i; k < N; ++k) { for (l = 0; l < M; ++l){ B[l][k] = A[k][l]; } } for (k = 0; k < i; ++k) { for (l = j; l < M; ++l) { B[l][k] = A[k][l]; } }

推薦閱讀：