計算機系統(tǒng)結構-陳智勇-第4章-流水線計算機設計技術

4.8相關處理和控制機構4.9先進的流水技術—動態(tài)調度4.10超標量處理機和VLIW體系結構4.11超流水處理機4.12超標量超流水處理機習題44.1重疊解釋方式和相關處理4.1.1重疊解釋方式的提出解釋一條機器指令的那些微操作可分解成取指令、分析指令與執(zhí)行指令，從時間上看如圖4.1所示。

取指令指的是按指令計數(shù)器的內(nèi)容訪問主存，取出該指令送到指令寄存器。指令的分析指的是對指令的操作碼進行譯碼，按尋址方式和地址字段形成操作數(shù)的有效地址，并用此有效地址去取操作數(shù)（可能訪主存，也可能訪寄存器），還要為準備取下一條指令提前形成下一條指令的地址等。指令的執(zhí)行則指的是對操作數(shù)進行運算、處理，或存儲運算結果（可能要訪主存）。

指令的解釋方式可以有順序解釋方式和重疊解釋方式。指令的順序解釋方式是指各條機器指令之間順序串行地執(zhí)行，執(zhí)行完一條指令后才取出下一條指令來執(zhí)行，而且每條機器指令內(nèi)部的各條微指令也是順序串行地執(zhí)行，如圖4.2所示。順序執(zhí)行的優(yōu)點是控制簡單。由于下一條指令的地址是在指令解釋過程的末尾形成的，因此無論是由指令計數(shù)器加1，還是由轉移指令把轉移地址送到指令地址計數(shù)器，形成下一條指令的地址，由本條指令轉入下一條指令的時間關系都是一樣的。但由于是順序執(zhí)行的，上一步操作未完成，下一步操作就不能開始。因此，帶來的主要缺點是速度慢，機器各部件的利用率很低。例如，在取指令和取操作數(shù)期間，主存儲器是忙碌的，但是運算器處于空閑狀態(tài)。在對操作數(shù)執(zhí)行運算期間，運算器是忙碌的，而主存卻是空閑的。

指令的另一種解釋方式是重疊解釋方式，在解釋第k條指令的操作完成之前，就可開始解釋第k+1條指令。顯然，重疊解釋并不能加快一條指令的實現(xiàn)，但能加快相鄰兩條以至一段程序的解釋。圖4.3給出了指令的重疊解釋的方式。至于中央處理機、存儲器和輸入輸出設備之間的重疊操作，也是一種重疊方式，是實現(xiàn)I/O指令與其它指令的重疊。在一般的機器上，操作數(shù)和指令是混合存貯于同一主存內(nèi)的，而且主存同時只能訪問一個存貯單元。從圖4.3可以看出，重疊解釋方式需要“取指k+1”與“分析k”在時間上重疊，顯然，對于一般機器，取指需要訪問主存，分析中取操作數(shù)也可能訪問主存。如果不在硬件上花費一定的代價解決好訪主存的沖突，就無法實現(xiàn)“取指k+1”與“分析k”的重疊。

為實現(xiàn)“取指k+1”與“分析k”的重疊對計算機組成有如下要求：

(1)讓操作數(shù)和指令分別存放于兩個獨立編址且可同時訪問的存儲器中；這還有利于實現(xiàn)指令的保護，但這增加了主存總線控制的復雜性及軟件設計的麻煩。

(2)仍然維持指令和操作數(shù)混存，但采用多體交叉主存結構；只要第k條指令的操作數(shù)與第k+1條指令不在同一個存儲體內(nèi)，仍可在一個主存周期（或稍許多一些時間）內(nèi)取得這兩者，從而實現(xiàn)“分析k”與“取指k+1”重疊。當然，若這兩者正好共存于一個體時就無法重疊。(3)增設指令緩沖寄存器。設置指令緩沖寄存器就可以乘主存有空時，預先把下一條或下幾條指令取出來存放在指令緩沖寄存器中。最多可預取多少條指令取決于指令緩沖寄存器的容量。這樣，“分析k”就能與“取指k+1”重疊，因為只是前者需訪主存取操作數(shù)，而后者是從指緩取第k+1條指令。只要每次取指都可從指緩中得到，則“取指k+1”的時間很短，完全可以把這個微操作合并到“分析k+1”內(nèi)，從而由原來的取指、分析、執(zhí)行重疊演變成只需“執(zhí)行k”與“分析k+1”的一次重疊，如圖4.4所示。4.1.2一次重疊工作方式從圖4.4可以看出，為了實現(xiàn)“執(zhí)行k”與“分析k+1”重疊還必須在硬件上保證有獨立的指令分析部件和指令執(zhí)行部件。在實際應用中，“分析”和“執(zhí)行”所需的時間常常不完全一樣，在設計時，應解決好控制上的同步，保證任何時候都只是“執(zhí)行k”與“分析k+1”一次重疊。即任何時候，指令分析部件和指令執(zhí)行部件都只有相鄰兩條指令的解釋?！耙淮沃丿B”解釋方式的優(yōu)點為省硬件，機器內(nèi)只需要一套指令分析部件和指令執(zhí)行部件，也有助于簡化控制。但缺點是，在實際情況中，“分析”和“執(zhí)行”所需的時間常常不完全一樣，設計時應適當安排好每條指令的微操作，使“分析”和“執(zhí)行”所需的時間盡可能等長，才能使重疊方式有較高的效率。如果采用多次重疊，不僅要設置多套指令分析和指令執(zhí)行部件，控制還相當復雜。所以，重疊方式的機器大多數(shù)都采用一次重疊，若仍達不到速度要求時，寧可采用后面要介紹的流水方式。

在實際設計中，為了實現(xiàn)“分析k+1”和“執(zhí)行k”的一次重疊，還需要在硬件控制上解決許多問題。先看轉移指令的處理問題。例如：第k條指令是按其執(zhí)行結果進行轉移的條件轉移指令，當條件轉移不成功時，重疊操作是有效的；但當遇到條件轉移，并且成功轉移到第m條指令時，這時與“執(zhí)行k”重疊的“分析k+1”的操作是無效的，重疊方式實際上變成了順序方式，因為在“執(zhí)行k”的末尾才形成下一條要執(zhí)行指令的地址，顯然，下一條指令應該執(zhí)行第m條指令，

即當?shù)趍條指令在指緩內(nèi)時，應該執(zhí)行的是“分析m”，若不在，應該執(zhí)行的是“取指m”，并且應該是在“執(zhí)行k”結果出來之后。而“分析k+1”（包含了取指k+1）取的是第k+1條指令的內(nèi)容，這就會出錯。圖4.5給出了執(zhí)行條件轉移時指令重疊的情況。

為了避免出錯，第k條和第k+1條指令就不能同時解釋，因此采用重疊方式的機器中應盡量減少程序中條件轉移指令的使用，否則將會使重疊效率顯著下降。如果出現(xiàn)條件轉移指令，可以采用其它技術，如延遲轉移技術，使重疊效率不下降。

控制上還要解決好鄰近指令之間有可能出現(xiàn)的某種關聯(lián)。當一段程序的鄰近指令之間出現(xiàn)某種關聯(lián)后，為了避免出錯而使它們不能同時被解釋的現(xiàn)象稱之為“相關”。相關可以是指令相關，也可以是操作數(shù)相關。指令相關是指第k條指令執(zhí)行的結果會影響第k+1條指令內(nèi)容而產(chǎn)生的關聯(lián)，造成第k條指令和第k+1條指令不能同時解釋。例如，在采用VonNeumann型機器上，可通過執(zhí)行第k條指令的辦法來形成第k+1條指令：

k：存，通用寄存器號，k+1功能：(通用寄存器)k+1k+1：……

由于在“執(zhí)行k”的末尾才形成第k+1條指令，按照一次重疊的時間關系，“分析k+1”所分析的是早已取進指緩的第k+1條指令的舊內(nèi)容，這就會出錯，這種情況就是我們所說的指令相關。特別是當指令緩沖器可緩沖存放n條指令情況下，執(zhí)行到第k條指令時，與已預取進指緩的第k+1到第k+n條指令都有可能發(fā)生指令相關。指令緩沖寄存器的容量愈大，或者說指令預處理能力愈強的機器發(fā)生指令相關的概率就愈高。

操作數(shù)相關是指在第k條指令和第k+1條指令的數(shù)據(jù)地址之間發(fā)生關聯(lián)，而造成第k條指令和第k+1條指令不能同時解釋的現(xiàn)象。例如：第k+1條指令的源操作數(shù)地址i正好是第k條指令存放運算結果的地址。在順序解釋時，由于先由第k條指令把運算結果存入主存i單元，而后再由第k+1條指令從i單元取出，當然不會出錯。但在“分析k+1”與“執(zhí)行k”重疊解釋時，“分析k+1”從i單元取出的源操作數(shù)內(nèi)容成了“執(zhí)行k”存入運算結果前的原始內(nèi)容，而不是第k條指令的運算結果，這必然會出錯。操作數(shù)相關不只是會發(fā)生在主存空間，還會發(fā)生在通用寄存器空間。4.1.3相關處理

1.指令相關的處理對于有指令緩沖器的機器，由于指令是提前由主存取進指緩的，為了判定是否發(fā)生了指令相關，需要進行相當復雜的對多條指令地址與多條指令的運算結果地址比較，看是否有相同的。如果發(fā)現(xiàn)有指令相關，還要讓已預取進指緩中的相關指令作廢，并重取、更換指緩中的內(nèi)容，這樣做不僅操作控制復雜，而且增加了輔助操作時間，特別是要花一個主存周期去訪存重新取指，必然會帶來時間損失。

因為可能被修改的指令是以“執(zhí)行”指令的操作數(shù)形式出現(xiàn)，并存于第k+1條指令的物理地址，而下一條指令又是從該地址取出來的，而指令代碼本身就是數(shù)據(jù)，因此指令相關實際上就轉化成了操作數(shù)相關，統(tǒng)一用處理操作數(shù)相關的方法來解決，從而在程序中就不會發(fā)生指令相關了。

實際上操作數(shù)可能存放于主存，也可能存放于通用寄存器中，因此就有主存空間數(shù)相關和通用寄存器組數(shù)相關。一般的機器中，通用寄存器還可以存放變址值，而變址值是在“分析”的前半時間為形成操作數(shù)地址時所要用到的，它必須在分析時間段的一開始就要訪問變址寄存器。這樣，若在第k條指令“執(zhí)行”的末尾形成的結果正好是第k+1條指令“分析”時所要用的變址值時，還會發(fā)生通用寄存器組的變址值相關。2.主存空間數(shù)相關的處理主存空間數(shù)相關是指相鄰兩條指令之間出現(xiàn)要求對主存同一單元先寫入而后再讀出的關聯(lián)。如果讓“執(zhí)行k”與“分析k+1”在時間上重疊，就會使“分析k+1”讀出的操作數(shù)不是程序要求的第k條指令執(zhí)行完后應當寫入的結果，而造成錯誤。如圖4.6所示。主存空間數(shù)相關的處理方法通常采用推后第k+1條指令的讀操作數(shù)。

具體方法是由存控通過給讀數(shù)、寫數(shù)申請安排不同的訪存優(yōu)先級來解決。通常很多機器都將訪存優(yōu)先級依次定為通道申請、寫數(shù)、讀數(shù)、取指令。這樣，當?shù)趉條和k+1條指令出現(xiàn)主存空間數(shù)相關時，“執(zhí)行k”與“分析k+1”同時對主存同一個單元發(fā)出訪存申請，但因“寫數(shù)”級別高于“讀數(shù)”，存控先處理“執(zhí)行k”的寫數(shù)，“分析k+1”的讀數(shù)申請必然只能推遲到下一個主存周期才有可能被處理，從而就自動實現(xiàn)了推后“分析k+1”的讀，不用處理機另外采取措施。如圖4.7所示。3.通用寄存器組相關的處理通用寄存器既可存放操作數(shù)、運算結果，也可以存放變址值，但是在指令解釋過程中，使用通用寄存器作為不同用途所需的有關微操作時間要求是不相同的。存放于通用寄存器中的基址或變址值一般總是在“分析”周期的前半段就要取出來用；而操作數(shù)則是在“分析”周期的后半段取出，到“執(zhí)行”周期的前半段才用得上；運算結果卻是在“執(zhí)行”周期的末尾才形成，并送入通用寄存器中。

圖4.8給出了它們之間的時間關系。正是因為它們的時間要求不同，所以通用寄存器數(shù)相關和通用寄存器變址值相關的情況及其處理方法不相同。設機器的基本指令格式如圖4.9所示。L1、L3分別指示存放第一操作數(shù)和運算結果的通用寄存器號，B2為形成第二操作數(shù)地址的基址值所在通用寄存器號，d2為相對位移量。

設機器的基本指令格式如圖4.9所示。L1、L3分別指示存放第一操作數(shù)和運算結果的通用寄存器號，B2為形成第二操作數(shù)地址的基址值所在通用寄存器號，d2為相對位移量。(1)通用寄存器組數(shù)相關的情況和處理辦法假設某臺機器正常情況下，“分析”和“執(zhí)行”的周期與主存周期一樣都是4拍。有些指令需要從通用寄存器組中取兩個操作數(shù)（L1）和（L2），若通用寄存器組做在一個片子上，每次只能讀出一個數(shù)，則在“分析k+1”期間，操作數(shù)（L1）和（L2）就需要在不同拍時取得，分別送入運算器的B和C寄存器，以便在“執(zhí)行k+1”時供運算用。這樣“執(zhí)行k”與“分析k+1”間通用寄存器組的時間關系如圖4.10所示。當程序執(zhí)行過程中出現(xiàn)L1（k+1）=L3（k）時就發(fā)生了L1相關；而當L2（k+1）=L3（k）時就發(fā)生了L2相關。

當程序執(zhí)行過程中出現(xiàn)要解決通用寄存器組數(shù)相關的情況，主要有以下兩種方法：①與前述處理主存空間數(shù)相關的一樣，推后“分析k+1”的讀（寄存器的內(nèi)容）。具體有兩種不同的方法：可以把“分析k+1”推后到“執(zhí)行k”結束時開始，也可以只要推后到“執(zhí)行k”把結果送入L3，然后再由“分析k+1”在?。↙1）或（L2）時能取到就可以了。采用前一種推后的辦法，只要發(fā)生數(shù)相關就使一次重疊變成了完全的順序串行，速度明顯下降；后一種推后的方法則是發(fā)生數(shù)相關時，相鄰兩條指令的解釋仍有部分重疊，可以減少速度損失，但控制要稍微復雜一些。

這兩種方法都是靠推后讀，犧牲速度來避免相關時出錯。那么能否在不降低速度的情況下仍然能保證數(shù)相關時的正確處理呢？②在運算器的輸出到B、C輸入之間增設一條“相關專用通路”，如圖4.11所示，則在發(fā)生L1或L2相關時，讓相關專用通路接通，就可以在“執(zhí)行k”時將運算結果送入通用寄存器以在完成其應有的功能的同時，直接將運算結果回送到B或C寄存器，從而大大縮短了其間的傳送時間，并能保證當“執(zhí)行k+1”需要用此操作數(shù)時，它已在B或C寄存器中準備好了。

也就是說，盡管原先將通用寄存器的舊內(nèi)容經(jīng)數(shù)據(jù)總線分別在“分析k+1”的第3拍或第4拍末送入了操作數(shù)寄存器B或C中，但之后經(jīng)相關專用通路在“執(zhí)行k+1”真正用它之前，操作數(shù)寄存器B或C重新獲得第k條指令送來的新結果。這樣，既保證了相關時不用推后“分析k+1”，重疊效率不下降，又可以保證指令重疊解釋時數(shù)據(jù)不出錯。

推后“分析k+1”和設置“相關專用通路”是解決重疊方式相關處理的兩種基本方法。兩者的主要區(qū)別為前者是以降低速度為代價，使設備基本上不增加，后者是以增加設備為代價，使重疊效率不下降。“相關專用通路”法照樣可用于解決前述的主存空間數(shù)相關，但由于主存空間數(shù)相關的出現(xiàn)概率比通用寄存器組數(shù)相關的出現(xiàn)概率低得多，所以，主存數(shù)相關不采用“相關專用通路”法，而只采用推后讀來解決。(2)通用寄存器組基址值或變址值相關的情況及其處理辦法在采用基址尋址時，操作數(shù)的有效地址為：(Xd)+(B2)·(B2≠0000)+d2，由分析器內(nèi)的地址加法器形成。由于通常情況下，“分析”周期等于主存周期，所以，從時間關系上要求在“分析”周期的前半段，就能由通用寄存器輸出總線取得(B2)，送入地址加法器。

由于運算結果是在“分析”周期的末尾才送入通用寄存器組的，它當然不能立即出現(xiàn)在通用寄存器輸出總線上。也就是說，在“執(zhí)行k”得到的、送入通用寄存器的運算結果來不及作為“分析k+2”的基址值用，更不用說作為“執(zhí)行k+1”的基址值用。因此，雖然是一次重疊，但基址值相關(B相關)就不止會出現(xiàn)一次相關，還會出現(xiàn)二次相關。即當出現(xiàn)B（k+1）=L3(k)

時，稱為發(fā)生了B一次相關；而當出現(xiàn)B（k+2）=L3(k)時，稱為發(fā)生了B二次相關。這里所謂的一次和二次指的是相關指令相隔的指令條數(shù)。

對于基址值相關，其解決辦法同數(shù)相關的一樣，也可有推后分析（讀基址寄存器的內(nèi)容）和設置相關專用通路兩種。變址值相關與基址值相關類似，處理方法也一樣。①推后分析的方法。由圖4.12可看出，對于B二次相關，只需推后“分析k+2”的始點，使“執(zhí)行k”送入通用寄存器的運算結果，在“分析k+2”開始時已出現(xiàn)于通用寄存器的輸出總線上，如圖4.13（a）所示。而對B一次相關，則除此之外，還需要推后一個“執(zhí)行”周期，如圖4.13（b）所示。②設置相關專用通路的方法。由于B一次、二次相關的概率并不很低，增設B相關專用通路還是值得的，其辦法如圖4.14所示。這樣，在B二次相關時，就可把“執(zhí)行k”得到的運算結果，在送入通用寄存器組的同時，經(jīng)“B相關專用通路”直接送到“訪存操作數(shù)地址”形成機構，由于縮短了其間的傳送延遲，使得不必推后“分析k+2”，就能保證使用正確的基址值。同理，在B一次相關時，只需使“分析k+1”推后到接著“執(zhí)行k”進行就可以了。

綜上所述，實現(xiàn)在時間上的重疊，(1)需要付出空間代價；如增設數(shù)據(jù)總線和控制總線、指令緩沖器、地址加法器、相關專用通路等，需將指令分析部件和指令執(zhí)行部件分開、單獨設置，需將主存采用多體交叉存取等等。(2)要處理好這二條指令之間可能存在的關聯(lián)。如轉移的處理以及指令相關、主存空間數(shù)相關、通用寄存器組的數(shù)相關和在址/變址值相關等的處理。相關處理的辦法無非是“推后讀”和設置相關專用通路兩種，應當根據(jù)Huffman概念在成本和效率上加以權衡選用。(3)還應合理安排調配好機器每條指令的微操作，使“分析”和“執(zhí)行”所需的時間盡可能匹配，以提高重疊的效率。4.2流水線的工作原理

如果CPU用一次重疊方式解釋指令仍達不到所要求的速度性能時,可以考慮同時解釋多條指令。其中最常用的是流水方式，它是通過并行硬件來改善性能的最普通的手段。在60年代，硬件的價格相對較高，流水線計算機都是巨型機。IBM的STRETCH和CDC的6600就是60年代早期大量應用流水線的兩種機器，它們對后來巨型機的結構產(chǎn)生了深刻的影響。

到了80年代，技術的進步使硬件價格大幅度下降，使流水線技術能在各種類型的計算機上得到應用。例如，Intel8086微處理機雖然價格十分低廉，也能在芯片執(zhí)行運算的同時應用流水線技術訪問存儲器。而發(fā)展到Pentium系列CPU產(chǎn)品的時候，更是一個高級的超標量處理器?？梢哉f，計算機發(fā)展到現(xiàn)在，流水技術已經(jīng)成為各類機器普遍采用的、用來改善性能的基本手段。

計算機的流水技術是如何工作的呢？流水技術的基本思想在馮·諾依曼的第一臺存儲程序計算機中已經(jīng)提出。流水技術早已應用于社會生產(chǎn)與活動的各個方面，并不是計算機所特有的。其主要特點是在一個任務完成以前就可以開始一個新的任務。先看一次重疊的情況，“執(zhí)行k”與“分析k+1”的一次重疊是把一條指令的解釋過程分解成“分析”與“執(zhí)行”兩個子過程，分別在獨立的分析部件和執(zhí)行部件上進行。因此，不必等一條指令的“分析”、“執(zhí)行”子過程都完成才送入下條指令，而是分析部件在完成一條指令的“分析”子過程時，就可開始下一條指令的“分析”子過程。

若“分析”與“執(zhí)行”子過程都需要Δt的時間，如圖4.15所示，就一條指令的解釋來看，需要2Δt才能完成，但從機器的輸出來看，每隔Δt就能完成一條指令的解釋。也就意味著，一次重疊解釋比起指令的串行解釋，可使機器的最大吞吐率提高一倍。這里的最大吞吐率是指當流水線正常滿負荷工作時，單位時間內(nèi)機器所能處理的最多指令條數(shù)或機器能輸出的最多結果數(shù)。若將指令的分析和執(zhí)行部分進一步細分成一些子過程，并改進相應硬件的結構，使得子過程分別由獨立的子部件實現(xiàn)，形成流水處理的方式，其最大吞吐率可進一步提高，如圖4.16的流水處理過程和相應的時-空圖。

如圖4.16(a)所示，把“分析”子過程再細分成“取指令”、“指令譯碼”和“取操作數(shù)”3個子過程，并改進運算器的結構以加快其“執(zhí)行”子過程，這4個子過程分別由獨立的子部件實現(xiàn)，讓經(jīng)過各子部件的時間都相同，用Δt1表示，則指令解釋的時間-空間關系如圖4.16(b)所示。一條指令從進入流水線到結果流出需經(jīng)歷“取指令”、“指令譯碼”、“取操作數(shù)”和“執(zhí)行”4個子過程，每個子過程需要Δt1的時間，一條指令的解釋需要4Δt1的時間完成。

當?shù)?條指令完成“取指令”子過程時，就可以開始第2條指令的“取指令”子過程；當?shù)?條指令完成“指令譯碼”子過程而進入“取操作數(shù)”子過程時，可以開始第2條指令的“指令譯碼”子過程，同時，第2條指令的“取指令”子過程結束，可以開始第3條指令的“取指令”子過程；依此類推，當?shù)?條指令進入“執(zhí)行”子過程時，第2條指令可進入“取操作數(shù)”子過程，第3條指令可進入“指令譯碼”子過程，第4條指令可進入“取指令”子過程。顯然，圖4.16(b)中的流水線可同時解釋4條指令。

如果完成一條指令的時間為T，則對于分解為“分析”和“執(zhí)行”兩個子過程的，其T=2Δt，而對于分解為“取指令”、“指令譯碼”、“取操作數(shù)”和“執(zhí)行”4個子過程的，其T=4Δt1。這樣，雖然完成一條指令所需時間仍是T，對于順序解釋方式，每隔T由處理機“流出”一個結果；但對圖4.15的重疊方式是每隔T/2（即每隔Δt）就可由處理機“流出”一個結果，吞吐率提高了一倍；而對圖4.16的流水方式是每隔T/4（即每隔Δt1）“流出”一個結果，即吞吐率比順序方式提高了三倍。

流水處理帶來的好處是顯而易見的，以圖4.16為例，若進入流水線的指令數(shù)為6，則其從第1條指令流入流水線，到最后一條指令的結果流出，使用的時間是9Δt1，即9T/4的時間；如果是順序執(zhí)行，則需要6T的時間，從一組指令序列的執(zhí)行速度來看，采用流水解釋方式的機器的速度要比順序解釋方式的機器快得多。“流水”在概念上與“重疊”沒有什么差別，可以看成是“重疊”的進一步引伸。兩者的差別只在于“一次重疊”只是把一條指令的解釋分解為兩個子過程，而“流水”則是分解成更多個子過程。前者同時解釋兩條指令，后者可同時解釋多條指令。例如圖4.16的流水處理過程可同時解釋4條指令。如果能把一條指令的解釋分解成時間相等的N個子過程，則每隔Δt=T/N就可以處理一條指令。如圖4.17所示，這意味著，流水線的最大吞吐率是取決于子過程所經(jīng)過的時間Δt，Δt越小，流水線的最大吞吐率就越高。

如果流入流水線的指令數(shù)為6，則從第1條指令流入，到第6條指令的結果流出，所需要的時間為（NΔt+5Δt）。如果流入流水線的指令數(shù)是X，則從第1個指令流入，到第X條指令的結果流出，所需要的時間為（NΔt+(X-1)Δt）。設流水線對一條指令的解釋可以細分為n個子過程，每個子過程處理的時間均為Δt，若有m條指令進入該流水線，則從第1條指令流入，到第m條指令的結果流出所需要的時間定義為Tm，則有：

從第1條指令流入流水線開始，到最后一個結果流出的這一段時間內(nèi)，每隔Δt流出一個結果。應該注意的是，只有當流水線正常滿負荷流動時，才會每隔Δt流出一個結果。流水線從開始啟動工作到流出第一個結果，需要經(jīng)過一段流水線的建立時間，在這段時間里流水線并沒流出任何結果。

在計算機實際的流水線中，各子部件經(jīng)過的時間會有差異。為解決這些子部件處理速度的差異，一般在子部件之間需設置高速接口鎖存器。所有鎖存器都受同一時鐘信號控制來實現(xiàn)各子部件信息流的同步推進。時鐘信號周期不得低于速度最慢子部件的經(jīng)過時間與鎖存器的存取時間之和，還要考慮時鐘信號到各鎖存器可能存在時延差。所以，子過程的細分，會因鎖存器數(shù)增多而增大指令或指令流過流水線的時間，這在一定程度上會抵消子過程細分而使流水線吞吐率得到提高的好處。4.3流水線的特點

在流水技術中，一般有如下特點：一條流水線通常由多個流水段組成；各個流水段分別承擔不同的工作，也可以把這些流水段看作功能部件。如在圖4.16(a)中，流水段由四部分組成，依次是“取指令”、“指令譯碼”、“取操作數(shù)”和“執(zhí)行”4個功能段。在實際機器中，一條流水線的功能部件按完成的任務及采用的設計思想不同，其數(shù)目也各不相同。

例如，80486、Pentium的流水線設計為5段，PentiumIII的流水線設計為10段，AMDAthlon的流水線有11段，PentiumIV的流水線達到了20段，MIPS的R4000有8個流水段，DEC的Alpha21064處理機共有三條指令流水線，整數(shù)操作流水線和訪問存儲器流水線分為7個流水段，而浮點操作流水線分為10個流水段。每個流水段有專門的功能部件對指令進行某種加工；例如，80486的流水線分為5段，分別為“取指令”、“譯碼段1”、“譯碼段2”、“執(zhí)行”和“寫回”。在譯碼段1完成所有的操作碼和尋址方式的譯碼工作。而在譯碼段2則將每個操作碼擴展成對ALU的控制信號。在執(zhí)行段則要完成ALU運算、Cache訪問和寄存器修改。

各流水段所需的時間是一樣的；在設計流水線的控制線路及計算流水線的性能時會帶來方便，簡化了設計。但在實際機器中，各流水段所需的時間很難保證一致。流水線工作階段可分為建立、滿載和排空三個階段。從第一個任務進入流水線到流水線所有的部件都處于工作狀態(tài)的這一個時期，稱為流水線的建立階段。當所有部件都處于工作狀態(tài)時，稱為流水線的滿載階段。從最后一條指令流入流水線到結果流出，稱為流水線的排空階段。在理想情況下，當流水線充滿后，每隔Δt時間將會有一個結果流出流水線。4.4流水線的分類

從不同的角度，可對流水線進行不同的分類。

4.4.1根據(jù)向下擴展和向上擴展的思想分類依據(jù)向下擴展和向上擴展的思想，可分類出在計算機系統(tǒng)不同等級上使用的流水線。向下擴展是指把子過程進一步向下細分，讓每個子過程經(jīng)過的時間都同等程度地減少，吞吐率就會進一步提高。如把圖4.15中的“分析”子過程細分為“取指令”、“指令譯碼”和“取操作數(shù)”3個子過程。

在機器中“執(zhí)行”子過程會因指令不同，執(zhí)行時間不同，而使細分的情形不同。如浮點加法可進一步細分成為“求階差”、“對階”、“尾數(shù)相加”和“規(guī)格化”4個子過程，如圖4.18所示。

子過程的進一步細分是以增加設備為代價的。例如，“求階差”和“尾數(shù)相加”都要用到加法器，為此需要分別設置階碼加法器和尾數(shù)加法器?！皩﹄A”和“規(guī)格化”都要用到移位也就需要分別設置兩套移位器。設備的增加不僅會使成本增加，也使控制變得復雜。但它比起完全靠重復設置多套分析部件和執(zhí)行部件來提高指令并行性，其設備量的增加畢竟要少得多。子過程細分并不是無止境的，因為級間緩沖器數(shù)的增多，使成本提高，輔助延時增大，控制復雜，電路設計和實現(xiàn)困難等，抵消了子過程細分帶來的好處。PentiumIII的流水線設計為10段，AMDAthlon的流水線有11段，PentiumIV的流水線達到了20段，PentiumIV的Willamette版本在運行一些測試程序時，其性能比相同時鐘頻率PentiumIII及AMDAthlon要低10%～20%。但是子過程的細分可以在相同設計條件和生產(chǎn)工藝下提高芯片的時鐘頻率，PentiumIII處理器擁有10級的流水線設計，其頻率很難超過1GHz；而PentiumIV處理器采用了20級的流水線，其頻率已經(jīng)突破3GHz。

流水的向上擴展可理解為在多個處理機之間進行流水。如圖4.19所示。多個處理機串行地對數(shù)據(jù)集進行處理，某個處理機專門完成其中的一個任務。因為各個處理機都在同時工作，所以能對多個不同的數(shù)據(jù)集流水地處理，使計算機系統(tǒng)處理能力有較大的提高。

綜上所述，按流水處理的級別不同，可以把流水線分為部件級、處理機級和系統(tǒng)級的流水。部件級流水是指構成部件內(nèi)的各個子部件之間的流水，如運算器內(nèi)浮點加法流水線及Cache和多體交叉主存的流水。處理機級流水是指構成處理機的各個部件的流水，如“取指”、“分析”、“執(zhí)行”間的流水。系統(tǒng)級流水是指構成計算機系統(tǒng)的多個處理機之間的流水，也稱為宏流水。4.4.2按流水線功能的多少分類按流水線具有功能的多少來劃分，可以分為單功能流水線和多功能流水線。單功能流水線是指只能完成一種固定功能的流水線。Cray-1計算機中有12條單功能流水線，分別為：地址加、地址乘、標量加、標量移位、標量邏輯運算、標量加1計數(shù)、向量加、向量移位、向量邏輯運算、浮點加、浮點乘、浮點迭代求倒數(shù)；Pentium有一條5段的定點和一條8段的浮點流水線；PentiumⅢ有三條指令流水線，其中兩條定點指令流水線，一條浮點指令流水線，其流水線的功能段為10個。

多功能流水線是指同一流水線的各個段之間可以有多種不同的聯(lián)接方式以實現(xiàn)多種不同的運算或功能。例如美國Texas公司的ASC計算機運算器的流水線就是多功能的，它有8個可并行工作的獨立功能段，能夠實現(xiàn)：定點加減法、定點乘法、浮點加減法、浮點乘法、邏輯運算、移位操作、數(shù)據(jù)轉換、向量運算等。

如圖4.20所示，TI-ASC機器要進行浮點加、減法時，其流水線功能段的聯(lián)接如圖4.20(b)所示；而要進行定點乘法運算時，其流水線功能段的聯(lián)接如圖4.20(c)所示。除此之外，它還可以根據(jù)運算的要求來實現(xiàn)多種不同的聯(lián)接。4.4.3按流水線的工作方式分類按多功能流水線的各段能否允許同時用于多種不同功能聯(lián)接流水，可把流水線分為靜態(tài)流水線和動態(tài)流水線。靜態(tài)流水線是指在同一時間內(nèi)，多功能流水線中的各個功能段只能按一種功能的聯(lián)接方式工作。就指令級流水而言，僅當流入的是一串相同運算的指令時，才能發(fā)揮出靜態(tài)流水線的效能。若進入的是浮加、定乘、浮加、定乘……這樣一串不同指令相間時，靜態(tài)流水線的效能會降低到比順序方式的還要差。

因此，在靜態(tài)流水線機器中，要求程序員編制出（或是編譯程序生成）的程序應盡可能調整成有更多相同運算的指令串，以提高其流水的效能。以TI-ASC機器的流水線為例，如果先執(zhí)行n條浮點加法指令，再執(zhí)行m條定點乘法指令，其時-空圖如圖4.21所示。

而動態(tài)流水線是指在同一時間內(nèi)，多功能流水線中的各個功能段可按不同運算或功能的聯(lián)接方式工作。如圖4.22所示，在同一時間段內(nèi)，某些段按浮點加法聯(lián)接，而另一些段按定點乘法聯(lián)接。這樣做的好處在于，不要求流入流水線的指令串有相同的功能也能提高流水的吞吐率和設備的利用率。

從圖4.21和圖4.22比較，靜態(tài)流水線與動態(tài)流水線的差別在于：對于相同的一串運算功能不同的指令而言，動態(tài)流水線的吞吐率和設備利用率比靜態(tài)流水線的高；由于在同一時間內(nèi)，可以通過不同的聯(lián)接實現(xiàn)不同的運算，故動態(tài)流水線的控制比靜態(tài)流水線要復雜，需增加相應硬件，故成本比靜態(tài)流水線的高；從軟、硬件功能分配的觀點上看,靜態(tài)流水線把功能負擔較多地加到軟件上，以簡化硬件控制，而動態(tài)流水線則把功能負擔較多地加在硬件控制上，以提高流水的效能。4.4.4按流水線的連接方式分類根據(jù)流水線中各功能段之間是否有反饋回路，可把流水線分為線性流水線和非線性流水線。若流水線各段串行聯(lián)接，沒有反饋回路，各個段只經(jīng)過一次的，稱為線性流水線。而如果流水線中除有串行聯(lián)接的通路外，有某種反饋回路，使一個任務流經(jīng)流水線時，需多次經(jīng)過某個段或越過某些段，則稱之為非線性流水線。在非線性流水線中，一個重要的問題是確定什么時候向流水線送入新的任務，使此任務流經(jīng)流水線各段時不會與先進入的任務爭用流水段。這個問題將在本章4.7節(jié)中討論。4.5線性流水線性能分析

衡量流水線處理機性能的指標主要是吞吐率和效率，本節(jié)將以線性流水線為例討論流水線處理機的性能。

4.5.1吞吐率和加速比

1.吞吐率(throughputrate)

吞吐率指單位時間內(nèi)流水線能處理的指令條數(shù)或能輸出的數(shù)據(jù)量。吞吐率越高，計算機系統(tǒng)的處理能力就越強。對流水線而言，吞吐率就是單位時間內(nèi)能流出的任務數(shù)或能流出的結果數(shù)。(1)最大吞吐率最大吞吐率是指在流水線正常滿負荷工作時，單位時間內(nèi)機器所能處理的最多指令條數(shù)或機器能輸出的最多結果數(shù)。由于指令的取指和執(zhí)行過程中的各個子過程所需的時間不同，為了避免各段之間經(jīng)過時間不匹配，也為了保證各段之間數(shù)據(jù)通路寬度上能匹配，通常都要在各子過程之間插入一個鎖存器，這些鎖存器都受同一個時鐘脈沖的控制，從而達到同步。如果指令的解釋細分為n個子過程，且各個子過程所需的時間分別為Δt1、Δt2、Δt3、…、Δtn，時鐘周期應當為max{Δt1、Δt2、Δt3、…、Δtn}，對應于流水線的最大吞吐率為：

由此可以看出，流水線的最大吞吐率取決于最慢子過程所需要的時間，我們把流水線中經(jīng)過時間最長的子過程稱為“瓶頸”子過程。(4.1)

如圖4.23(a)所示，有一個4段的指令流水線，其中A、C、D段經(jīng)過的時間均為Δt，而B段的處理時間需要3Δt，則B段就是該指令流水線的瓶頸。根據(jù)流水線的最大吞吐率公式，其最大吞吐率TPmax=1/(3Δt)，即流水線滿負荷工作時，只能每隔3Δt才解釋完一條指令，每隔3Δt才能流出一個結果。其時-空圖如圖4.23(b)所示。

顯然，流水線的最大吞吐率受限于瓶頸子過程，要提高流水線的最大吞吐率，應當設法消除此瓶頸子過程。消除瓶頸的一種辦法是將瓶頸子過程再細分。如對圖4.23(a)的B段進一步進行細分，將其再細分為三個段B1、B2和B3，并且每個段的處理時間都是Δt，這樣，該指令流水線的最大吞吐率就變成1/Δt。如圖4.24所示。并不是所有子過程都可以進一步細分，如對圖4.23(a)中的B段如果不能進一步細分，可以采用消除瓶頸的另一種辦法，即重復設置多套瓶頸段并聯(lián)，讓它們交叉進行。

對于圖4.23(a)所示的問題，則可以采用三套B段并聯(lián)，分別以BS1、BS2、BS3命名，每隔Δt輪流給一個瓶頸段分配任務，使它們?nèi)钥擅扛籀解釋完一條指令。如圖4.25所示，其流水線的最大吞吐率也是1/Δt。這種辦法需要解決好在各并行子過程之間的任務分配和同步控制，比起瓶頸子過程再細分控制要復雜、設備量要多些。(2)實際吞吐率流水線的實際吞吐率用TP表示，是指從啟動流水線處理機開始到流水線操作結束，單位時間內(nèi)能流出的任務數(shù)或能流出的結果數(shù)。前面的分析都是在流水線連續(xù)流動時能達到的最大吞吐率。實際上，流水開始時總要有一段建立時間，此外還常常會由于各種原因，如功能部件沖突等使流水線無法連續(xù)流動，不得不流一段時間，停一段時間，因此實際吞吐率TP總是小于最大吞吐率TPmax。

設指令流水線由m段組成，如圖4.26所示，且各段經(jīng)過的時間均為Δt，則一條指令的解釋需要mΔt的時間，之后每隔Δt完成一條指令的解釋，則完成n條指令的解釋所需要的時間為：

該流水線的實際吞吐率為：(4.2)

從式4.2可以看出，實際吞吐率總是小于最大吞吐率，只有當進入流水線的任務數(shù)遠大于流水線功能段的數(shù)目時，即時，才能使實際吞吐率趨近于最大吞吐率，或者可以近似認為TP=TPmax。對于圖4.26，如果流入流水線的任務數(shù)不是n，而是周期性的任務，即每流入n條指令之后，延遲ΔT的時間，再流入n條指令，延遲ΔT之后，再流入n條指令，周而復始，則這時的流水線的實際吞吐率TP就應為：(4.3)

綜上所述，流水線的實際吞吐率除了與該流水線的功能段數(shù)目有關外，還與流入該流水線的指令流或任務流有關。指令流不同，其實際吞吐率也不同。在實際應用中，除了在硬件上對子過程細分外，還應當從軟件上采取措施，如選擇合適的算法、程序設計方法、編譯器等，從軟、硬兩方面入手，保證在流水線中連續(xù)流動的任務數(shù)n能遠遠大于子過程數(shù)m，才能充分發(fā)揮流水線的效率。否則，在極端情況下，即n=1的時候，由于m的增大，鎖存器數(shù)也增多，這樣實際上增大了任務從流入到流出的流水線通過時間，以至于使其速度反而比順序串行的還要低。

如果各段經(jīng)過的時間Δti不相等，其中“瓶頸”段時間為Δtj，完成n條指令的解釋，流水線的實際吞吐率為：(4.4)2．加速比(speedupratio)

所謂加速比是指流水線工作相對于等效的非流水線順序串行工作方式，速度提高的比值。設指令流水線由m段組成，各段經(jīng)過的時間均為Δt，共完成n條指令的解釋，則此流水線方式工作的加速比為：(4.5)

由式4.5可以看出，當n>>m時，流水線的加速比Sp才接近于流水線的段數(shù)m，也就是說，當流水線各段時間都一樣時，其最大加速比等于流水線的段數(shù)m。因此，在n>>m的前提下，增大流水線的段數(shù)m，可以提高流水線的加速比Sp。如果考慮各段經(jīng)過的時間Δti不相等，其中“瓶頸”段時間為Δtj，完成n條指令的解釋，則此流水線方式工作的加速比為：(4.6)4.5.2效率(efficiency)

流水線的效率是指流水線的設備利用率。即在整個運行時間里，流水線的設備有百分之多少的時間是真正用于工作的。由于流水線存在有建立時間和排空時間，在連續(xù)完成n個任務的時間里，各段并不是滿負荷工作的，因此流水線的效率一定小于1。設指令流水線由m段組成，各段經(jīng)過的時間均為Δt，完成n條指令的解釋，流水線的效率為：η1+η2+…+ηmm·η1m·nΔtm·nΔtη===η1==(4.7)mmm·(mΔt+(n-1)Δt)m·T

對于式4.7，從時-空圖上來看，所謂效率實際就是n個任務占用的時-空區(qū)和m個段總的時-空區(qū)面積之比。如果考慮各段經(jīng)過的時間Δti不相等，其中“瓶頸”段時間為Δtj，完成n條指令的解釋。由于流水線的效率實際上就是n個任務占用的時-空區(qū)和m個段總的時-空區(qū)面積之比，因此，整個流水線的效率為：η1+η2+…+ηmn·∑Δti

η==(4.8)mm·(∑Δti+(n-1)Δtj)

mmi=1i=1

比較各種公式，可以得出如下結論：

(1)Sp=TP·ΣΔti(2)η=Sp/m

mi=14.6線性流水線性能分析舉例

對于單功能線性流水線，輸入連續(xù)任務的情況，通過上一節(jié)給出的公式很容易計算出流水線的吞吐率、加速比和效率。

例4.1

用一條4段浮點加法器流水線求8個浮點數(shù)的和：Z＝A＋B＋C＋D＋E＋F＋G＋H。已知流水線的各段經(jīng)過時間都是Δt，流水線的輸出結果可以直接返回到流水線的輸入或暫存于相應的緩沖寄存器中，其延遲時間忽略不計。流水線為雙輸入端，如圖4.27(a)所示。

實現(xiàn)8個浮點數(shù)的相加，先完成A+B、C+D、E+F、G+H，然后（A+B）和（C+D）、（E+F）和（G+H）又作為新的輸入進入流水線，分別實現(xiàn)A+B+C+D及E+F+G+H，最后完成所要求的加法，如圖4.27所示。這樣，流入流水線的任務數(shù)為7個，從時-空圖上可以看出，從任務開始到結束，共需15Δt，而順序完成7個任務需要的時間為7×4Δt=28Δt。因此，該流水線的實際吞吐率為：TP=7/(15Δt)

加速比為：Sp=28Δt/(15Δt)≈1.87

效率為：η=28Δt/(4×15Δt)≈46.7%

例4.2

設有二個向量A、B，各有4個元素，要在如圖4.28所示的靜態(tài)雙功能流水線上，計算向量點積A·B=Σai×bi。在該雙功能流水線中，S1→S2→S3→S5組成加法流水線，S1→S4→S5組成乘法流水線。設每個流水段所經(jīng)過的時間為Δt，而且流水線的輸出結果可以直接返回到輸入或暫存于相應的緩沖寄存器中，其延遲時間和功能切換時間忽略不計。使用合理的算法，能使完成向量點積A·B運算所用的時間最短，并求出流水線在此期間的實際吞吐率TP和效率η。

選擇適合于靜態(tài)流水線工作的算法：⑴連續(xù)計算a1×b1、a2×b2、a3×b3、a4×b44個乘法；⑵等執(zhí)行乘法工作的流水線排空后，進行功能部件的切換，按加法的方式聯(lián)接流水線功能部件，連續(xù)計算(a1×b1+a2×b2)、(a3×b3+a4×b4)；⑶產(chǎn)生了上述兩個結果后，再最后計算：(a1×b1+a2×b2)+(a3×b3+a4×b4)。顯然，最后總共流入多功能流水線的任務數(shù)為7個，完成任務所需的時間為15Δt，而順序完成7個任務需要的時間為4×3Δt+3×4Δt=24Δt。

因此，該流水線的實際吞吐率為：TP=7/(15Δt)

效率為：η=24Δt/(5×15Δt)=32%

前面討論的是靜態(tài)流水線，如果把靜態(tài)流水線改為動態(tài)流水線，其它條件不變，那么，在計算向量點積A·B=Σai×bi時，流水線在此期間的吞吐率TP和效率η又該是多少呢？動態(tài)流水線的時-空圖如圖4.29所示。

從圖4.29中可以看出，進入流水線的任務數(shù)還是7個，但所需要的時間比靜態(tài)流水線少Δt，只需要14Δt就可完成。在此期間，動態(tài)流水線的實際吞吐率為：TP=7/(14Δt)=1/(2Δt)

效率為：η=(4×3Δt+3×4Δt)/(5×14Δt)≈34.3%

從以上兩個例子可以看出，動態(tài)流水線與靜態(tài)流水線相比，具有較高的實際吞吐率和效率。4.7非線性流水線的基本概念

前面討論都是以線性流水線為基礎的，由于線性流水線在執(zhí)行每個任務（指令、操作）的過程中，各段均只通過一次，因此每拍都可以將一個新的任務送入流水線，這些任務不會爭用同一個流水段。在非線性流水線中，由于存在有反饋回路，當一個任務在流水線中流過時，在同一個功能段可能要經(jīng)過多次。因此，就不能每一個時鐘周期向流水線輸入一個新任務，否則會發(fā)生在同一個時刻有幾個任務爭用同一個功能段的情況。這種情況稱為功能部件沖突，或流水線沖突。

為了避免流水線發(fā)生沖突，一般采用延遲輸入新任務的方法。那么，在非線性流水線的輸入端，究竟每間隔多少個時鐘周期向流水線輸入一個新任務才能使流水線的各個功能段都不發(fā)生沖突，這就是非線性流水線的調度問題。在許多非線性流水線中，間隔的周期數(shù)往往不是一個常數(shù)，而是一串周期變化的數(shù)字。因此，非線性流水線調度的任務是要找出一個最小的循環(huán)周期，按照這周期向流水線輸入新任務，流水線的各個功能段都不會發(fā)生沖突，而且流水線的吞吐率和效率最高。

在非線性流水線的表示中，它與線性流水線有2個明顯不同的地方：

(1)有反饋線和前饋線；

(2)其輸出端經(jīng)常不在最后一個功能段，而可能從中間任意一個功能段輸出。典型的非線性流水線的連接圖如圖4.30所示。

為了能對流水線的任務進行優(yōu)化調度和控制，1971年E.S.Davidson提出使用一個二維的預約表(reservationtable)來描述一個任務在非線性流水線中對各功能段的使用情況。預約表用于非線性流水線，是一張二維的表格，其橫坐標表示流水線工作的時鐘周期，縱坐標表示流水線的功能段，中間畫“√”表示該功能段在這一時鐘周期處于工作狀態(tài)，空白的地方表示該功能段在這個時鐘周期不工作。

在預約表中，一行有多個“√”表示一個任務在不同時鐘周期重復使用了同一個功能段；而一列有多個“√”則表示在同一個時鐘周期同時使用了多個功能段。預約表的總行數(shù)表示流水線功能段的個數(shù)，總列數(shù)表示一個任務從流入到流出所經(jīng)過的時鐘周期數(shù)。對于圖4.30的流水線，由5個功能段組成，段號k分別為1到5，任務經(jīng)過流水線總共需N=9拍，假設其預約表如圖4.31所示。

值得說明的是：(1)一張非線性流水線的預約表可能與多個非線性流水線連接圖相對應；(2)一個非線性流水線的連接圖也可能對應多張預約表。因此，一條非線性流水線一般需要一個各功能段之間的連接圖和一張預約表來共同表示。

根據(jù)預約表可以很快得出一個任務使用圖4.30的流水線各段所需間隔的拍數(shù)。將流水線中所有各段對一個任務流過時，產(chǎn)生爭用同一段的節(jié)拍間隔數(shù)匯集在一起，構成一個延遲禁止表F(forbiddenlist)。從圖4.31所給出的預約表，l段相隔8拍，那么兩個任務相隔8拍流入流水線必將會爭用1段；2段相隔1、5、6拍，則相隔1、5或6拍流入流水線必將會爭用2段；5段相隔1拍，兩個任務相隔1拍流入流水線必將會爭用4段；4段相隔1拍，兩個任務相隔1拍流入流水線必將會爭用5段。由圖4.31的預約表可以得到相應非線性流水線的延遲禁止表F為(1，5，6，8)。即要想不出現(xiàn)爭用流水線功能段的現(xiàn)象，相鄰兩個任務送入流水線的間隔拍數(shù)就不能為1、5、6、8拍，這些間隔拍數(shù)應當禁止使用。

可以用一個有N-1位的位向量來表示后繼新任務間隔各種不同拍數(shù)送入流水線時，是否會發(fā)生功能段使用的沖突，稱此位向量為沖突向量C(collisionvector)。沖突向量（cN-1…ci…c2c1）中第i位的狀態(tài)用以表示與當時相隔i拍給流水線送入后繼任務是否會發(fā)生功能段的使用沖突。如果不會發(fā)生沖突，令該位為“0”，表示允許送入；否則，讓該位為“1”，表示禁止送入。沖突向量取N-1位，是因為經(jīng)N拍后，任務己流出流水線，不會與后續(xù)的任務爭用流水線功能段了。

不難看出，輸入后續(xù)任務還需等待的拍數(shù)與前一個任務在流水線中已進行了幾拍有關。當?shù)谝粋€任務第1拍送入流水線時，根據(jù)禁止表F=(1，5，6，8)，可以形成此時的沖突向量C為(10110001)，稱此為剛流入流水線時的初始沖突向量。由于初始沖突向量的c2、c3、c4、c7為0，所以第二個任務可以距第一個任務2、3、4或7拍流入流水線。當?shù)诙€任務流入流水線后，應當產(chǎn)生新的沖突向量，以便決定第三個任務可以相隔多少拍流入流水線，才不會與已進入流水線的前面第一、第二個任務爭用功能段，…，依此順序類推。

顯然，隨著流水線中第一個任務每拍向前推進一段，原先禁止第二個任務流入流水線的各種間隔拍數(shù)均相應減去l拍。這意味著可以將初始沖突向量放在一個移位器中，每拍邏輯右移1位，讓左面移空的位補以“0”，以表示如果間隔8拍流入后續(xù)任務的話，前一個任務必定已流出流水線而不會發(fā)生功能部件使用沖突。因此，隨著任務在流水線中的推進，會不斷動態(tài)地形成當時的沖突向量。

如果選擇第二個任務在間隔2拍時流入流水線，對第一個任務而言，沖突向量右移2位成了（00101100）。這樣，要想使第三個任務流入流水線后，既不會與第一個任務發(fā)生功能段沖突，也不會與第二個任務發(fā)生功能段沖突，新的沖突向量就應當是第一個任務當前的沖突向量（00101100）與第二個任務的初始沖突向量（10110001）按位"或"，其結果為（10111101）。即第三個任務只能在第二個任務流入流水線后，隔2拍或7拍流入，才不會發(fā)生與先前流入流水線的那些任務爭用功能段。

按照這樣的思路，選擇各種可能的間隔拍數(shù)流入新的任務，從而又可以產(chǎn)生新的沖突向量，一直進行到不再產(chǎn)生不同的沖突向量為止。由此可以畫出用沖突向量表示的流水線狀態(tài)轉移圖。圖中兩個沖突向量之間用有向弧上的數(shù)字表示引入后續(xù)任務產(chǎn)生新的沖突向量所用的間隔拍數(shù)。本例的流水線狀態(tài)轉移圖如圖4.32所示。

從上面的分析中可以看出，從第二個任務開始，流入流水線的任務間隔拍數(shù)就有不同的選擇；而實際應用的時候，只能選擇一種間隔拍數(shù)進入流水線，那么應該選擇哪一個間隔拍數(shù)進入流水線才不會產(chǎn)生沖突，而且效率最高？只要按流水線狀態(tài)圖中由初始狀態(tài)出發(fā)，能構成一種間隔拍數(shù)呈周期性重復的方案來進行流水線的調度，都不會發(fā)生功能段使用沖突。然而，我們還希望能尋找一種最佳的調度方案，以便使流水線的吞吐率最高。顯然，只需要分別計算出每種調度方案的平均間隔拍數(shù)，然后，找出其中之最小者，就是流水線各后續(xù)任務流入流水線所用間隔的最佳調度。表4.1各種調度方案的平均間隔拍數(shù)調度方案(2,2,7)(2,7)(3,4)(4,3)(3,4,7)(3,7)(4,3,7)(4,7)(7)平均間隔拍數(shù)3.674.53.53.54.6754.675.57

由表4.1中可見，采用先隔3拍后隔4拍輪流給流水線送入任務的調度方案是最佳的，平均每隔3.5拍即可流入一個任務，吞吐率最高。盡管（4，3）調度方案平均間隔拍數(shù)也是3.5拍，但若實際流入任務數(shù)不是循環(huán)所需任務數(shù)的整數(shù)倍時，其實際吞吐率相對會低些，所以不作為最佳調度方案。如圖4.33所示，如果有4個任務流入流水線，采用（3，4）的調度方案流入時，所需要的拍數(shù)為9+3+4+3=19拍，而采用（4，3）調度方案時，所需要的拍數(shù)就變成9+4+3+4=20拍。

同樣是4個任務，采用不同調度方案，完成任務的拍數(shù)相差1拍。但若流入的任務數(shù)為5個的話，采用（3，4）調度方案或（4，3）調度方案，所需的拍數(shù)是一樣的，都是23拍。這是一種不等間隔的調度策略，比起相等間隔的調度策略在控制上要復雜一些。

為了簡化控制，也可以采用相等間隔調度，不過常常會因此而使吞吐率和效率下降。在本例只有一種相等間隔調度方案，即每隔7拍輸入一個任務，吞吐率比（3，4）調度方案降低了1/2。如果能有幾種不同的相等間隔調度方案，顯然應取其中間隔最小的，這樣會使吞吐率的下降最少。4.8相關處理和控制機構

流水線只有連續(xù)不斷地流動，即不出現(xiàn)“斷流”，才能獲得高效率。造成流水線“斷流”的原因很多，有編譯程序形成的目標程序不能發(fā)揮流水結構的作用，存儲系統(tǒng)供不上為連續(xù)流動所需的指令和操作數(shù)，轉移（無條件轉移、條件轉移）指令的使用，相關（指令相關、主存操作數(shù)相關和通用/變址寄存器組操作數(shù)相關）和中斷的出現(xiàn)等。

前面討論了重疊方式中出現(xiàn)的指令相關、主存操作數(shù)相關、通用寄存器組的操作數(shù)相關及基址值變址值相關。這些相關在流水機器中同樣也會出現(xiàn)。而且，由于流水是同時解釋更多條指令，所以相關狀況要比重疊機器的更復雜、更嚴重，如果處理不當，就會使流水效率顯著下降。指令相關、主存操作數(shù)相關和通用/變址寄存器組操作數(shù)相關由于只影響相關的二條或幾條指令，而至多影響流水線某些段的推后工作，并不會改動指令緩沖器中預取到的指令內(nèi)容，影響是局部的，所以被稱之為局部性相關。

同樣，流水機器在遇到轉移指令，尤其是條件轉移指令時，效率也會顯著下降。如果流水機器的轉移條件碼是由條件轉移指令本身或是由它的前一條指令形成時，則只有該指令流出流水線才能建立轉移條件，并依此決定下一條指令的地址。那么從條件轉移指令進入流水線，譯碼出它是條件轉移指令直至它流出的整個期間，流水線都不能繼續(xù)往前處理。若轉移成功，且轉向的目標指令又不在指令緩沖器內(nèi)時，還得要重新訪存取指令。

轉移指令和其后的指令之間存在關聯(lián)，使之不能同時解釋，其造成的對流水機器的吞吐率和效率下降的影響要比指令相關、主存操作數(shù)相關和通用/變址寄存器操作數(shù)相關嚴重得多，它可能會造成流水線中很多已被解釋的指令作廢，重新預取指令進入指令緩沖寄存器，它將影響整個程序的執(zhí)行順序，所以稱之為全局性相關。4.8.1局部性相關的處理局部性相關包括指令相關、訪存操作數(shù)相關和通用/變址寄存器組操作數(shù)相關等，都是由于在機器同時解釋的多條指令之間出現(xiàn)了對同一個單元（包括主存單元和通用寄存器）的“先寫后讀”要求。重疊機器在處理這些局部性相關時有兩種辦法：一種辦法是推后對相關單元的讀，直至寫入完成；另一種辦法是設置相關專用通路，使得不必先把運算結果寫入相關存儲單元，再由它讀出后才能使用，而是經(jīng)相關專用通路直接使用運算結果，這樣，就可省去“寫入”和“讀出”兩個訪問周期。

由于流水技術是重疊技術的延伸，因此上述兩種方法的思路也適用于流水機器處理局部性相關，但由于流水機器是同時解釋更多條指令，所以其相關專用通路的設計當然要比重疊的復雜。流水線有多個子過程，多條指令同時處在不同子過程上解釋。在控制機構上需要解決好如下問題：如何判定流入流水線的多條指令之間是否相關，如何控制推后對相關單元的讀，如何設置相關專用通路并控制相關專用通路的連通和斷開。對流水的流動順序的安排和控制可以有兩種方式：順序流動方式和異步流動方式。

順序流動方式是指流水線輸出端的任務（指令）流出順序和輸入端的流入順序一樣。如圖4.34所示，有一個8段的流水線，其中第2段為讀段，第7段為寫段。有一串指令h、i、j、k、l、m、……依次流入，當指令j的源操作數(shù)地址與指令h的目的操作數(shù)地址相同時，h和j就發(fā)生了先寫后讀的操作數(shù)相關。順序流動方式時，就要求j流到讀段時必須停下來等待，直到h到達寫段并完成寫入后，才能繼續(xù)向前流動，否則j將會因讀出的不是h寫入后的內(nèi)容而造成錯誤。

這是一種推后對相關單元讀的辦法，由于j停下來，j之后的指令也被迫停下來。順序流動方式的優(yōu)點是控制比較簡單。例如TI-ASC機就采用了這種方式。其缺點是一旦相關后，在空間和時間上都會有損失，使得流水線的吞吐率和功能部件的利用率降低。空間上會有功能段空閑出來，使部件利用率（效率）降低，時間上推后流出，會使流水線吞吐率降低。

異步流動方式是指流水線輸出端的任務（指令）流出順序和輸入端的流入順序可以不一樣。異步流動方式的優(yōu)點是流水線的吞吐率和功能部件的利用率都不會下降。如圖4.34的“可以不順序流動的”那行所示的指令在流水線內(nèi)的流動順序，如果讓j之后的那些指令，如k、l、m、n等，只要與j沒有相關，就越過j繼續(xù)向前流動。但采用異步流動方式帶來了新的問題，采用異步流動的控制復雜，而且會發(fā)生在順序流動中不會出現(xiàn)的其它相關。由于異步流動要改變指令的執(zhí)行順序，同時流水線的異步流動還會使相關情況復雜化，出現(xiàn)除“先寫后讀”相關外的“寫-寫”相關、“先讀后寫”相關等。

例如，若指令i、k都有寫操作，而且是寫入同一單元，那該單元的最后內(nèi)容本應是指令k的寫入結果。但是，由于指令i執(zhí)行時間很長或有“先寫后讀”相關，就會出現(xiàn)指令k先于指令i到達“寫段”，從而使得該單元的最后內(nèi)容錯為指令i的寫入結果。我們稱這種對同一單元，要求在先的指令先寫入，在后的指令后寫入的關聯(lián)為“寫-寫”相關。采用異步流動時，應在控制機構上保證當發(fā)生“寫-寫”相關后寫入的先后順序不變。另外，若指令i的讀操作和指令k的寫操作是對應于同一單元，指令i讀出的本應是該單元的原存內(nèi)容。但若指令k越過指令i向前流，且其寫操作在指令i的讀操作開始前完成，那指令i就會錯誤地讀出了指令k的寫入結果。我們稱這種對同一單元，要求在先的指令先讀出，在后的指令才寫入的關聯(lián)為“先讀后寫”相關。顯然，“寫-寫”相關和“先讀后寫”相關都只有在異步流動時才有可能發(fā)生，順序流動時是不可能發(fā)生的。所以，在設計采用異步流動方式工作時，控制機構應能處理好這3種關系。

在前面異步流動方式的例子中，“寫段”和“讀段”之間設置了相關專用通路。然而，流水機器是同時解釋多條指令，還經(jīng)常采用多個可并行工作的功能部件，不應當在各個功能部件之間為每種局部性相關都設置單獨的相關專用通路，否則會使硬件耗費大，控制復雜。一般的流水線機器都是采用分布式管理和控制以及設置公共數(shù)據(jù)總線來簡化各種相關的判別和實現(xiàn)相關專用通路的連接。4.8.2全局性相關的處理全局性相關指的是已進入流水線的轉移指令（尤其是條件轉移指令）和其后面的指令之間的相關。下面介紹一些常用的處理方法。

1.分支預測技術若指令i是條件轉移指令，它有兩個分支，如圖4.35所示。一個分支是i+1、i+2、i+3、…，按原來的順序繼續(xù)執(zhí)行下去，稱轉移不成功分支，另一個分支是轉向p，然后繼續(xù)執(zhí)行p+1、p+2、…，稱為轉移成功分支。

流水方式是同時解釋多條指令，因此，當指令i進入流水線，后面進i+1還是進p，只有等條件碼建立才能知道，而這一般要等該條件轉移指令快流出流水線時才行。如果在此期間讓i之后的指令等著，流水線就會“斷流”,性能將會急劇下降。為了在遇到條件轉移指令后，流水線仍能繼續(xù)向前流動，不使吞吐率和效率下降，絕大多數(shù)機器都采用所謂的“猜測法”，即分支預測技術。猜取第i+1條指令和第p條指令所在分支中的一個繼續(xù)向前流動。

分支預測技術可以分為靜態(tài)分支預測和動態(tài)分支預測，這里我們討論靜態(tài)分支預測技術，可以有兩種實現(xiàn)方法。一種是分析程序結構本身的特點或使用該程序以前運行時收集的模擬信息。不少條件轉移兩個分支的出現(xiàn)概率是能夠預估的，只要程序設計者或編譯程序把出現(xiàn)概率高的分支安排為猜選分支，就能顯著減少由于處理條件轉移所帶來的流水線吞吐率和效率的損失。另一種是按照分支的方向來預測分支是否轉移成功，當兩者概率差不多時，一般選取不成功轉移分支。

因為這些指令一般已預取進指令緩沖器，可以很快從指令緩沖器取出，進入流入線而不必等待。如果猜選成功轉移分支，指令p很可能不在指令緩沖器中，需花較長時間去訪存取得，使流水線實際上斷流。例如IBM360/91就采用轉移不成功分支。但這兩種方法猜錯的概率都不會低于30%。要提高預測的準確度，可以采用動態(tài)預測的方法，在硬件上建立分支預測緩沖站及分支目標緩沖站，根據(jù)執(zhí)行過程中轉移的歷史記錄來動態(tài)的預測轉移選擇，其預測準確度可以提高到90%左右。這種方法在POWERPC620的分支預測中得到了采用。

顯然，采用猜測法的控制機構應能保證在猜錯時可返回到分支點之前，并能把沿猜測分支流水時的指令的已有解釋全部作廢，并恢復分支點處的原有現(xiàn)場。恢復已經(jīng)開始解釋的那些指令的原有現(xiàn)場有如下三種方法：一是對猜測指令的解釋只完成譯碼和準備好操作數(shù)，在轉移條件碼出現(xiàn)前不執(zhí)行運算；二是對猜測指令的解釋可完成到運算完畢，但不送回運算結果；然而早期所用的這兩種辦法不方便，因為若猜對后還要讓這些指令繼續(xù)完成余留的操作。隨著器件技術的發(fā)展，已經(jīng)可以讓它們和正常情況一樣，不加區(qū)別地全部解釋完。三是對在流水線中的猜測指令不加區(qū)別地全部解釋完，但需把可能被破壞的原始狀態(tài)都用后援寄存器保存起來，一旦猜錯就取出后援寄存器的內(nèi)容來恢復分支點的現(xiàn)場。一般猜對的概率要高，猜對后既不用恢復，