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

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

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

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

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

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

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

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

5.2.1流水線工作原理

5.2.2流水線的分類

5.2.3線性流水線的性能分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Tk＝(k＋n－1)t

其中：k

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

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

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

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

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

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

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

b為每個鎖存器的價格

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

求PCR的最大值為：5.流水線性能分析舉例對于單功能線性流水線，輸入連續(xù)任務(wù)的情況，通過上面給出的公式很容易計算出流水線的吞吐率、加速比和效率。對于輸入不連續(xù)任務(wù)，或多功能流水線，通常采用基本公式計算。例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非線性流水線的調(diào)度非線性流水線調(diào)度的任務(wù)是要找出一個最小的循環(huán)周期，按照這周期向流水線輸入新任務(wù)，流水線的各個功能段都不會發(fā)生沖突，而且流水線的吞吐率和效率最高。1.非線性流水線的表示線性流水線能夠用流水線連接圖唯一表示對于非線形流水線，連接圖不能唯一表示工作流程，因此，引入流水線預(yù)約表例如：

非線形流水線的連接圖和預(yù)約表

一張預(yù)約表可能與多個流水線連接圖相對應(yīng)

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

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

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

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

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

初始沖突向量：S=101010(2)構(gòu)造狀態(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)化調(diào)度方法L.E.Shar于1972年提出流水線最小平均啟動距離的限制范圍：

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

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

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

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

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

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

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

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

解決指令相關(guān)的根本辦法是：

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

n：OPA1，A2，A3

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

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

A1（n）＝A2（n＋1）

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

n：OPR1，A2

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

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

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

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

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

……L：……

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

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

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

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

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

軟件“猜測法”：

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

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

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ù)相關(guān)在亂序流動方式中，可能發(fā)生三種數(shù)據(jù)相關(guān)

寫寫相關(guān)

k：LOADF1,A;F1（A）寫讀相關(guān)

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

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

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

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

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

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

對于寫寫相關(guān)D(i)∩D(j)≠5.5超標量處理機 5.5.1基本結(jié)構(gòu)

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

5.5.3多流水線調(diào)度

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

超標量處理機超流水線處理機超標量超流水線處理機5.5.1基本結(jié)構(gòu)普通標量流水線處理機：

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

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

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

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

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

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ù)相關(guān)，包括2個寫讀相關(guān)，1個讀寫相關(guān)和1個寫寫相關(guān)。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典型處理機結(jié)構(gòu)5.6.3超流水線處理機性能超流水線處理機的兩種定義：在一個周期內(nèi)分時發(fā)射多條指令的處理機指令流水線的段數(shù)大于等于8的流水線處理機提高處理機性能的兩種方法：通過增加硬件資源來提高處理機性能通過各部分硬件的重疊工作來提高處理機性能兩種不同并行性：超標量處理機采用的是空間并行性。超流水線處理機采用的是時間并行性。5.6.1指令執(zhí)行時序每隔1/n個時鐘周期發(fā)射一條指令，即處理機的流水線周期為1/n個時鐘周期。5.6.2典型處理機結(jié)構(gòu)

MIPSR4000處理機：每個時鐘周期包含兩個流水段是一種很標準的超流水線處理機結(jié)構(gòu)。指令流水線有8個流水段。指令Cache和數(shù)據(jù)Cache的容量各8KB，每個時鐘周期可以訪問Cache兩次，在一個時鐘周期內(nèi)可以從指令Cache中讀出兩條指令，從數(shù)據(jù)Cache中讀出或?qū)懭雰蓚€數(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典型處理機結(jié)構(gòu)5.7.3超標