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

3.1 基本概念

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

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

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

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

1. 流水線冒險 (Hazard)
- 結(jié)構(gòu)冒險：硬件資源沖突。解決方法：資源重復(fù)（如哈佛架構(gòu)分離指令/數(shù)據(jù)Cache，多端口寄存器文件）。
- 數(shù)據(jù)冒險：數(shù)據(jù)依賴導(dǎo)致無法獲得正確操作數(shù)。
- 寫后讀 (RAW)：真數(shù)據(jù)相關(guān)，必須等待。可通過旁路/轉(zhuǎn)發(fā) (Forwarding/Bypassing) 技術(shù)緩解。

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

• 控制冒險：分支指令改變PC，導(dǎo)致預(yù)取的下游指令無效。

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

3.3 動態(tài)調(diào)度與亂序執(zhí)行

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

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

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

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

3.4 分支預(yù)測

控制冒險是限制ILP的主要瓶頸之一，現(xiàn)代處理器采用分支預(yù)測來推測執(zhí)行。

1. 靜態(tài)分支預(yù)測：編譯器主導(dǎo)。
- 策略：預(yù)測永遠(yuǎn)不跳轉(zhuǎn)、永遠(yuǎn)跳轉(zhuǎn)、根據(jù)跳轉(zhuǎn)方向預(yù)測等。

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

3.5 多發(fā)射處理器

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

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

3.6 性能限制與ILP的未來

限制ILP的因素：
- 真實的數(shù)據(jù)依賴（程序固有的）
- 過程（函數(shù)調(diào)用）和分支
- 指令發(fā)射、執(zhí)行、提交的帶寬限制
- 存儲系統(tǒng)延遲（Cache Miss）

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

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