PIPE 管線實作與冒險 (Pipelined PIPE Implementation & Hazards)

Overview Table

4.5.1 SEQ+:重排計算階段 (p.457-458)

SEQ 在 clock cycle 結尾計算新 PC;SEQ+ 改成在 cycle 開頭由上一條指令留下的狀態(pIcode、pCnd、pValM、pValC、pValP)動態算出「當前指令」的 PC。這種改變狀態表示但不改邏輯行為的轉換稱為 circuit retiming,常用於平衡管線各階段的延遲。

 SEQ:                          SEQ+:
 ┌────┐                        ┌──────────────────────────┐
 │ PC │◄─ New PC(cycle 結尾算)  │ pIcode pCnd pValM pValC  │
 └────┘                        │ pValP(上一 cycle 存的訊號) │
   由本 cycle 的                └───────────┬──────────────┘
   icode/Cnd/valC/valM/valP 算       cycle 開頭 → 選出目前 PC

4.5.2-4.5.3 插入管線暫存器與訊號命名 (p.458-463)

在 SEQ+ 的階段間插入管線暫存器,得到初版 PIPE−(「−」表示效能還不到位)。管線暫存器(實際硬體元件):

訊號命名規則(理解 PIPE 的關鍵):

• 大寫前綴 D_, E_, M_, W_ = 管線「暫存器」中的欄位,如 M_stat。
• 小寫前綴 f_, d_, e_, m_, w_ = 該「階段」內組合邏輯剛算出的訊號,如 m_stat(memory 階段算出、含資料位址錯誤)。
• 寫回埠的位址來自 W_dstE / W_dstM(不是 decode 的 dstE/dstM)→ 原則:一條指令的所有資訊要留在同一個管線階段內,否則會把 A 指令的值寫到 B 指令指定的暫存器。

Select A 區塊:只有 call 在 memory 階段、jump 在 execute 階段需要 valP,且這些指令都不需要暫存器 A 埠的讀值,因此把 valP 與 A 埠讀值合併為單一訊號 valA 帶下去,減少管線暫存器狀態與接線(取代 SEQ 的「Data」區塊)。

4.5.4 Next PC 預測 (p.463-465)

目標:每個 clock cycle 發射(issue)一條新指令 → 吞吐量 1 instr/cycle。抓完指令就得立刻知道下一條位址,但:

• 條件分支:要到 execute 階段之後才知道跳不跳。
• ret:要到 memory 階段之後才知道返回位址。

策略(branch prediction,幾乎所有處理器都用某種形式):

• call / jmp(無條件):下一個 PC 必為 valC → 預測百分之百正確。
• 其他指令:必為 valP → 完全可靠。
• 條件 jXX:採 always taken,預測 PC = valC(成功率約 60%;never taken 約 40%;BTFNT(backward taken, forward not taken)約 65%,因為迴圈由向後分支收尾且會執行多次)。
• ret:返回位址可能是堆疊頂任何值,不預測,直接 stall 到 ret 通過 write-back。

fetch 階段兩個區塊:

      F 暫存器(predPC)──┐
  M_valA(誤預測分支的 valP)──┼──► Select PC ──► f_pc ──► instruction memory
  W_valM(ret 的返回位址) ──┘
  Predict PC:jXX/call → valC;其他 → valP → 存入 F.predPC

4.5.5 管線冒險 (Pipeline Hazards) (p.465-480)

相依 (dependency) 可能導致管線算錯時稱為冒險 (hazard):data hazard(前面指令的結果被後面指令當運算元)與 control hazard(前面指令決定後面指令的位置:jump/call/ret)。

Y86-64 各類狀態的冒險分析(p.471 Aside,系統化分析範例):

Data hazard 的產生(prog1–prog4)

decode 階段讀 register file,但結果要三個 cycle 後(通過 write-back)才寫回 → 前面 1~3 條指令寫入的暫存器若被當作來源,讀到的就是舊值。中間隔 ≥3 條無關指令(prog1)才安全;隔 2、1、0 條(prog2/3/4)各有 1~2 個運算元讀錯。

解法一:Stalling(停頓)

控制邏輯偵測到 execute/memory/write-back 中有指令將更新來源暫存器時,把 decode 的指令扣住(D 與 F 保持不變,PC 固定使下一指令重複被抓),同時對 execute 注入 bubble。Bubble = 動態產生的 nop:不改暫存器、記憶體、CC、狀態。prog2 停 1 cycle、prog4 停 3 cycle——正確但吞吐量大減(常見「寫後緊接著用」會停到 3 cycle)。

 prog4 (無 nop):
 irmovq $10,%rdx   F D E M W
 irmovq $3,%rax      F D E M W
   bubble                 E M W        ← 每 stall 一次
   bubble                   E M W        就對 E 注入一個 bubble
   bubble                     E M W
 addq %rdx,%rax        F D D D D E M W  ← decode 重複 3 次
 halt                    F F F F D E M W ← fetch 跟著重複

解法二:Forwarding(轉發/bypassing)

與其等寫回,不如把「即將寫入的值」直接從後段送回 decode 當運算元。5 個轉發來源 × 2 個目的地(valA、valB):

decode 的 Sel+Fwd A(兼併 valP)與 Fwd B 比較 d_srcA/d_srcB 與各目的暫存器 ID 決定是否轉發。用 e_valE 沒有時序問題:decode 只需在 cycle 結尾前備妥 valA/valB,ALU 輸出在那之前已有效。加上轉發後的完整設計即 PIPE。

Load/use hazard 與 load interlock

記憶體讀取發生在 memory 階段(太晚),mrmovq/popq 讀出的值無法轉發給緊接其後在 decode 的指令——那需要值「倒流時光」。解法:stall 1 cycle + forwarding 的組合,稱為 load interlock:

 mrmovq 0(%rdx),%rax   F D E M W
   bubble                    E M W
 addq %rbx,%rax          F D D E M W   ← decode 停 1 cycle,
                               ▲          cycle 8 由 m_valM 轉發 %rax

Load interlock + forwarding 足以處理所有 data hazard;只有 load interlock 會損失吞吐量。

Control hazard

只有 ret 與(誤預測的)jump 會發生:

• ret:stall 直到 ret 通過 memory/write-back,共注入 3 個 bubbles。實作上 fetch 無法注入 bubble——fetch 每個 cycle 一定會抓些什麼,於是連續 3 個 cycle 重複抓 ret 的下一條指令(預測 PC=valP),但每次都在 decode 被換成 bubble;ret 到 write-back 時,Select PC 改用 W_valM 抓返回點。
• 誤預測分支:jump 進入 execute 時由 e_Cnd 發現不該跳,此時已誤抓 2 條目標端指令,但它們尚未改變 programmer-visible state(最早要到 execute 才會改 CC)→ 下一個 cycle 對 decode 與 execute 注入 bubbles 取消它們(instruction squashing),同時由 M_valA(= 該 jump 的 valP)抓 fall-through 指令。代價:浪費 2 個 cycle。

 xorq %rax,%rax        F D E M W
 jne target (不跳)       F D E M W
 irmovq $2,%rdx (目標)     F D          ← cycle 4 發現誤預測
   bubble                      E M W     ← squash
 irmovq $3,%rbx (目標+1)     F
   bubble                    D E M W     ← squash
 irmovq $1,%rax (正確路徑)     F D E M W

4.5.6 例外處理 (Exception Handling) (p.480-483)

Y86-64 三種內部例外:(1) halt;(2) 非法 icode/ifun 組合(SINS);(3) 取指或資料讀寫存取非法位址(SADR)。目標:excepting instruction 之前的指令全部完成、之後的指令不得影響 programmer-visible state,處理器停機並設定狀態碼。

三個微妙之處與對策:

機制:每個管線暫存器都帶 stat 欄位,例外發生時只記在該指令的 stat 裡、照常流動;到 write-back 時控制邏輯才偵測並停機。因為指令依程式順序到達 write-back,最先發生例外的指令必最先到達 write-back——排序自動正確。

4.5.7 PIPE 各階段實作 (p.483-491)

多數區塊與 SEQ 相同,只是訊號加上前綴(如 SEQ 的 srcA → PIPE 的 d_srcA,輸入改用 D_icode、D_rA)。完整 HCL 見 Web Aside ARCH:HCL(p.508)。

PC 選擇與預測(fetch):

word f_pc = [
    M_icode == IJXX && !M_Cnd : M_valA;  # 誤預測分支 → 抓 fall-through
    W_icode == IRET : W_valM;            # ret 完成 → 返回位址
    1 : F_predPC;                        # 預設:預測值
];
word f_predPC = [
    f_icode in { IJXX, ICALL } : f_valC;
    1 : f_valP;
];

狀態計算拆成兩段:fetch 可偵測 imem_error、非法指令、halt(→ f_stat);非法資料位址須延到 memory 階段(→ m_stat)。

Decode 轉發邏輯與優先序(整個 PIPE 最關鍵的 HCL):

word d_valA = [
    D_icode in { ICALL, IJXX } : D_valP; # 合併 valP
    d_srcA == e_dstE : e_valE;   # 1. execute 轉發
    d_srcA == M_dstM : m_valM;   # 2. memory(valM 優先於 valE)
    d_srcA == M_dstE : M_valE;   # 3.
    d_srcA == W_dstM : W_valM;   # 4. write-back
    d_srcA == W_dstE : W_valE;   # 5.
    1 : d_rvalA;                 # 無轉發:用暫存器讀值
];

Write-back:整體狀態 Stat 由 W_stat 決定;W 中若是 bubble 屬正常運作:

word Stat = [ W_stat == SBUB : SAOK; 1 : W_stat; ];

Execute:與 SEQ 相同,另把 e_valE/e_dstE 送回 decode 作轉發來源;Set CC 增加輸入 m_stat 與 W_stat,後段有例外指令時抑制 CC 更新。

Memory:SEQ 的「Mem. data」區塊消失(valP/valA 的選擇已被 decode 的 Sel+Fwd A 取代);M、W 的多個值回送前段供轉發與管線控制使用。

4.5.8 管線控制邏輯 (p.491-500)

forwarding + 預測解決不了的 4 種特殊情況與偵測條件(Fig 4.64):

管線暫存器的低階機制:每個管線暫存器加 stall、bubble 兩個控制輸入(兩者同時為 1 視為錯誤):

 stall=0, bubble=0 → Normal:clock 上升載入輸入(state=y)
 stall=1, bubble=0 → Stall :維持原狀態(state=x)——扣住指令
 stall=0, bubble=1 → Bubble:重設為 nop 組態(state=nop)
   (D 的 reset:icode=INOP;E 的 reset:icode=INOP 且
    dstE/dstM/srcA/srcB = RNONE)

各情況的控制動作(Fig 4.66):

控制條件的組合(常見設計 bug:漏掉多條件同時成立):多數條件互斥(load/use 需 execute 是載入指令、誤預測需是 jump,不可能同時),只剩兩種組合:

• 組合 A:execute 是不跳的 jXX + decode 是 ret(ret 位於未採用分支的目標)。動作合併 = F: stall、D: bubble、E: bubble——照誤預測處理即可;F 雖 stall 但下個 cycle Select PC 會用 M_valA,F 內容無關緊要 → 自動正確。
• 組合 B:load/use hazard + ret(載入指令寫 %rsp、ret 要用它彈返回位址)。天真合併會讓 D 同時 bubble+stall(錯!)——正確做法:只採 load/use 的動作(F: stall、D: stall、E: bubble),ret 的處理延後一個 cycle。作者原始設計正是在此有 bug,通過大量模擬測試仍未被發現,靠系統化分析才揪出。

控制訊號 HCL(範例):

bool F_stall =
    E_icode in { IMRMOVQ, IPOPQ } && E_dstM in { d_srcA, d_srcB } ||
    IRET in { D_icode, E_icode, M_icode };

bool D_bubble =
    (E_icode == IJXX && !e_Cnd) ||       # 誤預測分支
    !(E_icode in { IMRMOVQ, IPOPQ } && E_dstM in { d_srcA, d_srcB }) &&
      IRET in { D_icode, E_icode, M_icode };   # ret 但排除組合 B

控制邏輯結構(Fig 4.68):輸入 W_stat, m_stat, M_icode, e_Cnd, E_dstM, E_icode, d_srcA, d_srcB, D_icode,輸出 F_stall, D_stall, D_bubble, E_bubble, M_bubble, W_stall, set_cc;其餘控制訊號恆為 0。

4.5.9 效能分析:CPI (p.500-504)

CPI(cycles per instruction) = 管線平均吞吐量的倒數(以 cycle 計)。觀察 execute 階段:處理 $C_i$ 條指令與 $C_b$ 個 bubbles,共約 $C_i+C_b$ 個 cycle:

bubble 數:load/use = 1、誤預測分支 = 2、ret = 3。每項 penalty = 指令頻率 × 條件頻率 × bubbles:

CPI = 1.27。改善方向應鎖定 mispredicted branch(佔 0.27 中的 0.16):條件分支常見、always-taken 常猜錯、每次取消 2 條指令。(若改用 BTFNT 65% 成功率:mp = 0.20×0.35×2 = 0.14,CPI = 1.25——Practice 4.43。)

4.5.10 未竟事項 (p.504-506)

• 多週期指令:整數乘除、浮點運算需 3~64 cycles。簡單做法:留在 execute 階段多個 cycle、前段 stall(效能差);較好做法:獨立的特殊功能單元(整數乘除單元、管線化的 FPU),decode 時 issue 給它,主管線繼續流動;仍用 stall/forwarding/管線控制同步。
• 記憶體系統介接:實際上一個 cycle 內完成存取靠 TLB + L1 caches(指令、資料各一)多數時間可行。Cache miss(3~20 cycles):純硬體處理,對管線控制多加 stall 條件、把指令扣在 fetch/memory 階段。Page fault(資料在磁碟,需數百萬 cycles):發出例外、由 OS handler 載入頁面後重新執行該指令——硬體與 OS 合作。

4.6 Summary (p.506-509)

• ISA 是抽象層:提供「一條指令執行完才開始下一條」的循序視圖;實作(SEQ → SEQ+ → PIPE− → PIPE)只需保證 programmer-visible 行為一致。
• 三個教訓:(1) 管理複雜度是首要之務(統一框架共享硬體單元);(2) 不必直接實作 ISA(管線化利用硬體平行);(3) 硬體設計者必須一絲不苟(晶片出廠即無法修補;系統化測試 + 分析看似無意義的組合)。
• 五階段管線是 1980 年代中期的先進水準(SPARC、MIPS、i486);現代 superscalar 處理器每 cycle 抓取/解碼/執行多條指令,CPI 可 < 1.0,故指標改用 IPC = 1/CPI;out-of-order execution 更以完全不同順序執行並保持循序 ISA 語意(見 05-Program-Optimization/02-Modern-Processor-Operation)。管線化簡單處理器仍主宰嵌入式市場(低成本、低功耗),many-core 主張以多個簡單核心換取總算力。
• 章末提供 SEQ/PIPE 模擬器(GUI 與文字版),控制邏輯由 HCL 轉譯成 C。

Exam/Test Patterns

Related Notes

• 04-Processor-Architecture/04-Pipelining-Principles
• 04-Processor-Architecture/03-Sequential-SEQ-Implementation
• 04-Processor-Architecture/01-Y86-64-ISA
• 04-Processor-Architecture/02-Logic-Design-and-HCL
• 05-Program-Optimization/02-Modern-Processor-Operation
• 08-Exceptional-Control-Flow/01-Exceptions
• 06-Memory-Hierarchy/03-Cache-Memories