第五章重疊、流水和向量處理機1

第五章重疊、流水和向量處理機

§1重疊方式通常提高指令執(zhí)行速度的途徑有如下三種：提高處理機的工作主頻。采用更好的算法和設(shè)計更好的功能部件。多條指令并行執(zhí)行，稱為指令級并行技術(shù)。

可以從兩個方面來開發(fā)處理機內(nèi)部的并行性：空間并行性：即在一個處理機內(nèi)設(shè)置多個獨立的操作部件，并讓這些操作部件并行工作，這種處理機稱為多操作部件處理機或超標量處理機;時間并行性：就是采用流水線技術(shù)。流水線技術(shù)是一種非常經(jīng)濟、對提高處理機的運算速度非常有效的技術(shù)。采用流水線技術(shù)可以不增加硬件或只需要增加少量硬件就能夠把處理機的運算速度提高幾倍它是目前使用非常普遍的一種并行處理方式。

本章學(xué)習(xí)標量計算機上使用的流水加速技術(shù)。主要內(nèi)容有流水技術(shù)的分類、流水線性能指標計算、非線性流水線的調(diào)度算法。標量計算機指只能直接進行標量運算的計算機，與能夠直接進行向量運算的向量計算機相對應(yīng)。流水處理方式的特征，是讓多個依次啟動的任務(wù)，盡量同時使用系統(tǒng)的不同部件，通過時間重疊來提高處理速率。這種技術(shù)理論上不增加成本。標量計算機上使用的流水加速技術(shù)屬于指令級并行技術(shù)。

每條指令的處理過程，可以劃分為取指、譯碼、取數(shù)、運算、送結(jié)果5個子過程，也可以分得更細或更粗一些。劃分的原則是各部分時間長度大致相等、并使用CPU中不同的部件，這樣才有利于多任務(wù)重疊處理。基本名詞術(shù)語標量處理機，超標量處理機：標量處理機指只能進行標量運算的處理機，超標量處理機指能在一個時鐘周期內(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ì)，準備好所需數(shù)據(jù)3）執(zhí)行：將準備好的數(shù)按譯出性質(zhì)進行處理，主要涉及ALU（算術(shù)邏輯運算部件）2.對指令執(zhí)行的幾種方式1）順序執(zhí)行(傳統(tǒng)機采用)只有在前一條指令的各過程段全部完成后，才從存儲器取出下一條指令2)僅兩條指令重疊：第i條指令的執(zhí)行與第i+1條的取指重疊。3)三條指令重疊：第i條指令的執(zhí)行與第i+1條的譯碼及第i+2條的取指重疊。

取

譯

執(zhí)

取

譯

執(zhí)

i條

i+1條

i條取譯執(zhí)i+1條取譯執(zhí)i+2條取譯執(zhí)i條取譯執(zhí)取譯執(zhí)i+1條

若一條指令的過程段劃分更多時，重疊組合方式更多。重疊解釋并不能加快一條指令的實現(xiàn)，但能加快一段程序的解釋。3.重疊方式中所需時間表達式及所需時間計算1）條件：設(shè)一條指令分為三個過程段，各過程段分別用t取、t譯、t執(zhí)表示。執(zhí)行K條指令，分別采用順序執(zhí)行、兩條重疊、三條重疊。假設(shè):各個功能段時間相同,公式見教材P231各個功能段時間不相同,公式見順序執(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)例子當k=200，t取=3Δt，t譯=4Δt，t執(zhí)=5Δt，時，分別計算上述三種執(zhí)行方式的時間。順序執(zhí)行：200×(3+4+5)=2400Δt兩條重疊：3+200×4+(200-1)×5+5=1803Δt三條重疊：3+4+(200-2)×5+5+5=1007Δt4重疊方式需要解決的問題1）對存儲器的頻繁訪問①有哪些訪問：取指令、取操作數(shù)、存放執(zhí)行結(jié)果,I/O通道訪問.②希望存儲器為多體結(jié)構(gòu)，以適應(yīng)多種訪問源的需要。③當存儲器為單體結(jié)構(gòu)時，需要將訪問源排隊，先后順序為：取指令、取數(shù)據(jù)、I/O通道訪問、存結(jié)果先行控制（look-ahead）技術(shù)最早在IBM公司研制的STRETCH機器中采用。目前，許多處理機中都已經(jīng)采用了這種技術(shù)，包括超流水處理機和超標量處理機等。先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預(yù)處理技術(shù)，以及兩者的結(jié)合。緩沖技術(shù)是在工作速度不固定的兩個功能部件之間設(shè)置緩沖棧，用以平滑它們的工作。預(yù)處理技術(shù)是把進入運算器的指令都處理成寄存器－寄存器（RR型）指令，為進入運算器的指令準備好所需要的全部操作數(shù)。5.1先行控制技術(shù)采用先行控制方式的處理機結(jié)構(gòu)2）應(yīng)具有先行控制部件①

先行：在重疊操作中，當前一條指令在執(zhí)行過程中就需要提前取出后面的指令進行相應(yīng)處理，這種提前取出后繼指令進行相應(yīng)處理，稱為先行。②先行控制部件的主要包括

Ⅰ）先行地址站，包括先行指令地址站和先行操作數(shù)地址站；

Ⅱ）先行指令站，用來存放多條指令；

Ⅲ）先行操作數(shù)站，用來存放多個操作數(shù)；

Ⅳ）先行地址形成部件，用來形成先行指令地址以及先行操作數(shù)地址；

Ⅴ）先行操作碼譯碼站，用來完成對多條指令的譯碼并保留譯碼輸出狀態(tài)。也應(yīng)具有后行部件

后行部件：對指令執(zhí)行后的結(jié)果進行處理的器件，稱

后行部件。包括：

①后行數(shù)地址站，提供后行數(shù)存放地址。

②后行數(shù)站，存放運行的結(jié)果，并且，這些結(jié)果需送存

儲器。5.2.1基本思想5.2流水處理的概念5.2.2流水技術(shù)

流水技術(shù)：將一個重復(fù)的時序過程分解成為若干個子過程，而每個子過程都可有效地在其專用功能段上與其他子過程同時執(zhí)行。時－空圖:從時間和空間兩個方面描述了流水線的工作過程。時－空圖中，橫坐標代表時間，縱坐標代表流水線的各個段。CPU中的各個部件按流水處理順序連接起來，就稱為一條流水線。5.2.3流水線工作原理流水線方式是把一個復(fù)雜的過程分解為若干個子過程，每個子過程與其他子過程同時進行。處理機解釋程序的方式有順序方式、重疊方式、流水方式等順序方式是解釋完一條指令再開始解釋下一條；

流水方式是把一個重復(fù)的過程分解為若干個子過程，每個子過程可以與其它子過程同時進行，以此提高單位時間內(nèi)解釋指令的數(shù)目；

重疊方式是一種簡單的流水方式，它把指令分成2個子過程每條指令只與下一條指令相重疊。

重疊方式流水線當分析部件完成上一條指令的“分析”后，就立即將之送入執(zhí)行部件，同時分析部件可以開始處理下一條指令。雖然從執(zhí)行一條指令的全過程來看，仍需要2?t的時間，但從機器的輸出端來看，卻是每隔一個?t就能給出一條指令的執(zhí)行結(jié)果。

流水線結(jié)構(gòu)圖

流水線工作時空圖

5.2.4流水線的特點流水過程由多個相聯(lián)系的子過程組成，每個子過程稱為流水線的級或段，段的數(shù)目稱為流水線的深度。在流水線中處理的必須是連續(xù)任務(wù)，只有不斷的提供任務(wù)才能充分發(fā)揮流水線的效率。把一個任務(wù)分解為幾個有聯(lián)系的子任務(wù)，每個子任務(wù)由一個專門的功能部件來實現(xiàn)。在流水線的每一個功能部件的后面都要有一個緩沖器，用于保存本段的執(zhí)行結(jié)果。各個功能段所需時間應(yīng)盡量相等，否則時間長的功能段將成為流水線的“瓶頸”，會造成流水線的“堵塞”和“斷流”。這個時間一般為一個時鐘周期（節(jié)拍）。流水線需要有“裝入時間”和“排空時間”。5.3流水技術(shù)的分類1）按各過程段用時是否全等劃分①均勻流水線：各過程段用時全等②非均勻流水線：各過程段用時不全等（如上圖）Ⅰ）時間匹配的均勻流水線。Ⅱ）時間不匹配的非均勻流水線。2）按處理的數(shù)據(jù)類型①標量流水線：用于對標量數(shù)據(jù)進行流水處理。②向量流水線：用于對向量數(shù)據(jù)進行流水處理。（向量很適合流水處理）3）按流水線的規(guī)模①操作流水線：如將一條指令劃分為多個過程段進行流水處理。規(guī)模最小②指令流水線：以指令為單位進行處理，用于多進程、多任務(wù)。規(guī)模較大③宏流水線：以程序的邏輯功能段為單位進行流水處理。規(guī)模最大4）按流水線具有功能的多少①單功能流水線：各過程段之間固定連接，不能重新構(gòu)成其它流水線——固定流水線②多功能流水線分：靜態(tài)流水線：各過程段之間可重新連接，但不同時刻只能重構(gòu)成一種不同的流水線。動態(tài)流水線：各過程段之間可重新連接，不同時刻可重構(gòu)成多種流水線。5）按部件在同一時刻送出支路數(shù)的多少來分。①一維流水線：在同一時刻，部件只能向一個地方傳送結(jié)果。②陣列流水線：在同一時刻，部件可同時向多個地方傳送結(jié)果。5.4.5“瓶頸”問題及其解決方法瓶頸：瓶頸就是Δti最大的段，它使流水線“流速”減慢。 S1 S2 S3 S4

Δt 3Δt Δt Δt方法1：再細分──將瓶頸設(shè)備再細分為下一級流水線 S1 S2a S2b S2c S3 S4

Δt Δt Δt Δt Δt Δt方法2：并行設(shè)置──將瓶頸設(shè)備重復(fù)設(shè)置多套。

衡量流水線的主要指標有吞吐率，加速比和效率。5.4.1吞吐率TP吞吐率（TP──ThroughPut）指流水線在單位時間內(nèi)執(zhí)行的任務(wù)數(shù)，可以用輸入任務(wù)數(shù)或輸出任務(wù)數(shù)表示。其中k表示流水線劃分的段數(shù)。當滿足 條件時，有 。5.4線性流水線性能分析S41234……N-1NS31234……N-1NS21234……N-1NS11234……N-1N時間K×T(N-1)×TN×T(K-1)×TTk

流水線產(chǎn)生n個結(jié)果所需要的時間：

實際吞吐率：

最大吞吐率：最大吞吐率與實際吞吐率的關(guān)系：（1） 流水線各段的執(zhí)行時間相等

實際吞吐率：

最大吞吐率：

（2） 流水線各段的執(zhí)行時間不等5.4.2加速比（即吞吐率之比，）不使用流水線所用的時間與使用流水線所用的時間之比一般表示：s=T0/TK其中實際加速比：最大加速比：段效率： ， 各段平均效率：其中表示第i段設(shè)備量占整條流水線全部設(shè)備量的百分比當滿足 條件（即"等長"、"等權(quán)"）時，有：5.4.3效率（設(shè)備利用率）上式指出，S=E×k，就是說當效率達到100%時，流水方式（一個任務(wù)/Δt）吞吐率為順序方式（一個任務(wù)/(k×Δt)）的k倍。實際效率：最大效率：瓶頸問題用兩種方法改進后的效率和吞吐率靜態(tài)雙功能流水線的效率與吞吐率教材P241非線性流水線的吞吐率和效率教材P291

5.5流水線中的相關(guān)相關(guān)的定義：流水線中的相關(guān)是指相鄰或相近的指令因存在某種關(guān)聯(lián)，后面的指令不能在原指定的時鐘周期開始執(zhí)行。一般來說，流水線中的相關(guān)主要分為如下三種類型：結(jié)構(gòu)相關(guān)：當硬件資源滿足不了指令重疊執(zhí)行的要求，而發(fā)生資源沖突時，就發(fā)生了結(jié)構(gòu)相關(guān)。數(shù)據(jù)相關(guān)：當一條指令需要用到前面指令的執(zhí)行結(jié)果，而這些指令均在流水線中重疊執(zhí)行時，就可能引起數(shù)據(jù)相關(guān)。

3.控制相關(guān)：當流水線遇到分支指令和其它能夠改變PC值的指令時，就會發(fā)生控制相關(guān)。

一旦流水線中出現(xiàn)相關(guān)，必然會給指令在流水線中的順利執(zhí)行帶來許多問題，如果不能很好地解決相關(guān)問題，輕則影響流水線的性能，重則導(dǎo)致錯誤的執(zhí)行結(jié)果。消除相關(guān)的基本方法是讓流水線暫停執(zhí)行某些指令，而繼續(xù)執(zhí)行其它一些指令。

在后面的討論中，我們約定：當一條指令被暫停時，在該暫停指令之后發(fā)射的所有指令都要被暫停，而在該暫停之前發(fā)射的指令則可繼續(xù)進行，在暫停期間，流水線不會取新的指令。

5.5.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ù)的存儲器訪問時，暫停取后一條指令的操作。該周期稱為流水線的一個暫停周期。暫停周期一般也稱為流水線氣泡，或簡稱為“氣泡”。在流水線中插入暫停周期可以消除這種結(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)而將流水線中的所有功能單元完全流水化，或者設(shè)置足夠的硬件資源，那么所帶來的硬件代價必定很大。

5.5.2數(shù)據(jù)相關(guān)當指令在流水線中重疊執(zhí)行時，流水線有可能改變指令讀/寫操作數(shù)的順序，使得讀/寫操作順序不同于它們非流水實現(xiàn)的順序，這將導(dǎo)致數(shù)據(jù)相關(guān)。

ADDR1，R2，R3SUBR4，R5，R1ANDR6，R1，R7ORR8，R1，R9XORR10，R1，R11ADD指令后的所有指令都要用到ADD指令的計算結(jié)果，ADD指令在WB段才將計算結(jié)果寫入寄存器R1中，但是SUB指令在其ID段就要從寄存器R1中讀取該計算結(jié)果，這種情況就叫做數(shù)據(jù)相關(guān)。除非有措施防止這一情況出現(xiàn)，否則SUB指令讀到的是錯誤的值。所以，為了保證上述指令序列的正確執(zhí)行，流水線只好暫停ADD指令之后的所有指令，直到ADD指令將計算結(jié)果寫入寄存器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ù)就是：在流水線中，約定在時鐘周期的后半部分進行寄存器文件的讀操作，而在時鐘周期的前半部分進行寄存器文件的寫操作。在圖中，我們將寄存器文件的邊框適當?shù)禺嫵商摼€來表示這種技術(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的輸入寄存器；當定向硬件檢測到前一個ALU運算結(jié)果的寫入寄存器就是當前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ā)生在一對指令對存儲器同一單元進行讀寫的時候。不過，本章僅討論有關(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之前進入流水線，由此可能帶來的數(shù)據(jù)相關(guān)有：寫后讀相關(guān)（ReadAfterWrite，RAW）：j的執(zhí)行要用到i的計算結(jié)果，當它們在流水線中重疊執(zhí)行時，j可能在i寫入其計算結(jié)果之前就先行對保存該結(jié)果的寄存器進行讀操作，從而得到錯誤的值。這是最常見的一種數(shù)據(jù)相關(guān)，采用定向技術(shù)消除的數(shù)據(jù)相關(guān)就屬于這種類型。寫后寫相關(guān)（WriteAfterWrite，WAW）：j和i的目的寄存器相同，當它們在流水線中重疊執(zhí)行時，j可能在i寫入其計算結(jié)果之前就先行對該結(jié)果寄存器進行寫操作，從而導(dǎo)致寫入順序錯誤，在目的寄存器中留下的是i寫入的值，而不是j寫入的值。

如果在流水線中不只一個段可以進行寫操作，或者當流水線暫停某條指令時，允許該指令之后的指令繼續(xù)前進，就可能會產(chǎn)生這種類型的數(shù)據(jù)相關(guān)。讀后寫相關(guān)（WriteAfterRead，WAR）：j可能在i讀取某個源寄存器的內(nèi)容之前就先對該寄存器進行寫操作，導(dǎo)致i后來讀取到的值是錯誤的。需要暫停的數(shù)據(jù)相關(guān)前面我們討論了如何利用定向技術(shù)消除由于數(shù)據(jù)相關(guān)帶來的暫停。但是，并不是所有數(shù)據(jù)相關(guān)帶來的暫停都可以通過定向技術(shù)消除。對數(shù)據(jù)相關(guān)的編譯器調(diào)度方法流水線常常會遇到許多種類型的暫停。比如，采用典型的代碼生成方法對A=B＋C這種常用的表達式進行處理，可以得到如圖所示的指令序列。從圖中可以看出，在ADD指令的流水過程中必須插入一個暫停時鐘周期，以保證變量C的讀入值有效。既然定向無法消除指令序列中所包含的這種暫停，那么能否讓編譯器在進行代碼生成時就消除這些潛在的暫停呢？指令級調(diào)度實際上，編譯器的確可以通過重新組織代碼順序來消除這種暫停。通常稱這種重新組織代碼順序消除暫停的技術(shù)為流水線調(diào)度（pipelinescheduling）或指令調(diào)度（instructionscheduling）。

5.5.3控制相關(guān)在流水線上執(zhí)行分支指令時，PC值有兩種可能的變化情況。一種是PC值發(fā)生改變（為分支轉(zhuǎn)移的目標地址）；一種是PC值保持正常。如果一條分支指令將PC值改變?yōu)榉种мD(zhuǎn)移的目標地址，那么我們稱分支轉(zhuǎn)移成功；如果分支轉(zhuǎn)移條件不成立，PC值保持正常，我們稱分支轉(zhuǎn)移失敗。處理分支指令最簡單的方法是：一旦在流水線中檢測到某條指令是分支指令，就暫停執(zhí)行該分支指令之后的所有指令，直到分支指令到達流水線的MEM段，確定了新的PC值為止。我們當然不希望流水線還沒有確定某條指令是分支指令之前就暫停執(zhí)行指令，所以對分支指令而言，當流水線完成其譯碼操作（ID段）之后才會暫停執(zhí)行其后繼指令。

根據(jù)上述處理分支指令的方法，可以得到如圖所示流水線時空圖。從圖中可以看出，在流水線中插入了兩個暫停周期，當分支指令在MEM段確定新的PC值后，流水線作廢分支直接后繼指令的IF周期（相當于一個暫停周期），按照新的有效PC值取指令。減少分支暫停時鐘周期數(shù)減少流水線處理分支指令時的暫停時鐘周期數(shù)有如下兩種途徑：在流水線中盡早判斷出分支轉(zhuǎn)移是否成功；盡早計算出分支轉(zhuǎn)移成功時的PC值（即分支的目標地址）。

為了優(yōu)化處理分支指令，在流水線中應(yīng)該同時采用上述兩條途徑，缺一不可。即使知道分支轉(zhuǎn)移的目標地址，而不知道分支轉(zhuǎn)移是否成功對減少暫停是徒勞的；知道分支轉(zhuǎn)移是否成功，而不知道分支轉(zhuǎn)移的目標地址，同樣對降低分支損失毫無幫助。下面讓我們看看如何基于這些思想，從硬件上改進流水線，達到降低分支損失的目的。在流水線中，分支指令通常需要測試分支條件寄存器的值是否為0，所以可以把測試分支條件寄存器的操作移到ID段完成，從而使得在ID周期末就完成分支轉(zhuǎn)移成功與否的檢測。

另外，由于要盡早計算出兩個PC值（分支轉(zhuǎn)移成功和失敗時的PC值），也可以將計算分支目標地址的操作移到ID段完成。為此，需要在ID段增設(shè)一個加法器（注意，為了避免結(jié)構(gòu)相關(guān)，不能用EX段的ALU功能部件來計算分支轉(zhuǎn)移目標地址）。下圖是對流水線進行上述改進后的流水線數(shù)據(jù)通路。容易看出，基于上述改進后的流水線數(shù)據(jù)通路，處理分支指令只需要一個時鐘周期的暫停。減少分支暫停時鐘周期數(shù)降低流水線分支損失的方法有許多種。前面論述了改進流水線硬件減少流水線暫停周期的方法。這里主要從編譯技術(shù)的角度，論述四種降低流水線分支損失的簡單方法。首先需要說明的是，這些方法對分支轉(zhuǎn)移成功與否進行的預(yù)測都是靜態(tài)的，并在整個程序的執(zhí)行過程中保持這種預(yù)測結(jié)論，即：要么總是認為分支轉(zhuǎn)移成功，要么總是認為分支轉(zhuǎn)移失敗。凍結(jié)（freeze）或排空（flush）流水線的方法

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

另一種降低流水線分支損失的方法便是預(yù)測分支成功，一旦流水線譯碼到一條指令是分支指令，且完成了分支目標地址的計算，我們就假設(shè)分支轉(zhuǎn)移成功，并開始在分支目標地址處取指令執(zhí)行。

在某些流水線中，特別是那些具有隱含設(shè)置條件碼或分支條件更復(fù)雜指令的流水線機器中，在確定分支轉(zhuǎn)移成功與否之前，便可以知道分支的目標地址，這時采用這種方法便可以降低這些流水線的分支損失。

4.延遲分支（delayedbranch）方法為降低流水線分支損失而采用的第四種方法就是延遲分支方法。其主要思想是從邏輯上“延長”分支指令的執(zhí)行時間。延遲長度為n的分支指令的執(zhí)行順序是：

分支指令

順序后繼指令1

……

順序后繼指令n

如果分支成功，分支目標處指令

所有順序后繼指令都處于分支延遲槽（branch-delayslots）中，無論分支成功與否，流水線都會執(zhí)行這些指令。

基于延遲分支方法，無論分支成功與否，其流水線時空圖所描述的流水線的行為是類似的，流水線中均沒有插入暫停周期，從而極大地降低了流水線分支損失。從圖中可以看出，實際上是處于分支延遲槽中的指令“掩蓋”了流水線原來所必需插入的暫停周期。5.6非線性流水線調(diào)度技術(shù)調(diào)度問題的提出：一個任務(wù)在通過非線性流水線時對有些功能段要通過多次（非線性定義），所以容易與緊跟而來的后繼任務(wù)發(fā)生設(shè)備爭用。調(diào)度機構(gòu)的作用就是合理安排前后任務(wù)進入流水線的相差時間，既要避免爭用，又要使相差時間盡可能少，以提高吞吐率。1.非線性流水線的表示

一條非線性流水線一般需要一個各功能段間的連接圖和一張預(yù)約表共同表示。下圖是一條4個功能段組成的非線性流水線，它有從S1到S4的單方向傳輸線。但它有兩條反饋線和一條前饋線；輸出端不一定在最后一個功能段，而可能從任意一個功能段輸出。

輸出

輸入S1S2S3S42.

非線性流水線的預(yù)約表×S4××S3××S2×

××S17

6

5

4321時功能段3.對于非線性流水線的表示

預(yù)約表的橫坐標表示流水線的時鐘周期，縱坐標表示流水線的功能段，中間有“×”的表示該功能段在這一個時鐘周期處于工作狀態(tài)，即在這個時鐘周期有任務(wù)通過這個功能段；空白的表示該功能段在這一個時鐘周期不處于工作狀態(tài)。預(yù)約表行數(shù)是非線性流水線的段數(shù)；而列數(shù)是一個任務(wù)從進入流水線到從流水線中輸出所經(jīng)歷的時鐘周期數(shù)。一張非線性流水線的預(yù)約表可能與多個非線性流水線連接圖相對應(yīng)；同樣，一個非線性流水線的連接圖也可能對應(yīng)有多張預(yù)約表。4.非線性流水線的沖突

非線性流水線的啟動距離：向一條非線性流水線的輸入端連續(xù)輸入兩個任務(wù)之間的時間間隔。非線性流水線的沖突：當以某一個啟動距離向一條非線性流水線連續(xù)輸入任務(wù)時，可能在某一個功能段或某幾個功能段中發(fā)生有幾個任務(wù)同時爭用同一個功能段的情況。5.無沖突調(diào)度方法目標：找出具有最小平均啟動時間的啟動循環(huán)，按照這樣的啟動循環(huán)向非線性流水線的輸入端輸入任務(wù)，流水線的工作速度最快，而且所有功能段在任何時間都沒有沖突。

算法：共5個步驟第1步.分析預(yù)約表R描述非線性流水線有2種圖形：(a)連接圖，僅給出各段之間的靜態(tài)空間連接關(guān)系；(b)預(yù)約表，就是一個任務(wù)通過流水線的時空圖，能全面反映該流水線的動態(tài)特性。要檢驗2個任務(wù)相距k拍是否沖突，可將它們的預(yù)約表錯位k列重疊（如圖）。5.6.1不改變流水線結(jié)構(gòu)的調(diào)度方法第2步.作禁止表FF是1-N之間可沖突拍數(shù)的集合，N是預(yù)約表的列數(shù)減1。具體操作是將同一行中任意2個標記之間的拍數(shù)差記下來，再將各行的這類數(shù)字匯成一個集合，即為禁止表。本例中F={3，4，6}

第3步.作原始沖突向量C為了設(shè)計調(diào)度機構(gòu)，需將禁止表轉(zhuǎn)化為原始沖突向量C（Collision）。C是含N個分量的布爾向量，一般形式為C=(cN...c1)，其中N是預(yù)約表的列數(shù)減1，也可以是禁止表中的最大元素。第i個分量取值原則為：本例中C=(101100)

動態(tài)沖突向量

（初值000000）右移寄存器： 0010110 右移出0“或”運算器： 按位“或” 0接通 1斷開常量發(fā)生器： 101100 原始沖突向量時鐘輸入 流水線 任務(wù)排隊1.每個時鐘脈沖使流水線中現(xiàn)有任務(wù)前進一步，也使右移寄存器移出一位；2.如果新任務(wù)進入，則用它的原始沖突向量與右移寄存器內(nèi)容相“或”。使用沖突向量C實現(xiàn)調(diào)度的原理圖第4步.作狀態(tài)轉(zhuǎn)移圖這是為了研究無窮多個任務(wù)時任務(wù)之間可能存在的合法間隔情況。從表達方便考慮，用動態(tài)沖突向量作為狀態(tài)變量。具體作圖方法是：(1)先畫“根結(jié)點”，它就是第一個任務(wù)進入后的右移寄存器狀態(tài)，數(shù)值等于原始沖突向量；(2)分析當前結(jié)點的各位，如果ci=0則發(fā)出一個旁標i值的箭頭，ci=1則不能發(fā)出箭頭，因為1表示“禁止”。此外還發(fā)出一個旁標“N+1*”的箭頭，“N+1*”意為“≥N+1”；(3)每個箭頭末端產(chǎn)生一個新的結(jié)點，其狀態(tài)等于原結(jié)點狀態(tài)右移i位后與原始沖突向量相“或”；(4)如果新結(jié)點狀態(tài)與已有的結(jié)點重復(fù)，則取消它，箭頭指向已有的那個結(jié)點。第5步.作平均延遲拍數(shù)表(1)在狀態(tài)轉(zhuǎn)移圖中尋找全部簡單循環(huán)填入右表第1欄。所謂簡單循環(huán)是指其中各結(jié)點僅通過一次的閉合路徑。注意它不一定要通過根結(jié)點；(2)計算各簡單循環(huán)的平均間隔拍數(shù)填入右表第2欄。平均間隔拍數(shù)等于該簡單循環(huán)中所有數(shù)字之和除以數(shù)字個數(shù)；(3)取平均延遲拍數(shù)最少的方案作為最優(yōu)方案。本例為(1,1,7)；(4)調(diào)度機構(gòu)實現(xiàn)：計數(shù)器加譯碼電路。本例可用模9計數(shù)器，譯碼條件是計數(shù)值等于0、1、2時允許進入流水線。時間功能段1S1S2S3S4234567891011…11111,21,211,2,322222,333,33,4…………,4

45.6.2改變流水線結(jié)構(gòu)的優(yōu)化調(diào)度方法──預(yù)留算法

目的：等間隔的最小延遲調(diào)度方案方法：插入延遲器件第1步，確定相鄰任務(wù)間隔拍數(shù)：因為最小間隔拍數(shù)是一行內(nèi)“×”的最大數(shù)目（第11行），取最小間隔拍數(shù)。第2步，確定插入延遲器件位置的原則（P302第2行）：從第一個“×”

開始，凡是相距最小間隔拍數(shù)整倍數(shù)位置的“×”都要向后推遲。實例（P301倒數(shù)第7行）：

1.確定間隔拍數(shù)（最多3個“×”，所以是3拍）；

2.插入延遲器件（使各行“×”的間距不為3的倍數(shù)）；

3.修改預(yù)約表（P302圖5.53(a)）；

4.寫調(diào)度方案（3）（示意圖見下頁）5.7超標量/超流水/超長指令字技術(shù)

本節(jié)學(xué)習(xí)其它指令級并行技術(shù)。主要內(nèi)容有超標量技術(shù)、超流水技術(shù)、多操作部件技術(shù)、超長指令字技術(shù)。下面是一些相關(guān)的名詞術(shù)語標量處理機，超標量處理機：標量處理機指只能進行標量運算的處理機，超標量處理機指能在一個時鐘周期內(nèi)同時發(fā)射多條指令的處理機；指令級并行技術(shù)：指能使多條指令并行執(zhí)行的技術(shù)，包括流水技術(shù)、多操作部件技術(shù)和超長指令字技術(shù)；流水線處理機，超流水線處理機：流水線處理機指用流水作業(yè)方式并行解釋多條指令的處理機，超流水線處理機指能在一個時鐘周期內(nèi)分時發(fā)射多條指令的處理機；超長指令字技術(shù)VLIW：指讓一條指令包含多個獨立的操作字段，并且分別控制多個功能部件并行工作的技術(shù)。5.7.1超標量技術(shù)

一個時鐘節(jié)拍內(nèi)同時發(fā)射多條指令

通常，把一個時鐘周期內(nèi)能夠同時發(fā)射多條指令的處理機稱為超標量處理機。超標量處理機最基本的要求是必須有兩套或兩條以上完整的指令執(zhí)行部件。上圖是典型超標量處理機的指令流水線，為了能夠在一個時鐘周期內(nèi)同時發(fā)射多條指令，超標量處理機必須有兩條或兩條以上能夠同時工作的指令流水線。目前，在多數(shù)超標量處理機中，每個時鐘周期發(fā)射兩條指令，通常不超過4條。由于存在有數(shù)據(jù)相關(guān)和條件轉(zhuǎn)移等問題，采用一般的指令調(diào)度技術(shù)，理論上的最佳情況是每個時鐘周期發(fā)射3條指令。對大量程序的模擬統(tǒng)計結(jié)果也表明，每個時鐘周期發(fā)射2至4條指令比較合理。例如，Intel公司的i860、i960、Pentium處理機，Motolora公司的MC88110處理機，IBM公司的Power6000處理機等每個時鐘周期都發(fā)射兩條指令；美國德州儀器公司（TI）為SUN公司生產(chǎn)SuperSPARC處理機每個時鐘周期發(fā)射三條指令。超標量處理機指令調(diào)度要解決的問題數(shù)據(jù)相關(guān)控制相關(guān)功能部件沖突多發(fā)射流水線的調(diào)度問題（例子說明）

共需10個周期。有8個空閑周期，其中4個是為了保證指令的順序發(fā)射順序完成。（1）順序發(fā)射順序完成（2） 順序發(fā)射亂序完成共需9個周期。僅有3個空閑周期。（3）亂序發(fā)射亂序完成共需8個周期，無空閑周期。

超標量處理機性能N條沒有資源沖突、數(shù)據(jù)相關(guān)和控制相關(guān)的指令在單條流水線普通標量處理機上的執(zhí)行時間為：

T(1,1)=(K+N-1)×T把相同的N條指令在一臺每個時鐘周期發(fā)射M條的超標量處理機上執(zhí)行時間為：

T(m,1)=(K+(N-m)/M)×T加速比S(m,1)=T(1,1)/T(m,1)

其中，K是流水線的級數(shù)，T是一個時鐘周期的時間長度。5.7.2超流水技術(shù)

一個時鐘節(jié)拍內(nèi)分時發(fā)射多條指令

超流水線處理機性能在一臺指令級并行度為（1，n）的超流水線處理機上，執(zhí)行N條沒有數(shù)據(jù)相關(guān)和控制相關(guān)的指令所需要的時間為：

T(1,n)=(K+(N-1)/n)×T加速比S(1,n)=T(1,1)/T(1,n)=n×(K+N-1)/(n×K+N-1)1.超標量超流水線處理機 超標量超流水線處理機在一個時鐘周期內(nèi)要發(fā)射指令n次，每次發(fā)射指令m條，因此，超標量超流水線處理機每個時鐘周期總共要發(fā)射指令m×n條。 在下圖中，每一個時鐘周期分為3個流水線周期，每一個流水線周期發(fā)射3條指令。從圖中可以看出，每個時鐘周期能夠發(fā)射并執(zhí)行完成9條指令。因此，在理想情況下，超標量超流水線處理機執(zhí)行程序的速度應(yīng)該是超標量處理機和超流水線處理機執(zhí)行程序速度的乘積。5.7.3超標量超流水技術(shù)2. 超標量超流水線處理機的性能（1）性能 在一臺指令級并行度為（m，n）的超標量超流水線處理機上，連續(xù)執(zhí)行N條沒有資源沖突、沒有數(shù)據(jù)相關(guān)和控制相關(guān)的指令所需要的時間為：

其中，k是指令流水線的時鐘周期數(shù)，而不是流水線級數(shù)?！鱰是一個時鐘周期的時間長度。上式中的第一項是開始m條指令通過指令流水線所需要的時間，第二項是執(zhí)行其余N-m條指令所需要的時間；這時，每一個時鐘周期平均執(zhí)行完成m×n條指令，也就是每一個流水線周期平均執(zhí)行完成n條指令。（2）性能比較（3）結(jié)論：超標量處理機的相對性能最高，其次是超標量超流水線處理機，超流水線處理機的相對性能最低，主要原因如下：超標量處理機在每個時鐘周期的一開始就同時發(fā)射多條指令，而超流水線處理機則要把一個時鐘周期平均分成多個流水線周期，每個流水線周期發(fā)射一條指令。因此，超流水線處理機的啟動延遲比超標量處理機大。條件轉(zhuǎn)移造成的損失，超流水線處理機要比超標量處理機大。在指令執(zhí)行過程中的每一個功能段，超標量處理機都重復(fù)設(shè)置有多個相同的指令執(zhí)行部件，而超流水線處理機只是把同一個指令執(zhí)行部件分解為多個流水級。因此，超標量處理機指令執(zhí)行部件的沖突要比超流水線處理機小。 當橫坐標給出的設(shè)計指令級并行度比較低時，處理機實際指令級并行度的提高比較快。但是，當設(shè)計指令級并行度進一步增加時，處理機實際指令級并行度提高的速度越來越慢。因此，在實際設(shè)計超標量、超流水線、超標量超流水線處理機的指令級并行度時要適當；否則，有可能造成花費了大量的硬件，但實際上處理機所能達到的指令級并行度并不高。目前，一般認為m和n都不要超過4。一個特定程序由于受到本身的數(shù)據(jù)相關(guān)和控制相關(guān)的限制，它的指令級并行度的最大值是確定的。這個最大值主要由程序自身的語義來決定，與這個程序運行在那一種處理機上無關(guān)。因此，上圖中的三條曲線，對于某一個特定的程序，最終都要收攏到同一個點上。當然，對于各個不同程序，這個收攏點的位置也是不同的。

一個程序能夠達到的實際指令級并行度還與所采用的調(diào)度算法有關(guān)。目前，國際上已經(jīng)提出了多種開發(fā)指令級并行性的優(yōu)化調(diào)度算法。對于沒有條件轉(zhuǎn)移操作，沒有輸入輸出，沒有程序調(diào)用和程序中斷，單入口單出口的基本塊程序，實現(xiàn)最優(yōu)調(diào)度并不十分困難。但是，對于一般程序，要充分開發(fā)程序中的指令級并行性，實現(xiàn)最優(yōu)調(diào)度非