計(jì)算機(jī)體系結(jié)構(gòu)（第二版）課件第二章流水線技術(shù)

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)一、重疊執(zhí)行方式的基本結(jié)構(gòu)

1.重疊執(zhí)行方式的基本結(jié)構(gòu)

采用二次重疊執(zhí)行方式，同時(shí)有三條指令分別在取指令、分析和執(zhí)行。要使它們能夠重疊執(zhí)行，處理機(jī)在結(jié)構(gòu)上必須有獨(dú)立的取指令部件、指令分析部件和指令執(zhí)行部件。它們有各自的控制線路，實(shí)現(xiàn)各自的功能，這樣才能取指令、分析和執(zhí)行的同時(shí)進(jìn)行。為此，要把順序執(zhí)行方式中的一個(gè)集中的指令控制器分解成三個(gè)相結(jié)獨(dú)立的控制器，分別是：存儲控制器，簡稱存控；指令控制器，簡稱指控；運(yùn)算控制器，簡稱運(yùn)控。重疊執(zhí)行方式的基本結(jié)構(gòu)如圖所示。一、多條指令的執(zhí)行方式

二、什么是流水線

三、流水線的表示方法四、流水線的分類五、流水線的特點(diǎn)

第一節(jié)流水線的基本概念

第一節(jié)流水線的基本概念

一、多條指令的執(zhí)行方式

一條指令的執(zhí)行過程可以分為多個(gè)階段，通常分為取指令、分析指令、執(zhí)行指令三個(gè)階段。假設(shè)三個(gè)階段所需要的時(shí)間均為t。（1）順序方式。順序執(zhí)行方式是指在任何時(shí)刻，處理機(jī)中只有一條指令在執(zhí)行。執(zhí)行n條指令所需要的時(shí)間為T=3nt。控制簡單，節(jié)省設(shè)備。執(zhí)行指令速度慢，功能部件利用率低。（2）一次重疊方式。一次重疊執(zhí)行方式是指在任何時(shí)刻，處理機(jī)中至多只有二條指令在同時(shí)執(zhí)行。執(zhí)行n條指令所需要的時(shí)間為T=(2n+1)t。時(shí)間縮短近一半，功能部件利用率高。需要增加一些硬件，控制過程也復(fù)雜一些。（3）二次重疊方式。二次重疊執(zhí)行方式是指在任何時(shí)刻，處理機(jī)中至多可以有三條指令在同時(shí)執(zhí)行。執(zhí)行n條指令所需要的時(shí)間為T=(n+2)t。時(shí)間縮短了近2/3，提高指令的執(zhí)行速度。付出更高的代價(jià)。取指k分析k執(zhí)行k取指k+1分析k+1執(zhí)行k+1取指k分析k執(zhí)行k取指k+1分析k+1執(zhí)行k+1取指k+2分析k+2執(zhí)行k+2取指k分析k執(zhí)行k取指k+1分析k+1執(zhí)行k+1取指k+2分析k+2執(zhí)行k+2順序執(zhí)行方式

一次重疊執(zhí)行方式

二次重疊執(zhí)行方式

第一節(jié)流水線的基本概念二、什么是流水線

計(jì)算機(jī)中的流水線與工廠中的生產(chǎn)流水線十分相似，它是指把一個(gè)重復(fù)的過程分解為若干個(gè)子過程，一個(gè)過程的子過程可以與其它過程的不同的子過程并行進(jìn)行，實(shí)現(xiàn)不同過程在時(shí)間上重疊進(jìn)行的工作方式。實(shí)現(xiàn)流水線的技術(shù)方法稱為流水線技術(shù)。從本質(zhì)上講，流水線技術(shù)是一種時(shí)間并行技術(shù)，是通過時(shí)間重疊的技術(shù)途徑實(shí)現(xiàn)并行處理（時(shí)間并發(fā)性）。根據(jù)子過程劃分，相應(yīng)的流水線也要?jiǎng)澐殖鱿鄳?yīng)的段，每一個(gè)段稱為流水節(jié)拍、流水步、流水步驟、流水階段、流水段、功能段等。一個(gè)流水階段與另外一個(gè)流水階段相連接形成流水線。過程從流水線的一端進(jìn)入，經(jīng)過流水線的處理，從流水線的另一端進(jìn)出。流水線技術(shù)是一種非常經(jīng)濟(jì)而又有效的技術(shù)，已成為計(jì)算機(jī)中普遍使用的一種并行處理技術(shù)。采用流水線技術(shù)只需要增加少量的硬件，就能夠把處理機(jī)的運(yùn)算速度提高幾倍。

第一節(jié)流水線的基本概念

第一節(jié)流水線的基本概念

流水線的表示方法有三種：連接圖、時(shí)空圖和預(yù)約表，其中時(shí)空圖用于表示線性流水線，預(yù)約表用于表示非線性流水線，而連接圖則均可表示。

1.連接圖

四個(gè)流水段的指令流水線的連接圖如圖所示，其實(shí)質(zhì)是將帶執(zhí)行時(shí)間的各流水段按照流水線的執(zhí)行順序從左到右排列，并用帶箭頭的直線把它們連接起來。

2.時(shí)空圖

時(shí)空圖是一種最常用、能直觀描述線性流水線工作過程的表示方法，四個(gè)流水段的指令流水的時(shí)空圖如圖所示。其實(shí)質(zhì)是利用平面直角坐標(biāo)系的第一象限。橫坐標(biāo)表示時(shí)間，即是輸入到流水線的各個(gè)任務(wù)在流水線中所經(jīng)過的時(shí)間。縱坐標(biāo)表示空間，即流水線的每一個(gè)流水段。三、流水線的表示方法線性指令流水線的連接圖

非線性指令流水線的連接圖

取指令譯碼執(zhí)行保存結(jié)果取指令譯碼執(zhí)行保存結(jié)果12345123451234512345四功能段指令流水線時(shí)空圖

第一節(jié)流水線的基本概念

第一節(jié)流水線的基本概念3.預(yù)約表

預(yù)約表是一種最常用、能直觀描述某過程非線性流水線工作狀態(tài)的表示方法，四個(gè)流水段的指令流水線的預(yù)約表如圖3.4所示。其實(shí)質(zhì)是利用一張表，行表示時(shí)間即非線性流水線的段數(shù)，列表示空間既任務(wù)通過非線性流水線的時(shí)間，表中用“×”表示行對應(yīng)流水段在列對應(yīng)時(shí)間段要被使用。一行中可以有多個(gè)“×”，表明同一個(gè)任務(wù)在不同時(shí)間重復(fù)使用了同一個(gè)流水段；一列中有多個(gè)“×”則表明任務(wù)在同一時(shí)間使用了多個(gè)流水段?！痢痢痢痢?/p>

四功能段非線性指令流水線預(yù)約表

第一節(jié)流水線的基本概念

四、流水線的分類

從不同的角度，可以把流水線分成多種不同類型，以反映流水線在某一方面的結(jié)構(gòu)、特點(diǎn)或性能。

1.按流水線的功能多寡分類

（1）單功能流水線（UnifunctionPipelining）單功能流水線是指只能完成一種固定功能的流水線。（2）多功能流水線（MultifunctionPipelining）多功能流水線是指流水線的各段可以實(shí)現(xiàn)不同的連接，在不同的時(shí)間內(nèi)，或在同一時(shí)間內(nèi)，通過不同的連接方式實(shí)現(xiàn)不同的處理功能。

輸入示階差對階規(guī)格化尾數(shù)加輸出

第一節(jié)流水線的基本概念輸入對階尾數(shù)加規(guī)格化尾數(shù)乘輸出累加求階差定點(diǎn)乘法

浮點(diǎn)加法

浮點(diǎn)點(diǎn)積

TI-ASC計(jì)算機(jī)的多功能流水線

輸入尾數(shù)乘累加輸出輸入求階差對階尾數(shù)加規(guī)格化輸出

第一節(jié)流水線的基本概念2.按多功能流水線在同一時(shí)間內(nèi)各段連接方式分類

在多功能流水線中，按照在同一時(shí)間內(nèi)是否可以實(shí)現(xiàn)多種連接，來同時(shí)執(zhí)行多種功能的要求，把多功能流水線分為靜態(tài)流水線和動態(tài)流水線。（1）靜態(tài)流水線（StaticPipelining）靜態(tài)流水線是指在同一段時(shí)間內(nèi)，多功能流水線只能按一種方式連接，實(shí)現(xiàn)一種功能。只有當(dāng)按照這種連接流入的所有處理的對象都流出流水線之后，多功能流水線才能重新進(jìn)行連接以實(shí)現(xiàn)其他功能。如圖3.6所示中的8段多功能流水線如果按照圖3.7所示的時(shí)空圖工作，那么就是一種靜態(tài)流水線。（2）動態(tài)流水線（DynamicPipelining）動態(tài)流水線是指在同一段時(shí)間內(nèi)，多功能流水線中的各段可以實(shí)現(xiàn)多種連接，同時(shí)執(zhí)行多種功能。當(dāng)然，任何一個(gè)功能段只能參加到一種連接中。

第一節(jié)流水線的基本概念空間浮點(diǎn)加定點(diǎn)乘輸出1 2n-1n 1累加12n-1n12數(shù)乘123規(guī)格化123n-1n尾數(shù)加123n-1n對階123n-1n 求階差

123n-1n輸入123n-1n123n-1n時(shí)間靜態(tài)流水線的時(shí)空圖

空間浮點(diǎn)加定點(diǎn)乘輸出12…n-1n123…累加1234…尾數(shù)乘12345…規(guī)格化12…n-1n尾數(shù)加12…n-1n對階12…n-1n求階差12…n-1n輸入12…n-1n123456…

時(shí)間動態(tài)流水線的時(shí)空圖

第一節(jié)流水線的基本概念

第一節(jié)流水線的基本概念

3.按流水線的級別分類

按照流水線的級別，可以把流水線分為功能部件級、處理機(jī)級和處理機(jī)間級。（1）指令流水線（InstructionPipelining）指令流水線又稱為處理機(jī)級流水線，它是把一條指令的執(zhí)行過程分解為多個(gè)子過程，每個(gè)子過程在一個(gè)獨(dú)立的功能部件中完成。（2）運(yùn)算操作流水線（ArthmeticPipelining）運(yùn)算操作流水線又稱為功能部件級流水線，它是把處理機(jī)的算術(shù)邏輯部件分段，使運(yùn)算過程能進(jìn)行流水操作。（3）宏流水線（MacroPipelining）宏流水線又稱為處理機(jī)間流水線，它是由兩個(gè)或兩個(gè)以上的處理機(jī)通過存儲器串行連接起來，每個(gè)處理機(jī)對同一數(shù)據(jù)流的不同部分分別進(jìn)行處理，前一個(gè)處理機(jī)的輸出結(jié)果存入存儲器中，作為后一個(gè)處理機(jī)的輸入，每個(gè)處理機(jī)完成整個(gè)任務(wù)中的一部分。

第一節(jié)流水線的基本概念處理機(jī)1存儲器處理機(jī)2處理機(jī)n存儲器存儲器…處理機(jī)1存儲器處理機(jī)2處理機(jī)n存儲器存儲器…一種宏流水線

第一節(jié)流水線的基本概念

4.按流水線的各功能段之間是否有反饋回路分類按照流水線的各功能段之間是否有反饋回路，可以把流水線分為線性流水線和非線性流水線。（1）線性流水線（linearPipelining）線性流水線是指流水線各段串行連接，數(shù)據(jù)順序流經(jīng)流水線各段水線各段一次且僅流過一次。（2）非線性流水線（nonlinearpipelining）非線性流水線是指在流水線各段之間除有串行連接之外，還有反饋回路，數(shù)據(jù)流經(jīng)有反饋回路的功能段的次數(shù)可以有多次。

第一節(jié)流水線的基本概念五、流水線的特點(diǎn)

（1）流水線是由多個(gè)獨(dú)立的從一個(gè)大的處理功能部件分解而來的小功能部件組成，依靠小功能部件并行工作來提高處理速度。把一個(gè)重復(fù)的處理過程分解為若干個(gè)子過程，每個(gè)子過程需要設(shè)置一個(gè)對應(yīng)的功能部件來實(shí)現(xiàn)，這是流水線本質(zhì)。（2）流水線中各功能段的時(shí)間應(yīng)盡量相等，否則將引起“堵塞”、“斷流”等。在流水線設(shè)計(jì)中，當(dāng)遇到“瓶頸”時(shí)，必須采取辦法解決。（3）流水線需要有“裝入時(shí)間”和“排空時(shí)間”。“裝入時(shí)間”是指第一個(gè)任務(wù)進(jìn)入流水線到輸出流水線的時(shí)間?！芭趴諘r(shí)間”是指第n個(gè)（最后一個(gè)）任務(wù)進(jìn)入流水線到輸出流水線的時(shí)間。

（4）只有連續(xù)不斷地提供同種任務(wù)才能充分發(fā)揮流水線的效率。因此，在采用流水線方式工作的處理機(jī)中，特別是當(dāng)流水線的級數(shù)較多時(shí)，要在軟件和硬件設(shè)計(jì)等多方面盡量為流水線提供連續(xù)的任務(wù)，以提高流水線的效率。（5）在流水線的每一個(gè)功能部件的后面都要有一個(gè)緩沖寄存器，或稱為鎖存器、閘門寄存器等。它的作用是保存本流水段的執(zhí)行結(jié)果，如圖所示。

第一節(jié)流水線的基本概念取指令譯碼執(zhí)行存結(jié)果鎖存器鎖存器鎖存器鎖存器流水線中鎖存器

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)二、先行控制方式的基本結(jié)構(gòu)五、流水線結(jié)構(gòu)設(shè)計(jì)中的若干問題

三、先行控制的指令流水線四、運(yùn)算操作流水線和宏流水線的基本結(jié)構(gòu)一、重疊執(zhí)行方式的基本結(jié)構(gòu)重疊執(zhí)行方式的基本結(jié)構(gòu)

取指部件讀數(shù)寫數(shù)主存儲器分析部件運(yùn)算部件寄存器組運(yùn)算控制器存儲控制器取指修改PC

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)

2.訪問沖突及其解決方法

采用了重疊執(zhí)行方式的基本結(jié)構(gòu)后，可實(shí)現(xiàn)取指令、分析和執(zhí)行的并發(fā)進(jìn)行，但存在訪問主存的沖突問題（即資源沖突、結(jié)構(gòu)相關(guān)）。例如，取指令要訪存，分析指令時(shí)可能要訪存取操作數(shù)，執(zhí)行指令時(shí)可能要向主存寫運(yùn)算結(jié)果。在一般機(jī)器中，指令和數(shù)據(jù)是混合存放在一個(gè)主存中，而且在一個(gè)存儲周期只能訪問一個(gè)存儲單元。因此，一般的存儲器體系結(jié)構(gòu)無法實(shí)現(xiàn)指令的重疊執(zhí)行。解決這個(gè)問題的方法一般有以下三種。（1）設(shè)置兩個(gè)獨(dú)立編址的主存儲器。（2）主存儲器采用多體交叉編址的并行存儲器。（3）采用先行控制技術(shù)是解決訪存沖突的根本辦法。

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)二、先行控制方式的基本結(jié)構(gòu)

1.先行控制方式的基本原理

在二次重疊執(zhí)行方式執(zhí)行指令中，假設(shè)取指令、分析指令和執(zhí)行指令的時(shí)間相等，則流水線連續(xù)流暢，否則功能段會相互等待。但實(shí)際上往往是不相等的，若取指令、分析指令和執(zhí)行指令分別為△t1、△t2、△t3，且△t2＞△t3＞△t1，多條指令的執(zhí)行過程如圖2-13所示。從圖2-13可以看出，取指段在取完第k+1條指令后，由于分析段還沒有分析完第k條指令，第k+1條指令不能進(jìn)入分析段而產(chǎn)生了堵塞，導(dǎo)致取指段空閑；執(zhí)行段執(zhí)行完第k條指令后，由于分析段還沒有分析完第k+1條指令，執(zhí)行段得不到第k+1條指令而產(chǎn)生了斷流，又導(dǎo)致執(zhí)行段空閑。另外，當(dāng)指令之間存在數(shù)據(jù)相關(guān)等相關(guān)時(shí)，重疊也會被打斷。例如，如果第k條指令是轉(zhuǎn)移指令，則順序取來的第k+1條指令可能無效,從而產(chǎn)生了停頓。

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)取指k分析k執(zhí)行k分析k+1取指k+1執(zhí)行k+1取指k+2分析k+2執(zhí)行k+2各功能段延遲時(shí)間不相等的二次重疊執(zhí)行方式

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)

先行控制方式的基本思想是：當(dāng)流水線中某功能段的延遲時(shí)間較長時(shí)，該功能段前面的功能段對后繼任務(wù)進(jìn)行預(yù)處理，預(yù)處理好的后繼任務(wù)置于緩沖器中。而該功能段后面的功能段則對以前置于緩沖器的任務(wù)進(jìn)行后行處理。這樣，所有的功能段都處于忙碌狀態(tài)。某任務(wù)的流程中，各功能段之間有等待的時(shí)間間隔，但各自的流程是連續(xù)的。當(dāng)然，如果前面功能段的緩沖器已滿，或者后面功能段沒有后行處理任務(wù)，流水線仍是不流暢的。采用先行控制方式工作，不僅可解決延遲時(shí)間不相等和不能在較長時(shí)間內(nèi)提供同種任務(wù)而造流水線不流暢，解決了訪問沖突。當(dāng)有多個(gè)功能段要訪問存儲器時(shí)，根據(jù)具體情況，讓某功能段訪存，其前面的功能段則對后繼任務(wù)進(jìn)行預(yù)處理，而后面的功能段則進(jìn)行后行處理。

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)2．什么是先行控制

先行控制是通過對任務(wù)的預(yù)處理和緩沖，以平滑功能部件工作速度上的差異，使功能部件能獨(dú)立地工作，并始終處于忙碌狀態(tài)，提高任務(wù)執(zhí)行的速度。它實(shí)質(zhì)是緩沖技術(shù)和預(yù)處理技術(shù)相結(jié)合的結(jié)果。緩沖技術(shù)和預(yù)處理技術(shù)是先行控制的關(guān)鍵。緩沖技術(shù)是在工作速度不固定的兩個(gè)功能段之間設(shè)置緩沖棧，用以平滑它們的工作速度的差異。預(yù)處理技術(shù)是把要進(jìn)入某功能段的任務(wù)進(jìn)行外圍處理，減少該功能段的執(zhí)行時(shí)間。例如，把進(jìn)入運(yùn)算器的指令都處理成寄存器——寄存器型（RR型）指令，它與緩沖技術(shù)相結(jié)合，為進(jìn)入運(yùn)算器指令準(zhǔn)備好所需的全部操作數(shù)。

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)

3.先行控制方式的基本結(jié)構(gòu)

先行控制方式的基本結(jié)構(gòu)如圖所示。它一般要設(shè)置4個(gè)先行緩沖棧，這四個(gè)緩沖棧的作用如下。（1）先行指令緩沖棧（2）先行操作棧（3）先行讀數(shù)棧（4）后行寫數(shù)棧通常把先行指令緩沖棧、先行讀數(shù)棧、先行操作棧和后行寫數(shù)棧統(tǒng)稱為先行控制器。先行控制器與指令分析器一起構(gòu)成先行控制方式中的指令控制部件。而原來的運(yùn)算器及運(yùn)算控制器一起組成指令執(zhí)行部件。

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)主存儲器存儲控制器先行指令緩沖棧指令分析器寄存器組運(yùn)算器運(yùn)算控制器先行讀數(shù)棧后行寫數(shù)棧先行操作棧先行控制的基本結(jié)構(gòu)

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)

先行指令緩沖棧的組成結(jié)構(gòu)如圖所示。只要指令緩沖棧未滿，存儲控制器就根據(jù)先行程序計(jì)數(shù)器PC1進(jìn)行取指令，指令分析器在分析完一條指令后，則根據(jù)現(xiàn)行程序計(jì)數(shù)器PC2自動從指令緩沖棧取另外一條指令來進(jìn)行分析，先行程序計(jì)數(shù)器PC1與現(xiàn)行程序計(jì)數(shù)器PC2的順序一致，一維持正確的執(zhí)行順序。

主存儲器存儲控制器先行程序計(jì)數(shù)器PC1指令寄存器IR指令緩沖寄存器堆控制邏輯現(xiàn)行程序計(jì)數(shù)器PC2指令分析器先行指令緩沖棧的組成

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)4.緩沖深度的選擇

先行控制器四個(gè)緩沖棧中的緩沖寄存器的個(gè)數(shù)即是緩沖深度。緩沖深度多少合適呢？緩沖深度小，緩沖作用不大；緩沖深度大，會浪費(fèi)寄存器，控制也復(fù)雜。對于緩沖深度的選擇，一般是在采用靜態(tài)分析的基礎(chǔ)上，通過系統(tǒng)模擬的方法來確定各個(gè)緩沖棧的緩沖深度。靜態(tài)分析方法可從兩個(gè)極端情況來考察。一是假設(shè)先行指令緩沖棧緩沖深度深度為Di，且已完全充滿。此時(shí)在先行指令緩沖棧的輸出端，給指令分析器的提供指令較簡單，流出的速度快；而在輸入端，由于要訪存取指令，指令注入速度慢。設(shè)平均每條指令分析的時(shí)間為t1,平均取一條指令的時(shí)間為t2。在先行指令緩沖棧從完全充滿到全部被取空的過程中，若指令分析器一共分析了L1條，所花時(shí)間為L1t1，同時(shí)從主存中讀取了L1－Di條指令，所花時(shí)間二者應(yīng)相等，即L1t1=（L1－Di）t2。故得：

Di=「L1（t2–t1）/t2」

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)

當(dāng)取值大于L1條時(shí)，該先行指令緩沖器將被取空，指令分析器被迫處于等待狀態(tài)。二是假定先行指令緩沖棧為空，且取指速度快，平均時(shí)間為t2ˊ；而分析指令由于指令復(fù)雜、速度較慢，平均時(shí)間為t1ˊ。從先行指令緩沖棧完全為空到完全充滿指令的過程中，若從主存取到先行指令緩沖中的指令條數(shù)為L2條，而指令分析器分析的指令條數(shù)為Di，所花時(shí)間二者應(yīng)相等，即L2t2ˊ=（L2－Di）t2ˊ。故得：

Di=「L2（t1ˊ–t2ˊ）/t1ˊ」當(dāng)取值大于L2條時(shí)，該先行指令緩沖器將被充滿，也就失去了緩沖作用。

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)

若讓t1與t2非常接近，即提高主存速度，如采用并行主存儲器，或增大Cache容量或級數(shù)，對減少緩沖深度很有效。由于在一般程序中，執(zhí)行時(shí)間短的指令要遠(yuǎn)遠(yuǎn)多于執(zhí)行時(shí)間長的指令，指令分析器分析指令的速度要大于運(yùn)算器執(zhí)行指令的速度。因此常用前一種方法來計(jì)算緩沖深度。另外在確定緩沖深度時(shí)，還要選擇一些典型程序，通過模擬方法選取合理的緩沖深度。各個(gè)緩沖棧的緩沖深度有如下關(guān)系：

D先行指令≥D先行操作≥D先行讀數(shù)≥D后行寫數(shù)

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)三、先行控制的指令流水線

在采用先行控制方式的處理機(jī)中，先行控制結(jié)構(gòu)中的各個(gè)部件也構(gòu)成了一條流水線，如圖所示。它把指令的執(zhí)行分解為五個(gè)子過程，即取指令、指令譯碼、取操作數(shù)、執(zhí)行運(yùn)算、寫結(jié)果。由于各種指令在同一個(gè)功能部件中執(zhí)行的時(shí)間可能相差很大，因此，在各個(gè)功能段之間都設(shè)置多個(gè)緩沖寄存器，以平滑流水線中各功能部件的操作。先行指令緩沖棧先行指令分析器先行讀數(shù)數(shù)棧

先行操作棧指令執(zhí)行部件后行寫數(shù)棧功能：取指令組計(jì)算操作數(shù)地址形成RR*型指令運(yùn)算保存結(jié)果輸入輸出先行控制方式中的指令流水線

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)四、運(yùn)算操作流水線和宏流水線的基本結(jié)構(gòu)

1.運(yùn)算操作流水線的基本結(jié)構(gòu)

把運(yùn)算操作過程分成多個(gè)子過程，每一個(gè)子過程的延遲時(shí)間雖然不可能絕對相等，但偏移不大。因此，采用集中控制方式，使所有的流水段與一個(gè)統(tǒng)一的時(shí)鐘同步。而時(shí)鐘周期的大小則要根據(jù)流水段的劃分來確定。由于實(shí)際執(zhí)行的誤差，可能引起段間的干擾。為避免干擾，保證段間時(shí)間寬度匹配，在各段之間增設(shè)門（Latch）寄存器，如圖所示。門寄存器則是各段之間的標(biāo)志。

2.宏流水線的基本結(jié)構(gòu)

宏流水線是每個(gè)處理機(jī)對同一數(shù)據(jù)流的不同作業(yè)分別進(jìn)行處理，其結(jié)構(gòu)則是異構(gòu)型的多處理機(jī)系統(tǒng)。多處理機(jī)系統(tǒng)對任務(wù)處理的效率，不僅與系統(tǒng)結(jié)構(gòu)有關(guān)，而且與算法、語言、軟件等有關(guān)。

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)段S1門寄存器段S2段Sn門寄存器門寄存器門寄存器運(yùn)算操作流水線的基本結(jié)構(gòu)

第二節(jié)處理機(jī)實(shí)現(xiàn)流水線的基本結(jié)構(gòu)五、流水線結(jié)構(gòu)設(shè)計(jì)中的若干問題

1.瓶頸問題

當(dāng)流水線的各段時(shí)間相等時(shí)，其任務(wù)是每一個(gè)節(jié)拍同步地往前流動一段，該節(jié)拍往往就是機(jī)器的時(shí)鐘周期。當(dāng)流水線各段時(shí)間不相等時(shí)，時(shí)間最大的那個(gè)段就成了瓶頸，機(jī)器的時(shí)鐘周期取決于該瓶頸段的延遲時(shí)間。

2.額外開銷問題

流水線的額外開銷由兩部分構(gòu)成：流水線寄存器延遲和時(shí)鐘偏移開銷。采用流水技術(shù)后，雖然可以提高指令執(zhí)行的吞吐率，從而提高程序的執(zhí)行速度，但流水線并不能真正減少單條指令的執(zhí)行時(shí)間。實(shí)際上，由于這些開銷的存在，反而會使每條指令的執(zhí)行時(shí)間有所增加。3.相關(guān)問題

在運(yùn)算操作流水線中，如果后面的計(jì)算要用到前面計(jì)算的結(jié)果，則流水線的性能和效果會受到比較大的影響。對于指令流水線來說，也是如此。如果流水線中的指令之間存在關(guān)聯(lián)，則它們可能要相互等待，引起流水線的停頓。如何處理好相關(guān)問題，是流水線設(shè)計(jì)中要解決的重要問題之一。

第三節(jié)線性流水線的性能及其分析一、吞吐率（TP,Thoughputrate）二、加速比（S，Speedupratio）

三、效率(E，Efficiency)

四、吞吐率、加速比和效率之間的關(guān)系

六、流水線最佳段數(shù)的選擇

五、流水線“瓶頸”問題的解決方法

第三節(jié)線性流水線的性能及其分析一、吞吐率（TP,Thoughputrate）

1.吞吐率的定義

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

TP=n/Tk式中：n為任務(wù)數(shù)，Tk是處理完成n個(gè)任務(wù)所用的時(shí)間，式是計(jì)算流水線吞吐率最基本公式。

第三節(jié)線性流水線的性能及其分析

2.流水線各段的執(zhí)行時(shí)間相等的吞吐率若有一條k段的線性流水線，各段的執(zhí)行時(shí)間相等，均為△t。當(dāng)n個(gè)任務(wù)是連續(xù)的理想情況下輸入到流水線，流水線的時(shí)空圖如圖所示。時(shí)間空間S4S3S2S1123…n-1n123…n-1n123…n-1n123…n-1n

k·△t(n-1)△t

n·△t(k-1)△tTk各段執(zhí)行時(shí)間均相等的流水線時(shí)空圖

第三節(jié)線性流水線的性能及其分析

流水線完成n個(gè)任務(wù)所需要的總時(shí)間可從兩方面來分析。一是從流水線的輸出端看，用k個(gè)△t輸出第一任務(wù)，即k·△t為“裝入時(shí)間”，其余n-1個(gè)任務(wù)，每個(gè)△t輸出一個(gè)任務(wù)，即用n-1個(gè)時(shí)期周期輸出n-1個(gè)任務(wù)。二是從流水線的輸入端看，用n個(gè)△t向流水線輸入n個(gè)任務(wù)，另外還要用k-1個(gè)△t作為流水線的“排空時(shí)間”。因此，流水線完成n個(gè)任務(wù)需要的總時(shí)間為：

Tk=（n+k-1）·△t連續(xù)輸入n個(gè)任務(wù)的一條k段線性流水線的實(shí)際吞吐率為：相應(yīng)的最大吞吐率為最大吞吐率與實(shí)際吞吐率的關(guān)系是

第三節(jié)線性流水線的性能及其分析

123…n

123…n

123…n

123…nS4S3S2S1時(shí)間

當(dāng)流水線中各流水段的執(zhí)行時(shí)間不相等時(shí)，流水線的最大吞吐率與實(shí)際吞吐率主要是由流水線中執(zhí)行時(shí)間最長的那個(gè)流水段來決定。這時(shí)除“瓶頸”流水段一直忙碌外，其余流水段都有空閑時(shí)間，圖中“”的部分表示該段流水線在這一段時(shí)間內(nèi)是空閑的，這實(shí)際上是一種資源的浪費(fèi)。

(n-1)△t2Tk

第三節(jié)線性流水線的性能及其分析線性流水線的實(shí)際吞吐率為相應(yīng)流水線的最大吞吐率為：

第三節(jié)線性流水線的性能及其分析二、加速比（S，Speedupratio）1.加速比的定義流水線的加速比是指完成同樣一批任務(wù)，不使用流水線即順序執(zhí)行所用的時(shí)間與使用流水線所用的時(shí)間之比。如果不使用流水線所用的時(shí)間為T0，使用流水線的執(zhí)行時(shí)間為Tk，則流水線的加速比為：

S=T0/Tk是計(jì)算流水線加速比的基本公式。

2.流水線各段的執(zhí)行時(shí)間相等的加速比若有一條k段的線性流水線，各段的執(zhí)行時(shí)間相等，均為△t。當(dāng)n個(gè)任務(wù)是連續(xù)的理想情況下輸入到流水線，該流水線完成n個(gè)連續(xù)任務(wù)所需要的時(shí)間見（2-4）式。如果不使用流水線執(zhí)行這n個(gè)任務(wù)，所需要的時(shí)間為：。因此，流水線的實(shí)際加速比為：

第三節(jié)線性流水線的性能及其分析相應(yīng)的最大加速比為:3.流水線各段的執(zhí)行時(shí)間不相等的加速比

第三節(jié)線性流水線的性能及其分析三、效率(E，Efficiency)1.效率的定義流水線的效率是指流水線的設(shè)備利用率。在時(shí)空圖上，流水線的效率定義為n個(gè)任務(wù)占用的時(shí)空區(qū)與k個(gè)流水段占用的總時(shí)空區(qū)之比。即：

E=n個(gè)任務(wù)占用的時(shí)空區(qū)/k個(gè)流水段占用的總時(shí)空區(qū)式是計(jì)算流水線效率的基本公式，其分母是n個(gè)任務(wù)所用的時(shí)間與k個(gè)流水段所圍成的時(shí)空總面積，分子是n個(gè)任務(wù)實(shí)際上占用的有效時(shí)空面積。因此，流水線的效率包含時(shí)間和空間兩方面的因素，通過時(shí)空圖來計(jì)算流水線的效率非常方便。

第三節(jié)線性流水線的性能及其分析

2.流水線各段的執(zhí)行時(shí)間相等的效率各段的執(zhí)行時(shí)間相等，均為△t的k段的線性流水線，完成n個(gè)連續(xù)任務(wù)所需要的時(shí)間見（2-4）式，每個(gè)功能段在這段時(shí)間內(nèi)都被占用，則時(shí)空圖的總面積為k(k+n-1)△t。一個(gè)任務(wù)占用的時(shí)空區(qū)為k.△t，n個(gè)任務(wù)實(shí)際占用的有效面積為n.k.△t。各段的執(zhí)行時(shí)間相等的流水線效率為：

從式中可以看出，當(dāng)n＞＞k時(shí)，流水線的效率達(dá)到最大值1。這時(shí)，流水線的各段均處于忙碌狀態(tài)。從時(shí)空圖中看，每一塊都是有效的。相應(yīng)的流水線的最大效率為：

3.流水線各段的執(zhí)行時(shí)間不相等的效率

第三節(jié)線性流水線的性能及其分析

第三節(jié)線性流水線的性能及其分析四、吞吐率、加速比和效率之間的關(guān)系說明流水線的效率是流水線實(shí)際加速比S與它的最大加速比Smax=k之比。只有當(dāng)流水線的效率達(dá)到其最大值，即E=1時(shí)，才能使實(shí)際加速比達(dá)到最大，即S=k。當(dāng)n＞＞k時(shí)，有：Emax=1Smax=kTPmax=1/△t

各段的執(zhí)行時(shí)間不相等時(shí)，即流水線中存在“瓶頸”流水段，除了瓶頸流水段一直處于忙碌狀態(tài)之外，其他各個(gè)流水段都有空閑時(shí)間，這些流水段的效率沒有得到充分發(fā)揮。因此，整個(gè)流水線的吞吐率、加速比和效率也比較低。采用提高流水線吞吐率的方法，由于能夠使流水線中的各個(gè)流水段始終處于忙碌狀態(tài)，沒有空閑時(shí)間。因此，流水線的吞吐率、加速比和效率也就顯著提高了。

第三節(jié)線性流水線的性能及其分析五、流水線“瓶頸”問題的兩種解決方法

1.分離“瓶頸”流水段

分離“瓶頸”流水段將流水線的“瓶頸”功能段部分再細(xì)分，分解成幾個(gè)獨(dú)立的子功能段，消除執(zhí)行時(shí)間不相等而帶來的“瓶頸”段。例如，把圖2.19所示的第二個(gè)流水段再細(xì)分為三個(gè)子流水段，分別為S2-1、S2-2和S2-3，如圖所示。這樣，每個(gè)流水段及子流水段的延遲時(shí)間均為△t。

2.重復(fù)設(shè)置“瓶頸”流水段

如果由于結(jié)構(gòu)等方面的原因，瓶頸流水段難以再細(xì)分，則可以通過重復(fù)設(shè)置瓶頸流水段，讓多個(gè)瓶頸流水段并行工作，消除執(zhí)行時(shí)間不相等而帶來的“瓶頸”段。例如，把圖所示的第二個(gè)流水段重復(fù)設(shè)置，流水線連接圖如圖所示。但是，采用瓶頸流水段重復(fù)設(shè)置的方法，其控制邏輯比較復(fù)雜。S1S2-2S2-3S3S4S2-1S2-1S2-2S2-3S4S3S1“瓶頸”流水段再次細(xì)分流水線

“瓶頸”流水段重復(fù)設(shè)置流水線

第三節(jié)線性流水線的性能及其分析

第三節(jié)線性流水線的性能及其分析123456789…n-2n-1n123456789…n-2n-1n147…n-2258…n-1369…n123456789…n-2n-1nS4S3S2-3S2-2S2-1S1空間時(shí)間

第三節(jié)線性流水線的性能及其分析六、流水線最佳段數(shù)的選擇假設(shè)在非流水線的機(jī)器上采用順序執(zhí)行方式完成一個(gè)任務(wù)所需要的時(shí)間為t，那么，在同等速度的有k段流水線的機(jī)器上執(zhí)行一個(gè)任務(wù)需要的時(shí)間為：t/k+d，其中d為鎖存器的延遲時(shí)間。流水線的最大吞吐率為：TP=1/(t/k+d)。又粗略地估計(jì)流水線的總價(jià)格為：C=a+bk。其中，a為所有流水段的總價(jià)格，b為每個(gè)鎖存器的價(jià)格。流水線的性能價(jià)格比PCR定義為：K0=

目前,一般處理機(jī)中的流水線段數(shù)在2段至10段之間,極少有超過15段的流水線,一般把8段或超過8段的流水線稱為超流水線。

第三節(jié)線性流水線的性能及其分析

例2.1一個(gè)四段線性流水線，各段執(zhí)行時(shí)間不等，如圖3-19所示。①當(dāng)n=4時(shí)，畫出它的時(shí)空圖，求TP、TPmax、S和E的值。②當(dāng)n=12時(shí)，畫出分離“瓶頸”流水段的流水線連接圖和時(shí)空圖，求TP、TPmax、S和E的值。③當(dāng)n=12時(shí)，畫出重復(fù)設(shè)置“瓶頸”流水段的流水線連接圖和時(shí)空圖，求TP、TPmax、S和E的值。解：（1）流水線的時(shí)空圖如圖3-20所示，由時(shí)空圖可以看出，n=4時(shí)，k=4。所以TP=n/Tn=n/[6△t+(n-1)3△t]=4/15△tTPmax=TP=1/3△t T0=n×k△t=4×(1+3+1+1)△t=24△t S=T0/Tn=24△t/15△t=1.6

因?yàn)橛行娣e=3×(△t×4)+1×(3△t×4)=24△t

實(shí)際面積=4×Tn=60△t

所以E=24△t/60△t=0.4

第三節(jié)線性流水線的性能及其分析（2）線性流水線中的段2為“瓶頸”流水段，分離該流水段后的流水線連接圖如圖3-21所示，時(shí)空圖類似于圖3-18。且n=12時(shí)，k=6。所以TP=n/Tn=n/[6△t+(n-1)△t]=12/17△t TPmax=TP=1/△tS=n·k/(k+n-1)=12×6/(6+12-1)=4.24E=S/k=0.7（3）線性流水線中的段2為“瓶頸”流水段，重復(fù)設(shè)置該流水段后的流水線連接圖如圖3-22所示，時(shí)空圖如圖3-23所示。且n=12時(shí)，k=6。所以TP=n/Tn=n/[6△t+(n-1)△t]=12/17△t TPmax=TP=1/△tS=n·k/(k+n-1)=12×6/(6+12-1)=4.24E=S/k=0.7

第三節(jié)線性流水線的性能及其分析

例2.2如圖2-25所示的靜態(tài)加、乘雙功能流水線中，由段S1、S2、S3、S4、S6組成乘法流水線，由段S1、S5、S6組成加法流水線。設(shè)向量a=（a1，a2，a3，a4），向量b=（b1，b2，b3，b4），計(jì)算П(ai+bi)。畫出該流水線時(shí)空圖，求TP、S和E的值。S1S2S3S4S6S5乘流水線XYZ加流水線

第三節(jié)線性流水線的性能及其分析

解：由于該流水線為靜態(tài)雙功能流水線，計(jì)算要求先加后乘，因此應(yīng)先置加法功能，連續(xù)計(jì)算（a1+b1）、（a2+b2）、（a3+b3）、（a4+b4）四個(gè)加法后；再設(shè)置乘法功能，而且按[(a1+b1)×(a2+b2)]×[(a3+b3)×(a4+b4)]順序做3個(gè)乘法。因此可畫出該流水線的時(shí)空圖如圖2-26所示，圖中A=a1+b1，B=a2+b2，C=a3+b3，D=a4+b4。空間S6S5S4S3S2S11234三12341234一二一二一二一二一二三三三三ABCDA·BC·D(A·B)×(C·D)

t6t12t17a1b1a2b2a3b3a4b4ABCDA·BC·D時(shí)間

第三節(jié)線性流水線的性能及其分析

由時(shí)空圖可以看出，在總共17個(gè)△t的時(shí)間內(nèi)輸出7個(gè)結(jié)果，所以有：

TP=n/Tn=7/17△t

而當(dāng)用串行方法完成操作時(shí)，需要四次加法和三次乘法，完成一次加法需要3△t，完成一次乘法需要5△t，完成該運(yùn)算總共需要時(shí)間為：

T0=4×3△t+3×5△t=27△t

所以S=T0/Tn=1.88E=有效時(shí)空區(qū)面積/全部時(shí)空區(qū)面積

=(3×4△t+5×3△t)/(6×17△t)=0.264

第三節(jié)線性流水線的性能及其分析

例2.3有一條動態(tài)多功能流水線由5段組成，如圖2.27所示。加法用1、3、4、5段，乘法用1、2、5段，第4段的時(shí)間為2△t，其余各段時(shí)間均為△t，而且流水線的輸出可以直接返回輸入端或暫存于相應(yīng)的流水寄存器中。若在該流水線上計(jì)算試計(jì)算其吞吐率、加速比和效率。

S1S2S3S4S5乘流水線加流水線

第三節(jié)線性流水線的性能及其分析

解：首先應(yīng)選擇適合于流水線工作的算法。對于本題，應(yīng)先計(jì)算A=A1×B1、B=A2×B2、C=A3×B3和D=A4×B4，再計(jì)算A×B和C×D；然后求總的累加結(jié)果。其次，畫出完成計(jì)算的時(shí)空圖，如圖2.28所示，圖中陰影部分表示相應(yīng)段在工作。412312341234空間S5S4S3S2S1ABCDA＋BC＋D(A＋B)＋(C＋D)

t6t16ABCDA＋BC＋DA1A2A3A4B1B2B3B4一一一一二二二二三三三三時(shí)間

第三節(jié)線性流水線的性能及其分析

由圖2.28可見，它在16個(gè)△t時(shí)間中，給出了7個(gè)結(jié)果。所以吞吐量為：

TP=7/16△t

如果不用流水線，由于一次求積需3△t，一次求和需5△t，則產(chǎn)生上述7個(gè)結(jié)果共需要（4×3＋3×5）△t=27△t，所以加速比為：

S=27△t/16△t≈1.69

該流水線的效率可由陰影區(qū)的面積和5個(gè)段總時(shí)空區(qū)的面積的比值求得：

E=（4×3＋3×5）△t/5×16△t≈0.338

第四節(jié)流水線中的相關(guān)及其處理

一、流水線中相關(guān)的基本概念二、資源相關(guān)三、操作數(shù)相關(guān)四、指令相關(guān)五、變址相關(guān)六、條件轉(zhuǎn)移相關(guān)及其對流水線效率的影響七、條件轉(zhuǎn)移相關(guān)的處理技術(shù)八、無條件轉(zhuǎn)移相關(guān)九、中斷轉(zhuǎn)移相關(guān)

第四節(jié)流水線中的相關(guān)及其處理一、流水線中相關(guān)的基本概念

1.什么是順序流動與異步流動

流水線中任務(wù)是從輸入端流入，于輸出端流出。一般來說，先流入流水線的任務(wù)，則先于輸出端流出。但是，由于要處理的任務(wù)有簡單、有復(fù)雜，執(zhí)行時(shí)間有多少，即可能發(fā)生超越現(xiàn)象，還有任務(wù)在流水線中，由于某種原因有一段時(shí)間沒有流動。因此，有可能發(fā)生任務(wù)流入流水線的順序與任務(wù)流出流水線的順序不一樣。順序流動是指任務(wù)從流水線流出的次序同它們流入流水線的次序一樣。異步流動是指任務(wù)從流水線流出的次序同它們流入流水線的次序不一樣，也稱為亂序流動或錯(cuò)序流動。

第四節(jié)流水線中的相關(guān)及其處理2.流水線中的相關(guān)及其分類

相關(guān)是指程序中指令之間存在的相互依賴關(guān)系，是程序固有的一種屬性。而某一次相關(guān)是否導(dǎo)致實(shí)際沖突的發(fā)生以及該沖突所帶來的流水線停頓時(shí)間，則是流水線的屬性。流水線中的相關(guān)是指程序中指令之間存在的可能影響指令流水線連續(xù)流動執(zhí)行的某種關(guān)系，這種相關(guān)一般有三大類，即資源（結(jié)構(gòu)）相關(guān)、數(shù)據(jù)相關(guān)和控制相關(guān)。數(shù)據(jù)相關(guān)與資源相關(guān)由于它對程序執(zhí)行過程影響較小，僅涉及相應(yīng)指令的前后一條或幾條指令的執(zhí)行，所以又稱為局部相關(guān)；控制相關(guān)由于它對程序執(zhí)行過程影響較大，可能改變程序的執(zhí)行方向，所以又稱為全局相關(guān)。

第四節(jié)流水線中的相關(guān)及其處理控制相關(guān)數(shù)據(jù)相關(guān)指令相關(guān)變址相關(guān)操作數(shù)相關(guān)：先寫后讀、先讀后寫、寫—寫流水線的相關(guān)資源相關(guān)：主存相關(guān)、操作部件相關(guān)轉(zhuǎn)移相關(guān)：無條件、一般條件、復(fù)合條件、循環(huán)中斷相關(guān)

第四節(jié)流水線中的相關(guān)及其處理3.數(shù)據(jù)相關(guān)及其類型分析

數(shù)據(jù)相關(guān)是指在流水線的機(jī)器中，程序中相近的兩條指令要對同一存儲單元進(jìn)行操作時(shí)，應(yīng)有一定的先后次序，否則會導(dǎo)致數(shù)據(jù)供求關(guān)系上的沖突，引發(fā)程序執(zhí)行錯(cuò)誤。從存儲單元的操作次序來看，數(shù)據(jù)相關(guān)有“先寫后讀”相關(guān)、“先讀后寫”相關(guān)和“寫—寫”相關(guān)三種。存儲單元存儲的內(nèi)容一般有指令、操作數(shù)和地址（一般是地址信息的一部分，可稱之為變址），因此，從存儲單元存儲的內(nèi)容來看，數(shù)據(jù)相關(guān)有指令相關(guān)、操作數(shù)相關(guān)和變址相關(guān)三種。指令相關(guān)一定是前面一條指令要修改或產(chǎn)生在其后的指令，變址相關(guān)一定是前面一條指令要產(chǎn)生在其后指令的部分地址信息（如基址或變址），因此，指令相關(guān)和變址相關(guān)從操作次序上屬于“先寫后讀”相關(guān)。操作數(shù)相關(guān)從操作次序上來講可以任意，因此操作數(shù)相關(guān)則有“先寫后讀”相關(guān)、“先讀后寫”相關(guān)和“寫后寫”相關(guān)三種。

第四節(jié)流水線中的相關(guān)及其處理4.控制相關(guān)及其分類

控制相關(guān)是指在流水線的機(jī)器中，由于轉(zhuǎn)移指令或中斷引起程序執(zhí)行方向的改變，使得轉(zhuǎn)移指令或中斷引起的斷點(diǎn)指令與后續(xù)指令不能同時(shí)在流水線中執(zhí)行。它包括轉(zhuǎn)移相關(guān)和中斷相關(guān)兩種。轉(zhuǎn)移指令一般可分為無條件轉(zhuǎn)移指令、一般條件轉(zhuǎn)移指令、復(fù)合條件轉(zhuǎn)移指令和循環(huán)轉(zhuǎn)移指令，因此，從轉(zhuǎn)移指令的條件來看，轉(zhuǎn)移相關(guān)有無條件轉(zhuǎn)移相關(guān)、一般條件轉(zhuǎn)移相關(guān)、復(fù)合條件轉(zhuǎn)移相關(guān)和循環(huán)轉(zhuǎn)移相關(guān)四種。5.相關(guān)處理及其基本思想

由于程序中相關(guān)的存在，就限制了流水線并行執(zhí)行指令，如何克服相關(guān)對并行執(zhí)行指令的限制則是相關(guān)處理。相關(guān)處理的充分條件是保證程序順序，所謂程序順序是指由原來程序確定的完全串行方式下指令的執(zhí)行順序。但并不是存在相關(guān)的指令一定要保證程序順序，只有可能導(dǎo)致錯(cuò)誤時(shí)，才必須保證程序順序，即相關(guān)處理的必要條件是保證語義順序。這就為消除相關(guān)、提高并行執(zhí)行指令的程度提供了基礎(chǔ)。相關(guān)處理的基本思想有兩種，一是避免發(fā)生沖突，即相關(guān)仍然存在；二是消除相關(guān)，即相關(guān)不存在了。流水線處理機(jī)的實(shí)際CPI等于理想流水線CPI加上各類停頓的時(shí)鐘周期數(shù)。即：

CPI實(shí)際=CPI理想＋停頓資源沖突＋停頓數(shù)據(jù)沖突＋停頓控制沖突其中理想流水線的CPI是流水線性能指標(biāo)的最大值。那么，流水線中的相關(guān)處理實(shí)質(zhì)是減少停頓的時(shí)鐘周期數(shù)。第四節(jié)流水線中的相關(guān)及其處理第四節(jié)流水線中的相關(guān)及其處理二、資源相關(guān)

1.資源相關(guān)及其形成

資源相關(guān)是指相近的多條指令進(jìn)入流水線后，同一時(shí)間爭用同一功能部件從而發(fā)生的沖突或爭用現(xiàn)象。在指令流水線中，指令在執(zhí)行（操作）部件的延遲時(shí)間一般比其它功能部件要長且不相同，存儲部件在指令執(zhí)行過程中可能多次要被訪問，爭用現(xiàn)象一般發(fā)生在操作部件和存儲部件上。因此，資源相關(guān)一般可分為主存相關(guān)和操作部件相關(guān)。

假設(shè)指令執(zhí)行過程為取指令、譯碼、執(zhí)行和寫結(jié)果，執(zhí)行部件一般是由定點(diǎn)算術(shù)邏輯部件（ALU，延遲時(shí)間為2個(gè)時(shí)鐘周期）、浮點(diǎn)數(shù)加法部件（FADD，延遲時(shí)間為3個(gè)時(shí)鐘周期）、浮點(diǎn)乘除法部件（FMDU，延遲時(shí)間為4個(gè)時(shí)鐘周期）、圖形處理部件（GPU，延遲時(shí)間為4個(gè)時(shí)鐘周期）和存取數(shù)部件（LSU，延遲時(shí)間為1個(gè)時(shí)鐘周期）組成的多功能操作部件，其他功能部件的延遲時(shí)間為1個(gè)時(shí)鐘周期。現(xiàn)需要執(zhí)行以下程序指令：

kFADDRO，R1；RO←（RO）＋（R1）

k+1FMULR2，R3；R2←（R2）×（R3）

k+2FADDR4，R5；R4←（R4）＋（R5）

k+3FMULR6，R7；R6←（R7）×（R8）第四節(jié)流水線中的相關(guān)及其處理0123456789101213K空間寫結(jié)果浮點(diǎn)乘浮點(diǎn)加譯碼取指時(shí)間KK+1KK+1KK+1K+1K+2K+2K+2K+3K+2K+3K+3K+3K+2K+3第四節(jié)流水線中的相關(guān)及其處理

由于k和k+2兩條指令都要使用浮點(diǎn)加功能部件，那么在第五個(gè)△t時(shí)，就會出現(xiàn)浮點(diǎn)加法部件爭用的現(xiàn)象。由于k+1和k+3兩條指令都要使用浮點(diǎn)乘除功能部件，那么在第六個(gè)△t時(shí)，就會出現(xiàn)浮點(diǎn)乘除法部件爭用的現(xiàn)象。

若現(xiàn)需要執(zhí)行以下程序指令：

kFADDMEM1，R0，R1；MEM1←（RO）＋（R1）

k+1ADDMEM2，R2，R3；MEM2←（R2）＋（R3）

k+2……k+3……k+4……k+5……

第四節(jié)流水線中的相關(guān)及其處理01234567K空間寫結(jié)果定點(diǎn)加浮點(diǎn)加譯碼取指時(shí)間KK+1KK+1K+1K+2K+2K+3K+3K+5KK+4K+4K+1

由于k和k+1指令在第六個(gè)△t時(shí)都要向存儲器寫數(shù)，k+5指令在第六個(gè)△t時(shí)要向存儲器取指令，從而出現(xiàn)了存儲部件爭用的現(xiàn)象。第四節(jié)流水線中的相關(guān)及其處理2.資源相關(guān)的處理

對于給定的流水線，當(dāng)存在資源相關(guān)時(shí)，為了使流水線正常流動，可以采用延遲執(zhí)行方法處理。例如，對于圖2-30中的操作部件相關(guān)，可延遲k+2、k+3條指令進(jìn)入指令流水線，當(dāng)k+2條指令在第四個(gè)△t、k+3條指令在第六個(gè)△t進(jìn)入指令流水線，則避免了浮點(diǎn)數(shù)加法部件和浮點(diǎn)乘除法部件的沖突。當(dāng)然流水線的吞吐率和效率均下降了。要使流水線效率不下降，就必須對流水線或主存進(jìn)行改造，以消除資源相關(guān)。對于操作部件相關(guān)，實(shí)際上操作部件是瓶井，流水線瓶井段的解決方法有細(xì)分瓶井段或重復(fù)設(shè)置瓶井段。對于主存相關(guān)，實(shí)際上是主存訪問的沖突，存儲訪問沖突的解決方法有指令與數(shù)據(jù)Cache分離、采用多體交叉并行存儲器和指令存儲預(yù)取技術(shù)。第四節(jié)流水線中的相關(guān)及其處理三、操作數(shù)相關(guān)

1.什么是操作數(shù)相關(guān)

操作數(shù)相關(guān)是指在流水線的機(jī)器中，程序中相近的兩條指令的操作數(shù)在同一存儲單元而要進(jìn)行操作時(shí)，應(yīng)有一定的先后次序，否則會導(dǎo)致數(shù)據(jù)供求關(guān)系上的沖突，引發(fā)程序執(zhí)行錯(cuò)誤。操作數(shù)相關(guān)包括“先寫后讀”相關(guān)、“先讀后寫”相關(guān)和“寫后寫”相關(guān)三種。第四節(jié)流水線中的相關(guān)及其處理三、操作數(shù)相關(guān)

第四節(jié)流水線中的相關(guān)及其處理

2.操作數(shù)相關(guān)的形成假設(shè)有一串指令在由8個(gè)功能段組成的指令流水線中執(zhí)行，這一串指令流入的次序是g、h、i、j、k、……。由于在指令流水線中，讀操作數(shù)段在前，寫操作數(shù)段在后，因此，“先寫后讀”相關(guān)不僅在流水線異步流動過程中會出現(xiàn)，即使順序流動也容易形成?！跋茸x后寫”與“寫—寫”相關(guān)只有在流水線異步流動過程中才可能形成，順序流動不會出現(xiàn)。三、操作數(shù)相關(guān)

第四節(jié)流水線中的相關(guān)及其處理

2.操作數(shù)相關(guān)的形成

如果指令h寫入結(jié)果的目的地址同指令i讀取操作數(shù)的源地址是同一個(gè)存儲單元或寄存器，即這兩條指令有“先寫后讀”的要求。如果當(dāng)指令i到達(dá)讀段時(shí)，指令h還沒有到達(dá)寫段完成寫操作數(shù)，那么指令i讀出的數(shù)據(jù)就是錯(cuò)誤的。

存儲單元pOinmlkj（i先寫k后寫相關(guān)）

p（i）Onml kj h（i先讀j后寫相關(guān)）指令：j（i）hg （h先寫i后讀相關(guān)）輸入輸出12讀34567寫8第四節(jié)流水線中的相關(guān)及其處理三、操作數(shù)相關(guān)

第四節(jié)流水線中的相關(guān)及其處理

2.操作數(shù)相關(guān)的形成如果順序指令i的讀操作數(shù)和指令j的寫操作數(shù)是同一個(gè)存儲單元或寄存器，即這兩條指令有“先讀后寫”的要求。當(dāng)指令i與其前面的指令h或g存在其它相關(guān)，則可采用異步流動方式，即如果指令i以后的指令與進(jìn)入流水線的全部指令之間都沒有相關(guān)，那么完全可以僅使相關(guān)的指令i暫停流動，而其后的指令依次越過指令i繼續(xù)向前流動。但是可能出現(xiàn)指令j的寫操作數(shù)先于指令i的讀操作數(shù)，那么指令i讀取的數(shù)據(jù)就可能是錯(cuò)誤的。顯然，“先讀后寫”相關(guān)只有在流水線異步流動過程中才可能形成，順序流動不會出現(xiàn)。存儲單元pOinmlkj（i先寫k后寫相關(guān)）

p（i）Onml kj h（i先讀j后寫相關(guān)）指令：j（i）hg （h先寫i后讀相關(guān)）輸入輸出12讀34567寫8第四節(jié)流水線中的相關(guān)及其處理三、操作數(shù)相關(guān)

第四節(jié)流水線中的相關(guān)及其處理

2.操作數(shù)相關(guān)的形成如果順序指令i的寫操作和指令k寫操作是同一個(gè)存儲單元或寄存器，即這兩條指令有“寫后寫”的要求。若由于其他的相關(guān)，采用了異步流動方式，則可能出現(xiàn)指令k先于指令i到達(dá)寫段，那么該存儲單元或寄存器的內(nèi)容最后是由指令i寫入的，而不是按指令流序列的順序要求由指令k寫入的，那么，該存儲單元的數(shù)據(jù)就是錯(cuò)誤的。顯然，“寫—寫”相關(guān)也是只有在異步流動中才可能形成。存儲單元pOinmlkj（i先寫k后寫相關(guān)）

p（i）Onml kj h（i先讀j后寫相關(guān)）指令：j（i）hg （h先寫i后讀相關(guān)）輸入輸出12讀34567寫8第四節(jié)流水線中的相關(guān)及其處理

3.操作數(shù)相關(guān)的處理

延遲的方法(二種)

一是后讀或后寫指令及其后的指令停止流動，即使指令j及其后的指令停止在流水線中流動，當(dāng)指令h流過相應(yīng)操作段后，指令j及其后的指令才繼續(xù)流動。這種方法保證了順序流動，且控制實(shí)現(xiàn)比較簡單，也不需要對流水線作任何改進(jìn)，但是降低了流水線的吞吐率和效率。

第四節(jié)流水線中的相關(guān)及其處理三、操作數(shù)相關(guān)

3.操作數(shù)相關(guān)的處理

延遲的方法(二種)

另一是為保持流水線連續(xù)流動，則僅使后讀或后寫一條指令停止流動，即當(dāng)指令j以后的指令與已進(jìn)入流水線的全部指令之間都沒有相關(guān)時(shí)，完全可以僅使相關(guān)的指令j暫停流動，而其后的指令依次越過指令j繼續(xù)向前流動，即采用異步流動。采用異步流動方式能提高流水線吞吐率和效率，但是容易出現(xiàn)兩種新的相關(guān)問題——“寫后寫”相關(guān)和“先讀后寫”相關(guān)，還要解決超越和新出現(xiàn)的兩種相關(guān)，使控制變得復(fù)雜。第四節(jié)流水線中的相關(guān)及其處理三、操作數(shù)相關(guān)

設(shè)置相關(guān)專用通路的方法在一般程序中，“先寫后讀”相關(guān)出現(xiàn)的概率很大。建立相關(guān)專用通路的方法是在流水線的讀段與寫段之間增加一條專用的數(shù)據(jù)通路，以減少停止流動指令的等待時(shí)間，如圖所示。輸入輸出12讀34567寫8存儲單元

專用通路指令：k（j）ih g （h先寫j后讀相關(guān)）第四節(jié)流水線中的相關(guān)及其處理

設(shè)置相關(guān)專用通路兩種方式：一是設(shè)置運(yùn)算器輸出到輸入端的專用數(shù)據(jù)通路，使上一指令的輸出結(jié)果直接送到運(yùn)算器的一個(gè)輸入鎖存器，如圖所示。另一是利用D型觸發(fā)器建立通用寄存器到運(yùn)算器的直接通路，D型觸發(fā)器可在一個(gè)脈沖觸發(fā)下將輸入端狀態(tài)傳遞給輸出端，這樣可實(shí)現(xiàn)同一個(gè)脈沖觸發(fā)下運(yùn)算器的結(jié)果立即送到相關(guān)的寄存器。

鎖存器

鎖存器通用寄存器運(yùn)算器專用通路第四節(jié)流水線中的相關(guān)及其處理數(shù)據(jù)重定向的方法（1）對于“先寫后讀”操作數(shù)相關(guān)。若先A→B，后B→C，可等效于A→B和A→C，即新增加一條A到C的專用路徑，取消原來B到C的路徑。這樣就可以避免寫讀相關(guān)，或縮短發(fā)生寫讀相關(guān)的時(shí)間，但沒有消除“先寫后讀”相關(guān)。（2）對于“寫后寫”操作數(shù)相關(guān)。若先A→B，后C→B，經(jīng)過數(shù)據(jù)重定向，改為C→B′。引用變量B則改為引用變量B′。這樣就消除了“寫后寫”相關(guān)，即“寫后寫”不存在先后次序的限制了。（3）對于“先讀后寫”操作數(shù)相關(guān)。若先B→A，后C→B，經(jīng)過數(shù)據(jù)重定向，讓B′存B的內(nèi)容，則改為B′→A和C→B。這樣就消除了“先讀后寫”相關(guān)，即“先讀后寫”不存在先后次序的限制了。第四節(jié)流水線中的相關(guān)及其處理例如要執(zhí)行下列程序指令：

k：LOADF1，Ak+1：FADDF1，F(xiàn)2k+2：FMULF1，F(xiàn)3k+3：STOREB，F(xiàn)1

其中：F1、F2、F3為浮點(diǎn)通用寄存器，A、B是主存儲器單元。程序指令執(zhí)行過程中的數(shù)據(jù)流程如圖2-35（a）所示，圖中箭線表示數(shù)據(jù)傳輸路徑。為了處理“先讀后寫”數(shù)據(jù)相關(guān)，專門設(shè)置了A→FADD、FADD→FMUL、FMUL→B三條通路，撤消了F1→FADD和F1→FMUL二條通路。另外，為了處理“寫后寫”數(shù)據(jù)相關(guān)，撤消了A→F1和FADD→F1二條通路，數(shù)據(jù)流程如圖2-35（b）所示。第四節(jié)流水線中的相關(guān)及其處理k+3k+2k+2k+1k+1k+1kFADDABF1FMULF2k+2F3原始數(shù)據(jù)流程k+1k+2k+3k+2k+1k、k+1FADDABF1FMULF2k+2F3數(shù)據(jù)重定向后的數(shù)據(jù)流程

第四節(jié)流水線中的相關(guān)及其處理四、指令相關(guān)

例如以下程序指令：k：storek+1，R0；[k+1]←R0k+1：……

顯然，第k+1條指令內(nèi)容由第k條指令決定。指令相關(guān)是指相近的兩條指令，后面的指令由前面指令的執(zhí)行結(jié)果來決定（修改或產(chǎn)生后面的指令），使得這兩條指令不能同時(shí)在流水線上流動，否則后面的指令是無效的。要判斷是否產(chǎn)生了指令相關(guān)，需要對多條指令地址與多條指令的運(yùn)算結(jié)果地址比較，是極其復(fù)雜的。如果發(fā)現(xiàn)指令相關(guān)，還要讓已取到指令緩沖區(qū)的相關(guān)指令作廢，重新取指令，不僅要化費(fèi)一定的硬件代價(jià)，時(shí)間損失也很大。所以指令相關(guān)的處理方法是在程序中不允許修改指令。第四節(jié)流水線中的相關(guān)及其處理五、變址相關(guān)

例如以下程序指令：k：opB，R0；B←BOPR0k+1：storeR1，B（X＋d）；R1←[（B）＋（X）＋d]k+2：storeR2，B（X）；R2←[（B）＋（X）]其中：R0、R1、R2為通用寄存器，B為基址寄存器，X為變址寄存器。變址相關(guān)是