控制相關的動態(tài)解決技術

1、128秦杰 鄭麗萍 張慶輝4.3 控制相關的動態(tài)解決技術 處理器一個時鐘周期流出多條指令受到以下兩處理器一個時鐘周期流出多條指令受到以下兩 個因素的限制：個因素的限制： 流出流出n n條條指令的處理器中，遇到分支指令的指令的處理器中，遇到分支指令的 速度也快了速度也快了n n倍；倍； 根據根據AmdahlAmdahl定律可知，隨著機器定律可知，隨著機器CPICPI的降低，的降低， 控制相關對性能的影響越來越大?？刂葡嚓P對性能的影響越來越大。第四章 指令級并行228秦杰 鄭麗萍 張慶輝本節(jié)著重于：本節(jié)著重于： 通過硬件技術，動態(tài)地進行分支處理，對程通過硬件技術，動態(tài)地進行分支處理，對程序運行時的

2、分支行為進行預測，提前對分支操作做序運行時的分支行為進行預測，提前對分支操作做出反應，加快分支處理的速度。出反應，加快分支處理的速度。 分支的最終延遲分支的最終延遲取決于流水線的結構、預測的取決于流水線的結構、預測的方法和預測錯誤后恢復所采取的策略。方法和預測錯誤后恢復所采取的策略。 4.3 控制相關的動態(tài)解決技術328秦杰 鄭麗萍 張慶輝4.3.1 分支預測緩沖 動態(tài)分支預測必須解決動態(tài)分支預測必須解決兩個問題兩個問題： 如何記錄一個分支操作的歷史。如何記錄一個分支操作的歷史。 決定預測的走向。決定預測的走向。 記錄分支歷史的方法有以下幾種：記錄分支歷史的方法有以下幾種： （1 1）僅僅記錄

3、最近一次或最近幾次的分支歷史；）僅僅記錄最近一次或最近幾次的分支歷史； （2 2）記錄分支成功的目標地址；）記錄分支成功的目標地址； （3 3）記錄分支歷史和分支目標地址，相當于前）記錄分支歷史和分支目標地址，相當于前 面兩種方式的結合；面兩種方式的結合； （4 4）記錄分支目標地址的一條或若干條指令。）記錄分支目標地址的一條或若干條指令。 4.3 控制相關的動態(tài)解決技術428秦杰 鄭麗萍 張慶輝分支預測緩沖技術分支預測緩沖技術（Branch-Prediction BufferBranch-Prediction Buffer或者或者Branch History TableBranch Hist

4、ory Table，簡寫為，簡寫為BTBBTB或者或者BHTBHT）：）： 目前廣泛使用的最簡單的動態(tài)分支預測技術。目前廣泛使用的最簡單的動態(tài)分支預測技術。 使用一片存儲區(qū)域，記錄最近一次或幾次分支特使用一片存儲區(qū)域，記錄最近一次或幾次分支特征的歷史。征的歷史。 1. 只有只有1 1個預測位個預測位的分支預測緩沖的分支預測緩沖 索引索引：分支指令地址的低位。：分支指令地址的低位。 存儲區(qū)存儲區(qū)：1 1位位的分支歷史記錄位，又稱為的分支歷史記錄位，又稱為 預測位，記錄該指令最近一次預測位，記錄該指令最近一次 分支是否成功。分支是否成功。4.3 控制相關的動態(tài)解決技術528秦杰 鄭麗萍 張慶輝狀態(tài)

5、轉換圖狀態(tài)轉換圖 “0”“0”記錄分支不成功記錄分支不成功 “1”1”記錄分支成功記錄分支成功 1 0 分支不成功 分支成功 分支不成功 分支成功 圖圖4.9 4.9 只有只有1 1個預測位的分支預測緩沖狀態(tài)轉換圖個預測位的分支預測緩沖狀態(tài)轉換圖 4.3 控制相關的動態(tài)解決技術628秦杰 鄭麗萍 張慶輝2. 2. 分支預測緩沖技術包括兩個步驟分支預測緩沖技術包括兩個步驟 分支預測分支預測 如果當前緩沖記錄的預測位為如果當前緩沖記錄的預測位為“1”1”，則預，則預 測分為成功；如果預測位為測分為成功；如果預測位為“0”0”，則預測分支，則預測分支為不成功。為不成功。預測位修改預測位修改 如果當前

6、分支成功，則預測位置為如果當前分支成功，則預測位置為“1”1”； 如果當前分支不成功，預測位置為如果當前分支不成功，預測位置為“0”0”。 3.3.分支預測錯誤時，預測位就被修改，并且需分支預測錯誤時，預測位就被修改，并且需 要恢復現(xiàn)場，程序從分支指令處重新執(zhí)行要恢復現(xiàn)場，程序從分支指令處重新執(zhí)行。 4.3 控制相關的動態(tài)解決技術728秦杰 鄭麗萍 張慶輝 i-1 i i+1 i+2 p+1 p+2 猜測執(zhí)行路徑 實際執(zhí)行路徑 分支指令 得到分支結果 圖圖4.10 4.10 分支預測執(zhí)行不成功和重新執(zhí)行過程分支預測執(zhí)行不成功和重新執(zhí)行過程 4.3 控制相關的動態(tài)解決技術828秦杰 鄭麗萍 張慶

7、輝例例4.64.6 一個循環(huán)共循環(huán)一個循環(huán)共循環(huán)1010次，它將分支成功次，它將分支成功9 9次，次， 1 1次不成功。假設此分支的預測位始終在次不成功。假設此分支的預測位始終在緩沖區(qū)中。那么分支預測的準確性是多少？緩沖區(qū)中。那么分支預測的準確性是多少？ 解解 這種固定的預測將會在第一次和最后一次這種固定的預測將會在第一次和最后一次 循環(huán)中出現(xiàn)預測錯誤。循環(huán)中出現(xiàn)預測錯誤。 第一次預測錯誤是源于上次程序的執(zhí)行，第一次預測錯誤是源于上次程序的執(zhí)行， 因為上一次程序最后一次分支是不成功的。因為上一次程序最后一次分支是不成功的。 最后一次預測錯誤是不可避免的，因為前最后一次預測錯誤是不可避免的，因為

8、前 面的分支總是成功，共面的分支總是成功，共九九次。次。 因此，盡管分支成功的比例率是因此，盡管分支成功的比例率是90%90%， 但分支預測的準確性為但分支預測的準確性為80%80%（兩兩次不正確，次不正確， 8 8次確）。次確）。 4.3 控制相關的動態(tài)解決技術928秦杰 鄭麗萍 張慶輝4.4.1 1位預測機制的位預測機制的缺點缺點 只要預測出錯，往往是連續(xù)兩次而不是一次。只要預測出錯，往往是連續(xù)兩次而不是一次。5.5.解決方法解決方法 采用采用兩個預測位的預測機制兩個預測位的預測機制。 在兩個預測位的分支預測中，更改對分支的在兩個預測位的分支預測中，更改對分支的預測必須有兩次連續(xù)預測錯誤。

9、預測必須有兩次連續(xù)預測錯誤。 兩位分支預測的狀態(tài)轉換圖兩位分支預測的狀態(tài)轉換圖4.3 控制相關的動態(tài)解決技術1028秦杰 鄭麗萍 張慶輝 分支預測： 不成功 分支預測： 成功 11 10 分支不成功 分支成功 分支不成功 分支成功 01 00 分支不成功 分支成功 分支不成功 分支成功 圖圖4.11 4.11 具有兩個分支預測位的分支預測緩沖狀態(tài)轉換機制具有兩個分支預測位的分支預測緩沖狀態(tài)轉換機制 4.3 控制相關的動態(tài)解決技術1128秦杰 鄭麗萍 張慶輝6. 6. n n位位分支預測緩沖分支預測緩沖采用采用n n位位計數器，則計數器的值在計數器，則計數器的值在0 0到到2 2n n-1-1之

10、間：之間： 當計數器的值大于或等于最大值的一半（當計數器的值大于或等于最大值的一半（2 2n-1n-1）時，則預測下一次分支成功；時，則預測下一次分支成功； 否則預測下一次分支不成功。否則預測下一次分支不成功。預測位的修改和兩位預測時相同：預測位的修改和兩位預測時相同： 當分支成功時計數器的值當分支成功時計數器的值加加1 1，不成功時，不成功時減減1 1。研究表明：研究表明： n n位位分支預測的性能和兩位分支預測差不多，分支預測的性能和兩位分支預測差不多，因而大多數處理器都只采用兩位分支預測。因而大多數處理器都只采用兩位分支預測。4.3 控制相關的動態(tài)解決技術1228秦杰 鄭麗萍 張慶輝7.

11、7.對于真實的應用程序，兩位的分支預測的準對于真實的應用程序，兩位的分支預測的準確率可達到多少呢？確率可達到多少呢？ SPEC89SPEC89標準程序的測試：標準程序的測試： 在使用在使用40964096個記錄項的緩沖區(qū)時，分支個記錄項的緩沖區(qū)時，分支 預測準確率可達到預測準確率可達到99%99%到到82%82%。 使用無窮多歷史記錄項的分支預測緩沖，使用無窮多歷史記錄項的分支預測緩沖， 只有少量程序的分支預測準確率僅僅比只有少量程序的分支預測準確率僅僅比40964096 個記錄項提高個記錄項提高1%1%，多數程序的預測精度是相，多數程序的預測精度是相 同的。同的。 因此，對于因此，對于SPE

12、C89SPEC89應用環(huán)境而言，應用環(huán)境而言，4K4K的的 緩沖區(qū)是恰當的。緩沖區(qū)是恰當的。8.8.上述分支預測機制對于改進后的上述分支預測機制對于改進后的DLXDLX流水線沒流水線沒有幫助。有幫助。 4.3 控制相關的動態(tài)解決技術1328秦杰 鄭麗萍 張慶輝4.3.2 分支目標緩沖 目標：目標：將分支的開銷降為零。將分支的開銷降為零。方法：方法：分支目標緩沖分支目標緩沖 將分支成功的分支指令的地址和它的分支目將分支成功的分支指令的地址和它的分支目標地址都放到一個緩沖區(qū)中保存起來，緩沖區(qū)標地址都放到一個緩沖區(qū)中保存起來，緩沖區(qū)以分支指令的地址作為標示；取指令階段，所以分支指令的地址作為標示；取

13、指令階段，所有指令地址都與保存的標示作比較，一旦相同，有指令地址都與保存的標示作比較，一旦相同，我們就認為本指令是分支指令，且認為它轉移我們就認為本指令是分支指令，且認為它轉移成功，并且它的分支目標（下一條指令）地址成功，并且它的分支目標（下一條指令）地址就是保存在緩沖區(qū)中的分支目標地址。就是保存在緩沖區(qū)中的分支目標地址。 這個緩沖區(qū)就是這個緩沖區(qū)就是分支目標緩沖區(qū)分支目標緩沖區(qū)（Branch-Branch-Target BufferTarget Buffer，簡記為，簡記為BTBBTB，或者，或者Branch-Branch-Target CacheTarget Cache）。）。 4.3 控

14、制相關的動態(tài)解決技術1. 1. 分支目標緩沖結構和工作過程分支目標緩沖結構和工作過程 N 命中？ 當前 PC 地址標示 分支目標 PC 分支目標指令 查找、比較 分支目標緩沖 沒有命中，則認為本指令不是分支，按普通指令執(zhí)行 Y 命中，則認為本指令是分支，且分支成功，以分支目標緩沖中分支目標 PC 作為下一條指令地址 圖圖4.12 4.12 分支目標緩沖的結構和工作過程分支目標緩沖的結構和工作過程 2. 2. 在流水線的各個階段中，具有分支目標緩沖的工作在流水線的各個階段中，具有分支目標緩沖的工作 分配如圖分配如圖4.134.13。 當前 PC 值送存儲器和 BTB BTB 中存在？ 成功分支指

15、令？ 當前分支成功？ 以分支目標 PC 值送存儲器 否 是 否 普通指令 是 是 否 預測成功，后續(xù)指令無延遲執(zhí)行 預測錯誤，清除取來的指令并從分支的另外一個目標取指令，刪除BTB 中對應項 將當前指令PC 值和分支目標PC 送入 BTB 中作為一個新項 取指令 指令譯碼 指令執(zhí)行 問題：問題：解決預測錯誤或不命中的延遲。解決預測錯誤或不命中的延遲。 1628秦杰 鄭麗萍 張慶輝3. 3. 采用采用BTBBTB技術時指令在各種情況下的延遲技術時指令在各種情況下的延遲 指令在BTB中？是是不是不是預測結果成功成功實際的動作成功不成功成功不成功延遲周期0220表表4.3 4.3 采用采用BTBBT

16、B技術時指令在各種情況下的延遲技術時指令在各種情況下的延遲 4.3 控制相關的動態(tài)解決技術1728秦杰 鄭麗萍 張慶輝例例4.74.7 按按表表4.34.3計算分支轉移總的延遲，根據下面的假計算分支轉移總的延遲，根據下面的假 設，計算分支目標緩沖的性能。設，計算分支目標緩沖的性能。 （1 1）對于）對于BTBBTB中的指令，預測準確率中的指令，預測準確率90%90% （2 2）緩沖區(qū)命中率）緩沖區(qū)命中率90%90% （3 3）不在）不在BTBBTB中分支轉移成功的比例為中分支轉移成功的比例為60%60% 解解 根據根據表表4.34.3的分類，性能計算包括的分類，性能計算包括4 4個個部分：部分

17、： （1 1）在）在BTBBTB中，預測成功，實際成功，此時的中，預測成功，實際成功，此時的 延遲為延遲為0 0。 （2 2）在）在BTBBTB中，預測成功，實際不成功，此時中，預測成功，實際不成功，此時 的延遲為：的延遲為： 4.3 控制相關的動態(tài)解決技術1828秦杰 鄭麗萍 張慶輝 BTBBTB命中率命中率 預測錯誤率預測錯誤率 2 2 = 90% = 90% 10% 10% 2 2 = 0.18 = 0.18（時鐘周期）（時鐘周期）（3 3）不在）不在BTBBTB中，實際成功，此時的延遲為：中，實際成功，此時的延遲為：（1-BTB1-BTB命中率）命中率） 不在不在BTBBTB中分支轉移

18、成功率中分支轉移成功率 2 2 = 10% = 10% 60% 60% 2 2 = 0.12 = 0.12（時鐘周期）（時鐘周期）（4 4）不在）不在BTBBTB中，實際不成功，此時的延遲為中，實際不成功，此時的延遲為0 0。4.3 控制相關的動態(tài)解決技術1928秦杰 鄭麗萍 張慶輝4. 4. 對分支預測機制的一種改進對分支預測機制的一種改進 在緩沖區(qū)中不僅存入目的地址，而且還存入一在緩沖區(qū)中不僅存入目的地址，而且還存入一 個或多個目標指令。個或多個目標指令。 有兩種潛在的有兩種潛在的好處好處： 在連續(xù)取指令之前，可以較長時間的訪問緩沖在連續(xù)取指令之前，可以較長時間的訪問緩沖區(qū)，這時的分支目的

19、緩沖區(qū)較大。區(qū)，這時的分支目的緩沖區(qū)較大。對目的指令進行緩沖，構成稱為對目的指令進行緩沖，構成稱為分支目標指令分支目標指令緩沖緩沖（branch foldingbranch folding）的結構，它可使無條）的結構，它可使無條件分支的延遲達到零，甚至有的條件分支也可件分支的延遲達到零，甚至有的條件分支也可達到零延遲達到零延遲 。4.3 控制相關的動態(tài)解決技術2028秦杰 鄭麗萍 張慶輝4.3.3 基于硬件的前瞻執(zhí)行 前瞻（前瞻（SpeculationSpeculation）的技術方法）的技術方法： 它允許在處理器還未判斷指令是否能執(zhí)行它允許在處理器還未判斷指令是否能執(zhí)行之前就提前執(zhí)行，以克服

20、控制相關。之前就提前執(zhí)行，以克服控制相關。 在大多數指令前瞻正確的前提下，前瞻就在大多數指令前瞻正確的前提下，前瞻就可以有效地加快分支處理的速度?？梢杂行У丶涌旆种幚淼乃俣?。 1.1.基于硬件的前瞻執(zhí)行結合了基于硬件的前瞻執(zhí)行結合了三種思想三種思想： （1 1）采用動態(tài)的分支預測技術來選擇后續(xù)執(zhí)）采用動態(tài)的分支預測技術來選擇后續(xù)執(zhí) 行語句；行語句；4.3 控制相關的動態(tài)解決技術2128秦杰 鄭麗萍 張慶輝 （2 2）在控制相關消除之前指令前瞻執(zhí)行；）在控制相關消除之前指令前瞻執(zhí)行； （3 3）對基本塊采用動態(tài)調度。）對基本塊采用動態(tài)調度。 2.2.基于硬件的前瞻是動態(tài)地根據數據相關性來選擇基

21、于硬件的前瞻是動態(tài)地根據數據相關性來選擇指令和指令的執(zhí)行時間。指令和指令的執(zhí)行時間。 實質：實質：數據流驅動運行數據流驅動運行（data-flow executiondata-flow execution） 只要操作數有效，指令就可以執(zhí)行。只要操作數有效，指令就可以執(zhí)行。3.3.指令的確認指令的確認 前瞻執(zhí)行的指令產生的結果要一直到指令處前瞻執(zhí)行的指令產生的結果要一直到指令處于非前瞻執(zhí)行狀態(tài)時，才能確定為最終結果，才于非前瞻執(zhí)行狀態(tài)時，才能確定為最終結果，才允許最終寫到寄存器或存儲器中去。允許最終寫到寄存器或存儲器中去。 4.3 控制相關的動態(tài)解決技術2228秦杰 鄭麗萍 張慶輝4.4.實現(xiàn)前

22、瞻的實現(xiàn)前瞻的關鍵思想關鍵思想： 允許指令亂序執(zhí)行，但必須順序確認。允許指令亂序執(zhí)行，但必須順序確認。5.5.再定序緩沖（再定序緩沖（reorder bufferreorder buffer，簡記為，簡記為ROBROB） 保存那些執(zhí)行完畢但未經確認的指令及其結保存那些執(zhí)行完畢但未經確認的指令及其結果。在指令執(zhí)行完畢和確認之間這段時間里，由果。在指令執(zhí)行完畢和確認之間這段時間里，由 再定序緩沖提供所有其他指令需要的作為操作數再定序緩沖提供所有其他指令需要的作為操作數的數據。再定序緩沖區(qū)還可以取代?。ǖ臄祿?。再定序緩沖區(qū)還可以取代?。╨oadload）緩）緩 沖區(qū)。沖區(qū)。 4.3 控制相關的動態(tài)解

23、決技術2328秦杰 鄭麗萍 張慶輝再定序緩沖的每個項包含再定序緩沖的每個項包含三個域三個域： （1 1）指令的類型）指令的類型 指令類型包括是否是分支（尚無結果）、指令類型包括是否是分支（尚無結果）、 存操作（目的地址為存儲器）或寄存器操作存操作（目的地址為存儲器）或寄存器操作 （ALUALU操作或目的地址是寄存器的取操作）。操作或目的地址是寄存器的取操作）。 （2 2）目的地址）目的地址 目的地址域給出結果應寫入的目的寄存目的地址域給出結果應寫入的目的寄存 器號（對于取操作和器號（對于取操作和ALUALU指令）或存儲器的地指令）或存儲器的地 址（存操作）。址（存操作）。 （3 3）值域）值域

24、 值域用來保存指令前瞻執(zhí)行的結果，直值域用來保存指令前瞻執(zhí)行的結果，直 到指令得到確認。到指令得到確認。 4.3 控制相關的動態(tài)解決技術 使用再定序緩沖的處理部件的硬件結構使用再定序緩沖的處理部件的硬件結構 浮點 操作 隊列 再定序緩沖 浮點寄存器組 FP 加法器 FP 乘法器 公共數據總線 從存儲器來 (取的結果) ） 從指令部件來 保留站 去存儲器 (地址/數據) 操作總線 操作數總線 圖圖4.14 4.14 采用采用TomasuloTomasulo算法并支持前瞻執(zhí)行的算法并支持前瞻執(zhí)行的DLXDLX浮點部件的結構浮點部件的結構 2528秦杰 鄭麗萍 張慶輝例例4.84.8 假設浮點功能單元的延遲為加法是假設浮點功能單元的延遲為加法是2 2個個時鐘周時鐘周 期，乘法是期，乘法是1010個個時鐘周期，除法時鐘周期，除法4040個個時鐘周時鐘周 期。給出下面的代碼段當指令期。給出下面的代碼段當指令MULTDMULTD要確認要確認 時的狀態(tài)。時的狀態(tài)。 LDLDF6,3