《計算機系統(tǒng)結構》課件（單博煒）第3、4章 流水線技術與向量處理技術、存儲系統(tǒng)

第三章流水線技術與向量處理技術計算機系統(tǒng)設計的基本任務之一就是加快指令的解釋過程。除了采用高速部件，努力提高指令內部的并行性，從而加快單條指令的解釋過程之外，也可以采用提高指令間的并行性，從而并發(fā)地解釋兩條或兩條以上的指令，以達到提高計算機整體速度的目的。流水線技術是提高處理機指令執(zhí)行速度的主要途徑本章在并行性基本概念的基礎上，著重介紹重疊解釋、先行控制、流水線的工作原理與分類、流水線的性能計算方法和相關處理等基本原理，以及非線性流水線的調度方法；討論超標量處理機和把流水線技術與超標量技術相結合的超標量超流水線處理機，以及超長指令字等先進的指令級并行技術。最后闡述向量處理技術與向量處理機，絕大多數(shù)向量處理機都采用流水線結構。

3.1流水線的基本原理重疊解釋方式先行控制流水技術原理流水線分類流水線例子1．重疊方式原理一條指令的解釋過程可分成取指、分析和執(zhí)行三個子過程取指子過程是把要處理的指令從存儲器里取到處理機的指令寄存器；分析子過程則包括對指令的譯碼，形成操作數(shù)真地址并取操作數(shù)，形成下一條指令地址；執(zhí)行子過程是對操作數(shù)進行運算并將結果寫到目標單元中。指令的解釋方式可以有順序解釋方式和重疊解釋方式兩種順序執(zhí)行的優(yōu)點是控制簡單，但由于順序執(zhí)行的前一步操作未完成，后一步操作就不能開始，故其主要缺點是速度慢，機器各部件的利用率很低。重疊解釋方式，在解釋第k條指令的操作完成之前，就可開始解釋第k+l條指令。顯然，重疊執(zhí)行方式并不能縮短一條指令的執(zhí)行時間，但是縮短了多條指令的平均執(zhí)行時間2．重疊方式結構為了實現(xiàn)重疊方式，處理機必須從硬件組成上符合某些原則首先，為了實現(xiàn)“執(zhí)行k”與“分析k+1”重疊，必須在硬件上保證有獨立的取指令部件、指令分析部件和指令執(zhí)行部件。它們有各自的控制線路，實現(xiàn)各自的功能。為此，把處理機中原來一個集中的控制器，分解為存儲控制器（存控）、指令控制邏輯和運算控制器（運部控）三個部分其次，在一般的機器上，操作數(shù)和指令是混合存儲于同一主存內的，而且主存同時只能訪問一個存儲單元。為了解決好可能出現(xiàn)的訪存沖突讓操作數(shù)和指令分別存放于兩個獨立編址且可同時訪問的存儲器中。

仍維持指令和操作數(shù)混存，但采用多體交叉主存結構。增設指令緩沖寄存器。設置指令緩沖寄存器就可以在主存空閑時，預先把下一條或下幾條指令取來存放在指令緩沖寄存器中。預取指令的最大數(shù)量取決于指令緩沖寄存器的容量，它按先進先出的方式工作，保證指令順序不會混亂。這樣，“分析k”訪主存取操作數(shù)，“取指k+1”則從指令緩沖器中取第k+l條指令，互不干擾。而且，從指令緩沖器中取指所用時間很短，完全可以把這個微操作合并到“分析k+1”內，從而由原來的取指、分析、執(zhí)行重疊演變成只需“執(zhí)行k”與“分析k+1”的一次重疊，如圖3.5所示?！耙淮沃丿B”解釋方式的優(yōu)點為節(jié)省硬件，機器只需要一套指令分析部件和指令執(zhí)行部件，同時有助于簡化控制。先行控制一次重疊方式中保證“執(zhí)行k”與“分析k+1”重疊。如果所有指令“分析”與“執(zhí)行”的時間均相等，則一次重疊的流程是非常流暢的，指令的分析和執(zhí)行部件的功能均能充分發(fā)揮，機器的速度也能顯著提高。但實際中很難做到各種類型指令的“分析”與“執(zhí)行”時間始終相等。此時，一次重疊的流程中可能出現(xiàn)如圖3.6所示的情況。這時，指令分析部件和執(zhí)行部件就不能連續(xù)、流暢的工作，從而使機器的整體速度受到影響。先行控制原理減少這種情況下機器速度損失的基本思想是運用緩沖技術和預處理技術。緩沖技術是在兩個工作速度不同的功能部件之間設置緩沖器，用以平滑它們之間工作速度的差異。預處理技術則是把進入運算器的指令都處理成寄存器-寄存器型（R-R型）指令，它與緩沖技術相結合，為進入運算器的指令準備好所需要的全部操作數(shù)。具體就是在執(zhí)行部件執(zhí)行第k條指令的同時，指令控制部件能對其后繼的第k+l、k+2、…條指令進行預取和預處理，為執(zhí)行部件執(zhí)行新的指令做好必要而充分的前期準備。先行控制結構采用先行控制方式的處理機結構如圖3.8所示。在指令控制部件中，除了原有指令分析器外，又增加了先行指令棧、先行讀數(shù)棧、先行操作棧和后行寫數(shù)棧。(l)先行指令棧先行指令棧的作用是后繼指令預取，保證指令分析器在順序取指時能從先行指令棧內取到，它的作用相當于一次重疊結構中的指緩寄存器。先行指令棧是主存與指令分析器之間的一個緩沖部件，用于平滑主存和指令分析器之間的工作。當指令分析器分析某條指令用時較長或主存空閑時，可就從主存中多取幾條指令存入先行指令棧備取。(2)先行讀數(shù)棧指令分析器完成指令譯碼后，經(jīng)過尋址操作得到操作數(shù)有效地址。如果仍由指令分析器向存控發(fā)取數(shù)請求信號，則必然等待存控的響應，這就妨礙了后繼指令的連續(xù)處理。若將有效地址送先行讀數(shù)棧內的先行地址緩沖寄存器，則指令分析器可以繼續(xù)處理后繼指令。先行讀數(shù)棧由一組先行地址緩沖寄存器、先行操作數(shù)緩沖寄存器和相應的控制邏輯組成。每當?shù)刂肪彌_寄存器接到有效地址后，控制邏輯主動向存控發(fā)取數(shù)請求信號，讀出的數(shù)據(jù)送到先行數(shù)據(jù)緩沖寄存器內。先行讀數(shù)棧以先進先出的方式工作。運算器直接從其讀取數(shù)據(jù)操作，不向主存取數(shù)。因此，先行讀數(shù)棧是主存和運算器間的緩沖部件。先行讀數(shù)棧內的數(shù)據(jù)對運算器內正在執(zhí)行的指令而言是屬于后繼指令執(zhí)行所需的數(shù)據(jù)，故稱“先行”。設置先行讀數(shù)棧后，將運算器原來要訪存取操作數(shù)變?yōu)樵L問先行讀數(shù)棧中的寄存器，從而使指令的執(zhí)行速度大大加快。(3)先行操作棧指令分析器與運算器之間的緩沖部件是先行操作棧，由一組操作命令緩沖寄有器及相應的控制邏輯組成。由指令分析器對指令進行預處理后送入先行操作棧。各種運算型指令、移位指令、數(shù)據(jù)傳送指令等都要處理成寄存器-寄存器型（R-R型）指令。例如，對于變址型（R-X型）和存儲器型（R-S型）指令，指令分析器計算出主存有效地址后送入先行讀數(shù)棧，由先行讀數(shù)棧負責到主存讀取操作數(shù)，同時用先行讀數(shù)棧中存放這個操作數(shù)的寄存器編號替換原來指令中的主存地址碼，從而轉換成R-R型指令送入先行操作棧。為了與指令系統(tǒng)中原有的R-R型指令相區(qū)別，通常把送入先行操作棧中的指令稱為R-R*型指令。先行操作棧、是指令分析器和運算控制器之間的一個緩沖存儲器，一旦運算器空閑，運算控制器就從先行操作棧中取出下一條R-R*型指令，運算器需要的操作數(shù)則來自先行讀數(shù)?；蛲ㄓ眉拇嫫髦?。同樣，先行操作棧內命令對于運算器內正在執(zhí)行的命令而言是“先行”的。(4)后行寫數(shù)棧如果指令分析器遇到向主存寫數(shù)的指令，則把形成的主存有效地址送入后行寫數(shù)棧的后行地址緩沖寄存器中，并把預處理好的RR*型指令送入先行操作棧，這條R-R*型指令中的目標寄存器就是后行寫數(shù)棧的緩沖寄存器編號。當運算器執(zhí)行這條RR*型寫數(shù)指令時，只需將數(shù)據(jù)送人后行寫數(shù)緩沖寄存器即可，不與主存打交道，可繼續(xù)執(zhí)行后繼命令。后行寫數(shù)棧由一組后行地址緩沖寄存器、后行寫數(shù)緩沖寄存器，及相應控制邏輯組成。每當接到運算器送來的要寫入主存的數(shù)據(jù)，由控制邏輯白動地向主存發(fā)寫數(shù)請求信號，由后行寫數(shù)棧負責把后行寫數(shù)緩沖寄存器中的數(shù)據(jù)按后行地址緩沖寄存器中的主存地址送人主存。它是運算器和主存間的緩沖部件。由于后行寫數(shù)棧中寫回的數(shù)據(jù)，對于運算器中正在執(zhí)行的命令而言，是先前命令“滯后”寫回的數(shù)據(jù)，故叫后行寫數(shù)棧。它也是按先進先出方式工作的。1．流水處理方式流水線技術就是將一個完整的處理過程分解為若干個子過程，而每個子過程都可以有效地在其專用功能部件上與其他子過程對不同的對象同時執(zhí)行。處理機可以在不同級別上采用流水線方式工作。在一次重疊方式中，把一條指令解釋過程分解為“分析”與“執(zhí)行”兩個子過程，分別在獨立的分析部件和執(zhí)行部件上進行。描述流水線的工作過程，常采用時-空圖的方法。時-空圖的橫坐標表示時間，縱坐標表示流水線的各功能部件，每個功能部件通常稱為一個功能段。圖3.10所示的是由這四個過程段構成的流水線連續(xù)對六條指令的流水處理過程和相應的時-空圖?！傲魉痹诟拍钌吓c“重疊”沒有什么差別，可以看成是“重疊”的進一步引申：只是“一次重疊”把一條指令的解釋分解為兩個子過程，而“流水”則是分解成更多個子過程。前者同時解釋兩條指令，后者可同時解釋多條指令。應該注意的是，只有當流水線正常滿負荷流動時，才會每隔Δt流出一個結果。流水線從開始啟動工作到流出第一個結果，需要經(jīng)過一段流水線的建立時間，在這段時間里流水線并沒流出任何結果。在計算機實際的流水線中，各子部件經(jīng)過的時間會有差異。為解決各子部件處理速度的差異，一般在子部件之間需設置高速接口鎖存器。所有鎖存器都受同一時鐘信號控制，以實現(xiàn)各子部件信息流的同步推進。時鐘信號周期不得低于速度最慢子部件的經(jīng)過時間與鎖存器的存取時間之和，還要考慮時鐘信號到各鎖存器可能存在的時延差。因此，子過程的細分，會因鎖存器數(shù)增多而增大指令流過流水線的時間，這在一定程度上會抵消子過程細分而使流水線吞吐率得到提高的好處。2．流水線的特點(l)流水線可以劃分為若干個互有聯(lián)系的子過程（功能段）。每個功能段有專用功能部件實現(xiàn)對任務的某種如工。(2)實現(xiàn)子過程的功能段所需時間應盡可能相等，避免因時間不等而產(chǎn)生的處理瓶頸。這在設計流水線的控制線路及計算流水線的性能方面會帶來方便，簡化設計。但在實際機器中，各流水段所需的時間很難保證一致。(3)流水線工作狀態(tài)可分為建立、滿載和排空三個階段。從第一個任務進入流水線到流水線所有的部件都處于工作狀態(tài)的這一個時期，稱為流水線的建立階段。當所有部件都處于工作狀態(tài)時，稱為流水線的滿載階段。從最后一個任務流人流水線到結果流出，稱為流水線的排空階段。在理想情況下，當流水線充滿后，每隔Δt時間將會有一個結果流出流水線。(4)由于各種原因使指令流不能連續(xù)執(zhí)行時，會使流水過程中斷，而重新形成流水過程則需要通過時間，所以流水過程不應常“斷流”，否則流水線效率就不會很高。因此，流水技術適用于大量重復的程序過程，只有在輸入端連續(xù)地提供服務，流水線效率才能夠充分發(fā)揮。流水線的分類從不同的角度，可對流水線進行不同的分類。按流水線具有的功能分類流水線可以分為單功能流水線和多功能流水線。單功能流水線(unifunctionpipelining)是指只能完成一種固定功能的流水線。如Pentium有一條五段的定點和一條八段的浮點流水線。在計算機中要實現(xiàn)多個功能，必須采用多個單功能流水線。多功能流水線(multifuncitonpipelining)是指同一流水線的各個段之間可以有多種不同的連接方式，以實現(xiàn)多種不同的運算或功能。例如，美國Texas公司的ASC計算機運算器的流水線就是多功能的，它有八個可并行丁作的獨立功能段，如圖3.11(a)所示，能夠實現(xiàn)定點加/減法、定點乘法、浮點加／減法、浮點乘法、邏輯運算、移位操作、數(shù)據(jù)轉換、向量運算等。

TI-ASC機器要進行浮點加、減法時，其流水線功能段的連接如圖3.11(b)所示；而要進行定點乘法運算時，其流水線功能段的連接如圖3.11(c)所示。按流水線多種功能的連接分類按多功能流水線的各段能否允許同時用于多種不同功能連接流水，可把流水線分為靜態(tài)流水線和動態(tài)流水線。靜態(tài)流水線(staticpipelining)是指在同一時間內，多功能流水線中的各個功能段只能按一種功能的連接方式丁作。只有當按照這種連接流入的所有處理的對象都流出流水線之后，多功能流水線才能重新進行連接以實現(xiàn)其他功能。以TII-ASC機器的流水線為例，如果按照圖3.12所示的時-空圖工作，那么就是一種靜態(tài)流水線動態(tài)流水線(dynamicpipelining)是指在同一時間內，多功能流水線中的各個功能段可以實現(xiàn)多種連接，同時執(zhí)行多種功能。圖3.13比較圖3.12和圖3.13，得出靜態(tài)流水線與動態(tài)流水線的差別在于：對于相同的一串運算功能不同的指令而言，動態(tài)流水線的吞吐率和設備利用率比靜態(tài)流水線的高。由于在同一時間內，要通過不同的連接實現(xiàn)不同的運算，因而動態(tài)流水線的控制比靜態(tài)流水線要復雜，這就需增加相應硬件，故成本比靜態(tài)流水線的高。從軟、硬件功能分配的觀點上看，靜態(tài)流水線把功能負擔較多地加到軟件上，要求程序員編寫出（或是編譯程序生成）的程序應盡可能有更多相同運算的指令串，以提高其流水的效能，簡化硬件控制，而動態(tài)流水線則把功能負擔較多地加在硬件控制上，以提高流水的效能。按流水線的級別分類按流水處理的級別不同，可以把流水線分為部件級流水線、處理機級流水線和系統(tǒng)級流水線。部件級流水線，又稱運算操作流水線(arithmeticpipelining)．它是指處理機功能部件內部分段，采用流水操作來實現(xiàn)功能。例如，對于一些比較復雜的運算操作部件，如浮點加法器、浮點乘法器等，一般要采用多級流水線來實現(xiàn)。后行寫數(shù)棧和先行讀數(shù)棧都要實現(xiàn)訪存操作，也可以采用多級流水線來實現(xiàn)。處理機級流水線又稱為指令流水線(instructionpipelining)．它是把一條指令的解釋過程分解為多個子過程，每個子過程在一個獨立的功能部件中完成。組成先行控制器的各個部件實際上也構成了一條流水線，它把指令過程被分解為五個子過程，用五個專用功能段進行流水處理，如圖3.14所示。系統(tǒng)級流水線又稱為宏流水線(macropipelining)，如圖3.15所示。這種流水線由兩個或兩個以上的處理機通過存儲器串行連接起來，每個處理機對同一數(shù)據(jù)流的不同部分分別進行處理，前一個處理機的輸出結果存人存儲器中，作為后一個處理機的輸入，每個處理機完成整個任務中的一部分。按流水線的連接方式分類按照流水線的各功能段之間是否有反饋回路，可以把流水線分為線性流水線和非線性流水線。線性流水線(linepipelining)是指流水線各段串行連接，數(shù)據(jù)順序流經(jīng)流水線各段一次且僅流過一次。圖3.10所示的指令流水線就屬于線性流水線。非線性流水線(nonlinearpipelining)是指在流水線各段之間除有串行連接之外，還有某種反饋回路，使一個任務流經(jīng)流水線時，需多次經(jīng)過某個段或越過某些段。非線性流水線常用于遞歸調用或組成多功能流水線，如圖3.16所示。按數(shù)據(jù)表示分類以機器所具有的數(shù)據(jù)表示可以把流水線處理機分為標量流水處理機和向量流水處理機。標量流水處理機只能對標量數(shù)據(jù)進行處理，它沒有向量數(shù)據(jù)表示，只能用標量循環(huán)方式來對向量、數(shù)組進行處理。向量流水處理機則指的是機器具有向量數(shù)據(jù)表示，設置有向量指令和向量運算硬件，能對向量、數(shù)組中的各個元素流水的處理。向量流水處理機是向量數(shù)據(jù)表示和流水技術的結合。流水線性能分析衡量流水線性能的主要指標有吞吐率、加速比和效率。本節(jié)以線性流水線為例，分析流水線的主要性能指標。該分析方法也適用于非線性流水線。吞吐率吞吐率(TP，ThroughputRate)是指單位時間內流水線能夠處理的任務數(shù)（或指令數(shù)）或流水線能輸出的結果的數(shù)量，它是衡量流水線速度的主要性能指標。最大吞吐率Tpmax：是指在流水線正常滿負荷工作時，單位時間內機器所能處理的最多指令條數(shù)或機器能輸出的最多結果數(shù)。(2)實際吞吐率TP：流水線的實際吞吐率TP是指從啟動流水線處理機開始到流水線操作結束，單位時間內能流出的任務數(shù)或能流出的結果數(shù)。實際吞吐率TP總是小于最大吞吐率TPmax。各段執(zhí)行時間相等的吞吐率若一條m段線性流水線．各段執(zhí)行時間相等，均為Δt0，當有n個任務連續(xù)流人流水線時，流水線的工作過程可用如圖3.17所示的時-空圖表示。m段流水線的完成n個任務所需時間T為實際吞吐率為當n趨于無窮大時，TP達到最大各段執(zhí)行時間不等的吞吐率當流水線各段執(zhí)行時間不相等時，為了使各段之間的時間匹配，需要在各子過程之間插入鎖存器，這些鎖存器受同一個時鐘脈沖的控制，從而達到同步。若一條m段線性流水線各段執(zhí)行時間分別為Δt1，Δt2，Δt3，…，Δtm，則時鐘周期應為max{Δt1，Δt2，Δt3，…，Δtm}，流水線的最大吞吐率為TPmax=1/max{Δt1，Δt2，Δt3，…，Δtm}顯然，流水線的最大吞吐率取決于流水線中最慢子過程所需要的時間。我們把流水線中經(jīng)過時間最長的子過程稱為“瓶頸”子過程。該流水線完成行個任務的實際吞吐率為式中，tj為瓶頸段的經(jīng)過時間。[例3.1]一個四段線性流水線，各段執(zhí)行時間不等，如圖3.18(a)所示。求流水線最大吞吐率和連續(xù)輸入n個任務的實際吞吐率。解：圖中S1、S3、S4段的處理時間均為Δt，而S2段的處理時間需要3Δt，故S2段是該流水線的瓶頸段。根據(jù)流水線的最大吞吐率公式，其最大吞吐率為該流水線滿負荷工作時，每隔3Δt才能輸出一個結果。其時-空圖如圖3.18(b)所示。流水線連續(xù)輸入n個任務的實際吞吐率為瓶頸段的存在是引起流水線吞吐率下降的重要原因，必須找出并設法消除流水線中的瓶頸，才能提高流水線的吞吐率。消除瓶頸段，提高流水線吞吐率的方法(l)瓶頸子過程細分將圖3.18(a)歷示的瓶頸段S2進一步分離為三個子功能段S21、S22和S23，并且各子功能段的執(zhí)行時間均為Δt，把原來執(zhí)行時間不等的四段流水線改造為如圖3.19所示的執(zhí)行時間相等的六段流水線。瓶頸段分離后流水線的最大吞吐率為由于可間隔一個Δt輸入一個任務，流水線連續(xù)輸入n個任務的實際吞吐率為(2)瓶頸段部件重復設置由于結構等方面的原因，并不是所有子過程都可以進一步細分。那么，可以采用重復設置瓶頸段部件，讓多個瓶頸段并行工作來消除瓶頸段原執(zhí)行時間的“瓶頸”。如對圖3.18(a)所示流水線的瓶頸段S2，可再增設兩個相同的段，并分別以S2a、S2b、S2c命名，如圖3.20(a)所示。S1間隔Δt輪流給各瓶頸段提供任務，使它們仍可每隔Δt解釋完一條指令，其時-空圖如圖3.20(b)所示。流水線的最大吞吐率為TPmax=l/Δt，連續(xù)輸入n個任務的實際吞吐率為這種辦法需要解決好在各并行子過程之間的任務分配和同步控制，與瓶頸子過程細分方法相比，控制要復雜些，設備量要多些。加速比流水線的加速比Sp(speedupratio)是指流水方式與非流水線順序方式工作，完成同樣任務量時的工作速度提高的比值。1．各段執(zhí)行時間相等的加速比

流水線完成這n個任務所用的時間為Tm=(m+n-1)Δt順序執(zhí)行這n個任務，則所用的時間為T0

=n·m·Δt。加速比為當

時，流水線的加速比Sp接近于流水線的段數(shù)m2．各段執(zhí)行時間不等的加速比

如果流水線各功能段的執(zhí)行時間不相等，其中“瓶頸”段經(jīng)過的時間為Δtj，則一條m段線性流水線完成n個連續(xù)輸入的任務時，此流水線的實際加速比為效率流水線的效率η(efficiency)是指流水線的設備利用率，即流水線在整個運行時間里，流水線的設備實際使用時間所占的比率。由于流水線存在有建立時間和排空時間，在連續(xù)完成n個任務的時間里，各段并不是滿負荷T作的，所以流水線的效率一定小于1。1．各段執(zhí)行時間相等的效率從時-空圖上看，流水線的效率即為n個任務占用的時空區(qū)與m個功能段總的時空區(qū)面積之比。2．各段執(zhí)行時間不等的效率如果流水線各功能段的執(zhí)行時間不等，則各段的效率也不等，若其中“瓶頸”段的經(jīng)過時間為Δtj，則一條m段線性流水線連續(xù)輸入，n個任務時．整個流水線的效率為流水線的效率仍然是n個任務占用的時空區(qū)和m個段總的時空區(qū)面積之比。[例3.2]設有兩個向量A、B，各有四個元素，要在如圖3.21所示的靜態(tài)雙功能流水線上計算向量點積A·B。在該雙功能流水線中，S1→S2→S3→S5組成加法流水線，S1→S4→S5組成乘法流水線。設每個流水段所經(jīng)過的時間為Δt，而且流水線的輸出結果可以直接返回到輸入或暫存于相應的緩沖寄存器中，其延遲時間和功能切換時間忽略不計。求出流水線完成此運算工作期間的實陳吞吐率TP和效率η。解：首先選擇合理的算法，使完成向量點積A·B運算所用的時間最短，其算法如下。(1)功能部件連接構成乘法流水線，連續(xù)計算a1×b1、a2×b2

、a3×b3、a4×b4，得到四個乘積項。(2)等執(zhí)行乘法工作的流水線排空后，進行功能部件的切換連接，構成加法運算的流水線，并連續(xù)計算（a1×b1+a2×b2）、（a3×b3+a4×b4），得到兩個部分積。(3)產(chǎn)生了上述兩個結果后，再計算（a1×b1+a2×b2）+（a3×b3+a4×b4）最終得到向量點積。此過程總共流入多功能流水線的任務數(shù)為七個，完成任務所需的時間為15Δt，該流水線的實際吞吐率為順序完成這七個任務需要的時間為4×3Δt+3×4Δt=24Δt，故流水線的效率為[例3.3]上例圖3.21(a)中所示如果是動態(tài)雙功能流水線，其他條件不變。那么，在計算向量點積期間，流水線的吞吐率TP和效率η又是多少呢？解：動態(tài)流水線完成此運算的時-空圖如圖3.22所示由圖3.22中可以看出，進人流水線的任務數(shù)還是七個，但所需要的時間比靜態(tài)流水線少Δt，只需要14Δt就可完成。因此，此期間動態(tài)流水線的實際吞吐率為流水線的效率為從以上兩個例子可以看出，動態(tài)流水線與靜態(tài)流水線相比，由于不同功能可以重疊處理，所以具有較高的實際吞吐率和效率。3.3流水線中的相關及處理流水線只有在連續(xù)不斷的工作的狀態(tài)下才能發(fā)揮高效率，所以應盡量避免其斷流情況的出現(xiàn)。導致流水線斷流的原因可能有編譯形成的目標程序不能發(fā)揮流水結構的作用，或者存儲系統(tǒng)不能為連續(xù)流動提供所需的指令和操作數(shù)。除此之外，就是由于出現(xiàn)了相關和中斷。所謂“相關”，是指由于機器語言程序的鄰近指令之間出現(xiàn)了某種關聯(lián)后，為了避免出錯而使得它們不能同時被解釋的現(xiàn)象。流水線的相關分為局部性相關和全局性相關兩類。局部性相關(localcorrelation)對程序執(zhí)行過程的影響較小，它僅涉及到相關指令前后的一條或幾條指令的執(zhí)行；全局性相關(globalcorrelation)是指影響整個程序執(zhí)行方向的相關，主要是轉移類指令和中斷引起的相關。局部性相關及處理局部性相關包括指令相關、主存窄間數(shù)相關和通用寄存器組數(shù)相關等。如果第k+l條指令是經(jīng)第k條指令的執(zhí)行來形成的，由于在“執(zhí)行k”的末尾才形成第k+1條指令，第k、k+l條指令就不能同時解釋，此時稱這兩條指令之間發(fā)生了“指令相關”。如果第k+l條指令的源操作數(shù)地址i正好是第k條指令存放運算結果的地址，在笫k、k+1條指令的數(shù)據(jù)地址之間有了關聯(lián)，稱為發(fā)生了“數(shù)相關”。通用寄存器數(shù)相關則是相鄰指令之間出現(xiàn)要求對同一通用寄存器先寫后讀的關聯(lián)。若讀出的內容是操作數(shù)，則是通用寄存器數(shù)相關；若讀出的內容是變址值，則是通用寄存器變址值相關。順序流動的相關順序流動方式是指任務從流水線輸出端流出的順序同它們進入流水線輸入端的順序一樣。如圖3.23所示，有一個八段的流水線，其中第二段為讀段，第七段為寫段。有一串指令h、i、j、k、l、m…依次流入．如果指令j的源操作數(shù)地址與指令h的目的操作數(shù)地址相同，而當指令j到達讀段時，指令h還沒有到達寫段完成寫入操作，則指令j讀出的數(shù)據(jù)就是錯誤的，指令h和j就發(fā)生了先寫后讀的操作數(shù)相關。解決順序流動的“先寫后讀”(RAW，ReadAfterWrite)相關的方法是：要求指令j流到讀段時停止在流水線中流動，直到指令h到達寫段并完成寫入后，j與其后的指令才能繼續(xù)向前流動。這是一種推后對相關單元讀的處理方法，其優(yōu)點是控制實現(xiàn)比較簡單，缺點是推后期間流水線中出現(xiàn)空段，降低了流水線的吞吐率和效率。相關專用通路解決“先寫后讀”相關的另一種方法是建立相關專用通路，即在流水線的讀段與寫段之間增加一條專用的數(shù)據(jù)通路。推后的方法是以增加時間為代價，降低速度來解決相關問題；相關專用通路是以增加設備為代價，提高成本來解決相關問題。異步流動的相關異步流動方式是指任務從流水線輸出端流出的順序同它們進入流水線輸入端的順序可以不一樣。異步流動也稱為亂序(outoforder)流動或錯序流動。在順序流動方式中，當指令j與它前面的指令h發(fā)生相關時，指令j及其之后的指令串都停止流動，以期保持指令串流人與流出順序一致。但是，如果指令j以后的指令與進入流水線的全部指令之間都沒有相關問題，那么完全可以僅使相關的指令j暫停流動，而其后的指令依次越過指令j繼續(xù)向前流動，這樣就使得指令串流出的次序同它們流入的次序不一樣了。這就是異步流動，如圖3.23所示。在異步流動時除了出現(xiàn)“先寫后讀”相關外，還可能會發(fā)生在順序流動中不會出現(xiàn)的其他類型的相關。例如，指令i、k是都有寫操作，而且是寫入同一單元，那該單元的最后內容本應是指令k的寫入結果。但是，若采用異步流動方式，則可能出現(xiàn)指令k先于指令i到達寫段，從而使得該單元的最后內容錯為指令i的寫入結果。我們稱這種對同一單元要求在先的指令先寫入，在后的指令后寫入的關聯(lián)為“寫后寫”相關(WAW，WriteAfterWrite)。另外，如果指令i的讀操作和指令k的寫操作是對應于同一單元的，則指令i讀出的本應是該單元的原存內容。若采用異步流動方式，則可能出現(xiàn)指令是的寫操作先于指令i的讀操作被執(zhí)行，那么指令i讀取的數(shù)據(jù)就會錯誤的為指令j寫入的數(shù)據(jù)。我們稱這種對同一單元，要求在先的指令先讀出，在后的指令后寫入的關聯(lián)為“先讀后寫”相關(WAR，WriteAfterRead)。顯然，“寫后寫”相關和“先讀后寫”相關都只有在異步流動時才有可能發(fā)生，順序流動時是不可能發(fā)生的。異步流動方式的優(yōu)點是流水線的吞吐率和和效率都不會下降，缺點是異步流動的控制復雜，在設計采用異步流動方式T作時，控制機構必須解決好超越和新出現(xiàn)的兩種相關。全局性相關及處理全局性相關指的是已進入流水線的轉移指令（尤其是條件轉移指令）和其后面的指令之間的相關。若指令i是條件轉移指令，它有兩個分支，如圖3.24所示。一個分支是i+l、i+2、i+3、…，按原來的順序繼續(xù)執(zhí)行下去，稱轉移不成功分支；另一個分支是轉向h，然后繼續(xù)執(zhí)行h+1、h+2、…，稱為轉移成功分支。流水方式是同時解釋多條指令的，因此，當指令i進入流水線時，后面進i+l還是進h，只有等條件碼建立才能知道，而這一般要等該條件轉移指令快流出流水線時，如果在此期間讓i之后的指令等著，流水線就會“斷流”，性能將會急劇下降。對于一條有k個流水段的流水線，若流水線的時鐘周期為Δt，由于條件轉移指令的影響，在最壞情況下，每一次條件轉移將造成k-l個時鐘周期的“斷流”。另外，假設條件轉移指令在一般程序中所占的比例為p，轉移成功的概率為q，則對于一個由n條指令組成的程序，由于條件轉移需要額外增加的時鐘周期數(shù)是npq（k-l）Δt，因此，這n條指令總的執(zhí)行時間是有條件轉移影響的流水線的吞吐率為流水線的最大吞吐率為流水線吞吐率下降的百分比為[例3.4]據(jù)統(tǒng)計，在一些典型程序中，轉移指令所占的比例為20%，轉移成功的概率為q=60%。假設有一條八個流水段的指令流水線，那么，由于條件轉移指令的影響，流水線的最大吞吐率下降多少？解：已知p=0.20，q=0.60，k=8由于條件轉移指令在一般程序中所占的比例較大，所以處理好條件轉移引起的全局相關是很重要的。為了在遇到條件轉移指令時，流水線仍能繼續(xù)向前流動，不使吞吐率和效率下降，絕大多數(shù)機器都采用所謂的“猜測法”，即轉移預測技術——猜選按轉移成功和轉移不成功分支中的一個繼續(xù)向前流動。1．靜態(tài)轉移預測技術所謂靜態(tài)轉移頂測是指在處理機的硬件和軟件設計完成之后，轉移猜測方向就已經(jīng)被確定了——或者是轉移不成功方向，或者是轉移成功方向。靜態(tài)轉移預測技術可以有兩種實現(xiàn)方法。一種是分析程序結構本身的特點或使用該程序以前運行時收集的模擬信息。另一種是按照分支的方向來預測分支是否轉移成功。當兩者概率差不多時，一般選取轉移不成功分支，IBM360／91就采用轉移不成功分支。2．動態(tài)轉移預測技術動態(tài)轉移預測是根據(jù)近期轉移是否成功的歷史記錄來預測下一次轉移的方向。動態(tài)轉移預測的關鍵有兩點：一是如何記錄轉移歷史信息，二是如何根據(jù)記錄的轉移歷史信息預測轉移的方向。3．延遲轉移技術延遲轉移技術是依靠編譯器把轉移指令之前的一條或幾條沒有數(shù)據(jù)相關和控制相關的指令調整到轉移指令的后面。當轉移指令進入流水線之后，由這些指令填充流水線的各功能段似保證流水線不斷流，且又不會出現(xiàn)相關問題，直到轉移條件碼建立。延遲轉移技術一般只用于單流水線標量處理機中，而且流水線的段數(shù)不能太多，因為段數(shù)越多，需要調整到轉移指令之后的沒有數(shù)據(jù)相關和控制相關的指令條數(shù)也越多。據(jù)統(tǒng)計，編譯器只調整一條指令的成功概率在90%以上，調整兩條指令的成功概率只有40%左右。當沒有合適的指令可供調整時，編譯器只能在轉移指令之后插入空操作指令。SUN公司的SPARC處理機、HP公司的HPPA處理機和SG公司的一部分MIPS處理機都采用了延遲轉移技術。4．加快和提前形成條件碼采取措施盡快、盡早地獲得條件碼以便提前知道程序流向哪個分支，將有利于流水機器簡化對條件轉移的處理。由前可知，條件轉移指令造成流水線性能下降的主要原因是條件碼形成得太晚。很多時候，條件轉移指令的轉移條件碼是由上一條運算型指令產(chǎn)生的，而有些運算型指令在其執(zhí)行完畢之前，就可以形成反映運算結果的部分條件碼，如零標志、符號標志等。因此可以在取得操作數(shù)之后、開始運算之前提前形成條件碼，或者可采用延遲轉移技術．由編譯器調整指令序列，提前執(zhí)行產(chǎn)生條件碼的運算型指令，盡早產(chǎn)生條件碼。5．加快短循環(huán)程序的處理由于程席中廣泛采用循環(huán)結構，流水機器多數(shù)采取特殊措施以加快循環(huán)程序的處理，具體有以下兩種措施：由于循環(huán)程序中執(zhí)行循環(huán)分支的概率高，所以對循環(huán)程序出口端的條件轉移指令恒猜選循環(huán)分支，將短循環(huán)程序整體一次性放入指令緩沖器，并暫停預取指令，以減少執(zhí)行循環(huán)程序的訪主存重復取指次數(shù)。6．改進循環(huán)程序的處理方法循環(huán)操作是程序中廣泛使用的一種特殊條件轉移。循環(huán)操作是否結束，取決于循環(huán)操作次數(shù)是否已達到原來規(guī)定次數(shù)。所謂改進循環(huán)程序的處理-就是通過軟件方法用編譯器來支持條件轉移指令的執(zhí)行。從前面分析看出，當轉移不成功時，條件轉移指令對流水線的影響比較小?；谶@種原因，編譯器在對源程序進行編譯時，要盡量提高出現(xiàn)轉移不成功的概率。圖3.25所示為用編譯器支持條件轉移指令執(zhí)行的方法。如圖3.25(a)所示的源程序，如果在一般編譯器中進行編譯，編譯結果生成的目標程序，其轉移成功的概率很高，而轉移不成功只有一次。這種編譯結果對流水線的影響非常大。

如果在編譯器中進行適當處理，將源程序編譯成如圖3.20(b)所示的結果，此時轉移成功與不成功的概率正好反過來。如果要支持復合型條件轉移指令（條件碼形成與轉移目標地址計算功能用一條指令實現(xiàn)），編譯器也可以把源程序編譯成如圖3.25(c)所示的結果。這種編譯結果也只有一次轉移成功，因而對流水線的影響同圖(b)一樣。非線性流水線的調度在非線性流水線中，由于存在有反饋回路，當一個任務在流水線中流過時，在某個功能段可能要經(jīng)過多次，如果仍按每一個時鐘周期向流水線輸入一個新任務，則會發(fā)生與后續(xù)任務爭用這個功能段的情況。這種情況稱為功能部件沖突或流水線沖突，屬于一種資源相關，它的出現(xiàn)將導致流水線阻塞。非線性流水線的調度是一個優(yōu)化調度問題，可以通過構造相應的狀態(tài)有向圖來尋找最優(yōu)凋度策略。1．預約表預約表用于非線性流水線，是一張二維的表格，其橫坐標表示流水線工作的時鐘周期，縱坐標表示流水線的功能段，中間畫“√”表示該功能段在這一時鐘周期處于工作狀態(tài)，空白的地方表示該功能段在這個時鐘周期不工作。2．禁止表根據(jù)預約表可以得出一個任務使用流水線中同一段所需全部的間隔拍數(shù)。例如，1段相隔8拍，2段相隔1、5、6拍，那么兩個任務相隔8拍流人流水線必將會爭用1段，而相隔1、5或6拍流人流水線必將會爭用2段。將后續(xù)任務禁止流人流水線的時間間隔的集合構成禁止表F(forbiddenlist)。圖3.26所示預約表對應的禁止表為F={1，5，6，8}．即要想不出現(xiàn)爭用流水線功能段的現(xiàn)象，相鄰兩個任務送入流水線的間隔拍數(shù)就不能為1、5、6、8拍，這些間隔拍數(shù)應當禁止使用。3．沖突向量沖突向量C(collisionvector)是一個n-1位的位向量。沖突向量(Cn-1…Ci…C2C1)中第i位的狀態(tài)用以表示與當時相隔i拍給流水線送人后續(xù)任務是否會發(fā)生功能段的使用沖突。如果不會發(fā)生沖突，令該位為0；否則，讓該位為1。禁止表F={1，5，6，8），可以形成此時的沖突向量C0=（10110001），4．流水線狀態(tài)轉移圖新的沖突向量應當是已在流水線中的任務右移k位后的當前沖突向量與剛流入流水線的新任務的初始沖突向量按位“或”的結果。窮盡此過程，直進行到不再產(chǎn)生不同的沖突向量為止5．列出無沖突調度方案按流水線狀態(tài)圖中由初始狀態(tài)出發(fā)，凡是間隔拍數(shù)能呈現(xiàn)周期性重復的環(huán)路，都構成一個無沖突調度方案。并計算出每種調度方案的平均間隔拍數(shù)最佳調度：平均間隔拍數(shù)最少，如方案(3，4)的平均間隔拍數(shù)為3.5拍，吞吐率最高，是最佳調度方案。計算最佳調度方案的流水線吞吐率和加速比最佳調度方案的平均間隔拍數(shù)為3.5拍，故流水線的最大吞吐率為

TPmax=1/3.5Δt由此可得流水執(zhí)行所需時間為23Δt，順序執(zhí)行每個任務所需時間為9Δt，五個任務共需9×5=45Δt時間。實際吞吐率為加速比為效率為

流水機器的中斷處理流水機器中斷處理中的關鍵問題是解決好斷點現(xiàn)場的保存和恢復。中斷的出現(xiàn)一般不能預知，因此，當有一個中斷源的中斷請求被響應時所產(chǎn)生問題是：如何從尚在流水線中未執(zhí)行完的指令中選擇作為送給中斷服務子程序的斷點現(xiàn)場（準確的斷點現(xiàn)場是指若在執(zhí)行完第i條指令時響應中斷請求，送給中斷處理程序的就是對應于第i條指令的中斷現(xiàn)場，如第i條指令的程序狀態(tài)字等）。對此，有兩種處理方法。不精確斷點(impreciseinterrupt)法不精確斷點法對中斷的處理是：中斷請求發(fā)出時還沒進入流水線的后繼指令不允許再進入，而凡是已經(jīng)進入流水線的指令序列仍然流動直到執(zhí)行完成，然后才轉入中斷處理程序。實際上，提出中斷請求的指令可能并不是最后那條指令，所以稱其為不精確斷點法。這個方法只確定最后一條指令為斷點指令，縣保存這一條指令的現(xiàn)場，因此，保存現(xiàn)場和恢復現(xiàn)場的工作量較小。但是，采用這種方法有兩個問題：一是因為斷點不精確，程序執(zhí)行結果可能出錯；二是由于程序不能準確中斷在程序員在程序中設置的斷點處，使程序員無法看到自己設置的斷點處的現(xiàn)場，因而程序調試困難。精確斷點(preciseinterrupt)法

精確斷點法對中斷的處理是：對于在流水線中同時執(zhí)行的多條指令，由哪一條指令的程序性錯誤或故障發(fā)出的中斷申請，斷點就是這條指令的地址。為了實現(xiàn)精確斷點法，需要把斷點指令之前尚在流水線中已完全執(zhí)行和部分執(zhí)行的指令的執(zhí)行結果都作為現(xiàn)場保存起來．為此，要設置一定數(shù)量的后援寄存器，以便能精確恢復斷點現(xiàn)場。因此，采用精確斷點法需要較高的硬件代價，控制邏輯也比較復雜。目前的流水線處理機一般都采用精確斷點法。先進的流水線調度技術當流水線技術采用按序(inorder)發(fā)射指令的機制時，指令序列在流水線中是順序流動的，如果當前指令在流水線中被暫停，則后續(xù)指令就無法前進。因此，當相鄰的兩條指令存在相關時，會引起流水線的斷流。如果有多個功能部件，它們就會處于空閑狀態(tài)。這是流水線技術的一個限制。如果采用亂序(outoforder)按術，則遇到類似問題時，后繼指令若無相關，就可以繞過當前相關指令，繼續(xù)在流水線中流動，這樣可提高流水線的效率。我們將要討論的先進的流水線動態(tài)調度技術正是基于這種思想實現(xiàn)的。在遇到無法消除的數(shù)據(jù)相關時，靜態(tài)調度(staticscheduling)方法是通過調度相關指令以減少暫停的影響，而采用動態(tài)調度(dynamicscheduling)的處理機則會盡量避免相關給流水線帶來的暫停。動態(tài)調度相對于靜態(tài)調度的優(yōu)點在于：它可以處理一些編譯時未發(fā)現(xiàn)的相關，從而簡化了編譯器，另外它還允許在一種流水線上編譯的代碼可以在其他流水線上有效的運行，實現(xiàn)代碼的可移植性。當然，這些流水線性能的改善是以顯著增加硬件的復雜程度為代價的。集中式動態(tài)調度方法——記分牌這種調度方法源自CDC6600，主要用一個稱為狀態(tài)記錄控制器(或記分牌(scoreboard))的調度部件對流水線中的各個功能部件的工作狀態(tài)、進入流水線中的各條指令的工作狀態(tài)、它們所使用的源寄存器和目的寄存器情況等進行集中的統(tǒng)一記錄和調度。記分牌記錄并管理如下三張表：指令狀態(tài)表。它登記已取指到指令流水線的各條指令的狀態(tài)——是否已完成發(fā)射、是否已取完操作數(shù)、是否已完成執(zhí)行、是否已完成寫回。功能部件狀態(tài)表。每一個功能部件占有一個表項，登記是否“忙”、目的寄存器名、源寄存器名等是否就緒。目標寄存器表。每一個寄存器與預約使用它作為目標寄存器的功能部件(ID)相聯(lián)系，一個寄存器只能作為一個功能部件而不能同時作為兩個功能部件的目標寄存器。記分牌隨時監(jiān)督并不斷修改這些表，規(guī)定了一些定向邏輯。指令調度上若一條譯后的指令所需的功能部件可用，并且目標寄存器也不是其他功能部件已預約的目標寄存器，那么這條指令就可發(fā)射，否則將指令掛起，直到條件滿足再發(fā)射。這樣首先杜絕了“寫后寫”相關。至于取寄存器操作數(shù)并非該段必須完成的功能，能取則取，不能取可在執(zhí)行段完成取操作，這樣會使流水線停頓減少。在取寄存器操作數(shù)時要判測是否有“先寫后讀”相關。若先前發(fā)射的指令以某寄存器為目標寄存器，則只有該指令向目標寄存器寫入后（目標寄存器表中此項清除），此寄存器才作為其他指令的源寄存器就緒，從而消除“先寫后讀”相關。在寫回段要判測是否有“先讀后寫”相關。先前發(fā)射的指令若以本指令預定的目標

寄存器為源寄存器，而還沒有讀取的話，則本指令的寫回操作要推遲．直到“先讀后寫”相關清除再寫回。因指令是按序發(fā)射，并按發(fā)射順序登記在指令狀態(tài)表中，故指令發(fā)射的先后順序容易斷定。分布式動態(tài)調度方法——Tomasulo算法Tomasulo算法的核心是在記分牌調度方法中融入寄存器重命名(registerrenaming)技術，并以此來解決“寫后寫”相關和“先讀后寫”相關。寄存器重命名的規(guī)則是：如果遇到“寫后寫”或“先讀后寫”相關，則對引起相關的目的寄存器重新命名，即對于引起“寫后寫”或“先讀后寫”相關的指令，其運算結果不能直接寫到指令指定的引起相關的目的寄存器中，而是先寫到另外一個動態(tài)分配的備用寄存器中。等到與其相關的指令完成了訪問并將結果寫入該寄存器之后，就可以將這些臨時的備用寄存器中的內容恢復到指令中正式指定的寄存器中去。在Tomasulo算法中，寄存器重命名是通過保留站(reservationstation)來實現(xiàn)的。保留站緩存了即將要發(fā)射的指令所需要的操作數(shù)。Tomasulo算法的基本思想是盡可能早地取得并緩存一個操作數(shù)，避免指令直接從寄存器中讀取數(shù)據(jù)的情況。指令執(zhí)行時從保留站中取得操作數(shù)，并將執(zhí)行結果直接送到等待數(shù)據(jù)的其他保留站。對于連續(xù)對同一寄存器的寫操作，只有最后一個才真正更新寄存器中的內容。一條指令被發(fā)射時，存放其操作數(shù)的寄存器被重新命名為對應保留站的名字，這就是Tomasulo算法中的寄存器重命名技術。圖3.30所示是IBM360/91浮點執(zhí)行部件的結構框圖浮點數(shù)緩沖器(FLB)接收和緩沖來自主存的操作數(shù)。要寫入存儲器的信息被送到存數(shù)緩沖器(SDB)中緩沖。浮點執(zhí)行部件中的浮點加法器和浮點乘/除法器都是流水線，且能同時并行工作。浮點操作棧(FLOS，F(xiàn)loatingPointOperandStack)用于緩沖來自指令部件的浮點操作指令通過給每個浮點寄存器(FLRi)設置一個“忙位”來判斷相關。。當某個浮點寄存器被使用時就將其“忙位”置為l，使用完則將其“忙位”置為0。若FLOS送出如下兩條指令：I1ADD F2，F(xiàn)LB1 ；(F2)+(FLB1)→F2I2MUL F2，F(xiàn)LB2 ；(F2)×(FLB2)→F2機器的處理過程如下(l)當FLOS送出I1時，將控制由FLR取得(F2)，由FLB取得(FLBI)送往加法器保留站，假設送往Al，同時將F2的“忙位”置1，以指明該寄存器的內容已送往保留站等待運算，其內容不能再被其他指令作為源操作數(shù)讀出使用。(2)由于F2作為“目的”寄存器準備接收由加法器送來的運算結果，故需將站號A1送入F2的“站號”字段，以控制加法流水線將流出的保留站A1的運算結果經(jīng)CDB總線送回F2。當結果送回后，將F2的“忙位”和“站號”置成0，即釋放F2并允許其他指令使用。(3)如果在F2的“忙位”為1，而加法結果尚未流出加法流水線時，F(xiàn)LOS送出了I2，則在訪問F2取源1操作數(shù)時，會因其“忙位”為1而表明出現(xiàn)F2相關。此時不能直接將F2的內容送往乘法器保留站，而應將保存在F2“站號”字段中的站號A1送往M1源1的“站號”字段，并將F2的站號由A1改為M1以指明將從M1接收運算結果。(4)當加法器對A1站的（源1）、（源2）進行相加，并將結果由CDB送出時，就會將直接送入“站號”為A1的M1保留站（源1）中，這相當于將此間的相關專用通路接通，之后要清除M1保留站（源1）的“站號”(5)此時乘法器的M1保留站的（源1）、（源2）均已就緒，可將其送人乘法器執(zhí)行乘運算，這實際相當于推后相乘的執(zhí)行。而乘積則經(jīng)CDB總線送往“站號”字段為M1的F2寄存器，同時將F2的“忙位”和“站號”置0，釋放F2。：動態(tài)轉移目標緩沖技術這是一種為減少轉移指令引起的流水線停頓，而盡早生成轉移目標地址的技術。它將以往成功轉移的轉移指令地址和其轉移目標地址放到一個類似Cache的緩沖區(qū)中保存起來，緩沖區(qū)以轉移指令的地址作為標志。在每條指令的取指階段，將指令的地址與緩沖區(qū)中保存的所有標志做相聯(lián)比較，若有相符的標志，則認為本指令是轉移指令，且轉移成功，它的下一條指令地址就是緩沖區(qū)中與相待標志對應的轉移目標地址。這個緩沖區(qū)稱為轉移目標緩沖區(qū)（BTB，BranchTargetBuffer或BranchTargetCache），轉移目標緩沖的工作過程為：(l)當前指令的地址與BTB中的標志作相聯(lián)比較，若有相符者，則認為此指令為轉移成功指令，且下一條指令的地址在BTB的轉移目標地址域中。因此在本指令的指令譯碼(ID)階段，開始從預測的指令地址處取下一條指令，如果預測正確將不會有任何延遲。(2)若在BTB中有與當前指令地址相符者，但當前指令轉移不成功，則預測錯誤，此時將該項從BTB中刪去。這時會耗費一個時鐘周期來取錯誤的指令，并在一個時鐘周期后重新取正確指令。(3)如果當前指令地址在BTB中沒有相符者而指令發(fā)生了轉移，則轉移目標地址將在指令譯碼(ID)階段末知道，此時應將該轉移指令的地址和轉移目標地址加入BTB中。(4)若當前指令地址在BTB中無相符者且指令不發(fā)生轉移，則按普通指令執(zhí)行。指令級并行技術前面介紹的技術主要是通過減少數(shù)據(jù)相關和控制相關，達到每條指令執(zhí)行的平均周期數(shù)CPI為1的理想情況。為獲得更高的性能，我們希望能夠使CPI進一步減小為CPI≤1。在20世紀80年代興起的RISC結構，其設計思想就是要讓單處理機在每個時鐘周期里可解釋多條指令。由此出現(xiàn)了采用提高指令級并行新技術的超級處理機，具代表性的有超標量(superscalar)處理機、超長指令字(VLIW，VeryLongInstructionWord)處理機和超流水線(superpipelining)處理機。超標量處理機標量流水處理機的時-空圖一般的流水機器在一個時鐘周期內只能發(fā)射一條指令，每個時鐘周期只能產(chǎn)生一個結果，稱為標量流水線處理機。超標量處理機在一個時鐘周期內能夠同時發(fā)射多條指令。超標量處理機是利用硬件資源重復設置來實現(xiàn)空間上的并行操作，從而縮短處理時間以減小CPI。采用多指令流水線的超標量處理機在每個Δt同時流出m條指令（稱并行度為m）。圖3.34所示為并行度m=3的超標量處理機的流水時一空圖，每三條指令為一組，執(zhí)行完12條指令只需7Δt。典型的超標量流水線處理機有IBMRS6000、PowerPC620、DEC21064等，還有如Intel公司的i960CA、Pentium系列處理機，Motorola公司的MC88110等。1986年的Inteli960CA時鐘頻率為25MHz，并行度m=3，有七個功能部件可以并發(fā)使用。1990年的IBMRS6000使用1μm的CMOS工藝，時鐘頻率為30MHz。處理機中有轉移處理、定點、浮點三種功能部件，它們可并行工作。轉移處理部件每Δt可執(zhí)行多達五條指令，并行度m=4，性能可達34MIPS和11MFLOPS。1992年的DEC21064使用0.75μm的CMOS，時鐘頻率為150MHz，并行度m=2，具有10段流水線，最高性能可達300MIPS和150MFLOPS。1995年的PowerPC620是PowerPC結構的第一個64位實現(xiàn)方案，它包括六個獨立執(zhí)行單元，允許處理器同時派遣四條指令到三個整數(shù)單元和一個浮點單元，時鐘頻率為150MHz。1998年的IntelPentiumⅡ處理器，具有11段流水線，能并行執(zhí)行三條Pentium指令，最高時鐘頻率為450MHz。超長指令字處理機超長指令字VLIW結構是水平微碼和超標量處理兩者相結合的產(chǎn)物。超長指令字處理機采用指令靜態(tài)調度策略，通過優(yōu)化編譯器找出指令間潛在的并行性，將多條指令中若干可并行執(zhí)行的操作安排在一個超長指令字中的各指令操作字段上，形成一條可達數(shù)百位的指令，超長指令字由此得名。圖3.35所示為典型的VLIW處理機結構和指令格式。VLIW結構由編譯器在編譯過程中重新安排指令順序，這使得超長指令字譯碼器邏輯簡單。運行時不再需要用軟件或硬件進行操作相關判定、指令調度及操作的亂序處理等控制邏輯，從而使碗件結構的復雜性大為降低，卻能獲得很強的性能。VLIW是一種單指令多操作碼多數(shù)據(jù)(SIMOMD)的系統(tǒng)結構。指令同時可流出的最大數(shù)目（并行度m）越大，超長指令字的性能優(yōu)勢就越顯著。圖3.36所示為VLIW執(zhí)行時一空圖，每拍啟動一條長指令，執(zhí)行三個操作，相當于三條指令，并行度m=3，經(jīng)過七個Δt后可得到4×3個結果。VLIW技術的關鍵是它的編譯技術。VLIW指令中并行操作的同步在編譯時完成，這

使它比超標量處理器具有更高的處理效率。而VLIW體系結構中對指令并行性和數(shù)據(jù)移

動在編譯時說明，則大大簡化了運行時的資源調度。但是，VLIW的指令格式是特殊的，因

而其代碼無法與一般的計算機兼容。VLIW的指令字很長而操作段格式固定，經(jīng)常使指令

字中的許多字段沒有操作，浪費了存儲空間。VLIW機的編譯程序與系統(tǒng)結構關系非常密

切，二者必須同時設計，故缺乏對傳統(tǒng)硬件和軟件的兼容。現(xiàn)代VLIW的研究在進一步深入開發(fā)更高效實用的編譯技術的同時，也試圖在體系結構方面有所改進，以彌補傳統(tǒng)VLIW存在的不足。超流水線處理機超流水線是指在每個節(jié)拍只發(fā)射一條指令，但每個機器周期內可并發(fā)發(fā)射多條指令并產(chǎn)生多個結果的流水線。與超標量流水線不同的是，超流水線每一節(jié)拍仍只流出一個結果，但一臺并行度為m的超流水線處理機的節(jié)拍Δt′只是機器時鐘周期Δt的l/m。因此在一個時鐘周期內，流水線仍可流出多個結果。圖3.37所示為并行度m=3的超流水線處理機工作時-空圖。與超標量流水線處理機利用資源重復開發(fā)空間并行性不同，超流水線處理機則著重開，發(fā)時間并行性，在流水部件上采用較短的時鐘周期，通過增加流水級數(shù)來提高速度。如果一臺有k段流水線的m并行度超流水線處理機，執(zhí)行完N條指令的時間為如果m=3，則所需時間為加速比為當N趨于無窮大時，加速比Sp趨近于m。典型的超流水線機器有1991年2月MIPS公司的64位RISC計算機MIPSR4000超標量超流水線處理機超標量超流水線處理機是超標量流水與超流水技術的結合。若一條指令包含取指令、譯碼、執(zhí)行、存結果四個子過程，各子過程經(jīng)過時間均為Δt′，且機器時鐘周期Δt=3Δt′，則指令在并行度m=9的超標量超流水線處理機中的操作情況如圖3.38所示。在一個時鐘周期內機器指令發(fā)射三次，每次發(fā)射三條指令，每個功能段延遲時間都是Δt′，則在流水線滿負荷工作時，完成12個任務只需要5Δt。美國DEC公司1992年推出的Alpha21064處理器就采用了超標量超流水結構。設流水線的級數(shù)為k，流水線中每級的執(zhí)行時間均為τ，采用超流水線時處理器的時鐘頻率為主機時鐘頻率的n倍，采用超標量時處理器的發(fā)射度為m。對于不同類型的流水線在執(zhí)行N條指令時的執(zhí)行時間有所不同。單發(fā)射標量流水線m發(fā)射超標量流水線單發(fā)射n倍超流水線

m發(fā)射n倍超標量超流水線一般情況下，當時鐘頻率和流水線級數(shù)相同時，有m發(fā)射的超標量處理機速度最多為單發(fā)射處理機速度的m倍。具有n倍時鐘頻率的超流水線處理機，它的速度最多可為單頻標量流水線的n倍。具有n倍時鐘頻率和m發(fā)射的超標量起流水線處理機，它的組合加速比可為單頻標量流水線的m·n倍。[例3.5]設有12個任務需要進入流水線，已知流水線的功能段均為四個，每個功能段的處理時間都是Δt。現(xiàn)計算在下列情況中完成12個任務分別需要多少時間？(1)單發(fā)射標量流水線。(2)超標量流水線，每個時鐘周期可以同時發(fā)射三條指令。(3)超流水線，每個時鐘周期可以分時發(fā)射三次，每次發(fā)射一條指令。(4)超標量超流水線，每個時鐘周期可以分時發(fā)射三次，每次發(fā)射三條指令。[例3.6]在下列不同結構的處理機上運行8×8的矩陣乘法C=A×B，計算所需要的最短時間（只計算乘法指令和加法指令的執(zhí)行時間，不計算取操作數(shù)、數(shù)據(jù)傳送和程序控制等指令的執(zhí)行時間）。加法部件和乘法部件的延遲時間都是三個時鐘周期，另外，加法指令和乘法指令還要經(jīng)過一個“取指令”和“指令譯碼”的時鐘周期，每個時鐘周期為20ns，C的初始值為0。各操作部件的輸出端有直接數(shù)據(jù)通路連接到有關操作部件的輸入端，在操作部件的輸出端設置有足夠容量的緩沖寄存器。(l)處理機中只有一個通用操作部件，采用順序方式執(zhí)行指令。(2)單流水線標量處理機。有一條兩個功能的靜態(tài)流水線，流水線每個功能段的延遲時間均為一個時鐘周期，加法操怍和乘法操作各經(jīng)過三個功能段。(3)多操作部件處理機。處理機內有獨立的乘法部件和加法部件，兩個操作部件可以并行工作。只有一個指令流水線，操作部件不采用流水線結構。(4)單流水線標量處理機。處理機內有兩條獨立的操作流水線，流水線每個功能段的延遲時間均為一個時鐘周期。(5)超標量處理機。每個時鐘周期同時發(fā)射一條乘法指令和一條加法指令，處理機內有兩條獨立的操作流水線，流水線的每個功能段的延遲時間均為一個時鐘周期。(6)超流水線處理機。把一個時鐘周期分為兩個流水節(jié)拍，加法部件和乘法部件的延遲時間都為六個流水節(jié)拍，“取指令”和“指令譯碼”仍分別為一個流水節(jié)拍，每個時鐘周期能夠分時發(fā)射兩條指令，即每個流水節(jié)拍能夠發(fā)射一條指令。(7)超標量超流水線處理機。把一個時鐘周期分為兩個流水節(jié)拍，加法部件和乘法部件延遲時間都為六個流水節(jié)拍，“取指令”和“指令譯碼”仍分別為一個流水節(jié)拍，每個流水節(jié)拍能夠同時發(fā)射一條乘法指令和一條加法指令。解：要完成兩個8×8矩陣相乘，共要進行8×8×8=512次乘法，8×8×7=448次加法(1)順序執(zhí)行時，每個乘法和加法指令都需要五個時鐘周期。計算所需要的時間為T=(512+448)×5×20ns=96000ns(2)單流水線標量處理機，操作部件為靜態(tài)雙功能流水線，結構如圖3.39所示。由于有足夠的緩沖寄存器，所以可以首先把所有的乘法計算完，流水線排空后再輸入加法任務，并通過調度使加法流水線不出現(xiàn)停頓。計算所需要的最短時間為T=[(5+512-1)+(3+448-1)])×20ns=19320ns(3)單流水線多操作部件處理機，結構如圖3.40所示。因為加法總共執(zhí)行448次，而乘法共執(zhí)行512次，所以加法操作可以在某些時候與乘法操作并行執(zhí)行。同時考慮乘法流水線的乘積與加法流水線的加數(shù)之間可能出現(xiàn)的“先寫后讀”數(shù)據(jù)相關，最后一次加法運算結束與最后一次乘法運算結束的時間差應為一次完整的加法流水操作過程，這里為三個時鐘周期。計算所需要的最短時間為T=[5+(512-1)×3+3]×20ns=30820ns(4)單流水線標量處理機有兩條獨立的操作流水線，結構如圖3.41所示。分析方法同(2)，但流水線不需排空。計算所需要的最短時間為T=[5+(512-1)+448]×20ns=19280ns(5)超標量處理機，能同時發(fā)射一條加法和一條乘法指令，有兩條獨立的操作流水線，結構如圖3.42所示。分析方法同(3)，區(qū)別在于乘與加操作均是流水化的，而且在不同的流水線上并行執(zhí)行。計算所需要的最短時間為T=[5+(512-1)+3]×20ns=10380ns(6)超流水線處理機每個時鐘周期分時發(fā)射兩條指令，加法部件和乘法部件都為六個流水級，“取指令”和“指令譯碼”仍分別為一個流水級，結構如圖3.43所示。分析方法同(4)，不同之處在于時鐘周期變成了10ns，且流水線已細化。計算所需要的最短時間為T=[8+(512-1)+448]×10ns=9670ns(7)超標量超流水線處理機一個時鐘周期分為兩個流水節(jié)拍，加法部件和乘法部件均為六個流水級，“取指令”和“指令譯碼”仍分別為一個流水級，每個流水節(jié)拍能同時發(fā)射一條加法和一條乘法指令，結構如圖3.44所示。綜合(5)和(6)的分析可知，計算所需要的最短時間為T=[8+(512-1)+6]×10ns=5250ns3.6向量處理技術從前面的分析中可知，如果輸入流水線的指令既無局部性相關，也無全局性相關，則流水線可能裝滿。此時，可獲得高的吞吐率和效率。在科學計算中，往往有大量不相關的數(shù)據(jù)進行同一種運算，這正適合于流水線特點，因此就出現(xiàn)了具有向量數(shù)據(jù)表示和相應向量指令的向量流水線處理機。由于這種機器能較好地發(fā)揮流水線技術特性，因此，可以達到較高的速度。一般稱向量流水處理機為向量機(vectorprocessor)。向量處理方法這里，用一個簡單的例子說明向量的處理方式。例如，以下是FORTRAN語言寫的一個循環(huán)程序：DO10i=1，N10d[i]=a[i]*(b[i]+c[i])對此，可以有下面幾種方法。1．水平（橫向）處理法如果用逐個求d[i]的方式，則：d[1]=a[1]*(b[1]+c[1])d[2]=a[2]*(b[2]+c[2])…d[i]=a[i]*(b[i]+c[i])…d[N]=a[N]*(b[N]+c[N])這種方法的每次循環(huán)中至少要用兩條指令：k[i]=b[i]+c[i]d[i]=k[i]*a[i]顯然在流水處理中，不僅有操作數(shù)相關（“先讀后寫”相關），而且每次循環(huán)中又有功能的切換(+、*、…)，這就使流水線的效率和吞吐率降低。實際上，可以認為A、B、C、D是長度為N的向量。A=（a1，a2，…，aN）B=（b1，b2，…，bN）C=（c1，c2，…，cN）D=（d1，d2，…，dN）因此，上述DO循環(huán)可以寫成如下向量運算的形式：D=A*(B+C)基于該向量表示形式，還可以有下面兩種處理方式。2．垂直（縱向）處理法垂直處理方法是對整個向量按相同的運算處理完之后，再去執(zhí)行別的運算。對于上式，則有K=B+CD=K*A可以看出，這種處理方式僅用了兩條向量指令，且處理過程中沒有出現(xiàn)轉移，每條向量指令內無相關，兩條向量指令問只有一次數(shù)據(jù)相關，如果仍用靜態(tài)多功能流水線，也只需一次功能切換。由于向量長度N是不受限制的，無論N有多大，相同運算都用一條向量指令完成。因此，向量運算指令的源向量和目的向量都存放在存儲器內，流水線運算部件的輸入、輸出端通過緩沖器與主存連接，從而構成存儲器一存儲器型的運算流水線，其結構如圖3.45所示。3．分組（縱橫）處理法把長度為N的向量分成若干組，每組長度為行，組內按縱向方式處理，依次處理各組。若 N=s·n+r其中r為余數(shù)，也作為一組處理，則共有s+1組，其運算過程為：第一組

K1~n=B1~n+C1~n

D1~n=K1~n*A1~n第二組

Kn+1~2n=Bn+1~2n+Cn+1~2n

Dn+1~2n=Kn+1~2n*An+1~2n

……第s+1組

Ksn+1~N=Bsn+1~N+Csn+1~N

Dsn+1~N=Ksn+1~N*Asn+1~N每組內各用兩條向量指令，僅有一次向量指令的數(shù)據(jù)相關。如果也用靜態(tài)多功能流水線，則各組需兩次功能切換，所以適合于對向量進行流水處理。這種處理方式對向量總長度N沒有限制，但組內長度不能超過n。因此，可設置長度為n的向量寄存器，使每組向量運算的源向量和目的向量均在向量寄存器中，運算流水線的輸入、輸出端與向量寄存器相連，構成所謂寄存器一寄存器型運算流水線，如圖3.46所示。向量處理機向量處理機的結構因具體機器而不同，20世紀70年代中期問世的CRAY-1向量流水處理機是向量處理機的典型代表。下面僅以CRAY-I機中的向量流水處理部分為例，介紹面向寄存器一寄存器型向量流水處理機的一些結構特點。CRAY-I向量處理機不能獨立工作，它需要一臺前置機對整個系統(tǒng)進行管理，在此只介紹CRAY-I向量處理機本身。Cray-1CRAY-1是由中央處理機、診斷維護控制處理機、大容量磁盤存儲子系統(tǒng)、前置處理機組成的功能分布異構型多處理機系統(tǒng)。CRAY-1向量處理機不能獨立T作，它需要一臺前置機對整個系統(tǒng)進行管理。圖3.47是CRAY-1向量處理機中有關向量流水處理部分的簡圖。每個Vi塊可存元素個數(shù)達64的一個向量。因此，向量寄存器中同時可存放八個向量。對于長度超過64個元素的長向量可以由軟件加以分段處理，每段64個元素。為了能充分發(fā)揮向量寄存器組和可并行工作的六個功能部件的作用以及加快向量處理，CRAY-I設計成每個Vi塊都有單獨總線可連到六個功能部件，而每個功能部件也各自都有把運算結果送回向量寄存器組的輸出總線。這樣，只要不出現(xiàn)Vi沖突和功能部件沖突，各個Vi之間和各個功能部件之間都能并行工作，從而大大加快了向量指令的處理，所謂Vi沖突是指并行工作的各向量指令的源向量或結果向量的Vi有相同的。除了相關情況之外，就是出現(xiàn)源向量沖突，例如：V4=V1+V2V5=V1^V3所謂功能部件沖突指的是同一個功能部件被一條以上的并行工作向量指令所使用。例如：

Vl=V2*V3V5=V1*V6CRAY-1的向量指令CRAY-1有標量類和向量類指令共128條，其中四種向量指令如圖3.48所示。CRAY-1提高運算速度的措施(l)鏈接技術。CRAY-I向量處理的