# 近水樓台先得月

###### tags: `IT鐵人`

## 區域性原則

有在組裝電腦的人就會知道，電腦的儲存裝置包括記憶體跟硬碟，硬碟又有分成SSD跟HDD，記憶體的空間比較小，存取速度比較快；硬碟的空間通常比較大，存取速度較慢。另外還有很靠近CPU的快取記憶體，存取速度又更快了，我們的指令跟程式都是從這些地方拿來處理的。

在執行程式的時候，如果指令或是資料在需要的時候才抓進來，時間會拉很長，所以我們會期望當我們需要資料時，資料能正好在靠近的地方，就能更快的處理。

不過由於越快的裝置儲存的空間就越小，這個現象稱為區域性。

區域性(Locality)：程式在任何一個時間點只會存取一小部份的位址空間。

|時間區域性(temporal locality)|空間區域性(spatial locality)|
|-|-|
|如果一個項目被存許到，那麼它很快就會再次被存取。|如果一個項目被存取到，那麼它位址附近的項目也會很快被存取。|

## 不同的記憶體技術

剛剛提到的三種記憶體(快取記憶體、記憶體、硬碟)，他們的技術大概分為以下四種。

資料大概是2015~2018

|類型|技術|存取時間|價位(per GB)|
|-|-|-|-|
|快取記憶體|SRAM|1~10ns|$1000|
|主記憶體|DRAM||80ns|$10|
|SSD|Flash Memory|100,000ns|$1|
|HDD|Magnetic Disk|10,000,000|$0.1|

可以看到速度差距很大，但速度快的又很貴，所以才需要我們這個章節討論的內容。

## 快取系統與虛擬記憶體

剛剛介紹的記憶體中，我們將快取記憶體(Cache)跟主記憶體(Memory)稱為快取系統；主記憶體(Memory)跟硬碟(Hard Disk)稱為虛擬記憶體。

簡單來說我們會偏向將最需要的部份放在快的那一層，對於快取系統來說放在快取記憶體，對於虛擬記憶體來說放在主記憶體。

每次我們需要東西時，如果它正好在比較快的那層，我們就稱為hit，反之稱為miss。所以我們要盡可能提昇hit rate，減少miss rate。

當東西不在快的那層時，我們就需要比較多的時間去下面一層尋找，這時要花比較多的時間，稱之為miss penalty，就是出錯得到的懲罰。

## Direct Mapped

記憶體中我們將最小的單位稱為block或line，杰哥習慣用block稱呼。也就是說Cache從Memory抓資料都是以一個block為單位。不過因為Cache的容量比較小，所以要抓儲存資料的方式就很重要。

這邊介紹最簡單的方式，Direct Mapped。基本上就是用取餘數的方式決定要將Memory資料放在Cache的哪個位置，因為解釋有點麻煩，直接用例子來說明：


在這邊我們假設一個block是4bytes，並且這時CPU要求byte address為38的資料，這時候我們要先算出他在哪個block，透過floor function和除法可以得到是第九個block，那麼第九個block應該要放在Cache的哪個位置？

這邊就是direct mapped的重點了，我們只要直接的取9 mod 4的結果即可，結果的1就代表我們應該放在Cache的第一個block。

另一件要注意的事情是，不只有第九個block會對應到Cache的第一個block，還有1,5,13等等，所以我們還要另外標記這是哪個個Memory block，只要取9除以4的商即可，也就是放在tag欄位的2，如此一來我們就可以保證這格不會被誤會成是第五個Memory block之類的。

## Cache Memory圖解

因為Cache不可能只有4個block，這邊用1024(1K)大小的Cache Memory簡略說明剛剛的對照關係：


我們假設byte address有32bits。以下慢慢說明每個分區代表的意思。

* 對於一個block有4bytes來說，我們需要2bits指名要哪個byte。
* 對於1024的Cache Index，我們取後面10bits指名，也就是餘數的部份。
* Tag的話就是剩下的20bits。
* 另外我們需要一個Valid bit表示這格的內容是不是有效的，有時候資料可能被人取走，我們沒辦法保證資料正確，或是在程式第一次載入時，其中的資料可能是上次殘留的，所以也要將Valid bit設定為0表示無效資料。
* Cache中的Data就是我們要的資料，取出來的32bits會跟byte offset比對，確認要取哪段byte。

## 利用空間區域性

不過剛剛一個block只放4bytes的資料，也就是一個word的大小。這樣沒有用到空間區域性的特性，所以我們要試著增加一個block的大小，這樣子一次拿出來的空間就更大，就越有機會抓到等等可能用到的資料，通常對於陣列最有效果。

增加block大小就需要多幾個bit指名要哪個word，以下展示一個block有四個word的Cache Memory：


這時候除了原本有的東西以外，還要多一個Block offset，指名要block中的哪個word，其餘的部份都一樣，只有tag的部份被壓縮空間。

可以想成因為Block數目變少了，每個Index可能分配到的Memory Block變少了，所以tag的數量就便少了。

## What's Next?

除了提昇Block數量以減少我們還有其他技巧可以減少miss rate，這部份留到下個單元再來解釋。

就醬~ㄅㄅ。

| 上一篇 | 下一篇 |
|-|-|
|[在Hazard尋求解法是否搞錯了什麼](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/BkGKEG61F)|[Set Associative Cache](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/ryJNh_igY)