計算機系統(tǒng)結構課件：第四章 流水線技術

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

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

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

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

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

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

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

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

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

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

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

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

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

14、速度之比。,總結：,若各t 相等： =TP* t,第四章 流水線技術,（二） 實例分析:性能分析（實測法, 分析法, 時空圖法） 例1. 四段流水線, t1=t3=t4=t, t2=3t,求4個任務、10個任務時的TP，、SP 。,（1）分析法: 各段時間不等（ n =10 ）,第四章 流水線技術,第四章 流水線技術,(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時：同上。,第四章 流水線技術,比較:,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ā)揮得更好。,第四章 流水線技術,例2.四段浮點加法運算器流水線，各段時間相等，計算 Z=A+B+C+D+E+F+G+H，求流水線的吞吐率TP、效率 及加速比Sp ，注意有相關。,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,第四章 流水線技術,例3. ASC計算機靜態(tài)多功

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

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

18、2段細分成3個子段，每個子段均為t，構成的流水線結構如圖所示。,t t t t t,段1 段2 段3,第四章 流水線技術,連續(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,第四章 流水線技術,若采取將3個2段并聯(lián)構成的流水線，其構成如圖所示。 連續(xù)流入3條指令及流入30條指

19、令時的吞吐率Tp和效率所計算的結果分別與子過程細分的相同。,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%,第四章 流水線技術,（3）將題（1）中n=3和n=30的計算結果進行比較可以看出，只有當連續(xù)流入流水線的指令越多時，流水線的實際吞吐率和效率才會提高。 將（1）（2）題的計算結果進行比較，同樣可以看出，無論采用瓶頸子過程再細分，還是將多個瓶頸子過程并聯(lián)來消除流水線瓶頸，都只有在連續(xù)流入流水線的指令數(shù)越多時，才能使實際吞吐

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

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

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

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

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

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

26、把結果存放到上一條指令存放操作數(shù)的寄存器中時發(fā)生的沖突。 X1=X2*X3 X3=X0-X4,這是個先讀后寫的（WAR）讀寫相關。如果這兩條指令接連地送到乘法功能部件和加法功能部件中，由于加法比乘法快得多，第二條的結果X3先產(chǎn)生，但必須等待第一條指令做完后才能送X3。,第四章 流水線技術,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ù)相關和定向傳遞指令,例：五段流水線的數(shù)據(jù)相關及采用定向技術解決此相關。,第四章 流水線技術,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ù)的方法,第四章 流水線技術,定向傳送及具有旁路的ALU,第四章 流水線技術,控制相關（control dependence） 控制相關主要由無條件轉移和條件轉移引起。 （轉移指令概率占

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

48、he的接口。U、V流水線采用的是按序發(fā)射、按序完成的調度策略。,第四章 流水線技術,例如：向量計算：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） 向量處理方式,五、 向量的流水處理,第四章 流水線技術,3.分組縱橫處理法 分成k組, 每組長度為m，組內垂直處理，組間水平處理。 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） 向量處理機的結構,向量（流水）處理機（Vector Processor）：由向量數(shù)據(jù)表示和流水線技術相結合構成的向量流水處理機。,第四章 流水線技術,一、存儲器存儲器型結構,參加運算的向量數(shù)據(jù)在存儲器中，運算的結果也送到存儲器中。 例：向量加法 C=A+B,存儲器,A,B,C,流水線運算部件,存儲器-存儲器型結構 （一種能實現(xiàn)兩個向量相加的流水結構的加法器）,第四章 流水線技術,A、B、C的向量長度為8，加法流水線分為4個功能段，主存儲器采取

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