第5章 華東理工大學計算機系統(tǒng)結構 計141阿金

第5章標量處理機5.1先行控制技術5.2流水線技術5.3相關性分析技術5.4超標量處理機5.5超流水線處理機5.6超標量超流水線處理機5.1先行控制技術5.1.1指令的重疊執(zhí)行方式5.1.2先行控制方式的原理5.1.3處理機結構5.1.4指令執(zhí)行序列5.1.5先行緩沖棧5.1.6緩沖深度的設計方法5.1.1指令的重疊執(zhí)行方式1.順序執(zhí)行方式執(zhí)行n條指令所用的時間為：如果每段時間都為t，則執(zhí)行n條指令所用的時間為：T＝3nt主要優(yōu)點：控制簡單，節(jié)省設備主要缺點：速度慢，功能部件的利用率低2.一次重疊執(zhí)行方式如果兩個過程的時間相等，則執(zhí)行n條指令的時間為：T＝(1+2n)t主要優(yōu)點：

指令的執(zhí)行時間縮短，功能部件的利用率明顯提高。主要缺點：

需要增加一些硬件，控制過程稍復雜。3.二次重疊執(zhí)行方式如果三個過程的時間相等，執(zhí)行n條指令的時間為：T＝(2＋n）t在理想情況下，處理機中同時有三條指令在執(zhí)行。處理機的結構要作比較大的改變，需要采用先行控制技術。

5.1.2先行控制方式的原理1.采用二次重疊執(zhí)行方式必須解決兩個問題：(1)有獨立的取指令部件、指令分析部件和指令執(zhí)行部件把一個集中的指令控制器，分解成三個獨立的控制器：存儲控制器、指令控制器、運算控制器(2)要解決訪問主存儲器的沖突問題取指令、分析指令、執(zhí)行指令都可能要訪問存儲器2.解決訪存沖突的方法：(1)采用低位交叉存取方式：這種方法不能根本解決沖突問題。 指令、讀操作數(shù)、寫結果。(2)兩個獨立的存儲器：獨立的指令存儲器和數(shù)據(jù)存儲器。如果再規(guī)定，執(zhí)行指令所需要的操作數(shù)和執(zhí)行結果只寫到通用寄存器，則取指令、分析指令和執(zhí)行指令就可以同時進行。在許多高性能處理機中，有獨立的指令Cache和數(shù)據(jù)Cache。這種結構被稱為哈佛結構。(3)采用先行控制技術

采用先行控制技術的關鍵是緩沖技術和預處理技術。緩沖技術通常用在工作速度不固定的兩個功能部件之間。設置緩沖棧的目的是用來以平滑功能部件之間的工作速度。在采用了緩沖技術和預處理技術之后，運算器能夠專心于數(shù)據(jù)的運算，從而大幅度提高程序的執(zhí)行速度。5.1.3處理機結構1.三個獨立的控制器：存儲控制器、指令控制器、運算控制器。2.四個緩沖棧：先行指令緩沖棧、先行讀數(shù)緩沖棧、先行操作棧、后行寫數(shù)棧。3.處理機組成4.先行指令緩沖棧的組成作用：只要指令緩沖棧沒有充滿，就自動發(fā)出取指令的請求。設置兩個程序計數(shù)器：先行程序計數(shù)器PC1，用來指示取指令，現(xiàn)行程序計數(shù)器PC，記錄指令分析器正在分析的指令地址。5.存在的主要問題：各類指令“分析”和“執(zhí)行”的時間相差很大數(shù)據(jù)相關轉移或轉子程序指令

先行緩沖站的組成5.1.4指令執(zhí)行時序設置了指令緩沖棧，取指令的時間就可以忽略不計。一條指令的執(zhí)行可分為2個過程1.分析指令和執(zhí)行指令時間不相等時的情況2.采用先行緩沖棧的指令執(zhí)行過程先行讀數(shù)棧,先行操作棧,后行寫數(shù)棧。理想情況下，指令執(zhí)行部件應該一直忙碌。連續(xù)執(zhí)行n條指令的時間為：

空間并行性：設置多個獨立的操作部件時間并行性：分時使用同一個部件的不同部分

5.2.1流水線工作原理

5.2.2流水線的分類

5.2.3線性流水線的性能分析

5.2.4非線性流水線的調度5.2流水線技術5.2.1流水線工作原理1.流水寄存器流水線的每一個階段稱為流水步、流水步驟、流水段、流水線階段、流水功能段、功能段、流水級、流水節(jié)拍等。在每一個流水段的末尾或開頭必須設置一個寄存器，稱為流水寄存器、流水鎖存器、流水閘門寄存器等。加入流水寄存器，會增加指令的執(zhí)行時間。在一般流水線時空圖中不畫出流水寄存器。2.一種指令流水線一般4至12個流水段，≥8個流水段的稱為超流水線處理機3.流水線時空圖

一個浮點加法器流水線的時空圖4.流水線的主要特點只有連續(xù)提供同類任務才能發(fā)揮流水線效率盡量減少因條件分支造成的“斷流”通過編譯技術提供連續(xù)的相同類型操作每個流水線段都要設置一個流水寄存器時間開銷：流水線的執(zhí)行時間加長是流水線中需要增加的主要硬件各流水段的時間應盡量相等流水線處理機的基本時鐘周期等于時間最長的流水段的時間長度。流水線需要有“裝入時間”和“排空時間”

5.2.2流水線的分類1.線性流水線與非線性流水線流水線的各個流水段之間是否有反饋信號線性流水線（LinearPipelining）：每一個流水段都流過一次，而且僅流過一次非線性流水線（NonlinearPipelining）：某些流水段之間有反饋回路或前饋回路。線性流水線能夠用流水線連接圖唯一表示非線性流水線必須用流水線連接圖和流水線預約表共同表示2.按照流水線的級別來分

處理機級流水線，又稱為指令流水線。例如：在采用先行控制器的處理機中，各功能部件之間的流水線

部件級流水線(操作流水線)

如浮點加法器流水線宏流水線(MacroPipelining)

處理機之間的流水線稱，每個處理機對同一個數(shù)據(jù)流的不同部分分別進行處理。3.單功能流水線與多功能流水線單功能流水線：只能完成一種固定功能的流水線。

Cray-1計算機種有12條，YH-1計算機有18條

Pentium有一條5段定點和一條8段浮點流水線。

PentiumⅢ有兩條定點和一條浮點指令流水線。多功能流水線：

流水線的各段通過不同連接實現(xiàn)不同功能

Texas公司的ASC機，8段流水線，能夠實現(xiàn)：定點加減法、定點乘法、浮點加法、浮點乘法、邏輯運算、移位操作、數(shù)據(jù)轉換等。4.靜態(tài)流水線與動態(tài)流水線靜態(tài)流水線：同一段時間內，各個功能段只能按照一種方式連接，實現(xiàn)一種固定的功能。動態(tài)流水線：在同一段時間內，各段可以按照不同的方式連接，同時執(zhí)行多種功能。5.流水線的其他分類方法按照數(shù)據(jù)表示方式：標量流水線和向量流水線按照控制方式：同步流水線和異步流水線順序流水線與亂序流水線，亂序流水線又稱為無序流水線、錯序流水線或異步流水線等。5.2.3線性流水線的性能分析

主要指標：吞吐率、加速比和效率1.吞吐率（ThoughPut）流水線吞吐率的最基本公式：

其中：n為任務數(shù)，Ｔk為完成n個任務所用的時間。各段執(zhí)行時間相等，輸入連續(xù)任務情況下，完成n個任務需要的總時間為：

Tk＝(k＋n－1)t

其中：k

為流水線的段數(shù)，t為時鐘周期。

Tk=k?Δt+(n-1)Δt=(k+n-1)t

吞吐率為：最大吞吐率為：

各段時間不等，完成n個連續(xù)任務：吞吐率：最大吞吐率：流水線各段執(zhí)行時間不相等的解決辦法(1)將“瓶頸”部分再細分（如果可分的話）2.加速比（Speedup）計算加速比的基本公式：各段執(zhí)行時間相等，輸入連續(xù)任務情況下,

加速比：最大加速比：各段時間不等，輸入連續(xù)任務情況下,實際加速比為：

當流水線段數(shù)增加時，需要連續(xù)輸入的任務數(shù)也必須增加3.效率（Efficiency）計算流水線效率的一般公式：各流水段時間相等，輸入n個連續(xù)任務，流水線的效率為：最高效率為：各流水段時間不等，輸入n個連續(xù)任務，流水線效率為：

各段設備量或價格不等時，流水線的效率為：即：其中，ai＜k，且＝k。流水線的吞吐率、加速比與效率的關系：因為：因此：E＝TP·t，S＝k·E4.流水線最佳段數(shù)的選擇采用順序執(zhí)行方式完成一個任務的時間為t在同等速度的k段流水線上執(zhí)行一個任務的時間為：t／k＋d(d為流水鎖存器的延遲時間)流水線的最大吞吐率為：P=1／(t／k＋d)流水線的總價格估計為：C＝a＋bk，其中：a為功能段身的總價格，

b為每個鎖存器的價格

A.G.Larson把流水線的性能價格比PCR定義為：

求PCR的最大值為：5.流水線性能分析舉例對于單功能線性流水線，輸入連續(xù)任務的情況，通過上面給出的公式很容易計算出流水線的吞吐率、加速比和效率。對于輸入不連續(xù)任務，或多功能流水線，通常采用基本公式計算。例5.2：

用一條4段浮點加法器流水線求8個浮點數(shù)的和：Z＝A＋B＋C＋D＋E＋F＋G＋H解：

Z＝[(A＋B)＋(C＋D)]＋[(E＋F)＋(G＋H)]解：5.2.4非線性流水線的調度非線性流水線調度的任務是要找出一個最小的循環(huán)周期，按照這周期向流水線輸入新任務，流水線的各個功能段都不會發(fā)生沖突，而且流水線的吞吐率和效率最高。1.非線性流水線的表示線性流水線能夠用流水線連接圖唯一表示對于非線形流水線，連接圖不能唯一表示工作流程，因此，引入流水線預約表例如：

非線形流水線的連接圖和預約表

一張預約表可能與多個流水線連接圖相對應

一個流水線連接圖對應與多張預約表2.非線性流水線的沖突啟動距離：連續(xù)輸入兩個任務之間的時間間隔流水線沖突：幾個任務爭用同一個流水段3.無沖突調度方法由E.S.Davidson及其學生于1971年提出禁止向量：預約表中每一行任意兩個“×”之間距離的集合。上例中為（3，4，6）沖突向量：C＝（CmCm-1…C2C1）其中：m是禁止向量中的最大值。如果i在禁止向量中，則Ci＝1，否則Ci＝0。上例中C＝(101100)例5.3：一條4功能段的非線性流水線，每個功能段的延遲時間都相等，它的預約表如下：

(1)寫出流水線的禁止向量和初始沖突向量。

(2)畫出調度流水線的狀態(tài)圖。

(3)求最小啟動循環(huán)和最小平均啟動距離。

(4)求平均啟動距離最小的恒定循環(huán)。解：(1)禁止向量為：(2，4，6)

初始沖突向量：S=101010(2)構造狀態(tài)圖

S邏輯右移2、4、6位時，不作任何處理，邏輯右移1、3、5和大于等于7時：

S右移1位之后：010101∨101010＝111111，

S右移3位之后：000101∨101010＝101111，

S右移5位之后：000001∨101010＝101011，

S右移7位或大于7位后：還原到它本身。101111右移5位之后：000001∨101010＝101011，101011右移3位之后：000101∨101010＝101111，101011右移5位之后：000001∨101010＝101011。簡單循環(huán)：狀態(tài)圖中各種沖突向量只經(jīng)過一次的啟動循環(huán)。(3)最小的啟動循環(huán)為（1，7）和（3，5）,

平均啟動距離為4。(4)啟動距離最小的恒定循環(huán)為（5）4.優(yōu)化調度方法L.E.Shar于1972年提出流水線最小平均啟動距離的限制范圍：

(1)最小平均啟動距離的下限是預約表中任意一行里“×”的最多個數(shù)。

(2)最小平均啟動距離小于等于狀態(tài)圖中任意一個簡單循環(huán)的平均啟動距離。

(3)最小平均啟動距離的上限是沖突向量中1的個數(shù)再加上1。1992年，L.E.Shar又證明了上述限制范圍。最有用的是第1條。預約表中“×”最多的行一定是瓶頸流水段對于例5.3的預約表，在同一行中“×”最多的為2個，因此，最小平均距離可以達到2。最小啟動循環(huán)可以是(2)、(1,3)、(1,1,4)、(1,2,3)、……。現(xiàn)取恒定循環(huán)(2)。每一行中與第1個“×”的距離為2的倍數(shù)的位置都要預留出來。

S3行的第2個“×”從周期5延遲到周期6。為此，

S2行的第2個“×”從周期6延遲到周期7；

S1行的第2個“×”從周期7延遲到周期8。實際上，只要在流水段S4的輸出端到流水段S3的輸入端中間插入一個非計算延遲D1。在非線性流水線中，“×”最多的流水段一定是“瓶頸“流水段。實現(xiàn)最優(yōu)調度的目標是使“瓶頸”流水段處于忙碌狀態(tài)，沒有空閑周期。最優(yōu)調度方法能夠使非線性流水線的吞吐率、加速比和效率達到最優(yōu)。5.3相關性分析技術5.3.1數(shù)據(jù)相關5.3.2控制相關5.3.3條件分支對流水線的影響5.3.4靜態(tài)分支預測技術5.3.5動態(tài)分支預測技術5.3.1數(shù)據(jù)相關數(shù)據(jù)相關：在執(zhí)行本條指令的過程中，如果用到的指令、操作數(shù)、變址量等是前面指令的執(zhí)行結果，這種相關稱為數(shù)據(jù)相關。控制相關：由條件分支指令、轉子程序指令、中斷等引起的相關。解決數(shù)據(jù)相關的方法有兩種：推后處理設置專用路徑。1.指令相關發(fā)生指令相關的情況：

n：STORER1,n+1n+1：……

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

解決指令相關的根本辦法是：

在程序執(zhí)行過程中不允許修改指令?，F(xiàn)代程序設計方法要求程序具有再入性，可以被遞歸調用等，也要求不修改指令。在IBM370系列機中，用“執(zhí)行指令”來解決：在程序執(zhí)行過程中既能夠修改指令，程序又具有再入性?！皥?zhí)行指令”執(zhí)行由第二地址((X2)+(B2)+D2)決定的主存數(shù)據(jù)區(qū)中的指令。2.主存操作數(shù)相關發(fā)生主存操作數(shù)相關的指令序列：

n：OPA1，A2，A3

；A1＝(A2)OP(A3)n+1：OPA1，A2，A3

；A1＝(A2)OP(A3)出現(xiàn)下列情況之一，就發(fā)生主存操作數(shù)相關：

A1（n）＝A2（n＋1）

A1（n）＝A3（n＋1）解決辦法：運算結果寫到通用寄存器，而不寫到主存對于訪問主存儲器的請求，寫結果的優(yōu)先級高于讀操作數(shù)。3.通用寄存器數(shù)據(jù)相關發(fā)生寄存器數(shù)據(jù)相關的可能性很大，影響面也很大

n：OPR1，A2

；R1＝(R1)OP(A2)n+1：OPR1，R2

；R1＝(R1)OP(R2)發(fā)生R1(n)＝R1(n＋1)稱為R1數(shù)據(jù)相關。發(fā)生R1(n)＝R2(n＋1)稱為R2數(shù)據(jù)相關。

解決通用寄存器數(shù)據(jù)相關的方法：方法一：把讀操作數(shù)、寫運算結果與指令執(zhí)行合在一個節(jié)拍。從數(shù)據(jù)從通用寄存器讀出，在運算器中完成運算，結果寫回通用寄存器的整個回路中，只有通用寄存器是時序邏輯。當發(fā)生下述情況時，不能采用這種方法：當寄存器個數(shù)多時，讀寫寄存器的時間長當功能部件數(shù)量多時，寄存器的讀寫端口多當功能部件的執(zhí)行時間比較長，或要求指令的執(zhí)行時間短時方法二：建立相關專用通路(ByPass)由于發(fā)生寄存器數(shù)據(jù)相關的情況很普遍，一般計算機系統(tǒng)都采用專用數(shù)據(jù)通路。把讀通用寄存器、執(zhí)行操作和寫結果分為3個周期，或2個周期。采用專用數(shù)據(jù)通路能夠縮短1至2個周期。變址相關：在采用變址尋址方式的處理機中，由于變址量放在寄存器中，因此，可能發(fā)生與通用寄存器數(shù)據(jù)相關類似變址相關4.LOAD相關

LOAD操作的執(zhí)行時間可能比較長

n：LOADR1，A；R1＝(A)n+1：ADDR1，R2

；R1＝(R1)OP(R2)

如果R1(n)＝R2(n＋1)，或R1(n)＝R1(n＋1)，則發(fā)生LOAD數(shù)據(jù)相關。解決方法：方法一：由編譯器在LOAD之后插入不發(fā)生數(shù)據(jù)相關的指令，由于LOAD的執(zhí)行時間不確定，不能根本解決問題方法二：由硬件自動插入空操作，直到LOAD操作完成在單條流水線處理機中，也可以停止節(jié)拍發(fā)生器，直到數(shù)據(jù)從存儲器中讀出為止。5.3.2控制相關因程序的執(zhí)行方向可能被改變而引起的相關，也稱為全局相關。主要包括：無條件轉移、一般條件轉移、復合條件轉移、中斷等。1.無條件轉移在流水線處理機中，無條件轉移指令不進入執(zhí)行流水段，一般在指令譯碼階段就實際執(zhí)行完成。如果在處理機中設置有指令先行緩沖棧，則要全部或部分作廢先行指令緩沖棧中的指令。如果轉移目標指令L不在先行指令緩沖棧中，則要將先行指令緩沖棧中的所有指令全部作廢，并等待取出轉移目標指令L。如果轉移目標指令L在先行指令緩沖棧中，只要作廢先行指令緩沖棧中的部分指令。無條件轉移指令一般對指令執(zhí)行部件的工作不會造成影響。為進一步減少無條件轉移指令造成的影響，在先行指令緩沖棧的入口處增設一個專門處理無條件轉移指令的指令分析器2.一般條件轉移

k：……;置條件碼CCk+1：JMP(CC)L;如果CC為真轉向L

……L：……

當條件碼是上一條指令產(chǎn)生時，相關最嚴重無論轉移是否成功，條轉移指令都在指令分析階段就已經(jīng)執(zhí)行完成。無論轉移不成功或不成功，指令分析器要停頓一段時間，等待條件碼產(chǎn)生。如果轉移成功：指令L已經(jīng)在先行指令緩沖棧，指令分析器接著“分析L”，如果指令L不在先行指令緩沖棧，指令分析器要等待一個周期。轉移不成功，對程序執(zhí)行影響不大，當轉移成功時，不僅指令執(zhí)行過程變成完全串行，而且要作廢先行指令緩沖棧中的大量指令。在采用流水線方式的處理機中，要通過軟件與硬件的多種手段來近可能地降低轉移成功的概率，減少轉移成功造成的影響。3.復合條件轉移

k：OPL;產(chǎn)生條件碼，并決定是否轉向L

……L：……如果轉移不成功：不造成任何影響，就象普通的運算型指令一樣如果轉移成功：造成的影響比一般條件轉移指令還要大得多。全部或部分作廢先行指令緩沖棧、先行操作棧、先行讀數(shù)棧和指令分析器中的指令。必須采取策略，減小轉移成功造成的影響。5.3.3條件分支對流水線的影響處理好條件轉移和中斷的關鍵問題有兩個：要確保流水線能夠正常工作減少因“斷流”引起的吞吐率和效率的下降1.條件分支的處理方法條件轉移指令對流水線的影響很大，必須采取措施來減少這種影響?？赡艿拇胧┯校?1)延遲轉移技術和指令取消技術只能用于單流水線處理機中，且流水線的級數(shù)不能太多；據(jù)統(tǒng)計，編譯器調度一條指令成功的概率在90％以上，而調度兩條指令成功的概率只有40％左右。當沒有合適的指令可調度時，編譯器只能插入空操作。(2)動態(tài)分支預測技術根據(jù)近期轉移是否成功的記錄來預測下一次轉移的方向。所有的動態(tài)轉移預測方法都能夠隨程序的執(zhí)行過程動態(tài)地改變轉移的預測方向。(2)靜態(tài)分支預測技術轉移預測的方向是確定的，或者預測轉移不成功，或者預測轉移成功，在程序實際執(zhí)行過程中，轉移預測的方向不能改變。靜態(tài)轉移預測可以只用軟件實現(xiàn)，也可用硬件來實現(xiàn)，還可以在轉移的兩個方向上都預取指令。TI公司的SuperSPARC處理機采用了靜態(tài)轉移預測技術，而且設置有轉移目標緩沖棧，在兩個方向上都預取指令。2.條件分支在流水線中的執(zhí)行過程因為第i條指令所需要的條件碼由第i-1條指令給出；在一條由k個功能段的流水線中，第i-1條指令要等到第i+k-2條指令進入流水線時才能形成條件碼。轉移不成功，猜測正確，流水線的吞吐率和效率沒有降低，轉移成功，猜測錯誤，要先作廢流水線中已經(jīng)執(zhí)行的i+1、i+2、……、i+k-2指令；然后再從分支點開始執(zhí)行第P、p+1、……指令。一條k段流水線有k-2個功能段是浪費的。

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

TK-IF＝(n+k-1)t+npq(k-1)t有條件轉移影響的流水線吞吐率為：有條件轉移影響的流水線最大吞吐率為：流水線吞吐率下降的百分比為：在典型程序中，轉移指令占的比例為p＝20％，轉移成功的概率為ｑ＝60％。對于一條8功能段的指令流水線，由于條件轉移指令的影響，流水線的最大吞吐率要下降：如果指令流水線的功能段數(shù)為10，由于條件轉移指令的影響，流水線的最大吞吐率將下降一半以下：5.3.4靜態(tài)分支預測技術靜態(tài)分支預測：在程序執(zhí)行過程中轉移預測方向不能改變動態(tài)分支預測：在程序執(zhí)行過程中能夠改變轉移預測方向本節(jié)講靜態(tài)預測技術,下節(jié)講動態(tài)預測技術1.軟件“猜測法”目標：通過編譯器盡量降低轉移成功的概率。例如：對于循環(huán)程序，普通編譯器生成的目標代碼，轉移成功的概率很高，不成功的只有一次。這種編譯結果對流水線極為不利。

軟件“猜測法”：

通過編譯器降低轉移成功的概率2.硬件“猜測法”方法：通過改變硬件結構來降低轉移指令對流水線的影響在先行指令緩沖棧的人口處設置一個簡單的指令分析器，當檢測到轉移指令時，就把轉移目標地址L送入先行程序計數(shù)器PC1中，同時保留當前PC1中的內容到另一寄存器中。轉移成功，猜測正確。對轉移指令對流水線不造成影響。轉移不成功，用保存下來的地址恢復PC1和PC。軟硬件共同配合，都往同一個方向去猜測。3.兩個先行指令緩沖棧向前條件轉移，轉移成功與不成功各50%在先行指令緩沖棧中增加一個先行目標緩沖棧按照轉移成功的方向預取指令到先行目標緩沖棧中。先行指令緩沖棧仍然按照轉移不成功的方向繼續(xù)預取指令。如果轉移不成功，則繼續(xù)分析原來先行指令緩沖棧中指令。如果轉移成功，則分析新增設的先行目標緩沖棧中的指令。5.3.5動態(tài)分支預測技術動態(tài)轉移預測技術的兩個關鍵問題：如何記錄轉移歷史信息如何根據(jù)記錄的轉移歷史信息預測轉移方向記錄轉移歷史信息的方法有三種：(1)最近一次或幾次轉移是否成功的信息記錄在轉移指令中(2)用一個高速緩沖棧保存條件轉移指令的轉移目標地址(3)用Cache保存轉移目標地址之后的n條指令1.在指令Cache中記錄轉移歷史信息在指令Cache中專門設置一個字段，稱為“轉移歷史表”。在執(zhí)行轉移指令時，把轉移成功或不成功的信息記錄在這個表中。當下次再執(zhí)行到這條指令時，轉移預測邏輯根據(jù)“轉移歷史表”中記錄的信息預測轉移成功或不成功。只記錄最近一次轉移是否成功的歷史信息如果“轉移歷史表”中記錄的內容是“T”，則預測轉移成功，如果記錄的是“N”，則按照轉移不成功的方向繼續(xù)取指令。并用實際轉移是否成功的信息來修改“轉移歷史表”。

記錄最近兩次轉移是否成功的歷史信息圖中采用偏向成功的預測策略：只有歷史上最近兩次執(zhí)行這條轉移指令時轉移都沒有成功，本次才預測轉移不成功也可以采用其他預測策略“轉移歷史表”的修改規(guī)則和轉移預測規(guī)則可以有多種多樣，記錄轉移預測是否成功的信息。用最近預測是否成功的信息作為是否轉移的依據(jù)當“轉移歷史表”是空白時，可以有兩種做法：在“轉移歷史表”中預置轉移歷史信息。根據(jù)指令本身的偏移字段的符號來預測轉移的方向如果偏移字段為負，則預測轉移成功，否則預測轉移不成功主要優(yōu)點：不必專門設置轉移緩沖棧，所記錄的轉移歷史信息比較少。例如：DEC公司的Alpha21064處理機就采用了這種轉移預測方法，在它的一級指令Cache中有一個專門的“轉移歷史表”字段。Alpha21064的結構框圖：2.設置轉移目標地址緩沖棧用高速緩沖棧保存最近k條轉移指令的“轉移歷史表”和轉移目標地址當前指令地址與轉移目標緩沖棧中的所有轉移指令地址進行比較；如果發(fā)現(xiàn)有相等的，則根據(jù)所記錄的歷史信息預測本次轉移方向。根據(jù)某種規(guī)則修改“轉移歷史表”。3.設置轉移目標指令緩沖棧把上面方法中的“轉移目標地址”字段改為存放轉移目標地址之后的n條指令。預測轉移方向的規(guī)則和修改“轉移歷史表”的規(guī)則與上面的方法相同。5.4動態(tài)調度技術5.4.1順序流動與亂序流動5.4.2亂序流動中的數(shù)據(jù)相關實現(xiàn)方法：由硬件動態(tài)調整指令執(zhí)行順序，以減少數(shù)據(jù)相關造成的影響。主要優(yōu)點：能夠處理在編譯時無法確定的相關，并簡化編譯器設計在其他流水線機器上編譯的目標代碼也能夠高效運行用靜態(tài)調度法生成的代碼也能在動態(tài)調度法的機器中運行主要缺點：指令級并行度低，因為只能在比較小的范圍內尋找并行性5.4.1順序流動與亂序流動1.順序流動方式：任務按順序流入流水線,也按順序流出流水線把如下一段程序輸入到這條流水線中：

k：R0←（R1）

k+1：……k+2：R2←（R0）＋（R3）

k+3：……k+4：……k+5：……指令k+2無法繼續(xù)執(zhí)行，要在功能段S2中等待。后續(xù)的指令k+4、k+5、……等也不能進入流水線。功能段S3、S4、S5將逐漸空閑。缺點：吞吐率和效率降低優(yōu)點：流水線的控制邏輯比較簡單流水線“斷流”，有些功能段“空閑”2.亂序(Outoforder)流動方式：指令流出流水線的順序與流入流水線的順序不同。又稱為錯序流動方式、無序流動方式、異步流動方式等。5.4.2亂序流動中的數(shù)據(jù)相關在亂序流動方式中，可能發(fā)生三種數(shù)據(jù)相關

寫寫相關

k：LOADF1,A;F1（A）寫讀相關

k+1：FADDF2,F1;F2（F2）+（F1）

k+2：FMULF1,F3;F1（F1）（F3）

k+3：STOREF1,B;B（F1）讀寫相關(1)寫讀相關：指令k與指令k+1之間關于F1的相關，又稱為數(shù)據(jù)相關、先寫后讀相關、流相關、WR相關、RAW相關等。(2)讀寫相關：指令k+1與指令k+2之間關于F1的相關，變量名相關、先讀后寫相關、反相關、RW相關、WAR相關等。(3)寫寫相關：指令k與指令k+2左邊的F1之間的相關關系稱為：輸出相關、寫寫相關、WW相關、WAW相關或寫后再寫相關等。有時把相關稱為“冒險”(hazard)、“竟爭”

(competition)等。在程序執(zhí)行過程中，只有避免相關，執(zhí)行結果才是正確的。

三種數(shù)據(jù)相關可以用下列關系式來表示：對于寫讀相關D(i)∩S(j)≠

對于讀寫相關S(i)∩D(j)≠

對于寫寫相關D(i)∩D(j)≠5.5超標量處理機 5.5.1基本結構

5.5.2單發(fā)射與多發(fā)射

5.5.3多流水線調度

5.5.4超標量處理機性能三種主流處理機：

超標量處理機超流水線處理機超標量超流水線處理機5.5.1基本結構普通標量流水線處理機：

一條指令流水線，一個多功能操作部件，每個時鐘周期平均執(zhí)行指令的條數(shù)小于1。多操作部件標量處理機：

一條指令流水線，多個獨立的操作部件，

指令級并行度小于1。超標量處理機典型結構：多條并行工作的指令流水線，多個獨立的操作部件，

指令級并行度（ILP）大于1。

Motorola公司的MC88110有10個操作部件兩個寄存器堆：整數(shù)部件通用寄存器堆，32個32位寄存器浮點部件擴展寄存器堆，32個80位寄存器緩沖深度為4的先行讀數(shù)棧緩沖深度為3的后行寫數(shù)棧兩個獨立的高速Cache中，各為8KB，采用兩路組相聯(lián)方式轉移目標指令Cache，用于存放另一條分支上的指令5.5.2單發(fā)射與多發(fā)射1.單發(fā)射處理機：每個周期只取一條指令、只譯碼一條指令，只執(zhí)行一條指令，只寫回一個運算結果。取指令部件和指令譯碼部件各設置一套；只設置一個多功能操作部件或設置多個獨立的操作部件；操作部件中可以采用流水線結構，也可以不采用流水線結構。目標是每個時鐘周期平均執(zhí)行一條指令，ILP的期望值為1。2.多發(fā)射處理機：每個周期同時取多條指令、同時譯碼多條指令，同時執(zhí)行多條指令，同時寫回多個運算結果。多個取指令部件，多個指令譯碼部件和多個寫結果部件。設置多個指令執(zhí)行部件，有些指令執(zhí)行部件采用流水線結構。目標是每個時鐘周期平均執(zhí)行多條指令，ILP的期望值大于1。3.超標量處理機：有兩條或兩條以上能同時工作的指令流水線先行指令窗口：能夠從指令Cache中預取多條指令，能夠對窗口內的指令進行數(shù)據(jù)相關性分析和功能部件沖突檢測。例如：Intel公司的i860、i960、Pentium，Motolora公司的MC88110，IBM公司的Power6000,TI公司生產(chǎn)SuperSPARC等操作部件的個數(shù)一般多于每個周期發(fā)射的指令條數(shù)。通常為4個至16個操作部件。超標量處理機的指令級并行度：1＜ILP＜m5.5.3多流水線調度順序發(fā)射(in-orderissue)與亂序發(fā)射(out-orderissue)：指令發(fā)射順序是按照程序中指令排列順序進行的稱為順序發(fā)射順序完成(in-ordercompletion)與亂序完成(out-ordercompletion)：指令完成順序是按照程序中指令排列順序進行的稱為順序完成多流水線的調度主要有三種方法：順序發(fā)射順序完成順序發(fā)射亂序完成亂序發(fā)射亂序完成以如下6條指令組成的程序為例，說明這三種調度方法

I1：LOADR1,A；R1←(A)I2：FADDR2,R1；R2←(R2)＋(R1)I3：FMULR3,R4；R3←(R3)×(R4)I4：FADDR4,R5；R4←(R4)＋(R5)I5：DECR6；R6←(R6)－1I6：FMULR6,R7；R6←(R6)＋(R7)6條指令中有4個數(shù)據(jù)相關，包括2個寫讀相關，1個讀寫相關和1個寫寫相關。1.順序發(fā)射順序完成

共用10個時鐘周期完成還有8個空閑的時鐘周期2.順序發(fā)射亂序完成總的執(zhí)行時間為9個時鐘周期，

節(jié)省了一個時鐘周期。少了5個空閑時鐘周期。3.亂序發(fā)射亂序完成

沒有空閑周期，功能部件得到充分利用。總的執(zhí)行時間為8個周期，節(jié)省2個周期。5.5.4超標量處理機性能單流水線普通標量處理機的指令級并行度記作(1,1)，超標量處理機的指令級并行度記作(m,1)，超流水線處理機的指令級并行度記作(1,n)，而超標量超流水線處理機的指令級并行度記作(m,n)。在理想情況下，N條指令在單流水線標量處理機上的執(zhí)行時間為：

T(1,1)＝(k＋N－1)t在每個周期發(fā)射m條指令的超標量處理機上執(zhí)行的時間為：

超標量處理機相對于單流水線標量處理機的加速比為：超標量處理機的加速比的最大值為：S(m,1)MAX＝m5.6超流水線處理機5.6.1指令執(zhí)行時序5.6.2典型處理機結構5.6.3超流水線處理機性能超流水線處理機的兩種定義：在一個周期內分時發(fā)射多條指令的處理機指令流水線的段數(shù)大于等于8的流水線處理機提高處理機性能的兩種方法：通過增加硬件資源來提高處理機性能通過各部分硬件的重疊工作來提高處理機性能兩種不同并行性：超標量處理機采用的是空間并行性。超流水線處理機采用的是時間并行性。5.6.1指令執(zhí)行時序每隔1/n個時鐘周期發(fā)射一條指令，即處理機的流水線周期為1/n個時鐘周期。5.6.2典型處理機結構

MIPSR4000處理機：每個時鐘周期包含兩個流水段是一種很標準的超流水線處理機結構。指令流水線有8個流水段。指令Cache和數(shù)據(jù)Cache的容量各8KB，每個時鐘周期可以訪問Cache兩次，在一個時鐘周期內可以從指令Cache中讀出兩條指令，從數(shù)據(jù)Cache中讀出或寫入兩個數(shù)據(jù)。主要運算部件有整數(shù)部件和浮點部件。如果在LOAD指令之后的兩條指令中，任何一條指令要在它的EX流水級使用這個數(shù)據(jù)，則指令流水線要暫停一個時鐘周期。5.6.3超流水線處理機性能指令級并行度為(1,n)的超流水線處理機，執(zhí)行N條指令所的時間為：超流水線處理機相對于單流水線普通標量處理機的加速比為：

加速比的最大值為：S(1,n)MAX＝n5.7超標量超流水線處理機一個時鐘周期發(fā)射m次，每次發(fā)射n條指令

5.7.1指令執(zhí)行時序5.7.2典型處理機結構5.7.3超標