著名的CMU CSAPP：3e的Lab源码与答案 cmu 15-213

# Lab4 CacheLab The original tar file is `cachelab-handout.tar` and the writeup is `attacklab.pdf`. My solution is in `cachelab-handout`. Read `6 Working on the Lab` in the writeup file before starting Part A, and Part B: these notes are at the end of the file and you might not notice them early enough. However, they provide useful information about the two tasks. ### Part A PartA is relatively easy, if you remember the following: - When reading the address, use `long long` for possible long address, and use `%llx`, to read a `long long int` hex form. - As `s`, `E`, `b` are all constants determined at run time, you cannot construct an array directly. You have to use `malloc` to dynamically allocate memory on the heap. Note that, actually the compiler would not stop you from doing so, but the result is undefined. - You should be clear about the operations: `L`, `S`, and `M`. - `L`: load the data into cache. Possible outcome: `hit`, `miss`, `miss eviction`. - `S`: store/write data from cache back to memory. If the data is already in the cache, write back. If the data is not originally in the cache, load the data into cache, and then write back. Possible outcome: `hit`, `miss`, `miss eviction`. - `M`: modify some data (load the data into cache, modify, and write back to memory), can be considered as a combination of `L` and `S`. Because after `L`, the data must be in the cache, so the outcome of `S` must be `hit`. ### Part B Part B is much harder. To solve this, you should recall how cache works: by extracting the set bits and tag bits from the address. Thus, the cache eviction behaves differently when dealing with Matrix of different size. For example, in 32x32 problem, the cache can contain at most 8 rows, so the 9th row would evict the 1st row; but in 64x64 problem, the cache can contain at most 4 rows, so the 5th row would evict the 1th row. Blocking technique is used for all problems in Part B. Estimating/Computing cache miss is an important skill you pick up and get familar with when working on this part. There are a lot of notes and explanationn in the `trans.c` file. *Sidenote*: I found the 64x64 problem very hard and turned to Google for help. When searching in English, most results only contain code but no explanation at all. When searching in Chinese "cache lab 解答", a lot of useful blogs and answers come out. - 32 x 32 This part is still handlable. The cache can contain at most 8 rows, so the block size cannot be larger than 8, otherwise cache misses occur even within the same block. It turns out that 8x8 blocking gives satisfying result. - 64 x 64 This part is much harder. The cache can contain at most 4 rows, so the block size cannot be larger than 4. Function `blocksize_4_64_64` applies the blocking naively but the result is 1699 misses, the reason is that since the blocking size is smaller than the size of the if cache line, cache is not fully utilizd. I improved the function to `blocksize_8_4_64_64`, where we consider four 4x4 blocks within a 8x8 block at the same time. The performance is better, with 1475 misses and gives me 6/8 points. I did not pursue further improvement, as I already spend a lot of time on it. - 67 x 61 Much simpler than 64 x 64 case, as the number is not good. Simply apply the blocking naively and experiment with different blocking size. Block size of 8 and 16 both give satisfying result. ### Thoughts I spent around two hours on Part A, when I did not use `malloc` to allocate the cache data structure, but use `cache_line_t cache[S][E]` directly, even though the writeup explicity requires the code to use `malloc`. When using `cache_line_t cache[S][E]`, after I set the valid bits to some value, they become random value when I try to access them in other functions. Then I swithch to `malloc`, no such problem occurs, and I finish the problem in one or two hours. The lesson from this is that: First, when you need an array whose size is not known at compile time, use `malloc` to allocate memory dynamically. Second, and more importantly, do not be afraid to use `malloc` and pointers in C. I also wasted some time on Part B. Somehow at some point, I began to think that each row in the matrix would be mapped to a cache set and blablabla, which is obviously wrong. But, coincidently, I finished the 32 x 32 case successfylly, which is even worse because it took a very long time for me to find this great mistake in concept... The process is a bit painful, but really help me learn cache mechanism, blocking and caching performance compution.