計算機體系結(jié)構(gòu)第三章-1

第三章流水線技術(shù)

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

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

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

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

Ti=t取指令

+t分析

+t執(zhí)行3.1重疊執(zhí)行和先行控制

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

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

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

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

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

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

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

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

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

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

先行指令棧

后行寫數(shù)棧

先行讀數(shù)棧存儲控制器去主存儲器地址線

指令分析器

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

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

先行指令棧

后行寫數(shù)棧

先行讀數(shù)棧存儲控制器去主存儲器地址線

指令分析器

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

指令執(zhí)行部件

指令分析器鎖存器鎖存器分析k+1執(zhí)行kΔt2Δt1

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

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

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

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

處理機2M

處理機nM

輸出

處理機1M輸入

任務1

任務2

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

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

分母Tk

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

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

2.各級執(zhí)行時間不等的流水線執(zhí)行時間不等的流水線時空圖3.3流水線的性能指標n12…3123n…n…321312n…(n-1)Δt2Tk時間空間S4S3S2S1各段時間不等的吞吐率:同樣，當n→∞時的最大吞吐率為：?=DDD-+D=kikitttntnTP121),,,(max)1(…),,,(max121maxktttTPDDD=…3.3流水線的性能指標3.流水線瓶頸問題如果流水線中各級的執(zhí)行時間不相等，其中時間最長的段就成了流水線中的“瓶頸”。瓶頸問題對流水線的吞吐率影響是明顯的，所以消除“瓶頸”是設計流水線的一個重要原則?！捌款i”問題的消除采用的方法主要有兩種：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流水線的性能指標二.加速比處理同一批任務，不用流水線(順序執(zhí)行)與采用流水線所花費的時間之比，稱為流水線的加速比。設不使用流水線所用的時間為Ts，使用流水線所用時間為Tk，那么加速比就是：1.流水線各段時間均相等（都是△t）一條k段流水線完成n個連續(xù)任務順序執(zhí)行n個任務的時間：Ts=n·kΔt采用流水線所需時間為：Tk=(k+n–

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

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

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

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

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

首先，選擇一種效率較高的運算方法。若按從左至右順序相加進行運算，效率很低?？刹捎脙蓛上嗉樱?/p>

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

3.3流水線