Cache的工作方式复习
参考资料: 华盛顿大学课程讲义
简单来说就是内存地址的一个非单射满射，对于长度为M的地址，取用其中的X位来索引所在集和，这X位之后的Y位来索引字节，这X位的前(M-X-Y)位来作为标记。最常采用的应该是Set-associative cache，它是Direct-mapped与Fully-associative的折衷。
-
Cache is a series of blocks, store a block at a time
-
Cache can be orgnized into differet formats
1. Direct-mapped cache
address: $i$ mod cache_size
additional bits: tag and valid bit
two problems in direct-mapped cache:
1. no spatial advantages
2. conflicts
Exploit spatial locality
address: ($i$ / block_size) mod block_num
2. Fully associative cache
Data can be put into any block, no mapping at all.
Reduce conficts and fully use cache blocks.
disadvantages of fully associative cache:
1. tag is address in fact
2. have to search the whole table for data, because data can be anywhere
3. Set-associative cache
Introduce groups of blocks, called sets.
A set has $2^x$ blocks, called “$2^x$-way associative cache”
address: ($i$ / block_size) mod set_num
