管線化原理 (Pipelining Principles)

#csapp #processor-arch #pipelining #concept

Overview Table

主題	核心概念	關鍵數據/公式	書頁
SEQ 的問題	時脈必須慢到讓訊號在一個週期內走完全部 stage,硬體單元大部分時間閒置	ret:讀指令→讀 %rsp→ALU +8→讀記憶體,全部須在一週期完成	p.448
Computational pipeline	把運算切成多個 stage,以 pipeline register 分隔,多條指令同時在線	Throughput = $\frac{1 instr}{clock period}$	p.448-450
Throughput vs. Latency	管線化提高 throughput、但略增 latency	3-stage 例:8.33 vs 3.12 GIPS(×2.67);360 vs 320 ps(×1.12)	p.449-450
Pipeline 運作細節	rising clock edge 觸發 register 載入;clock 太慢無妨、太快會出錯	週期 = 最慢 stage 延遲 + register 延遲	p.450-452
限制一:不均勻切割	時脈受最慢 stage 限制,快的 stage 閒置	50/150/100 ps → 週期 170 ps,5.88 GIPS	p.452-453
限制二:深管線報酬遞減	register 延遲成為固定 overhead,無法無限加速	6-stage:14.29 GIPS,僅 ×1.71;極限 $1 / 20 ps = 50$ GIPS	p.454-455
限制三:feedback 相依	指令間有 data / control dependency;天真管線化會改變系統行為	I1 結果原本餵給 I2,管線化後變成餵給 I4	p.455-457
銜接 4.5:SEQ+	把 PC 計算移到週期開頭,作為管線化的過渡設計	新增 pIcode、pCnd、pValM、pValC、pValP 狀態暫存器	p.457

為什麼需要管線化:SEQ 太慢 (p.448)

SEQ 唯一(但致命)的問題是時脈必須夠慢,讓訊號在單一週期內傳遍所有 stage。以 ret 為例:從更新後的 PC 開始,必須依序完成——讀 instruction memory → 從 register file 讀 stack pointer → ALU 將 %rsp 加 8 → 從 memory 讀 return address 決定下一個 PC——全部擠在一個 clock cycle 內。

硬體使用率極差:每個單元在整個週期中只有一小段時間是 active 的。
解法:pipelining(管線化)——把任務切成一系列離散 stage,允許多個「顧客」(指令)同時在系統內前進。
生活類比 (p.448):自助餐檯(沙拉→主菜→甜點→飲料)、自動洗車(噴水→刷洗→打蠟→烘乾)。前車移到刷洗段,新車即可進入噴水段;所有車必須同速前進以免追撞。

核心 trade-off:pipelining 提高 throughput(單位時間服務的顧客數),但可能略增 latency(單一顧客的服務時間)。只想拿甜點的顧客在非管線系統可直奔甜點區,在管線系統則必須照序通過所有 stage。

4.4.1 Computational Pipelines (p.448-450)

在計算管線中,「顧客」是指令 (instructions),stage 執行指令的一部分。基本硬體單元是「combinational logic + clocked register」:組合邏輯經過一段 gate delay 後輸出成為輸入的函數,clock 訊號控制 register 定期載入結果(例:CD 播放器的解碼器)。延遲以 picosecond (ps, $10^{- 12}$ s) 計。

Unpipelined(未管線化)系統 (Figure 4.32):

        300 ps            20 ps
  +---------------+    +-----+
--| Combinational |----| Reg |--   Delay      = 320 ps
  |     logic     |    |     |     Throughput ~ 3.12 GIPS
  +---------------+    +--+--+
                        Clock
  Pipeline diagram:
  I1  ##########
  I2            ##########
  I3                      ##########
      ------------ Time ---------->   (指令不重疊,一次一條)

Throughput = \frac{1 instruction}{(20 + 300) ps} \cdot \frac{1,000 ps}{1 ns} \approx 3.12 GIPS

GIPS = giga-instructions per second(每秒十億條指令)。
Latency(延遲)= 執行單一指令從頭到尾的總時間 = 320 ps;未管線化時 latency 是 throughput 的倒數。
Pipeline diagram:時間由左至右,指令由上至下,實心方塊表示執行期間;方塊不垂直重疊代表無平行。

Three-stage pipeline (Figure 4.33):把 300 ps 邏輯切成 A、B、C 三段各 100 ps,段間插入 pipeline register(每個 20 ps):

   100ps    20ps    100ps    20ps    100ps    20ps
  +-----+  +----+  +-----+  +----+  +-----+  +----+
--|  A  |--|Reg |--|  B  |--|Reg |--|  C  |--|Reg |--
  +-----+  +-+--+  +-----+  +-+--+  +-----+  +-+--+
             +------------+--+------------------+
                        Clock       Delay = 360 ps, Throughput = 8.33 GIPS
  I1   A  B  C
  I2      A  B  C          <- I1 離開 A,I2 立即進入 A
  I3         A  B  C       <- 第 3 週期起穩態:每週期完成一條、進入一條

時脈週期 = $100 + 20 = 120$ ps → throughput ≈ 8.33 GIPS。
Latency = $3 \times 120 = 360$ ps(單一指令需 3 個完整週期)。
穩態 (steady state):三個 stage 全部 active,每個 clock cycle 有一條指令離開、一條進入(第 3 週期時 I1 在 C、I2 在 B、I3 在 A)。
效益:throughput 提升 $8.33 / 3.12 = 2.67$ 倍;代價:額外硬體 + latency 增為 $360 / 320 = 1.12$ 倍(增加的 latency 來自 pipeline register 的時間 overhead)。

4.4.2 管線運作細節 (A Detailed Look at Pipeline Operation) (p.450-452)

指令在 stage 之間的轉移由 clock 訊號的 rising edge(上升緣) 控制:每 120 ps clock 從 0 升到 1,啟動下一輪 stage 運算。以 240–360 ps 這一個週期為例 (Figure 4.35),四個關鍵時點:

時點 1 (t=239, clock 升起前):
  I2 在 stage A 算完的值已抵達第一個 pipeline register 的「輸入端」,
  但 register 的狀態與輸出仍是 I1 先前在 A 算出的值;
  I1 在 B 的結果同樣停在第二個 register 的輸入端。

時點 2 (t=241, clock 升起後):
  輸入被載入 register,成為新的輸出;stage A 的輸入同時
  被設定為 I3,開始其計算。

時點 3 (t=300, 傳播中):
  訊號在各 stage 的組合邏輯中傳播;不同區段的傳播速度可以不同
  (書中以彎曲的 wave front 表示)。

時點 4 (t=359, 下次 clock 升起前):
  各結果值已抵達 pipeline register 輸入端;t=360 clock 再升起,
  每條指令都前進一個 stage。

Clock 速度的不對稱性:放慢 clock 不會改變管線行為——訊號早已傳到 register 輸入端,register 狀態要等 clock 上升才改變。但 clock 太快會出災難性錯誤:訊號來不及傳過組合邏輯,clock 上升時 register 輸入端的值尚未有效 (not yet valid)。

與 SEQ 的時序原理相同(見 04-Processor-Architecture/03-Sequential-SEQ-Implementation §4.3.3):在組合邏輯區塊之間放置 clocked registers 這個簡單機制,就足以控制指令在管線中的流動;clock 反覆升降,各指令互不干擾地流過各 stage。

4.4.3 管線化的限制 (Limitations of Pipelining) (p.452-455)

Figure 4.33 是理想情況:運算恰好切成三個獨立且等長的 stage,每段是原邏輯的三分之一時間。實務上有多種因素削弱管線化的效益。

限制一:Nonuniform Partitioning(切割不均勻)(p.452-453)

若三段延遲為 50 / 150 / 100 ps(總和仍是 300 ps),時脈週期受最慢 stage 限制:

   50ps 20ps    150ps  20ps    100ps 20ps
  +----+ +---+ +-----+ +---+ +-----+ +---+
--| A  |-|Reg|-|  B  |-|Reg|-|  C  |-|Reg|--  週期 = 150+20 = 170 ps
  +----+ +---+ +-----+ +---+ +-----+ +---+
  I1 A... B    C..
  I2      A... B    C..      . = 閒置 (idle):A 每週期閒 100 ps,
  I3           A... B   C..      C 每週期閒 50 ps,只有 B 全程忙碌

指標	理想均勻 (100×3)	不均勻 (50/150/100)
時脈週期	120 ps	170 ps(= 最慢 stage 150 + register 20)
Throughput	8.33 GIPS	5.88 GIPS
Latency	360 ps	510 ps(3 × 170)

例外/實務限制:把運算切成延遲均勻的 stage 是硬體設計的重大挑戰——ALU、記憶體等單元往往無法再細分成延遲更短的小單元,因此很難做出平衡的 stage。書中設計 pipelined Y86-64 時不深究此細節,但實際系統設計中 timing 最佳化至關重要。

限制二:Diminishing Returns of Deep Pipelining(深管線的報酬遞減)(p.454)

把運算切成 6 段各 50 ps(Figure 4.37):最小週期 = $50 + 20 = 70$ ps → throughput = 14.29 GIPS。

Stage 數加倍(3→6)、每段邏輯時間減半,throughput 卻只提升 $14.29 / 8.33 = 1.71$ 倍——因為 pipeline register 的延遲是固定 overhead,不隨切割縮小。
在 6-stage 設計中,register 延遲占整個週期的 $20 / 70 = 28.6 %$ 。
現代處理器採用很深的管線(15 stage 以上) 以最大化時脈:架構師把指令執行切成大量極簡步驟、電路設計師刻意壓低 pipeline register 延遲、晶片設計師精心設計 clock distribution network 確保全晶片時脈同步變化。

一般化(Practice Problem 4.29 的結論):把 300 ps 邏輯切成 $k$ 段(每段 $300 / k$ ps、register 20 ps):

Latency $= k \cdot (300 / k + 20) = 300 + 20 k$ ps(隨 k 線性上升)
Throughput $= \frac{1000}{300 / k + 20} = \frac{1000 k}{300 + 20 k}$ GIPS
$k \to \infty$ 時的極限:Throughput $\to 1000 / 20 = 50 GIPS$ ——上限完全由 register 延遲決定。

限制三:相依性(見 4.4.4)

4.4.4 具有回饋的系統管線化 (Pipelining a System with Feedback) (p.455-457)

前面假設管線中的物件(車、人、指令)彼此完全獨立。但執行 x86-64 / Y86-64 機器程式的系統,連續指令間存在相依性:

(1) Data dependency(資料相依)——後一條指令要讀前一條寫入的暫存器:

1  irmovq $50, %rax      --+ 寫 %rax
2  addq   %rax, %rbx     <-+ 讀 %rax,寫 %rbx --+
3  mrmovq 100(%rbx), %rdx                     <-+ 讀 %rbx

(2) Control dependency(控制相依)——條件分支的結果決定下一條要執行哪條指令:

1  loop:
2      subq %rdx,%rbx
3      jne targ          <- 條件成立跳 targ (halt);不成立續行 irmovq
4      irmovq $10,%rdx
5      jmp loop
6  targ:
7      halt

在 SEQ 中,這些相依由 feedback path 處理(Figure 4.22 右側):把更新後的 register 值送回 register file、新 PC 值送回 PC register。

天真管線化會破壞行為 (Figure 4.38):

(a) Unpipelined + feedback        (c) 3-stage pipeline + feedback(錯誤)
   +-------------+                   +---+ +-+  +---+ +-+  +---+ +-+
 +>| Comb. logic |->[Reg]--+->     +>| A |-|R|--| B |-|R|--| C |-|R|-+->
 | +-------------+         |       | +---+ +-+  +---+ +-+  +---+ +-+ |
 +-------------------------+       +---------------------------------+
 (b) I1 的結果 -> I2 的輸入        (d) I1 的結果繞回時,進入的已是 I4:
     I1 -> I2 -> I3 逐條相依            I1 的結果變成 I4 的輸入!

原系統:每條指令的結果回饋給下一條指令(I1→I2→I3)。
直接插入 pipeline register 後:I1 的結果要三個週期才繞回輸入端,此時進入管線的是 I4——為了加速卻改變了系統的計算行為,這是不可接受的。

設計 pipelined Y86-64 的核心約束:必須妥善處理指令間的 data 與 control dependency,使最終行為與 ISA 定義的模型一致。具體解法(stalling、forwarding、branch prediction 等 hazard 處理)見 04-Processor-Architecture/05-Pipelined-PIPE-Implementation-and-Hazards。

銜接 4.5:SEQ+ 與 PC 計算的搬移 (p.457)

4.5 開頭(本頁範圍內)提出通往管線化的過渡設計 SEQ+:

將 SEQ 的 PC update stage 移到 clock cycle 的開頭(而非結尾)——改為計算「當前指令的 PC」。此改動對整體硬體結構影響極小,但更契合管線各 stage 的活動順序。
作法:新增狀態暫存器保存前一指令算出的訊號(pIcode、pCnd、pValM、pValC、pValP);新週期開始時,這些值流過與原本完全相同的邏輯,算出「現在這條指令」的 PC。
對比:SEQ 在週期結尾用本週期算出的 icode/Cnd/valC/valM/valP 計算「新 PC」存入 PC register;SEQ+ 在週期開頭用上一週期存下的 p 開頭訊號「選出」目前 PC。
完整的 PIPE 設計與 hazard 處理見 04-Processor-Architecture/05-Pipelined-PIPE-Implementation-and-Hazards。

Exam/Test Patterns

情境 / 關鍵字	答案
給各 stage 延遲 + register 延遲,求時脈週期	週期 = max(stage 延遲) + register 延遲;throughput = 1/週期
求 pipelined latency	latency = stage 數 × 時脈週期(含每段的 register 延遲)
未管線化系統的 latency 與 throughput 關係	latency = 1/throughput(互為倒數);管線化後此關係不成立
週期以 ps 給定,求 GIPS	throughput(GIPS)= 1000 ÷ 週期(ps)
「clock 放慢會怎樣?」	行為不變(register 等 clock 上升才載入);「clock 太快?」→ register 輸入尚未有效,結果錯誤
不均勻 stage(如 50/150/100 ps)為何變慢	週期被最慢 stage 綁死;快的 stage 每週期閒置(idle)
P4.28:六塊 80/30/60/50/70/10 ps 切 2 段求最大 throughput	在 C、D 之間插 register:170/130 → 週期 190 ps,≈5.26 GIPS,latency 380 ps
P4.28:切 3 段	AB \| CD \| EF = 110/110/80 → 週期 130 ps,≈7.69 GIPS,latency 390 ps
P4.28:切 4 段	A \| BC \| D \| EF = 80/90/50/80 → 週期 110 ps,≈9.09 GIPS,latency 440 ps
P4.28:最少 stage 數達最大 throughput	受最大不可分割塊 A = 80 ps 限制 → 週期 100 ps;5 段 A\|B\|C\|D\|EF → 10 GIPS,latency 500 ps
P4.29:切 k 段的 latency / throughput / 極限	latency = $300 + 20 k$ ps;throughput = $\frac{1000 k}{300 + 20 k}$ GIPS; $k \to \infty$ 極限 50 GIPS(= 1 / register 延遲)
「加深管線為何無法無限加速?」	pipeline register 延遲是固定 overhead;6-stage 例中占週期 28.6%
「pipelining 改變了程式行為」的情境	系統含 feedback path(data/control dependency),直接插 register 使 I1 的結果餵給 I4 而非 I2
指出指令序列中的相依類型	寫後讀同一暫存器 → data dependency;條件跳轉決定下一條指令 → control dependency
SEQ+ 與 SEQ 的差異	PC 計算移到週期開頭、計算「當前」PC;靠 pIcode/pCnd/pValM/pValC/pValP 狀態暫存器保存上一指令的訊號

04-Processor-Architecture/03-Sequential-SEQ-Implementation — SEQ 的五 stage 與時序原理,是本節管線化的出發點
04-Processor-Architecture/05-Pipelined-PIPE-Implementation-and-Hazards — SEQ+ → PIPE,data/control hazard 的實際解法
04-Processor-Architecture/01-Y86-64-ISA — 指令集定義了管線化必須保持的行為模型
04-Processor-Architecture/02-Logic-Design-and-HCL — combinational logic 與 clocked register 的硬體基礎
05-Program-Optimization/02-Modern-Processor-Operation — 真實處理器的深管線與超純量執行
01-Computer-Systems-Tour/04-Amdahls-Law-and-Concurrency-Themes — throughput/latency 與整體加速的權衡觀點

Overview Table

為什麼需要管線化:SEQ 太慢 (p.448)

4.4.1 Computational Pipelines (p.448-450)

4.4.2 管線運作細節 (A Detailed Look at Pipeline Operation) (p.450-452)

4.4.3 管線化的限制 (Limitations of Pipelining) (p.452-455)

限制一:Nonuniform Partitioning(切割不均勻)(p.452-453)

限制二:Diminishing Returns of Deep Pipelining(深管線的報酬遞減)(p.454)

限制三:相依性(見 4.4.4)

4.4.4 具有回饋的系統管線化 (Pipelining a System with Feedback) (p.455-457)

銜接 4.5:SEQ+ 與 PC 計算的搬移 (p.457)

Exam/Test Patterns

Related Notes