計算機體系結構第三章-1

第三章流水線技術

主要內容3.1重疊執行和先行控制3.2流水線的基本概念3.3流水線的性能指標3.4流水線的相關與沖突

3.5流水線的實現引入提高計算機性能（速度）的兩個重要方法：

1.縮短執行每條指令所需的平均周期數CPI。如：RISC技術

2.提高處理機在執行指令中的并行度，即同一時刻中處理機內同時運行多條指令。如：采用流水線技術第三章流水線技術3.1重疊執行和先行控制3.1重疊執行和先行控制一.指令的重疊執行一條指令的執行過程可以粗略地分為：取指令、分析和執行三個階段，且這個次序是不能改變的。取指令執行分析tTi用Ti表示執行一條指令所需的時間，可以寫成：

Ti=t取指令

+t分析

+t執行3.1重疊執行和先行控制

如果連續執行多條指令（一段程序），計算機對前后相鄰指令的執行過程可以有兩種不同的方式:1.順序執行方式，即等前一條指令執行完畢，緊接著執行下一條指令。取指分析執行取指分析執行k+1k如果取指令、指令分析和指令執行的時間相等，都是t，則n條指令順序執行的時間為：T=3nt

優：控制簡單。缺：速度慢；功能部件利用率低。3.1重疊執行和先行控制一次重疊執行方式：取指分析執行取指分析執行取指分析執行第k條指令第k+1條指令第k+2條指令如果三個階段所需時間t相等，n條指令順序執行的時間為：T=(1+2n)t2.讓前后連續的指令在處理機內以重疊的方式執行.優：總執行時間減少近

1/3；功能部件利用率提高。缺：需增加硬件；控制過程更復雜。

二次重疊執行方式：取指k分析k執行k取指k+1分析k+1執行k+1取指k+2分析k+2執行k+2第k條指令第k+1條指令第k+2條指令如果三個階段所需時間t相等，n條指令順序執行的時間為：T=（2+n)t優：總執行時間減少近

2/3；功能部件利用率進一步提高。缺：增加硬件；主存沖突。3.1重疊執行和先行控制3.1重疊執行和先行控制二.先行控制技術1．實現重疊執行存在的問題（1）問題一： 需要獨立的取指部件，分析部件，執行部件。解決方案:

分別設置對應存儲控制器，指令控制器和運算控制器。3.1重疊執行和先行控制（2）問題二：

主存訪問沖突取指令，處理機按指令計數器PC的指示訪問存儲器；分析指令，可能需要從存儲器中獲取操作數；執行指令，可能要求將結果寫回到存儲器中。處理機中三個獨立的部件可能同時提出對存儲器讀寫的請求，從而發生存儲器訪問沖突。3.1重疊執行和先行控制解決方案：1）分別設置兩個獨立的存儲器：指令存儲器和數據存儲器，或一級Cache分為程序Cache和數據Cache，同時工作解決同時讀指令和讀數據引起的沖突。程序空間和數據空間相互獨立并具有獨立的指令總線和數據總線的系統結構就稱為哈佛結構缺點：結構復雜，需要大量的數據線；對匯編程序員和機器程序員不透明2）多體交叉存儲器結構也可減少沖突的發生。3）先行控制技術是最根本的辦法在主存和指令分析部件之間增設指令緩沖站（先行指令指令緩沖站）先行指令傳沖站組成和工作原理PC1：用于從主存預取指令

每分析完一條指令，就自動向指令緩沖站發出取下一條指令的請求。指令取出之后就把指令緩沖站中的該指令作廢。指令緩沖站中存放的指令的條數是動態變化的。

按隊列方式工作。只要指令緩沖站不滿，它就自動地向主存控制器發取指令請求，不斷地預取指令。PC:用來記錄當前正在分析的指令的地址3.1重疊執行和先行控制3.1重疊執行和先行控制問題：在復雜的計算機指令系統中，各種指令在分析和執行階段所需的時間可能有很大的差別。于是，前面對三個階段所需時間t相等的假設就可能不成立，所得到的節約三分之二時間的結論也被動搖了。下圖形象地表示了這種情況所造成的影響。第k條指令分析k執行k第k+2條指令執行k+2分析k+2第k+1條指令分析k+1執行k+1

這種情況可用先行控制技術來緩解。3.1重疊執行和先行控制2．采用先行控制技術的處理機運算控制器

先行指令棧

后行寫數棧

先行讀數棧存儲控制器去主存儲器地址線

指令分析器

先行操作棧運算器通用寄存器3.1重疊執行和先行控制

緩沖站實際上是一個以先進先出（FIFO）方式工作的移位寄存器組，上圖表示了緩沖棧所處的地位。前置部件的輸出不直接送入后置部件，而是通過緩沖棧暫存后才輸出。前置部件后置部件緩沖站①②③運算控制器

先行指令棧

后行寫數棧

先行讀數棧存儲控制器去主存儲器地址線

指令分析器

先行操作棧運算器通用寄存器3.1重疊執行和先行控制3．先行控制原理通過先行指令計數器PC1預取指令序列通過現行指令計數器PC取出現行指令指令分析器指令分析器:對取自先行指令棧的指令進行預處理.1.對于程序控制類的指令，如轉移指令，指今分析器可以直接完成指令的執行.2.對于數據運算型指令，指令分析器要將它們變換成寄存器-寄存器（RR型）指令，即將操作數預先存到寄存器中，使指令能快速執行.立即尋址傳數據變址尋址或存儲器型指令,傳地址RR*指令3.1重疊執行和先行控制先行控制技術中采取了兩個根本的措施：指令預處理技術和緩沖技術。由于指令和數據的緩沖，保證了指令分析和指令的執行都能全速地運行。第k條指令分析k執行k第k+2條指令執行k+2分析k+2第k+1條指令分析k+1執行k+1第k條指令分析k執行k第k+2條指令執行k+2分析k+2第k+1條指令分析k+1執行k+1改進前改進后3.2流水線的基本概念3.2流水線的基本概念一.什么是流水線1.流水線技術（pipelining）把一個重復的過程分解為若干個子過程，每個子過程由專門的功能部件來實現。把多個處理過程在時間上錯開，依次通過各功能段，這樣，每個子過程就可以與其他的子過程并行進行。流水線中的每個子過程及其功能部件稱為流水線的級或段，段與段相互連接形成流水線。流水線的段數稱為流水線的深度(PipelineDepth)。3.2流水線的基本概念2．流水線結構重疊執行是流水線結構的思想基礎，只要在指令分析器與指令執行部件之后都加上一個鎖存器，就成了一個簡單的流水線結構。

指令執行部件

指令分析器鎖存器鎖存器分析k+1執行kΔt2Δt1

結果出指令入在流水線的每一個功能部件的后面都要有一個緩沖寄存器，或稱為鎖存器、閘門寄存器等，它的作用是保存本流水段的執行結果。3．時空圖：可以直觀地表現流水線的工作過程

橫軸表示時間，即各條指令在處理機中經歷各個操作時占用的時間段。

縱軸表示空間，即流水線的各個子操作過程，通常也稱為“功能段”。k·Δt(n-1)Δtn-1123………nn-1123………nn-1123………nn-1123………n時間空間S1S2S3S4n-1123………nS5填入填滿排空通過時間排空時間3.2流水線的基本概念4．流水線的工作特點1）一條流水線通常由多個流水段組成，在每一個流水段有專門的功能部件來實現。2）各流水段所需的時間應盡可能相等，否則將引起流水線堵塞、斷流。時間較長的段將成為流水線瓶頸。3）流水線每個功能部件后面都有一個緩沖寄存器，稱為流水寄存器。4）流水線的工作一般分為3個階段，即填入(建立)、填滿和排空。5）流水線技術適合于大量重復的時序過程，只有在輸入端不斷地提供任務，才能充分發揮流水線的效率。3.2流水線的基本概念二.流水線的種類1.按處理機分類（1）操作部件級為最低級別的流水線。是把處理機的算術邏輯運算部件分段。如果某一部件的處理過程比較復雜，如浮點運算,需要較長的時間。這時可以將該部件分為若干子部件，分別完成浮點運算中有關的子操作，這種在部件范圍內形成的流水線稱為操作部件級流水線。3.2流水線的基本概念例如：一個浮點加法部件的流水線：求階差對階尾數加規格化入出部件級流水線通常是流水線處理機中的一部分，這時的處理機由于流水級數較多，又稱為超流水線處理機。3.2流水線的基本概念（2）處理機級又稱為指令流水線，就是將一條指令的解釋執行過程分解成若干個子過程，使每個子過程分別在一個部件中完成。取指令譯碼執行存結果入出3.2流水線的基本概念

（3）處理機間級處理機間流水線通常是多處理機系統中對任務采取的一種處理策略。上圖是處理機間流水線示意圖，圖中每個處理機是以任務為單位進行處理的，而處理機間的任務傳遞則是由公用存儲器完成的。應當指出，圖中給出的是一個處理的“流水”，并沒有涉及更多的硬件結構。實際上這個過程更應該看作是一種任務的調度策略。

處理機2M

處理機nM

輸出

處理機1M輸入

任務1

任務2

任務n3.2流水線的基本概念2.按流水線功能多少分類（1）單功能流水線指一條流水線只能完成一種單一的任務。（2）多功能流水線指能夠在一個時間段內或不同時間段間改變部件之間的連接，從而達到改變其功能的流水線。在標量運算中，各種運算是混在一起的。例如：ASC處理機，運算流水線（浮點加減法運算+定點乘法運算）ASC處理機的多功能流水線3、按照工作方式分類（1）靜態流水線當執行某一規定功能的指令全部流出后，才允許改變部件間連接的流水線。3.2流水線的基本概念（可以是單功能流水線也可以是多功能流水線）3.2流水線的基本概念（2）動態流水線沒有這種時間上的限制，可以在任何時候根據需要改變其連接。（只能是多功能流水線）3.2流水線的基本概念4.按連接方式分類（1）線性流水線是指在部件上沒有反饋連接的流水線。在這種流水線中，指令依次通過各個部件僅一次，完成指令執行的全過程。目前所使用的流水線絕大部分都是這類線性流水線。（2）非線性流水線是指在各部件除了串行的連接外，還通過反饋線使某些部件得以重復使用。指令在通過這種流水線時，可能在反饋部件上重復運行若干次。3.2流水線的基本概念反饋回路S1S2S3入出S3××××S1S2時間非線性流水線工作特性示意圖3.2流水線的基本概念5.按流入流出順序分類（1）順序流水線其輸出的結果與輸入的次序相同，早期的流水線又稱為順序流水線。（2）亂序流水線將原始的輸入次序打亂，以最有利于處理機執行的方式運行，在輸出結果時才恢復原次序。在一些現代處理機中，如Pentium4在流水線運行過程中采用了亂序方式。3.2流水線的基本概念除了上述幾種分類方法以外，還可以根據各種不同的觀點對流水線進行區分。比如：按照數據表示方式的不同，可以將流水線分為標量流水線和向量流水線兩種。在標量處理機中使用的當然是標量流水線。根據流水線在各級之間流動時的控制方法不同，又可以分成同步和異步兩種流水線。處理機內的指令流水線都是同步流水線，即使用統一的時鐘控制各級同時開始同時完成動作。而處理機間的流水線通常都是異步流水線，需要在任務傳送時進行應答，以確保傳輸的可靠性。課后練習(下面的練習可以鞏固你的知識！)1.如果一條指令的執行需要取指、譯碼和執行三個過程，每一級分別需要Dt，2Dt和3Dt。畫出按順序執行、一次重疊、二次重疊及先行控制四種方式工作時的時空圖。3.3流水線的性能指標3.3流水線的性能指標

吞吐率、加速比和效率是表明流水線性能的主要指標。一.吞吐率定義：在單位時間內流水線所完成的任務數量。kTnTP=n：任務總數Tk：處理完成n個任務所用的時間3.3流水線的性能指標1.各段執行時間相等的流水線一條k段的流水線完成n個任務的時空圖:所需總時間為：最大吞吐率為:ttnknTPnD=D-+=￥?1)1(limmax實際吞吐率為:tnknTPD-+=)1(3.3流水線的性能指標

分母Tk

：當n→∞時,（k–1）可以忽略不計，Tk→n·△t

只有當n>>k時，才有TP≈TPmax。

2.各級執行時間不等的流水線執行時間不等的流水線時空圖3.3流水線的性能指標n12…3123n…n…321312n…(n-1)Δt2Tk時間空間S4S3S2S1各段時間不等的吞吐率:同樣，當n→∞時的最大吞吐率為：?=DDD-+D=kikitttntnTP121),,,(max)1(…),,,(max121maxktttTPDDD=…3.3流水線的性能指標3.流水線瓶頸問題如果流水線中各級的執行時間不相等，其中時間最長的段就成了流水線中的“瓶頸”。瓶頸問題對流水線的吞吐率影響是明顯的，所以消除“瓶頸”是設計流水線的一個重要原則。“瓶頸”問題的消除采用的方法主要有兩種：1）分割瓶頸部件的工作2）重復設置瓶頸部件3.3流水線的性能指標3.3流水線的性能指標消除“瓶頸”影響的兩種方法示意圖：ΔtS1S2S3S4Δt3ΔtΔt細分瓶頸段：重復瓶頸段：3.3流水線的性能指標重復設置瓶頸段后的時空圖缺點：控制邏輯比較復雜，所需的硬件增加了。不消除“瓶頸”時的吞吐率：兩種方式在效果上是可以等效的，在輸入n條指令的情況下，實際吞吐率都為：tnntnnTPD+=D-+=)5()16(?=DDD-+D=kikitttntnTP121),,,(max)1(…=63D-+Dtntn)1(=3D+t3nn)(3.3流水線的性能指標3.3流水線的性能指標二.加速比處理同一批任務，不用流水線(順序執行)與采用流水線所花費的時間之比，稱為流水線的加速比。設不使用流水線所用的時間為Ts，使用流水線所用時間為Tk，那么加速比就是：1.流水線各段時間均相等（都是△t）一條k段流水線完成n個連續任務順序執行n個任務的時間：Ts=n·kΔt采用流水線所需時間為：Tk=(k+n–

1)Δt加速比為：1)1(s-+=D-+D==nknktnktknTTSk

當n>>k,最大加速比：knknkSn=-+=￥?1limmax3.3流水線的性能指標2.流水線的各段時間不完全相等（△ti表示第i段的執行時間）一條k段流水線完成n個連續任務，一條指令的執行時間是各級運行時間之和∑Δti。順序執行n個任務的時間：Ts=n·∑Δti采用流水線所需時間為：Tk=∑Δti+(n-1)max(Δt1,Δt2,…Δtk,)加速比為：??==DDD-+DD=kikikiitttnttnS1211),,,(max)1(…3.3流水線的性能指標3.3流水線的性能指標三.效率定義：流水線中的設備實際使用時間與整個運行時間的比值，即流水線設備的利用率。1.假設各級執行時間相等顯然，n越大，空閑部件占據的比例就小，流水線表現的效率越高。最高效率為：11limmax=-+=￥?nknEn3.3流水線的性能指標流水線效率等于：注：上式僅適用于各段時間相等流水線。3.3流水線的性能指標2.從時空圖上看，效率就是n個任務占用的時空面積和k個段總的時空面積之比。流水線效率的一般公式：（直觀，通用）空區個流水線級占用的總時條指令占用的時空區knE=

例如：各級執行時間不等的流水線中的效率??==DDD-+DD=kikikiitttntktnE1211)],…,(max)1([同樣，效率公式：加速比公式：兩者相結合得出：E=S/k或S=k·E1-+=nknkS1-+=nknE效率公式：tnknTPD-+=)1(吞吐率公式：1-+=nknE

兩者相結合得出：E=TP·Δt或TP=E/Δt3.3流水線的性能指標3.效率與吞吐率、加速比的關系（各級時間相等的流水線）例：一個5級的線性流水線，可完成兩個數相加運算。若要進行8個操作數連續相加運算，如何實現？性能如何？分析：

假設M=A+B+C+D+E+F+G+H

首先，選擇一種效率較高的運算方法。若按從左至右順序相加進行運算，效率很低。可采用兩兩相加：

M=（A+B）+（C+D）+（E+F）+（G+H）12345673.3流水線的性能指標工作時空圖：從時空圖中看出，由于輸入任務的不連續，全部7個任務（加法指令），總共需要18個時鐘周期后完成。如每段執行時間均等于Δt，吞吐率TP為：時間空間12345671234567123456712345671234567123184567891011121314151617S5S1S2S3S4M=（A+B）+（C+D）+（E+F）+（G+H）1234567這時流水線的加速比為:而效率達到：時間空間12345671234567123456712345671234567123184567891011121314151617S5S1S2S3S4效率為何仍然不高？整個流水線的效率很低的原因：（1）存在有數據相關，當發生數據相關時，必須等待前一個運算結果產生之后，下一個運算才能開始；（2）流水線有填入與排空部分，當輸入到流水線中的任務不多時，填入與排空部分所占的比例比較大。

3.3流水線