第三章 指令級(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。
- 限制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ù)
- 記分板算法 (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段:
- 發(fā)射 (Issue):檢查結(jié)構(gòu)沖突與WAW相關(guān)。
- 讀操作數(shù) (Read Operands):等待數(shù)據(jù)相關(guān)消除(即源操作數(shù)就緒)。
- 執(zhí)行 (Execution):在功能單元中計(jì)算。
- 寫回 (Write Back):結(jié)果寫回寄存器。
- 缺點(diǎn):檢測(cè)和解決所有相關(guān),硬件復(fù)雜;無法處理WAR和WAW相關(guān)(通過停頓解決,影響效率)。
- 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í)行
- 分支預(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è)。
- 推測(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ù)(由編譯器完成)
- 循環(huán)展開 (Loop Unrolling)
- 將循環(huán)體復(fù)制多次,減少循環(huán)控制指令(如分支、自增)的開銷,為編譯器調(diào)度創(chuàng)造更多指令,以填充延遲槽。
- 需注意寄存器壓力增加和代碼膨脹問題。
- 指令調(diào)度 (Instruction Scheduling)
- 編譯器通過調(diào)整指令順序,盡可能分離存在數(shù)據(jù)相關(guān)的指令,以填充因數(shù)據(jù)相關(guān)或功能單元延遲導(dǎo)致的流水線氣泡。
- 常用方法:靜態(tài)調(diào)度、軟流水線 (Software Pipelining) 等。
- 靜態(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í)并行。