標量流水線技術第1頁，共87頁，2023年，2月20日，星期一第4章標量流水線技術4.1概述4.2標量流水線工作原理4.3指令級流水線第2頁，共87頁，2023年，2月20日，星期一4.1概述4.1.1控制流及其改變4.1.2程序執行過程中的重疊操作與先行控制第3頁，共87頁，2023年，2月20日，星期一4.1.1控制流及其改變

所謂控制流是指被執行的指令序列的處理順序，其地址由程序計數器PC給出，一條接著一條地執行。在一般情況下，PC的值是時間的單調函數，如圖4.1（a）所示。但是當遇上轉移類指令時，控制流將發生間斷，轉移到目標地址后又順序執行，PC中的值如圖4.1（b）所示。通常，改變程序順序執行的因素有多種，常見的有以下4種。圖4.1程序計數器PC與時間t的關系

第4頁，共87頁，2023年，2月20日，星期一（1）轉移指令轉移指令可分為無條件轉移和條件轉移兩種類型，且有多條，都是把轉移目標地址送入程序計數器PC中，然后又順序執行，如圖4.1（b）所示。（2）過程調用與返回即執行被調用的過程或子程序，其入口地址送入PC中；返回時，返回地址送入PC，另外還有嵌套和遞歸。

（3）協同程序協同程序與過程調用程序有所不同，它是被調用過程未必從頭開始執行，而是從上一次返回的位置開始，如圖4.2所示。（4）中斷與自陷中斷是由外部事件引起，自陷是由CPU的內部原因引起，CPU執行中斷服務程序，執行完后返回原來被中斷的程序。以上幾種情況都改變PC中的值，使控制流發生改變。圖4.2協同程序改變控制流第5頁，共87頁，2023年，2月20日，星期一4.1.2程序執行過程中的重疊操作與先行控制

1.程序執行過程中的重疊操作在計算機運行的過程中，指令的解釋方式可分為三種，即順序、重疊和流水，依據不同的解釋方式，可以產生不同的工作方式和過程。下面僅介紹順序解釋方式和重疊解釋方式，流水線方式將在第4.2節介紹。（1）順序解釋方式順序解釋是最簡單的一種方式，它是一條指令執行完后再去解釋下一條指令。早期的計算機多采用這種方式，指令執行過程分為取指令、分析（譯碼）和執行三個階段，順序進行，其示意如圖4.3所示。圖4.3順序執行方式

第6頁，共87頁，2023年，2月20日，星期一

若取指令、分析和執行所用的時間（周期）相等，設為t，則順序解釋執行n條指令所需要的時間T=3×n×t。如果各部分時間表示為t取指、t分析和t執行，則順序執行n條指令所用的時間為：

（2）重疊解釋方式是在兩條相鄰指令的解釋過程中，存在某些時段可以重疊進行，其示意如圖4.4所示。圖4.4重疊執行方法

T=∑(t取i+t分i+t執i)ni=1（4.1）第7頁，共87頁，2023年，2月20日，星期一圖4.5兩階段一次重疊工作方式圖(a)是一次重疊方式，執行n條指令所用的時間為：T=(2n+1)t；圖(b)是二次重疊方式，執行n條指令所用的時間為：

T=3t+(n-1)t=(n+2)t。

為實現重疊解釋方式，需要硬件支持，比如設置指令緩沖寄存器或稱指令隊列。又如程序與數據分別存儲，以便分別迅速讀取操作數。

若指令的解釋過程可分為兩個段，上述重疊解釋過程可如圖4.5所示。如果“分析”和“執行”的時間相同，那么解釋執行n條指令的時間為：

T=(n+1)t。第8頁，共87頁，2023年，2月20日，星期一2.先行控制

在上述重疊解釋方式中假設“分析”和“執行”的時間相等，但是實際的解釋執行過程中，“分析”和“執行”的時間往往不相等，如圖4.6(a)所示，這樣解釋執行n條指令的時間為：

T=t分１＋∑［max(t分i，t執i-1)］+t執nni=2(4.2)圖4.6分析與執行時間不相等和先行控制方式第9頁，共87頁，2023年，2月20日，星期一為解決重疊過程中的“空閑”，可采用先行控制技術，使“分析”和“執行”分別連續進行，如圖4.6（b）所示。這時，執行n條指令所需要的時間為：ni=1T先行=t分１＋∑t執i(4.3)圖4.6分析與執行時間不相等和先行控制方式第10頁，共87頁，2023年，2月20日，星期一

為了實現“分析”和“執行”分別連續進行，8086微處理器把CPU分為總線接口部件和執行部件，且設置一個指令隊列，可在執行第k條指令時由總線接口部件預取第k+1、k+2甚至k+2條指令。

圖4.7先行控制邏輯

以上可見，先行控制技術實質上是預取處理技術和緩沖技術的結合，緩沖部件一般采用先進先出寄存器，其個數稱為緩沖深度。先行控制邏輯如圖4.7所示，其中緩沖區的深度一般應滿足以下關系：D取指?！軩操作數≥D讀棧≥D寫棧第11頁，共87頁，2023年，2月20日，星期一4.2標量流水線工作原理4.2.1標量流水線工作原理4.2.2標量流水線分類4.2.3流水線性能分析4.2.4流水線中的主要障礙4.2.5流水線的實現與控制4.2.6流水線的動態調度第12頁，共87頁，2023年，2月20日，星期一4.2.1標量流水線工作原理1.標量流水線工作原理如果能把指令的執行過程細分為五個部分，如圖4.8所示。這五個部分由相應的硬件來實現，因此也稱為五個子過程或狀態，用Si表示。這樣，前一條指令只要走出第一子過程，就可以讀取下一條指令……。于是，構成標量流水線工作方式。

圖4.8流水過程示意圖

第13頁，共87頁，2023年，2月20日，星期一

設每一子過程時間相同，指令流入，經過五個子過程后從輸出端流出，若用二維坐標表示，即可構成如圖4.9所示時空圖，即空間與時間之間的二維關系圖。在理想情況下每經一個時鐘周期指令向右移動一格，新的指令從左邊進入。經過4個時鐘周期后五個部件全部工作，其中前4個時鐘周期稱為填入階段；以后，稱為填滿，即正常工作；最后，各條指令一一退出，稱為排空階段。若用m表示部件或空間段數，整個時間可為兩個部分。m△t是第一條指令流出時間，即流出第一個結果的時間；以后（n-1）△t中，每經一拍流出一個結果。圖4.9流水線各段組成與時空圖

第14頁，共87頁，2023年，2月20日，星期一

2.流水線工作特點概括起來，流水線的工作特點主要有以下幾點：（1）一條流水線通常由多個流水段組成；（2）在每一個流水段有專門的功能部件，對指令進行某種加工處理；（3）流水線的工作一般分為三個階段，即建立（填入）、填滿和排空；（4）在理想情況下，各流水段所需要的時間是相等的，流水線填滿后每隔△t時間就會有一個結果流出流水線。第15頁，共87頁，2023年，2月20日，星期一4.2.2標量流水線分類

③處理機流水線是一種宏流水過程，其中每一個處理機完成某一專門的任務，各處理機產生的結果存放到與下一個處理機共享存儲器中，如圖4.10所示。

圖4.10處理機流水線

從不同的角度來看，有不同的分類方式，大致有以下幾類。1.按照處理機分類按照處理機分類，流水線可以分為操作部件級、指令級和處理機級。①操作部件級流水線是按復雜的算術邏輯運算的過程構成流水線，比如把浮點加法運算分成求階差、對階、尾數相加和結果規格化四個子過程。②指令級流水線是把一條指令的解釋執行過程分成若干個子過程，比如前面所說的取指令、譯碼、執行、訪存和寫回五個子過程。第16頁，共87頁，2023年，2月20日，星期一2.按照功能分類

按功能可分為單功能流水線和多功能流水線兩種。單功能流水線是所有設備按照一種模式工作，僅完成一種功能；多功能流水線是指構成流水線的設備可不同組合，在不同的時間完成不同功能。圖4.11所示是TI-ASC計算機的流水結構，可構成多種流水線，比如定點加、浮點加、定點乘和浮點向量點積等。第17頁，共87頁，2023年，2月20日，星期一圖4.11多功能流水線的多種連接

第18頁，共87頁，2023年，2月20日，星期一

3.按照工作方式分類按工作方式可分為靜態和動態流水線。靜態流水線是在同一時間內只能以一種方式工作。其結構可以是單功能，也可以是多功能。其中多功能結構的流水線在同一時間只能進行一種工作；在從一種功能轉換成另一種功能時流水線必須排空。一般不希望流水線功能頻繁切換。動態流水線則允許在同一時間內將不同的功能段連接成不同的子流水線集，以完成不同的運算功能。顯然，動態流水線必定是多功能流水線；單功能流水線必定是靜態流水線。第19頁，共87頁，2023年，2月20日，星期一4.按照連接方式分類

可分為線性流水線和非線性流水線。所謂線性流水線是指從輸入到輸出各功能部件只允許經過一次，沒有反饋回路或者分支。非線性流水線是某些功能部件可能被反復使用，如圖4.12所示，S3的輸出可反饋到S2，S4的輸出可反饋到S1。顯然存在功能段使用沖突。

圖4.12非線性流水線示意圖

第20頁，共87頁，2023年，2月20日，星期一4.2.3流水線性能分析

目前，衡量流水線性能的技術指標主要有三個，即吞吐率、效率和加速比。1.吞吐率Tp吞吐率是指單位時間內處理機所能處理的任務數或者輸出的結果數，可分為最大吞吐率和實際吞吐率。（1）最大吞吐率若以△ti表示通過流水線各功能段所用的時間，那么在流水線穩定后可獲得的最大吞吐率可表示為：顯然，△ti最大的一段將成為流水線的瓶頸。如果段的△ti相差不大，則屬于正常流水線。一般需要采取一定的措施，使各段的△ti趨于一致。(4.4)Tpmax=1max(△ti)ni=1第21頁，共87頁，2023年，2月20日，星期一（2）流水線中的瓶頸如圖4.13(a)所示，由4個功能段構成流水線，其中通過第1、2、4段所用的時間為△t，通過第3段所用的時間為3△t，則時空圖如圖4.13(b)所示。顯然，最大吞吐率將降為Tpmax=1/(3△t)。圖4.13帶瓶頸流水線及其消除時空圖第22頁，共87頁，2023年，2月20日，星期一（3）消除瓶頸影響的方法為消除瓶頸影響可采取相應的措施，比如把第3段細分，使之成為3段，每段所用的時間近乎于△t，如圖4.13(c)所示。這樣，可使6個任務依次進入流水線，使最大吞吐率仍然保持為Tpmax=1/△t。圖4.13帶瓶頸流水線及其消除時空圖第23頁，共87頁，2023年，2月20日，星期一

也可采用空間重復因素，增設2個第3段，并列工作，如圖4.13(d)所示。這樣，連續的3個任務可分別通過S3a、S3b和S3c，其時空圖如圖4.13(e)所示。可在一定程度上減輕瓶頸引起的吞吐率下降。圖4.13帶瓶頸流水線及其消除時空圖續第24頁，共87頁，2023年，2月20日，星期一(4.5)Tp===nm△t+(n-1)△t1△t[1+(m-1)/n]Tpmax1+(m-1)/n(4.6)Sp====m△t+(n-1)△t1+(m-1)/nToTknm△tnmm+n-1m

（4）實際吞吐率任何一個流水線都存在填入和排空過程，因此實際吞吐率總是小于最大吞吐率。設m為流水線中功能段數，從圖4.9可以看出，完成n個任務所用的時間為：T=m△t+(n-1)△t則實際吞吐率為：顯然，當n＞＞m時，Tp→Tpmax。2.加速比Sp加速比是指執行同一任務時不采用流水線技術所用的時間與采用流水線方式所用的時間之比。對于n個任務，設有m段流水線。若不采用流水線，所用的時間為To，采用流水線后使用的時間為Tk，則加速比為：顯然，n＞＞m時，Sp→m，即最大加速比。m增大，加速比提高。第25頁，共87頁，2023年，2月20日，星期一E====n個任務占用時空區面積m段流水線總時空區面積m(m+n-1)△tnm△tnm+n-1Spm(4.7)

3.效率E效率是指流水線中各功能段的時間利用率，也就是各功能段被實際利用的時空區與各功能段所提供總的時空區面積之比。如圖4.9所示，效率可表示為：

圖4.9流水線各段組成與時空圖第26頁，共87頁，2023年，2月20日，星期一

圖4.14雙功能靜態流水線

【例4.1】流水線性能分析。設有A、B兩個向量，每個向量有4個元素，要求在如圖4.14所示的靜態加、乘雙功能流水線上計算，并求吞吐率、加速比和效率。第27頁，共87頁，2023年，2月20日，星期一

解：在流水線中，由功能段S1、S2、S3、S4、S6構成乘法流水線，S1、S5、S6構成加法流水線。設經過每一個功能段的時間均為△t，流水線的輸出可直接返回輸入端或者暫存到緩沖寄存器中，流水線功能切換時間忽略不計。為了在最短的時間內完成上述運算，可讓流水線先進行兩個向量中4個元素的加法運算，即求(a0+b0)、(a1+b1)、(a2+b2)、(a3+b3)；然后切換成乘法功能，再按照[(a0+b0)×(a1+b1)]×[(a2+b2)×(a3+b3)]的順序進行三次乘法運算。根據分析，可畫出流水線的時空圖，如圖4.15所示。從圖中可以看出，在17△t時間內輸出了7個結果，因此實際吞吐率為：Tp=7/17△t順序操作，則需要作4次加法運算和3次乘法運算。一次加法運算需要3△t，一次乘法運算需要5△t，總共需要To=4×3△t+3×5△t=27△t。這樣加速比為：Sp=To/Tp=27△t/17△t=1.88流水線的效率可用陰影面積除以全部6個狀態段的總時空面積而求得：E=(3×4△t+5×3△t)/(6×17△t)=27/102=26.4%第28頁，共87頁，2023年，2月20日，星期一

圖4.15流水線時空圖舉例

第29頁，共87頁，2023年，2月20日，星期一4.2.4流水線中的主要障礙

在實際應用中，往往有這樣或者那樣的原因使流水線不能暢通，概括起來有三種：資源相關、數據相關和控制相關。仍設流水線有五個功能段S1～S5（IF、ID、EXE、MEM、WB）。但不同指令在流過時對流水線的使用不同。下面以ALU、LOAD和STORE、BRANCH指令為例，予以說明。（1）ALU類指令在S1取出，S2譯碼，S3執行，S4不進行任何操作，在S5把執行結果寫回目標寄存器堆。（2）傳送類指令LOAD和STORE在S1取出，S2譯碼及讀寄存器堆，S3計算有效地址，S4訪問存儲器：LOAD指令在S4讀存儲器，并送數據寄存器，在S5把讀出的數據寫回寄存器堆；STORE指令僅在S4把數據寄存器中的數據寫入目標存儲器單元。第30頁，共87頁，2023年，2月20日，星期一

（3）分支轉移類BRANCH在S1取出，S2譯碼并讀寄存器堆，S3生成轉移目標地址，并形成條件碼，S4判斷條件，若成立，則將轉移地址送入程序計數器PC；S5不進行任何操作。三類指令對各功能段的占用如表4.1所示。表4.1三類指令對流水線的使用指令功能段)ALU指令LOAD/STOREBRANCHIf(S1)取指取指取指ID(S2)譯碼

讀寄存器堆譯碼

讀寄存器堆譯碼

讀寄存器堆EX(S3)執行計算有效地址計算轉移目標地址

設置條件碼MEM(S4)－訪存（讀或寫）若條件成立

轉移目標地址送PCWB(S5)結果寫回寄存器堆讀出數據寫入寄存器堆－第31頁，共87頁，2023年，2月20日，星期一

1.資源相關也稱為資源或結構沖突。如圖4.16所示，有5條指令相繼進入流水線，其中第1條指令是存儲器讀LOAD。在時鐘周期T4第1條指令執行到MEM段，和第i+3條指令的IF段發生沖突，即資源相關。

圖4.16兩條指令同時訪問存儲器沖突

第32頁，共87頁，2023年，2月20日，星期一圖4.17用停頓的方法解決存儲器沖突為了解決沖突，故在取第i+3條指令時暫停一拍，如圖4.17所示。第33頁，共87頁，2023年，2月20日，星期一2.數據相關(1)數據相關往往發生在兩條指令執行中，后一條指令所需要的操作數正好是前一條指令執行的結果。如有以下兩條指令，其執行過程如圖4.18所示。ADDR1，R2，R3；R2+R3→R1SUBR4，R1，R5；R1-R5→R4SUB指令需要在第3拍使用前一條ADD的執行結果，而ADD指令的結果要在第5拍時才能寫入寄存器R1中。即讀超前于寫（RAW）。圖4.18數據相關沖突

第34頁，共87頁，2023年，2月20日，星期一圖4.19加法運算結果定向傳送（2）解決辦法可采用“定向傳送”技術，也稱為旁路技術或相關專用通路技術。如圖4.19所示，第一條指令ADD需在WB段才能把結果寫回到R1中，而后繼指令中除了XOR之外都要在此之前使用。若采用停頓法，需停頓3拍。而ADD指令則是在EX段就已產生了運算結果，因此可直接傳送給后續的SUB、AND和OR指令的EX段。第35頁，共87頁，2023年，2月20日，星期一

定向傳送示意如圖4.20(a)所示，定向傳送的實現如圖4.20(b)所示，即增加旁路，實現運算結果的定向傳送。當然，這種方式將增加電路的復雜性。

圖4.20旁路定向傳送

第36頁，共87頁，2023年，2月20日，星期一圖4.19加法運算結果定向傳送在有些計算機中把時鐘周期分為前半周期和后半周期。讀操作一般在后半周期進行，寫操作一般在前半周期進行。這樣，對于圖4.19所示的指令OR的定向傳送可以取消，如圖4.21所示。第37頁，共87頁，2023年，2月20日，星期一

圖4.21減少定向傳送措施

第38頁，共87頁，2023年，2月20日，星期一

（3）數據相關類型數據相關有三種類型，即RAW、WAR、WAW：①RAW：是指令j試圖在指令i寫入寄存器之前讀取寄存器中的數據，這樣指令j讀出的就是其原來的內容，簡稱為讀超前于寫。②WAR：是指令j試圖在指令i讀出寄存器中的數據之前寫入寄存器，這樣指令i讀出的就是寄存器中的新內容，簡稱為寫超前于讀。③WAW：是指令j試圖在指令i寫入寄存器之前寫入寄存器，這樣兩條指令的寫入過程顛倒，簡稱為j寫超前于i寫。（4）裝入延遲在RISC機中，執行指令LOAD存在一定的延遲，稱為裝入延遲。如圖4.22(a)所示，指令LOAD在MEM段(S4)才能把數據從存儲器中讀出，而指令ADD則在EX段就要使用。

圖4.22(a)RISC機中的裝入延遲第39頁，共87頁，2023年，2月20日，星期一圖4.22(b)裝入延遲引起的停頓

由于是訪問存儲器，尚不能定向傳送，多采用停頓的方法，如圖4.22(b)所示，稱為流水線裝入延遲或者“空泡”。第40頁，共87頁，2023年，2月20日，星期一

3.控制相關（1）控制相關也稱為控制轉移沖突，主要由轉移類指令引起。統計表明，一般程序中轉移指令占1/4。轉移發生時，流水線受到破壞，程序計數器PC指向新的指令地址。由于一般在MEM段的末尾才能使PC值改變，于是需停頓3個時鐘周期，如圖4.23所示。

圖4.23控制相關引起的停頓

第41頁，共87頁，2023年，2月20日，星期一

【例4.2】設在某一程序中，有25%的轉移指令，其中2/3轉移發生，試計算執行一條指令的平均時鐘周期。

解：設執行一條指令的平均時鐘周期為Pi，則Pi=1×75%+1×25%×[1×1/3+2/3×(3+1)]=1.5(周期)顯然，使流水線的性能下降33.3%。（2）減少控制相關對流水線性能影響的措施常有以下幾種。①盡早判斷轉移發生和生成轉移地址。把原在MEM段進行目標地址的計算提前到ID段進行，并在條件成立時送入程序計數器PC。這樣，可使流水線頓時間由3拍減少到1拍。②預取轉移成功和不成功兩個方向上的目標指令。設兩個指令隊列，預取兩個隊列。③加快和提前形成條件碼。比如乘除法運算的結果符號可根據兩操作數的符號提前產生。第42頁，共87頁，2023年，2月20日，星期一④加快短循環程序的處理。對于反復執行的短循環程序可以全部取出，放入指令緩沖器中，以提高處理速度。⑤提高轉移方向的預測率預測方法可用狀態圖表示，如圖4.25所示。圖4.25轉移預測狀態圖第43頁，共87頁，2023年，2月20日，星期一其中使用兩位二進制數表示是否轉移，11和10表示預測轉移發生狀態，00和01表示預測轉移不發生狀態。ⅰ

如果狀態標志處在11狀態，即預測轉移發生，這時如發生轉移，原狀態保持；若不發生轉移，則低位清0，狀態標志變為10，仍是預測轉移發生狀態。ⅱ

在10狀態，如果發生轉移，則低位置1，狀態標志變為11；若不發生轉移，則高位清0，狀態標志變為00。ⅲ

在00狀態，如果不發生轉移，原狀態保持；若發生轉移，則低位置1，狀態標志變為01，仍預測轉移不發生。ⅳ

在01狀態，如果發生轉移，則高位置1，狀態標志變為11；若不發生轉移，則低位清0,狀態標志變為00。統計表明，預測準確率達83%。第44頁，共87頁，2023年，2月20日，星期一⑥

采用延遲轉移技術如圖4.24所示，在執行轉移指令時流水線停頓，即轉移延遲。延遲時間稱為延遲槽。可取適當的指令在延遲遭執行，即填補延遲槽。常用方法有三種，如圖4.26所示。

圖4.26采用延遲轉移技術的3種方法

第45頁，共87頁，2023年，2月20日，星期一在圖4.26(a)中，是用條件轉移指令IF的前一條指令ADDR1，R2，R3填補到延遲槽。在圖4.26(b)中，是用轉移目標處的第一條指令SUBR4，R5，R6填補延遲槽，而原來位置的指令仍然保留。在圖4.26(c)中，是用非轉移方向的指令填補延遲槽。前提是不發生數據相關。實踐表明，第一種方案較好于其它兩種。第46頁，共87頁，2023年，2月20日，星期一4.2.5流水線的實現與控制

1.流水線中的中斷處理在早期的流水線計算機中，只對中斷的現場進行不精確保護，即對進入流水線的指令處理完畢，再去響應中斷請求。顯然，此時已不再是中斷請求時的現場。這對于外部設備的中斷請求可能影響不大，但是對于陷阱和內部中斷影響就大了?，F在采用的是精確斷點保護法，即使用大量的后援寄存器，以使進入流水線的所有指令的現場都得到保護和恢復。2.非線性流水線中功能段的競爭與調度對于非線性流水線，存在前饋和反饋。若不能很好地調度，就會出現兩條指令或任務爭用某一功能段。若要不發生沖突，就要相隔適當的時間調度下一條指令或任務進入流水線。下面借助于預約表進行分析。第47頁，共87頁，2023年，2月20日，星期一

設有一個非線性、單功能流水線P，由K個功能段組成，每一個任務流過流水線需要的時鐘周期數為N（t1,t2,…,tn），縱向表示功能段，橫向表示時鐘周期，可畫出如圖4.27所示的預約表。圖中的每一行表示P的一個功能段，每一列表示一個時鐘周期，總列數表示任務從流入到流出所經過的總時鐘周期數。若某任務在某一時刻ti使用功能段Si，用“√”

表示。一行中有多個“√”，表示重復使用該功能段。根據預約表很容易看出第一段間隔數為8，第二段間隔數為1，5，6等。把所有行的間隔節拍數都列出來，可構成一個間隔禁止表F(Forbiddenlist)，即F={1，5，6，8}，表示禁止相隔這些拍數調度。圖4.27預約表

第48頁，共87頁，2023年，2月20日，星期一

可用N-1位的二進制向量C=(Cn-1，Cn-2，……，C2，C1)表示，稱為沖突向量(Collisionvector)。其中第i位的狀態表示與當前任務相隔i拍調入下任務時，是否發生沖突。0表示不沖突，1表示沖突。沖突向量取N-1位是因為經過N拍后任務就流出流水線，又由于位數N是最大禁止間隔，因此Cn-1位總是1。根據上述禁止表F，可形成相應的沖突向量（10110001），稱為原始沖突向量。第2，3，4，7位為0，可與當前任務相隔2拍、3拍、4拍或7拍調入下一任務。下一任務進入流水線后，將產生新的沖突向量。然后再根據新的沖突向量確定第三個任務何時調入。第49頁，共87頁，2023年，2月20日，星期一

如何形成新的沖突向量呢？任何一個任務在流水線中每經一拍向前推進一段，相當于原始沖突向量右移一位，左邊補0。這樣，就形成了新的沖突向量。例如選擇第二個任務在2拍后調入流水線，則原始沖突向量應當邏輯右移兩位，即（00101100）。為使第三個任務調入后不與前兩個任務發生沖突，新的沖突向量應當是第二個任務的當前沖突向量（00101100）與第二個任務的初始沖突向量（10110001）按位“或”，結果為（10111101）。按照這一方式，選擇各種可能的間隔拍數調入新的任務，并產生新的沖突向量，一直進行到不再產生新的沖突向量為止。第50頁，共87頁，2023年，2月20日，星期一

需要注意的是，在產生新的沖突向量時每次右移后的位向量應與原始沖突向量按位“或”。由此可以畫出用沖突向量表示的流水線狀態轉移圖，如圖4.28所示。圖4.28流水線狀態圖第51頁，共87頁，2023年，2月20日，星期一表4.2各調度方案平均間隔拍數調度策略平均間隔拍數(3,4)(4,3)(2,7)(2,2,7)(3,4,3,7)(3,4,7)(4,3,7)(3,7)(4,7)(7)3.503.504.503.674.254.674.675.005.507.00

采用圖中任何一個閉合回路進行調度，都不會發生功能部件沖突。但需找到一個最佳策略，以便獲得最高吞吐率。其方法是計算出每一種調度法的平均間隔拍數，如表4.2所示。然后，找出最小的一個。這里，平均間隔為3.5拍的調度策略有兩種，即（3,4）和（4,3）。第52頁，共87頁，2023年，2月20日，星期一4.2.6流水線的動態調度

靜態調度主要借助于軟件對指令的執行順序進行調整，目前已經得到廣泛應用。動態調度起始更早，但是直到20世紀后期才得以發展。它主要是通過硬件重新安排指令的執行順序，以減少流水線中的停頓。有以下優點：①能處理在編譯時難以發現的相關；②能簡化編譯程序；③使代碼具有可移植性。其缺點主要是硬件電路復雜。目前主要有兩種方法，一種是集中式動態調度，另一種是分布式動態調度。第53頁，共87頁，2023年，2月20日，星期一

1.集中式動態調度集中式動態調度是依賴硬件在程序運行的過程中對可能出現的相關進行預測，從而保證流水線中的各個功能部件能最大限度地重疊工作，其示意如圖4.29所示。

圖中主要設置了一個狀態寄存器RF和一個記錄控制器（也稱為記分牌），用來對各功能部件的工作狀態、進入流水線中的各條指令的狀態、圖4.29集中式動態調度使用的源寄存器和目標寄存器的狀況進行集中統一的記錄和調度。早期的CDC6600計算機采用的就是這一技術，現在的RISC超級標量機很多也采用與之類似的措施，以提高流水線的性能。第54頁，共87頁，2023年，2月20日，星期一2.分布式動態調度是把調度控制分配到各功能部件上。早期的IBM360/91采用了這一技術，其示意如圖4.30所示。其中每一個浮點數寄存器FLR設置一個“忙”標志，以表示指令間所用的數據是否會發生沖突。其浮點運算器主要包括以下部件。（1）運算器：由相互獨立的加法器和乘除法器組成。（2）保存站：在加法器中有三個A1～A3，在乘除法器中有兩個M1～M2，當兩個數據都到齊后，若運算器空閑，立即進行運算。每一個保存站都有地址，稱為站號。保存站與浮點操作數緩沖寄存器FLB統一編址，如圖3.30所示。（3）指令處理部件：也稱為浮點操作棧，用來存放取出的指令，經譯碼產生控制信號，送往相應的部件。（4）浮點數據預取緩沖器FLB：暫存存儲器中預取出來的浮點數，作為源操作數。（5）浮點數據寄存器FLR：作為另一源操作數；或者存放運算結果或中間結果，即目標寄存器。各寄存器有一個“忙”標志，其中“1”表示寄存器正被使用。另外，每個寄存器設有“站號標記”，表示數據由何而來。該組寄存器表示為F0～F7。（6）數據存儲緩沖器SDB：用來暫存欲存入存儲器的數據，也設有站號，表示數據由何而來。（7）公用數據總線CDB：用來連接上述各個部件，傳送數據。第55頁，共87頁，2023年，2月20日，星期一圖4.30IBM360/91流水線的分布式動態調度示意圖

第56頁，共87頁，2023年，2月20日，星期一F0置忙

M1：源1站號置0001源2站號置0010F0置1000A1：源1站號置0011源2站號置0100F0置1010S1：LDF0，FLB1F0←0001

S2：MDF0，FLB2

S3：STDF0，AC1站←1000S4：LDF0，FLB3F0站←0011S5：ADDF0，FLB4第57頁，共87頁，2023年，2月20日，星期一

這種調度方法是把數據的傳送控制分派到各個單元的站號的設置上，即分布式動態調度方式。其特點可概括為以下幾點。（1）通過公用數據總線把數據直接傳送到所需要的部件，減少了流水線中的停頓周期。（2）通過加法器保存站和乘除法保存站，可緩解資源使用中沖突的機會。（2）通過修改站號實現分布式動態調度，可消除WAR和WAW數據相關的可能性。（3）通過對FLR寄存器“忙”標志的判斷，可檢查是否存在RAW數據相關。

第58頁，共87頁，2023年，2月20日，星期一圖4.31轉移目標緩沖器

3.硬件動態預測轉移法是由轉移目標緩沖器BTB（Branchtargetbuffer）來實現。BTB由高速存儲器或者寄存器堆組成，按內容訪問，圖4.31所示。第59頁，共87頁，2023年，2月20日，星期一

其中存放轉移指令的地址（即PC值）、轉移目標地址和2位狀態標志。標志位按照圖4.25設置，用于轉移預測。

圖4.25轉移預測狀態圖

遇到轉移指令時，用PC值與BTB中的內容進行比較。若有相符合內容，則判斷標志位，以確定是否取出轉移目標地址。若轉移條件成立，則根據取出的目標地址執行程序；若轉移條件不成立，則取消本次操作，并修改狀態標志位。第60頁，共87頁，2023年，2月20日，星期一4.3指令級流水線4.3.1指令級流水線4.3.2超級標量流水線4.3.3超長指令字4.3.4展開循環體后調度4.3.5軟件流水法4.3.6超級流水機舉例第61頁，共87頁，2023年，2月20日，星期一4.3.1指令級流水線

流水線可分為粗粒度和細粒度兩種類型，其中細粒度流水線指的就是指令級流水線。20世紀80年代發展起來的RISC機在指令級流水線的開發中取得了很大的成就，它的目標是使CPI達到1。新一代RISC機還試圖使CPI小于1。指令級流水線的并行性常用并行度來衡量，是指在不存在相關，可同時并行執行的指令的條數。下面舉例說明。

第62頁，共87頁，2023年，2月20日，星期一【例4.2】分析下面兩個程序段的并行度。程序段1程序段2LOADR1，M[R7]ADDR2，R1，1ADDR3，R3，1SUBR4，R3，R2FPMULF3，F3，F4STOREM[R4]，R5

解：由于在程序段1中，3條指令所使用的數據地址不存在相關，因此可并行執行，其并行度為3。而在程序段2中，ADD指令的目標寄存器是R2，而在SUB指令中R2是源操作數，存在RAW相關；同時，在SUB指令中R4是目標寄存器，而在STORE指令中R4作為基地址寄存器，也是一種RAW相關。因此，在程序段2中3條指令只能順序執行，即并行度為1。目前在指令級流水線中，主要使用的方法有超級標量流水線法和超長指令字法。第63頁，共87頁，2023年，2月20日，星期一4.3.2超級標量流水線

1.基本概念在理想的流水線中，每一個時鐘周期可啟動一條指令。執行過程分為4個階段，理想流水線的示意如圖4.32所示。在超級標量流水線中，人們希望在一個時鐘周期內啟動多條指令。如圖4.33所示同時啟動了3條指令，因此并行度為3。圖4.32理想流水線圖4.33每拍啟動三條指令第64頁，共87頁，2023年，2月20日，星期一

圖4.34每1/2拍或每1/3拍啟動一條或三條指令也可以每1/2周期或者每1/3周期啟動一條指令，如圖4.34(a)所示每1/2周期啟動一條指令，并行度為2。還可以每1/2周期或者1/3周期啟動多條指令，如圖4.34(b)所示每1/3周期啟動了3條指令，其并行度為9。第65頁，共87頁，2023年，2月20日，星期一

圖4.37超長指令字（VLIW）

另外，也可以通過超長指令字實現每個時鐘周期完成多個操作，如圖4.37所示。第66頁，共87頁，2023年，2月20日，星期一2.超級標量機的組成特點在超級標量流水線計算機中要實現一拍完成多個操作，就必須有相應的功能部件予以支持。如圖4.35(a)所示，只有一個ALU，每一拍只能進行一種操作，即啟動一條指令。如圖4.35(b)提供一個ALU和一個浮點運算器FP，可在一拍中進行兩種操作，即啟動兩條指令。圖中I-Cache表示指令高速緩沖存儲器，RF表示寄存器堆。

圖4.35超級標量機多執行部件第67頁，共87頁，2023年，2月20日，星期一

圖4.36超級標量機典型結構3.超級標量機的典型結構圖4.36所示是一種超級標量機的典型結構，由存儲部件、ALU部件及控制部件組成。第68頁，共87頁，2023年，2月20日，星期一

程序執行時同時取出兩條指令，分別送相應的譯碼器。譯碼后，根據狀態記錄部件中記錄的功能部件與寄存器使用情況，確定哪些指令可以送入執行部件中同時執行；有關寄存器和執行部件的狀態可能發生變化，送狀態記錄部件，供下一次判斷使用。即根據狀態記錄部件中記錄的相關信息來確定多條指令可否同時被調度和執行。自20世紀80年代末，超級標量機陸續問世，比如Intel公司的i860、IBM公司的RS6000以及Motorola公司的88110等。在一個周期內可啟動2～4條指令。但是在實際運行時，一個時鐘周期啟動的指令條數往往小于IPC（Instructionpercycle）的值。主要特點:①配置有多個性能不同的處理部件，采用多條流水線并行處理。②能同時對多條指令進行譯碼，并根據狀態記錄部件中記錄的狀態將可執行指令送入相應的執行部件。③通過硬件實現多條指令的調度，即用硬件資源重復來實現空間上的并行操作。第69頁，共87頁，2023年，2月20日，星期一4.3.3超長指令字1.超長指令字超長指令字VLIW（Verylonginstructionword）是在20世紀80年代初由美國耶魯大學的Fisher教授首先提出來的。它的一條指令很長可達上百位，甚至上千位，主要在于減少訪存次數，如圖4.37所示在一個周期完成多個操作。

圖4.37超長指令字（VLIW）

特點：單一控制器，每個周期啟動一條指令。在其內部，一條超長指令字被分成多個控制字段，獨立控制一個功能部件。第70頁，共87頁，2023年，2月20日，星期一2.超長指令字計算機的組成原理

超長指令字計算機的結構示意如圖4.38所示，包含兩個存儲器讀/寫部件、一個浮點加法部件和一個浮點乘法部件。所有功能部件均由統一的時鐘信號驅動，根據超長指令的各個控制字段工作。圖中包括存/取1、存/取2、浮點加、浮點乘及其相關的數據通路，可同時進行兩路存儲器訪問、浮點加和浮點乘操作。這種計算機是在編譯時處理可能出現的數據相關和資源相關，因此硬件電路比較簡單。而且，在編譯階段完成超長字指令中多個可并行執行的操作的調度。圖4.38超長指令字計算機結構示意圖第71頁，共87頁，2023年，2月20日，星期一表4.3順序執行序列源代碼操

作需用周期C=A+BLOADALOADBC=A+BSTOREC1111K=I+JLOADILOADJK=I+JSTOREK1111L=M-KLOADML=M-KSTOREL111Q=C×KQ=C×KSTOREQ21合計14個周期3.超長指令字的生成設有以下賦值運算：C=A+BK=I+JL=M-KQ=C×K若按照順序操作，所使用的指令序列如表4.3所示，共需要14個周期。從中找出不存在任何相關的操作同時進行，即可得到如表4.4所示的并/串行操作序列。這樣，每一行可構成一個超長字指令，編譯時可把13條指令壓縮成6條，僅需要6個周期即可完成。表4.4并行操作序列周期操

作1LOADALOADB2LOADILOADJC=A+B3LOADMSTORECK=I+J4STOREKL=M-KQ=C×K5STOREL6STOREQ第72頁，共87頁，2023年，2月20日，星期一

4.VLIW壓縮調度技術上述壓縮采用的是表調度法，而且是一種局部壓縮調度法。目前常用的壓縮調度方法可分為局部壓縮和全局壓縮。（1）局部壓縮局部壓縮是在小范圍內進行，即一個基本的程序塊，僅有一個入口和一個出口。（2）全局壓縮全局壓縮允許代碼在基本程序塊之間移動。當然，這種移動必須保證各個基本程序塊原語義不變。目前全局壓縮有三種方式，即路徑調度、滲透調度和軟件流水。①路徑調度法是在編譯時把代碼劃分為若干不相交的子集，稱之為路徑，然后選擇執行概率最高的路徑作為主路徑。對主路徑采用表調度法進行壓縮，且允許代碼在一定約束條件下在基本塊之間移動。這種方式可能犧牲非主路徑的性能，以獲得主路徑的最佳效果。但是非主路徑需要進行補償。第73頁，共87頁，2023年，2月20日，星期一

圖4.39表示沿主路徑壓縮及補償的示意。在圖4.39中，(a)的陰影框表示主路徑，（b）表示壓縮后對非主路徑造成的影響，(c)表示補償，其中R表示重聚補償，S表示分裂補償。補償的具體過程如圖4.40所示。圖4.39沿主路徑壓縮與補償示意圖

第74頁，共87頁，2023年，2月20日，星期一在圖4.40中，是對主路徑進行調度后而進行的補償。其中圖(a)是用第一條指令填補if語句的延遲槽，而對if語句進行的分裂補償。圖(b)是用第二條指令填補乘法語句的延遲槽，而對乘法指令進行重聚補償。圖4.40路徑調度與補償

第75頁，共87頁，2023年，2月20日，星期一②滲透調度法（Percolationscheduling）是通過一系列語義的等價變換，把操作不斷地推向前進，即滲透。滲透后把屬于不同基本塊的操作最大限度地重疊起來。不是根據轉移分支的概率選擇操作，而是設法讓后續的操作近早執行。具體的實施方法，請參閱高級編譯技術的有關章節。③軟件流水法（Softwarepipelining）主要是加快循環程序的執行，在4.3.5節介紹。

第76頁，共87頁，2023年，2月20日，星期一4.3.4展開循環體后調度

展開循環體后調度是在編譯時多次展開循環體，然后在程序語義保持不變的前提下對指令序列重新排列，以提高流水線的并行度。下面舉例說明：設有以下循環體程序段，為存儲器中的某一向量加上F2中的一個指定的標量值。

LOOP：LDF0，0(R1)；F0←M[(R1)+0]，讀向量元素ADDDF4，F0，F2；F4←(F0)+(F2)SD0(R1)，F4；M[(R1)+0]←F4，存向量元素SUBR1，R1，#8；R1←(R1)-8，將指針減8BNEZR1，LOOP；若(R1)≠0，則轉移到LOOP第77頁，共87頁，2023年，2月20日，星期一

設浮點加法需要3個周期，寄存器整型運算需要1個周期，分支指令需要2個周期，讀存儲器需要2個周期，寫存儲器時只要送入存儲緩沖器即可，因此僅1個周期。為了使流水線正確工作，須插入等待周期，用STALL表示：LOOP：LDF0，0(R1)；F0←M[(R1)+0]，讀向量元素STALL；停頓ADDDF4，F0，F2；F4←(F0)+(F2)STALLSTALLSD0(R1)，F4；M[(R1)+0]←F4，存向量元素SUBR1，R1，#8；R1←(R1)-8，將指針減8BNEZR1，LOOP；若(R1)≠0，則轉移到LOOPSTALL需要9個周期。

第78頁，共87頁，2023年，2月20日，星期一

1.未展開循環體調度對循環體重新調度，僅需6個周期完成。LOOP：LDF0，0(R1)；F0←M[(R1)+0]，讀向量元素STALL；裝載停頓ADDDF4，F0，F2；F4←(F0)+(F2)SUBR1，R1，#8；R1←(R1)-8，將指針減8B