Ch6 Instruction
==

###### tags:`計算機組織`
[toc]
## Principle of locality
Programs access a relatively small portion of their address space at any instant of time.
:face_with_finger_covering_closed_lips: 我們在某一個時間只會存取記憶體某一部分的位置。
### Temporal locality(locally in time)
if an item is referenced, it will tend to be referenced again soon.
:panda_face: 如果一個項目被存取到，那它很快會再被存取到
e.g
- loop
### Spatial locality(locally in space)
if an item is referenced, items whose address are close by will tend to be referenced soon.
:panda_face: 如果一個項目被存取到，那它附近位址的項目也會很快被存取到
e.g.
- code execution sequentially
- array
### simple structure of computer
因為有 locality 的特性，我們通常會把locality 高的放在比較上層的 memory。

### 練習
:question: Write a C program which exhibits the temporal and spatial localities. This program cannot exceed 5 lines.
:face_with_monocle: solution:

void clear(int array[], int size){
    int i;
    for(int i=0; i<size; i++){
        array[i] = 0;
    }
}

:question: 名詞解釋
- locality of reference : locality of reference 程式在執行時，有傾向訪問同一個或附近位址的記憶體位址
- spatial locality : 如果一個項目被訪問，它附近的記憶體位址也會很快被訪問
- temporal locality : 如果一個項目被訪問，它很快會再被訪問。

## Different memory technoloies
1. SRAM semiconductor memory: 存在 latch
- 邏輯閘很快
- 但需要六顆電晶體
- density 比較低
- volatile
2. DRAM semiconductor memory: 存在 capacitor
- capacitor 充放電會比較慢
- 比較 cheap
- density 比較高
- 因為沒有完美 capacitor 需要 refresh，功率消耗高
- volatile
3. Flash semiconductor memory
- non-volatile
- USB
4. Magnetic disk
- 易壞
- 磁化很慢
- non-volatile
5. Read only memory(ROM)
- 存儲 BIOS
### Conclusion
- SRAM : 速度快，較DRAM占空間
- DRAM : 資料需要 refresh，慢，體積小

### 練習
:question: DRAM 的特性

:face_with_monocle: solution
- is volatile
- is a capacitor
- is cheaper than cell of SRAM
- must be refresh regularly
- is smaller than cells in a SRAM

## 基本知識
- 傳輸的基本單位 : block or line
- 找到 : hit
- 沒找到 : miss
- 找到的比例 : hit rate = 1 - miss rate
- 沒找到的比例 : miss rate
- hit time : 找的時間(考試只有這項) + 傳回去的時間
- miss penalty : 從 memory 搬一個 block 到 cache + cache 傳回 CPU 的時間，考試來說是從 main memory 傳到上一層 cache 的時間

## memory hierarchy 基本架構
- 容量由最後一層決定
- 讀取速度由最靠近的那層 memory 決定

### 以 personal 的 Computer 來說
- SRAM : cache
- DRAM : (main) memory
- Hard Disk : Magnetic disk

### 練習

:question: Which of the following statements are generally true?
1. Caches take advantage of temporal locality.
2. On a read, the value returned depends on which blocksare in the cache.
3. Most of the cost of the memory hierarchy is at the highest level.
4. Most of the capacityof the memory hierarchy is at the lowest level.

:face_with_monocle: solution : 1、4

## 4 大 Problem For Memory Hierachy
### Question 1 : Where Can a Block Be Placed?
- Direct map
- 1 place be place = number of set
- number of block in cache = 1
- n-way set associative
- n place be set = block per set
- number of sets = number of block in cache / associative
- fully associative
- any place = number of block in cache
- number of sets = 1
- 增加 associative
- 優點 : 因為減少 conflict，associative 增加會降低 miss rate
- 缺點 :
- 成本增加 : tag 變多，比較器變多
- access time 或是 hit time 變長

### Question 2: How Is a Block Found?
- Direct map
- Location : index
- tag comparison = 1
- n-way set associative
- Location : index, search among elements
- tag comparison = degree of associative
- fully associative
- Location : 查詢所有的 cache entries / 查詢 page table
- tag comparison = size of cache / 0
- direct map cache
- access time 短
- 架構簡單
- 大部分的 cache 和 TLB 都是用 n-way set associative cache
- 在 virtual memory 的部分，一定會用 fully associative，因為 miss penalty is too expensive。

### Question 3: Which Block Should Be Replaced on a Cache Miss?
- Direct map : only one candidates
- n-way set associative : candidates 是, set 裡面的 block
- fully associative : 所有 block 都是 candidates
- 策略
- random
- 機制比較簡單
- 可能會出錯
- LRU
- 需要 maintain
- maintain 會導致 performance 的下降
- 關聯度高不會用 LRU，而是用 approximate LRU 或是 random
- virtual memory 的 replacement policy 是用 approximate LRU

### Question 4: What Happens on a Write?
- write through
- 實作簡單，實務上會需要 write buffer
- 存取 perfromance 差
- 發生 miss 的處理比較簡單
- write back : 反之
- write 一個 word 可以用 cache 的速度
- 寫入多個 word，之需要一次寫入下一層 memory
- 可以採用 high bandwidth transfer