計算機系統(tǒng)結構

計算機系統(tǒng)結構第1頁，共39頁，2023年，2月20日，星期二1流水線的結構相關結構相關：如果指令在流水線重疊執(zhí)行過程中，硬件資源滿足不了指令重疊執(zhí)行的要求，會產(chǎn)生資源沖突或競爭，稱為流水線結構相關。

指令執(zhí)行Load、Store：存儲器操作指令ALU：運算BRANCH轉移控制部件：執(zhí)行轉移指令第2頁，共39頁，2023年，2月20日，星期二表2.1不同類型指令中各流水段的操作IF：按指令計數(shù)器內容訪問主存，指令送到寄存器ID：指令譯碼。讀寄存器IE：形成操作數(shù)地址ME:訪問主存讀取操作數(shù)----常與取指發(fā)生結構沖突WB:讀出結果寫回寄存器。結構相關常常發(fā)生在存儲器操作指令load/store

第3頁，共39頁，2023年，2月20日，星期二

假定流水線中有五條指令I1,I2,I3,I4,I5.非流水機器中，指令順序執(zhí)行，資源不會沖突。流水線執(zhí)行時，系統(tǒng)資源可能發(fā)生沖突。LOAD中

ME:訪問主存

IF:（主存中）取指令延遲技術：使某些指令延遲、停頓一或多個時鐘周期第4頁，共39頁，2023年，2月20日，星期二解決存儲器爭用沖突的辦法延遲技術：使某些指令延遲、停頓一或多個時鐘周期雙端口存儲器：允許同時讀兩個數(shù)據(jù)或指令雙存儲器（哈弗結構）：一個數(shù)據(jù)存儲，一個指令存儲。4軟件優(yōu)化編譯：指令重新排序消除結構相關。其它功能部件的結構相關，解決沖突辦法與上述思路類似。第5頁，共39頁，2023年，2月20日，星期二2流水線的數(shù)據(jù)相關

流水線中，多條指令并行執(zhí)行，程序在實際執(zhí)行中可能導致數(shù)據(jù)供求關系上產(chǎn)生沖突(違反了原定的次序)，稱為數(shù)據(jù)相關。

如以下兩條指令：

ADD

R1，R2，R3；(R2)＋(R3)→R1SUBR4，R1，R5；(R1)－(R5)→R4第6頁，共39頁，2023年，2月20日，星期二

指令在流水線中執(zhí)行時,可能改變指令讀／寫操作數(shù)順序ID：讀寄存器R1

先寫后讀WR

第7頁，共39頁，2023年，2月20日，星期二數(shù)據(jù)相關及其避免方法1后推法：遇到數(shù)據(jù)相關時，停頓后繼指令的執(zhí)行，直至前指令結果產(chǎn)生。2定向技術：又稱旁路技術或專用通路技術，想法是使后續(xù)指令提前得到前指令(ALU類）結果。3

聯(lián)鎖硬件(適合存儲器操作load,store指令）:4軟件法（靜態(tài)指令調度）：采用優(yōu)化編譯，通過指令重新排序方法來消除數(shù)據(jù)相關。

第8頁，共39頁，2023年，2月20日，星期二定向技術解決數(shù)據(jù)相關的ALU方案通過專門電路將該運算結果提前送到有關緩沖寄存器。供后續(xù)指令執(zhí)行（得到需要的操作數(shù)）。適合ALU類指令。第9頁，共39頁，2023年，2月20日，星期二采用定向技術解決數(shù)據(jù)相關

ME:空操作WB：寫回適合ALU類指令!第10頁，共39頁，2023年，2月20日，星期二3

采用聯(lián)鎖硬件解決數(shù)據(jù)相關

定向傳送技術來不及用時，可通過流水線聯(lián)鎖硬件，使某些指令或流水段暫停流動一或多個周期，再用定向傳送技術。又稱為空閑周期。

第11頁，共39頁，2023年，2月20日，星期二

4軟件法（靜態(tài)指令調度）：優(yōu)化編譯法，通過指令重新排盡可能消除數(shù)據(jù)相關。

如ADD

R1，R2，R3；SUBR4，R1，R5；改為ADD

R1，R2，R3；………

SUBR4，R1，R5；使兩條“相關”指令“分開”

第12頁，共39頁，2023年，2月20日，星期二【例】假設某指令序列中20%的指令是LOAD指令，且緊跟LOAD指令之后的半數(shù)指令使用到LOAD指令載入的結果。如果這種數(shù)據(jù)相關將產(chǎn)生一個時鐘周期的延遲，問理想流水線(沒有任何延遲，CPI為1)的指令執(zhí)行速度要比這種真實流水線快多少?

解：假定問理想流水線(沒延遲）的CPI為1。LOAD指令之后的半數(shù)指令需要暫停，CPI為2。又知LOAD指令占全部指令的20%，所以真實流水線的實際CPI為

第13頁，共39頁，2023年，2月20日，星期二2.4流水線控制相關

流水線控制相關：指因程序執(zhí)行轉移類指令而引起的沖突相關。包括無條件轉移、條件轉移、子程序調用、中斷等，它們屬分支指令，執(zhí)行中可能改變程序方向，造成流水線斷流。與數(shù)據(jù)相關相比,控制相關會引起程序執(zhí)行方向的改變，使流水線損失更大，稱為全局相關。全局相關結構圖如下圖所示。這里程序劃分為三個部分B0,B1和B2

，

每一部分內不再有分支操作指令，稱為一個基本塊（basicblock）。第14頁，共39頁，2023年，2月20日，星期二流水線控制相關流水線中條件轉移類執(zhí)行時，有兩種結果：

1.發(fā)生轉移，將程序計數(shù)器PC內容改成轉移目標地址；

2.不發(fā)生轉移，PC指向下一條指令地址。條件轉移指令往往要在流水線末端時轉移條件才能建立。流水線性能會大幅度下降。從相關角度看，條件轉移指令或中斷指令與后續(xù)指令存在著一種控制上的全局相關。第15頁，共39頁，2023年，2月20日，星期二條件轉移指令對流水線的影響

圖中條件轉移指令（BRANCH)通常要在ME段末尾才會使PC內容發(fā)生改變，流水線需停頓3個時鐘，直到PC中生成新地址后，才能取出下一條指令。

在最壞情況，條件轉移造成k-1個時鐘周期的停頓第16頁，共39頁，2023年，2月20日，星期二轉移指令對性能的影響

設一有k個流水段的流水線，執(zhí)行n條指令設條件轉移指令在程序中所占的比例為p，轉移成功概率為q。在最壞情況，一次轉移造成k-1個時鐘周期的“斷流”。n條指令的程序，條件轉移需要額外增加的時鐘周期數(shù)是pqn(k-1)Δt，因條件轉移,完成n條指令的總執(zhí)行時間

第17頁，共39頁，2023年，2月20日，星期二轉移指令對性能的影響

相應的流水線吞吐率為

當n→∞時，流水線最大吞吐率為（分析公式意義）

流水線吞吐率下降率為

第18頁，共39頁，2023年，2月20日，星期二【例】據(jù)統(tǒng)計，在一些典型程序中，轉移指令所占的比例為20%，轉移成功的概率為q＝60%。假設有一條8個流水段的指令流水線，問：由于條件轉移指令的影響，流水線的最大吞吐率下降多少?

解：已知p＝0.20,q＝0.60

k＝8

根據(jù)則第19頁，共39頁，2023年，2月20日，星期二靜態(tài)分支技術靜態(tài)轉移預測技術(猜測法)提前形成條件碼，生成轉移目標地址延遲轉移改進循環(huán)程序硬件上計算兩個PC值(轉移成功或失敗)。動態(tài)分支預測技術“轉移歷史表”BHT。“轉移目標緩沖?！保˙TB）轉移目標指令緩沖棧BTIB?？刂葡嚓P的解決方法第20頁，共39頁，2023年，2月20日，星期二1靜態(tài)轉移預測技術：條件轉移指令出現(xiàn)時，對條件轉移方向進行預測（或轉移成功或不成功）。按預測方向設置指令緩沖棧并預取指令。程序執(zhí)行過程中，靜態(tài)預測轉移的方向變。靜態(tài)轉移預測可用硬件，也可軟件實現(xiàn)?？梢栽谵D移的兩個方向上都采取預取指令。第21頁，共39頁，2023年，2月20日，星期二遇條件轉移時，用“猜測法”選擇一個分支方向。選擇“轉移不成功”方向?？刂七壿嫼唵巍！安聹y”不正確，已執(zhí)行多個流水段將浪費。靜態(tài)轉移預測技術

第22頁，共39頁，2023年，2月20日，星期二2提前形成條件碼，生成轉移目標地址條件轉移指令BRANCH通常要在ME形成條件轉移地址。多數(shù)情況下，可以提前判別轉移是否發(fā)生或形成條件轉移代碼。一些運算型條件轉移指令，在實際運算前（ID)或運算中間(EX)就能產(chǎn)生條件碼。不必等運算結束。把計算轉移目標地址操作移到ID段完成.

靜態(tài)分支技術

第23頁，共39頁，2023年，2月20日，星期二3延遲轉移：遇轉移指令時，依靠編譯器把一條或幾條與轉移結果無關的指令調度到轉移指令后面（調度槽），以延長轉移指令的可執(zhí)行時間，這些調度指令完成后，轉移指令的目的地址已計算出來。調度到轉移指令后的無關指令須遵循有效和有用的原則。延遲轉移要求流水線段數(shù)不能太多，段數(shù)越多，調度到轉移指令后的“無關指令”也要愈多。沒有合適指令調度時，無關指令可以是空操作。靜態(tài)分支技術第24頁，共39頁，2023年，2月20日，星期二“延遲轉移”下的調度模式

調度的ADD字指令必須滿足：1無關性。2有用性。3有效性

第25頁，共39頁，2023年，2月20日，星期二“延遲轉移”下的流水線時空圖轉移延遲槽中的指令“填補”了流水線原來須插入的暫停周期。假定把計算轉移目標地址操作已移到ID段完成.

第26頁，共39頁，2023年，2月20日，星期二4改進循環(huán)程序：

循環(huán)操作是程序中廣泛使用的一種條件轉移。條件轉移是否結束，取決于循環(huán)操作是否達到規(guī)定次數(shù)。

一般轉移不成功時，轉移指令對流水線的影響較小。因此,對給定的程序，轉移成功的概率越高，則對流水線的影響越大。編譯器在對源程序進行編譯時，通過提高循環(huán)程序中轉移不成功的概率。

第27頁，共39頁，2023年，2月20日，星期二i>0轉移（概率大）i=0轉移（概率?。?/p>

第28頁，共39頁，2023年，2月20日，星期二5硬件上設置兩個指令緩沖棧

當指令分析器分析到條件轉移指令時，設置兩個指令緩沖棧指令緩沖棧A——按轉移不成功方向預取指令，指令緩沖棧B——按轉移成功的方向預取指令。

當轉移條件碼產(chǎn)生時，轉移不成功，分析A中的指令；否則,分析B中指令第29頁，共39頁，2023年，2月20日，星期二動態(tài)分支預測技術

從轉移指令近期轉移是否成功的記錄，預測下一次轉移的方向。稱為動態(tài)分支預測技術.一、如何記錄轉移歷史信息根據(jù)記錄的轉移歷史信息，預測轉移方向。

記錄轉移歷史信息的方法通常有三種：把最近幾次轉移或不轉移的信息記錄在一個“轉移歷史表”BHT。把最近幾次轉移或不轉移的信息記錄在一個“轉移目標緩沖?！保˙TB）。第三種是存放在一個轉移目標指令緩沖棧BTIB。第30頁，共39頁，2023年，2月20日，星期二1

使用BHT的轉移預測BHT格式：

[轉移指令，歷史表信息，轉移目標指令(地址）]執(zhí)行轉移指令時，轉移成功或轉移失敗的信息可記錄在一個所謂的“轉移歷史表”BHT中。一個二進制位記錄最近一次轉移是否成功的信息。多個二進制位記錄最近幾次轉移是否成功的信息。無論預測的轉移方向與實際執(zhí)行結果的轉移方向是否相同，都要修改“轉移歷史表”BHT。為兼顧預測效果和便于硬件實現(xiàn)，常用2位計數(shù)器來記錄最近二次轉移是否成功的信息。第31頁，共39頁，2023年，2月20日，星期二用二進制數(shù)字10、11、01、00來表示轉移預測狀態(tài)的轉換圖轉移?。恨D移順序取：不轉移第32頁，共39頁，2023年，2月20日，星期二轉移歷史表BHT的硬件邏輯結構

第33頁，共39頁，2023年，2月20日，星期二優(yōu)點:轉移預測提前到取指階段。預測正確，則沒有任何延遲損失。預測不正確，則清除指令預取(隊列)緩沖器。會產(chǎn)生延遲時間損失.當執(zhí)行轉移指令時，把轉移成功與不成功的信息記錄在“轉移歷史表”中。當一條轉移指令第一次執(zhí)行時，沒有歷史轉移記錄，這時可預置轉移歷史信息。

BHT方法可以同I-cache（指令cache）結合起來。BHT的轉移預測第34頁，共39頁，2023年，2月20日，星期二

用轉移目標緩沖棧（BTB）的轉移預測使用轉移目標緩沖棧作為轉移預測策略。把BHT中轉移指令字段改為轉移指令地址

BTB格式[轉移指令地址，歷史表信息，轉移目標指令地址]一般在譯碼分析階段得到轉移指令地址

第35頁，共39頁，2023年，2月20日，星期二使用轉移目標指令緩沖棧(BTIB)轉移指令在指令分析部件中譯碼時，轉移不成功方向的指令已被預取到指令緩沖棧中，或者已經(jīng)存放在I-cache中。在轉移成功方向上也預取一部分指令，把BTB中的“轉移目標地址”改為存放轉移目標地址之后的n條指令。這種預測稱為轉移目標指令緩沖棧BTIB。

第36頁，共39頁，2023年，2月20日，星期二例題：在一臺單流水線處理機上執(zhí)行下面程序。指令經(jīng)過“取指”、“譯碼”、“執(zhí)行”、“寫結果”四個流水段，每個流水段延遲時間是5ns。但“執(zhí)行”流水段LS部件和ALU部件只能有一個工作，LS部件完成LOAD和STORE操作，ALU部件完成其它操作。兩個操作部件的輸出端和輸入端有直接輸出通路相互切換連接，ALU部件產(chǎn)生的條件碼能直接送入控制器。假定采用靜態(tài)分支預測技術，每次都預測轉移不成功。畫出指令流水線的時空圖.

I1SUBR0，R0