計算機結構

ref: 黃婷婷課程, 杰哥

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來暫時存取前一個結果

加上Pipeline register(藍色)

該stage得到的結果可能在後面才用到, 加上control unit讓結果可以傳下去

加上control unit(橘色)

Hazard:

• Data Hazard: 前, 後指令用到同個register, 前指令修改後, 還沒存回去, 後面指令拿到old data

ex: 如下圖, 5個指令用到r1, add修改後還儲存, sub, and, or拿到old data; xor拿到正確data

data hazard

解法:

• 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:

1. 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%。