《計算機系統(tǒng)結構》PPT課件

《《計算機系統(tǒng)結構》PPT課件》由會員分享，可在線閱讀，更多相關《《計算機系統(tǒng)結構》PPT課件（71頁珍藏版）》請在裝配圖網上搜索。

1、第五章標量處理機,5.1先行控制技術 5.2 流水線處理機 5.3 超標量與超流水線處理機,只有標量數據表示和標量指令系統(tǒng)的處理機稱為標量處理機 提高指令執(zhí)行速度的主要途徑：(1) 提高處理機的工作主頻(2) 采用更好的算法和設計更好的功能部件(3) 采用指令級并行技術 三種指令級并行處理機：(1) 流水線處理機和超流水線(Super- pipelining)處理機(2) 超標量(Superscalar)處理機(3) 超長指令字(VLIW: Very Long Instruction Word)處理機,5.1先行控制技術,先行控制技術的關鍵是緩沖技術和與處理技術。,一條指令的執(zhí)行過程可以分為多

2、個階段，如： 取指 分析 執(zhí)行 可以有多種處理方式：,5.1 指令的重疊執(zhí)行方式,1、順序執(zhí)行方式 執(zhí)行n條指令所用的時間為： 如果每段時間都為t，則執(zhí)行n條指令所用的時間為： T=3nt,取指令k,分析k,執(zhí)行k,取指令k+1,分析k+1,執(zhí)行k+1,主要優(yōu)點：控制簡單，節(jié)省設備。 主要缺點：執(zhí)行指令的速度慢，功能部件的利用率很低。 2、一次重疊執(zhí)行方式 一種最簡單的流水線方式 如果兩個過程的時間相等，則執(zhí)行n條指令的時間為：T=(1+2n)t,取指,分析,執(zhí)行,取指,分析,執(zhí)行,取指,分析,執(zhí)行,主要優(yōu)點：指令的執(zhí)行時間縮短功能部件的利用率明顯提高 主要缺點：需要增加一些硬件控制過程稍復雜

3、,3、二次重疊執(zhí)行方式 如果三過程的時間相等，執(zhí)行n條指令的時間為：T=(2+n)t 理想情況下同時有三條指令在執(zhí)行 處理機的結構要作比較大的改變，必須采用先行控制方式,取指k+2,分析k+2,執(zhí)行k+2,取指k+1,分析k+1,執(zhí)行k+1,取指k,分析k,執(zhí)行k,5.1.2先行控制方式的原理 1、采用二次重疊執(zhí)行方式，必須解決兩個問題： (1) 有獨立的取指令部件、指令分析部件 和指令執(zhí)行部件 獨立的控制器： 存儲控制器、指令控制器、運算控制器 (2) 要解決訪問主存儲器的沖突問題 取指令、分析指令、執(zhí)行指令都可能要訪問存儲器 2、解決訪存沖突的方法： (1) 采用低位交叉存取方式： 這種方

4、法不能根本解決沖突問題。 取指令、讀操作數、寫結果。,(2) 兩個獨立的存儲器：獨立的指令存儲器和數據存儲器。 如果再規(guī)定，執(zhí)行指令所需要的操作數和執(zhí)行結果只寫到通用寄存器，那么，取指令、分析指令和執(zhí)行指令就可以同時進行。 在許多高性能處理機中，有獨立的指令Cache和數據Cache。 這種結構被稱為哈佛結構。 (3) 采用先行控制技術。 先行控制技術的關鍵是緩沖技術和預處理技術。 緩沖技術是在工作速度不固定的兩個功能部件之間設置緩沖棧，用以平滑它們的工作。 在采用了緩沖技術和預處理技術之后，運算器能夠專心于數據的運算，從而大幅度提高程序的執(zhí)行速度。,5.1.2.1處理機結構,圖5.3 5.4

5、 需要解決的三個問題： （1）指令不同，執(zhí)行與分析相互等待 （2）數據相關 （3）轉移指令,5.1.2.2指令執(zhí)行順序Fig5.6 5.7 5.8,5.1.2.3先行緩沖棧 Fig5.9 先行指令緩沖棧用于平滑主存儲器和指令分析器的工作。 先行指令緩沖棧用于平滑分析與運算。 先行讀數棧用于平滑主存與運算器。 后行寫數棧用于平滑主存與運算器。,5.1.2.4緩沖深度的設計各個緩沖棧中的緩沖寄存器個數的設置,靜態(tài)分析法 一種極端 另一種極端,5.1.3數據相關,（1）數據相關包括 指令相關 主存操作數相關 通用寄存器相關 變址相關 （2）解決數據相關的途徑： 一、推后分析法 二、設置專用路徑,5.

6、1.4控制相關,包括：無條件轉移、一般條件轉移、安全條件轉移。 解決方法： 1、軟件猜測法 2、硬件猜測法 3、兩個先行指令緩沖棧,5.2 流水線處理機 5.2.1 流水線工作原理 5.2.2 流水線的分類 5.2.3 線性流水線的性能分析 5.2.4 非線性流水線的調度技術 5.2.5局部相關 5.2.6全局相關,處理機內部并行性 空間并行性： 設置多個獨立的操作部件 多操作部件處理機 超標量處理機 時間并行性：采用流水線技術。不增加或只增加少量硬件就能使運算速度提高幾倍流水線處理機超流水線處理機,5.2.1 流水線工作原理 1、簡單流水線 流水線的每一個階段稱為流水步、流水步驟、流水段、流

7、水線階段、流水功能段、功能段、流水級、流水節(jié)拍等。,分析器 分析k+1,流水鎖存器,執(zhí)行部件 執(zhí)行k,流水鎖存器,輸 入,輸 出,t1,t2,在每一個流水段的末尾或開頭必須設置一個寄存器，稱為流水寄存器、流水鎖存器、流水閘門寄存器等。會增加指令的執(zhí)行時間。 為了簡化，在一般流水線中不畫出流水鎖存器。 2、一種指令流水線,取指,形成操作數地址,譯碼,取操 作數,執(zhí)行,保存 結果,一般4至12個流水段，等于及大于8個流水段的稱為超流水線處理機 3、流水線的時空圖 一條簡單流水線的時空圖：,分析k,分析k+1,分析k+2,分析k+3,執(zhí)行k,執(zhí)行k+1,執(zhí)行k+2,執(zhí)行k+3,時間,空間,0,t1,

8、t2,t3,t4,t5,一個浮點加法器流水線的時空圖(由求階差、對階、尾數加和規(guī)格化4個流水段組成)：,ED1,時間,空間,0,t1,t2,t3,t4,t5,ED2,ED3,ED4,ED5,EA1,EA2,EA3,EA4,EA5,MA1,MA2,MA3,MA4,MA5,NL1,NL2,NL3,NL4,NL5,t6,t7,t8,NL：規(guī)格化,MA：尾數加,EA：對階,ED：求階差,4、流水線的主要特點 只有連續(xù)提供同類任務才能充分發(fā)揮流水線的效率：對于指令流水線：要盡量減少因條件分支造成的“斷流”對于操作部件：主要通過編譯技術，盡量提供連續(xù)的同類操作 在流水線的每一個流水線段中都要設置一個流水鎖

9、存器時間開銷：流水線的執(zhí)行時間加長是流水線中需要增加的主要硬件之一,各流水段的時間應盡量相等流水線處理機的基本時鐘周期等于時間最長的流水段的時間長度 流水線需要有“裝入時間”和“排空時間”,裝入時間：在流水線開始時有一段流水線填入時間，使得流水線填滿。 正常流動時間：流水線正常工作，各功能段源源不斷滿載工作。 排空時間：在流水線第一條指令結束時，其他指令還需要一段釋放時間。,5.2.2 流水線的分類 1、線性流水線與非線性流水線 流水線的各個流水段之間是否有反饋信號 線性流水線(Linear Pipelining)每個流水段都流過一次，且僅流過一次 非線性流水線(Nonlinear Pipel

10、ining)在流水線的某些流水段之間有反饋回路或前饋回路 線性流水線能夠用流水線連接圖唯一表示非線性流水線必須用流水線連接圖流水線預約表等共同表示,S1,輸入,S2,S3,輸出,前饋回路,反饋回路,一種簡單的非線性流水線,2、按照流水線的級別來分 處理機級流水線, 又稱為指令流水線 (Instruction Pipelining)例如：在采用先行控制器的處理機中，各功能部件之間的流水線,先行指令緩沖棧,輸入,先行控制方式中的指令流水線,先行指令分析器,先行讀數棧先行操作棧,取指,譯碼,取操作數,指令執(zhí) 行部件,后行 寫數棧,輸出,執(zhí)行,寫結果,部件級流水線（操作流水線），如浮點加法器流水線 處

11、理機之間的流水線稱為宏流水線 (Macro Pipelining)每個處理機對同一個數據流的不同部分分別進行處理,求階差,輸入,輸出,t1,對階,尾數加,規(guī)格化,t2,t3,t4,P1,輸 入,任務1,M,M,P2,任務2,M,P3,任務3,輸 出,3、單功能流水線與多功能流水線 單功能流水線：只能完成一種固定功能的流水線Cray-1計算機中有12條；YH-1計算機有18條；Pentium有一條5段的定點和一條8段的浮點流水線；Pentium有三條指令流水線，其中兩條定點指令流水線，一條浮點指令流水線。,多功能流水線：流水線的各段通過不同連接實現不同功能 Texas公司的ASC計算機中的8段流

12、水線，能夠實現：定點加減法、定點乘法、浮點加法、浮點乘法、邏輯運算、移位操作、數據轉換、向量運算等。,4、靜態(tài)流水線與動態(tài)流水線 靜態(tài)流水線：同一段時間內，多功能流水線中的各個功能段只能按照一種固定的方式連接，實現一種固定的功能。只有連續(xù)出現同一種運算時，流水線的效率才能得到充分的發(fā)揮。 動態(tài)流水線：在同一段時間內，多功能流水線中的各段可以按照不同的方式連接，同時執(zhí)行多種功能。,5.2.3 線性流水線的性能分析 衡量流水線性能的主要指標有：吞吐率、加速比和效率 1、吞吐率（Through Put） 定義:單位時間內能處理的指令條數或能輸出的數據量。吞吐率越高，計算機系統(tǒng)的處理能力就越強。就流水

13、線而言，吞吐率就是單位時間內能流出的任務數或能流出的結果數。 求流水線吞吐率的最基本公式：TP = n / Tk n為任務數, Tk為完成n個任務所用時間 各段執(zhí)行時間相等，輸入連續(xù)任務情況下完成n個連續(xù)任務需要的總時間為：Tk= (k+n-1) t k為流水線的段數， t為時鐘周期,吞吐率：最大吞吐率為： 各段執(zhí)行時間不相等、輸入連續(xù)任務情況下：吞吐率為：最大吞吐率為：,2、加速比（Speedup） 計算流水線加速比的基本公式：S = 順序執(zhí)行時間T0 / 流水線執(zhí)行時間Tk 各段執(zhí)行時間相等，輸入連續(xù)任務情況下加速比為： 最大加速比為： 各段執(zhí)行時間不等，輸入連續(xù)任務情況下實際加速比為：,

14、3、效率（Efficiency） 定義：設備的利用率，直接反映了處理機結構有效程度。 計算流水線效率的一般公式： 各流水段執(zhí)行時間相等，輸入n個連續(xù)任務流水線的效率為： 流水線的最高效率為： 各流水段執(zhí)行時間不等，輸入n個連續(xù)任務流水線的效率為：,流水線各段的設備量或各段的價格不相等時：流水線的效率為：即：其中，ai k，且,流水線的吞吐率、加速比與效率的關系：因為因此：E=TP t ，S=kE 5、流水線性能分析舉例 對于單功能線性流水線，輸入連續(xù)任務的情況，通過上面給出的公式很容易計算出流水線的吞吐率、加速比和效率。,例5.1：用一條4段浮點加法器流水線求8個浮點數的和：ZABCDEFGH

15、 分析： 1、線性流水線，輸入任務不連續(xù) 2、存在數據相關，如只有A+B的運算結果出來之后才能做加C的運算 3、如果這樣，與順序執(zhí)行方式完全一樣 4、如果作如下變換： Z = (A+B) + (C+D) + (E+F) + (G+H) 小括號內的操作之間，沒有數據相關，可以連續(xù)輸入到流水線中。,解：Z = (A+B) + (C+D) + (E+F) + (G+H),1,時間,空間,2,3,求階差,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,對階,尾數加,規(guī)格化,加數,A,C,E,G,A+B,E+F,B,D,F,H,C+D,G+H,A+B+

16、C+D,E+F+G+H,結果,A+B,C+D,E+F,G+H,A+B+C+D,E+F+G+H,7個浮點加法共用了15個時鐘周期。流水線的吞吐率為：流水線的加速比為：流水線的效率為：,5.2.4非流水線的調度技術,5.2.4.1非線性流水線的表示 1、一條非流水線一般需要一個各功能段之間的連接圖和一張預約表共同來表示。 2、一張非線性流水線的預約表可能與多個非線性流水線連接圖相對應 3、一個非線性流水線的連接圖也可能對應有多張預約表,5.2.4.2非線性流水線的沖突,向一條非線性流水線的輸入端連續(xù)輸入兩個任務之間的時間間隔稱為非線性流水線的啟動距離或等待時間。 非線性流水線的沖突：某一個或幾個功

17、能段中發(fā)生的多個任務同時爭用同一功能段的情況。 禁止啟動距離：引起非線性流水線功能段沖突的啟動距離。所有的禁止啟動距離為沖突向量。 非線性流水線中，不發(fā)生沖突的啟動距離通常情況下是一個循環(huán)數列。 恒定循環(huán)。,5.2.4.3無沖突調度方法,對于一張有K列的預約表，則有m=k-1。禁止向量用C=（CmC3C2C1）, 如果i在禁止向量中，則Ci=1，否則Ci=0，其中Cm一定為1，因為m比在禁止向量中。 一張預約表對應一個狀態(tài)圖 不同的預約也可能有相同的狀態(tài)圖,5.2.4.4優(yōu)化調度方法,1、最小平均啟動距離的下限是任意一行中“叉號”的最多個數。 2、最小平均啟動距離小于或等于任意一個簡單循環(huán)的平

18、均啟動距離。 3、最小平均啟動距離的上限是1的個數加1。 上述方法適用于單功能非線性流水線和靜態(tài)多功能非線性流水線。,5.2.5局部相關,5.2.5.1順序流動與亂序流動 先寫后讀寫讀 先讀后寫讀寫 寫寫 B0和B2之間的相關是全局相關，B2內部的相關是局部相關。,5.2.5.2數據相關及其避免方法,先寫后讀 先讀后寫 寫寫 避免方式： （1）延遲執(zhí)行 （2）建立專用路徑如采用分散控制的公共數據總線法，采用集中控制的CDC記分牌法等。,5.2.5.3 數據重定向,P308 圖5.62 P309 圖5.63,5.2.5.4 Tomasula動態(tài)指令調度算法令牌法,5.2.6 全局相關,全局相關是

19、由條件轉移或程序中斷引起的相關，也叫控制相關。 5.2.6.1 轉移的影響 為了不破壞通用寄存器和主存儲器中的內容，有兩種方法： （1）只進行指令譯碼和準備好運算所需要的操作數，在轉移條件沒有形成之前不執(zhí)行運算。簡單 （2）一直執(zhí)行運算，但不送回運算結果。設置緩沖器，回送結果復雜,減少條件轉移指令影響可采取的措施 1、延遲轉移技術和指令取消技術 2、靜轉移預測技術 3、動態(tài)轉移預測技術,5.2.6.2動態(tài)轉移預測技術,動態(tài)轉移預測技術要解決的兩個問題： （1）如何記錄轉移歷史信息。 （2）如何根據所記錄的轉移歷史信息預測轉移的方向。,三種動態(tài)轉移預測技術,方法一：在指令Cache中記錄轉移歷史

20、信息 方法二：轉移目標地址緩沖棧 方法三：轉移目標指令緩沖棧 5.2.6.3提前形成條件碼 5.2.6.4精確斷點與不精確斷點 不精確斷點最后進入流水線的那條指令的地址 精確斷點從中間進入流水線的那條指令的地址,5.3超標量處理機與超流水線處理機,指令級并行處理機： 超標量 m 超流水線 n 超標量超流水線 （m,n） 區(qū)別：一般流水線處理機，具有一個多功能的操作部件。ILP1,5.3.1 超標量處理機 5.3.1 .1基本結構 5.3.1.2 單發(fā)射與多發(fā)射 5.3.1.3 超標量處理機性能,5.3.1 基本結構,典型結構 （1）多個操作部件。 （2）一個或幾個較大的通用寄存器堆。 （3）一

21、個或兩個高速Cache. 先進的 （1）三個處理單元 包括 A 定點CPU-由多個整數處理部件組成。 B 浮點CPU-浮點加法和乘除部件組成。 C 圖形加速部件 （2）大量的寄存器,5.3.1.2 單發(fā)射與多發(fā)射 單發(fā)射處理機：取指、譯碼各設置一套，ILP的期望值1。一般為ILP1 多發(fā)射處理機：取指、譯碼各設置兩套以上，ILP的期望值m。一般為1ILPm 先行至另窗口可以先發(fā)射無數據相關的指令。,5.3.1.3多流水線調度,指令的發(fā)射順序與完成順序 （1）順序發(fā)射順序完成 （2）順序發(fā)射亂序完成 （3）亂序發(fā)射順序完成 其中（1）和（2）均未用先行指令窗口 Fig 5.74 5.75 5.7

22、6 及程序,5.3.1.4資源沖突,以無流水線的操作與有流水線的操作相比，后者比前者少了3個時鐘周天氣，“忙”標志觸發(fā)器。 每個時鐘發(fā)射m條指令，對延遲時間為K個時鐘周期的操作。不用流水線結構則使用同一個部件的兩條指令的序號用那個該至少相差m*k.若用流水線，則相差m個，則不沖突。,5.3.1.5超標量處理機性能 N條指令在單流水線普通標量處理機上的執(zhí)行時間: T(1,1)=(k+N-1)t，k是流水級數，t為始終周期 N條指令在一臺每個時鐘周期發(fā)射m條指令的超標量處理機上所需時間： T(m,1)=k+(N-m)/m t 則相對于單流水線普通標量處理機的加速比為： S(m,1)=T(1,1)/

23、T(m,1)=m(k+N-1)/N+m(k-1) 當N趨近于無窮大時，S(m,1)max=m,5.3.2超流水線處理機 兩種定義：一個周期內能夠分時發(fā)射多條指令的處理機稱為超流水線處理機 兩種不同并行性：超標量處理機采用的是空間并行性超流水線處理機采用的是時間并行性,5.3.2.1 指令執(zhí)行時序 每隔1/n個時鐘周期發(fā)射一條指令，流水線周期為1/n個時鐘周期 在超標量處理機中，流水線的有些功能段還可以進一步細分 例如：ID功能段可以再細分為譯碼、讀第一操作數和讀第二操作數三個流水段。也有些功能段不能再細分，如WR功能段一般不再細分。因此有超流水線的另外一種定義：有8個或8個以上流水段的處理機稱

24、為超流水線處理機,5.3.2.2 典型處理機結構 MIPS R4000處理機每個時鐘周期包含兩個流水段，是一種很標準的超流水線處理機結構。指令流水線有8個流水段 有兩個Cache，指令Cache和數據Cache的容量各8KB，每個時鐘周期可以訪問Cache兩次，因此在一個時鐘周期內可以從指令Cache中讀出兩條指令，從數據Cache中讀出或寫入兩個數據。 主要運算部件有整數部件和浮點部件,5.3.2.3 超流水線處理機性能 指令級并行度為(1,n)的超流水線處理機，執(zhí)行N條指令所的時間為： K是指令流水線的時鐘周期數，而不是流水線級數 超流水線處理機相對于單流水線普通標量處理機的加速比為：,即

25、： 超流水線處理機的加速比的最大值為：S(1,n)MAX = n,5.3.3 超標量超流水線處理機 把超標量與超流水線技術結合在一起，就成為超標量超流水線處理機從開發(fā)程序的指令級并行性來看 （1）超標量開發(fā)空間并行性依靠多個操作在重復設置的部件上并行操作來提高速度。 （2）超標量開發(fā)時間并行性在同一個部件操作上重疊操作。 5.3.3.1 指令執(zhí)行時序 5.3.3.2 典型處理機結構 5.3.3.3 超標量超流水線處理機性能,5.5.1 指令執(zhí)行時序 超標量超流水線處理機在一個時鐘周期內分時發(fā)射指令n次，每次同時發(fā)射指令m條，每個時鐘周期總共發(fā)射指令m n條。,IF,時鐘周期,指令,I1,I2,

26、I3,ID,EX,WR,1,2,3,4,5,I4,I5,I6,I7,I8,I9,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,IF,ID,EX,WR,I10,I11,I12,每時鐘周期發(fā)射3次,每次3條指令,5.5.2 典型處理機結構 DEC公司的Alpha處理機采用超標量超流水線結構。主要由四個功能部件和兩個Cache組成：整數部件EBOX、浮點部件FBOX、地址部件ABOX和中央控制部件IBOX。

27、中央控制部件IBOX可以同時從指令Cache中讀入兩條指令，同時對讀入的兩條指令進行譯碼，并且對這兩條指令作資源沖突檢測，進行數據相關性和控制相關性分析。如果資源和相,關性允許，IBOX就把兩條指令同時發(fā)射給EBOX、ABOX和FBOX三個指令執(zhí)行部件中的兩個。 指令流水線采用順序發(fā)射亂序完成的控制方式。在指令Cache中有一個轉移歷史表，實現條件轉移的動態(tài)預測。在EBOX內還有多條專用數據通路，可以把運算結果直接送到執(zhí)行部件。 Alpha 21064處理機共有三條指令流水線整數操作流水線和訪問存儲器流水線分為7個流水段，其中，取指令和分,析指令為4個流水段，運算2個流水段，寫結果1個流水段。

28、浮點操作流水線分為10個流水段，其中，浮點執(zhí)行部件FBOX的延遲時間為6個流水段。 所有指令執(zhí)行部件EBOX、IBOX、ABOX和FBOX中都設置由專用數據通路。 Alpha 21064處理機的三條指令流水線的平均段數為8段，每個時鐘周期發(fā)射兩條指令。因此，Alpha 21064處理機是超標量超流水線處理機。,5.5.3 超標量超流水線處理機性能 指令級并行度為(m,n)的超標量超流水線處理機，連續(xù)執(zhí)行N條指令所需要的時間為： 超標量超流水線處理機相對于單流水線標量處理機的加速比為：,在理想情況下，超標量超流水線處理機加速比的最大值為： S(m, n)MAXm n,本 章 重 點 1、指令的重疊執(zhí)行方式及時空圖表示方法 2、線性流水線的性能分析及計算 3、超標量處理機的指令執(zhí)行時序及性能 4、超流水線處理機的指令執(zhí)行時序及性能 5、超標量超流水線處理機的指令執(zhí)行時序 及性能,