1、第6章 流水線原理及其1 重疊方式,通常提高指令執(zhí)行速度的途徑有如下三種： 提高處理機的工作主頻。 采用更好的算法和設(shè)計更好的功能部件。 多條指令并行執(zhí)行，稱為指令級并行技術(shù)。,可以從兩個方面來開發(fā)處理機內(nèi)部的并行性： 空間并行性：即在一個處理機內(nèi)設(shè)置多個獨立的操作部件，并讓這些操作部件并行工作，這種處理機稱為多操作部件處理機或超標(biāo)量處理機; 時間并行性：就是采用流水線技術(shù)。流水線技術(shù)是一種非常經(jīng)濟、對提高處理機的運算速度非常有效的技 術(shù)。采用流水線技術(shù)可以不增加硬件或只需要增加少量硬件就能夠把處理機的運算速度提高幾倍 它是目前使用非常普遍的一種并行處理方式。,本章學(xué)習(xí)標(biāo)量計算機上使用的流水加

2、速技術(shù)。主要內(nèi)容有流水技術(shù)的分類、流水線性能指標(biāo)計算、非線性流水線的調(diào)度算法。 標(biāo)量計算機指只能直接進(jìn)行標(biāo)量運算的計算機，與能夠直接進(jìn)行向量運算的向量計算機相對應(yīng)。 流水處理方式的特征，是讓多個依次啟動的任務(wù)，盡量同時使用系統(tǒng)的不同部件，通過時間重疊來提高處理速率。這種技術(shù)理論上不增加成本。 標(biāo)量計算機上使用的流水加速技術(shù)屬于指令級并行技術(shù)。 每條指令的處理過程，可以劃分為取指、譯碼、取數(shù)、運算、送結(jié)果5個子過程，也可以分得更細(xì)或更粗一些。劃分的原則是各部分時間長度大致相等、并使用CPU中不同的部件，這樣才有利于多任務(wù)重疊處理。,基本名詞術(shù)語 標(biāo)量處理機，超標(biāo)量處理機：標(biāo)量處理機指只能進(jìn)行標(biāo)量

3、運算的處理機，超標(biāo)量處理機指能在一個時鐘周期內(nèi)同時發(fā)射多條指令的處理機； 指令級并行技術(shù)：指能使多條指令并行執(zhí)行的技術(shù)，包括流水技術(shù)、多操作部件技術(shù)和超長指令字技術(shù)； 流水線處理機，超流水線處理機：流水線處理機指用流水作業(yè)方式并行解釋多條指令的處理機，超流水線處理機指能在一個時鐘周期內(nèi)分時發(fā)射多條指令的處理機； 超長指令字技術(shù)VLIW：指讓一條指令包含多個獨立的操作字段，并且分別控制多個功能部件并行工作的技術(shù)。,一重疊解釋方式 1.一條指令的幾個過程段 1）取指令：根據(jù)PC（指令計數(shù)器）從M（存儲器）取出指令送到IR（指令寄存器） 2）譯碼分析：譯出指令的操作性質(zhì)，準(zhǔn)備好所需數(shù)據(jù) 3）執(zhí)行：將

4、準(zhǔn)備好的數(shù)按譯出性質(zhì)進(jìn)行處理，主要涉及ALU（算術(shù)邏輯運算部件） 2. 對指令執(zhí)行的幾種方式,1）順序執(zhí)行 (傳統(tǒng)機采用) 只有在前一條指令的各過程段全部完成后，才從存儲器取出下一條指令 2) 僅兩條指令重疊：第i條指令的執(zhí)行與第i+1條的取指重疊。 3) 三條指令重疊：第i條指令的執(zhí)行與第i+1條的譯碼及第i+2條的取指重疊。,若一條指令的過程段劃分更多時，重疊組合方式更多。 重疊解釋并不能加快一條指令的實現(xiàn)，但能加快一段程序的解釋。 3. 重疊方式中所需時間表達(dá)式及所需時間計算 1）條件：設(shè)一條指令分為三個過程段，各過程段分別用t取、t譯、t執(zhí)表示。 執(zhí)行K條指令，分別采用順序執(zhí)行、兩條重

5、疊、三條重疊。 假設(shè):各個功能段時間相同,公式見教材P285,各個功能段時間不相同,公式見 順序執(zhí)行 k*（t取+t譯+t執(zhí)） 兩條重疊 t取+ k* t譯+(k-1) *( t取,t執(zhí))max+ t執(zhí) 三條重疊 t取+( t譯, t取)max+(k-2) *（t取,t譯,t 執(zhí)）max+( t執(zhí), t譯)max+ t執(zhí),3) 例子 當(dāng)k=200，t取=3t，t譯=4t，t執(zhí)=5t，時，分別計算上述三種執(zhí)行方式的時間。 順序執(zhí)行：200(3+4+5)=2400t 兩條重疊：3+2004+(200-1)5+5=1803t 三條重疊：3+4+(200-2)5+5+5=1007t,4 重疊方式需要解

6、決的問題 1）對存儲器的頻繁訪問 有哪些訪問：取指令、取操作數(shù)、存放執(zhí)行結(jié)果, I/O通道訪問. 希望存儲器為多體結(jié)構(gòu)，以適應(yīng)多種訪問源的需要。 當(dāng)存儲器為單體結(jié)構(gòu)時，需要將訪問源排隊，先后順序為： 取指令、取數(shù)據(jù)、I/O通道訪問、存結(jié)果,先行控制（look-ahead）技術(shù)最早在IBM公司研制的STRETCH機器中采用。目前，許多處理機中都已經(jīng)采用了這種技術(shù)，包括超流水處理機和超標(biāo)量處理機等。 先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理技術(shù)，以及兩者的結(jié)合。 緩沖技術(shù)是在工作速度不固定的兩個功能部件之間設(shè)置緩沖棧，用以平滑它們的工作。 預(yù)處理技術(shù)是把進(jìn)入運算器的指令都處理成寄存器寄存器（RR型）指

7、令，為進(jìn)入運算器的指令準(zhǔn)備好所需要的全部操作數(shù)。,6.1 先行控制技術(shù),采用先行控制方式的處理機結(jié)構(gòu),2）應(yīng)具有先行控制部件 先行：在重疊操作中，當(dāng)前一條指令在執(zhí)行過程中就需要提前取出后面的指令進(jìn)行相應(yīng)處理，這種提前取出后繼指令進(jìn)行相應(yīng)處理，稱為先行。 先行控制部件的主要包括 ）先行地址站，包括先行指令地址站和先行操作數(shù)地址站； ）先行指令站，用來存放多條指令； ）先行操作數(shù)站，用來存放多個操作數(shù)； ）先行地址形成部件，用來形成先行指令地址 以及先行操作數(shù)地址； ）先行操作碼譯碼站，用來完成對多條指令的 譯碼并保留譯碼輸出狀態(tài)。,也應(yīng)具有后行部件 后行部件：對指令執(zhí)行后的結(jié)果進(jìn)行處理的器件，稱

8、 后行部件。包括：后行數(shù)地址站，提供后行數(shù)存放地址。后行數(shù)站，存放運行的結(jié)果，并且，這些結(jié)果需送存 儲器。,6.2.1 基本思想,6.2 流水處理的概念,6.2.2 流水技術(shù),流水技術(shù)：將一個重復(fù)的時序過程分解成為若干個子過程，而每個子過程都可有效地在其專用功能段上與其他子過程同時執(zhí)行。 時空圖:從時間和空間兩個方面描述了流水線的工作過程。時空圖中，橫坐標(biāo)代表時間，縱坐標(biāo)代表流水線的各個段。 CPU中的各個部件按流水處理順序連接起來，就稱為一條流水線。,6.2.3 流水線工作原理 流水線方式是把一個復(fù)雜的過程分解為若干個子過程，每個子過程與其他子過程同時進(jìn)行。 處理機解釋程序的方式有順序方式、

9、重疊方式、流水方式等 順序方式是解釋完一條指令再開始解釋下一條； 流水方式是把一個重復(fù)的過程分解為若干個子過程，每個子過程可以與其它子過程同時進(jìn)行，以此提高單位時間內(nèi)解釋指令的數(shù)目； 重疊方式是一種簡單的流水方式，它把指令分成2個子過程 每條指令只與下一條指令相重疊。,重疊方式流水線,當(dāng)分析部件完成上一條指令的“分析”后，就立即將之送入執(zhí)行部件，同時分析部件可以開始處理下一條指令。 雖然從執(zhí)行一條指令的全過程來看，仍需要2t的時間，但從機器的輸出端來看，卻是每隔一個t就能給出一條指令的執(zhí)行結(jié)果。,流水線結(jié)構(gòu)圖,流水線工作時空圖,6.2.4 流水線的特點,流水過程由多個相聯(lián)系的子過程組成，每個子

10、過程稱為流水線的級或段，段的數(shù)目稱為流水線的深度。 在流水線中處理的必須是連續(xù)任務(wù)，只有不斷的提供任務(wù)才能充分發(fā)揮流水線的效率。 把一個任務(wù)分解為幾個有聯(lián)系的子任務(wù)，每個子任務(wù)由一個專門的功能部件來實現(xiàn)。 在流水線的每一個功能部件的后面都要有一個緩沖器，用于保存本段的執(zhí)行結(jié)果。 各個功能段所需時間應(yīng)盡量相等，否則時間長的功能段將成為流水線的“瓶頸”，會造成流水線的“堵塞”和“斷流”。這個時間一般為一個時鐘周期（節(jié)拍）。 流水線需要有“裝入時間”和“排空時間”。,6.3 流水技術(shù)的分類,1）按各過程段用時是否全等劃分 均勻流水線：各過程段用時全等 非均勻流水線：各過程段用時不全等（如上圖） ）時

11、間匹配的均勻流水線。 ）時間不匹配的非均勻流水線。,2）按處理的數(shù)據(jù)類型 標(biāo)量流水線：用于對標(biāo)量數(shù)據(jù)進(jìn)行流水處理。 向量流水線：用于對向量數(shù)據(jù)進(jìn)行流水處理。（向量很適合流水處理） 3）按流水線的規(guī)模 操作流水線：如將一條指令劃分為多個過程段進(jìn)行流水處理。規(guī)模最小 指令流水線：以指令為單位進(jìn)行處理，用于多進(jìn)程、多任務(wù)。規(guī)模較大 宏流水線：以程序的邏輯功能段為單位進(jìn)行流水處理。規(guī)模最大,4）按流水線具有功能的多少 單功能流水線：各過程段之間固定連接，不能重新構(gòu)成其它流水線固定流水線 多功能流水線分： 靜態(tài)流水線：各過程段之間可重新連接，但不同時刻只能重構(gòu)成一種不同的流水線。 動態(tài)流水線：各過程段之

12、間可重新連接，不同時刻可重構(gòu)成多種流水線。 5）按部件在同一時刻送出支路數(shù)的多少來分。 一維流水線：在同一時刻，部件只能向一個地方傳送結(jié)果。 陣列流水線：在同一時刻，部件可同時向多個地方傳送結(jié)果。,5.4.5 “瓶頸”問題及其解決方法,瓶頸：瓶頸就是ti最大的段，它使流水線“流速”減慢。 S1S2S3S4 t3ttt 方法1：再細(xì)分 將瓶頸設(shè)備再細(xì)分為下一級流水線 S1S2aS2bS2cS3S4 tttttt 方法2：并行設(shè)置 將瓶頸設(shè)備重復(fù)設(shè)置多套。,衡量流水線的主要指標(biāo)有吞吐率，加速比和效率。 6.4.1 吞吐率TP 吞吐率（TP ThroughPut）指流水線在單位時間內(nèi)執(zhí)行的任務(wù)數(shù)，可

13、以用輸入任務(wù)數(shù)或輸出任務(wù)數(shù)表示。 其中k表示流水線劃分的段數(shù)。 當(dāng)滿足 條件時，有 。,6.4 線性流水線性能分析,S4 1 2 3 4 N-1 N S3 1 2 3 4 N-1 N S2 1 2 3 4 N-1 N S1 1 2 3 4 N-1 N 時間 KT (N-1)T NT (K-1)T Tk,流水線產(chǎn)生n個結(jié)果所需要的時間： 實際吞吐率： 最大吞吐率： 最大吞吐率與實際吞吐率的關(guān)系：,（1）流水線各段的執(zhí)行時間相等,實際吞吐率： 最大吞吐率：,（2）流水線各段的執(zhí)行時間不等,6.4.2 加速比（即吞吐率之比，）,不使用流水線所用的時間與使用流水線所用的時間之比 一般表示：s=T0/T

14、K 其中 實際加速比： 最大加速比：,段效率：，各段平均效率： 其中 表示第i段設(shè)備量占整條流水線全部設(shè)備量的百分比 當(dāng)滿足 條件（即等長、等權(quán)）時，有：,6.4.3 效率（設(shè)備利用率）,上式指出，S=Ek，就是說當(dāng)效率達(dá)到100%時，流水方式（一個任務(wù)/t）吞吐率為順序方式（一個任務(wù)/(kt)）的k倍。,實際效率： 最大效率：,瓶頸問題用兩種方法改進(jìn)后的效率和吞吐率,P295,6.5 流水線中的相關(guān),相關(guān)的定義： 流水線中的相關(guān)是指相鄰或相近的指令因存在某種關(guān)聯(lián)，后面的指令不能在原指定的時鐘周期開始執(zhí)行。 一般來說，流水線中的相關(guān)主要分為如下三種類型： 結(jié)構(gòu)相關(guān)：當(dāng)硬件資源滿足不了指令重疊執(zhí)

15、行的要求，而發(fā)生資源沖突時，就發(fā)生了結(jié)構(gòu)相關(guān)。 數(shù)據(jù)相關(guān)：當(dāng)一條指令需要用到前面指令的執(zhí)行結(jié)果，而這些指令均在流水線中重疊執(zhí)行時，就可能引起數(shù)據(jù)相關(guān)。 3. 控制相關(guān)：當(dāng)流水線遇到分支指令和其它能夠改變 PC 值的指令時，就會發(fā)生控制相關(guān)。,一旦流水線中出現(xiàn)相關(guān)，必然會給指令在流水線中的順利執(zhí)行帶來許多問題，如果不能很好地解決相關(guān)問題，輕則影響流水線的性能，重則導(dǎo)致錯誤的執(zhí)行結(jié)果。消除相關(guān)的基本方法是讓流水線暫停執(zhí)行某些指令，而繼續(xù)執(zhí)行其它一些指令。 在后面的討論中，我們約定：當(dāng)一條指令被暫停時，在該暫停指令之后發(fā)射的所有指令都要被暫停，而在該暫停之前發(fā)射的指令則可繼續(xù)進(jìn)行，在暫停期間，流水線

16、不會取新的指令。,5.6.1 結(jié)構(gòu)相關(guān),如果某些指令組合在流水線中重疊執(zhí)行時，產(chǎn)生資源沖突，則稱該流水線有結(jié)構(gòu)相關(guān)。為了能夠在流水線中順利執(zhí)行指令的所有可能組合，而不發(fā)生結(jié)構(gòu)相關(guān)，通常需要采用流水化功能單元的方法或資源重復(fù)的方法。,許多流水線機器都是將數(shù)據(jù)和指令保存在同一存儲器中。如果在某個時鐘周期內(nèi)，流水線既要完成某條指令對數(shù)據(jù)的存儲器訪問操作，又要完成取指令的操作，那么將會發(fā)生存儲器訪問沖突問題 產(chǎn)生結(jié)構(gòu)相關(guān)。為了解決這個問題，可以讓流水線完成前一條指令對數(shù)據(jù)的存儲器訪問時，暫停取后一條指令的操作。該周期稱為流水線的一個暫停周期。暫停周期一般也稱為流水線氣泡，或簡稱為“氣泡”。在流水線中插

17、入暫停周期可以消除這種結(jié)構(gòu)相關(guān)。,結(jié)構(gòu)相關(guān)舉例訪存沖突,為消除結(jié)構(gòu)相關(guān)插入流水氣泡,時空圖來表示暫停情況,分析,為消除結(jié)構(gòu)相關(guān)而引入的暫停將影響流水線的性能。為了避免結(jié)構(gòu)相關(guān)，可以考慮采用資源重復(fù)的方法。比如，在流水線機器中設(shè)置相互獨立的指令存儲器和數(shù)據(jù)存儲器；也可以將 Cache 分割成指令 Cache 和數(shù)據(jù) Cache。,假設(shè)不考慮流水線其它因素對流水線性能的影響，顯然如果流水線機器沒有結(jié)構(gòu)相關(guān)，那么其 CPI 也較小。然而，為什么有時流水線設(shè)計者卻允許結(jié)構(gòu)相關(guān)的存在呢？主要有兩個原因：一是為了減少硬件代價，二是為了減少功能單元的延遲。如果為了避免結(jié)構(gòu)相關(guān)而將流水線中的所有功能單元完全流

18、水化，或者設(shè)置足夠的硬件資源，那么所帶來的硬件代價必定很大。,6.6.2 數(shù)據(jù)相關(guān),當(dāng)指令在流水線中重疊執(zhí)行時，流水線有可能改變指令讀/寫操作數(shù)的順序，使得讀/寫操作順序不同于它們非流水實現(xiàn)的順序，這將導(dǎo)致數(shù)據(jù)相關(guān)。,ADD指令后的所有指令都要用到ADD指令的計算結(jié)果，ADD 指令在 WB 段才將計算結(jié)果寫入寄存器 R1 中，但是 SUB 指令在其 ID 段就要從寄存器 R1 中讀取該計算結(jié)果，這種情況就叫做數(shù)據(jù)相關(guān)。除非有措施防止這一情況出現(xiàn)，否則 SUB 指令讀到的是錯誤的值。所以，為了保證上述指令序列的正確執(zhí)行，流水線只好暫停 ADD 指令之后的所有指令，直到 ADD 指令將計算結(jié)果寫入

19、寄存器 R1 之后，再啟動 ADD 指令之后的指令繼續(xù)執(zhí)行。,數(shù)據(jù)相關(guān)舉例,例子分析,從上圖還可以看到， AND 指令同樣也將受到這種相關(guān)關(guān)系的影響。 ADD 指令只有到第五個時鐘周期末尾才能結(jié)束對寄存器 R1 的寫操作，所以 AND 指令在第四個時鐘周期從寄存器 R1 中讀出的值也是錯誤的。而 XOR 指令則可以正常操作，因為它是在第六個時鐘周期讀寄存器 R1 的內(nèi)容。 另外，利用流水線的一種簡單技術(shù)，可以使流水線順利執(zhí)行 OR 指令。這種技術(shù)就是：在流水線中，約定在時鐘周期的后半部分進(jìn)行寄存器文件的讀操作，而在時鐘周期的前半部分進(jìn)行寄存器文件的寫操作。在圖中，我們將寄存器文件的邊框適當(dāng)?shù)禺?/p>

20、成虛線來表示這種技術(shù)。,通過定向技術(shù)減少數(shù)據(jù)相關(guān)帶來的暫停,數(shù)據(jù)相關(guān)問題可以采用一種稱為定向（也稱為旁路或短路）的簡單技術(shù)來解決 。定向技術(shù)的主要思想是：在某條指令（如圖中的 ADD 指令）產(chǎn)生一個計算結(jié)果之前，其它指令（如圖中的 SUB 和 AND 指令）并不真正需要該計算結(jié)果，如果能夠?qū)⒃撚嬎憬Y(jié)果從其產(chǎn)生的地方（寄存器文件 EX/MEM）直接送到其它指令需要它的地方（ALU 的輸入寄存器），那么就可以避免暫停.,基于這種考慮，定向技術(shù)的要點可以歸納為： 寄存器文件 EX/MEM 中的 ALU 的運算結(jié)果總是回送到 ALU 的輸入寄存器； 當(dāng)定向硬件檢測到前一個 ALU 運算結(jié)果的寫入寄存器

21、就是當(dāng)前 ALU 操作的源寄存器時，那么控制邏輯將前一個 ALU 運算結(jié)果定向到 ALU 的輸入端，后一個 ALU 操作就不必從源寄存器中讀取操作數(shù)。 流水線中的指令所需要的定向結(jié)果可能并不僅僅是前一條指令的計算結(jié)果，而且還有可能是前面與其不相鄰指令的計算結(jié)果,采用定向技術(shù)消除數(shù)據(jù)相關(guān),定向技術(shù)的推廣,上述定向技術(shù)可以推廣到更一般的情況，可以將一個結(jié)果直接傳送到所有需要它的功能單元。也就是說，一個結(jié)果不僅可以從某一功能單元的輸出定向到其自身的輸入，而且還可以從某一功能單元的輸出定向到其它功能單元的輸入 。 前面的一些數(shù)據(jù)相關(guān)的實例均是有關(guān)寄存器操作數(shù)的，但是數(shù)據(jù)相關(guān)也有可能發(fā)生在一對指令對存儲

22、器同一單元進(jìn)行讀寫的時候。不過，本章僅討論有關(guān)寄存器的數(shù)據(jù)相關(guān)。,到數(shù)據(jù)存儲器和ALU的定向路徑,數(shù)據(jù)相關(guān)分類,根據(jù)指令對寄存器的讀寫順序，可以將數(shù)據(jù)相關(guān)分為三類。習(xí)慣上，這些相關(guān)是根據(jù)流水線所必須保持的訪問順序來命名的?？紤]流水線中的兩條指令 i 和 j ，且 i 在 j 之前進(jìn)入流水線，由此可能帶來的數(shù)據(jù)相關(guān)有：,寫后讀相關(guān)（Read After Write，RAW）：j 的執(zhí)行要用到 i 的計算結(jié)果，當(dāng)它們在流水線中重疊執(zhí)行時，j 可能在 i 寫入其計算結(jié)果之前就先行對保存該結(jié)果的寄存器進(jìn)行讀操作，從而得到錯誤的值。這是最常見的一種數(shù)據(jù)相關(guān)，采用定向技術(shù)消除的數(shù)據(jù)相關(guān)就屬于這種類型。,寫

23、后寫相關(guān)（Write After Write，WAW）：j 和 i 的目的寄存器相同，當(dāng)它們在流水線中重疊執(zhí)行時，j 可能在 i 寫入其計算結(jié)果之前就先行對該結(jié)果寄存器進(jìn)行寫操作，從而導(dǎo)致寫入順序錯誤，在目的寄存器中留下的是 i 寫入的值，而不是 j 寫入的值。如果在流水線中不只一個段可以進(jìn)行寫操作，或者當(dāng)流水線暫停某條指令時，允許該指令之后的指令繼續(xù)前進(jìn)，就可能會產(chǎn)生這種類型的數(shù)據(jù)相關(guān)。 讀后寫相關(guān)（Write After Read，WAR）：j 可能在 i 讀取某個源寄存器的內(nèi)容之前就先對該寄存器進(jìn)行寫操作，導(dǎo)致 i 后來讀取到的值是錯誤的。,需要暫停的數(shù)據(jù)相關(guān),前面我們討論了如何利用定向

24、技術(shù)消除由于數(shù)據(jù)相關(guān)帶來的暫停。但是，并不是所有數(shù)據(jù)相關(guān)帶來的暫停都可以通過定向技術(shù)消除。,對數(shù)據(jù)相關(guān)的編譯器調(diào)度方法,流水線常常會遇到許多種類型的暫停。比如，采用典型的代碼生成方法對A=BC這種常用的表達(dá)式進(jìn)行處理，可以得到如圖所示的指令序列。從圖中可以看出，在 ADD 指令的流水過程中必須插入一個暫停時鐘周期，以保證變量C的讀入值有效。既然定向無法消除指令序列中所包含的這種暫停，那么能否讓編譯器在進(jìn)行代碼生成時就消除這些潛在的暫停呢？,指令級調(diào)度,實際上，編譯器的確可以通過重新組織代碼順序來消除這種暫停。通常稱這種重新組織代碼順序消除暫停的技術(shù)為流水線調(diào)度（pipeline schedul

25、ing）或指令調(diào)度（instruction scheduling）。,6.6.3 控制相關(guān),在流水線上執(zhí)行分支指令時，PC 值有兩種可能的變化情況。一種是 PC 值發(fā)生改變（為分支轉(zhuǎn)移的目標(biāo)地址）；一種是 PC 值保持正常。如果一條分支指令將PC值改變?yōu)榉种мD(zhuǎn)移的目標(biāo)地址，那么我們稱分支轉(zhuǎn)移成功；如果分支轉(zhuǎn)移條件不成立，PC 值保持正常，我們稱分支轉(zhuǎn)移失敗。,處理分支指令最簡單的方法是：一旦在流水線中檢測到某條指令是分支指令，就暫停執(zhí)行該分支指令之后的所有指令，直到分支指令到達(dá)流水線的 MEM 段，確定了新的 PC 值為止。我們當(dāng)然不希望流水線還沒有確定某條指令是分支指令之前就暫停執(zhí)行指令，所

26、以對分支指令而言，當(dāng)流水線完成其譯碼操作（ID段）之后才會暫停執(zhí)行其后繼指令。根據(jù)上述處理分支指令的方法，可以得到如圖所示流水線時空圖 。從圖中可以看出，在流水線中插入了兩個暫停周期，當(dāng)分支指令在 MEM 段確定新的 PC 值后，流水線作廢分支直接后繼指令的 IF 周期（相當(dāng)于一個暫停周期），按照新的有效 PC 值取指令。,減少分支暫停時鐘周期數(shù),減少流水線處理分支指令時的暫停時鐘周期數(shù)有如下兩種途徑： 在流水線中盡早判斷出分支轉(zhuǎn)移是否成功； 盡早計算出分支轉(zhuǎn)移成功時的 PC 值（即分支的目標(biāo)地址）。 為了優(yōu)化處理分支指令，在流水線中應(yīng)該同時采用上述兩條途徑，缺一不可。即使知道分支轉(zhuǎn)移的目標(biāo)地

27、址，而不知道分支轉(zhuǎn)移是否成功對減少暫停是徒勞的；知道分支轉(zhuǎn)移是否成功，而不知道分支轉(zhuǎn)移的目標(biāo)地址，同樣對降低分支損失毫無幫助。下面讓我們看看如何基于這些思想，從硬件上改進(jìn)流水線，達(dá)到降低分支損失的目的。,在流水線中，分支指令通常需要測試分支條件寄存器的值是否為0，所以可以把測試分支條件寄存器的操作移到 ID 段完成，從而使得在 ID 周期末就完成分支轉(zhuǎn)移成功與否的檢測。另外，由于要盡早計算出兩個 PC 值（分支轉(zhuǎn)移成功和失敗時的 PC 值），也可以將計算分支目標(biāo)地址的操作移到 ID 段完成。為此，需要在 ID 段增設(shè)一個加法器（注意，為了避免結(jié)構(gòu)相關(guān)，不能用EX段的 ALU 功能部件來計算分支

28、轉(zhuǎn)移目標(biāo)地址）。下圖是對流水線進(jìn)行上述改進(jìn)后的流水線數(shù)據(jù)通路。容易看出，基于上述改進(jìn)后的流水線數(shù)據(jù)通路，處理分支指令只需要一個時鐘周期的暫停。,減少分支暫停時鐘周期數(shù),降低流水線分支損失的方法有許多種。前面論述了改進(jìn)流水線硬件減少流水線暫停周期的方法。這里主要從編譯技術(shù)的角度，論述四種降低流水線分支損失的簡單方法。首先需要說明的是，這些方法對分支轉(zhuǎn)移成功與否進(jìn)行的預(yù)測都是靜態(tài)的，并在整個程序的執(zhí)行過程中保持這種預(yù)測結(jié)論，即：要么總是認(rèn)為分支轉(zhuǎn)移成功，要么總是認(rèn)為分支轉(zhuǎn)移失敗。,凍結(jié)（freeze）或排空（flush）流水線的方法在流水線中，處理分支最簡單的方法是凍結(jié)或排空流水線，保持或清除流水

29、線在分支指令之后讀入的任何指令，直到知道分支指令的目標(biāo)地址以及分支轉(zhuǎn)移是否成功為止。這種方法優(yōu)點在于其對硬件和軟件的要求都十分簡單，我們前面采用的就是這種方法。,預(yù)測分支失敗的方法 如果流水線采用預(yù)測分支失敗的方法處理分支指令，那么當(dāng)流水線譯碼到一條分支指令時，流水線繼續(xù)取指令，并允許該分支指令后的指令繼續(xù)在流水線中流動。當(dāng)流水線確定分支轉(zhuǎn)移成功與否以及分支的目標(biāo)地址之后，如果分支轉(zhuǎn)移成功，流水線必須將在分支指令之后取出的所有指令轉(zhuǎn)化為空操作，并在分支的目標(biāo)地址處重新取出有效的指令；如果分支轉(zhuǎn)移失敗，那么可以將分支指令看作是一條普通指令，流水線正常流動，無需將在分支指令之后取出的所有指令轉(zhuǎn)化為

30、空操作。,預(yù)測分支成功的方法另一種降低流水線分支損失的方法便是預(yù)測分支成功，一旦流水線譯碼到一條指令是分支指令，且完成了分支目標(biāo)地址的計算，我們就假設(shè)分支轉(zhuǎn)移成功，并開始在分支目標(biāo)地址處取指令執(zhí)行。 在某些流水線中，特別是那些具有隱含設(shè)置條件碼或分支條件更復(fù)雜指令的流水線機器中，在確定分支轉(zhuǎn)移成功與否之前，便可以知道分支的目標(biāo)地址，這時采用這種方法便可以降低這些流水線的分支損失。,4.延遲分支（delayed branch）方法 為降低流水線分支損失而采用的第四種方法就是延遲分支方法。其主要思想是從邏輯上“延長”分支指令的執(zhí)行時間。延遲長度為 n 的分支指令的執(zhí)行順序是： 分支指令 順序后繼指

31、令1順序后繼指令 n如果分支成功，分支目標(biāo)處指令 所有順序后繼指令都處于分支延遲槽（branch-delay slots）中，無論分支成功與否，流水線都會執(zhí)行這些指令。,基于延遲分支方法，無論分支成功與否，其流水線時空圖所描述的流水線的行為是類似的，流水線中均沒有插入暫停周期，從而極大地降低了流水線分支損失。從圖中可以看出，實際上是處于分支延遲槽中的指令“掩蓋”了流水線原來所必需插入的暫停周期。,6.6 非線性流水線調(diào)度技術(shù),調(diào)度問題的提出： 一個任務(wù)在通過非線性流水線時對有些功能段要通過多次（非線性定義），所以容易與緊跟而來的后繼任務(wù)發(fā)生設(shè)備爭用。 調(diào)度機構(gòu)的作用就是合理安排前后任務(wù)進(jìn)入流水

32、線的相差時間，既要避免爭用，又要使相差時間盡可能少，以提高吞吐率。,1. 非線性流水線的表示,一條非線性流水線一般需要一個各功能段間的連接圖和一張預(yù)約表共同表示。 下圖是一條4個功能段組成的非線性流水線，它有從S1到S4 的單方向傳輸線。但它有兩條反饋線和一條前饋線；輸出端不一定在最后一個功能段，而可能從任意一個功能段輸出。 輸出 輸入,2. 非線性流水線的預(yù)約表,3. 對于非線性流水線的表示,預(yù)約表的橫坐標(biāo)表示流水線的時鐘周期，縱坐標(biāo)表示流水線的功能段，中間有“ ”的表示該功能段在這一個時鐘周期處于工作狀態(tài)，即在這個時鐘周期有任務(wù)通過這個功能段；空白的表示該功能段在這一個時鐘周期不處于工作狀

33、態(tài)。 預(yù)約表行數(shù)是非線性流水線的段數(shù)；而列數(shù)是一個任務(wù)從進(jìn)入流水線到從流水線中輸出所經(jīng)歷的時鐘周期數(shù)。 一張非線性流水線的預(yù)約表可能與多個非線性流水線連接圖相對應(yīng)；同樣，一個非線性流水線的連接圖也可能對應(yīng)有多張預(yù)約表。,4. 非線性流水線的沖突,非線性流水線的啟動距離：向一條非線性流水線的輸入端連續(xù)輸入兩個任務(wù)之間的時間間隔。 非線性流水線的沖突：當(dāng)以某一個啟動距離向一條非線性流水線連續(xù)輸入任務(wù)時，可能在某一個功能段或某幾個功能段中發(fā)生有幾個任務(wù)同時爭用同一個功能 段的情況。,5. 無沖突調(diào)度方法,目標(biāo)：找出具有最小平均啟動時間的啟動循環(huán)，按照這樣的啟動循環(huán)向非線性流水線的輸入端輸入任務(wù)，流水線的工作速度最快，而且所有功能段在任何時間都沒有沖