計算機(jī)系統(tǒng)結(jié)構(gòu)

計算機(jī)系統(tǒng)結(jié)構(gòu)1流水線的結(jié)構(gòu)相關(guān)結(jié)構(gòu)相關(guān)：如果指令在流水線重疊執(zhí)行過程中，硬件資源滿足不了指令重疊執(zhí)行的要求，會產(chǎn)生資源沖突或競爭，稱為流水線結(jié)構(gòu)相關(guān)。

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

第3頁,共39頁，2024年2月25日，星期天

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

ME:訪問主存

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

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

如以下兩條指令：

ADD

R1，R2，R3；(R2)＋(R3)→R1SUBR4，R1，R5；(R1)－(R5)→R4第6頁,共39頁，2024年2月25日，星期天

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

先寫后讀WR

第7頁,共39頁，2024年2月25日，星期天數(shù)據(jù)相關(guān)及其避免方法1后推法：遇到數(shù)據(jù)相關(guān)時，停頓后繼指令的執(zhí)行，直至前指令結(jié)果產(chǎn)生。2定向技術(shù)：又稱旁路技術(shù)或?qū)Ｓ猛芳夹g(shù)，想法是使后續(xù)指令提前得到前指令(ALU類）結(jié)果。3

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

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

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

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

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

第11頁,共39頁，2024年2月25日，星期天

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

如ADD

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

R1，R2，R3；………

SUBR4，R1，R5；使兩條“相關(guān)”指令“分開”

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

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

第13頁,共39頁，2024年2月25日，星期天2.4流水線控制相關(guān)

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

，

每一部分內(nèi)不再有分支操作指令，稱為一個基本塊（basicblock）。第14頁,共39頁，2024年2月25日，星期天流水線控制相關(guān)流水線中條件轉(zhuǎn)移類執(zhí)行時，有兩種結(jié)果：

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

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

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

在最壞情況，條件轉(zhuǎn)移造成k-1個時鐘周期的停頓第16頁,共39頁，2024年2月25日，星期天轉(zhuǎn)移指令對性能的影響

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

第17頁,共39頁，2024年2月25日，星期天轉(zhuǎn)移指令對性能的影響

相應(yīng)的流水線吞吐率為

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

流水線吞吐率下降率為

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

解：已知p＝0.20,q＝0.60

k＝8

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

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

靜態(tài)分支技術(shù)

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

調(diào)度的ADD字指令必須滿足：1無關(guān)性。2有用性。3有效性

第25頁,共39頁，2024年2月25日，星期天“延遲轉(zhuǎn)移”下的流水線時空圖轉(zhuǎn)移延遲槽中的指令“填補(bǔ)”了流水線原來須插入的暫停周期。假定把計算轉(zhuǎn)移目標(biāo)地址操作已移到ID段完成.

第26頁,共39頁，2024年2月25日，星期天4改進(jìn)循環(huán)程序：

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

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

第27頁,共39頁，2024年2月25日，星期天i>0轉(zhuǎn)移（概率大）i=0轉(zhuǎn)移（概率小）

第28頁,共39頁，2024年2月25日，星期天5硬件上設(shè)置兩個指令緩沖棧

當(dāng)指令分析器分析到條件轉(zhuǎn)移指令時，設(shè)置兩個指令緩沖棧指令緩沖棧A——按轉(zhuǎn)移不成功方向預(yù)取指令，指令緩沖棧B——按轉(zhuǎn)移成功的方向預(yù)取指令。

當(dāng)轉(zhuǎn)移條件碼產(chǎn)生時，轉(zhuǎn)移不成功，分析A中的指令；否則,分析B中指令第29頁,共39頁，2024年2月25日，星期天動態(tài)分支預(yù)測技術(shù)

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

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

使用BHT的轉(zhuǎn)移預(yù)測BHT格式：

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

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

BHT方法可以同I-cache（指令cache）結(jié)合起來。BHT的轉(zhuǎn)移預(yù)測第34頁,共39頁，2024年2月25日，星期天

用轉(zhuǎn)移目標(biāo)緩沖棧（BTB）的轉(zhuǎn)移預(yù)測使用轉(zhuǎn)移目標(biāo)緩沖棧作為轉(zhuǎn)移預(yù)測策略。把BHT中轉(zhuǎn)移指令字段改為轉(zhuǎn)移指令地址

BTB格式[轉(zhuǎn)移指令地址，歷史表信息，轉(zhuǎn)移目標(biāo)指令地址]一般在譯碼分析階段得到轉(zhuǎn)移指令地址

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

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

I1SUBR0，R0