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

費(fèi)西安交通丈學(xué)農(nóng)科生課程：計算機(jī)系統(tǒng)結(jié)構(gòu)

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

第四章指令級并行執(zhí)行與調(diào)度

鄭慶華教授

西安交大計算機(jī)系

2009年4月

<鄭慶華教授

-

fmJQ口，.T、A-2tj1^1*^r-L-.r-tr-*r言TRFI

及西安交通大學(xué)如科生課程：計辭機(jī)系統(tǒng)結(jié)構(gòu)

引言

■標(biāo)量處理機(jī)：只有數(shù)據(jù)表示和標(biāo)量指令的處理機(jī)。

■提高處理機(jī)指令執(zhí)行速度的三條途徑：

1)Approach-1:CPU工作主頻的提高

2)Approach-2:采用更好的算法和功能部件。例如：

采用RISC,改進(jìn)乘法、除法的算法。

3)Approach-3:指令并行技術(shù)：①流水線技術(shù)；②

超標(biāo)量超流水線技術(shù)，即：一個處理機(jī)中設(shè)置多個

獨(dú)立的部件。如：Pentium;③超長指令字，在一

條指令中，設(shè)置有多個獨(dú)立的操作字段，每個字段

可以獨(dú)立控制。

jiu.ruu.cn內(nèi)”人牛我僅

本章內(nèi)容提綱

4.1指令級并行的概念

4.2指令的動態(tài)調(diào)度

4.3動態(tài)分支預(yù)測技術(shù)

4.4多指令流出技術(shù)

4.5循環(huán)展開和指令調(diào)度

4.6Pentium計算機(jī)原理

A.-Il1*—r-4crCZ1I’僅dl

4.1指令級并行

4.1.1指令級并行的概念

＞幾乎所有的處理機(jī)都利用流水線使指令重疊并行

執(zhí)行，以達(dá)到提高性能的目的。這種指令之間存

在的潛在并行性稱為指令級并行。

(ILP：Instruction-LevelParallelism)

＞本章研究：如何通過各種可能的技術(shù)，獲得更多

的指令級并行性。

硬件+軟件技術(shù)

必須要硬件和軟件技術(shù)互相配合，才能夠最大限度地挖

掘出程序中存在的指令級并行。

fmJQ-1~A.21JerwrUIT*僅TI

1.流水線處理機(jī)的實(shí)際CPI

＞理想流水線的CPI加上各類停頓的時鐘周期數(shù)：

CPI流水線=CPI理想+停頓結(jié)構(gòu)沖突+停頓數(shù)據(jù)沖突+停頓控制沖突

＞理想CPI是衡量流水線最高性能的一個指標(biāo)。

＞IPC：InstructionsPerCycle

（每個時鐘周期完成的指令條數(shù)）

2.基本程序塊

＞基本程序塊：一段除了入口和出口以外不包含其

他分支的線性代碼段。

＞程序平均每5?7條指令就會有一個分支。

E71

3.循環(huán)級并行：使一個循環(huán)中的不同循環(huán)體并行執(zhí)行。

＞開發(fā)循環(huán)體中存在的并行性

□最常見、最基本

＞是指令級并行研究的重點(diǎn)之一

＞例如，考慮下述語句：

for（i=l；i＜=500；i=i+l）

a[i]=a[i]+s；

□每一次循環(huán)都可以與其他的循環(huán)重疊并行執(zhí)行；

□在每一次循環(huán)的內(nèi)部，卻沒有任何的并行性。

fmJQ-1~A.21JerwrUIT*僅TI

4.最基本的開發(fā)循環(huán)級并行的技術(shù)

＞循環(huán)展開(loopunrolling)技術(shù)

＞采用向量指令和向量數(shù)據(jù)表示

5.流水線沖突：是指對于具體的流水線來說，由于相關(guān)的

存在，使得指令流中的下一條指令不能在指定的時鐘周

期執(zhí)行。

＞相關(guān)是程序固有的一種屬性，它反映了程序中指令

之間的相互依賴關(guān)系。

＞具體的一次相關(guān)是否會導(dǎo)致實(shí)際沖突的發(fā)生以及該

沖突會帶來多長的停頓，則是流水線的屬性。

6.可以從兩個方面來解決相關(guān)問題：

＞保持相關(guān)，但避免發(fā)生沖突。指令調(diào)度

＞通過代碼變換，消除相關(guān)。

rm/，Q0,^7-1~A.21J■在E71

7.控制相關(guān)并不是一個必須嚴(yán)格保持的關(guān)鍵屬性。

8.為正確地執(zhí)行程序，必須保持最關(guān)鍵的兩個屬性是：數(shù)

據(jù)流和異常行為。

＞保持異常行為是指：無論怎么改變指令的執(zhí)行順

序，都不能改變程序中異常的發(fā)生情況。

□即原來程序中是怎么發(fā)生的，改變執(zhí)行順序后還是怎么

發(fā)生。

□弱化為：指令執(zhí)行順序的改變不能導(dǎo)致程序中發(fā)生新的

異常。

＞如果我們能做到保持程序的數(shù)據(jù)相關(guān)和控制相關(guān)，

就能保持程序的數(shù)據(jù)流和異常行為。

fmJQ-1~A.21JerwrUIT*僅TI

□舉例說明

DADDUR2,R3,R4

BEQZR2,L1

LWRI,0(R2)

L1：

＞數(shù)據(jù)流：指數(shù)據(jù)值從其產(chǎn)生者指令到其消費(fèi)者指令

的實(shí)際流動。

□分支指令使得數(shù)據(jù)流具有動態(tài)性，因為它使得給定指令

的數(shù)據(jù)可以有多個來源。

□僅僅保持?jǐn)?shù)據(jù)相關(guān)性是不夠的，只有再加上保持控制順

序，才能夠保持程序順序。

fmJQ-1~A.21JerwrUIT*僅TI

□舉例：

DADDURI,R2,R3

BEQZR4,LI

DSUBURI,R5,R6

1????

ORR7,RLR8

有時，不遵守控制相關(guān)既不影響異常行為，也不改

變數(shù)據(jù)流。

□可以大膽地進(jìn)行指令調(diào)度，把失敗分支中的指令調(diào)度到

分支指令之前。改為：

DADDURI,R2,R3

BEQZR12,Skipnext

DSUBUR4,R5,R6

DADDUR5,R4,R9

Skipnext：ORR7,R8,R9

rmxq口”，JA.CCHr"\dl

本章內(nèi)容提綱

4.1指令級并行的概念

4.2指令的動態(tài)調(diào)度

4.3動態(tài)分支預(yù)測技術(shù)

4.4多指令流出技術(shù)

4.5循環(huán)展開和指令調(diào)度

4.6Pentium計算機(jī)原理

fCC/?？谄珹--2111,-r-41/"verUII,僅dl

4.2指令的動態(tài)調(diào)度

＞靜態(tài)調(diào)度

□依靠編譯器對代碼進(jìn)行靜態(tài)調(diào)度，以減少相關(guān)和沖突。

□它不是在程序執(zhí)行的過程中、而是在編譯期間進(jìn)行代碼調(diào)度和優(yōu)

化。

□通過把相關(guān)的指令拉開距離來減少可能產(chǎn)生的停頓。

＞動態(tài)調(diào)度

□在程序的執(zhí)行過程中，依靠專門硬件對代碼進(jìn)行調(diào)度，減少數(shù)據(jù)

相關(guān)導(dǎo)致的停頓。

■能夠處理一些在編譯時情況不明的相關(guān)（比如涉

及到存儲器訪問的相關(guān)），并簡化了編譯器；

■能夠使本來是面向某一流水線優(yōu)化編譯的代碼在

其他的流水線（動態(tài)調(diào)度）上也能高效地執(zhí)行。

□以硬件復(fù)雜性的顯著增加為代價

fmJQ-1~A.21JerwrUIT*僅TI

4.2.1動態(tài)調(diào)度的基本思想

到目前為止我們所使用流水線的最大的局限性：

A指令必須按序流出和執(zhí)行

＞考慮下面一段代碼：

DIV.DF4,FO,F2

SUB.DF10,F4,F6

ADD.DF12,F6,F14

SUB.D指令與DIV.D指令有F4相關(guān)，導(dǎo)致流水線停

頓。

ADD.D指令與流水線中的任何指令都沒有關(guān)系，但也

因此受阻。

rm/Q6片?-A.21.71#-ti

在前面的基本流水線中:

--------->ID

檢測結(jié)構(gòu)沖突

檢測數(shù)據(jù)沖突

一旦一條指令受阻，其后的指令都將停頓。

解決辦法：允許亂序執(zhí)行

rmX?？谄?1--A-1二—f4fLicmE71

1.為了允許亂序執(zhí)行，我們將5段流水線的譯碼階段再分為

兩個階段：

＞流出(Issue,IS)：指令譯碼，檢查是否存在結(jié)構(gòu)

沖突。(in-orderissue)

＞讀操作數(shù)(ReadOperands,RO)：等待數(shù)據(jù)沖突消

失，然后讀操作數(shù)。(outoforderexecution)

檢測結(jié)構(gòu)沖突檢測數(shù)據(jù)沖突

rm/，Q0,^7-1~A.21J■在E71

2.在前述5段流水線中，是不會發(fā)生WAR沖突和WAW

沖突的。但亂序執(zhí)行就使得它們可能發(fā)生了。

＞例如，考慮下面的代碼

DIV.DF10,FO,F2

卜存在輸出相關(guān)

一rSUB.DF10,F4,F6

存在反相關(guān)《

IADD.DF6,F8,F14

Tomasulo算法可以通過使用寄存器重命名來消除。

E71

3.動態(tài)調(diào)度的流水線支持多條指令同時處于執(zhí)行當(dāng)中。

＞要求：具有多個功能部件、或者流水功能部件、或

者兼而有之。

＞我們假設(shè)具有多個功能部件。

4.指令亂序完成帶來的最大問題：異常處理比較復(fù)雜，分

精確異常處理和不精確異常處理；

＞動態(tài)調(diào)度要保持正確的異常行為

□只有那些在嚴(yán)格按程序順序執(zhí)行時會發(fā)生的異常，才能

真正發(fā)生。

□保持正確的異常行為：對于一條會產(chǎn)生異常的指令來

說，只有當(dāng)處理機(jī)確切地知道該指令將被執(zhí)行后，才允

許它產(chǎn)生異常。

rm/，Q0,^7-1~A.21J■在府

＞即使保持了正確的異常行為，動態(tài)調(diào)度處理機(jī)仍可能發(fā)

生不精確異常。

＞不精確異常：當(dāng)執(zhí)行指令i導(dǎo)致發(fā)生異常時，處理機(jī)的現(xiàn)

場（狀態(tài)）與嚴(yán)格按程序順序執(zhí)行時指令i的現(xiàn)場不同。

□發(fā)生不精確異常的原因：

因為當(dāng)發(fā)生異常（設(shè)為指令i）時：

■流水線可能已經(jīng)執(zhí)行完按程序順序是位于指令i

之后的指令；

■流水線可能還沒完成按程序順序是指令i之前的

指令。

□不精確異常使得在異常處理后難以接著繼續(xù)執(zhí)行程序。

＞精確異常：如果發(fā)生異常時，處理機(jī)的現(xiàn)場跟嚴(yán)格按程

序順序執(zhí)行時指令i的現(xiàn)場相同。

記分牌算法和TomasuI。算法是兩種比較典型的動態(tài)調(diào)度算

法。

rm/，Q0,^7-1~A.21J■在府

4.2.2Tomasulo算法

1.核心思想

>記錄和檢測指令相關(guān)，操作數(shù)一旦就緒就立即執(zhí)行，把發(fā)生

RAW沖突的可能性減少到最?。?/p>

>通過寄存器換名來消除WAR沖突和WAW沖突。

2.IBM360/91首先采用了Tomasulo算法。

>TBM360/91的設(shè)計目標(biāo)是基于整個360系列的統(tǒng)一指令集和編

譯器來實(shí)現(xiàn)高性能，而不是設(shè)計和利用專用的編譯器來提高性

能。需要更多地依賴于硬件。

>IBM360體系結(jié)構(gòu)只有4個雙精度浮點(diǎn)寄存器，限制了編譯器調(diào)

度的有效性。

>360/91的訪存時間和浮點(diǎn)計算時間都很長。

（也是Tomasulo算法要解決的問題）

rm/，Q0,^7-1~A.21J■在

3.寄存器換名可以消除WAR沖突和WAW沖突。

＞考慮以下代碼:

DIV.DFO,F2,F4

反相關(guān)(F8)JADD.DF6,FO,F8

導(dǎo)致WAR沖乳SD輸出相關(guān)（F6）

F6,0(RI)“導(dǎo)致WAW沖突

SUB.DF8,F10,F14

MUL.DF6,F10,F8

＞消除名相關(guān)

□引入兩個臨時寄存器S和T

□把這段代碼改寫為:

DIV.DFO,F2,F4

ADD.DS,FO,F8

上兩個F6都換名為S

S.DS,0(R1)

「SUB.DT,F10,F14

兩個F8都換名為T」

IMUL.DF6,F10,T

fmJQ-1~A.21JerwrUIT*僅TI

4.基于Tomasulo算法的MIPS處理器浮點(diǎn)部件的基本結(jié)構(gòu)

從指令部件來

指浮點(diǎn)寄存器FP、

令

隊

列

load/store操作

浮點(diǎn)操作

store緩沖器地址部件

操作數(shù)總線

{load緩沖器

6

5操作總線

4

保tf

3

3留

2

2站

1

標(biāo)

1識

數(shù)據(jù)地址標(biāo)識

存儲部件浮點(diǎn)加法器浮點(diǎn)乘法器

、，公共數(shù)據(jù)總線（CDB）、「

rm/，Q0,^7-1~A-.21J.在府

叁西安交通大學(xué)本科生課程：計筆機(jī)系統(tǒng)結(jié)構(gòu)

ThreeStagesofTomasuloAlgorithm

1.Issue-getinstructionfromFPOpQueue

Ifreservationstationfree(nostructuralhazard),:

controlissuesinstruction&sendsoperands(renamesregisters).

2.Execution-operateonoperands(EX)

Whenbothoperandsreadythenexecute;

ifnotready,watchCommonDataBusforresult

3.Writeresult-finishexecution(WB)

WriteonCommonDataBustoallawaitingunits;

markreservationstationavailable

?Normaldatabus:data+destination("goto"bus)

?Commondatabus:data+source('bom。from-bus)

-64bitsofdata+4bitsofFunctionalUnitsourceaddress

-WriteifmatchesexpectedFunctionalUnit(producesresult)

-Doesthebroadcast

jtu.rdu.cn鄭慶華教授

fmjo口F-i**A.一1271

>保留站(reservationstation)

每個保留站中保存一條已經(jīng)流出并等待到本功能部件執(zhí)行

的指令(相關(guān)信息)。

包括：操作碼、操作數(shù)以及用于檢測和解決沖突的信息。

■在一條指令流出到保留站的時候，如果該指

令的源操作數(shù)已經(jīng)在寄存器中就緒，則將之

取到該保留站中。

■如果操作數(shù)還沒有計算出來，則在該保留站

中記錄將產(chǎn)生這個操作數(shù)的保留站的標(biāo)識。

□浮點(diǎn)加法器有3個保留站：ADD1,ADD2,ADD3

□浮點(diǎn)乘法器有兩個保留站：MULTI,MULT2

□每個保留站都有一個標(biāo)識字段，唯一地標(biāo)識了該保留站。

fmJQ-1~A.21JerwrUIT*僅TI

>公共數(shù)據(jù)總線CDB

（一條重要的數(shù)據(jù)通路）

□所有功能部件的計算結(jié)果都是送到CDB上，由它把這些

結(jié)果直接送到（播送到）各個需要該結(jié)果的地方。

□在具有多個執(zhí)行部件且采用多流出（即每個時鐘周期流

出多條指令）的流水線中，需要采用多條CDB。

>load緩沖器和store緩沖器

□存放讀/寫存儲器的數(shù)據(jù)或地址

□load緩沖器的作用有3個：

■存放用于計算有效地址的分量；

■記錄正在進(jìn)行的load訪存，等待存儲器的

響應(yīng)；

■保存已經(jīng)完成了的10ad的結(jié)果（即從存儲

器取來的數(shù)據(jù)），等待CDB傳輸。

fmJQ-1~A.21JerwrUIT*僅TI

□store緩沖器的作用有3個：

■存放用于計算有效地址的分量；

■保存正在進(jìn)行的store訪存的目標(biāo)地址，該

store正在等待存儲數(shù)據(jù)的到達(dá)；

■保存該store的地址和數(shù)據(jù)，直到存儲部件接

收。

＞浮點(diǎn)寄存器FP

□共有16個浮點(diǎn)寄存器：FO,F2,F4,…，F(xiàn)30o

□它們里過一對總線連接到功能部件，并通過CDB連接到

store緩沖器。

＞指令隊列

□指令部件送來的指令放入指令隊列

□指令隊列中的指令按先進(jìn)先出的順序流出

fmJQ-1~A.21Jt*-erwrUIT*僅TI

＞運(yùn)算部件

□浮點(diǎn)加法器完成加法和減法操作

□浮點(diǎn)乘法器完成乘法和除法操作

5.在Tomasul。算法中，寄存器換名是通過保留站和流出邏

輯來共同完成的。

＞當(dāng)指令流出時，如果其操作數(shù)還沒有計算出來，則

將該指令中相應(yīng)的寄存器號換名為將產(chǎn)生這個操作

數(shù)的保留站的標(biāo)識。

＞指令流出到保留站后，其操作數(shù)寄存器號或者換成

了數(shù)據(jù)本身（如果該數(shù)據(jù)已經(jīng)就緒），或者換成了

保留站的標(biāo)識，不再與寄存器有關(guān)系。

fmJQ-1~A.21JerwrUIT*僅TI

6.Tomasulo算法具有以下兩個特點(diǎn)：

＞沖突檢測和指令執(zhí)行控制是分布的。

每個功能部件的保留站中的信息決定了什么時候

指令可以在該功能部件開始執(zhí)行。

＞計算結(jié)果通過CDB直接從產(chǎn)生它的保留站傳送到

所有需要它的功能部件，而不用經(jīng)過寄存器。

7.指令執(zhí)行的步驟

使用Tomasulo算法的流水線需3段：

＞流出：從指令隊列的頭部取一條指令。

□如果該指令的操作所要求的保留站有空閑的，就把

該指令送到該保留站（設(shè)為r）。

fmJQ-1~A.21JerwrUIT*僅TI

■如果其操作數(shù)在寄存器中已經(jīng)就緒，就將這

些操作數(shù)送入保留站八

■如果其操作數(shù)還沒有就緒，就把將產(chǎn)生該操

作數(shù)的保留站的標(biāo)識送入保留站入

■一旦被記錄的保留站完成計算，它將直接把

數(shù)據(jù)送給保留站J

（寄存器換名和對操作數(shù)進(jìn)行緩沖，消除WAR沖

突）

□完成對目標(biāo)寄存器的預(yù)約工作，除了WAW沖突

□如果沒有空閑的保留站，指令就不能流出。

（發(fā)生了結(jié)構(gòu)沖突）

＞執(zhí)行

□當(dāng)兩個操作數(shù)都就緒后，本保留站就用相應(yīng)的功能部件

開始執(zhí)行指令規(guī)定的操作。

□load和store指令的執(zhí)行需要兩個步驟：

■計算有效地址（要等到基地址寄存器就緒）

■把有效地址放入load或store緩沖器

＞寫結(jié)果

□功能部件計算完畢后，就將計算結(jié)果放到CDB上，所有等

待該計算結(jié)果的寄存器和保留站（包括store緩沖器）都

同時從CDB上獲得所需要的數(shù)據(jù)。

fmJQ-1~A.21JerwrUIT*僅TI

8.每個保留站有以下6個字段：

>Op：要對源操作數(shù)進(jìn)行的操作。

>Qj,Qk：將產(chǎn)生源操作數(shù)的保留站號。

□等于0表示操作數(shù)已經(jīng)就緒且在Vj或Vk中，或者不需要操

作數(shù)。

>Vj,Vk：源操作數(shù)的值。

□對于每一個操作數(shù)來說，V或Q字段只有一個有效。

□對于load來說，Vk字段用于保存偏移量。

>Busy：為“yes”表示本保留站或緩沖單元“忙”。

>A：僅load和store緩沖器有該字段。開始是存放指令中的立

即數(shù)字段，地址計算后存放有效地址。

>Qi：寄存器狀態(tài)表。

□每個寄存器在該表中有對應(yīng)的一項，用于存放將把結(jié)果寫

入該寄存器的保留站的站號。

□為0表示當(dāng)前沒有正在執(zhí)行的指令要寫入該寄存器，也即該

寄存器中的內(nèi)容就緒。

府

Tomasulo算法舉例

例4.1對于下述指令序列，給出當(dāng)?shù)谝粭l指令完成并寫

入結(jié)果時，Tomasulo算法所用的各信息表中的內(nèi)容。

L.DF6,34(R2)

L.DF2,45(R3)

MUL.DF0,F2,F4

SUB.DF8,F2,F6

DIV.DF10,F0,F6

ADD.DF6,F8,F2

fCCJOA.?tJiT—ccrCH廠反E

當(dāng)采用Tomasulo算法時，在上述給定的時刻，保留

站、load緩沖器以及寄存器狀態(tài)表中的內(nèi)容。

指令狀態(tài)表

指令

流出執(zhí)行寫結(jié)果

L.DF6,34(R2)VVV

L.DF2,45(R3)VV

MUL.DFO,F2,F4V

SUB.DF8,F6,F2V

DIV.DF10,FO,F6V

ADD.DF6,F8,F2V

rm/，Q0,^7-1~A,-21二?在cr府

保留站

名稱

BusyOpVjVkQiQkA

Loadlno

Load2yesLD5+Regs[R3

AddlyesSUBMem[34+Regs[R2]]I,oad2

Add2yesADD/iddlLoad2

Add3no

MultiyesMULReg[F4]I,oad2

Mult2yesDIVMem[34+Regs[R2]]Plultl

寄存器狀態(tài)表

FO〕F2F4F6F8F10???F30

QiMultiLoad2Adc12Add1Mut2...

rcc/ahm-人士LU'S_IRF1

Tomasulo算法具有兩個主要的優(yōu)點(diǎn)：

＞沖突檢測邏輯是分布的

（通過保留站和CDB實(shí)現(xiàn)）

□如果有多條指令已經(jīng)獲得了一個操作數(shù)，并同時在等待

同一運(yùn)算結(jié)果，那么這個結(jié)果一產(chǎn)生，就可以通過CDB

同時播送給所有這些指令，使它們可以同時執(zhí)行。

＞消除了WAW沖突和WAR沖突導(dǎo)致的停頓

使用保留站進(jìn)行寄存器換名，并且操作數(shù)一旦就緒就將

之放入保留站。

fmJQ-1~A.21JerwrUIT*僅TI

例4.2對于例4.1中的代碼，假設(shè)各種操作的延遲為：

load：1個時鐘周期

加法：2個時鐘周期

乘法：10個時鐘周期

除法：40個時鐘周期

給出MUL.D指令準(zhǔn)備寫結(jié)果時各狀態(tài)表的內(nèi)容。

解MUL.D指令準(zhǔn)備寫結(jié)果時各狀態(tài)表的內(nèi)容如下圖所

7Jxo

fmJQ-1~A.21Jt*-erwrUIT*僅TI

指令狀態(tài)表

指令

流出執(zhí)行寫結(jié)果

L.DF6,34(R2)VVV

L.DF2,45(R3)VVV

MUL.DFO,F2,F4VV

SUB.DF8,F6,F2VVV

DIV.DF10,FO,F6V

ADD.DF6,F8,F2VVV

fmXQ口片-1--A-1二—f4fLicmE71

保留站

名稱

BusyOpVjVkQjQkA

Loadlno

Load2yes

Addlyes

Add2yes

Add3no

MultiyesMuiMem[45+Regs[R3]]Reg[F4]

Mult2yes

DIVMem[34+Regs[R2]]Multi

寄存器狀態(tài)表

FOF2F4F6F8F10???F30

QiMultiMult2???

fmXQ口片-1--A-1二frFmcC2i僅

TomasuloM體算法

各符號的意義

>r：分配給當(dāng)前指令的保留站或者緩沖器單元編號;

>rd：目標(biāo)寄存器編號；

>rs>rt：操作數(shù)寄存器編號；

>imm：符號擴(kuò)展后的立即數(shù)；

ARS：保留站；

>result：浮點(diǎn)部件或load緩沖器返回的結(jié)果；

>Qi：寄存器狀態(tài)表；

>Regs[]：寄存器組；

fmJQ-1~A.21Jt*-erwrUIT*僅TI

＞與rs對應(yīng)的保留站字段：Vj,Qj

＞與rt對應(yīng)的保留站字段：Vk,Qk

＞Qi、Qj、Qk的內(nèi)容或者為0,或者是一個大于0的

整數(shù)。

□Qi為0表示相應(yīng)寄存器中的數(shù)據(jù)就緒。

□Qj、Qk為0表示保留站或緩沖器單元中的Vj或Vk字

段中的數(shù)據(jù)就緒。

□當(dāng)它們?yōu)檎麛?shù)時，表示相應(yīng)的寄存器、保留站或

緩沖器單元正在等待結(jié)果。

fmJQ-1~A.21JerwrUIT*僅TI

符號說明：（舉例）

MUL.DF4,F0,F2L.DF2,45(R3)

111111

rdrsrtrtimrs

?m.

jkkJ

S.DF3,40(R4)

III

rtimrs

rmxQ口”，JA.7^t"CCHr"\dl

MUL.DF4,FO,F2

1.指令流出III

>浮點(diǎn)運(yùn)算指令rdrsrt

進(jìn)入條件：有空閑保留站(設(shè)為r)jk

操作和狀態(tài)表內(nèi)容修改：

if(Qi[rs]=O)〃檢測第一操作數(shù)是否就緒

{RS[r].Vj—Regs[rs]；//第一操作數(shù)就緒。把寄存器rs

//中的操作數(shù)取到當(dāng)前保留站的

Vjo

RS[r].Qj<-0}；//置Qj為0,表示當(dāng)前保留站的Vj

//中的操作數(shù)就緒。

else//第一操作數(shù)沒有就緒

{RS[r].Qj<-Qi[rs]}//進(jìn)行寄存器換名，即把將產(chǎn)生該

//操作數(shù)的保留站的編號放入當(dāng)前保留站的Qj。

fmJQ-1~A.21JerwrUIT*僅TI

if(Qi[rt]=O)〃檢測第二操作數(shù)是否就緒

{RS[r].Vk<-Regs[rt]；//第二操作數(shù)就緒。把寄存器rt中的

//操作數(shù)取到當(dāng)前保留站的Vk。

RS[r].Qk—0}//置Qk為0,表示當(dāng)前保留站的Vk中的

//操作數(shù)就緒。

else〃第二操作數(shù)沒有就緒

{RS[r].Qk<-Qi[rt]}〃進(jìn)行寄存器換名,即把將產(chǎn)生該操作

//數(shù)的保留站的編號放入當(dāng)前保留站的

Qko

RS[r].Busy—yes；〃置當(dāng)前保留站為“忙”

RS[r].Op—Op；〃設(shè)置操作碼

Qi[rd]—r；//把當(dāng)前保留站的編號r放入rd所對應(yīng)

//的寄存器狀態(tài)表項，以便rd將來接收結(jié)

府

L.DF2,45(R3)

III

>load和store指令rtimmrs

進(jìn)入條件：緩沖器有空閑單元（設(shè)為「）kj

操作和狀態(tài)表內(nèi)容修改:

if(Qi[rs]=0)//檢測第一操作數(shù)是否就緒

{RS[r].Vj<r-Regs[rs]；//第一操作數(shù)就緒，把寄存器rs中的

//操作數(shù)取到當(dāng)前緩沖器單元的Vj

RS[r].Qj<-0}；//置Qj為3表示當(dāng)前緩沖器單元的Vj

//中的操作數(shù)就緒。

else//第一操作數(shù)沒有就緒

{RS[r].Qj—Qi[rs]}//進(jìn)行寄存器換名，即把將產(chǎn)生該

//操作數(shù)的保留站的編號存入當(dāng)前緩沖器單元的Qj。

fmJQ-1~A.21JerwrUIT*僅TI

L.DF2,45(R3)

III

rtimmrs

kj

RS[r].Busy—yes；//置當(dāng)前緩沖器單元為“忙”

RS[r].A—Imm；//把符號位擴(kuò)展后的偏移量放入

//當(dāng)前緩沖器單元的A

對于load指令：

Qi[rt]<—r；//把當(dāng)前緩沖器單元的編號r放入

//load指令的目標(biāo)寄存器rt所對應(yīng)的寄存器

//狀態(tài)表項，以便rt將來接收所取的數(shù)據(jù)。

rm/，Q0,^7-1~A.21J■在府

S.DF3,40(R4)

III

rtimmrs

對于store指令:kj

if(Qi[rt]=0)//檢測要存儲的數(shù)據(jù)是否就緒

{RS[r].Vk<-Regs[rt];//該數(shù)據(jù)就緒，把它從寄存器rt取到

//store緩沖器單元的Vk

RS[r].Qk<-0}；//置Qk為0,表示當(dāng)前緩沖器單元的Vk

//中的數(shù)據(jù)就緒。

else//該數(shù)據(jù)沒有就緒

{RS[r].Qk^Qi[rt]}//進(jìn)行寄存器換名，即把將產(chǎn)生該數(shù)

據(jù)的保留站的編號放入當(dāng)前緩沖器單元的Qk。

fmJQ-1~A.21JerwrUIT*僅TI

2.執(zhí)行

>浮點(diǎn)操作指令

□進(jìn)入條件：(RS[r|.Qj=O)且(RS[r].Qk=O)；

〃兩個源操作數(shù)就緒

□操作和狀態(tài)表內(nèi)容修改：進(jìn)行計算，產(chǎn)生結(jié)果。

>load/store指令

□進(jìn)入條件：(RS[r].Qj=0)且r成為load/store

緩沖隊列的頭部

□操作和狀態(tài)表內(nèi)容修改：

RS[r].A-RS[r].Vj+RS[r].A；〃計算有效地址

對于load指令，在完成有效地址計算后，還要進(jìn)行:

從Mem[RS[r].A]讀取數(shù)據(jù)；〃從存儲器中讀取數(shù)據(jù)

fmJQ-1~A.21Jt*-erwrUIT*僅TI

3.寫結(jié)果

＞浮點(diǎn)運(yùn)算指令和load指令

進(jìn)入條件：保留站r執(zhí)行結(jié)束，且CDB就緒。

操作和狀態(tài)表內(nèi)容修改：

Vx(if(Qi[x]=r)//對于任何一個正在等該結(jié)果

//的浮點(diǎn)寄存器X

{Regs[x]—result；//向該寄存器寫入結(jié)果

Qi[x]-0};//把該寄存器的狀態(tài)置為數(shù)據(jù)就緒

Vx(if(RS[x].Qj=r)//對于任何一個正在等該結(jié)果

〃作為第一操作數(shù)的保留站X

{RS[x].Vj<—result；//向該保留站的Vj寫入結(jié)果

RS[x].Qj^0)；//置Qj為0,表示該保留站的

//Vj中的操作數(shù)就緒

fmJQ-1~A.21JerwrUIT*僅TI

Vx(if(RS[x].Qk=r)//對于任何一個正在等該結(jié)果作為

//第二操作數(shù)的保留站x

{RS[x].Vk<—result；//向該保留站的Vk寫入結(jié)果

RS[x].Qk.O}；//置Qk為0,表示該保留站的Vk中的

//操作數(shù)就緒。

RS[r].Busy<—no；//釋放當(dāng)前保留站，將之置為空閑狀態(tài)。

>store指令

進(jìn)入條件：保留站r執(zhí)行結(jié)束，且RS[r].Qk=0

//要存儲的數(shù)據(jù)已經(jīng)就緒

操作和狀態(tài)表內(nèi)容修改：

Mem[RS[r].A]?-RS[r].Vk//數(shù)據(jù)寫入存儲器，地址由store

//緩沖器單元的A字段給出。

RSFrlBusv-no」〃釋放當(dāng)前緩沖器單元，將之置為空閑狀態(tài)。

rmxq口片A."7^i“一ccnr*W

本章內(nèi)容提綱

4.1指令級并行的概念

4.2指令的動態(tài)調(diào)度

4.3動態(tài)分支預(yù)測技術(shù)

4.4多指令流出技術(shù)

4.5循環(huán)展開和指令調(diào)度

4.6Pentium計算機(jī)原理

?一，□/?？谄?丁rki-ccnI“日dl

1.采用動態(tài)分支預(yù)測技術(shù)的目的

＞預(yù)測分支是否成功

＞盡快找到分支目標(biāo)地址（或指令），以避免控制相

關(guān)造成流水線停頓

2.需要解決的關(guān)鍵問題

＞如何記錄分支的歷史信息；

＞如何根據(jù)這些信息來預(yù)測分支的去向（甚至取到

指令）O

fmJQ-1~A.21JerwrUIT*僅TI

3.動態(tài)分支預(yù)測：在程序運(yùn)行時，根據(jù)分支指令過去的表

現(xiàn)來預(yù)測其將來的行為。

□如果分支行為發(fā)生了變化，預(yù)測結(jié)果也跟著改變。

□有更好的預(yù)測準(zhǔn)確度和適應(yīng)性。

4.分支預(yù)測的有效性取決于：

＞預(yù)測的準(zhǔn)確性

＞預(yù)測正確和不正確兩種情況下的分支開銷

決定分支開銷的因素：

-流水線的結(jié)構(gòu)

-預(yù)測的方法

■預(yù)測錯誤時的恢復(fù)策略等

A一Xcl.c_ccrCHI

注意：在預(yù)測錯誤時，要作廢已經(jīng)預(yù)取和分析的指

令，恢復(fù)現(xiàn)場，并從另一條分支路徑重新取指

令。

得到分支結(jié)果

fmJQ-1-A-.21Jt*-r-4**.r-erwrUIT*僅TI

4.3.1采用分支歷史表BHT

1.分支歷史表BHT(BranchHistoryTable)或分支預(yù)測緩沖

器(BranchPredicitonBuffer)

＞最簡單的動態(tài)分支預(yù)測方法。

＞用BHT來記錄分支指令最近一次或幾次的執(zhí)行情況

(成功或不成功)，并據(jù)此進(jìn)行預(yù)測。

2.只有1個預(yù)測位的分支預(yù)測緩沖：只記錄分支指令最近一

次的歷史，BHT中只需要1位二進(jìn)制位。

fmJQ-1~A.21JerwrUIT*僅TI

3.采用兩位二進(jìn)制位來記錄歷史

□提高預(yù)測的準(zhǔn)確度

□研究結(jié)果表明：兩位分支預(yù)測的性能與n位(n>2)分支

預(yù)測的性能差不多。

>兩位分支預(yù)測的狀態(tài)轉(zhuǎn)換如下所不：

八號鉆抽分支成?3廠、分支不成也，

分支預(yù)測：((11)<>(

成功八支成功,

分支成功八…々變丕感理

)]

分支預(yù)測：//分支不成

不成功」'分支成八分支不成功

rm/，Q0,^7-1~A-.21J.在cr府

＞兩位分支預(yù)測中的操作有兩個步驟：

□分支預(yù)測

■當(dāng)分支指令到達(dá)譯碼段（ID）時，根據(jù)從

BHT讀出的信息進(jìn)行分支預(yù)測。

■若預(yù)測正確，就繼續(xù)處理后續(xù)的指令，流

水線沒有斷流。否則，就要作廢已經(jīng)預(yù)取

和分析的指令，恢復(fù)現(xiàn)場，并從另一條分

支路徑重新取指令。

□狀態(tài)修改

4.BHT方法只在以下情況下才有意義：判定分支是否成功

所需的時間大于確定分支目標(biāo)地址所需的時間。

5.研究結(jié)果表明：對于SPEC89測試程序來說，具有大小

為4K的BHT的預(yù)測準(zhǔn)確率為82%?99%。一般來說，采

用4K的BHT就可以了。

E71

4.3.2采用分支目標(biāo)緩沖器BTB

目標(biāo)：將分支的開銷降為0

方法：分支目標(biāo)緩沖

＞將分支成功的分支指令的地址和它的分支目標(biāo)地址

都放到一個緩沖區(qū)中保存起來，緩沖區(qū)以分支指令

的地址作為標(biāo)識。

＞這個緩沖區(qū)就是分支目標(biāo)緩沖器（Branch-Target

Buffer,簡記為BTB,或者Branch-TargetCache）。

rm/，Q-1-A-.21J.在i'-

當(dāng)前取指令的地址

1.BTB的結(jié)構(gòu)

查找

＞看成是用專門的硬士ttWW、，預(yù)測的分支目標(biāo)地址

件實(shí)現(xiàn)的一張表

格。

＞表格中的每一項至

**

少有兩個字段：??

??

□執(zhí)行過的成功分支

指令的地址：該表

的匹配標(biāo)識

口預(yù)測的分支目標(biāo)地認(rèn)為本指令不是分支指令,

址按普通指令正常執(zhí)行。

|Y

認(rèn)為該指令是成功的分支指令，用預(yù)測的

分支目標(biāo)地址作為下一條指令的PC值。

府

2.采用BTB后，在流水線各個階段所進(jìn)行的相關(guān)操作:

IF段

ID段

EX段

rm/，Q0,^7-1~A--21二?在i'-r-4?*?r-i?-*c

3.采用BTB后，各種可能情況下的延遲:

指令在BTB中？預(yù)測實(shí)際情況延遲周期

日

X.成功成功0

日

成功不成功2

不是成功2

不是不成功0

JQ口片-1A--2LZfrF-7..LiemcC2i僅TI

4.BTB的另一種形式：在分支目標(biāo)緩沖器中存放一條或

者多條分支目標(biāo)處的指令。

＞有三個潛在的好處：

□更快地獲得分支目標(biāo)處的指令；

□