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

一、 基本概念
1. 指令級(jí)并行 (ILP)：指在單個(gè)處理器內(nèi)，通過硬件或軟件技術(shù)，使得多條指令在執(zhí)行階段可以重疊進(jìn)行，從而提高程序執(zhí)行速度。其核心思想是挖掘和利用程序中指令之間潛在的并行性。
2. 關(guān)鍵度量：
* 并行度：平均每個(gè)時(shí)鐘周期可以執(zhí)行的指令數(shù)。

• 主要目標(biāo)：使 CPI (Clock Cycles Per Instruction) 盡可能接近1甚至小于1。

1. 限制ILP的因素：

• 數(shù)據(jù)相關(guān) (Data Hazard)：真數(shù)據(jù)相關(guān)（寫后讀，RAW）限制了指令的執(zhí)行順序。

• 名字相關(guān) (Name Hazard)：反相關(guān)（寫后寫，WAW）和輸出相關(guān)（讀后寫，WAR），可通過寄存器重命名解決。

• 控制相關(guān) (Control Hazard)：由分支指令引起，影響指令的取指順序。

• 結(jié)構(gòu)沖突 (Structural Hazard)：硬件資源沖突。

二、 基于硬件的動(dòng)態(tài)調(diào)度技術(shù)

1. 記分板算法 (Scoreboarding)

• 目標(biāo)：在保持?jǐn)?shù)據(jù)流和異常行為的前提下，允許指令亂序執(zhí)行（Out-of-Order Execution）。

• 核心思想：中央控制器（記分板）跟蹤所有指令的狀態(tài)、數(shù)據(jù)相關(guān)性和資源使用情況。指令在譯碼后進(jìn)入記分板，當(dāng)操作數(shù)就緒且功能單元可用時(shí)，記分板才發(fā)射該指令執(zhí)行。

• 執(zhí)行階段：分為4段：

1. 發(fā)射 (Issue)：檢查結(jié)構(gòu)沖突與WAW相關(guān)。

1. 讀操作數(shù) (Read Operands)：等待數(shù)據(jù)相關(guān)消除（即源操作數(shù)就緒）。

1. 執(zhí)行 (Execution)：在功能單元中計(jì)算。

1. 寫回 (Write Back)：結(jié)果寫回寄存器。

• 缺點(diǎn)：檢測(cè)和解決所有相關(guān)，硬件復(fù)雜；無法處理WAR和WAW相關(guān)（通過停頓解決，影響效率）。

1. Tomasulo算法

• 核心改進(jìn)：

• 分布式控制：通過保留站（Reservation Station）進(jìn)行指令調(diào)度，而非中央記分板。

• 寄存器重命名：使用保留站和公共數(shù)據(jù)總線（CDB）實(shí)現(xiàn)，徹底消除WAR和WAW相關(guān)。

• 前瞻執(zhí)行：為處理控制相關(guān)（分支）奠定基礎(chǔ)。

• 主要部件與流程：

• 保留站：緩存已發(fā)射但未執(zhí)行的指令及其操作數(shù)（或指向操作數(shù)的指針）。

• 公共數(shù)據(jù)總線：廣播結(jié)果，實(shí)現(xiàn)數(shù)據(jù)前遞（Forwarding）。

• 流程：發(fā)射 -> 執(zhí)行 -> 寫回。在“發(fā)射”階段，若操作數(shù)未就緒，則從寄存器或CDB獲取“標(biāo)簽”，實(shí)現(xiàn)寄存器重命名。

• 優(yōu)勢(shì)：能高效處理數(shù)據(jù)相關(guān)，支持亂序執(zhí)行，為后續(xù)的分支預(yù)測(cè)和推測(cè)執(zhí)行提供了硬件基礎(chǔ)。

三、 基于硬件的分支預(yù)測(cè)與推測(cè)執(zhí)行

1. 分支預(yù)測(cè) (Branch Prediction)

• 動(dòng)機(jī)：減少控制相關(guān)帶來的流水線停頓。

• 靜態(tài)分支預(yù)測(cè)：編譯時(shí)確定，如“總是預(yù)測(cè)不跳轉(zhuǎn)”、“向后跳轉(zhuǎn)預(yù)測(cè)跳轉(zhuǎn)”等。簡(jiǎn)單但準(zhǔn)確率有限。

• 動(dòng)態(tài)分支預(yù)測(cè)：運(yùn)行時(shí)根據(jù)歷史信息進(jìn)行預(yù)測(cè)。

• 分支歷史表 (BHT)：使用分支指令地址的低位索引一個(gè)表，表中記錄上次執(zhí)行的結(jié)果（跳轉(zhuǎn)/不跳轉(zhuǎn)）。

• 兩位飽和計(jì)數(shù)器：提高預(yù)測(cè)準(zhǔn)確性，需兩次預(yù)測(cè)錯(cuò)誤才會(huì)改變預(yù)測(cè)方向，具有良好的穩(wěn)定性。

• 分支目標(biāo)緩沖器 (BTB)：緩存預(yù)測(cè)跳轉(zhuǎn)的分支指令的目標(biāo)地址，可在取指階段直接提供目標(biāo)指令地址。

• 相關(guān)分支預(yù)測(cè)器 (如兩位局部/全局歷史預(yù)測(cè)器)：利用分支之間的相關(guān)性（模式）進(jìn)行更精確的預(yù)測(cè)。

1. 推測(cè)執(zhí)行 (Speculative Execution)

• 概念：基于分支預(yù)測(cè)的結(jié)果，在分支指令結(jié)果確定之前，提前執(zhí)行預(yù)測(cè)路徑上的指令。

• 硬件支持（結(jié)合Tomasulo算法）：

• 重排序緩沖器 (ROB)：核心組件。按程序順序緩存所有推測(cè)執(zhí)行的指令及其結(jié)果。

• 流程：指令按序發(fā)射到ROB和保留站，亂序執(zhí)行，但結(jié)果先寫入ROB，并不立即更新寄存器。只有當(dāng)指令在ROB中變?yōu)樽钆f的、且非推測(cè)狀態(tài)時(shí)，才按序提交結(jié)果到寄存器或內(nèi)存。

• 異常處理：在推測(cè)執(zhí)行期間發(fā)生的異常被記錄在ROB中，只有在該指令提交時(shí)才真正處理，保證了異常行為的精確性。

• 錯(cuò)誤預(yù)測(cè)恢復(fù)：當(dāng)分支預(yù)測(cè)錯(cuò)誤時(shí)，清空該分支之后的所有推測(cè)執(zhí)行指令（清空ROB和保留站相關(guān)項(xiàng)），并從正確路徑重新取指。

四、 基于軟件的靜態(tài)調(diào)度技術(shù)（由編譯器完成）

1. 循環(huán)展開 (Loop Unrolling)

• 將循環(huán)體復(fù)制多次，減少循環(huán)控制指令（如分支、自增）的開銷，為編譯器調(diào)度創(chuàng)造更多指令，以填充延遲槽。

• 需注意寄存器壓力增加和代碼膨脹問題。

1. 指令調(diào)度 (Instruction Scheduling)

• 編譯器通過調(diào)整指令順序，盡可能分離存在數(shù)據(jù)相關(guān)的指令，以填充因數(shù)據(jù)相關(guān)或功能單元延遲導(dǎo)致的流水線氣泡。

• 常用方法：靜態(tài)調(diào)度、軟流水線 (Software Pipelining) 等。

1. 靜態(tài)多發(fā)射處理器與VLIW

• 靜態(tài)多發(fā)射：處理器每個(gè)時(shí)鐘周期發(fā)射固定數(shù)量的指令包，依賴編譯器在編譯時(shí)挖掘ILP，并將指令打包，硬件相對(duì)簡(jiǎn)單。

• 超長(zhǎng)指令字 (VLIW)：靜態(tài)多發(fā)射的典型代表。一條“超長(zhǎng)指令”包含多個(gè)獨(dú)立操作字段，編譯器負(fù)責(zé)調(diào)度和打包，硬件無需復(fù)雜的動(dòng)態(tài)調(diào)度邏輯。

• 挑戰(zhàn)：對(duì)編譯器要求極高；二進(jìn)制代碼兼容性差；難以處理緩存缺失等動(dòng)態(tài)事件。

五、 多發(fā)射處理器
1. 超標(biāo)量處理器 (Superscalar)：每個(gè)時(shí)鐘周期動(dòng)態(tài)發(fā)射可變數(shù)量的指令（如1-8條），依賴硬件（如Tomasulo）進(jìn)行動(dòng)態(tài)調(diào)度、相關(guān)檢測(cè)和亂序執(zhí)行。這是現(xiàn)代通用CPU的主流技術(shù)。
2. 超流水線處理器 (Superpipelining)：將流水線劃分成更多、更細(xì)的階段，通過提高主頻來提升性能，屬于時(shí)間并行。常與超標(biāo)量技術(shù)結(jié)合使用。

本章小結(jié)
指令級(jí)并行是提升單處理器性能的核心技術(shù)。主要途徑包括：

• 硬件動(dòng)態(tài)方法：通過記分板、Tomasulo算法實(shí)現(xiàn)亂序執(zhí)行；結(jié)合分支預(yù)測(cè)和推測(cè)執(zhí)行（ROB）克服控制相關(guān)。
• 軟件靜態(tài)方法：通過編譯器進(jìn)行循環(huán)展開、指令調(diào)度，服務(wù)于靜態(tài)多發(fā)射/VLIW架構(gòu)。
• 現(xiàn)代高性能處理器（如Intel/AMD的CPU）普遍采用動(dòng)態(tài)調(diào)度的超標(biāo)量結(jié)構(gòu)，并結(jié)合強(qiáng)大的分支預(yù)測(cè)和推測(cè)執(zhí)行技術(shù)，以挖掘程序中的指令級(jí)并行。