第三章 指令級并行 (Instruction-Level Parallelism, ILP)

3.1 基本概念

指令級并行（ILP） 是指單個處理器中，通過硬件或軟件技術，同時執行多條指令中不同操作的能力。其目標是提高指令吞吐率，減少程序執行時間。

核心思想：利用指令間的獨立性，通過流水線（Pipelining）、亂序執行（Out-of-Order Execution, OoOE）、超標量（Superscalar） 等技術，讓處理器在一個時鐘周期內發射和執行多條指令。

關鍵限制：
- 數據相關（真相關）：后續指令依賴于前面指令的結果。
- 名稱相關：包括反相關和輸出相關，可通過寄存器重命名解決。
- 控制相關：由分支指令引起的依賴。

3.2 指令流水線的深入與冒險

1. 流水線冒險 (Hazard)
- 結構冒險：硬件資源沖突。解決方法：資源重復（如哈佛架構分離指令/數據Cache，多端口寄存器文件）。
- 數據冒險：數據依賴導致無法獲得正確操作數。
- 寫后讀 (RAW)：真數據相關，必須等待?？赏ㄟ^旁路/轉發 (Forwarding/Bypassing) 技術緩解。

• 讀后寫 (WAR) 與 寫后寫 (WAW)：名稱相關，可通過亂序執行與寄存器重命名消除。

• 控制冒險：分支指令改變PC，導致預取的下游指令無效。

2. 提高流水線性能
- 增加流水線級數（加深流水線）：提高主頻，但增加冒險懲罰和復雜度。
- 提高流水線吞吐率：每個周期發射多條指令（超標量、超長指令字VLIW）。

3.3 動態調度與亂序執行

核心：記分牌算法 與 Tomasulo算法

Tomasulo算法（曲老師重點講解）是動態調度、實現亂序執行的核心算法，尤其適合處理寄存器數量有限和長延遲操作（如訪存、浮點運算）。

核心組件與流程：
1. 保留站 (Reservation Stations)：緩存已發射但未執行的指令及其操作數（或指向操作數的標簽）。
2. 公共數據總線 (CDB)：用于將執行完畢的結果廣播到所有需要該結果的保留站和寄存器文件。
3. 寄存器重命名：通過重排序緩沖 (ROB) 或保留站本身，將體系結構寄存器映射到物理寄存器或標簽，徹底消除WAR和WAW冒險。

執行階段：
- 發射 (Issue)：指令順序發射到空閑保留站，并監聽操作數是否就緒。
- 執行 (Execute)：當操作數全部就緒且功能單元空閑時開始執行（亂序）。
- 寫回 (Write Result)：通過CDB廣播結果。

3.4 分支預測

控制冒險是限制ILP的主要瓶頸之一，現代處理器采用分支預測來推測執行。

1. 靜態分支預測：編譯器主導。
- 策略：預測永遠不跳轉、永遠跳轉、根據跳轉方向預測等。

2. 動態分支預測：硬件在運行時根據歷史信息進行預測。
- 分支歷史表 (BHT)：用分支指令地址的低位索引一個表，表中記錄上一次該分支是否跳轉（1位預測器）。
- 兩位飽和計數器預測器：狀態機（00-不跳轉，11-跳轉），只有連續兩次預測錯誤才改變預測方向，抗干擾能力強。
- 相關（兩級）分支預測：利用其他分支的歷史結果來預測當前分支（如GShare, Tournament Predictor）。
- 分支目標緩沖 (BTB)：緩存預測跳轉的分支的目標地址，實現快速取指。

3.5 多發射處理器

1. 超標量 (Superscalar)
- 硬件在運行時動態檢查指令間的依賴性，每個周期可發射可變數量的指令（如2-8條）。
- 代表：現代x86、ARM高性能核心。
- 關鍵挑戰：依賴檢查邏輯復雜，隨著發射寬度增加，復雜度呈指數增長。

2. 超長指令字 (VLIW)
- 編譯器在編譯時靜態分析指令間的并行性，將多條可并行執行的操作打包成一條很長的指令（一個“包”）。
- 硬件簡單，但依賴于智能編譯器，且二進制代碼兼容性差。
- 代表：Intel Itanium (IA-64) 的EPIC架構。

3.6 性能限制與ILP的未來

限制ILP的因素：
- 真實的數據依賴（程序固有的）
- 過程（函數調用）和分支
- 指令發射、執行、提交的帶寬限制
- 存儲系統延遲（Cache Miss）

超越ILP的技術：當單線程ILP挖掘接近極限時，計算機體系結構轉向：
- 線程級并行 (TLP)：同時多線程 (SMT)、多核 (Chip Multiprocessor)。
- 數據級并行 (DLP)：SIMD指令擴展（如SSE, AVX, Neon）。
- 請求級并行 (RLP)：面向吞吐量計算，如GPU。

---
本章：指令級并行是現代高性能CPU設計的基石。從經典的5級流水線出發，通過動態調度（Tomasulo）、分支預測、多發射（超標量/VLIW）等一系列復雜技術，盡可能地挖掘程序中的指令間并行性。ILP的收益存在遞減效應，這推動了多核與異構計算時代的到來。