流水線技術(shù)

流水段分支指令操作IFIDEXIF/ID.IR←

Mem[PC];IF/ID.NPC,PC←

(ifID/EX.cond{ID/EX.NPC}else{PC+4});ID/EX.A←Regs[IF/ID.IR6..10];ID/EX.B←Regs[IF/ID.IR11..15];

ID/EX.NPC←IF/ID.NPC+(IR16)16##IR16..31;

ID/EX.IR←IF/ID.IR;ID/EX.cond

←(Regs[IF/ID.IR6..10]op0;

ID/EX.Imm

←(IR16)16##IR16..31;MEMWB表3.6改進(jìn)后流水線的分支操作調(diào)度策略對(duì)調(diào)度的要求什么情況下起作用？從前調(diào)度從目標(biāo)處調(diào)度從失敗處調(diào)度必須保證在分支失敗時(shí)執(zhí)行被調(diào)度

的指令不會(huì)導(dǎo)致錯(cuò)誤。有可能需要

復(fù)制指令。被調(diào)度的指令必須與分支無關(guān)必須保證在分支成功時(shí)執(zhí)行被調(diào)度

的指令不會(huì)導(dǎo)致錯(cuò)誤。任何情況

分支成功時(shí)(但由于復(fù)制指令，有

可能會(huì)增大程序空間) 分支失敗時(shí)三種方法的要求及效果表3.7各種減少分支損失方法的效果調(diào)度方法每條分支指令的

平均分支損失暫停流水線預(yù)測分支成功預(yù)測分支失敗1.00每條條件分支指

令的分支損失延遲分支每條無條

件分支指

令的損失因分支暫停造成的實(shí)際CPI整型

平均浮點(diǎn)

平均整型

平均整型

平均浮點(diǎn)

平均浮點(diǎn)

平均1.001.000.620.251.001.001.001.001.000.690.211.001.171.151.001.171.150.741.121.110.701.000.350.000.301.041.04流水段功能部件描述A浮點(diǎn)加法器尾數(shù)加流水段D浮點(diǎn)除法器除法流水段E浮點(diǎn)乘法器例外測試段M浮點(diǎn)乘法器乘法器第一個(gè)流水段N浮點(diǎn)乘法器乘法器第二個(gè)流水段R浮點(diǎn)加法器舍入段S浮點(diǎn)加法器操作數(shù)移位段U

展開浮點(diǎn)數(shù)浮點(diǎn)指令延遲初始化間隔使用的流水段加、減43U,S+A,A+R,R+S乘84U,E+M,M,M,M,N,N+A,R除3635U,A,R,D28,D+A,D+R,D+A,D+R,A,R求平方根112111U,E,(A+R)108,A,R取反21U,S求絕對(duì)值21U,S浮點(diǎn)比較32U,A,R

基準(zhǔn)程序流水線CPI載入暫停時(shí)鐘周期數(shù)分支暫停時(shí)鐘周期數(shù)浮點(diǎn)結(jié)果暫停時(shí)鐘周期數(shù)浮點(diǎn)結(jié)構(gòu)性暫停時(shí)鐘周期數(shù)compresseqntottespressogccli整數(shù)平均1.201.881.421.561.641.540.140.270.070.130.180.160.060.610.350.430.460.380.000.000.000.000.000.000.000.000.000.000.000.00doducmdljdp2earhydro2dsu2cor浮點(diǎn)平均2.842.662.172.532.182.480.010.010.000.000.020.010.220.310.460.620.070.331.391.200.590.750.840.950.220.150.120.170.260.18總平均2.000.100.360.460.093.1 流水線的基本概念3.1.1基本概念

1.產(chǎn)品生產(chǎn)流水線

下面通過一個(gè)例子來說明流水線的好處:

一種方案：

另一種方案：流水線生產(chǎn)過程的抽象描述:這種流水工作方式的主要特點(diǎn):

每件產(chǎn)品還是要經(jīng)過4道工序處理，從單件產(chǎn)品角度來看，加工時(shí)間并沒有改變，但從多件產(chǎn)品角度來看，由于4道工序在同時(shí)進(jìn)行，處理速度提高4倍。指令流水線:把指令的解釋過程分解為“分析”和“執(zhí)行”

兩個(gè)子過程，并讓這兩個(gè)子過程分別用獨(dú)立的分

析部件和執(zhí)行部件來實(shí)現(xiàn)。

理想情況：速度提高一倍指令流水線:浮點(diǎn)加法流水線把浮點(diǎn)加法的全過程分解為“求階差”、“對(duì)

階”、“尾數(shù)相加”、“規(guī)格化”四個(gè)子過程，并讓

它們分別用各自獨(dú)立的部件來實(shí)現(xiàn)。

理想情況：速度提高3倍浮點(diǎn)加法流水線時(shí)－空?qǐng)D:時(shí)－空?qǐng)D從時(shí)間和空間兩個(gè)方面描述了流水

線的工作過程。時(shí)－空?qǐng)D中，橫坐標(biāo)代表時(shí)間，

縱坐標(biāo)代表流水線的各個(gè)段。流水技術(shù)

流水技術(shù)是指：將一個(gè)重復(fù)的時(shí)序過程分解

成為若干個(gè)子過程，而每個(gè)子過程都可有效地在

其專用功能段上與其他子過程同時(shí)執(zhí)行。(1)

流水過程由多個(gè)相聯(lián)系的子過程組成，每個(gè)

子過程稱為流水線的“級(jí)”或“段”?！岸巍钡臄?shù)

目稱為流水線的“深度”。流水技術(shù)的特點(diǎn)(2)

每個(gè)子過程由專用的功能段實(shí)現(xiàn)；(3)

各個(gè)功能段所需時(shí)間應(yīng)盡量相等，否則，時(shí)間長

的功能段將成為流水線的瓶頸，會(huì)造成流水線的

“堵塞”和“斷流”。這個(gè)時(shí)間一般為一個(gè)時(shí)鐘周期

（拍）；(4)

流水線需要有“通過時(shí)間”（第一個(gè)任務(wù)流出結(jié)果所

需的時(shí)間），在此之后流水過程才進(jìn)入穩(wěn)定工作狀

態(tài)，每一個(gè)時(shí)鐘周期（拍）流出一個(gè)結(jié)果；(5)

流水技術(shù)適合于大量重復(fù)的時(shí)序過程，只有輸入

端能連續(xù)地提供任務(wù)，流水線的效率才能充分發(fā)

揮。3.1.2流水線的分類◆

單功能流水線：只能完成一種固定功能的

流水線。

◆

多功能流水線：流水線的各段可以進(jìn)行不同的

連接，從而實(shí)現(xiàn)不同的功能。

例如：TIASC的多功能流水線1．按功能的多少來分2．按同一時(shí)間內(nèi)各段之間的連接方式來分◆

靜態(tài)流水線：在同一時(shí)刻，流水線的各段只能

按同一種功能的連接方式工作。

在靜態(tài)流水線中，只有當(dāng)輸入是一串相同

的運(yùn)算操作時(shí)，流水的效率才能得到發(fā)揮。◆

動(dòng)態(tài)流水線：在同一時(shí)刻，流水線的各段可以

按不同功能的連接方式工作。

這樣就不是非得相同運(yùn)算的一串操作才能

流水處理。

優(yōu)點(diǎn)：能提高流水線的效率

缺點(diǎn)：會(huì)使流水線的控制變得復(fù)雜3．按照流水線的級(jí)別來分◆

部件級(jí)流水線（運(yùn)算操作流水線）：它是把

處理機(jī)的算術(shù)邏輯部件分段，以便為各種數(shù)

據(jù)類型進(jìn)行流水操作?！?/p>

處理機(jī)級(jí)流水線（指令流水線）：它是把指

令的解釋執(zhí)行過程按照流水方式進(jìn)行處理。

例如，前面把指令解釋過程分解為：

分析和執(zhí)行。

DLX的基本流水線把指令解釋過程分解為：

取指令、指令譯碼、執(zhí)行、訪存、寫回?！?/p>

處理機(jī)間流水線（宏流水線）：它是指由兩個(gè)

以上的處理機(jī)串行地對(duì)同一數(shù)據(jù)流進(jìn)行處理，

每個(gè)處理機(jī)完成一項(xiàng)任務(wù)。4．按照數(shù)據(jù)表示來分◆

向量處理機(jī)：具有向量指令和向量數(shù)據(jù)表示的

處理機(jī)。

例如：TIASC,CRAY-I等◆標(biāo)量處理機(jī)：不具有向量指令和向量數(shù)據(jù)表示，

僅對(duì)標(biāo)量進(jìn)行流水處理的處理機(jī)。

例如：IBM360/91,Amdahl470V/6等5.按照是否有反饋回路來分◆線性流水線：流水線中的各段串行連接，沒

有反饋回路。◆非線性流水線：流水線中的各段除有串行連接

外，還有反饋回路。◆順序流動(dòng)流水線：流水線輸出端任務(wù)流出的順

序與輸入端任務(wù)流入的順序相同?！舢惒搅鲃?dòng)流水線（亂序流水線）：流水線輸出

端任務(wù)流出的順序與輸入端任務(wù)流入的順序

不同。

例如：動(dòng)態(tài)流水線6.按照流動(dòng)是否可以亂序來分3.2 DLX的基本流水線3.2.1DLX的一種簡單實(shí)現(xiàn)非流水線實(shí)現(xiàn)最多用5個(gè)時(shí)鐘周期來實(shí)現(xiàn)一條指令：(1)取指令周期(IF，InstructionFetch)(2)指令譯碼/讀寄存器周期(ID，InstructionDecode)(3)執(zhí)行/有效地址計(jì)算周期(EX，Execution)(4)存儲(chǔ)器訪問/分支完成周期(MEM，MemoryAccess)(5)寫回周期(WB，WriteBack)定義:ADD： 加法器PC： 指令計(jì)數(shù)器NPC： 下一條順序指令計(jì)數(shù)器IR： 指令寄存器A、B： 操作數(shù)臨時(shí)寄存器Imm： 立即數(shù)臨時(shí)寄存器Cond： 條件值寄存器MUX： 多路開關(guān)ALU： 運(yùn)算器ALUOutput：運(yùn)算器輸出寄存器LMD： 存儲(chǔ)器數(shù)據(jù)讀取寄存器時(shí)鐘周期說明：（1）取指令周期（IF）

IR←Mem[PC]

NPC←PC＋4（2）指令譯碼/讀寄存器周期（ID）

操作碼譯碼

A←Regs[IR6

..10]

B←Regs[IR11

..15]

Imm←(IR16)16##IR16

..31

指令譯碼和讀寄存器是并行進(jìn)行的。之所

以能做到這一點(diǎn)，是因?yàn)樵贒LX指令格式中，

操作碼在固定位置。這種技術(shù)也稱為固定字段

譯碼?！舸鎯?chǔ)器訪問

ALUOutput←A＋I(xiàn)mm

圖示

◆寄存器―寄存器ALU操作

ALUOutput←AopB

圖示

◆寄存器―立即值A(chǔ)LU操作

ALUOutput←AopImm

圖示

◆分支操作

ALUOutput←NPC＋I(xiàn)mm

Cond←(Aop0) 圖示（3）執(zhí)行/有效地址計(jì)算周期（EX）

在這個(gè)周期，不同的指令有不同的操作。上述四種操作都要用到ALU，它們能放在同一個(gè)時(shí)鐘周期中完成的原因：因?yàn)樵贒LX指令集結(jié)構(gòu)中，沒有任何指令需要同時(shí)計(jì)算數(shù)據(jù)的存儲(chǔ)器地址、計(jì)算分支指令的目標(biāo)地址和進(jìn)行ALU數(shù)據(jù)運(yùn)算，也即這樣做是由DLX指令集結(jié)構(gòu)本身的特點(diǎn)所允許的?！舸鎯?chǔ)器訪問

LMD←Mem[ALUOutput]

或

Mem[ALUOutput]←B

圖示

◆計(jì)算下一條指令地址

if（cond）PC←ALUOutput

else

PC←NPC

圖示（5）寫回周期（WB）

不同指令在該周期完成的工作也不一樣?！艏拇嫫鳕D寄存器型ALU指令

Regs[IR16

..20]←ALUOutput

圖示

◆寄存器―立即值型ALU指令

Regs[IR11

..15]←ALUOutput

圖示（4）存儲(chǔ)器訪問/分支完成周期（MEM）◆Load指令

Regs[IR11

..15]←LMD

實(shí)現(xiàn)特點(diǎn)：不同的時(shí)鐘周期之間的數(shù)據(jù)傳遞通過記憶裝置來實(shí)現(xiàn)，這種記憶裝置可以分外部可見與不可見兩類，外部可見記憶裝置包括存儲(chǔ)器、通用寄存器、PC等，用于在指令之間傳遞數(shù)據(jù)；外部不可見記憶裝置為一些臨時(shí)寄存器，包括LMD、Imm、A、B、IR、NPC、ALUOutput以及Cond，用于在一條指令的不同周期之間傳遞數(shù)據(jù)指令周期數(shù):

分支指令和Store指令需要4個(gè)時(shí)鐘周期,

其它指令需要5個(gè)時(shí)鐘周期

假設(shè)分支指令占總指令數(shù)的12％,Store指令占總指令數(shù)的5％則:

CPI＝4.83

上述實(shí)現(xiàn)無論在性能上，還是在硬件開銷上，都不是優(yōu)化的?？赡芨倪M(jìn)：

1)硬件開銷---ADD由ALU來完成;(增加數(shù)據(jù)通路成本)2)改進(jìn)CPI---ALU指令的WB操作放到MEM周期完成;

其它周期的合并.3.2.2基本的DLX流水線

我們可以把3.2.1中的數(shù)據(jù)通路流水化：

每個(gè)時(shí)鐘周期啟動(dòng)一條新的指令。

這樣，該數(shù)據(jù)通路中的每一個(gè)周期就成

了一個(gè)流水段。1.一種簡單的DLX流水線2.簡單DLX流水線的流水過程第一種描述（類似于時(shí)空?qǐng)D）

第二種描述（按時(shí)間錯(cuò)開的數(shù)據(jù)通路資源）3.采用流水技術(shù)還應(yīng)解決好以下幾個(gè)問題：上述簡單DLX流水線中：◆指令存儲(chǔ)器（IM）和數(shù)據(jù)存儲(chǔ)器（DM）分

開，避免了訪存沖突。

◆

ID段和WB段都要訪問同一寄存器文件。

ID段：讀

WB段：寫

如何解決對(duì)同一寄存器的訪問沖突？（1)資源沖突問題

例如，不能要求一個(gè)ALU同時(shí)既做有效

地址計(jì)算，又做減法操作。◆

PC問題

流水線為了能夠每個(gè)時(shí)鐘周期啟動(dòng)一條

新的指令，就必須在每個(gè)時(shí)鐘周期進(jìn)行PC值

的加4操作，并保留新的PC值。這種操作必

須在IF段完成，以便為取下一條指令做好準(zhǔn)

備。

但分支指令也可能改變PC的值，而且是

在MEM段進(jìn)行，這會(huì)導(dǎo)致沖突。

為解決問題，我們重新組織數(shù)據(jù)通路，

把所有改變PC值的操作都放在IF段進(jìn)行。但分支指令如何處理？（2）每一流水段內(nèi)的操作都必須在一個(gè)時(shí)鐘周期

內(nèi)完成◆流水線各段之間需設(shè)置流水線寄存器

（也稱為鎖存器）

◆流水線寄存器組及其所含寄存器的命名

例如，ID段和EX段之間的流水線寄存

器組中的IR寄存器的名稱為:ID/EX.IR

◆流水線寄存器的作用

把數(shù)據(jù)和控制信息從一個(gè)流水段傳

送到下一個(gè)流水段。

◆流水線寄存器的構(gòu)成（3）流水線寄存器（組）流水段任何指令類型ALU指令Load/Store指令分支指令I(lǐng)FIDEXIF/ID.IR←

Mem[PC]IF/ID.NPC,PC←(ifEX/MEM.cond{EX/MEM.ALUOutput}else{PC+4});ID/EX.A←Regs[IF/ID.IR6..10];ID/EX.B←Regs[IF/ID.IR11..15];ID/EX.NPC←IF/ID.NPC;ID/EX.IR←IF/ID.IR;ID/EX.Imm

←(IF/ID.IR16)16##IF/ID.IR16..31;EX/MEM.IR←ID/EX.IR;

EX/MEM.ALUOutput←

ID/EX.AfuncID/EX.B

或

EX/MEM.ALUOutput←

ID/EX.AopID/EX.Imm;

EX/MEM.cond←0;EX/MEM.IR←ID/EX.IR;EX/MEM.ALUOutput←

ID/EX.A+ID/EX.Imm;EX/MEM.cond←0;EX/MEM.B←ID/EX.B;EX/MEM.ALUOutput←

ID/EX.NPC+

ID/EX.Imm;

EX/MEM.cond←

(ID/EX.Aop0);4.DLX流水線的操作流水段任何指令類型ALU指令Load/Store指令分支指令MEMWBMEM/WB.IR←EX/MEM.IR;MEM/WB.ALUOutput←

EX/MEM.ALUOutput;MEM/WB.IR←EX/MEM.IR;MEM/WB.LMD←

Mem[EX/MEM.ALUOutput];

或

Mem[EX/MEM.ALUOutput]←

EX/MEM.B;Regs[MEM/WB.IR16..20]←

MEM/WB.ALUOutput;

或

Regs[MEM/WB.IR11..15]←

MEM/WB.ALUOutput;Regs[MEM/WB.IR11..15]←

MEM/WB.LMD;5．DLX流水線的控制

主要是確定如何控制那四個(gè)多路選擇器:IF段MUX:下一條指令地址為增長后的PC(當(dāng)前PC加4)或向前數(shù)第三條指令的ALUOutput的值,前提是那條指令為分支指令并且條件成立EX段MUX:上面一個(gè)MUX選擇一個(gè)操作數(shù)是寄存器值還是NPC(分支指令),下面一個(gè)MUX選擇另一個(gè)操作數(shù)是寄存器值還是立即數(shù)(I型指令)WB段MUX:寫回寄存器的值來自于LMD(Load指令)或ALUOutput(ALU指令)3.2.3流水線性能分析

吞吐率是指單位時(shí)間內(nèi)流水線所完成的任務(wù)數(shù)或輸出結(jié)果的數(shù)量。1.吞吐率(1)最大吞吐率TPmax

最大吞吐率是指流水線在連續(xù)流動(dòng)達(dá)到穩(wěn)

定狀態(tài)后所得到的吞吐率。

◆若流水線各段的時(shí)間相等，均為△t0

，

則：

TPmax＝1/△t0◆若流水線各段的時(shí)間不等，則：◆最大吞吐率取決于流水線中最慢的一段所

需的時(shí)間，這段就成了流水線的瓶頸?！粝款i的方法(舉例)▲

細(xì)分瓶頸段

▲

重復(fù)設(shè)置瓶頸段(時(shí)-空?qǐng)D)1max{△ti

}TPmax＝─────(2)實(shí)際吞吐率TP

流水線的實(shí)際吞吐率小于最大吞吐率?！舻谝环N情況：各段時(shí)間相等（設(shè)為△t0）

假設(shè)流水線由m

段組成，完成n

個(gè)任務(wù)?！鴷r(shí)空?qǐng)D

▲完成n

個(gè)任務(wù)所需的時(shí)間

T流水＝m△t0＋(n－1)△t0

(說明)

▲實(shí)際吞吐率TP＝───＝──────────T流水nm△t0＋(n－１)△t0n(1＋)△t0

m－11TPmaxn＝────────＝─────1＋nm－1TP＜TPmax

當(dāng)n>>m時(shí)，TP≈TPmax▲時(shí)空?qǐng)D

▲完成n

個(gè)任務(wù)所需的時(shí)間

T流水＝∑△ti＋(n－1)△tj△tj＝max{△ti

}

▲實(shí)際吞吐率◆第二種情況：各段時(shí)間不等TP＝──────────∑△ti＋(n－1)△tjmi=1ni=1m

加速比是指流水線的速度與等功能非流水

線的速度之比。2.加速比S

S＝T非流水／T流水

（其中T流水和T非流水分別為按流水和按非流水

方式處理n

個(gè)任務(wù)所需的時(shí)間）若流水線為m

段，且各段時(shí)間相等，均為

△t0

，則：

T非流水＝nm△t0

(解釋)

T流水＝m△t0＋(n－1)△t0

可以看出：當(dāng)n>>m時(shí)，S≈

mS＝───＝

─────────T非流水T流水nm△t0m△t0＋(n－1)△t0mnm＋n－1mn1＋

m－1＝

────

＝────S＝──────────∑△ti＋(n－1)△tjmi=1n∑△tii=1m若流水線各段的時(shí)間不等，則：效率是指流水線的設(shè)備利用率。

(1)由于流水線有通過時(shí)間和排空時(shí)間，所以

流水線的各段并不是一直滿負(fù)荷地工作。

故：E

＜13．效率E(2)若各段時(shí)間相等，則各段的效率ei相等，即

e1＝e2＝e3＝＝em＝n△t0／T流水

(解釋)

整個(gè)流水線的效率為:當(dāng)n>>m

時(shí)，E

≈1E

＝

───＝

────＝

─────n△t0T流水nm＋n－11n1＋

m－1(3)從時(shí)－空?qǐng)D上看，效率實(shí)際上就是n

個(gè)任務(wù)所

占的時(shí)空區(qū)與m

個(gè)段總的時(shí)空區(qū)之比，即：

n個(gè)任務(wù)占用的時(shí)空區(qū)

E＝━━━━━━━━━━━━━

m個(gè)段總的時(shí)空區(qū)……(4)由于效率E

＝

─────1n1＋

m－1而加速比S＝

─────mn1＋

m－1因此E

＝

──Sm說明效率和加速比成正比又由于吞吐率:TP(1＋)△t0

m－11n＝────────因此E

＝

TP

△t0

說明效率和吞吐率成正比

提高流水線效率所采取的措施對(duì)于提高

吞吐率也有好處。

n個(gè)任務(wù)占用的時(shí)空區(qū)

E＝━━━━━━━━━━━━━

m個(gè)段總的時(shí)空區(qū)(5)若各段時(shí)間不相等，則由于n個(gè)任務(wù)占用的時(shí)空區(qū)=n

而∑△tii=1m

m個(gè)段總的時(shí)空區(qū)=m

T流水

=m[∑△ti

+(n-1)△tj]i=1m因此

E＝━━━━━━━━━━━━━━━

m[∑△ti

+(n-1)△tj]i=1m∑△tii=1m

n4．流水線性能分析舉例例3.1

在靜態(tài)流水線上計(jì)算∑

AiBi

，

求：吞吐率，加速比，效率。4i=1解：(1)確定適合于流水處理的計(jì)算過程。

(2)畫時(shí)空?qǐng)D

(3)計(jì)算性能吞吐率TP＝7／(20△t)

加速比S＝(34△t)／(20△t)＝1.7

效率E＝(4×4＋3×6)／(8×20)＝0.21可以看出，在求解此問題時(shí)，該流水線的效率

不高。

(原因？)例3.3假設(shè)在DLX的非流水實(shí)現(xiàn)和基本流水線中，5個(gè)功能單元的時(shí)間為：10，8，10，10，7（ns），

流水額外開銷為：1ns，求加速比S。解：T非流水＝10＋8＋10＋10＋7＝45(ns)

T流水

＝10＋1＝11(ns)

S＝45／11＝4.1動(dòng)態(tài)流水線的時(shí)－空?qǐng)D

舉例Ⅱ:

這樣行不行？

正確答案5．有關(guān)流水線性能的若干問題(1)流水線并不能減少(而且一般是增加)單條指

令的執(zhí)行時(shí)間，但卻能提高吞吐率。

(2)增加流水線的深度(段數(shù))可以提高流水線的

性能。

(3)流水線的深度受限于流水線的額外開銷。

(4)流水線的額外開銷包括：

◆流水線寄存器的延遲

◆時(shí)鐘扭曲(5)當(dāng)時(shí)鐘周期小到與額外開銷相同時(shí)，流水已沒意

義。因?yàn)檫@時(shí)在每一個(gè)時(shí)鐘周期中已沒有時(shí)間來

做有用的工作。

(6)需用高速的鎖存器來作為流水寄存器。

Earle鎖存器(1965)的三個(gè)特點(diǎn):

◆對(duì)時(shí)鐘扭曲不太敏感（相對(duì)而言）

◆其延遲為常數(shù)：2個(gè)門級(jí)延遲，避免了數(shù)據(jù)通

過鎖存器時(shí)的扭曲。(7)相關(guān)問題

如果流水線中的指令相互獨(dú)立，則可以充分

發(fā)揮流水線的性能。但在實(shí)際中，指令間可能會(huì)

是相互依賴，這會(huì)降低流水線的性能。下一節(jié)介

紹如何解決相關(guān)問題。

◆鎖存器中可以進(jìn)行兩級(jí)邏輯運(yùn)算而不增延遲時(shí)

間。這樣每個(gè)流水段中的兩級(jí)邏輯可以與鎖存

器重疊，從而能隱藏鎖存器開銷的絕大部分。3.3 流水線中的相關(guān)1．相關(guān)的概念

流水線中的相關(guān)是指相鄰或相近的兩條指

令因存在某種關(guān)聯(lián)，后一條指令不能按照原指定的時(shí)鐘周期運(yùn)行?！?/p>

結(jié)構(gòu)相關(guān)

當(dāng)硬件資源滿足不了同時(shí)重疊執(zhí)行的指

令的要求，而發(fā)生資源沖突時(shí)，就發(fā)生了結(jié)

構(gòu)相關(guān)。2．相關(guān)的分類◆數(shù)據(jù)相關(guān)

當(dāng)一條指令需要用到前面某條指令的結(jié)

果，從而不能重疊執(zhí)行時(shí)，就發(fā)生了數(shù)據(jù)相

關(guān)。

◆控制相關(guān)

當(dāng)流水線遇到分支指令和其他能夠改變

PC

值的指令時(shí)，就會(huì)發(fā)生控制相關(guān)。在本章中，我們約定：

當(dāng)一條指令被暫停時(shí)，暫停其后所有指令（包括還未進(jìn)入流水線的指令），但繼續(xù)執(zhí)行在其前的、在流水線中的指令。在暫停期間，流水線不會(huì)取新的指令。

3．消除相關(guān)的基本方法

讓流水線中的某些指令暫停，而讓其它

指令繼續(xù)執(zhí)行。3.3.1結(jié)構(gòu)相關(guān)1.結(jié)構(gòu)相關(guān)的產(chǎn)生原因：因某種指令組合產(chǎn)生資源的訪問沖突。2.解決資源訪問沖突的方法：

(1)把功能部件流水化;

(2)把資源重復(fù)設(shè)置。3.常見的導(dǎo)致結(jié)構(gòu)相關(guān)的原因：

◆功能部件不是全流水

◆重復(fù)設(shè)置的資源的份數(shù)不夠4.結(jié)構(gòu)相關(guān)舉例：訪存沖突解決方法Ⅱ：設(shè)置相互獨(dú)立的指令存儲(chǔ)器和

數(shù)據(jù)存儲(chǔ)器或設(shè)置相互獨(dú)立的

指令Cache和數(shù)據(jù)Cache。

當(dāng)數(shù)據(jù)和指令存在同一存儲(chǔ)器中時(shí)，訪

存指令會(huì)導(dǎo)致訪存沖突。解決辦法Ⅰ：

插入暫停周期

（“流水線氣泡”或“氣泡”）

引入暫停后的時(shí)空?qǐng)D5.避免結(jié)構(gòu)相關(guān)：6.有些設(shè)計(jì)方案允許有結(jié)構(gòu)相關(guān)◆所有功能單元完全流水化

◆設(shè)置足夠的硬件資源

硬件代價(jià)很大?！艚档统杀?/p>

◆減少部件的延遲3.3.2數(shù)據(jù)相關(guān)1.數(shù)據(jù)相關(guān)簡介

當(dāng)指令在流水線中重疊執(zhí)行時(shí)，流水線有

可能改變指令讀/寫操作數(shù)的順序，使之不同

于它們?cè)诜橇魉畬?shí)現(xiàn)時(shí)的順序，這將導(dǎo)致數(shù)據(jù)

相關(guān)。

數(shù)據(jù)相關(guān)舉例2.利用定向技術(shù)減少數(shù)據(jù)相關(guān)引起的暫停

定向技術(shù)的主要思路：在發(fā)生上述數(shù)據(jù)相關(guān)時(shí)，后面的指令并不是馬上就要用到前一條指令的計(jì)算結(jié)果。如果能夠?qū)⒂?jì)算結(jié)果從其產(chǎn)生的地方直接送到需要它的地方，就可以避免暫停；采用定向技術(shù)消除上例中的相關(guān)過程演示定向技術(shù)的實(shí)現(xiàn)：在某一個(gè)功能單元的輸入端和與某一個(gè)功能單元輸出端具有數(shù)據(jù)通路的流水寄存器之間通過多路器建立通路。

當(dāng)定向硬件檢測到前面某條指令的結(jié)果寄存器就是當(dāng)前指令的源寄存器時(shí)，控制邏輯會(huì)開通前面那條指令的結(jié)果目前所在的位置（某個(gè)流水寄存器）到當(dāng)前指令所需的位置（某個(gè)功能單元的輸入端）的通路。不一定是同一個(gè)功能單元，例如：

Load指令

ALU指令DLX中相關(guān)功能單元：

(1)ALU

---結(jié)果可能在EX/MEM和MEM/WB兩個(gè)流水寄存器組的ALUOutput寄存器中。

(2)數(shù)據(jù)存儲(chǔ)器

---結(jié)果可能在MEM/WB流水寄存器組的LMD寄存器中。需要開通的數(shù)據(jù)通路：

ALU輸入端、數(shù)據(jù)存儲(chǔ)器輸入端至EX/MEM和MEM/WB兩個(gè)流水寄存器組中的ALUOutput和LMD寄存器。3.數(shù)據(jù)相關(guān)的分類(2)

寫后寫相關(guān)(WAW)

在i

寫入之前，j

先寫。

最后寫入的結(jié)果是i

的，錯(cuò)誤！

按照指令對(duì)寄存器的讀寫順序，可以將數(shù)據(jù)

相關(guān)分為以下三種類型：

（考慮兩條指令i和j

，假設(shè)i先進(jìn)入流水線）(1)

寫后讀相關(guān)(RAW)

在i

寫入之前，j

先去讀。

j

讀出的內(nèi)容是錯(cuò)誤的。

這是最常見的相關(guān)。①

這種相關(guān)僅出現(xiàn)在這樣的流水線中：◆

流水線中有多個(gè)段可以進(jìn)行寫操作

◆

當(dāng)某條指令在流水線中暫停時(shí)，允許其后

的指令繼續(xù)向前流動(dòng)②DLX整數(shù)流水線中不會(huì)發(fā)生這種相關(guān)

（僅在WB段進(jìn)行寫操作）③若對(duì)DLX作以下修改，則會(huì)發(fā)生WAW相關(guān)：

◆

把ALU操作指令的“寫回”移到MEM段

◆

假設(shè)訪問數(shù)據(jù)存儲(chǔ)器需占用兩拍

舉例(3)讀后寫相關(guān)(WAR)在i

讀之前，j

先寫。

i

讀出的內(nèi)容是錯(cuò)誤的！①

這種相關(guān)僅出現(xiàn)在這樣的流水線中：

有些指令是在流水線的后部讀源操作數(shù)，

而有些指令則是在流水線的前部寫結(jié)果。②DLX流水線中不會(huì)發(fā)生這種相關(guān)；

（讀在先(ID),寫在后(WB)）③這種相關(guān)很少發(fā)生；

（因?yàn)榱魉€一般是先讀操作數(shù)，后寫結(jié)果）。④

復(fù)雜指令可能導(dǎo)致這種相關(guān)。(1)

并非所有的數(shù)據(jù)相關(guān)都可以用定向技術(shù)解決；

舉例

(2)

增加流水線互鎖硬件:

當(dāng)互鎖硬件發(fā)現(xiàn)這種相關(guān)時(shí)，就暫停流水線，直到相關(guān)消失。

舉例：演示A

演示B

4.需要暫停的數(shù)據(jù)相關(guān)5．對(duì)數(shù)據(jù)相關(guān)的編譯調(diào)度方法(1)

流水線中常常會(huì)遇到許多種類型的暫停；

例如，按通常的代碼生成模式，表達(dá)式

A＝B＋C的代碼會(huì)導(dǎo)致暫停(3)

舉例：

例3.6

請(qǐng)為下列表達(dá)式生成沒有暫停的DLX

指令序列：

a＝b＋c；

d＝e－f；

假設(shè)載入延遲為1個(gè)時(shí)鐘周期。

題解(2)

編譯器可以通過重新排列代碼的順序來消

除這種暫停，這種技術(shù)稱為流水線調(diào)度或

指令調(diào)度；

指令發(fā)射(issue)：指令從譯碼段(ID)進(jìn)入

執(zhí)行段(EX)；相應(yīng)的指令稱為已發(fā)射的指令。

(2)DLX整數(shù)流水線中，可以在ID段檢測所有的

數(shù)據(jù)相關(guān)；

若數(shù)據(jù)相關(guān)，則在指令發(fā)射前，讓其暫停。

這樣能減少硬件復(fù)雜度(因?yàn)椴槐貟炱鹨迅淖?/p>

了機(jī)器狀態(tài)的指令）

(3)

至于定向：可以在ID段確定需要什么樣的定向，并

設(shè)置相應(yīng)的控制；也可以在需要用到操作數(shù)的那個(gè)

時(shí)鐘周期檢測并實(shí)現(xiàn)定向；6.對(duì)DLX流水線控制的實(shí)現(xiàn)舉例說明：Load互鎖（由Load指令引起的RAW相關(guān)的互鎖）結(jié)論：是否引起暫停，僅需把Load指令的目的寄存器地址與Load指令后指令的源寄存器地址進(jìn)行比較。當(dāng)檢測到相關(guān)后，控制部件必須在流水線中插入暫停周期，并使IF和ID段中的指令停止前進(jìn)。

▲

將ID/EX中的控制部分清“O”。

▲IF/ID內(nèi)容回送到其自身入口。定向邏輯（有更多的情況要考慮）

如果定向目標(biāo)是ALU輸入：

(1)

比較的一頭是ALU的兩個(gè)輸入，即ID/EX的

IR6..10

和IR11..15

(2)定向源在EX段產(chǎn)生(R-RALU,ALU立即值)

▲結(jié)果在WB段被寫入目標(biāo)寄存器

▲隨后的兩條指令都可以通過定向獲得該結(jié)果

▲比較的另一頭是EX/MEM和MEM/WB的IR11..15

(3)

定向源在MEM段產(chǎn)生(LOAD指令)

▲比較的另一頭是MEM/WB的IR11..15◆所有的定向發(fā)生在：

ALU或DM輸出→ALU輸入，DM輸入，“O”檢測部件3.3.3流水線的控制相關(guān)1.分支指令的執(zhí)行結(jié)果一、分支引起的暫停及減少分支開銷的方法◆轉(zhuǎn)移失?。篜C值加4

◆轉(zhuǎn)移成功：將PC值改變?yōu)檗D(zhuǎn)移目標(biāo)地址

到MEM段的末尾才改變

一旦檢測到分支指令(在ID段)，就暫停

執(zhí)行其后的指令，直到分支指令到達(dá)MEM段，

確定出新的PC值為止。2.處理分支指令最簡單的方法3.減少分支開銷的兩種途徑

在DLX流水線中，分支轉(zhuǎn)移成功導(dǎo)致暫停3個(gè)時(shí)鐘周期。

若分支指令的頻度為30％，理想CPI＝1，則實(shí)際CPI＝1＋30％×3≈2◆

在流水線中盡早判斷分支轉(zhuǎn)移是否成功；

---在分支不成功時(shí)有利；

◆

轉(zhuǎn)移成功時(shí)，盡早計(jì)算出轉(zhuǎn)移目標(biāo)地址。

---在分支成功時(shí)有利；對(duì)于DLX作如下改進(jìn):

(1)把“＝0？”測試移至ID段；二、程序中分支的行為特點(diǎn)(2)在ID段增設(shè)一個(gè)加法器，這樣可以把分支

開銷減少一拍。改進(jìn)后流水線的分支操作

（表3.6）1.各種能改變PC值的指令的執(zhí)行頻度（SPEC基準(zhǔn)程序，DLX上執(zhí)行）

◆

條件分支

整數(shù)程序：14％～15％

浮點(diǎn)程序：3％～12％◆向前分支與向后分支的比：

3∶12．條件分支轉(zhuǎn)移成功的概率◆無條件分支

絕大多數(shù)：≤4％◆平均值

▲整數(shù)程序

向前：13％無條件：4％

向后：3％

▲

浮點(diǎn)程序

向前：7％無條件：1％

向右：3％所有條件分支：67％向前：60％向后：85％（向后分支一般形成循環(huán)）三、減少流水線分支損失的方法（４種簡單的靜態(tài)方法）1.“凍結(jié)”或“排空”流水線

在流水線中停住或刪除分支后的指令，

直到知道轉(zhuǎn)移目標(biāo)地址。優(yōu)點(diǎn)：簡單。2．預(yù)測分支失敗

◆流水線繼續(xù)照常流動(dòng)，就像沒發(fā)生什么似的?！粼谥婪种ЫY(jié)果之前，分支指令后的指令不

能改變機(jī)器狀態(tài)，或者改變了之后能夠回退。

◆若分支失敗，則照常執(zhí)行；否則，從轉(zhuǎn)移目

標(biāo)處開始取指令執(zhí)行。

DLX流水線的處理過程3.預(yù)測分支成功

◆

假設(shè)分支轉(zhuǎn)移成功，并開始從分支目標(biāo)地址

處取指令執(zhí)行。

◆

起作用的前題：先知道分支目標(biāo)地址，后知

道分支是否成功。

◆

對(duì)DLX流水線沒有任何好處。

4.延遲分支(delayedbranch)

(1)

基本概念

把分支開銷為n的分支指令看成是延遲長

度為n的分支指令，其后緊跟有n個(gè)延遲槽。

流水線遇到分支指令時(shí)，按正常方式處理，順

帶執(zhí)行延遲槽中的指令，從而減少分支開銷。

延遲分支以及指令的執(zhí)行順序

(2)

具有一個(gè)分支延遲槽的DLX流水線的執(zhí)行過程

分支延遲槽中的指令“掩蓋”了流水線原來必需插入的暫停周期。(3)

分支延遲指令的調(diào)度（編譯器）

任務(wù)：在延遲槽中放入有用的指令

◆

三種調(diào)度方法

▲

從前調(diào)度（最好）

▲

從目標(biāo)處調(diào)度

▲

從失敗處調(diào)度

◆

這三種方法的要求及效果

◆延遲分支調(diào)度受到的限制

▲對(duì)放入延遲槽的指令有限制

▲編譯器預(yù)測分支是否成功的能力若條件不滿足？---填入NOP指令◆進(jìn)一步改進(jìn)：引入“取消分支”（當(dāng)三種調(diào)度的條件均不滿足時(shí)，預(yù)測一個(gè)方向并填入指令）

若預(yù)測方向正確，正常執(zhí)行延遲槽中的指令；

否則，將之變?yōu)閚o-op指令。

“預(yù)測成功-取消”分支的執(zhí)行過程四、各種分支處理方法的性能1.假設(shè)：

理想CPI＝1

則流水線的加速比為：

S=T非流水/T流水＝D／(1＋C）＝D／(1＋f×p分支)

D

──

流水線的深度C

──

分支引起的流水線暫停時(shí)鐘周期數(shù)

(每條指令的平均值)f

──

分支的出現(xiàn)頻度p分支

──

分支開銷2．DLX流水線中各種分支處理方法的開銷

(表3.7)3.4 流水線計(jì)算機(jī)實(shí)例分析

(MIPSR4000)3.4.1MIPSR4000整型流水線1.指令集：MIPS-3指令集(64位),類似于DLX共8個(gè)段：較深的流水線有利于提高時(shí)鐘頻率。超級(jí)流水與DLX流水線相比：把訪存操作進(jìn)一步分段。

取指令：IF，IS

讀寫數(shù)據(jù)：DF，DS，TC2．MIPSR4000流水線結(jié)構(gòu)3.流水線中各段的功能

4．指令序列在流水線中的重疊執(zhí)行過程5.載入延遲為兩個(gè)時(shí)鐘周期6.指令序列在流水線中的執(zhí)行時(shí)空?qǐng)D

7.R4000流水線的定向路徑比DLX流水線的多

ALU輸入端的定向源有4個(gè)：

EX/DF，DF/DS，DS/TC，TC/WB8.分支處理

◆在EX段完成分支條件的計(jì)算基本分支延遲：3個(gè)時(shí)鐘周期

◆采用單周期延遲分支

◆

預(yù)測分支：失敗分支

◆處理分支指令的時(shí)空?qǐng)D3.4.2MIPSR4000浮點(diǎn)流水線1.R4000浮點(diǎn)部件

◆1個(gè)浮點(diǎn)除法器

◆1個(gè)浮點(diǎn)乘法器

◆1個(gè)浮點(diǎn)加法器2．8個(gè)流水段

(表3.9）

3.R4000浮點(diǎn)流水線是一種多功能非線性流水線

4.雙精度浮點(diǎn)操作指令的延遲、啟動(dòng)間隔以及

流水段的使用情況

（表3.10）3.4.3MIPSR4000流水線的性能分析1.引起流水線暫停的四個(gè)主要原因：

◆

Load暫停：在Load指令后一個(gè)或兩個(gè)時(shí)鐘

周期內(nèi)使用Load的結(jié)果；

◆

分支暫停：分支成功時(shí)的兩個(gè)時(shí)鐘周期的

暫停以及未填或被取消操作的延遲槽；

◆浮點(diǎn)結(jié)果暫停：由于浮點(diǎn)操作數(shù)的RAW相關(guān)

而造成的延遲；

◆

浮點(diǎn)部件結(jié)構(gòu)暫停：為避免浮點(diǎn)部件的沖

突，對(duì)指令發(fā)射的限制而引起的延遲。2．暫停對(duì)R4000流水線CPI的影響

(表3.11)3.5 向量