1、提高指令執行速度的主要途徑：(1)提高處理機的工作主頻(2)采用更好的算法和設計更好的功能部件(3)采用指令級并行技術時間重疊:流水線技術資源重復:超標量技術三種指令級并行處理機：(1)流水線處理機和超流水線(Super-pipelining)處理機(2)超標量(Superscalar)處理機(3)超長指令字(VLIW: Very Long Instruction Word)處理機5.1先行控制技術5.2流水線技術5.3相關性分析技術5.4動態調度技術5.5超標量處理機5.6超流水線處理機5.7超標量超流水線處理機第5章 標量處理機5.1 先行控制技術5.1.1指令的重疊執行方式5.1.2先行

2、控制方式的原理5.1.3處理機結構5.1.4指令執行序列5.1.5先行緩沖棧5.1.6緩沖深度的設計方法5.1.1指令的重疊執行方式1.順序執行方式執行n條指令所用的時間為：如果每段時間都為t，則執行n條指令所用的時間為：T3nt主要優點：控制簡單，節省設備主要缺點：速度慢，功能部件的利用率低2.一次重疊執行方式如果兩個過程的時間相等，則執行n條指令的時間為：T(1+2n)t主要優點： 指令的執行時間縮短， 功能部件的利用率明顯提高。主要缺點： 需要增加一些硬件， 控制過程稍復雜。3.二次重疊執行方式如果三個過程的時間相等，執行n條指令的時間為：T(2n)t理想情況下，處理機中同時有三條指令在

3、執行。處理機的結構要作比較大的改變，需要采用先行控制技術。 5.1.2先行控制方式的原理1.采用二次重疊執行方式必須解決兩個問題：(1)有獨立的取指令部件、指令分析部件和指令執行部件 把一個集中的指令控制器，分解成三個獨立的控制器：存儲控制器、指令控制器、運算控制器(2)訪問主存儲器的沖突問題 取指令、分析指令、執行指令都可能要訪問存儲器2.解決訪存沖突的方法：(1)采用低位交叉存取方式：增加頻寬 這種方法不能根本解決沖突問題。指令、讀操作數、寫結果。(2)兩個獨立的存儲器：獨立的指令存儲器和數據存儲器如果再規定，執行指令所需要的操作數和執行結果只寫到通用寄存器，則取指令、分析指令和執行指令就

4、可以同時進行。在許多高性能處理機中，有獨立的指令Cache和數據Cache。這種結構被稱為哈佛結構。3.先行控制技術基本思想：使分析和執行部件分別連續不斷地運行，使部件空閑狀態減至最低。關鍵是緩沖技術和預處理技術。緩沖技術：通常用于工作速度不固定的兩個功能部件之間。設置緩沖棧的目的是用來以平滑功能部件之間的工作速度。預處理技術：把進入運算器的指令都預處理成R-R型指令，與緩沖技術相結合，為進入運算器的指令準備好所需的全部操作數采用緩沖技術和預處理技術之后，運算器能夠專心于數據的運算，從而大幅度提高程序的執行速度。硬件要求增設指令緩沖棧，消除取指過程；增設數據緩沖棧，保證不同指令的讀、寫操作并行

5、；增設先行操作棧，保證執行部件能連續執行。5.1.3 處理機結構1.三個獨立的控制器：存儲控制器、指令控制器、運算控制器。2.四個緩沖棧：先行指令緩沖棧、先行讀數緩沖棧、先行操作棧、后行寫數棧。3.處理機組成4.先行指令緩沖棧的組成作用：只要指令緩沖棧沒有充滿，就自動發出取指令的請求。需要設置兩個程序計數器：先行程序計數器PC1：用來指示取指令；現行程序計數器PC：記錄指令分析器正在分析的指令地址。5.存在的主要問題：各類指令“分析”和“執行”的時間相差很大數據相關轉移或轉子程序指令 先行緩沖棧的組成5.1.4 指令執行時序設置了指令緩沖棧，取指令的時間就可以忽略不計。一條指令的執行可分為2個

6、過程：分析指令和執行指令。1.分析指令和執行指令時間不相等時的情況2.采用先行緩沖棧的指令執行過程理想情況下，指令執行部件應該一直忙碌。連續執行n條指令的時間為：需要設置先行讀數棧,先行操作棧,后行寫數棧。(a)重疊方式分析k+1分析k執行k執行k+1分析k+2執行k+2分析部件空閑執行部件空閑分析k+1分析k執行k分析k+2(b)先行控制執行k+1執行k+23.指令重疊執行與先行控制技術的比較5.1.5 先行緩沖棧設置先行緩沖棧的目的：使指令分析器和指令執行部件能夠獨立工作。1.先行指令緩沖棧：處于主存儲器與指令分析器之間，用它來平滑主存儲器取指令和指令分析器使用指令之間的速度差異RR型指令

7、，不必處理，直接送先行緩沖棧RS型指令，主存有效地址送先行讀數棧，用該先行讀數棧的寄存器編號替換指令中的主存地址碼部分，形成RR*指令送先行指令緩沖棧RI型指令，指令中的立即數送先行讀數棧，用該先行讀數棧的寄存器編號替換指令中的立即數部分，形成RR*指令送先行指令緩沖棧轉移指令，一般在指令分析器中直接執行。2.先行操作棧處于指令分析器和運算控制器之間，使指令分析器和運算器能夠各自獨立工作。采用先進先出方式工作，由指令寄存器堆和控制邏輯組成。3.先行讀數棧處于主存儲器與運算器之間，平滑運算器與主存儲器的工作每個緩沖寄存器由地址寄存器、操作數寄存器和標志三部分組成。也可以把地址寄存器和操作數寄存器

8、合為一個。當收到從指令分析器中送來的有效地址時，就向主存申請讀操作數。讀出的操作數存放在操作數寄存器中或覆蓋掉地址寄存器中的地址。4.后行寫數棧處于主存儲器與運算器之間，平滑運算器與主存儲器的工作每個后行緩沖寄存器由地址寄存器、數據寄存器和標志三部分組成。指令分析器遇到向主存寫結果的指令時，把形成的有效地址送入后行寫數棧的地址寄存器中，并用該地址寄存器的編號替換指令的目的地址部分，形成RR*指令送入先行操作棧。當運算器執行這條RR*型寫數指令時，只要把寫到主存的數據送到后行寫數棧的數據寄存器中即可。5.采用先行控制方式時一個程序的執行情況：5.1.6 緩沖深度的設計方法以靜態分析為主，通過模擬

9、來確定緩沖深度。1.先行指令緩沖棧的設計考慮兩種極端情況：假設緩沖深度為DI(1)先行指令緩沖棧已經充滿指令流出的速度最快，例如連續分析RR型指令，設這種指令序列的最大長度為L1，平均分析一條這種指令的時間為t1；指令流入的速度最慢，設平均取一條指令的時間為t2。從主存儲器中取到先行指令緩沖棧中的指令條數是L1DI條。應該滿足如下關系：L1 t1(LIDI) t2計算出緩沖深度為： 如果這種指令流的連續長度超過L1，則先行指令緩沖棧失去作用。(2)先行指令緩沖棧原來為空輸入端指令流入的速度最快，每次取指令的時間最短；設這種指令序列的最大長度為 L2，平均取一條這種指令的時間為t2；輸出端指令流

10、出的速度最慢，指令分析器連續分析最難分析的指令；設平均分析一條指令的時間為 t1。分析的指令條數是L2DI條。應該滿足如下關系：(L2DI)t1LIt2計算出緩沖深度為： 如果這種指令流的連續長度超過L2，先行指令緩沖棧失去緩沖作用。2.設計舉例在一般處理機中連續執行短指令的概率大。例5.1：一個采用先行控制方式的處理機，指令分析器分析一條指令用一個周期，到主存儲器中取一條指令裝入先行指令緩沖棧平均用4個周期，如果這種指令的平均長度為9，即90的指令是執行時間短的指令。解：計算先行指令緩沖棧的緩沖深度為：3.先行指令緩沖棧的工作時間關系第1個周期，取走指令k+1，請求取指令第4個周期末尾，指令

11、k+8取到先行指令緩沖棧第8個周期末尾，指令k+9取到先行指令緩沖棧第9個周期，分析指令k+9，先行指令緩沖棧空第10個周期，指令分析器等待4.其余緩沖棧的設計原則其余3個緩沖棧也采用類似的方法確定。一般有關系：DIDCDRDW其中：DI是先行指令緩沖棧的緩沖深度， DC是先行操作棧的緩沖深度， DR是先行讀數棧的緩沖深度， DW是后行寫數棧的緩沖深度。例如：IBM370/165機： DI4，DC3，DR2，DW1。 我國研制的兩臺大型計算機： DI8，DCDR4，DW2。 DI12，DCDR6，DW2。處理機內部的并行性： 空間并行性：設置多個獨立的操作部件 （資源重復）時間并行性：分時使用

12、同一個部件的不同部分（時間重疊）5.2.1流水線工作原理5.2.2流水線的分類5.2.3線性流水線的性能分析5.2.4非線性流水線的調度5.2 流水線技術5.2.1 流水線工作原理1.流水寄存器流水線的每一個階段稱為流水步、 流水步驟、流水線階段、流水段、流水功能段、功能段、流水級、流水節拍等。在每一個流水段的末尾或開頭必須設置一個寄存器，稱為流水寄存器、流水鎖存器、流水閘門寄存器等。加入流水寄存器，會增加指令的執行時間。在一般流水線時空圖中不畫出流水寄存器。基本思想：流水是重疊的進一步延伸，使指令解釋過程進一步細化，提高各部件的利用率，以提高指令執行速度。2.一種指令流水線一般4至12個流水

13、段，8個流水段的稱為超流水線處理機3.流水線時空圖一個浮點加法器流水線的時空圖(由求階差、對階、尾數加和規格化4個流水段組成)： 有些復雜指令，在執行階段也采用流水線方式工作，稱為操作流水線。4.流水線的主要特點只有連續提供同類任務才能發揮流水線效率（1）盡量減少因條件分支造成的“斷流”（2）通過編譯技術提供連續的相同類型操作每個流水線段都要設置一個流水寄存器（1）時間開銷：流水線的執行時間加長（2）是流水線中需要增加的主要硬件各流水段的時間應盡量相等 流水線處理機的基本時鐘周期等于時間最長的流水段的時間長度。流水線需要有“裝入時間”和“排空時間” 121321nn-1.43215432.54

14、3.54.5nn-1.n-1.nn-1n1234t0 t0 t0 t0T0=m t0n t0T(m-1) t0(n-1) t0裝入 正常 排空 流水時空圖空間時間5.2.2 流水線的分類1.按照流水線的各個流水段之間是否有反饋回路線性流水線（Linear Pipelining）：每一個流水段都流過一次，而且僅流過一次線性流水線能夠用流水線連接圖唯一表示非線性流水線（Nonlinear Pipelining）：某些流水段之間有反饋回路或前饋回路。非線性流水線必須用流水線連接圖和流水線預約表共同表示S1S2S3S4輸入輸出2.按照流水線的級別來分 處理機級流水線，又稱為指令流水線。 例如：在采用先

15、行控制器的處理機中，各功能部件之間的流水線 部件級流水線(操作流水線) 如浮點加法器流水線 宏流水線(Macro Pipelining) 處理機之間的流水線稱，每個處理機對同一個數據流的不同部分分別進行處理。3.按照流水線完成的功能來分 單功能流水線：只能完成一種固定功能的流水線。 Cray-1計算機種有12條，YH-1計算機有18條 Pentium有一條5段定點和一條8段浮點流水線。 Pentium有兩條定點和一條浮點指令流水線。 多功能流水線：流水線的各段通過不同連接實現不同功能 Texas公司的ASC機，8段流水線，能夠實現：定點加減法、定點乘法、浮點加法、浮點乘法、邏輯運算、移位操作、

16、數據轉換、向量運算等。4.按照流水線的連接方式來分靜態流水線：同一段時間內，各個功能段只能按照一種方式連接，實現一種固定的功能。動態流水線：在同一段時間內，各段可以按照不同的方式連接，同時執行多種功能。區別：從軟硬功能分配的觀點來看，靜態流水線把功能負擔較多地加到軟件上，以簡化硬件；動態流水線則把功能負擔較多地加在硬件上，以提高流水的效率。5.流水線的其他分類方法按照數據表示方式：標量流水線和向量流水線按照控制方式：同步流水線和異步流水線順序流水線與亂序流水線，亂序流水線又稱為無序流水線、錯序流水線或異步流水線等。5.2.3 線性流水線的性能分析主要指標：吞吐率、加速比和效率1.吞吐率（Tho

17、ugh Put）流水線吞吐率的最基本公式：其中：n為任務數， k為完成n個任務所用的時間。各段執行時間相等，輸入連續任務情況下，完成n個任務需要的總時間為： Tk(kn1)t其中：k 為流水線的段數，t為時鐘周期。 Tk= k t + (n-1) t = (k+n-1)t吞吐率為：最大吞吐率為：各段時間不等，完成n個連續任務：吞吐率：最大吞吐率：流水線各段執行時間不相等的解決辦法(1)將“瓶頸”部分再細分（如果可分的話）2.加速比（Speedup）計算加速比的基本公式：各段執行時間相等，輸入連續任務情況下,加速比：最大加速比：各段時間不等，輸入連續任務情況下, 實際加速比為：當流水線段數增加時

18、，需要連續輸入的任務 數也必須增加3.效率（Efficiency）計算流水線效率的一般公式：各流水段時間相等，輸入n個連續任務，流水線的效率為：最高效率為：各流水段時間不等，輸入n個連續任務，流水 線效率為： 各段設備量或價格不等時，流水線的效率為：即：其中權值aik，且 =k。流水線的吞吐率、加速比與效率的關系：因為：因此：ETPt，SkE4.流水線最佳段數的選擇采用順序執行方式完成一個任務的時間為t在同等速度的 k 段流水線上執行一個任務的時間為：tkd (d為流水鎖存器的延遲時間)流水線的最大吞吐率為：P=1(tkd)流水線的總價格估計為：Cab k， 其中：a為功能段身的總價格， b為

19、每個鎖存器的價格 A.G.Larson把流水線的性能價格比PCR定義為： 求PCR的最大值為：5.流水線性能分析舉例對于單功能線性流水線，輸入連續任務的情況，通過上面給出的公式很容易計算出流水線的吞吐率、加速比和效率。對于輸入不連續任務，或多功能流水線，通常不能采用基本公式計算。需要畫出時空圖，舉例說明如下。例5.2：用一條4段浮點加法器流水線求8個浮點數的和：ZABCDEFGH解：Z(AB)(CD)(EF)(GH)5.2.4 非線性流水線的調度非線性流水線調度的任務是要找出一個最小的循環周期，按照這周期向流水線輸入新任務，流水線的各個功能段都不會發生沖突，而且流水線的吞吐率和效率最高。1.非

20、線性流水線的表示線性流水線能夠用流水線連接圖唯一表示對于非線形流水線，連接圖不能唯一表示工作流程，因此，引入流水線預約表。 非線性流水線的連接圖和預約表一張預約表可能與多個流水線連接圖相對應一個流水線連接圖對應與多張預約表2.非線性流水線的沖突 啟動距離：連續輸入兩個任務之間的時間間隔 流水線沖突：幾個任務爭用同一個流水段3.無沖突調度方法由E.S.Davidson及其學生于1971年提出禁止向量：預約表中每一行任意兩個“”之間距離的集合。下面預約表中為（3，4，6）沖突向量：C（CmCm-1C2C1） 其中：m是禁止向量中的最大值。 如果i在禁止向量中，則Ci1，否則Ci0。 上例中C(10

21、1100)例5.3：一條4功能段的非線性流水線，每個功能段的延遲時間都相等，它的預約表如下： (1)寫出流水線的禁止向量和初始沖突向量。 (2)畫出調度流水線的狀態圖。 (3)求最小啟動循環和最小平均啟動距離。 (4)求平均啟動距離最小的恒定循環。解：(1)禁止向量為：(2，4，6) 初始沖突向量：S = 101010(2)構造狀態圖 S邏輯右移2、4、6位時，不作任何處理， 邏輯右移1、3、5和大于等于7時： S右移1位之后：010101101010111111， S右移3位之后：000101101010101111， S右移5位之后：000001101010101011， S右移7位或大于

22、7位后：還原到它本身。101111右移5位之后：000001101010101011101011右移3位之后：000101101010101111101011右移5位之后：000001101010101011簡單循環：狀態圖中各種沖突向量只經過一次的啟動循環。(3)最小的啟動循環為（1，7）和（3，5）, 最小平均啟動距離為 4。(4)啟動距離最小的恒定循環為（5）4.優化調度方法L.E.Shar于1972年提出流水線最小平均啟動距離的限制范圍：(1)最小平均啟動距離的下限是預約表中任意一行里“”的最多個數。(2)最小平均啟動距離小于等于狀態圖中任意一個簡單循環的平均啟動距離。(3)最小平均啟

23、動距離的上限是沖突向量中1的個數再加上1。1992年，L.E.Shar又證明了上述限制范圍。其中最有用的是第1條。預約表中“”最多的行一定是瓶頸流水段對于例5.3的預約表，在同一行中“”最多的為2個，因此，最小平均距離可以達到2。最小啟動循環可以是(2)、(1,3)、(1,1,4)、(1,2,3)、。現取恒定循環(2)。每一行中與第1個“”的距離為2的倍數的位置都要預留出來。 S3行的第2個“”從周期5延遲到周期6。為此： S2行的第2個“”從周期6延遲到周期7； S1行的第2個“”從周期7延遲到周期8。實際上，只要在流水段S4的輸出端到流水段S3的輸入端中間插入一個非計算延遲D1。在非線性流

24、水線中，“”最多的流水段一定是“瓶頸“流水段。實現最優調度的目標是使“瓶頸”流水段處于忙碌狀態，沒有空閑周期。最優調度方法能夠使非線性流水線的吞吐率、加速比和效率達到最優。5.3 相關性分析技術5.3.1數據相關5.3.2控制相關5.3.3條件分支對流水線的影響5.3.4靜態分支預測技術5.3.5動態分支預測技術5.3.6提前形成條件碼5.3.7精確斷點與不精確斷點5.3.1 數據相關數據相關：在執行本條指令的過程中，如果用到的指令、操作數、變址量等是前面指令的執行結果，這種相關稱為數據相關。控制相關：由條件分支指令、轉子程序指令、中斷等引起的相關。解決數據相關的兩種方法：推后處理設置專用路徑

25、。1.指令相關發生指令相關的情況： n： STORE R1, n+1 n+1： 滿足關系：結果地址(n)指令地址(n+1)當第n條指令還沒有把執行結果寫到主存之前，取出的第n+1條指令顯然是錯誤的。在k個流水段的流水線處理機中，第n條指令要修改從第n+1到第n+ k 指令中的任意一條指令，都可能造成程序執行結果發生錯誤。在采用先行控制方式的處理機中，如果執行部件正在執行第n條指令，與下述情況之一發生相關，都可能造成程序執行結果發生錯誤：存放在先行操作棧中的指令正在指令分析器中分析的指令已經預取到先行指令緩沖棧中的指令指令執行結果還在后行緩沖棧中的指令更嚴重的是：有些分支指令，可能已經在指令分析

26、器中執行完成。 解決指令相關的根本辦法是： 在程序執行過程中不允許修改指令。現代程序設計方法要求程序具有再入性，可以被遞歸調用等，也要求不修改指令。在IBM370系列機中，用“執行指令”來解決：在程序執行過程中既能夠修改指令，程序又具有再入性。“執行指令”執行由第二地址(X2)+(B2)+D2)決定的主存數據區中的指令。2.主存操作數相關發生主存操作數相關的指令序列： n：OP A1，A2，A3 ；A1(A2) OP (A3) n+1：OP A1，A2，A3 ；A1(A2) OP (A3)出現下列情況之一，就發生主存操作數相關： A1（n） A2（n1） A1（n） A3（n1）解決辦法：運算

27、結果寫到通用寄存器，而不寫到主存對于訪問主存儲器的請求，寫結果的優先級高于讀操作數。3.通用寄存器數據相關發生寄存器數據相關的可能性很大，影響面也很大 n：OP R1，A2 ；R1(R1) OP (A2)n+1：OP R1，R2 ；R1(R1) OP (R2)發生R1(n)R1(n1)稱為R1數據相關。發生R1(n)R2(n1)稱為R2數據相關。解決通用寄存器數據相關的方法：方法一：把讀操作數、寫運算結果與指令執行合在一個節拍。從數據從通用寄存器讀出，在運算器中完成運算，結果寫回通用寄存器的整個回路中，只有通用寄存器是時序邏輯。當發生下述情況時，不能采用這種方法：當寄存器個數多時，讀寫寄存器的

28、時間長當功能部件數量多時，寄存器的讀寫端口多當功能部件的執行時間比較長，或要求指令的執行時間短時 方法二：建立相關專用通路(ByPass)由于發生寄存器數據相關的情況很普遍，一般計算機系統都采用專用數據通路。把讀通用寄存器、執行操作和寫結果分為3個周期，或2個周期。采用專用數據通路能夠縮短1至2個周期。變址相關：在采用變址尋址方式的處理機中，由于變址量放在寄存器中，因此，可能發生與通用寄存器數據相關類似變址相關4. LOAD相關LOAD操作的執行時間可能比較長 n：LOAD R1，A ；R1(A) n+1：ADD R1，R2 ；R1(R1) OP (R2)如果 R1(n)R2(n1)，或 R1

29、(n)R1(n1)，則發生LOAD數據相關。解決方法：方法一：由編譯器在LOAD之后插入不發生數據相關的指令，由于LOAD的執行時間不確定，不能根本解決問題方法二：由硬件自動插入空操作，直到LOAD操作完成在單條流水線處理機中，也可以停止節拍發生器，直到數據從存儲器中讀出為止。5.3.2控制相關因程序的執行方向可能被改變而引起的相關，也稱為全局相關。主要包括：無條件轉移、一般條件轉移、復合條件轉移、中斷等。1. 無條件轉移在流水線處理機中，無條件轉移指令不進入執行流水段，一般在指令譯碼階段就實際執行完成。如果在處理機中設置有指令先行緩沖棧，則要全部或部分作廢先行指令緩沖棧中的指令。如果轉移目標

30、指令L不在先行指令緩沖棧中，則要將先行指令緩沖棧中的所有指令全部作廢，并等待取出轉移目標指令L。如果轉移目標指令L在先行指令緩沖棧中，只要作廢先行指令緩沖棧中的部分指令。無條件轉移指令一般對指令執行部件的工作不會造成影響。為進一步減少無條件轉移指令造成的影響，在先行指令緩沖棧的入口處增設一個專門處理無條件轉移指令的指令分析器2.一般條件轉移 k： ;置條件碼CC k+1：JMP(CC) L ;如果CC為真轉向L L：當條件碼是上一條指令產生時，相關最嚴重無論轉移是否成功，條件轉移指令都在指令分析階段就已經執行完成。無論轉移成功或不成功，指令分析器要停頓一段時間，等待條件碼產生。如果轉移成功：指

31、令L已經在先行指令緩沖棧，指令分析器接著“分析L”，如果指令L不在先行指令緩沖棧，指令分析器要等待一個周期。轉移不成功，對程序執行影響不大，當轉移成功時，不僅指令執行過程變成完全串行，而且要作廢先行指令緩沖棧中的大量指令。在采用流水線方式的處理機中，要通過軟件與硬件的多種手段來盡可能地降低轉移成功的概率，減少轉移成功造成的影響。3.復合條件轉移 k：OP L ;產生條件碼，并決定是否轉向L L：如果轉移不成功：不造成任何影響，就象普通的運算型指令一樣如果轉移成功：造成的影響比一般條件轉移指令還要大得多。全部或部分作廢先行指令緩沖棧、先行操作棧、先行讀數棧和指令分析器中的指令。必須采取策略，減小

32、轉移成功造成的影響。5.3.3條件分支對流水線的影響處理好條件轉移和中斷的關鍵問題有兩個：要確保流水線能夠正常工作減少因“斷流”引起的吞吐率和效率的下降1.條件分支的處理方法條件轉移指令對流水線的影響很大，必須采取措施來減少這種影響。可能的措施有：(1)延遲轉移技術和指令取消技術只能用于單流水線處理機中，且流水線的級數不能太多；據統計，編譯器調度一條指令成功的概率在90以上，而調度兩條指令成功的概率只有40左右。當沒有合適的指令可調度時，編譯器只能插入空操作。(2)動態分支預測技術根據近期轉移是否成功的記錄來預測下一次轉移的方向。所有的動態轉移預測方法都能夠隨程序的執行過程動態地改變轉移的預測

33、方向。(3)靜態分支預測技術轉移預測的方向是確定的，或者預測轉移不成功，或者預測轉移成功。在程序實際執行過程中，轉移預測的方向不能改變。靜態轉移預測可以只用軟件實現，也可用硬件來實現，還可以在轉移的兩個方向上都預取指令。TI公司的SuperSPARC處理機采用了靜態轉移預測技術，而且設置有轉移目標緩沖棧，在兩個方向上都預取指令。2.條件分支在流水線中的執行過程因為第i條指令所需要的條件碼由第i-1條指令給出；在一條由k個功能段的流水線中，第i-1條指令要等到第i+k-2條指令進入流水線時才能形成條件碼。轉移不成功，猜測正確，流水線的吞吐率和效率沒有降低；轉移成功，猜測錯誤，要先作廢流水線中已經

34、執行的i+1、i+2、i+k-2指令；然后再從分支點開始執行第P、p+1、指令。一條k段流水線有k-2個功能段是浪費的。條件分支指令在流水線中的執行過程當分支的執行方向猜測錯誤時，可能造成程序執行結果發生錯誤。 例如，若第i+1條指令是：(R1)(R2)R1，寄存器R1中內容就被破壞，整個程序執行的結果是錯誤的。 目前的處理機有兩種做法：只進行指令譯碼和準備好運算所需要的操作數，在轉移條件沒有形成之前不執行運算；一直執行到運算完成，但不送回運算結果。3.條件分支對流水線性能的影響假設條件轉移指令在一般程序中所占的比例為p，轉移成功的概率為q。n條指令的總的執行時間是： TK-IF(n+k-1)

35、t + npq(k-1)t有條件轉移影響的流水線吞吐率為：有條件轉移影響的流水線最大吞吐率為：流水線吞吐率下降的百分比為：在典型程序中，轉移指令占的比例為p20，轉移成功的概率為60。對于一條8功能段的指令流水線，由于條件轉移指令的影響，流水線的最大吞吐率要下降：如果指令流水線的功能段數為10，由于條件轉移指令的影響，流水線的最大吞吐率將下 降一半以下：5.3.4靜態分支預測技術靜態分支預測： 在程序執行過程中轉移預測方向不能改變動態分支預測： 在程序執行過程中能夠改變轉移預測方向靜態預測技術有：1.軟件“猜測法”目標：通過編譯器盡量降低轉移成功的概率。例如：對于循環程序，普通編譯器生成的目標

36、代碼，轉移成功的概率很高，不成功的只有一次。這種編譯結果對流水線極為不利。軟件“猜測法”：通過編譯器降低轉移成功的概率2.硬件“猜測法”方法：通過改變硬件結構來降低轉移指令對流水線的影響在先行指令緩沖棧的入口處設置一個簡單的指令分析器，當檢測到轉移指令時，就把轉移目標地址L送入先行程序計數器PC1中，同時保留當前PC1中的內容到另一寄存器中。轉移成功，猜測正確。對轉移指令對流水線不造成影響。轉移不成功，用保存下來的地址恢復PC1和PC。軟硬件共同配合，都往同一個方向去猜測。3.兩個先行指令緩沖棧向前條件轉移，轉移成功與不成功各50%在先行指令緩沖棧中增加一個先行目標緩沖棧按照轉移成功的方向預取

37、指令到先行目標緩沖棧中。先行指令緩沖棧仍然按照轉移不成功的方向繼續預取指令。如果轉移不成功，則繼續分析原來先行指令緩沖棧中指令。如果轉移成功，則分析新增設的先行目標緩沖棧中的指令。5.3.5動態分支預測技術動態轉移預測技術的兩個關鍵問題：如何記錄轉移歷史信息如何根據記錄的轉移歷史信息預測轉移方向記錄轉移歷史信息的方法有三種：(1)最近一次或幾次轉移是否成功的信息記錄在轉移指令中(2)用一個高速緩沖棧保存條件轉移指令的轉移目標地址(3)用Cache保存轉移目標地址之后的n條指令1.在指令Cache中記錄轉移歷史信息在指令Cache中專門設置一個字段，稱為“轉移歷史表”。在執行轉移指令時，把轉移成

38、功或不成功的信息記錄在這個表中。當下次再執行到這條指令時，轉移預測邏輯根據“轉移歷史表”中記錄的信息預測轉移成功或不成功。只記錄最近一次轉移是否成功的歷史信息如果“轉移歷史表”中記錄的內容是“T”，則預測轉移成功，如果記錄的是“N”，則按照轉移不成功的方向繼續取指令。并用實際轉移是否成功的信息來修改“轉移歷史表”。 記錄最近兩次轉移是否成功的歷史信息圖中采用偏向成功的預測策略：只有歷史上最近兩次執行這條轉移指令時轉移都沒有成功，本次才預測轉移不成功也可以采用其他預測策略。實際上，“轉移歷史表”的修改規則和轉移預測規則可以多種多樣：只要記錄轉移預測是否成功的信息；并用最近預測是否成功的信息作為是

39、否轉移的依據。當“轉移歷史表”是空白時，可以有兩種做法：在“轉移歷史表”中預置轉移歷史信息。根據指令本身的偏移字段的符號來預測轉移的方向。如果偏移字段為負，則預測轉移成功，否則預測轉移不成功主要優點：不必專門設置轉移緩沖棧，所記錄的轉移歷史信息比較少。例如：DEC公司的Alpha 21064處理機就采用了這種轉移預測方法，在它的一級指令Cache中有一個專門的“轉移歷史表”字段。Alpha 21064的結構框圖：2.設置轉移目標地址緩沖棧用高速緩沖棧保存最近k條轉移指令的“轉移歷史表”和轉移目標地址當前指令地址與轉移目標緩沖棧中的所有轉移指令地址進行比較；如果發現有相等的，則根據所記錄的歷史信

40、息預測本次轉移方向。根據某種規則修改“轉移歷史表”。3.設置轉移目標指令緩沖棧把上面方法中的“轉移目標地址”字段改為存放轉移目標地址之后的n條指令。預測轉移方向的規則和修改“轉移歷史表”的規則與上面的方法相同。5.3.6提前形成條件碼必要性：對提高流水線的性能非常有效可能性：可在運算開始或中間產生條件碼對于乘除法，兩個源操作數的符號相同結果為正，符號相反結果為負對于乘法，有一個操作數為0，則乘積為0被除數為0，商為0； 除數為0，除法結果溢出同號加或異號減，結果符號與第一操作數相同異號加或同號減，結果的符號與絕對值大的操作數相同溢出及是否為0可以通過一個比較器提前產生只要在一個時鐘周期之內產生

41、條件碼，流水線就不會“斷流”。如Amdahl470V/6在運算部件的入口處設置有一個LOCK部件，提前形成條件碼把產生條件碼與使用條件碼的指令分開 LOAD R1,NUM ;循環次數初值裝入R1 LOOP： ;循體開始 DEC R1 ;循環次數減“1” BNE LOOP ;測試循環是否則結束 HALT ;程序結束 NUM: n可以編譯成如下程序： LOAD R1,NUM ;循環次數裝入R1中 LOOP：LDEC R1 ;一條專用的 ;循環次數減1指令 ;循體開始 LBNE LOOP ;一條專用的測試循環 ;是否結束的指令 HALT ;程序結束 NUM: n ;循環次數指令LDEC和LBNE使用

42、專用的條件碼寄存器5.3.7 精確斷點與不精確斷點產生中斷時，流水線中有多條指令，斷點究竟在哪條指令？對于輸入輸出設備的中斷服務，實際上不需要有精確斷點。比較簡單的處理方法是：讓已經進入流水線的所有指令都執行完成，斷點就是最后進入流水線的那條指令的地址。對于程序性錯誤和機器故障等引起的中斷，它們出現的概率很低，處理原則：不在于縮短時間，關鍵是要正確保存現場和正確恢復斷點。不精確斷點(Imprecise)，流水線可以不斷流需要的硬件比較少，控制邏輯比較簡單中斷響應時間加長采用不精確斷點法可能會發生如下兩個問題：(1)程序的調試困難：設置斷點早期的流水線處理機，多采用不精確斷點法近期的流水線處理機

43、一般都采用精確斷點法(2)程序執行的結果可能出錯，例如： i：FADD R1, R2 ；(R1)(R2)R1 i+1：FMUL R3, R1 ；(R3)(R1)R3當第i條指令執行到S6段時發現浮點加法結果溢出，于是發出中斷服務申請。由于采用不精確斷點法，已經進入流水線的第i+1條指令將執行完成；因為第i+1條指令使用了不正確的R1，所以浮點乘法的執行結果是不正確的。采用精確斷(Precise)點法，要設置一定數量的后援寄存器，把整個流水線中所有指令的執行結果和現場都保存下來。5.4 動態調度技術5.4.1順序流動與亂序流動5.4.2亂序流動中的數據相關5.4.3數據重定向方法5.4.4Tom

44、asulo動態調度算法實現方法： 由硬件動態調整指令執行順序，以減少數據相關造成的影響。主要優點：能夠處理在編譯時無法確定的相關，并簡化編譯器設計在其他流水線機器上編譯的目標代碼也能夠高效運行用靜態調度法生成的代碼也能在動態調度法的機器中運行主要缺點：指令級并行度低，因為只能在比較小的范圍內尋找并行性5.4.1順序流動與亂序流動1.順序流動方式：任務按順序流入流水線,也按順序流出流水線把如下一段程序輸入到這條流水線中： k： R0（R1） k+1： k+2：R2（R0）（R3） k+3： k+4： k+5： 指令k+2無法繼續執行，要在功能段S2中等待。后續的指令k+4、k+5、等也不能進入流

45、水線。功能段S3、S4、S5將逐漸空閑。缺點：吞吐率和效率降低優點：流水線的控制邏輯比較簡單流水線“斷流”，有些功能段“空閑”2.亂序(Out of order)流動方式：指令流出流水線的順序與流入流水線的順序不同。又稱為錯序流動方式、無序流動方式、異步流動方式等。5.4.2亂序流動中的數據相關在亂序流動方式中，可能發生三種數據相關 寫寫相關 k：LOAD F1, A ;F1（A） 寫讀相關 k+1：FADD F2, F1 ;F2（F2）+（F1） k+2：FMUL F1, F3 ;F1（F1）（F3） k+3：STORE F1, B ;B（F1） 讀寫相關(1)寫讀相關：指令k與指令k+1之

46、間關于F1的相關，又稱為數據相關、先寫后讀相關、流相關、WR相關、RAW相關等。(2)讀寫相關：指令k+1與指令k+2之間關于F1的相關，變量名相關、先讀后寫相關、反相關、RW相關、WAR相關等。(3)寫寫相關：指令k與指令k+2左邊的F1之間的相關關系稱為：輸出相關、寫寫相關、WW相關、WAW相關或寫后再寫相關等。有時把相關稱為“冒險”(hazard)、“竟爭” (competition)等。在程序執行過程中，只有避免相關，執行結果才能是正確的。三種數據相關可以用下列關系式來表示： 對于寫讀相關 D(i)S(j) 對于讀寫相關 S(i)D(j) 對于寫寫相關 D(i)D(j)5.4.3數據重

47、定向方法1.三種數據相關的重定向 重定向之前，j只能在i之后執行。 重定向之后，可以做到：(1)寫讀相關，j與i可以同時執行 即專用數據通路(2)寫寫相關，先后順序無關(3)讀寫相關，先后順序無關 后兩種情況又稱為“變量換名技術”2.變量換名技術用來自動消除讀寫數據相關和寫寫數據相關規則：一個變量只允許定值一次在三種數據相關中，實際上只有寫讀數據相關必須依靠硬件、或采用軟硬件結合的方法來解決：推后處理或專用數據通路在上面的數據重定向圖中，把B換成了B，并在以后的都引用B，讀寫數據相關和寫寫數據相關就不存在了。一個實際例子：Loop: LD F0, 0(R1) ADD F0, F2 SD 0(R

48、1), F0 LD F0, -8(R1) ADD F0, F2 SD -8(R1), F0 LD F0, -16(R1) ADD F0, F2 SD -16(R1), F0 LD F0, -24(R1) ADD F0, F2 SD -24(R1), F0 SUBI R1, R1, #32 BNEZ R1, LoopLoop: LD F0, 0(R1) LD F4, -8(R1) LD F6, -16(R1) LD F8, -24(R1) ADD F0，F2 ADD F4，F2 ADD F6，F2 ADD F8，F2 SD 0(R1), F0 SD -8(R1), F4 SUBI R1, R1,

49、 #32 SD -16(R1), F6 BNEZ R1, Loop SD -24(R1), F83.一個簡單的程序： k： LOAD F1, A k+1： FADD F1, F2 k+2： FMUL F1, F3 k+3： STORE F1, B專門設置：AFADD、FMULB、FADDFMUL三條專用路徑。撤消：F1FADD、F1FMUL、FADDF1 、AF1的路徑。5.4.4Tomasulo動態調度算法實用的動態調度算法主要有兩種:(1)集中控制：CDC計分牌(scorebord)算法， 最先在CDC 6600大型機中采用。(2)分散控制：Tomasulo算法, 公共數據總線法，令牌法等

50、。最早在大型機IBM 360/91的浮點處理部件中被采用。以上面的一段程序為例說明Tomasulo算法k： LOAD F1,Ak+1： FADD F1,F2k+2： FMUL F1,F3k+3： STORE F1,B5.5 超標量處理機5.5.1 基本結構5.5.2 單發射與多發射5.5.3 多流水線調度5.5.4 資源沖突5.5.5 超標量處理機性能三種主流處理機： 超標量處理機 超流水線處理機 超標量超流水線處理機5.5.1 基本結構普通標量流水線處理機： 一條指令流水線，一個多功能操作部件， 每個時鐘周期平均執行指令的條數小于1。多操作部件標量處理機： 一條指令流水線，多個獨立的操作部件

51、， 指令級并行度小于1。超標量處理機典型結構： 多條并行工作的指令流水線，多個獨立的操作部件， 指令級并行度（ILP）大于1。Motorola公司的MC8811010個操作部件兩個寄存器堆： 整數部件通用寄存器堆，32個32位寄存器 浮點部件擴展寄存器堆，32個80位寄存器緩沖深度為4的先行讀數棧緩沖深度為3的后行寫數棧兩個獨立的高速Cache中，各為8KB，采用兩路組相聯方式轉移目標指令Cache，用于存放另一條分支上的指令5.5.2單發射與多發射1.單發射處理機：每個周期只取一條指令、只譯碼一條指令，只執行一條指令，只寫回一個運算結果。取指令部件和指令譯碼部件各設置一套；只設置一個多功能操

52、作部件或設置多個獨立的操作部件；操作部件中可以采用流水線結構，也可以不采用流水線結構。目標是每個時鐘周期平均執行一條指令，ILP的期望值為1。2.多發射處理機：每個周期同時取多條指令、同時譯碼多條指令，同時執行多條指令，同時寫回多個運算結果。多個取指令部件，多個指令譯碼部件和多個寫結果部件。設置多個指令執行部件，有些指令執行部件采用流水線結構。目標是每個時鐘周期平均執行多條指令，ILP的期望值大于1。3.超標量處理機：有兩條或兩條以上能同時工作的指令流水線先行指令窗口：能夠從指令Cache中預取多條指令，能夠對窗口內的指令進行數據相關性分析和功能部件沖突檢測。例如：Intel公司的i860、i

53、960、Pentium，Motolora公司的MC88110，IBM公司的Power 6000,TI公司生產SuperSPARC等操作部件的個數一般多于每個周期發射的指令條數。通常為4個至16個操作部件。超標量處理機的指令級并行度：1ILPm5.5.3多流水線調度順序發射(in-order issue)與亂序發射(out-order issue)：指令發射順序是按照程序中指令排列順序進行的稱為順序發射順序完成(in-order completion)與亂序完成(out-order completion)：指令完成順序是按照程序中指令排列順序進行的稱為順序完成多流水線調度的三種方法：順序發射順序

54、完成（Pentium）順序發射亂序完成（Pentium II/III）亂序發射亂序完成無論那種調度策略，都要保證程序運行的最終結果是正確的，發射策略由譯碼控制器完成，完成策略由執行控制器完成。以下列程序為例，說明這三種不同的調度方法： I1：LOAD R1, A ；R1(A) I2：FADD R2, R1 ；R2(R2)(R1) I3：FMUL R3, R4 ；R3(R3)(R4) I4：FADD R4, R5 ；R4(R4)(R5) I5：DEC R6 ；R6(R6)1 I6：FMUL R6, R7 ；R6(R6)(R7)6條指令中有4個數據相關：2個寫讀相關，1個讀寫相關和1個寫寫相關。1

55、.順序發射順序完成共用10個時鐘周期完成，還有8個空閑的時鐘周期2.順序發射亂序完成總執行時間為9個時鐘周期，節省了一個時鐘周期。只有3個空閑時鐘周期，少了5個空閑時鐘周期。3.亂序發射亂序完成總執行時間為8個時鐘周期，節省2個周期。沒有空閑周期，功能部件得到充分利用。5.5.4資源沖突如果操作部件采用流水線結構，發生資源沖突的可能性很小；如果不采用流水線結構，發生資源沖突的可能性就比較大。一個由4條指令組成的程序例子： I1：FADD R0, R1 ；R0(R0)(R1) I2：FMUL R2, R3 ；R2(R2)(R3) I3：FADD R4, R5 ；R4(R4)(R5) I4：FMU

56、L R6, R7 ；R6(R6)(R7)操作部件不采用流水線：執行完4條指令總共用了11個周期，有5個空閑周期。操作部件采用流水線：執行完4條指令共用8個周期，少用3個周期。操作部件采用流水線結構的原因分析假每個周期發射m條指令，操作部件的延遲時間為k個周期：如果操作部件不采用流水線結構，則使用同一個操作部件的兩條指令應該至少相差mk如果操作部件采用k段流水線結構，則使用同一個操作部件的兩條指令只需相差m或m以上指令流水線的段數k一般在4至10之間，每個時鐘周期發射的指令條數m在2至4之間。例如，取中間值，k7，m3為了不發生資源沖突，如果操作部件不采用流水線結構，兩條使用同一個功能部件的指令

57、序號必須相差21或21以上。如果操作部件采用流水線結構，兩條使用同一個功能部件的指令序號只需要相差3或3以上。因此，在超標量處理機中，操作部件一般要采用流水線結構。如果由于某種原因，操作部件不能采用流水線結構，則必須設置多個相同種類的操作部件普通標量處理機，希望相同操作連續出現： 只有連續出現相同操作的指令序列時，流水線的效率才能得到充分發揮。超標量處理機正好相反，希望相同操作不要連續出現：相同操作的指令序列連續出現時，會發生資源沖突。因此，要求相同操作的指令能夠相對均勻地分布在程序中。超標量處理機的這種要求正好符合一般標量程序的特點。5.5.5 超標量處理機性能單流水線普通標量處理機的指令級

58、并行度記作(1,1)，超標量處理機的指令級并行度記作(m,1)，超流水線處理機的指令級并行度記作(1,n)，超標量超流水線處理機的指令級并行度記作(m, n)。在理想情況下，N條指令在單流水線標量處理機上的執行時間為： T(1, 1)(kN1)t在每個周期發射m條指令的超標量處理機上執行的時間為： 超標量處理機相對于單流水線標量處理機的加速比為：超標量處理機的加速比的最大值為：S(m,1)MAXm5.6 超流水線處理機5.6.1指令執行時序5.6.2典型處理機結構5.6.3超流水線處理機性能超流水線處理機的兩種定義：在一個周期內分時發射多條指令的處理機指令流水線的段數大于等于8的流水線處理機（超級流水線）提高處理機性能的兩種方法：資源重復：通過增加硬件資源來提高處理機性能時間重疊：通過各部分硬件的重疊工作來提高處理機性能兩種不同并行性：空間并行性：超標量處理機采用的方法時間并行性：超流水線處理機采用的方法5.6.1 指令執行