第7章流水線技術(shù)與指令級(jí)并行7.1流水線處理的概念7.2浮點(diǎn)運(yùn)算流水線7.3指令流水線7.4流水線性能度量7.5指令流水線的性能提高7.6多發(fā)射處理器7.7指令級(jí)并行的概念

7.1流水線處理的概念

7.1.1流水線的一般結(jié)構(gòu)

在CPU中，流水線的一般結(jié)構(gòu)如圖7.1所示，這是一個(gè)典型的m級(jí)流水線，它由m個(gè)段(Stage或Segment，或稱為級(jí))S1、S2、…、Sm組成，每一段對(duì)通過(guò)它的信息同時(shí)完成各自單一的操作處理，最終的處理結(jié)果僅在一組信息通過(guò)了整個(gè)流水線之后才能獲得。圖7.1

CPU中流水線的一般結(jié)構(gòu)7.1.2流水線的類型

在現(xiàn)代計(jì)算機(jī)系統(tǒng)中有多種類型的流水線。

按流水線位于計(jì)算機(jī)系統(tǒng)的層次劃分，流水線可以分為系統(tǒng)級(jí)流水線、處理器級(jí)流水線和部件級(jí)流水線。圖7.2系統(tǒng)級(jí)流水線圖7.3處理器級(jí)流水線圖7.4部件級(jí)流水線——流水的微程序控制單元按流水線功能的強(qiáng)弱劃分，流水線可以分為單功能流水線和多功能流水線。圖7.5

TIASC計(jì)算機(jī)的運(yùn)算器流水線按同一時(shí)間內(nèi)流水段的連接方式劃分，流水線可以分為靜態(tài)流水線和動(dòng)態(tài)流水線。

按照流水線是否有反饋回路劃分，流水線可以分為線性流水線和非線性流水線。

按照輸出端任務(wù)流出順序與輸入端任務(wù)流入順序是否相同劃分，流水線可以分為順序流動(dòng)流水線(入出順序相同)和異步流動(dòng)流水線(入出順序不同)。

按一次處理對(duì)象的數(shù)量可將流水線分為標(biāo)量流水線、超標(biāo)量流水線、向量流水線和超長(zhǎng)指令字流水線。

7.2浮點(diǎn)運(yùn)算流水線

7.2.1浮點(diǎn)加減運(yùn)算流水線

由第3章可知，浮點(diǎn)數(shù)加/減運(yùn)算需要4個(gè)操作步驟,即對(duì)階、尾數(shù)加/減、結(jié)果處理和舍入處理。

4)舍入處理

舍入處理可以采用截?cái)喾?、末位恒置?”法、0舍1入法等。當(dāng)選擇截?cái)喾〞r(shí)，舍棄部分自然丟棄，所以不需要任何舍入處理操作或電路。圖7.6

IBMSystem360/91的浮點(diǎn)加/減法單元圖7.7浮點(diǎn)加/減法單元的流水線結(jié)構(gòu)7.2.2浮點(diǎn)乘除運(yùn)算流水線

浮點(diǎn)數(shù)乘/除運(yùn)算無(wú)需對(duì)階操作，相對(duì)于浮點(diǎn)數(shù)加/減運(yùn)算而言，它的操作步驟更加簡(jiǎn)潔。

4)舍入處理

舍入處理可以采用截?cái)喾?、末位恒置?”法、0舍1入法等。當(dāng)選擇截?cái)喾〞r(shí)，舍棄部分自然丟棄，所以不需要任何舍入處理操作或電路。

按照流水線的設(shè)計(jì)要求，浮點(diǎn)數(shù)乘/除運(yùn)算同樣可以用流水線實(shí)現(xiàn)，圖7.8就是一個(gè)兩段結(jié)構(gòu)的浮點(diǎn)數(shù)乘/除運(yùn)算流水線。由于階碼運(yùn)算與尾數(shù)運(yùn)算互不干擾，可以同時(shí)進(jìn)行，所以它們被放在流水線的同一段S1中處理，而S2段完成對(duì)尾數(shù)乘/除結(jié)果的規(guī)格化處理。圖7.8浮點(diǎn)乘/除法單元的流水線結(jié)構(gòu)若兩個(gè)n位定點(diǎn)二進(jìn)制數(shù)為X=xn－1xn－2…x0和Y=yn－1yn－2

…y0，則2n位乘積P為

(7-1)

式(7-1)表明，乘法的實(shí)現(xiàn)是通過(guò)一組Mi的求和來(lái)實(shí)現(xiàn)的。圖7.9兩級(jí)的進(jìn)位保留加法器圖7.10進(jìn)位保留(Wallace樹)乘法器圖7.11流水線進(jìn)位保留乘法器

7.3指令流水線

7.3.1基本的指令流水線

例如，可以將指令處理分解為以下4步:

(1)指令獲取(IF):從主存或Cache中獲取指令并對(duì)指令進(jìn)行譯碼。

(2)操作數(shù)加載(OL):從主存或Cache中獲取操作數(shù)放入寄存器中。

(3)執(zhí)行指令(EX):利用ALU等執(zhí)行部件，對(duì)寄存器中的操作數(shù)進(jìn)行處理，結(jié)果存于寄存器中。

(4)寫操作數(shù)(WO):將寄存器中的結(jié)果存入主存或Cache中。圖7.12由4級(jí)指令流水線組織的CPU結(jié)構(gòu)

R2000/3000采用的5級(jí)指令流水線由以下5段構(gòu)成:

(1)IF:利用指令Cache獲得指令。

(2)RD:當(dāng)對(duì)取得的指令進(jìn)行譯碼時(shí)，從寄存器RF中讀取操作數(shù)(MIPS指令無(wú)復(fù)雜的間接等尋址方式)。

(3)EX:利用ALU和必需的寄存器處理數(shù)據(jù)。

(4)MA:利用數(shù)據(jù)Cache加載或存儲(chǔ)操作數(shù)。

(5)WB:將操作數(shù)存儲(chǔ)(寫回)到寄存器。圖7.13

R2000/3000指令流水線結(jié)構(gòu)7.3.2指令流水線策略

1.增加指令流水線深度

采用深度指令流水線結(jié)構(gòu)是指將指令的執(zhí)行過(guò)程進(jìn)一步細(xì)化，使流水線的級(jí)(段)數(shù)變多，而每一級(jí)的工作更少、更合理。這樣做有兩個(gè)好處:一是流水線級(jí)數(shù)變多、處理更趨合

理，可使單條指令流水線并行執(zhí)行指令的能力更強(qiáng);二是每一級(jí)的處理時(shí)間更短，可以進(jìn)一步提高處理器的工作頻率。也就是說(shuō)，深度指令流水線可以使處理器執(zhí)行指令的速度更

快、效率更高。圖7.14為IntelPentiumⅡ的指令流水線結(jié)構(gòu)示意圖。PentiumⅡ架構(gòu)具有RISC內(nèi)核、CISC外殼的特點(diǎn)，內(nèi)部RISC微操作利用至少11段流水線實(shí)現(xiàn)(某些微操作需要多個(gè)執(zhí)行段)。圖7.14

IntelPentiumⅡ的指令流水線結(jié)構(gòu)

ROB是一個(gè)循環(huán)緩沖器，能夠保存多達(dá)40個(gè)微操作，并且也包含40個(gè)硬件寄存器。每一個(gè)緩沖器條目由以下幾個(gè)域組成:

·狀態(tài)——指示該微操作是否被安排執(zhí)行、是否已為了執(zhí)行而發(fā)送出、是否已完成執(zhí)行、是否準(zhǔn)備退出;

·存儲(chǔ)器地址——產(chǎn)生微操作的Pentium指令的地址;

·微操作——實(shí)際的操作;

·重命名寄存器——如果微操作與16個(gè)程序員可見寄存器關(guān)聯(lián)，則該條目更改寄存器名以便與40個(gè)硬件寄存器之一進(jìn)行映射。

2.增加指令流水線條數(shù)

以Intel微處理器為例，80486及之前的x86微處理器中只有一條指令流水線，程序中的所有指令都是通過(guò)這唯一的指令流水線來(lái)執(zhí)行的。而在Pentium處理器中設(shè)置了兩條指令

流水線，分別叫U指令流水線(主流水線)和V指令流水線(副流水線)。每個(gè)流水線都擁有自己的算術(shù)邏輯運(yùn)算部件ALU、地址生成邏輯以及與數(shù)據(jù)Cache的接口。U指令流水線可以執(zhí)行所有的指令，而V指令流水線只能執(zhí)行簡(jiǎn)單的指令。例如程序段:圖7.15

PowerPC601的指令流水線

7.4流水線性能度量

7.4.1時(shí)-空?qǐng)D

為了直觀地描述流水線的工作過(guò)程，通常采用時(shí)-空?qǐng)D。時(shí)-空?qǐng)D從時(shí)間和空間兩方面對(duì)流水線進(jìn)行描述，如圖7.16所示，其中橫坐標(biāo)表示時(shí)間，縱坐標(biāo)表示流水線資源(段，見圖7.16(a))或流水線處理對(duì)象(指令/數(shù)據(jù)，見圖7.16(b))。圖7.16流水線時(shí)-空?qǐng)D流水線的各段可以有不同的運(yùn)行時(shí)間τi(包含段間緩沖寄存器的緩沖延遲時(shí)間d)，此時(shí)橫坐標(biāo)以時(shí)間(如秒)為坐標(biāo)單位;但為了使流水線的控制易于實(shí)現(xiàn)，流水線的各段一般被設(shè)計(jì)為其運(yùn)行時(shí)間相同(設(shè)為τ)，且是流水線時(shí)鐘周期TCLK的整數(shù)倍，經(jīng)典設(shè)計(jì)為各段運(yùn)行時(shí)間1個(gè)時(shí)鐘周期(即1拍)，則

TCLK=τ=max{τi}從時(shí)-空?qǐng)D中可以看到，當(dāng)流水線被啟動(dòng)后，需要經(jīng)過(guò)一個(gè)啟動(dòng)階段流水管道才能被充滿，這個(gè)啟動(dòng)階段所用時(shí)間稱為通過(guò)時(shí)間(或填充時(shí)間)。在理想的情況下，

通過(guò)時(shí)間=(流水線級(jí)數(shù)－1)×?xí)r鐘周期

(7-2)

在通過(guò)時(shí)間之后，流水線達(dá)到穩(wěn)定而被充分利用，并且每個(gè)時(shí)鐘周期輸出一個(gè)新的結(jié)果。7.4.2吞吐率

1.最大吞吐率

最大吞吐率TPmax是指流水線在達(dá)到穩(wěn)定狀態(tài)后所得到的吞吐率，是流水線設(shè)計(jì)追求的重要指標(biāo)。

假設(shè)流水線各段運(yùn)行時(shí)間相等，為1個(gè)時(shí)鐘周期TCLK，則

(7-3)

也就是每一個(gè)時(shí)鐘周期流水線輸出一個(gè)結(jié)果，圖7.16(a)就說(shuō)明了這種情形。假設(shè)流水線各段運(yùn)行時(shí)間不等，第i段時(shí)間為τi

，如圖7.17(a)所示，則

(7-4)

在圖7.17(a)所示示例中，流水線的S3段運(yùn)行最慢，為3個(gè)時(shí)鐘周期，進(jìn)而影響到流水線每3個(gè)時(shí)鐘周期才能輸出一個(gè)處理結(jié)果，如圖7.17(b)時(shí)-空?qǐng)D所示。圖7.17各段時(shí)間不等的流水線結(jié)構(gòu)及時(shí)-空?qǐng)D最大吞吐率取決于流水線中最慢一段所需的時(shí)間，所以該段成為流水線的瓶頸。消除瓶頸的方法有:

(1)細(xì)分瓶頸段。這是一種普遍采用的方法，通過(guò)細(xì)分，使流水線的每一段運(yùn)行時(shí)間盡可能地短、盡可能地一致，從而消除瓶頸段。

(2)重復(fù)設(shè)置瓶頸段 。當(dāng)瓶頸段不便于細(xì)分時(shí)，可以采用重復(fù)設(shè)置瓶頸段(即資源復(fù)用)的方法，如圖7.18所示。圖7.18重復(fù)設(shè)置瓶頸段的流水線結(jié)構(gòu)及時(shí)-空?qǐng)D

2.實(shí)際吞吐率

若流水線由m段組成，完成n個(gè)任務(wù)的吞吐率稱為實(shí)際吞吐率，記作TP。使TP最大化，或使TP接近于TPmax，是流水線實(shí)現(xiàn)中重點(diǎn)要解決的問(wèn)題。假設(shè)流水線各段運(yùn)行時(shí)間相等，為1個(gè)時(shí)鐘周期TCLK，在不出現(xiàn)流水線斷流的情況下(如圖7.16(a)所示)，完成n個(gè)任務(wù)所用時(shí)間為

(7-5)

實(shí)際吞吐率為

(7-6)假設(shè)流水線各段時(shí)間不等，第i段時(shí)間為τi，如圖7.17所示，則完成n個(gè)任務(wù)所用時(shí)間為

(7-7)

實(shí)際吞吐率為

(7-8)由式(7-6)和式(7-8)可看出，當(dāng)n很大時(shí)，TP趨近于TPmax，這說(shuō)明流水技術(shù)適合于實(shí)現(xiàn)大量重復(fù)的時(shí)序過(guò)程。

對(duì)于指令流水線而言，吞吐率TP就是每秒執(zhí)行的指令數(shù)，所以也可以用MIPS指標(biāo)表示吞吐率，即

(7-9)其中，fCLK是流水線的時(shí)鐘頻率，以MHz為單位;CPI和MIPS可以通過(guò)運(yùn)行基準(zhǔn)程序來(lái)測(cè)試確定。對(duì)于單流水線計(jì)算機(jī)系統(tǒng)，因?yàn)?/p>

所以

由于超標(biāo)量計(jì)算機(jī)系統(tǒng)使用多條流水線同時(shí)執(zhí)行幾條指令流，其CPI＜1，所以TPmax＞fCLK。7.4.3加速比

若流水線為m段，加速比S定義為非流水線執(zhí)行時(shí)間T(1)與等功能的流水線執(zhí)行時(shí)間T(m)之比，即

(7-10)

若每段運(yùn)行時(shí)間均為τ，在不流水情況下，完成n個(gè)任務(wù)所需時(shí)間為在流水但不出現(xiàn)斷流的情況下，完成n個(gè)任務(wù)所需時(shí)間為

所以

(7-11)對(duì)于指令流水線而言，當(dāng)加速比S作為指令數(shù)n的函數(shù)時(shí)，則理論上有

(7-12)

當(dāng)加速比S作為指令流水線級(jí)數(shù)m的函數(shù)時(shí)，則理論上有

(7-13)7.4.4效率

效率指流水線的設(shè)備利用率。由于流水線有通過(guò)(填充)時(shí)間和排空時(shí)間，所以流水線的各段并非一直滿負(fù)荷工作，效率E<1。假設(shè)流水線各段運(yùn)行時(shí)間相等為τ，各段效率ei也相等，即

則整個(gè)流水線效率E為

(7-14)

當(dāng)n>>m時(shí)，E≈1。從時(shí)-空?qǐng)D上看，效率就是n個(gè)任務(wù)所占的時(shí)空區(qū)與m個(gè)段總的時(shí)空區(qū)之比。根據(jù)這個(gè)定義，可以計(jì)算流水線各段時(shí)間不等時(shí)的流水線效率為

(7-15)7.4.5吞吐率、加速比和效率的關(guān)系

由式(7-11)、(7-12)和式(7-14)可得:

(7-16)

即效率是實(shí)際加速比S與最大加速比m之比。由式(7-6)和式(7-14)可得:

(7-17)

當(dāng)τ不變時(shí)，流水線的效率E與吞吐率TP呈正比。為提高效率E而采取的措施，也有助于提高吞吐率TP。由式(7-16)和式(7-17)可得:

(7-18)

當(dāng)m和τ不變時(shí)，流水線的加速比S與吞吐率TP呈正比，提高加速比S，有助于提高吞吐率TP。7.4.6流水線性能分析

例7.1某處理器中，浮點(diǎn)加法器采用4級(jí)流水線實(shí)現(xiàn)，流水線示意圖如圖7.7和圖7.19(a)所示，每級(jí)處理時(shí)間為

250ps。請(qǐng)確定:

(1)該浮點(diǎn)加法器計(jì)算100組數(shù)據(jù)采用非流水和流水處理所用時(shí)間各是多少？

(2)采用流水處理的加速比是多少？

(3)采用流水處理的最大吞吐率是多少？圖7.19浮點(diǎn)加法流水線及時(shí)-空?qǐng)D

解采用非流水處理所用的時(shí)間為

Tn(1)=nmτ=100×4×250ps=100ns

采用流水處理的時(shí)-空?qǐng)D如圖7.19(b)所示，所用時(shí)間為

Tn(m)=mτ+(n－1)τ=(4+100－1)×250ps=25.75ns

加速比為

最大吞吐率為

例7.2某指令流水線由10級(jí)構(gòu)成，每級(jí)處理時(shí)間為

100ps?，F(xiàn)要執(zhí)行一段程序，該程序由50個(gè)結(jié)構(gòu)相同、順序執(zhí)行的小程序段組成，每個(gè)小程序段由15條指令構(gòu)成，其中第4條指令I(lǐng)4為條件跳轉(zhuǎn)指令，當(dāng)條件為真時(shí)程序跳轉(zhuǎn)到指

令I(lǐng)10，當(dāng)條件為假時(shí)程序順序執(zhí)行。請(qǐng)計(jì)算:

(1)當(dāng)所有條件跳轉(zhuǎn)指令均未發(fā)生條件跳轉(zhuǎn)時(shí)，執(zhí)行這段程序時(shí)流水線的實(shí)際吞吐率、加速比、效率各是多少？

(2)當(dāng)所有條件跳轉(zhuǎn)指令均發(fā)生條件跳轉(zhuǎn)時(shí)，執(zhí)行這段程序時(shí)流水線的實(shí)際吞吐率、加速比、效率又是多少？

解

(1)此時(shí)流水線的工作狀況可參考圖7.16(a)，因條件跳轉(zhuǎn)未發(fā)生，所以50個(gè)小程序段中的所有指令順序地在流水線上不斷流地執(zhí)行，所用時(shí)間為

實(shí)際吞吐率為加速比為

效率為

(2)因發(fā)生了條件跳轉(zhuǎn)，所以在執(zhí)行50個(gè)小程序段時(shí)，

每個(gè)小程序段只執(zhí)行10條指令，且流水線會(huì)出現(xiàn)50次斷流，每次斷流時(shí)，流水線要進(jìn)行重新填充操作，填充時(shí)間為

(m－1)×τ，此時(shí)流水線的工作狀況可參考圖7.16(b)，故完成規(guī)定程序所用的時(shí)間為

實(shí)際吞吐率為加速比為

效率為

(3)比較(1)、(2)兩種情形下的計(jì)算結(jié)果，可以清楚地看到，流水線一旦出現(xiàn)斷流，其性能將產(chǎn)生明顯的下降?！疤畛洹?、“停頓/拖延”對(duì)流水線來(lái)說(shuō)均是壞消息。

例7.3某指令流水線由5個(gè)功能單元構(gòu)成，其運(yùn)行時(shí)間分別為200ps、100ps、200ps、200ps、100ps。若流水線各段采用同步時(shí)鐘推進(jìn)，其總額外開銷為50ps，流水線額外開

銷包括流水緩沖寄存器的延遲(建立時(shí)間和傳輸延遲)以及時(shí)鐘偏移等。該指令流水線的加速比是多少？

解

例7.4某指令流水線各流水段的執(zhí)行時(shí)間分別為

IF:10ns;ID:8ns;ALU:10ns;MEM:10ns;WB:7ns

已知流水線級(jí)間緩沖延遲為1ns，求該指令流水線的加速比。

解在非流水線上，

平均指令執(zhí)行時(shí)間=10+8+10+10+7=45ns

在流水線上，

平均指令執(zhí)行時(shí)間=流水段最長(zhǎng)的執(zhí)行時(shí)間+級(jí)間緩沖延遲

=10+1=11ns

例7.5某指令流水線結(jié)構(gòu)如圖7.17(a)所示，在流水線不斷流的情況下，分析該流水線的吞吐率和加速比。

解由于流水線各段運(yùn)行時(shí)間不同，假設(shè)可以采用異步方式控制，即流水線各段的推進(jìn)可以按照各段運(yùn)行時(shí)間進(jìn)行控制，則流水線工作的時(shí)空狀態(tài)如圖7.20所示。由于最慢運(yùn)行段S3的限制，使得S1、S2段不能及時(shí)向前推進(jìn)，到執(zhí)行第

4條指令開始，對(duì)流水線各段推進(jìn)的控制已出現(xiàn)規(guī)律性，該

規(guī)律正是圖7.17(b)時(shí)-空?qǐng)D所描述的流水線各段的時(shí)鐘控制

規(guī)律。圖7.20圖7.17(a)流水線時(shí)-空?qǐng)D的另一種表示若流水線各段按照這種規(guī)律進(jìn)行異步推進(jìn)，則流水線達(dá)到穩(wěn)定時(shí)，一條指令執(zhí)行需要12個(gè)時(shí)鐘周期，每3個(gè)時(shí)鐘周期產(chǎn)生一條指令的處理結(jié)果，所以該流水線的性能為該流水線的CPI=3，沒(méi)有達(dá)到CPI=1(即每個(gè)時(shí)鐘周期輸出一個(gè)指令結(jié)果)的理想狀態(tài)。我們把CPI=1的指令流水線稱為指令的單周期實(shí)現(xiàn)，把CPI＞1的指令流水線稱為指令的多

周期實(shí)現(xiàn)。

如果對(duì)圖7.17(a)流水線采用同步方式控制，即流水線各段的推進(jìn)同時(shí)進(jìn)行，則取控制時(shí)鐘TC為

TC=3TCLK這樣，當(dāng)流水線達(dá)到穩(wěn)定時(shí)，一條指令執(zhí)行需要m×(3TCLK)=15個(gè)時(shí)鐘周期，但仍然是每3個(gè)時(shí)鐘周期(即

一個(gè)控制時(shí)鐘)產(chǎn)生一條指令的處理結(jié)果，所以此時(shí)流水線

的性能不變，即

也就是說(shuō)，流水線采用異步控制并沒(méi)有給流水線性能帶來(lái)改善，反而會(huì)增加控制電路的復(fù)雜性。所以，流水線采用的基本控制方式為同步方式。同步控制與異步控制的差別還在于填充時(shí)間的不同和一條指令執(zhí)行時(shí)間的不同。即

7.5指令流水線的性能提高

7.5.1流水線的基本性能問(wèn)題

從前述可知，流水線并不能減少單條指令的執(zhí)行時(shí)間，而且由于流水線段間存在緩沖寄存器的傳輸延遲、附加控制和時(shí)鐘偏移帶來(lái)的額外開銷時(shí)間，一般還會(huì)增加單條指令的執(zhí)行時(shí)間。流水線中的相關(guān)是指相鄰或相近的兩條指令因存在某種關(guān)聯(lián)，后一條指令不能在原指定的時(shí)鐘周期開始執(zhí)行。相關(guān)或冒險(xiǎn)有三類:

(1)結(jié)構(gòu)(Structural)相關(guān)。當(dāng)硬件資源滿足不了同時(shí)重疊執(zhí)行指令的要求而發(fā)生資源沖突時(shí)，出現(xiàn)結(jié)構(gòu)相關(guān)。

(2)數(shù)據(jù)(Data)相關(guān)。當(dāng)一條指令需要用到前面某條指令的結(jié)果，從而不能重疊執(zhí)行時(shí)，發(fā)生數(shù)據(jù)相關(guān)。

(3)控制(Control)相關(guān)。當(dāng)流水線遇到分支等轉(zhuǎn)移類指令或其他能夠改變PC值的指令時(shí)，產(chǎn)生控制相關(guān)。有停頓的流水線的CPI為

(7-19)

理想流水線CPI是指流水線能達(dá)到的最大性能，即理想CPI=1。通過(guò)減小式(7-19)右邊各項(xiàng)停頓值，可以將總的流水線CPI減小，或IPC(每時(shí)鐘周期指令數(shù)量)提高。

有停頓的流水線的加速比為

(7-20)7.5.2結(jié)構(gòu)相關(guān)

有兩種情形會(huì)導(dǎo)致結(jié)構(gòu)相關(guān):

(1)部分功能單元沒(méi)有充分流水，造成使用該單元的指令不能按照預(yù)定的節(jié)拍向前流水。解決的方法就是將流水線設(shè)計(jì)得更合理,使每一流水段運(yùn)行時(shí)間盡可能均衡。

(2)資源沖突(ResourceConflicts)。資源沖突主要出現(xiàn)在指令級(jí)并行機(jī)制中。

①增加資源副本。

②改變資源以便它們能并發(fā)使用。

③通過(guò)延遲(或暫停)流水線的沖突段或在沖突段插入流水線氣泡(氣泡在流水線中只占資源不做實(shí)際操作)，使各段“輪流”使用資源。7.5.3數(shù)據(jù)相關(guān)

1.相關(guān)類型

典型的數(shù)據(jù)相關(guān)有寫后讀(RAW)、讀后寫(WAR)和寫

后寫(WAW)，如圖7.21所示。假設(shè)兩條指令i和j，i先進(jìn)入

流水線。

(1)寫后讀相關(guān)。

(2)讀后寫相關(guān)。

(3)寫后寫相關(guān)。圖7.21典型的數(shù)據(jù)相關(guān)類型

2.解決方法

有幾種方法處理流水線中數(shù)據(jù)相關(guān)帶來(lái)的沖突:

(1)采用直通(Forwarding)技術(shù)。

(2)增加專用硬件。

(3)利用編譯器。圖7.22采用直通技術(shù)的流水線7.5.4控制相關(guān)

1.凍結(jié)(Freeze)流水線

早期的流水線CPU采用最簡(jiǎn)單的凍結(jié)流水線的方法處理分支指令。

2.預(yù)取分支目標(biāo)(PrefetchBranchTarget)

當(dāng)條件分支指令被識(shí)別時(shí)，除了緊隨其后的指令外，分支目標(biāo)也被預(yù)取，并保存到分支指令被執(zhí)行。如果分支跳轉(zhuǎn)發(fā)生，已預(yù)取到的目標(biāo)指令可立刻執(zhí)行。IBM360/91采用這種方法。

3.多流(MultipleStreams)

有些系統(tǒng)采用在條件分支的兩路上同時(shí)啟動(dòng)取指令操作，并將指令保存到分支指令被實(shí)際執(zhí)行時(shí)。分支指令執(zhí)行時(shí)，“真”的執(zhí)行通路即刻可以獲得。這種方法是對(duì)預(yù)取分支目標(biāo)的發(fā)展，在IBM370/168和IBM3033中采用。

4.循環(huán)緩沖器(LoopBuffer)

循環(huán)緩沖器是一個(gè)小的、非常高速的存儲(chǔ)器，它保存著最近獲取的n條順序指令，由流水線的取指段維護(hù)。如果分支發(fā)生，硬件首先檢查分支目標(biāo)是否在緩沖器中。如果在，

則下一條指令從緩沖器中獲取。循環(huán)緩沖器有以下好處:

(1)由于采用了預(yù)取方式，循環(huán)緩沖器將順序地保存現(xiàn)行指令及其后的一些指令。

(2)如果循環(huán)緩沖器有一定的容量，且目標(biāo)地址僅僅是在分支指令之后的幾個(gè)單元處，則當(dāng)分支發(fā)生時(shí)，目標(biāo)將已在緩沖器中。這點(diǎn)對(duì)于常見的if-then和if-then-else語(yǔ)句有利。

(3)這個(gè)策略特別適合處理循環(huán)或重復(fù)操作，所以稱為循環(huán)緩沖器。如果循環(huán)緩沖器大到足以容納一個(gè)循環(huán)中的全部指令，那么，循環(huán)中的指令僅需從內(nèi)存中讀出一次，可以大

大加快取指令的速度。

5.分支預(yù)測(cè)(BranchPrediction)

1)靜態(tài)分支預(yù)測(cè)(StaticBranchPrediction)

(1)預(yù)測(cè)分支不會(huì)發(fā)生(PredictNeverTaken)。

(2)預(yù)測(cè)分支總是發(fā)生(PredictAlwaysTaken)。

(3)由編譯器預(yù)測(cè)。

(4)測(cè)試法(Profiling)。

2)動(dòng)態(tài)分支預(yù)測(cè)(DynamicBranchPrediction)

動(dòng)態(tài)分支預(yù)測(cè)通過(guò)記錄分支指令的近期運(yùn)行歷史，并以此作為預(yù)測(cè)的依據(jù)來(lái)提高分支預(yù)測(cè)的準(zhǔn)確度。

(1)分支歷史表(BranchHistoryTable)。

分支歷史表也稱為分支預(yù)測(cè)緩存(Branch-predictionBuffer)，是由CPU維護(hù)的、由分支指令低位地址索引的一個(gè)小存儲(chǔ)器，用來(lái)記錄分支指令在最近一次執(zhí)行中是否發(fā)生了轉(zhuǎn)移。圖7.23分支歷史表圖7.24用于分支預(yù)測(cè)的2位有限狀態(tài)機(jī)

(2)分支歷史移位寄存器(BranchHistoryShiftRegister)。

這種方法又稱相關(guān)預(yù)測(cè)(CorrelatingPredictor)或雙級(jí)預(yù)測(cè)(Two-levelPredictor)，它利用分支歷史移位寄存器中的k位數(shù)據(jù)記錄前k個(gè)條件分支指令的情況，而不管它們的指令類

型?？梢酝ㄟ^(guò)將轉(zhuǎn)移地址的低位和k位的全局歷史相拼接，實(shí)現(xiàn)對(duì)歷史表的編址。移位寄存器將并行地和歷史表中的k位主鍵進(jìn)行比較，如果匹配，就使用找到的預(yù)測(cè)。

6.延遲分支(DelayedBranch)

這種方法是利用編譯器對(duì)指令代碼進(jìn)行重新排序，或在分支指令之后插入有用指令或空(NOP)操作指令，使分支延遲發(fā)生時(shí)流水線盡可能保持