# Ch.5-2 Basics of Cache
###### tags: `Computer Organization`, `計算機組織`
## Review
注意設計memory hierarchy的時候有四大重要問題：
1. block placement
2. block identification
3. block replacement
4. write strategy
## Direct-Mapped Cache
:::info
**KEY POINT**：一個蘿蔔一個坑
:::
### Block Placement
memory灰色的部分就對應cache灰色的部分
memory橘色的部分就對應cache橘色的部分
假設memory跟cache都有2的冪次方個block
則memory對應的cache block就是取餘數
（圖中memory有32個block，cache有8個blcok，則memory中2、10、18、26除以8的餘數都是2，所以這幾個對應到cache都是第2個block）
（最簡單的判斷方式就是看低位元，cache有$2^N$個block，就看memory各個block的最低$N$位元）
### Block Identification
1. valid bit：判斷資料是否有效（剛開機的都是無效，因為是之前存留下來的，所以要將valid bit設為0，表示這資料不可以用）
2. tag：memory address中高位元的部分。因為從block placement中可以發現，有多個memory block會共用一個cache block，所以需要有個tag來判斷現在在cache中的資料是哪一個memory block。
### Block Replacement
識別block之後，若發現不是自己要的，就要找新的對應的資料再放入cache
如果cache中已經有東西，如何選擇要擠掉誰呢？
>選擇block編號一樣的！

（注意valid bit不一定是0或1，但tag一定和要換進去的不一樣，不然就沒有換的必要了）
（不過通常會選擇優先換掉valid bit = 0的無效資料）
### Write Strategy
#### Cache Misses
我們常說的「跟記憶體拿資料」實際上是跟cache拿資料
- 如果cache hit，CPU就可以直接拿，速度很快
- 如果cache miss，CPU就要到下一層級的儲存單位拿資料（可能是cache／memory）
:::info
cache miss有兩種狀況：
1. Instruction cache miss：連指令是什麼都不知道→直接重新抓指令
2. Data cache miss：沒有需要用的資料→抓到cache中後再重新讀取
:::
#### Data-write hit的狀況
如果發生cache hit，就會取出其中資料來用，可能會寫入新的值。
此時若只更新cache，沒有更新memory，就會發生inconsistent。
當資料不同步，就可能影響後續其他運作。
有以下解決方法：
1. Write through
有新資料就同步給memory
缺點：會使得CPU運作下降
原因：（舉例）
　　　假設`base CPI = 1`，有10%的資料是inconsistent的要被更新，每寫入一次記憶體要花費100個cycle
　　　則`effective CPI = 1 + 0.1 * 100 = 11`
　　　會變成原本的11倍之多，是我們所不樂見的
2. Write buffer
有新資料會同時放入cache跟buffer，然後CPU繼續做自己的事情，buffer中的資料再慢慢更新記憶體
缺點：buffer可能會滿，CPU還是要等到有空的buffer能用才可以繼續運作
一般write buffer不會太大，大約<font color=red>四個</font>；運作機制像queue一樣是**FIFO**。
CPU頻率若沒有太快，通常buffer不會滿，
可是當寫入頻率高，buffer來不及把資料更新給RAM時又有新資料來臨，
這樣CPU就要停下來，會造成系統效能下降。
3. Write-back
加入一個dirty bit的機制
有資料更新，只更動cache，不主動寫回memory
運作：剛開始dirty bit = 0
　　　如果cache的資料有被更新，就令dirty = 1
　　　下次要更新時，如果要更新的block的dirty = 0則直接更新
　　　dirty = 1則將cache的資料放入write buffer再更新cache
#### Data-write miss的狀況
解決方法：
1. Write-allocate：重新把資料從memory放入cache
2. Wrtie around：不要把資料寫入cache了，直接寫入memory

如何選擇？
write around適合在程式一開始宣告並初始化一堆變數時使用，因為往往不會很快就用到他們；write-allocate則會用在預期很快就要用到的狀況。
所以write miss發生時，可以選擇要把資料放到cache還是memory

通常write hit是使用write back的話，write miss會搭配write allocation
而write hit是使用write through的話，write miss會搭配write around

### Example
1. P30-35頁
2. P36，假設cache大1KB，每個block大小是1 word->則有1K個blocks
3. P37，假設有64個blocks，每個block大小是16 bytes；問位址1234會在哪個block？
4. MIPS的cache architecture
## Memory Design to Support Cache
**調整memory設計以提升cache效能**
主要有三種方法將memory的資料傳給cache：

1. One-word-wide memory organization
memory、cache的寬度是1 word
所以傳輸用的bus寬度也是1個word
缺點：慢
2. Wide memory organization
memory、cache的寬度是4 word
所以傳輸用的bus寬度也是4個word
缺點：貴
3. Interleaved memory organization
memory是4個word，但是cache只有1個word
採用寬度為1個word的bus
特點：速度慢了一點，但是省錢很多


如果沒有用interleave，記憶體之間的資料存取必須等待memory cycle過完才可以
（如圖中上半部）
如果採用interleave，則可以同時做memory access，再慢慢讓bus傳輸

### Example
假設memory傳資料給cache有以下硬體條件：
* 1 memory bus clock to send the address傳輸地址
* 15 memory bus clocks for each DRAM access initiated做memory access
* 1 memory bus clock to send a word of data傳輸資料
* A cache block = 4 words

則有以下各種organizations的狀況：
1. 一個word的寬度的bank & bus
傳輸一個block（4 words）所需的資料
需要先傳1次地址，再傳4次資料，再存取4次資料
2. 兩個word的寬度的bank & bus
傳輸一個block（4 words）所需的資料
需要先傳1次地址，再傳2次資料，再存取2次資料
3. 四個word的寬度的bank & bus
傳輸一個block（4 words）所需的資料
需要先傳1次地址，再傳1次資料，再存取1次資料
4. 四個word的寬度的bank & 一個word寬度的bus
傳輸一個block（4 words）所需的資料
需要先傳1次地址，再傳1次資料，再存取4次資料