# Ch.5-3 Measuring and Improving Cache Performance
###### tags: `Computer Organization`, `計算機組織`
探討如何改善快取記憶體的效率
## Measuring Cache Performance
前面（紙本筆記）有提到衡量CPU效率可以看CPU time
但是因為CPU time不只要考慮CPU本身，還攸關到memory存取的時間
所以CPU time包含**cache hit的存取時間**跟**cache miss的memory存取時間**
所以出現了`Memory stall cycles`專門計算memory造成的時間影響


如果memory stall cycles越低，表示越好
反之則為越差（因為一直cache miss）

### Miss Example

I-cache處理指令instruction
D-cache處理資料data
所以miss cycles per instruction裡面
I的部分才只要算miss rate * miss penalty就好
而D要將load & store佔的比例考慮進去（因為只有他們要用data）

最後的結果可發現miss造成CPU time上升2.72倍之多
hen~~浪費時間

### Average Access Time
除了miss的部分會影響到以外，hit其實也很重要
這節探討每一次hit要花多久時間存取資料
:::info
**Average memory access time (AMAT)**
AMAT = hit time + miss rate * miss penalty

hit time：在cache中找到並存取資料的時間
miss rate：沒在cache中找到資料的比例
miss penalty：轉而到memory找出並存取資料的時間
:::
#### Example
### Performance Summary
1. CPU的效能急速上升的同時，記憶體卻沒有以一樣的速度在進步，所以會造成memory仍然會拖慢CPU效能的問題
2. 「利用pipeplining提升CPI，卻沒有提升memory」的狀況，使得memory stall cycle變高、變嚴重
3. CPU頻率一直上升，會使得memory stall造成的延遲更嚴重

基於以上，評估系統效能時，不可以忽略記憶體帶來的影響。
## Improving Cache Performance
可以改進memory效能的部分：
1. Reduce the miss ratio（減少miss rate）
2. Reduce the time to hit in the cache（減少hit time）
3. Reduce the miss penalty（減少miss時<font color=blue>到memory找資料的時間</font>）
### Exploiting Spatial Locality
利用saptial locality的特性，達到「一人得道，雞犬升天」。

:::info
透過加大block的size，讓一個被存取到的資料<font color=red>其鄰近周圍的資料</font>也可以一起被放入cache
也因此上面的欄位中，會多出block offset，用以表示所要的資料是在第幾個word
並且會因為多了block offset，而需要減少tag的bit數
:::
:::warning
正常而言，block的大小增加，應該可以減少miss rate
然而**可能會衍生以下狀況**：
1. 如果cache大小固定，單一block大小變大，總block個數就會變少
也就造成對應同一個block的memory會變多
變相競爭哪個memory可以被放入（發competition）
反而造成miss rate提升
2. 如果根據spatial locality放入的資料其實並沒有要用到，會形成pollution
3. 因為block size變大，一次要搬移的資料量變多
這會造成miss penalty上升

以上的解決方法：先把要用到的資料搬入cache就好，其他部分慢慢搬移
:::
### Associative Caches
利用「狡兔三窟」的概念，讓memory不再只對應到「唯一一個」cache block，用以解決competition的狀況。
1. Fully associative
memory可以放在**任意**block
但是這樣要取出資料時，會因為不知道所要的資料在哪裡（無跡可尋）
而必須將每個tag都拿來比較
這樣花費的硬體成本"非常高"
2. n-way set associative
假設總共有$m$個block
把所有的block分成$m/n$個set，每個set有$n$個block
memory對應的block是<font color=red>address % (set個數)得到的結果對應的set之中的某個block</font>
找資料時，只要比對對應set中那$n$個block的tag即可
雖然還是要比較，但是可以減少使用硬體，較fully省錢
#### Comparison with Direct Mapped

最下面的8-way set其實也就是fully了
注意：fully的狀況下，不會有index的欄位，因為只有一行
　　　2^0 = 1所以0bit就可以表示一行了

#### Example
1. Directed mapped

    紅色字體是發生replace的狀況

2. 2-way set associative

    要發生replacement的時候
    會選擇把「比較久」沒用到的東西清掉

3. Fully associative

    因為只有一個block，所以沒有index欄位

#### How Much Associativity
以下是實際計算出來，使用n-way set之後miss rate的數值
可以發現，雖然的確有效助於降低miss rate
但是n的數字越大，降低的miss rate幅度越小
所以不需要用到太大，因為得到的少，付出的成本又多
#### Tag Comparing Structure
1. Directed mapped
做memory access時，就會同時得到tag、data
透過「比對tag是否為想要的」來決定為hit還是miss
可以發現，還沒決定是否為hit時，已經有data在手，因此可以先拿來運算
如果是hit就賺到，是miss的話不要採用就好了
（類似之前branch prediction的概念）
2. N-way set associative
做memory access時，同時只會得到是在哪一個set
之後才能在這個set中比對tag，並用MUX選出對應的data
所以這裡的data會在hit決定之後才被取得
採用這種方法index會減少，但是因為大小固定，所以bit數不變，會使得tag bit變多
#### Cache Block Replacement
如果從memory要搬東西到cache時，發現該block已經有資料，要如何選擇要被替換掉的資料？
1. Directed mapped
最簡單。
因為是<font color=blue>「一個蘿蔔一個坑」</font>，所以block存有舊資料的狀況下，若有新資料要進來，直接取代就好了。
2. Set associative or fully associative
因為有一個memory可以在多個不同的block，
所以要選擇替換掉誰，可以設計一個replacement policy並遵循之。
:::info
Replacement Policy：
1. Random：隨便丟
2. LRU：丟最近沒用到的（這個最常被採用）
3. MRU：丟最近有用到的（實務上不太會使用）
:::
### Multilevel Caches
前面探討的是減少miss rate的部分
這個小節提到的可以減少hit time跟miss penalty
:::info
Multilevel顧名思義就是有多層級關係
一般是L1-L2-main memory
高階處理器會是L1-L2-L3-main memory

L1：最小、最快、最接近處理器
L2、L3：數字越大的容量也越大，也因此速度會比前者慢，但仍然遠快於main memory
L1發生miss會去L2，L2發生miss會去L3，連L3都miss才會去main memory找
:::
#### Example
* 只有L1 cache
* 加上L2 cache
可以發現performance相較只有L1的狀況下，提升2.4倍

#### Multilevel Cache Considerations
L1主要是用來減少hit time
L2、L3則是減少miss rate，透過減少局部的miss penalty，進而減少整體的miss penalty
### Sources of Cache Misses
造成miss的原因（3C）
1. Compulsory（cold start, process migration）
程式剛開始執行時，因為剛剛才開始嘛，所以東西都還沒放到cache
這是一定會發生，無法被避免的

如果一個程式很大，可能有數十億個指令時，這種miss造成的影響微不足道
因為只有最一開始會發生那一段時間而已
2. Conflict（collision）
好幾個memory對應到同一個cache block的狀況
可以增加cache size或用associativity來避免、減少competition發生
3. Capacity
這是說要用的資料比cache的size還大，這樣一定會發生miss
因為cache就放不下
所以加大cache size即可（但會導致速度變慢）

註　Invalidation：
cache中有某一塊記憶體的資料，然而這塊記憶體因為外部動作，被更新過
此時cache就必須將對應block的資料清除，否則就是舊資料

### Cache Design Space
設計一個cache有很多地方可以考量：
沒有哪一種最好，因為快就小、大就慢，還有價格的問題
所以都要視需求衡量
通常**越簡單的設計越容易成功**
### Cache Summary
1. 能夠讓cache提升效能，最大的原因在於**Principle of Locality**
其中又包含了temporal locality跟saptial locality
2. 造成miss的三大主因Compulsory、Conflict、Capacity
3. 設計cache可以考量的點有size、associativity、replacement policy、write-hit policy、write-miss policy