1、第四章 流水線技術(shù),加快指令執(zhí)行過程的兩種方法：,在設(shè)計中，選用高速的器件、更好的算法及提高指令內(nèi)部的并行程度等措施，可以加快每條指令的解釋過程； 可以通過提高指令間的并行性，使控制結(jié)構(gòu)能并發(fā)地解釋兩條、多條甚至整段程序來加快整個機(jī)器語言程序的解釋過程。,提高處理速度和系統(tǒng)使用效率的三條途徑：,時間重疊 資源重復(fù) 資源共享,CPU工作方式: 順序 重疊 流水,1.順序解釋方式(Sequence)：各條機(jī)器指令之間順序串行地執(zhí)行，執(zhí)行完一條指令后才取出下條指令來執(zhí)行，而且每條機(jī)器指令內(nèi)部的各個微操作也是順序串行地執(zhí)行。,取指令：按指令計數(shù)器的內(nèi)容訪主存，取出該指令送到指令寄存器； 分析：對指令的

2、操作碼進(jìn)行譯碼，按尋址方式和地址字段形成操作數(shù)地址，并用此地址取操作數(shù)，還要為取下條指令提前形成其地址； 執(zhí)行：對操作數(shù)進(jìn)行運(yùn)算、處理或存儲運(yùn)算結(jié)果。,一、 流水線處理概述,第四章 流水線技術(shù),取指令,分析,執(zhí)行,每階段時間為t，共n條指令,優(yōu)點(diǎn)：控制簡單； 缺點(diǎn)：速度慢，機(jī)器各部件的利用率很低。,若取指令、分析和執(zhí)行指令周期都相等，設(shè)為t，則順序解釋n條指令，需時間T=3nt。,如果每個階段所需時間不等，各為t取、t分和t執(zhí)，則順序執(zhí)行n條指令所需時間：,第四章 流水線技術(shù),（1） 流水線處理概念和特點(diǎn) 1、流水線的基本概念,流水線技術(shù)：將一個重復(fù)的時序過程分成若干個子過程，每個子過程都可有

3、效的在其專用功能段上和其它子過程同時執(zhí)行的一種技術(shù)。,流水線的基本結(jié)構(gòu)中主要包括三大部分：鎖存器、時鐘、功能段（站）。 流水線中每個功能段（站）都是由一些執(zhí)行算術(shù)和邏輯功能的組合邏輯線路組成的，它們可以互相獨(dú)立地對流過的信息進(jìn)行某種操作，相鄰兩個功能段（站）由高速鎖存器（latch）隔開，信息在各站間的流動靠同時送到各站的時鐘信號來控制。,二、流水工作方式,第四章 流水線技術(shù),S1,S2,Sk,輸入,輸出,流水線的基本結(jié)構(gòu),。,L L L L L,第四章 流水線技術(shù),如果每個子過程經(jīng)過的時間都是t，則指令的流水線處理過程可用時空圖來描述。,第四章 流水線技術(shù),2、流水線特點(diǎn)： 1）流水一定重疊

4、，比重疊更苛刻。 2）一條流水線通常由多個流水段組成。 3）每段有專用功能部件，各部件順序連接，不斷流。 4）流水線有建立時間、滿載時間、排空時間， 5）各段時間盡量短、一致，不一致時最慢子過程為瓶頸。 6）給出的最大吞吐率等指標(biāo)，為滿負(fù)載最佳指標(biāo)。,建立時間：在流水線開始時有一段流水線填入時間，使得流水線填滿。即第1條指令從流入到流出所需的時間。 正常流動時間：流水線正常工作，各功能段源源不斷滿載工作。 排空時間（釋放時間）：流水線最后一條指令流入后到流出的時間。,流水線的時空圖是描述流水線工作、分析評價流水線效能的重要工具。,第四章 流水線技術(shù),1、流水線的分級：（按處理的級別分級） 操作

5、部件級(arithmetic pipelining)：將復(fù)雜的算邏運(yùn)算組成流水工作方式； 指令級(instruction pipelining) ：把一條指令解釋過程分成多個子過程 ； 處理機(jī)級或宏流水線級(macro pipelining) ：由兩個以上處理機(jī)串行地對同一數(shù)據(jù)流進(jìn)行處理，每個處理機(jī)完成某一專門任務(wù)，各個處理機(jī)所得到的結(jié)果需存放在與下一個處理機(jī)所共享的存儲器中。,（2） 流水線的分級、分類,第四章 流水線技術(shù),多功能流水線從一種功能變?yōu)榱硪环N功能時需要重新連接，雖然它對資源的利用率可以較高，應(yīng)用時也較靈活，但它的控制比單功能流水線復(fù)雜得多。因此大多數(shù)流水計算機(jī)主要采用單功能流水

6、線。,2、流水線的分類： 按功能分類：單功能流水線、多功能流水線 單功能流水線(unifunction pipelining)：只能實(shí)現(xiàn)一種固定的專門功能的流水線（如CRAY-1）。 多功能流水線(multifunction pipelining) ：通過各站間的不同連接方式可以同時或不同時地實(shí)現(xiàn)多種功能的流水線（如TI-ASC）。,第四章 流水線技術(shù),按工作方式分類：靜態(tài)流水線、動態(tài)流水線 靜態(tài)流水線(static pipelining)：在同一時間內(nèi)各功能段只能按一種運(yùn)算（功能）的連接方式工作。 動態(tài)流水線(dynamic pipelining) ：在同一時間內(nèi)各功能段允許按多種不同運(yùn)算（

7、功能）的連接方式工作。,特點(diǎn)：靜態(tài)流水線僅當(dāng)指令都是同一類型時才能連續(xù)不斷地執(zhí)行。當(dāng)從一種功能方式變?yōu)榱硪环N功能方式時，必須先排空流水線，然后再切換成另一種功能進(jìn)行流水處理。 靜態(tài)流水線的功能不能頻繁地變換，否則它的效率將很低。 動態(tài)流水線可以提高流水線的吞吐率和設(shè)備的利用率。,第四章 流水線技術(shù),按連接方式（流水線中是否有反饋回路）分類：線性流水線、非線性流水線。 線性流水線(linear pipelining) ：從輸入到輸出，每個功能段只允許經(jīng)過一次，不存在反饋回路。一般的流水線均屬于這一類。 非線性流水線(non-linear pipelining) ：存在反饋回路，從輸入到輸出過程中

8、，某些功能段將數(shù)次通過流水線，這種流水線常用于進(jìn)行遞歸運(yùn)算。,第四章 流水線技術(shù),1、TI-ASC算術(shù)運(yùn)算流水線（多功能）,（3） 流水線舉例,第四章 流水線技術(shù),靜態(tài)多功能流水線時-空圖,靜態(tài)流水線：只有當(dāng)進(jìn)入的是一串相同運(yùn)算的指令時，流水的效能才得以發(fā)揮，才能使各個功能段并行地對多條指令的數(shù)據(jù)進(jìn)行流水處理。,第四章 流水線技術(shù),動態(tài)多功能流水線時-空圖,區(qū)別：如果從軟硬功能分配的觀點(diǎn)上來看，靜態(tài)流水線其實(shí)是把功能負(fù)擔(dān)較多地加到軟件上，以簡化硬件；動態(tài)流水線則是把功能負(fù)擔(dān)較多地加在硬件上，以提高流水的效能。,空間 (段號),第四章 流水線技術(shù),（一）VAX8600的流水結(jié)構(gòu) a. I部件：預(yù)

9、取指令，操作碼譯碼，預(yù)取操作數(shù)，并存放運(yùn)算結(jié)果。 b. E部件：執(zhí)行指令。 c. F部件：浮點(diǎn)加速器。 d. M部件：控制CPU和輸入輸出設(shè)備對主存的訪問，有16k字節(jié)的cache和把虛存地址轉(zhuǎn)換成實(shí)存地址的地址轉(zhuǎn)換表（快表）。 e. 操作臺：提供同操作員，引導(dǎo)設(shè)備和遠(yuǎn)程診斷的界面。,指令流水線：一條指令的取指令、譯碼、取操作數(shù)和執(zhí)行等幾個過程能同它前后的指令在時間上重疊，用這種指令重疊的方法構(gòu)成的流水線就是指令流水線，又叫指令先行控制。,2VAX8600和長城386計算機(jī)的指令流水線,第四章 流水線技術(shù),VAX8600的CPU結(jié)構(gòu)圖,第四章 流水線技術(shù),I部件和E部件這兩個互相獨(dú)立的部件組成

10、指令流水線。 I部件與E部件的關(guān)系：I部件有一個8個字節(jié)的指令緩沖寄存器。預(yù)取的操作數(shù)也包括從通用寄存器中的取數(shù)，為此在I部件中還有一組寄存器用作存放16個通用寄存器相同內(nèi)容的副本，E部件在修改通用寄存器內(nèi)容時，也同時自動修改I部件中副本的內(nèi)容。 I部件向E部件（或F部件）提供執(zhí)行所需的操作碼和操作數(shù)，當(dāng)E部件執(zhí)行完后，I部件提供存儲結(jié)果所需的寫數(shù)地址。指令整個工作過程是 流水線化的。,第四章 流水線技術(shù),VAX8600指令流水線的工作順序,實(shí)框：表示CPU在執(zhí)行一條典型的指令時的動作順序。 虛線：表示6個動作是各自分開進(jìn)行的，可以同其它指令的動作并行進(jìn)行。,第四章 流水線技術(shù),內(nèi)部有六個部件

11、 總線接口部件：同外部的接口，讀取指令、讀寫數(shù)據(jù)。 I部件： 指令預(yù)取部件：取指令放在指令預(yù)取隊列中，容量為16個字節(jié)。 指令譯碼部件：形成指令微碼，指令隊列中可放3條指令。 E部件： 執(zhí)行部件：控制部件、數(shù)據(jù)部件、保護(hù)測試部件 分段部件 分頁部件,存儲管理部件,（二）長城386指令流水線,第四章 流水線技術(shù),第四章 流水線技術(shù),（4）流水線性能分析計算,（一）技術(shù)指標(biāo),衡量流水線處理機(jī)的性能主要是吞吐率、加速比和效率。 1吞吐率(TP,Throughput Rate)：單位時間內(nèi)能處理的指令條數(shù)或能輸出的數(shù)據(jù)量。吞吐率越高，計算機(jī)系統(tǒng)的處理能力就越強(qiáng)。就流水線而言，吞吐率就是單位時間內(nèi)能流出

12、的任務(wù)數(shù)或能流出的結(jié)果數(shù)。,第四章 流水線技術(shù),最大吞吐率：流水線達(dá)到穩(wěn)定狀態(tài)后可獲得的吞吐率。 （1）TPmax=1/t（理想情況） （2）TPmax=1/ maxt1，t2，t3，t4,第四章 流水線技術(shù),子過程3為瓶頸段的時空圖,最大吞吐率TPmax=1/3t,第四章 流水線技術(shù),解決瓶頸有兩種方法：,A： B：,第四章 流水線技術(shù),T,重復(fù)設(shè)置瓶頸流水段后的工作時空圖,第四章 流水線技術(shù),實(shí)際吞吐率,設(shè)： m：指令流水線的段數(shù)； t0: 各段經(jīng)過的時間； n：指令條數(shù)。,（1）完成n條指令的解釋共需時間： T=mt0+(n-1) t0,第四章 流水線技術(shù),2. 效率(Efficienc

13、y)：流水線的設(shè)備利用率；即在整個運(yùn)行時間里，流水線的設(shè)備有多少時間是真正用于工作的。直接反映了處理機(jī)結(jié)構(gòu)的有效程度。,各段時間相等：,各段時間不等：,其中， tj為瓶頸段的時間。,第四章 流水線技術(shù),其中，分母為m個段總的加權(quán)時空區(qū)，分子為n個任務(wù)實(shí)際占用的總的加權(quán)時空區(qū)。 從時空圖來看，所謂效率就是n個任務(wù)占用的時空區(qū)和m個段總的時空區(qū)面積之比。,設(shè)備利用率占整個系統(tǒng)設(shè)備利用率的比重不同，可以給每個段賦予不同的“權(quán)”值i，這樣，線性流水線總效率的一般式為：,=,第四章 流水線技術(shù),各段時間相等:,各段時間不等:,3. 加速比(Speedup Ratio)：m段流水線的速度與等效的非流水線的

14、速度之比。,總結(jié)：,若各t 相等： =TP* t,第四章 流水線技術(shù),（二） 實(shí)例分析:性能分析（實(shí)測法, 分析法, 時空圖法） 例1. 四段流水線, t1=t3=t4=t, t2=3t,求4個任務(wù)、10個任務(wù)時的TP，、SP 。,（1）分析法: 各段時間不等（ n =10 ）,第四章 流水線技術(shù),第四章 流水線技術(shù),(2) 時空圖法:,TP=4/(6+3*3) t)=4/(15t)=0.267/t,=6*4 t /(4*15t)=2/5=40%,Sp=4*6t /15t=8/5=1.6,n=4時：,n=10時：同上。,第四章 流水線技術(shù),比較:,n=4 0.267,n=10 0.303,n=

15、100 0.33,40%,45%,50%,1.6,1.8,1.98,Sp,TP(1 / t),m=4,說明:nm時流水性能才發(fā)揮得更好。,第四章 流水線技術(shù),例2.四段浮點(diǎn)加法運(yùn)算器流水線，各段時間相等，計算 Z=A+B+C+D+E+F+G+H，求流水線的吞吐率TP、效率 及加速比Sp ，注意有相關(guān)。,Z=A+B+C+D+E+F+G+H,1,2,3,4,5,6,7,解： TP=7/（15t）= 0.47/ t =7*4/(15*4)=7/15 = 47 Sp=4*7/15=28/15 = 1.87,5,5,5,5,6,6,6,6,7,7,7,7,第四章 流水線技術(shù),例3. ASC計算機(jī)靜態(tài)多功

16、能算術(shù)運(yùn)算流水線各段時間相等，求計算6次浮點(diǎn)加、 5次定點(diǎn)乘的吞吐率、效率及加速比 （m=8,n=11）,第四章 流水線技術(shù),分析：T加=（6+(6-1)）* t = 11t T乘=（4+(5-1)）* t = 8t,則 TP = 11/(（11+8）t） =11/19t=0.58/t =（6*6+5*4）t /(19*8t)=6/52=7/19=36.8 Sp =（6*6+5*4）t /19t = 56t /19t =2.95,第四章 流水線技術(shù),例4：為提高流水線效率用哪兩種主要途徑來克服速度瓶頸？現(xiàn)有3段流水線，各段經(jīng)過時間依次為t、3t、t。 （1）分別計算在連續(xù)輸入3條指令時和30條

17、指令時的吞吐率和效率。 （2）按兩種途徑之一改進(jìn)，畫出你的流水線結(jié)構(gòu)示意圖，同時計算連續(xù)輸入3條指令和30條指令時的吞吐率和效率。 （3）通過對（1）（2）兩小題的計算比較可得出什么結(jié)論？,第四章 流水線技術(shù),解：提高流水線效率，消除速度瓶頸主要有將瓶頸段再細(xì)分以及重復(fù)設(shè)置多個瓶頸段并聯(lián)工作，給其輪流分配任務(wù)的兩種途徑。,（1）在3段流水線，各段經(jīng)過時間依次為t、3t、t的情況下，連續(xù)流入3條指令時，將n=3，m=3，t1=t，t2 =3t，t3=t，tj=3t代入，可得吞吐率TP和效率為 ：,第四章 流水線技術(shù),連續(xù)流入30條指令時，只需將上式中的n改為30，其它參數(shù)不變。,（2）若采取將第

18、2段細(xì)分成3個子段，每個子段均為t，構(gòu)成的流水線結(jié)構(gòu)如圖所示。,t t t t t,段1 段2 段3,第四章 流水線技術(shù),連續(xù)流入3條時，將n=3，m=5，ti= tj= t代入，得,7,3,7,5,5,3,7,5,3,7,3,2,5,3,),1,3,(,3,5,1,5,1,=,D,*,D,=,D,*,D,=,D,=,D,+,D,=,D,-,+,D,=,=,=,t,t,t,t,t,t,t,t,t,TP,i,i,i,i,i,h,= 43%,n=30： TP=0.88t =88%,= 0.43t,第四章 流水線技術(shù),若采取將3個2段并聯(lián)構(gòu)成的流水線，其構(gòu)成如圖所示。 連續(xù)流入3條指令及流入30條指

19、令時的吞吐率Tp和效率所計算的結(jié)果分別與子過程細(xì)分的相同。,3t t 3t t 3t,有瓶頸（1） 消除瓶頸（2） n=3： n=3： TP=0.237t TP=0.43t =45% =43% n=30： n=30： TP=0.326t TP=0.88 t =54% =88%,第四章 流水線技術(shù),（3）將題（1）中n=3和n=30的計算結(jié)果進(jìn)行比較可以看出，只有當(dāng)連續(xù)流入流水線的指令越多時，流水線的實(shí)際吞吐率和效率才會提高。 將（1）（2）題的計算結(jié)果進(jìn)行比較，同樣可以看出，無論采用瓶頸子過程再細(xì)分，還是將多個瓶頸子過程并聯(lián)來消除流水線瓶頸，都只有在連續(xù)流入流水線的指令數(shù)越多時，才能使實(shí)際吞吐

20、率和效率得到顯著的提高。若連續(xù)流入流水線的指令數(shù)越少，消除流水線瓶頸雖可以提高流水線的實(shí)際吞吐率Tp，而效率卻可能下降。,第四章 流水線技術(shù),例5有一個雙輸入端的加-乘雙功能靜態(tài)流水線，由經(jīng)過時間為t、2t、2t、3t的1、2、3、4四個子過程構(gòu)成。加按12 4連接，乘按134連接，流水線輸出設(shè)有數(shù)據(jù)緩沖器，也可將數(shù)據(jù)直接返回輸入。現(xiàn)要執(zhí)行 A*（B+C*（D+E*F）+G*H 的運(yùn)算；（1）請調(diào)整計算順序，畫出能獲得吞吐率盡量高的流水時空圖，標(biāo)出流水線入、出端數(shù)據(jù)的變化情況，求出完成全部運(yùn)算的時間及此期間流水線的效率。（2）如對流水線瓶頸子過程再細(xì)分，最少只需多少時間可完成全部運(yùn)算？（3）若

21、子過程3不能再細(xì)分，只能用并聯(lián)方法改進(jìn)，問流水線的效率為多少？,第四章 流水線技術(shù),結(jié)論：消除瓶頸方法，對較少任務(wù)而言，可減少計算時間，提高吞吐率；但因使用多套設(shè)備、且因靜態(tài)流水線需排空后才可切換功能，因此，可能使效率降低。,注： 消除瓶頸。 功能切換。 數(shù)據(jù)相關(guān)控制。 （1）T=36 t，=38% （2） T=26 t （3） =26%,第四章 流水線技術(shù),分段時間t盡量小、盡量一致，則TP越大； 當(dāng)n m 時，TP=1/ t； 若m太多，需鎖存器也越多，則處理時間長。 2. t選取：各級微操作所需邏輯門的延遲、加走線延遲、再加3%冗余量。 3. 緩沖深度影響（緩沖器個數(shù)）。 4. 非線性流

22、水的合理控制。,（二）相關(guān)處理 定義 ：相近指令出現(xiàn)某種關(guān)聯(lián)而使其不能同時執(zhí)行。 資源相關(guān) 數(shù)據(jù)相關(guān) 控制相關(guān),（5） 流水的控制和設(shè)計 （一）時序和緩沖,第四章 流水線技術(shù),1. 資源相關(guān)（resource dependence）,資源相關(guān)是指當(dāng)有多條指令進(jìn)入流水線后在同一機(jī)器周期內(nèi)爭用同一功能部件所發(fā)生的沖突。,兩條指令同時要用一個乘法器,指 令,流水段,不同類型指令中各流水段進(jìn)行的操作,第四章 流水線技術(shù),兩條指令同時訪存造成資源相關(guān),沖突,取指 譯碼 執(zhí)行 訪存 寫回,例2：,第四章 流水線技術(shù),（1）使i+3指令停頓一拍進(jìn)入流水線，以解決訪存相關(guān)。 （2）重復(fù)設(shè)置一個存儲器。,解決方

23、法：,第四章 流水線技術(shù),流水線順序流動方式：流水線輸出端任務(wù)的流出順序和輸入端的流入順序一致。 流水線亂序流動方式（異步流動方式、不按順序流動方式）：流水線輸出端任務(wù)的流出順序和輸入端的流入順序可以不一致。,2. 數(shù)據(jù)相關(guān)（data dependence）,數(shù)據(jù)相關(guān)：當(dāng)一條指令需要用到前面指令的執(zhí)行結(jié)果，而前面的指令均在流水線中重疊執(zhí)行，還未產(chǎn)生相應(yīng)的結(jié)果時，就會引起“數(shù)據(jù)相關(guān)”。,第四章 流水線技術(shù),例：有i 和j兩條指令，i指令在前，j指令在后，則可能發(fā)生三種不同類型的數(shù)據(jù)相關(guān)： RAW(Read After Write) (先寫后讀)（寫讀：WR）相關(guān) - 指令 j 試圖在指令 i 寫

24、入寄存器前就讀出該寄存器內(nèi)容，這樣，指令j就會錯誤地讀出該寄存器舊的內(nèi)容。 如：i: R1+R2-R3 j: R3*R4-R5,數(shù)據(jù)相關(guān)例,順序流動,第四章 流水線技術(shù),WAR (Write After Read) (先讀后寫)（讀寫：RW）相關(guān)- 指令 j 試圖在指令 i讀出寄存器之前就寫入該寄存器，這樣，指令i就錯誤地讀得該寄存器新的內(nèi)容。 如：i: R3*R4-R5 j: R1+R2-R3,不按順序流動,WAW (Write After Write) (先寫后寫)（寫寫：WW）相關(guān)- 指令j試圖在指令i寫寄存器之前就寫入該寄存器，這樣，兩次寫的先后次序被顛倒，就會錯誤地使由指令i寫入的值

25、成為該寄存器內(nèi)容。 如：i: R1*R2-R3 j: R4+R5-R3,不按順序流動,第四章 流水線技術(shù),例1：如果流水線要執(zhí)行以下的兩條指令： X3=X1-X2 X5=X3+X4,這是一個典型的先寫后讀的（RAW）寫讀相關(guān)。,例2：結(jié)果寄存器的沖突： X3=X4/X5 X3=X1-X2,這是個先寫后寫的（WAW）寫寫相關(guān)，兩條指令都要用X3存放結(jié)果，此時第二條指令要等待第一條指令完成后才能寫。,第四章 流水線技術(shù),解決數(shù)據(jù)相關(guān)的方法：（可采用軟件和硬件技術(shù)） 時間推后法 旁路技術(shù)或相關(guān)專用通路技術(shù)（定向技術(shù)） 定向技術(shù)：將一個計算結(jié)果直接傳送到所有需要它的功能單元的輸入端。,例3：一條指令要

26、把結(jié)果存放到上一條指令存放操作數(shù)的寄存器中時發(fā)生的沖突。 X1=X2*X3 X3=X0-X4,這是個先讀后寫的（WAR）讀寫相關(guān)。如果這兩條指令接連地送到乘法功能部件和加法功能部件中，由于加法比乘法快得多，第二條的結(jié)果X3先產(chǎn)生，但必須等待第一條指令做完后才能送X3。,第四章 流水線技術(shù),IF,ID,EX,MEM,WB,IF,ID,EX,MEM,WB,IF,ID,EX,MEM,WB,IF,ID,EX,MEM,WB,IF,ID,EX,MEM,WB,ADD R1,R2,R3,SUB R4,R1,R5,AND R6,R1,R7,OR R8,R1,R9,XOR R10,R1,R11,定向傳遞R1值,數(shù)

27、據(jù)相關(guān)和定向傳遞指令,例：五段流水線的數(shù)據(jù)相關(guān)及采用定向技術(shù)解決此相關(guān)。,第四章 流水線技術(shù),IF,EX,MEM,ID,R,IF,EX,MEM,ID,R,W,IF,EX,MEM,ID,R,W,IF,EX,MEM,ID,R,IF,EX,MEM,ID,R,ADD R1,R2,R3,SUB R4,R1,R5,AND R6,R1,R7,OR R8,R1,R9,XOR R10,R1,R11,定向傳遞R1值,減少定向傳送次數(shù)的方法,第四章 流水線技術(shù),定向傳送及具有旁路的ALU,第四章 流水線技術(shù),控制相關(guān)（control dependence） 控制相關(guān)主要由無條件轉(zhuǎn)移和條件轉(zhuǎn)移引起。 （轉(zhuǎn)移指令概率占

28、1/4左右，不可忽視） 解決控制相關(guān)主要使用的技術(shù)： 加快和提前形成條件碼：有的指令的條件碼并不一定要等執(zhí)行完畢得到運(yùn)算結(jié)果后才能形成； 靜態(tài)轉(zhuǎn)移預(yù)測技術(shù)：在硬件和軟件設(shè)計完成后，轉(zhuǎn)移預(yù)測方向則確定。 猜測法：按一個方向流水，預(yù)測成功或不成功方向； 預(yù)取轉(zhuǎn)移目標(biāo)：向兩個分支方向預(yù)取指令； 加快短循環(huán)程序處理 ：設(shè)置特殊循環(huán)指令、利用硬件向后檢測若干條指令（IBM360/91：向后檢測8條）；,第四章 流水線技術(shù),流水機(jī)器的中斷處理 流水機(jī)器處理中斷的關(guān)鍵不在于如何縮短斷流時間，而是如何處理好斷點(diǎn)現(xiàn)場及中斷后的恢復(fù)問題。 不精確斷點(diǎn)法(同外部設(shè)備中斷處理一樣)：不論第i條指令在流水線的哪一段發(fā)出

29、中斷申請，都不再允許那時還未進(jìn)入流水線的后續(xù)指令再進(jìn)入，允許已流入的指令執(zhí)行完；現(xiàn)場是最后一條指令的。 精確斷點(diǎn)法：不論第i條指令是在流水線中哪一段發(fā)的中斷申請，給中斷處理程序的現(xiàn)場全都是對應(yīng)第i條的，在第i條之后進(jìn)入流水線的指令的原有現(xiàn)場都能恢復(fù) (增加設(shè)備，增加后援R，保存流水線內(nèi)各條指令的原有狀態(tài)） 。,第四章 流水線技術(shù),（1） 先進(jìn)的流水調(diào)度方法 - 動態(tài)調(diào)度,靜態(tài)調(diào)度：借助軟件對指令執(zhí)行順序進(jìn)行調(diào)度，以減少由于流水線中存在相關(guān)沖突而引起流水線的停頓時間。目前比較流行。 動態(tài)調(diào)度：通過硬件重新安排指令的執(zhí)行順序以減少流水的停頓。,優(yōu)點(diǎn)： （1）能處理某些在編譯時無法知道的相關(guān)情況；

30、（2）能簡化編譯程序設(shè)計； （3）使代碼有可移植性。 缺點(diǎn)：相應(yīng)的硬件較為復(fù)雜。,三、先進(jìn)的流水技術(shù),第四章 流水線技術(shù),（2） 非線性流水線的沖突及調(diào)度,非線性流水線的沖突：由于段間設(shè)置有反饋回路，一個任務(wù)在流水的整個執(zhí)行過程中可能會多次通過同一流水段，因此不能每拍均向流水線送入新任務(wù)。若仍每拍送入一個新任務(wù)，則在某些時刻會發(fā)生幾個任務(wù)同時爭用同一流水段的現(xiàn)象，即產(chǎn)生功能段的使用沖突。 解決方法：間隔恰當(dāng)?shù)呐臄?shù)后再向流水線送入下一個任務(wù)。這就需要對流水線作適當(dāng)?shù)恼{(diào)度。 流水線調(diào)度解決的問題：間隔幾拍再向流水線送入下一個任務(wù)，才不發(fā)生功能段使用沖突。,第四章 流水線技術(shù),流水線調(diào)度常借助于二維

31、預(yù)約表和狀態(tài)轉(zhuǎn)換圖來進(jìn)行分析。 二維預(yù)約表（也稱預(yù)約表：Reservation Table ）：流水線各段的時間關(guān)系表。反映一個任務(wù)使用各段所需間隔的拍數(shù)。,根據(jù)預(yù)約表可較容易地推算出一個任務(wù)執(zhí)行時，各段所需 間隔的周期拍數(shù)。,1、預(yù)約表,設(shè)：非線性、單功能流水線P，由K段組成，每個任務(wù)流過流水線需N個時鐘周期（t1,t2,tn），段為縱坐標(biāo)，時間為橫坐標(biāo)。,第四章 流水線技術(shù),二維預(yù)約表,圖中每一行代表P的一個段，每一列表示相應(yīng)的時鐘周期（節(jié)拍）。若某個任務(wù)在周期ti需要使用Sj段進(jìn)行處理，則在行Sj和列ti 的相交處以“X”（ “” ）表示。,第四章 流水線技術(shù),禁止表F=1，5，6，8,

32、表明：要想使流入的任務(wù)不發(fā)生同時爭用功能段的情況，相鄰兩個任務(wù)進(jìn)入流水線的間隔拍數(shù)就一定不能為1、5、6、8拍。 即：非線性流水線的禁止啟動距離為：1、5、6、8拍。,2、禁止表F（Forbidden List）：非線性流水線中，各段對一個任務(wù)流過時會重復(fù)使用同一個功能段的節(jié)拍（時鐘周期）間隔數(shù)的集合。即表示：禁止使用此集合中的間隔拍數(shù)向流水線送入任務(wù)。,第四章 流水線技術(shù),3、沖突向量C（Collision Vector）（或稱位向量）： C=(CnCn-1. C2 C1) 其中第i位的狀態(tài)表示與當(dāng)時相隔 i 拍時間間隔，給流水線送入后繼任務(wù)是否會發(fā)生功能段的使用沖突。 若不會發(fā)生沖突：令該

33、位為“0”，即Ci=0, 表示允許送入； 若會發(fā)生沖突：令該位為“1”，即Ci=1, 表示禁止送入。 沖突向量C的位數(shù)n：為最大禁止間隔數(shù)。 例：禁止表F=1，3，6，則n 為6，可構(gòu)成6位沖突向量C： C = （100101） 前例中禁止表F=1，5，6，8，則可形成8位沖突向量C： C = （10110001）,第四章 流水線技術(shù),原始（初始）沖突向量：第1個 任務(wù)第1拍流入流水線時的沖突向量（可從禁止表F生成）。 從沖突向量C=（10110001）可知，隔2、3、4、7拍可送入新任務(wù)（第2個任務(wù)）。 但當(dāng)新任務(wù)（第2個任務(wù)）送入后，應(yīng)當(dāng)產(chǎn)生新的沖突向量，以便決定下一個（第3個）任務(wù)可進(jìn)入

34、的時刻。,第四章 流水線技術(shù),新的沖突向量的產(chǎn)生方法：若某任務(wù)K是在上一個任務(wù)間隔2拍時送入流水線，則把上一個任務(wù)當(dāng)時的沖突向量向右移2位（左邊空位補(bǔ)0），與當(dāng)前任務(wù)K的原始沖突向量按位“或”。 例：原始沖突向量C=（10110001） 選擇第2個任務(wù)在間隔3拍時流入：3：00010110 V 10110001（原始） 10110111（新） 選擇第3個任務(wù)在間隔4拍時流入：4：00001011 V 10110001（原始） 10111011（新）,第四章 流水線技術(shù),4、狀態(tài)轉(zhuǎn)移圖： 從原始沖突向量開始，選擇可輸入任務(wù)的節(jié)拍向流水線輸入新任務(wù)，產(chǎn)生新的沖突向量。按新的沖突向量流入新任務(wù)，又可

35、產(chǎn)生新的沖突向量，一直進(jìn)行到不再產(chǎn)生不同的沖突向量為止。按此，可畫出用沖突向量表示的狀態(tài)圖。圖中兩個沖突向量之間用有向弧上的數(shù)字表示引入后繼任務(wù)產(chǎn)生其新的沖突向量所用的間隔拍數(shù)。,非線性流水線預(yù)約表相應(yīng)狀態(tài)圖,禁止表F=1，5，6，8,第四章 流水線技術(shù),過程: 1. 按給出的預(yù)約表寫出禁止表 F=1，5，6，8；,2. 寫出n位初始沖突向量（10110001）；,3. 按禁止表約束條件列出新的沖突向量，直到不再生成新的沖突 向量為止（當(dāng)前沖突向量和初始沖突向量按位“或”）；,4. 畫出用沖突向量表示的流水線狀態(tài)轉(zhuǎn)移圖；,5. 列出按流水線狀態(tài)轉(zhuǎn)移圖中任何一個閉合回路進(jìn)行流水線調(diào)度的方法。 6

36、. 求出各種調(diào)度方法的平均間隔拍數(shù)（平均延遲、平均等待時間）；,7. 求出最佳等間隔和非等間隔調(diào)度拍數(shù)；,第四章 流水線技術(shù),非線性流水線預(yù)約表相應(yīng)狀態(tài)圖,調(diào)度策略 ： 平均間隔拍數(shù)： 非等間隔（2，2，7） （2+2+7）/ 3 = 3. 67 （3，4） （3+4）/ 2 = 3. 5 等間隔（7） 7,本例子中最佳非等間隔調(diào)度為（3，4），即：3拍，4拍，. 平均間隔為3.5拍，而等間隔調(diào)度為7拍。,第四章 流水線技術(shù),例：在一個4段非線性流水線處理機(jī)上需經(jīng)7拍才能完成一個任務(wù)，其預(yù)約表如表所示。分別寫出延遲禁止表F、沖突向量C；畫出流水線狀態(tài)轉(zhuǎn)移圖；求出最小平均延遲、流水線的最大吞吐率

37、及其調(diào)度時的最佳方案。按此流水調(diào)度方案，輸入6個任務(wù)，求實(shí)際的吞吐率。,解：延遲禁止表F=2，4，6 初始沖突向量C=（101010）,5、單功能流水線的調(diào)度控制：用狀態(tài)轉(zhuǎn)移圖對流水線進(jìn)行調(diào)度，控制產(chǎn)生等間隔或不等間隔的調(diào)度策略。,第四章 流水線技術(shù),各種調(diào)度方案及其相應(yīng)的平均延遲：,第四章 流水線技術(shù),由上表可知，最小的平均延遲為4拍。此時流水線的最大吞吐率： TPmax=1/4（任務(wù)/拍） 最小平均延遲調(diào)度方案有（1，7）、（3，5）兩種非等間隔周期性調(diào)度方案。 按（1，7）調(diào)度方案輸入6個任務(wù)，全部完成的時間為： 1+7+1+7+1+7=24拍 實(shí)際吞吐率 TP=6/24（任務(wù)/拍）=0

38、.25 （任務(wù)/拍）,第四章 流水線技術(shù),若按（3，5）調(diào)度方案輸入6個任務(wù)，全部完成的時間為： 3+5+3+5+3+7=26拍 實(shí)際吞吐率 TP=6/26（任務(wù)/拍） =0.23 （任務(wù)/拍） 若按（5，3）調(diào)度方案輸入6個任務(wù)，全部完成的時間為： 5+3+5+3+5+7=28拍 實(shí)際吞吐率 TP=6/28（任務(wù)/拍） =0.21 （任務(wù)/拍） 可見最佳方案應(yīng)當(dāng)為（1，7）調(diào)度方案，輸入6個任務(wù)的實(shí)際吞吐率比其它方案更高些。,第四章 流水線技術(shù),粗粒度并行性：在多處理機(jī)上分別運(yùn)行多個進(jìn)程，由多臺處理機(jī)合作完成一個程序；,單發(fā)射結(jié)構(gòu)的RISC：RISC機(jī)的體系結(jié)構(gòu)關(guān)鍵技術(shù)是精心的流水線設(shè)計和優(yōu)

39、化的編譯技術(shù)，使得每個周期能夠發(fā)射一條指令。它的CPI1（由于有相關(guān)等影響），這種結(jié)構(gòu)稱為單發(fā)射結(jié)構(gòu)的RISC。,細(xì)粒度并行性：指在一個進(jìn)程中進(jìn)行操作一級或指令一級的并行處理。RISC機(jī)進(jìn)一步開發(fā)細(xì)粒度并行性?，F(xiàn)在新的系統(tǒng)結(jié)構(gòu)設(shè)計，基本思想是要挖掘指令級的并行性，使單處理機(jī)達(dá)到一個時鐘周期完成多條指令。,對一個周期能發(fā)射多條指令計算機(jī)有超標(biāo)量、超流水、超長指令字計算機(jī)，此外還有數(shù)據(jù)流計算機(jī)也屬于多發(fā)射結(jié)構(gòu)。,四、流水中指令級并行性的進(jìn)一步開發(fā),第四章 流水線技術(shù),（1） 超級標(biāo)量計算機(jī),超標(biāo)量（Superscalar）計算機(jī)：每個時鐘周期內(nèi)能同時發(fā)射（啟動）多條指令的計算機(jī)。,主要特點(diǎn)： （1

40、）配置有多個性能不同的處理部件，采用多條流水線并行處理。 （2）能同時對若干條指令進(jìn)行譯碼，將可并行的指令送往不同的執(zhí)行部件，從而達(dá)到每個周期啟動多條指令。 （3）在程序運(yùn)行期間由硬件（通常是狀態(tài)記錄部件和調(diào)度部件）完成指令調(diào)度。,（4）超級標(biāo)量機(jī)的硬件是不能重新安排指令的前后次序的，但可以在編譯程序中采取優(yōu)化的辦法，事先在編譯時對指令的執(zhí)行次序進(jìn)行精心安排，把能并行執(zhí)行的指令搭配起來，挖掘更多的指令并行性。 （5）超級標(biāo)量處理機(jī)特別適合于求解象稀疏矩陣這樣的復(fù)雜標(biāo)量問題。,第四章 流水線技術(shù),每拍啟動3條指令 并行度=3,超級標(biāo)量機(jī),1超級標(biāo)量計算機(jī)的原理：,第四章 流水線技術(shù),2. 超標(biāo)量

41、流水線調(diào)度Cyclone計算機(jī),超標(biāo)量流水線的指令調(diào)度策略： 按序發(fā)射按序完成 按序發(fā)射無序完成 無序發(fā)射無序完成 無論那種調(diào)度策略，都要保證程序運(yùn)行的最終結(jié)果是正確的。 Pentium處理器采用的是按序發(fā)射按序完成策略。 PentiumII/III處理器采用的是按序發(fā)射無序完成。,指令發(fā)射：啟動指令進(jìn)入流水線的過程。 指令發(fā)射策略：指令發(fā)射所使用的協(xié)議或規(guī)則。 按序發(fā)射（in-order issue）：指令按原有次序發(fā)射。 無序發(fā)射或亂序發(fā)射（out-of-order issue）：將具有相關(guān)的指令推后發(fā)射，而將后面的無相關(guān)性的指令提前發(fā)射，即不按程序原有次序發(fā)射指令。,第四章 流水線技術(shù),

42、超長指令字（VLIW：Very Long Instruction Word）：由編譯程序在編譯時找出指令間潛在的并行性，進(jìn)行適當(dāng)調(diào)度安排，把多個能并行執(zhí)行的操作組合在一起，成為一條具有多個操作段的超長指令字。 在VLIW機(jī)器中，采用多個獨(dú)立的功能部件，以一條長指令（利用其中每個操作段）控制實(shí)現(xiàn)多個操作的并行執(zhí)行（相當(dāng)于同時執(zhí)行多條指令），減少存儲器訪問。,主要特點(diǎn)： （1）單一的控制流。只有一個控制器，每個周期啟動一條指令。 （2）超長指令字被分成多個控制字段，每個字段直接獨(dú)立地控制每個功能部件。 （3）含有大量的數(shù)據(jù)通路和功能部件，由于編譯器在編譯時間已考慮可能出現(xiàn)的數(shù)據(jù)相關(guān)和資源相關(guān)，故控

43、制硬件較簡單。 （4）在編譯階段完成超長指令中多個可并行執(zhí)行操作的調(diào)度。,（2） 超長指令字計算機(jī)（VLIW）,第四章 流水線技術(shù),每拍啟動一條長指令，執(zhí)行3個操作，相當(dāng)于3條指令，并行度=3。,超長指令字計算機(jī)（VLIW）,超長指令字計算機(jī)的例子：Cycra 5計算機(jī),第四章 流水線技術(shù),（3） 超級流水線計算機(jī),即：超流水結(jié)構(gòu)是把每一個功能段流水級（一個基本時鐘周期）分成多個（例如3個）子流水級（多個超流水線機(jī)器周期）；而在每一個子流水級中取出的仍只有一條指令，但總的來看，在一個基本時鐘周期內(nèi)取出了三條指令。,硬件結(jié)構(gòu)特點(diǎn)：對于超流水線結(jié)構(gòu)，其中指令部件可以只有一套，也可以有多套獨(dú)立的執(zhí)行

44、部件。雖然每個機(jī)器周期只能流出一條指令，但它的周期比其它機(jī)器短，一臺m度的超級流水線計算機(jī)的周期為一般機(jī)器周期的1/m，它的一個操作需要m個周期，因而在流水線能充分發(fā)揮作用時，其并行度能達(dá)到m。,超流水線（Super Pipelining）計算機(jī)：每個時鐘周期內(nèi)能分時發(fā)射（啟動）多條指令的計算機(jī)。,第四章 流水線技術(shù),并行度=3： 每1/3拍啟動一條指令,超級流水線的原理結(jié)構(gòu)圖,第四章 流水線技術(shù),這種方法主要通過提高流水線運(yùn)行速度來增強(qiáng)機(jī)器性能。為提高運(yùn)行速度，必須要加深流水深度，既增加流水段數(shù)，以減少每一段的延遲時間，這樣就可加快流水線的運(yùn)行頻率。 例：MIPS公司的64位RISC計算機(jī)R

45、4000超級流水處理機(jī)，分8段：取指1（IF），取指2（IS），讀RF，執(zhí)行（EX），取數(shù)1（DF），取數(shù)2（ DS），標(biāo)記檢查（TC），寫RF（WB）。,第四章 流水線技術(shù),（4） 超標(biāo)量超流水計算機(jī),把超標(biāo)量技術(shù)與超流水技術(shù)結(jié)合在一起，這就是超標(biāo)量超流水線處理機(jī)。超標(biāo)量超流水線處理機(jī)在一個時鐘周期內(nèi)要發(fā)射指令n次，每次發(fā)射指令m條，因此，超標(biāo)量超流水線處理機(jī)每個時鐘周期總共要發(fā)射指令m*n條。,超標(biāo)量超流水線處理機(jī)的指令執(zhí)行時空圖,第四章 流水線技術(shù),Pentium流水線結(jié)構(gòu)（五級雙流水線） 一個周期發(fā)射兩條整數(shù)指令,1、Pentium的超標(biāo)量流水線,（5） 奔騰系列處理機(jī)流水處理,第四章

46、 流水線技術(shù),結(jié)構(gòu)特點(diǎn)：Pentium是超標(biāo)量結(jié)構(gòu)，它可以并行地在一個周期內(nèi)執(zhí)行兩條整數(shù)指令。 Pentium的兩個整數(shù)流水線分別稱為“U”和“V”，而并行發(fā)射兩條指令稱為“成對”。 U管道可執(zhí)行IntelX86體系結(jié)構(gòu)中的任何指令，而V管道只可執(zhí)行“指令成對法則”中規(guī)定的“簡單”指令。當(dāng)指令是成對的，發(fā)給V管道的指令永遠(yuǎn)是發(fā)給U管道的那條指令后的順序的下一條指令。,2、PentiumCPU的體系結(jié)構(gòu),第四章 流水線技術(shù),(2)分立的指令CACHE和數(shù)據(jù)CACHE 不僅使指令預(yù)取和數(shù)據(jù)讀寫能無沖突地同時完成，而且可同時與U、V兩條流水線分別交換數(shù)據(jù)。,(3)重新設(shè)計的浮點(diǎn)運(yùn)算部件 執(zhí)行過程是分

47、為8段的流水線。前4段為指令預(yù)?。≒F）、指令譯碼（D1）、地址生成（D2）、取操作數(shù)（EX），在U、V流水線完成；后4段為執(zhí)行1（X1）、執(zhí)行2（X2）、結(jié)果寫回寄存器堆（WF）、錯誤報告（ER），在浮點(diǎn)運(yùn)算部件中完成。一般情況下，只能由U流水線完成一條浮點(diǎn)操作指令；少數(shù)情況下，V流水線也能同時完成一條如浮點(diǎn)數(shù)交換這樣的指令。,(4)以設(shè)置轉(zhuǎn)移目標(biāo)緩存器BTB方式實(shí)現(xiàn)動態(tài)轉(zhuǎn)移預(yù)測 Pentium采用動態(tài)轉(zhuǎn)移預(yù)測技術(shù)，來減少由于控制相關(guān)性引起的流水線性能損失 。,(1)超標(biāo)量流水線 超標(biāo)量流水線是Pentium系統(tǒng)結(jié)構(gòu)的核心。它的U和V兩條指令流水線都有自己的ALU、地址生成電路和與數(shù)據(jù)cac

48、he的接口。U、V流水線采用的是按序發(fā)射、按序完成的調(diào)度策略。,第四章 流水線技術(shù),例如：向量計算：A*(B+C) 的循環(huán)程序,用FORTRAN語言為 ： Do 10 I=1,n 10 D（I）=A（I）*（B（I）+C（I）,1.水平處理法(橫向) d1=a1*(b1+c1) d2=a2*(b2+c2) dn=an*(bn+cn),2.垂直處理法（縱向） Bi+CiEi(i=1到n) Ai*EiDi(i=1到n),適合于流水處理,（1） 向量處理方式,五、 向量的流水處理,第四章 流水線技術(shù),3.分組縱橫處理法 分成k組, 每組長度為m，組內(nèi)垂直處理，組間水平處理。 n=k*m+r (r為第

49、k+1組剩余分量) Bi+CiEi (1到m) Bi+CiEi (m+1到2m) Ei*AiDi (1到m) Ei*AiDi (m+1到2m) ,（2） 向量處理機(jī)的結(jié)構(gòu),向量（流水）處理機(jī)（Vector Processor）：由向量數(shù)據(jù)表示和流水線技術(shù)相結(jié)合構(gòu)成的向量流水處理機(jī)。,第四章 流水線技術(shù),一、存儲器存儲器型結(jié)構(gòu),參加運(yùn)算的向量數(shù)據(jù)在存儲器中，運(yùn)算的結(jié)果也送到存儲器中。 例：向量加法 C=A+B,存儲器,A,B,C,流水線運(yùn)算部件,存儲器-存儲器型結(jié)構(gòu) （一種能實(shí)現(xiàn)兩個向量相加的流水結(jié)構(gòu)的加法器）,第四章 流水線技術(shù),A、B、C的向量長度為8，加法流水線分為4個功能段，主存儲器采取

50、了8個存儲體，多體交叉訪問，如果不出現(xiàn)存儲體沖突，帶寬將是單體存儲器的8倍。,改進(jìn)多存儲模塊結(jié)構(gòu),第四章 流水線技術(shù),C=A+B向量處理時序圖,第四章 流水線技術(shù),二、寄存器寄存器型（如CRAY_1機(jī)）,原理：在運(yùn)算部件中設(shè)置多個向量寄存器，需要進(jìn)行向量處理時，先執(zhí)行存儲器取指令，將向量數(shù)據(jù)傳送至向量寄存器中，流水線運(yùn)算部件由向量寄存器提供數(shù)據(jù)、處理后的結(jié)果也送至向量寄存器中。Cray-1向量計算機(jī)就是一個典型的寄存器寄存器型。,結(jié)構(gòu)： （1）Cray-1機(jī)的主存儲器容量為8M字節(jié)，包含64個存儲模塊。 （2）Cray-1機(jī)設(shè)置了8個向量寄存器組（V0-V7)，每個寄存器組包含64個向量R，每個R為64位； Vi 最多可存64位。 （3）8個64位標(biāo)量寄存器。 （4）8個24位地址寄存器。 （5）256個長度為16位的指令緩沖寄存器。 （6）機(jī)器的運(yùn)算部件，采用獨(dú)立的多個功