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

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

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

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

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

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

Ti=t取指令

+t分析

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

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

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

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

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

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

分別設(shè)置對(duì)應(yīng)存儲(chǔ)控制器，指令控制器和運(yùn)算控制器。3.1重疊執(zhí)行和先行控制（2）問(wèn)題二：

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

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

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

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

先行指令棧

后行寫(xiě)數(shù)棧

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

指令分析器

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

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

先行指令棧

后行寫(xiě)數(shù)棧

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

指令分析器

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

指令執(zhí)行部件

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

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

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

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

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

處理機(jī)2M

處理機(jī)nM

輸出

處理機(jī)1M輸入

任務(wù)1

任務(wù)2

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

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

分母Tk

：當(dāng)n→∞時(shí),（k–1）可以忽略不計(jì)，Tk→n·△t

只有當(dāng)n>>k時(shí)，才有TP≈TPmax。

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

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

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

例如：各級(jí)執(zhí)行時(shí)間不等的流水線中的效率??==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流水線的性能指標(biāo)3.效率與吞吐率、加速比的關(guān)系（各級(jí)時(shí)間相等的流水線）例：一個(gè)5級(jí)的線性流水線，可完成兩個(gè)數(shù)相加運(yùn)算。若要進(jìn)行8個(gè)操作數(shù)連續(xù)相加運(yùn)算，如何實(shí)現(xiàn)？性能如何？分析：

假設(shè)M=A+B+C+D+E+F+G+H

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

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

3.3流水線