計算機(jī)系統(tǒng)結(jié)構(gòu)第三章流水線技術(shù)

1

第三章流水線技術(shù)3.1 流水線的基本概念3.2 流水線的時空圖及性能分析3.3 流水線的相關(guān)3.4 MIPSR4000流水線計算機(jī)

3.5流水線處理機(jī)及其設(shè)計23.1流水線的基本概念一．指令的重疊執(zhí)行1.一條指令執(zhí)行的幾個過程段

1）取指令：根據(jù)PC（指令計數(shù)器）從M（存儲器）取出指令送到IR（指令寄存器）

2）譯碼分析：譯出指令的操作性質(zhì)、尋址方式，取操作數(shù)

3）執(zhí)行：對操作數(shù)進(jìn)行處理，主要涉及ALU（算術(shù)邏輯運(yùn)算部件），存結(jié)果3.1.1有關(guān)基本概念32.對指令執(zhí)行的幾種方式

1）串行執(zhí)行只有在前一條指令的各過程段全部完成后，才從存儲器取出下一條指令

取

譯

執(zhí)

取

譯

執(zhí)

i條

i+1條2)僅兩條指令重疊：第i條指令的執(zhí)行與第i+1條的取指重疊。3)三條指令重疊：第i條指令的執(zhí)行與第i+1條的譯碼及第i+2條的取指重疊。i條取譯執(zhí)取譯執(zhí)i+1條i條取譯執(zhí)i+1條取譯執(zhí)i+2條取譯執(zhí)重疊方式并不能加快一條指令的實(shí)現(xiàn)，但能加快一段程序的執(zhí)行。5

3.重疊方式中所需時間表達(dá)式及所需時間計算

1）條件：設(shè)一條指令分為三個過程段，各過程段分別用t取、t譯、t執(zhí)表示。

執(zhí)行n條指令，分別采用順序執(zhí)行、兩條重疊、三條重疊。2）分別列出上述三種執(zhí)行方式所需時間表達(dá)式串行執(zhí)行n*（t取+t譯+t執(zhí)）兩條重疊t取+n*t譯+(n-1)*(t取,t執(zhí))max+t執(zhí)三條重疊t取+(t譯,t取)max+(n-2)*（t取,t譯,t執(zhí)）max+(t執(zhí),t譯)max+t執(zhí)63)例子當(dāng)n=200，t取=3Δt，t譯=4Δt，t執(zhí)=5Δt時，在重疊不停頓情況下，分別計算上述三種執(zhí)行方式的時間。串行執(zhí)行：

200×(3+4+5)=2400Δt

兩條重疊：

3+200×4+(200-1)×5+5=1803Δt2400/1803=1.33三條重疊：

3+4+(200-2)×5+5+5=1007Δt2400/1007=2.387重疊方式需要解決的問題在重疊執(zhí)行時需要解決的主要兩個問題：問題一：為了實(shí)現(xiàn)取指、分析指令、執(zhí)行指令同時進(jìn)行，需要有對應(yīng)的獨(dú)立部件。 問題二：主存訪問沖突。例如，取指令k+1時需訪存，分析指令k時可能也需要取操作數(shù)訪存。解決訪存沖突，可采用:1)指令Cache與數(shù)據(jù)Cache分離；2）指令預(yù)取緩沖器81、指令流水線：利用時間并行性二、流水線定義

下面一條將指令執(zhí)行分為2個階段的流水線，可以進(jìn)一步細(xì)分。

指令流水線是由一系列串聯(lián)的流水段（級）構(gòu)成，每個流水段完成指令的一個操作步驟。各個流水段之間設(shè)置流水線寄存器以暫存上個流水段的處理結(jié)果。9一個6段指令流水線。理想情況：指令序列執(zhí)行速度提高6倍102、浮點(diǎn)加法流水線把流水線技術(shù)應(yīng)用于運(yùn)算的執(zhí)行過程，就形成了運(yùn)算操作流水線，也稱為部件級流水線。把浮點(diǎn)加法的全過程分解為求階差、對階、尾數(shù)相加、規(guī)格化4個子過程。理想情況：速度提高4倍113.1.2流水線的分類

流水線可按不同的觀點(diǎn)進(jìn)行分類，一般來說流水線可以分為以下幾個類型。1、按各過程段用時是否相等分類流水線按各過程段用時是否相等可分為均勻流水線和非均勻流水線兩種。1）均勻流水線指的是各過程段用時全相等的流水線2）非均勻流水線指的是各過程段用時不全相等的流水線122、按處理的數(shù)據(jù)類型1）標(biāo)量流水線：用于對標(biāo)量數(shù)據(jù)進(jìn)行流水處理。2）向量流水線：用于對向量數(shù)據(jù)進(jìn)行流水處理。（向量很適合流水處理）

按處理的數(shù)據(jù)類型可分為標(biāo)量流水處理機(jī)和向量流水處理機(jī)兩種。133.按流水線的規(guī)模按流水線的規(guī)模可分為操作流水線、指令流水線和宏流水線。1）操作流水線是把處理機(jī)的算術(shù)邏輯部件分段，使得各種數(shù)據(jù)類型的操作能夠進(jìn)行流水，規(guī)模最小。2）指令流水線則是把執(zhí)行指令的過程按照流水方式處理。3）宏流水線它是指由兩個以上的處理機(jī)串行地對同一數(shù)據(jù)流進(jìn)行處理，每個處理機(jī)完成一項任務(wù)。144.按功能分類

按流水線完成的功能是否單一，流水線可分為單功能流水線與多功能流水線兩種。1）單功能流水線：只能完成一種固定功能的流水線。2）多功能流水線：流水線的各段可以進(jìn)行不同的連接，以實(shí)現(xiàn)不同的功能。例：ASC的多功能流水線15165.按連接工作方式分類

多功能流水線按連接工作方式可分為靜態(tài)流水線和動態(tài)流水線兩種。1）

靜態(tài)流水線：在同一時間內(nèi)，多功能流水線中的各段只能按同一種功能的連接方式工作。

對于靜態(tài)流水線來說，只有當(dāng)輸入的是一串相同的運(yùn)算任務(wù)時，流水的效率才能得到充分的發(fā)揮。172）動態(tài)流水線：在同一時間內(nèi)，多功能流水線中的各段可以按照不同的方式連接，同時執(zhí)行多種功能。

優(yōu)點(diǎn)靈活，能夠提高流水線各段的使用率，從而提高處理速度。

缺點(diǎn)控制復(fù)雜。18靜、動態(tài)流水線時空圖對比196.按連接方式分類

按照流水線的各個功能段之間是否有反饋信號，可將流水線分為線性流水線和非線性流水線。1）線性流水線：流水線的各段串行連接，沒有反饋回路。數(shù)據(jù)通過流水線中的各段時，每一個段最多只流過一次。2）非線性流水線：流水線中除了有串行的連接外，還有反饋回路20217.其他分類除上述幾種外，流水線分類還有下述幾種。1）根據(jù)控制方式分成順序流水線和亂序流水線。2）在線性流水線中，根據(jù)控制方式還可以分成同步流水線和異步流水線。223.1.3流水線的特點(diǎn)1.流水線處理的最好是連續(xù)任務(wù)，只有連續(xù)不斷的任務(wù)才能充分發(fā)揮流水線的效率。2.流水線依靠多個功能部件并行工作宋縮短程序的執(zhí)行時間，實(shí)際上是把一個大的功能部件分解為多個子過程，如前述將浮點(diǎn)數(shù)加法器分解為4個子過程。3.流水線中的每一功能部件后面都要有一個緩沖寄存器，即所謂的鎖存器，以便平滑各個功能段延時時間的不一致。4.流水線中各段時間應(yīng)盡量相等，避免段延時過長引起的相互等待。5.流水線需要有“裝入時間”和“排空時間”。233.2流水線的時空圖及性能分析一、時空圖時空圖從時間和空間兩個方面描述了流水線的工作過程。時空圖中，橫坐標(biāo)代表時間，縱坐標(biāo)代表流水線的各個段。4段指令流水線的時空圖3.2.1流水線的時空圖243.2.2流水線的性能分析吞吐率：在單位時間內(nèi)流水線所完成的任務(wù)數(shù)量或輸出結(jié)果的數(shù)量。一、吞吐率n：任務(wù)數(shù)Tk：處理完成n個任務(wù)所用的時間251、各段時間均相等的流水線各段時間均相等的流水線時空圖26流水線完成n個連續(xù)任務(wù)所需要的總時間為（假設(shè)一條k段線性流水線）

Tk＝kΔt＋(n-1)Δt＝(k＋n-1)Δt

流水線的實(shí)際吞吐率最大吞吐率27最大吞吐率與實(shí)際吞吐率的關(guān)系流水線的實(shí)際吞吐率小于最大吞吐率，它除了與每個段的時間有關(guān)外，還與流水線的段數(shù)k以及輸入到流水線中的任務(wù)數(shù)n有關(guān)。只有當(dāng)n>>k時，才有TP≈TPmax。

282、各段時間不完全相等的流水線各段時間不等的流水線及其時空圖舉例（時空圖）一條4段的流水線S1，S3，S4各段的時間：ΔtS2的時間：3Δt

（瓶頸段）流水線中這種時間最長的段稱為流水線的瓶頸段。2930各段時間不等的流水線的實(shí)際吞吐率：（Δti為第i段的時間，共有k個段）流水線的最大吞吐率為313、解決流水線瓶頸問題的常用方法1）細(xì)分瓶頸段：例如：對前面的4段流水線把瓶頸段S3細(xì)分為3個子流水線段：S3a，S3b，S3c改進(jìn)后的流水線的最大吞吐率：322)重復(fù)設(shè)置瓶頸段缺點(diǎn)：控制邏輯比較復(fù)雜，所需的硬件增加了。例如：對前面的4段流水線重復(fù)設(shè)置瓶頸段S3：S3a，S3b，S3c33重復(fù)設(shè)置瓶頸段后的時空圖34二、加速比

流水線的加速比（Speedup,S）完成某個任務(wù)順序執(zhí)行所用時間與流水線執(zhí)行所用時間之比。

假設(shè)：不使用流水線（即順序執(zhí)行）所用的時間為Ts，使用流水線后所用的時間為Tk，則該流水線的加速比為351、流水線各段時間相等（都是△t）一條k段流水線完成n個連續(xù)任務(wù)所需要的時間為

Tk=(k＋n-1)Δt順序執(zhí)行n個任務(wù)所需要的時間：

Ts=nk△t流水線的實(shí)際加速比為36各段時間均相等的流水線時空圖37最大加速比當(dāng)n>>k時，S≈k

思考：流水線的段數(shù)愈多愈好？

382、流水線的各段時間不完全相等時一條k段流水線完成n個連續(xù)任務(wù)的實(shí)際加速比為39三、效率

流水線效率（Efficiency，E）是指流水線的設(shè)備利用率。由于流水線有裝入時間與排空時間，在連續(xù)完成n個任務(wù)的時間內(nèi)，每個流水段不是滿負(fù)荷工作的。在時空圖上，流水線的效率是n個任務(wù)的實(shí)際占用面積與k個段和Tk時間圍成的總面積之比。40如果每個流水段時間是△t，且任務(wù)是連續(xù)的實(shí)際效率：最大效率：41舉例計算：S=a0+a1+a2+a3+a4+a5+a6+a7，流水線有5個功能段對相關(guān)算式要合理分解算式——盡量分解為少相關(guān)算式：①S0=a0+a1⑤S4=S0+S1②S1=a2+a3⑥S5=S2+S3③S2=a4+a5⑦S6=S4+S5④S3=a6+a742吞吐率：TP=7/18（1/Δt）效率：E=（作用區(qū)域面積）/（完成運(yùn)算所需時間矩形面積）

=（7*5Δt）/（18Δt*5）=7/18

43例：假設(shè)是靜態(tài)多功能流水線計算A*B=12345aibiA.BA+B=a1.b1+a2.b2+a3.b3+a4.b4441—2—3---5做加法1—4—5做乘法解：分解算式

①S1=a1.b1 ②s2=a2.b2③s3=a3.b3④s4=a4.b4⑤s5=s1+s2⑥s6=s3+s4⑦s7=s5+s645①②③④⑤⑥⑦①②③④⑤⑥⑦⑤⑥⑦①②③④⑤⑥⑦54321012345678910111213141516時間46吞吐率ＴＰ＝（１／△Ｔ）效率＝＝３２％473.3流水線中的相關(guān)3.3.1什么是流水線相關(guān)如果要執(zhí)行算式S=a/b+c，設(shè)a、b、c在存儲器中，要通過下列指令來執(zhí)行。

LDR1,ALDR2,BLDR3,CDIVR1，R1,R2ADDR1,R1，R3；要等DIV結(jié)果

STR1,S；存結(jié)果

第4條指令需要第1、2條指令的結(jié)果才能執(zhí)行；第5條指令需要第3、4條指令的結(jié)果才能執(zhí)行。這就出現(xiàn)了指令因等待前面結(jié)果，使后面沒指令無法繼續(xù)執(zhí)行下去的現(xiàn)象，即指令相關(guān)。48流水線中的相關(guān)主要分為以下3種類型1.結(jié)構(gòu)相關(guān)2.數(shù)據(jù)相關(guān)3.控制相關(guān)493.3.2流水線中的結(jié)構(gòu)相關(guān)（資源相關(guān)）

如果某些指令組合在流水線中重疊執(zhí)行時產(chǎn)生了資源沖突，那么我們稱該流水線有結(jié)構(gòu)相關(guān)。由于訪問同一個存儲器而引起的結(jié)構(gòu)沖突

50對于這種沖突，通常有以下兩種解決方法解決辦法(1)：插入暫停周期，即讓流水線在完成前一條指令對數(shù)據(jù)的存儲器訪問時，暫停其后的指令操作為消除結(jié)構(gòu)沖突而插入的流水線氣泡MREG51解決方法(2)：設(shè)置相互獨(dú)立的指令存儲器和數(shù)據(jù)存儲器或設(shè)置相互獨(dú)立的指令Cache和數(shù)據(jù)Cache

523.3.3流水線中的數(shù)據(jù)相關(guān)如果下面的條件之一成立，則指令j與指令i數(shù)據(jù)相關(guān)：（1）指令j使用指令i產(chǎn)生的結(jié)果

（2）指令j與指令k數(shù)據(jù)相關(guān)，指令k與指令i數(shù)據(jù)相關(guān)，則指令j與指令i數(shù)據(jù)相關(guān)。

第2個條件指出，如果兩條指令之間存在類似上述的相關(guān)鏈，則它們之間也是相關(guān)的。這條相關(guān)鏈甚至可以貫穿整個程序。53

例如：下面這一段代碼存在數(shù)據(jù)相關(guān)。Loop：L.D

F0，0（R1）

//數(shù)組元素送F0

ADD.D

F4，F(xiàn)0，F(xiàn)2

//加上F2中的值

S.D

F4，0（R1） //保存結(jié)果

DADDIU

R1，R1，－8

//數(shù)組指針遞減8個字節(jié)

BNE

R1，R2，Loop

//如果R1≠R2，則分支

54解決數(shù)據(jù)相關(guān)的一般方式：*暫停流水線；*使用相關(guān)專用數(shù)據(jù)通路（提前將結(jié)果提供給后面的指令）；*編譯優(yōu)化調(diào)度（靜態(tài)調(diào)度）；*動態(tài)調(diào)度。553.3.4流水線的控制相關(guān)

控制相關(guān)是指因為程序的執(zhí)行方向可能被改變而引起的相關(guān)?？赡芨淖兂绦驁?zhí)行方向的指令通常有無條件轉(zhuǎn)移、條件轉(zhuǎn)移、子程序調(diào)用、中斷等。無條件轉(zhuǎn)移指令在程序中的使用情況一般如下

k：

k＋1：JMPLk＋2：ADDR1,R2,R3……L：SUB56例如，有條件轉(zhuǎn)移指令的程序：MOVR1，NUMLOOP：…… …… …… DECR1 JGZLOOP；>=0轉(zhuǎn)移

SUB

從相關(guān)的角度看，轉(zhuǎn)移指令或斷點(diǎn)指令與后續(xù)指令之存在著一種相關(guān)，使后續(xù)指令不能同時進(jìn)入流水線執(zhí)行，意味著前者控制了后者，故稱為控制相關(guān)或全局相關(guān)。數(shù)據(jù)相關(guān)也稱為局部相關(guān)。57

控制相關(guān)會引起流水線停頓。減少流水線處理分支指令停頓的思路：*對于條件轉(zhuǎn)移，在流水線中應(yīng)盡早判斷出分支轉(zhuǎn)移的走向；*盡早計算出分支轉(zhuǎn)移的目標(biāo)地址。58*暫停流水線

軟件方法：由編譯器在需要流水線停頓處插入nop指令，去除相關(guān)。硬件方法：由控制相關(guān)信號去控制流水線暫停到相關(guān)解除。解決控制相關(guān)的一般方式：59*延遲轉(zhuǎn)移技術(shù)

例如：

PUSHBX MOVDX，8

ADDAX，CX JGL ┋

L：MOV

將前面1條指令調(diào)到轉(zhuǎn)移指令的后面執(zhí)行，同時也計算轉(zhuǎn)移地址。無論成功與否，上面的1條指令都不需取消。60

SUN公司的SPARC使用上述技術(shù)，分支指令格式中有一位a位。a位用于延遲轉(zhuǎn)移控制，當(dāng)a＝0時，跟在轉(zhuǎn)移指令下面的指令總是被執(zhí)行；當(dāng)a=1時，只在條件轉(zhuǎn)移指令轉(zhuǎn)移成功時，跟在轉(zhuǎn)移指令下面的指令才被執(zhí)行。一般用于單流水線標(biāo)量處理機(jī)中。據(jù)統(tǒng)計，編譯器調(diào)度一條指令成功的概率可達(dá)90%以上。

這是編譯器與硬件支持結(jié)合的方式。61*靜態(tài)轉(zhuǎn)移預(yù)測技術(shù)----處理器的硬件與軟件設(shè)計好后，條件轉(zhuǎn)移預(yù)測的方向已經(jīng)確定了，或者預(yù)測為轉(zhuǎn)移成功方向，或者預(yù)測為轉(zhuǎn)移不成功方向。*動態(tài)轉(zhuǎn)移預(yù)測技術(shù)：根據(jù)近期轉(zhuǎn)移是否成功的歷史記錄來預(yù)測下一次轉(zhuǎn)移的方向。62*提前形成條件轉(zhuǎn)移指令的條件碼

a．在流水線中提前形成條件碼（硬件）

條件轉(zhuǎn)移造成流水線停頓的一個原因是：前面指令形成條件碼太晚。 實(shí)際上，在大多數(shù)情況下，可以在運(yùn)算實(shí)際開始以前或者在運(yùn)算中間就能產(chǎn)生條件碼，不必等到運(yùn)算完成后。63例如：

MULAX，BX JSL

即只要比較兩個操作數(shù)的符號就可形成條件碼，而不必等到指令完成（積結(jié)果產(chǎn)生）。 方法是：在運(yùn)算器的入口處設(shè)置一個比較器，提前形成結(jié)果的符號，即是否為“負(fù)"條件碼。如果比較器能在一個時鐘周期內(nèi)產(chǎn)生條件碼，則正好可以提供給下一條條件轉(zhuǎn)移指令使用，流水線不"斷流"。

Amdahl470V/6計算機(jī)中采用該方法。64b．將產(chǎn)生條件碼的指令提前執(zhí)行

在某些情況下，通過編譯器調(diào)度指令，再設(shè)置一個專門的條件碼寄存器，解決循環(huán)控制問題：例如，有下面的程序：

MOVR1，NUMLOOP：…… …… …… DECR1 JGZLOOP；>=0轉(zhuǎn)移

HALT65

首先，編譯器發(fā)現(xiàn)DECR1指令，并把它上移，同時用LDECR1來替代它。其次，用LJGZLOOP代替JGZLOOP指令：

MOVR1，NUM LOOP：LDECR1；測試R1，產(chǎn)生的條件碼保存在專用的條件碼寄存器CCL中

…… …… …… LJGZLOOP；根據(jù)條件碼CCL決定是否轉(zhuǎn)移

HALT663.4MIPSR4000流水線計算機(jī)MIPS(MicroprocessorwithoutInterlockedPipedStages)4000處理機(jī)屬于超流水線處理機(jī)。3.4.1MIPSR4000流水線計算機(jī)基本結(jié)構(gòu)和工作原理R4000處理器是64位機(jī)，指令系統(tǒng)是32位長度的典型RISC指令集。67SGI公司生產(chǎn)的超流水線處理器MIPSR4000（RISC）：＊兩個Cache：指令Cache

和數(shù)據(jù)Cache，容量均為64KB，數(shù)據(jù)通路寬度為64位。每個主時鐘周期可以訪問Cache兩次。＊整數(shù)部件：32個64位通用寄存器，一個ALU，一個專用乘/除法部件。負(fù)責(zé)取指令，整數(shù)操作譯碼和執(zhí)行，LOAD和STORE操作的執(zhí)行。有相關(guān)專用數(shù)據(jù)通路。＊浮點(diǎn)部件：16個64位或32個32位的通用寄存器。

乘法部件、除法部件、加法/轉(zhuǎn)換/求平方根部件，三個部件可并行操作一、基本結(jié)構(gòu)6869MIPSR4000的流水線有8級，流水線操作如下圖：指令Cache：采用直接映像方式。從Cache中讀出的標(biāo)志要與

TLB得到的指令的存儲器物理地址比較，相等即命中。對命中的非存儲器操作指令，結(jié)果在EX末尾得到。取指令后一半數(shù)據(jù)cache后一半取指令前一半數(shù)據(jù)cache前一半二、工作原理708個流水段的功能：取指令前一半IF：PC內(nèi)容即指令虛擬地址IVA，交指令cache和TLB（TranslationLook-asideBuffer）地址轉(zhuǎn)換旁路緩沖器取指令后一半IS：指令cache送出指令和TLB生成物理地址寄存器堆RF：指令cache標(biāo)志檢查判命中，指令譯碼，相關(guān)檢查；從寄存器取操作數(shù)取指令后一半數(shù)據(jù)cache后一半取指令前一半數(shù)據(jù)cache前一半71728個流水段的功能（續(xù)1）：指令執(zhí)行EX：如是RR指令，ALU完成操作；如是load或store指令，計算數(shù)數(shù)據(jù)虛擬地址DVD；如是轉(zhuǎn)移指令，計算轉(zhuǎn)移目標(biāo)虛擬地址和檢查轉(zhuǎn)移條件取指令后一半數(shù)據(jù)cache后一半取指令前一半數(shù)據(jù)cache前一半73748個流水段的功能（續(xù)2）：數(shù)據(jù)cache前一半DF：數(shù)據(jù)虛擬地址DVA交數(shù)據(jù)cache和TLB數(shù)據(jù)cache后一半DS：數(shù)