# Mem Exploiting Memory Hierarchy
[TOC]
## 5.0 Out Line
<font color="#f00"></font>
- What are the challenges of building big, fast memory systems?
- What is a cache?
- Why caches work?
- How are caches organized?
- Where do we put things -and- how do we find them?
## 5.1 Direct Mapped Cache

### Large storage memory hierache

- SRAM
- Static RAM
- DRAM
- Dynamic RAM
- Disk
- Non-volatile 非揮發
- Flash Storage
- NOR flash: NOR gate
- NAND flash
- DRAM(Dynamic Random Access Memory)
- rectangular array
- Burst mode: faster
- Double data rate(DDR)
- Quad data rate(QDR)
-
### 基本Cache存取相關名詞

- Block : unit of copying , may be multiple words
- Hit : access satisfied by upper level
- data in block b is in cache
- Miss : block copied from lower level
- data in block b is not in cache go to mem take
- Hit ratio : **hits/accesses**
- Miss ratio : misses/accesses = **1 – hit ratio**
-
### ie
- consider
- cache hit time of 1 cycle
- Miss penalty 1000 cycle
- AVG acess time:
- 97 hit: 1cycle +.03 * 100 cycle =4
- 99 hit: 1cycle +.01 * 100 cycle=2

### 使用cache有效增加效率的原因(Locality)

###### Locality
因為program 很常會使用的 `data` and `指令`所以我們會把他的`addr` 放在鄰近的擺在附近
**==must use in time or in space usually==**
- Temporal locality：
- recently use data or instraction 

- instructions in a <font color="#f00">loop</font>, induction variables
- 

- Spatial locality：
- nearby addr 

- sequential <font color="#f00">instruction access</font>, array data
- from locations
i + 1, i + 2 or i + 3
- 
if in data:(class)
- 

- Direct mapped：
- 只有==hash==和定址而得到的一個項，沒有搜尋
- 

### Address的內容
- <font color="#f00">[tag]-[index]-[byte offset]</font>

- tag : 記錄現在在cache block中的是memory的哪一個block
- index : 用來對每一個block定址(global)
- offset : 用來對每一個byte/word定址(local)
### Cache Memory的內容

- <font color="#f00">[Index]-[Valid bit]-[Tag]-[Data]</font>

- Valid bit : 1 = present, 0 = not present

###### Direct mapped example:

- 若cache要存放的資料量為16Kbyte, address為32 bits, 每一個block大小為4 words, 則Cache大小為多少?
1. 首先求Entry數目，Entry數目=1k=2^10，因此 index=10
2. 再求block內的word數目，4=2²，因此 word offset=2
3. 再求word內的byte數目，很明顯是，4=2²，因此 byte offset=2
4. 最後求tag，為 *address−(index+offset)*
*tag=32–10(index)−2(word offset)−2(byte offset)*
- 最終得Cache大小為
*2^10×(1(valid)+18(tag)+4×32(blocksize))≒147000bits*
2^10(19*128)=1024*(147)
- 當題目有提到word的字眼 就用block offset，沒有的話，就只用byte offset即可
1. entry數 => Index bit
2. Block的word數 => block offset
3. N-bit Address => byte offset
###### example:

## 5.2 Cache Miss
### Block size issue
- 當block Size越來越大，會降低 miss rate，因為==spatial locality==。
- block越大miss penalty越嚴重，因為要搬更多東西。
- 在固定的cache size下，太大的block Size :
1. 會使block數目變少而miss rate上升
2. 會讓沒有物盡其用的情況變嚴重，白白複製一堆東西到cache

### Data Write issue
- <font color="#f00">write-through:</font> 同時更改cache和memory的的資料，效能差但可用write buffer使CPU繼續執行來改善，當發生write miss時，有兩種處理方式。
1. write around : 不存取cache直接去寫main memory
2. allocate on miss : 存取cache一起改
- <font color="#f00">write-back :</font>先寫到cache並註記為dirty，當dirty block整個被替換時才寫回memory
### Cache Performance：
Average memory access time (AMAT) ,<font color="#f00"> AMAT = Hit time + Miss rate × Miss penalty </font>

## 5.3 Cache Miss improvement
<font color="#f00"></font>
- <font color="#f00">Associative Cache：</font>增加空間使用的彈性，引入search的概念 (原本只有map和hash) ，使miss rate降低，硬體可平行做search。
- <font color="#f00">direct mapped :</font> hash 的概念 (block 位址直接mod n)
- <font color="#f00">2-way set associative : </font> 半hash、半search
- <font color="#f00">fully associative :</font> 全search
- 在vm的時候都是用full assoc (因為不用搜尋所有的存儲空間)

- 因為關係到search的查找模式，所以有replacement policy
- Least-recently used (LRU)
- Random

- When the CPU tries to read from memory, the address will be sent to a cache controller.

- multi-level caches
1. 第一層 cache：希望將 hit time 減到最小
2. 第二層 cache：希望將miss rate減到最小避免查找主記憶體，Hit time 影響較小
- 實務上的結果
- L-1 cache 大小< single cache 大小
- L-1 block 大小 < L-2 block 大小
###### example：考慮一個兩層架構的cache
Access time = 5 ns，
Main memory access time = 100ns
Clock cycle = 1/4GHz = 0.25ns

(算次數) Global miss rate to main memory = 0.5 %
Miss rate/instruction = 2% (算出現機率)

CPI = 1 + 0.02 × 20 + 0.005 × 400 = 3.4
- memory hierarchy interaction with software
- Radix Sort 複雜度較小，花的instruction少
- Radix Sort 要用bocket額外暫存，miss rate 較高
- 所以，總和起來還是quick sort快