計算機系統(tǒng)結(jié)構(gòu)隨書ppt 清華大學出本社

1、2021-12-191第五章標量處理機5.1 先行控制技術(shù)5.2 流水線技術(shù)5.3 相關(guān)性分析技術(shù)5.4 超標量處理機5.5 超流水線處理機5.6 超標量超流水線處理機2021-12-192只有標量數(shù)據(jù)表示和標量指令系統(tǒng)的處理機稱為標量處理機提高指令執(zhí)行速度的主要途徑：(1) 提高處理機的工作主頻(2) 采用更好的算法和設(shè)計更好的功能部件(3) 采用指令級并行技術(shù)三種指令級并行處理機：(1) 流水線處理機和超流水線(Super- pipelining)處理機(2) 超標量(Superscalar)處理機(3) 超長指令字(VLIW: Very Long Instruction Word)處理機

2、2021-12-1935.1 先行控制技術(shù)5.1.1 指令的重疊執(zhí)行方式1、順序執(zhí)行方式執(zhí)行n條指令所用的時間為：如果每段時間都為 t，則執(zhí)行n條指令所用的時間為： T=3ntniiiitttT1(）執(zhí)行分析取指令取指令k 分析k 執(zhí)行k 取指令k+1 分析k+1 執(zhí)行k+1 2021-12-194主要優(yōu)點：控制簡單，節(jié)省設(shè)備。主要缺點：執(zhí)行指令的速度慢，功能部件的利用率很低。2、一次重疊執(zhí)行方式一種最簡單的流水線方式取指 分析 執(zhí)行取指 分析 執(zhí)行取指 分析 執(zhí)行2021-12-195主要優(yōu)點：指令的執(zhí)行時間縮短功能部件的利用率明顯提高主要缺點：需要增加一些硬件控制過程稍復雜如果三個過程取指

3、令、分析、執(zhí)行的時間相等，則執(zhí)行n條指令的時間為：T=(1+2n)t2021-12-1963、二次重疊執(zhí)行方式理想情況下同時有三條指令在執(zhí)行如果三過程的時間相等，執(zhí)行n條指令的時間為：T=(2+n)t處理機的結(jié)構(gòu)要作比較大的改變，必須采用先行控制方式取指k+2 分析k+2 執(zhí)行k+2取指k+1 分析k+1 執(zhí)行k+1取指k分析k執(zhí)行k5.1.2 先行控制方式的原理1、采用二次重疊執(zhí)行方式，必須解決兩個問題：(1) 必須有獨立的取指令部件、指令分析部件和指令執(zhí)行部件。必須有獨立的控制器：存儲控制器、指令控制器、運算控制器(2) 要解決訪問主存儲器的沖突問題 取指令、分析指令、執(zhí)行指令都可能要訪問

4、存儲器2、解決訪存沖突的方法：(1) 采用低位交叉存取方式： 如果取指令、讀操作數(shù)、寫結(jié)果不在同一個存儲 體中。但是這種方法不能根本解決沖突問題。(2) 兩個獨立的存儲器：獨立的指令存儲器和數(shù)據(jù)存 儲器。解決取指令和存、取操作數(shù)的矛盾。如果再規(guī)定，執(zhí)行指令所需要的操作數(shù)和執(zhí)行結(jié)果只寫到通用寄存器，也就是指令形式受到限制，那么，取指令、分析指令和執(zhí)行指令就可以同時進行。因此，在許多高性能處理機中，有獨立的指令Cache和數(shù)據(jù)Cache。 這種結(jié)構(gòu)被稱為哈佛結(jié)構(gòu)。(3) 采用先行控制技術(shù)先行控制技術(shù)的關(guān)鍵是緩沖技術(shù)和預處理技術(shù)。緩沖技術(shù)是在工作速度不固定的兩個功能部件之間設(shè)置緩沖棧，用以平滑它們的

5、工作。預處理技術(shù)是指把進入運算器的指令都變成寄存器-寄存器型（RR型）指令，它必須與緩沖技術(shù)結(jié)合，要為進入運算器的指令準備好全部操作數(shù)。送入先行操作棧。采用了緩沖技術(shù)和預處理技術(shù)之后，運算器能夠?qū)Ｐ挠跀?shù)據(jù)的運算，從而大幅度提高程序的執(zhí)行速度。2021-12-19105.2 流水線技術(shù)5.2.1 流水線工作原理5.2.2 流水線的分類5.2.3 線性流水線的性能分析5.2.4 非線性流水線的調(diào)度技術(shù)2021-12-19115.2.1 流水線工作原理空間并行性：設(shè)置多個獨立的操作部件多操作部件處理機超標量處理機時間并行性：采用流水線技術(shù)。不增加或只增加少量硬件就能使運算速度提高幾倍流水線處理機超流

6、水線處理機2021-12-1912一、 流水線的表示方法1、簡單流水線流水線的每一個階段稱為流水步、流水步驟、流水段、流水線階段、流水功能段、功能段、流水級、流水節(jié)拍等。分析器分析k+1流水鎖存器執(zhí)行部件執(zhí)行k流水鎖存器輸入輸出t1t2Stage 1latch輸入輸出t1t2Stage 2latchStage 3latcht32021-12-1913在每一個流水段的末尾或開頭必須設(shè)置一個寄存器，稱為流水寄存器、流水鎖存器、流水閘門寄存器等。會增加指令的執(zhí)行時間。為了簡化，在一般流水線中不畫出流水鎖存器。注意：1、流水線工作的節(jié)拍，是各個功能段中花費時間最長的一個，所以功能段的劃分要合理，處理時

7、間盡量相同。 2、流水線m段，任務n個，每段花費的處理時間為t，則花費的時間為： Tpipe=mt+(n-1)t mt為裝入時間，所以裝入不宜過于頻繁2021-12-19142、一種指令流水線一般4至12個流水段，等于及大于8個流水段的稱為超流水線處理機3、流水線的時空圖一條簡單流水線的時空圖：分析k分析k+1 分析k+2 分析k+3執(zhí)行k執(zhí)行k+1 執(zhí)行k+2 執(zhí)行k+3時間空間0t1t2t3t4t5取指形成操作數(shù)地址譯碼取操作數(shù)執(zhí)行保存結(jié)果2021-12-1915一個浮點加法器流水線的時空圖(由求階差、對階、尾數(shù)加和規(guī)格化4個流水段組成)：ED1時間空間0t1t2t3t4t5ED2 ED3

8、 ED4 ED5EA1 EA2 EA3 EA4 EA5MA1MA2MA3MA4MA5NL1 NL2 NL3 NL4 NL5t6t7t8NL：規(guī)格化MA：尾數(shù)加EA：對階ED：求階差2021-12-1916浮點數(shù)加法：浮點數(shù)加法：一般格式： 31 31 23 22 0加法：符號階碼尾數(shù)階碼階碼1階碼階碼2尾數(shù)尾數(shù)1尾數(shù)尾數(shù)2對階對階尾數(shù)調(diào)整尾數(shù)調(diào)整加加/減減結(jié)果規(guī)格化結(jié)果規(guī)格化計算階碼差計算階碼差2021-12-19174. 流水線的主要特點5. （1）只有連續(xù)提供同類任務才能充分發(fā)揮流水線的效率：對于指令流水線：要盡量減少因條件分支造成的“斷流”對于操作部件：主要通過編譯技術(shù)，盡量提供連續(xù)的同

9、類操作6. （2）在流水線的每一個流水線段中都要設(shè)置一個流水鎖存器時間開銷：流水線的執(zhí)行時間加長是流水線中需要增加的主要硬件之一2021-12-1918（3）各流水段的時間應盡量相等流水線處理機的基本時鐘周期等于時間最長的流水段的時間長度（4）流水線需要有“裝入時間”和“排空時間”新任務裝入裝入時間新舊任務替換排空時間 2021-12-19195.2.2 流水線的分類1、線性流水線與非線性流水線流水線的各個流水段之間是否有反饋信號（1）線性流水線(Linear Pipelining)每個流水段都流過一次，且僅流過一次（2）非線性流水線(Nonlinear Pipelining)在流水線的某些流

10、水段之間有反饋回路或前饋回路線性流水線能夠用流水線連接圖唯一表示非線性流水線必須用流水線連接圖和流水線預約表等共同表示2021-12-1920S1輸入S2S3輸出前饋回路反饋回路一種簡單的非線性流水線S3S2S14321對應的兩種預約表S3S2S143215XX2021-12-19212、按照流水線的級別來分處理機級流水線, 又稱為指令流水線 (Instruction Pipelining)例如：在采用先行控制器的處理機中，各功能部件之間的流水線先行指令緩沖棧輸入先行控制方式中的指令流水線先行指令分析器先行讀數(shù)棧先行操作棧取指譯碼取操作數(shù)指令執(zhí)行部件后行寫數(shù)棧輸出執(zhí)行寫結(jié)果2021-12-19

11、22部件級流水線（操作流水線），如浮點加法器流水線（運算流水線,arithmetic pipelining）處理機之間的流水線稱為宏流水線 (Macro Pipelining)每個處理機對同一個數(shù)據(jù)流的不同部分分別進行處理求階差輸入輸出t1對階尾數(shù)加規(guī)格化t2t3t4P1輸入任務1MMP2任務2MP3任務3輸出2021-12-19233、單功能流水線與多功能流水線單功能流水線：只能完成一種固定功能的流水線Cray-1計算機中有12條；YH-1計算機有18條；Pentium有一條5段的定點和一條8段的浮點流水線；Pentium有三條指令流水線，其中兩條定點指令流水線，一條浮點指令流水線。2021

12、-12-1924多功能流水線：流水線的各段通過不同連接實現(xiàn)不同功能 Texas公司的ASC計算機中的8段流水線，能夠?qū)崿F(xiàn)：定點加減法、定點乘法、浮點加法、浮點乘法、邏輯運算、移位操作、數(shù)據(jù)轉(zhuǎn)換、向量運算等。 A B A B A B A B輸入輸入輸入輸入求階差求階差求階差求階差對階對階對階對階尾數(shù)加尾數(shù)加尾數(shù)加尾數(shù)加規(guī)格化規(guī)格化規(guī)格化規(guī)格化尾數(shù)乘尾數(shù)乘尾數(shù)乘尾數(shù)乘累加累加累加累加輸出輸出輸出輸出g= f(A ,B)定點乘浮點加浮點點積(a)功能段間的互連 (b)定點乘法 (c)浮點加法 (d)浮點點積浮點點積指：浮點點積指： n1iiiBA)B,A( fg2021-12-19264、靜態(tài)流水線

13、與動態(tài)流水線靜態(tài)流水線：同一段時間內(nèi)，多功能流水線中的各個功能段只能按照一種固定的方式連接，實現(xiàn)一種固定的功能。只有連續(xù)出現(xiàn)同一種運算時，靜態(tài)流水線的效率才能得到充分的發(fā)揮。動態(tài)流水線：在同一段時間內(nèi)，多功能流水線中的各段可以按照不同的方式連接，同時執(zhí)行多種功能。2021-12-19271時間空間02 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 4 1 2 3 1 2 1輸入求階差對階尾數(shù)加規(guī)格化尾數(shù)乘累加輸出靜態(tài)流水線時空圖浮點加法定點乘法2021-12-19281時間空間02 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 n1 2

14、3 n輸入求階差對階尾數(shù)加規(guī)格化尾數(shù)乘累加輸出動態(tài)流水線時空圖1 2 35461 2 3541 2 3 41 2 3浮點加法定點乘法2021-12-19295、流水線的其他分類方法按照數(shù)據(jù)表示方式：標量流水線和向量流水線按照控制方式：同步流水線和異步流水線順序流水線與亂序流水線：亂序流水線又稱為無序流水線、錯序流水線或異步流水線等S1就緒回答S2就緒回答S3就緒回答輸出就緒回答輸入2021-12-19305.2.3 線性流水線的性能分析衡量流水線性能的主要指標有：吞吐率、加速比和效率1、吞吐率（Though Put）求流水線吞吐率的最基本公式：TP = n / Tkn為任務數(shù), Tk為完成n個

15、任務所用時間各段執(zhí)行時間相等，輸入連續(xù)任務情況下完成n個連續(xù)任務需要的總時間為：Tk= (k+n-1) t k為流水線的段數(shù)， t為時鐘周期2021-12-19311時間空間S123 n-1 nS2S3S4123 n-1 n123 n-1 n123 n-1 nkt(n-1) tnt(k-1)tT2021-12-1932吞吐率：最大吞吐率為：各段執(zhí)行時間不相等、輸入連續(xù)任務情況下：吞吐率為：最大吞吐率為：tnknTP) 1(nTPLimnknttmax() 11),max() 1(211kkiitttntnTP ),max(121ktttTP 2021-12-1933流水線各段執(zhí)行時間不相等的解

16、決辦法S1輸入t1=tS2t2=3tS3t3=tS4t4=t輸出1時間空間S1S2S3S4ti(n-1)t2Tk23 n123n123 n123 n2021-12-1934一是將“瓶頸”流水段細分(如果可分的話)：二是將 “瓶頸”流水段重復設(shè)置：S1輸入輸出tS2-1tS2-2tS2-3tS3tS4tS2(3t)S1輸入輸出t1=tS2-1S2-1S2-1S3S4t3=tt4=tt2=3t2021-12-19351時間空間2 3nS1流水段重復設(shè)置的流水線S2-14 5 614n-2 n-1n-225n-136n1 2 3n4 5 6n-2 n-11 2 3n4 5 6n-2 n-1S2-2S

17、2-3S3S42021-12-19362、加速比（Speedup）計算流水線加速比的基本公式：S = 順序執(zhí)行時間T0 / 流水線執(zhí)行時間Tk各段執(zhí)行時間相等，輸入連續(xù)任務情況下加速比為： 最大加速比為：各段執(zhí)行時間不等，輸入連續(xù)任務情況下實際加速比為：1) 1(nknktnktnkSSLimk nknknmax12021-12-1937Snttntttiikiikk11121() max(, ,） K=6 K=10任務個數(shù)加速比102468112481632 64 1282021-12-19383、效率（Efficiency）(設(shè)備利用率)計算流水線效率的一般公式：各流水段執(zhí)行時間相等，輸入

18、n個連續(xù)任務流水線的效率為： 流水線的最高效率為：各流水段執(zhí)行時間不等，輸入n個連續(xù)任務流水線的效率為：kTkTknE0個流水段的總的時空區(qū)個任務占用的時空區(qū)1) 1(nkntnkktnkE11maxnknLimEn2021-12-1939流水線各段的設(shè)備量或各段的價格不相等時：流水線的效率為：即：其中，ai為i段的權(quán)值，ai k，且),max() 12111kkiikiitttntktnE （空區(qū)個流水段的總的加權(quán)時區(qū)個任務占用的加權(quán)時空knE ), ,max() 121111nkiiikiIikiiitttntaatanE（kakii12021-12-1940流水線的吞吐率、加速比與效率的

19、關(guān)系：因為因此：E=TP t ，S=kE4、流水線性能分析舉例對于單功能線性流水線，輸入連續(xù)任務的情況，通過上面給出的公式很容易計算出流水線的吞吐率、加速比和效率。例5.1：用一條4段浮點加法器流水線求8個浮點數(shù)的和：ZABCDEFGHtnknTP) 1(1nknkS1nknE2021-12-1941解：Z = (A+B) + (C+D) + (E+F) + (G+H)1時間空間2 3求階差45671 2 3 45671 2 3 45671 2 3 4567對階尾數(shù)加規(guī)格化加數(shù)A C E GA+BE+FB D F HC+DG+HA+B+C+DE+F+G+H結(jié)果A+BC+DE+FG+HA+B+C

20、+DE+F+G+H2021-12-19427個浮點加法共用了15個時鐘周期。流水線的吞吐率為：流水線的加速比為：流水線的效率為：ttTnTPk147015787115740ttTTSk470154740ttTkTEk2021-12-19435. 流水線最佳段數(shù)的選擇 其中最大吞吐量=1/（t/k+d） ；t 任務總時間，d 鎖存器時間，k 段數(shù) 流水線價格=（a+kb） ；a 所有功能段價格，b 鎖存器價格PCR的最佳值是： （書上P292）流流水水線線價價格格最最大大吞吞吐吐量量）價價格格比比（性性能能 PCR/bd)at(k0 2021-12-1944由于非線性，不能每次輸入一個任務，需要

21、調(diào)度。1、向一條流水線的輸入端，順序輸入兩個任務之間的時間間隔稱為啟動距離（initiation interval）或稱為等待時間（latency）。2、幾個任務同時爭用同一個流水段的情況稱為非線性流水線的沖突（collision）.3、引起非線性流水線沖突的啟動距離成為禁止啟動距離5.2.4.1非線性流水線的表示5.2.4 非線性靜態(tài)流水線的調(diào)度技術(shù)2021-12-19465.2.4.2非線性流水線的沖突無無沖突沖突2021-12-19472021-12-19481、禁止向量（禁用表，F(xiàn)orbidden List） 指任務連續(xù)進入流水線禁用的時間間隔 對應于以下的預留表： F =（4，1）2

22、、沖突向量（Collision Vector） 長度m的二進制數(shù) m：禁用表中的最大數(shù) C =（1 0 0 1）S3S2S143215Stage 1Stage2Stage 3幾個重要的描述用的參數(shù)幾個重要的描述用的參數(shù)2021-12-1949 C = c4 c3 c2 c1 =(1 0 0 1) 4 3 2 1 - 時間間隔 F =（4，1）3、狀態(tài)圖：右移三位右移三位與原沖突向量或與原沖突向量或操作操作右移二位右移二位與原沖突與原沖突向量向量或操作或操作2021-12-19504、平均啟動距離（平均等待周期） 不同的狀態(tài)循環(huán)有不同的平均啟動距離 例如：C0-a1-C1-a2 C0 周期稱為 C(2,3) L=(2+3)/2=2.5 C0-a3-C0-a3 周期稱為 C(3) L=3 2021-12-19515、最小平均啟動距離 平均啟動距離中最小的一個。 上述例子中為2.5 在控制上是比較復雜的（時間間隔依