# Ch.5-1 Memory Hierarchy
###### tags: `Computer Organization`, `計算機組織`

## Memory Technology
電腦中的記憶體有很多種，最主要的是random access memory(RAM)
特性：不管存取的位址在哪裡，存取的時間都一樣。

還有其他儲存裝置，像是：
- magnetic disk用機械的方式讀寫
- SSD跟USB的用快閃磁碟flash disk
### SRAM, Static Random Access Memory
優點：非常快
缺點：很貴，單位面積儲存的bit數較少（density低）、耗電高
特性：
1. 用電晶體做成
2. 供電屬於static。穩定供電，定期消耗電量才導致耗電高
3. 記憶體位址不會分割。只要有位址，直接到記憶體中存取
4. 用在CPU中的cache
### DRAM, Dynamic Random Access Memory
優點：便宜、低耗電、單位面積可儲存的bit數多（density高）
缺點：慢
特性：
1. 用電容做成
2. 供電屬於dynamic。有個**refresh**的機制，會定期給記憶體充放電（因為是電容做的）
3. 會將記憶體分割成row/column address，所以要經過row access跟column access才能存取到實際要用的資料（因為要求高密度，所以用二維的方式組成）
4. 用在main memory
## DRAM
### Array Architecture
DRAM是二維的陣列結構，先存取位址的高位元得知row後，再存取低位元得知column

下面舉例


高位元的部分進行row decode
會從四個橫排中選出一個
每個row上又有4個bit
再用低位元進行column decode
從4個bit選出其中一個
因為總共有4*4=16個，可是最後只會選出一個
所以叫做16*1

:::info
$4M=2^{22}$
所以4M總共有22條線，可以分成高低位元各11bit
:::

由address中高位元的11bit=2048個row中，指定一個row
然後再從這個row包含的address低位元11bit形成的2048個column找出資料
總共有2048*2048=4M個，只會取出一個
所以是4M*1

### DDR SDRAM
現在用的DRAM通常是DDR（Double Data Rate）
像使用flip-flop時，只會選擇clock的正緣<font color=red>或</font>負緣其中之一來觸發
而double data rate就是正負緣"都"可以觸發
換句話說，就是**0→1跟1→0都可以傳遞/接收資料**
相當於單位時間內可以執行的量倍增，throughput就能上升

:::info
左邊是1980-2012年的DRAM容量跟價格演進的表格
右邊是縱軸為存取速度、橫軸為年份的DRAM演進圖
可以發現近年來，DRAM有容量上升，價格下降的趨勢
row的存取速度（紅色）在過去與column的存取速度（藍色）的比值差不多：$250/150=1.66667$
近年來，row的速度卻遠慢於column的速度了：$35/0=\infty$
:::
:::danger
所以開始研究**最佳化row跟column access的速度**問題！
:::
## SRAM
SRAM的一個bit要由6個電晶體組成，且每個電晶體的大小都有玄機
有的要比較小，有的大，有的適中，才可以組成一整個完整的SRAM。
### SRAM Cell

運作：有點像DRAM

把word line設為1後，左右兩個名為med的NMOS電晶體就會通電
能將中間電晶體所儲存的資料經由bit line流出
由於一個電晶體不小，又要6個電晶體才可以組成一個SRAM
所以SRAM才會體積大、單位面積儲存bit數少，density低
且因為供電屬於static，資料是鎖在電晶體中，要一直通電，維持電晶體運作保存資料
因此存取資料很快

### Compare with DRAM
因為DRAM要分成row access跟column access，所以比較慢
但是只要用一顆電容就可以做好，所以單位面積儲存bit數多
:::info
因此，需要大容量的時候選擇DRAM
需要速度時，選擇SRAM
:::
## Why Memory Hierarchy?
### Technology Trends

（logic可以直接視為SRAM）
從圖中發現，容量部分，SRAM、DRAM、硬碟的成長幅度相當
但是速度成長的幅度就出現差距

### Processor Memory Latency Gap

上面的線代表CPU的效能，下面代表DRAM的效能
可以發現CPU成長的幅度非常大，DRAM相較起來非常小
為了不想要發生處理器一直在等待記憶體的狀況
想要一個容量大、速度快、便宜的記憶體
於是Memory Hierarchy就誕生了

## Memory Hierarchy
:::danger
**KEY POINT**：
讓處理器盡可能的存取比較快的記憶體
少用的資料就放到比較大，但是比較慢的記憶體
:::
1. upper level：距離CPU近的地方，速度快、容量小
2. lower level：距離CPU較遠的地方，速度慢、容量大

memory hiecrchy做的是把不常用的資料放到lower level
如果處理器要用到lower level裡面的資料，就把它搬到upper level
使得處理器可以用比較快的速度存取到資料
- **Block**：要被移動的資料的最基本單位（每次要移動，就是移一個或多個block）
### Principle of Locality
**★**所謂的`90/10 rule`或`80/20法則`
一般的程式中，其實只有$10-20%$的code主宰整個程式$80-90%$的運作（如迴圈）
所以只要顧好那$10-20%$的優化，就可以收穫$80-90%$的成效
1. Temporal locality：如果有一個資料被存取到，他在不久後的將來有可能再次被存取－－令比較常用的資料放在離CPU近的地方
2. Spatial locality：如果有一個資料被存取到，附近的資料可能是接著要被存取的資料－－把連續的資料放到離CPU近的地方
### Levels of Memory Hierarchy

越上面如register越快、越小，越接近CPU，就是upper level
越下面如硬碟、磁碟，越慢、越大，離CPU越遠，就是lower level
常用資料就要讓他盡量留在高的地方，以提升系統效能

### Hierarchy Managed
講述不同層級的儲存單元要製造出memory hierarchy的管理單位
1. Registers <-> Memory
由compiler或是programmer做到
compiler是我們寫高階語言的時候，由compiler自行決定
programmer則是寫組語的時候，programmer判斷何時移動記憶體跟暫存器的資料
2. cache <-> memory
由硬體做到，就是所謂的cache controller
後面將會討論cache controller的設計
3. memory <-> disk
透過硬體跟作業系統或是programmer
硬體跟OS就是所謂的virtual memory虛擬記憶體，後面也會詳談
programmer則可以決定什麼東西要放在檔案中，透過<font color=blue>開檔、讀取的動作</font>就可以寫入記憶體
### Memory Hierarchy Terminology
一些名詞介紹
#### Performance of main memory
* Latency：影響快取記憶體存取時的miss penalty（cache中沒找到，就要改去memory找，花費的時間會變多）
1. access time：送出要求到實際拿到資料的時間
2. cycle time：連續兩筆資料要存取時，中間應相差的時間
* Bandwidth：一次可以搬移多少資料（視CPU跟memory之間的bus決定）

ps.硬碟、磁帶的存取方式又各有不同之處

* Hit：想在上層找資料，且真的找到的狀況
1. hit rate：發生hit的比例（上層就找到資料的比例）
2. hit time：找到資料後，將之從上層取出的時間（RAM access time + time to determine hit/miss）
* Miss：想在上層找資料，結果沒找到（資料在下層）
1. miss rate：發生miss的比例 = 1 - (hit rate)
2. miss penalty：從下層找出資料並塞入上層的時間（存取下層的時間 + 從下傳到上的傳輸時間）（注意上層的空間不夠放新來的東西的話，就要把原本的東西丟掉）
:::danger
因為Hit time << Miss penalty

所以要創造好的memory hierarchy能做得有：
1. 提高hit rate
2. 降低miss rate
3. 減少hit time的長度
:::
### 4 Questions for Hierarchy Design
四個關於設計hierarchy時要考量的問題
1. block placement：block要放在哪裡？
2. block identification：怎樣知道要找的block在不在上層&在哪裡？
3. block replacement：如果block不在上層，要從下層找到並移到上層，而上層空間不夠，如何選擇要把上層的什麼東西丟掉？
4. write strategy：如果資料被寫入／更新，應該做什麼動作？只要更新上層的資料就好，還是下層的也要?
### Summary
1. locality
* temporal locality是從「時間」的角度看
* spatial locality是從「空間」的角度看
2. DRAM因為密度高所以大且便宜，但是慢
3. SRAM因為密度低所以小而貴，可是很快
因為SRAM很貴，所以不會用來大量使用；然而DRAM又太慢，跟不上CPU的速度，於是出現memory hierarchy，透過locality的特性及運用，讓人有一種「記憶體又大又快又便宜」的錯覺。