計算機結構
Pipeline:
the continuous and somewhat overlapped movement of instruction to the processor or in the arithmetic steps taken by the processor to perform an instruction.
ex: Split Single-cycle Datapath into 5 Steps, overlap the steps
沒有pipeline: 四個人要洗衣服,步驟有洗衣服 30min、烘衣服 40min、摺衣服 20min,如果大家輪流做,並且全部做完才輪到下一個人.
洗衣機, 烘衣機都有很長的idle時間
pipeline:
MIPS
- stages:
- Pipelined Datapath:
可能發生該Stage已經做完但下一個Stage尚未執行完,需要在中間加入Pipeline Register來暫時存取前一個結果
該stage得到的結果可能在後面才用到, 加上control unit讓結果可以傳下去
Hazard:
- Data Hazard: 前, 後指令用到同個register, 前指令修改後, 還沒存回去, 後面指令拿到old data
ex: 如下圖, 5個指令用到r1, add修改後還儲存, sub, and, or拿到old data; xor拿到正確data
解法:
- Data Hazard:
SW:
1. NOP: insert no operation
2. 重排指令順序: 通常compiler負責
HW:
Forwarding: 直接把運算完的結果送到下一個指令要讀取的Register的地方
- Control Hazard:
Dynamic Branch Prediction: 用猜的, 猜錯再重跑
- ripes simulator CPU指令的模擬
Memory
Hierarchy
jersv cache教學
- Locality:
- temporal locality (locality in time)
e.g. loop
2. spatial locality (locality in space)
e.g. array, program
Hit/miss
- Hit: data appears in upper level
1. hit rate: fraction of memory access found in the upper level
hit upper level/total access
2. hit time: 判斷記憶體是否hit + 把上層資料搬到處理器的時間
- miss: data needs to be retrieved from a block in the lower level
1.miss rate: 1 — (hit rate)
2. miss penalty: time to replace a block in the upper level + time to deliver the block to the processor
Direct mapped cache:
CPU ask for 38 -> floor function 算出 9th block -> 9 % 4 = 1, 知道在cache的index 1 -> 可是1,5,9 %4 都=1, 需要tag分辨
還有valid bit 確保data有效
Set Associative Cache:
大量存取block 1,5,9時會一直發生miss, 增加cache的block entry改善
當一個entry有太多Block時,找Block時就要在進入entry時一個一個檢查tag是否正確, miss rate會降低,hit time會增加
- Replace: block entry full時, 要找一個entry替換
最常使用的是LRU(Least Recently Used),也就是要淘汰距離上次使用到的時間最久的Block
Multilevel Cache:
- GMR(Global Miss Rate):對於所有access的miss rate。
- LMR(Local Miss Rate):只看自己經歷access的miss rate。
假設發生了1000次的access,其中L1發生了50次miss,而這50次又在L2發生了20次miss,後面又在L3發生了5次miss,所以總的來說,這樣子的三層Cache miss rate為0.5%。