1、第五章 標量處理機與流水線選擇題 25，簡答題10，演算題 151 選擇題1. 假設一條指令的執行過程可以分為“取指令”、“分析”和“執行”三段，每一段的執行時間分別為、和，順序執行n條指令至少需要花費的時間為：A. B. C. D. 答案：C2. 假設一條指令的執行過程可以分為“取指令”、“分析”和“執行”三段，每一段的執行時間均為，連續執行n條指令所需要花費的最短時間約為（假設僅有“取指令”和“執行”可重疊并假設n足夠大）：A. B. C. D. 答案B3. 假設一條指令的執行過程可以分為“取指令”、“分析”和“執行”三段，每一段的執行時間均為，連續執行n條指令所需要花費的最短時間約為（假

2、設僅有“取指令”和“分析”可重疊并假設n足夠大）：A. B. C. D. 答案B4. 假設一條指令的執行過程可以分為“取指令”、“分析”和“執行”三段，每一段的執行時間分別為、和，連續執行n條指令所需要花費的最短時間約為（假設僅有“取指令”和“執行:”可重疊并假設n足夠大）：A. B. C. D. 答案B5. 假設一條指令的執行過程可以分為“取指令”、“分析”和“執行”三段，每一段分別只有一個部件可供使用并且執行時間分別為、和，連續執行n條指令所需要花費的最短時間約為（假設“取指令”、“分析”和“執行”可重疊并假設n足夠大）：A. B. C. D. 答案C6. 看下述程序段：k：R0=R1&#

3、215;R4k+1：R6=R51k+2：R2=R0×R3k+3：R3=R4-1k+4：R2=R5K+5：下列哪個數據相關沒有在上述程序段中發生A. 先寫后讀相關B. 寫-寫相關C. 先讀后寫相關D. 以上都不對答案：D7. 看下述程序段：k：R5=R2k+1：R0=R1×R4k+2：R2=R51k+3：R4=R0×R3k+4：R3=R4-1K+5：k和k+2之間發生的是什么數據相關I. 先寫后讀相關II.寫-寫相關III. 先讀后寫相關A. 只有IB. 只有I、IIC. 只有I、IIID. 以上都不對答案：C8. 一條流水線可分為k段，各段的執行時間都是，共向該流

4、水線輸入n個任務，第n個任務結束于：A.B.C. D.答案：D9. 一條流水線的可分為k段，各段的執行時間都是，共向該流水線輸入n個任務，求該流水線實際吞吐率的為：A. B. C. D. 答案：D10. 一條流水線可以由以下時空圖來表示，求該流水線的實際吞吐率（假設n=100）4ns0空間時間nn-1321nn-1321nn-1n-1321n321A. B. C. D. 答案：C11. 一條4段的流水線可以由以下時空圖來表示，求該流水線的實際吞吐率（假設n=100）0543216空間時間(ns)321n321nn321321nA. B. C. D. 答案：D12. 一條流水線可以由以下時空圖來

5、表示，求該流水線的加速比24ns0空間時間nn-1321nn-1321nn-1n-131n321A. 2B. 3C. 4D. 6答案：C13. 一條4段流水線，每段執行時間為1ns，求該流水線執行100條指令最大效率為：A. 100%B. 96.2%C. 97.1%D. 388%答案：C14. 如下圖所示的浮點加法流水部件，計算，流水線經過多少時鐘后排空（假設時鐘為）t1=3tS2S2S1S4S3t1=tt1=tt1=t輸入輸出S2A. 16B. 15C. 14D. 13答案：B15. 某動態流水線有S1、S2、S3和S4段，其特性由下圖所示的預約表來表示t0t1t2t3t4t5t6S1S2S

6、3S4問該流水線的沖突向量是：A. (111111)B. (110111)C. (010101)D. (101010)答案：D16. 某動態流水線有S1、S2、S3和S4段，其特性由下圖所示的預約表來表示t0t1t2t3t4t5t6S1S2S3S4求該流水線的最小平均啟動周期A. 6B. 5C. 4D. 3.5答案：C17. 下圖所示的時空圖對應的處理機為：43212143時鐘周期I6I5I3I2I1指令4321432143214321A. 標量處理機B. 超標量處理機C. 超流水處理機D. 超標量超流水處理機答案：C18. 一臺度的超標量超流水線處理機的指令并行度為A. mB. m(n-1)

7、C. (m-1)(n-1)D. mn19. 連續執行100條指令時，一臺2度的超標量處理機的最大效率是多少（假設這里的每條流水線是4段標準流水線的流水線）A. 100%B. 97.1%C. 94.3%D. 92.6%答案：C20. 連續執行100條指令時，一臺5度的超標量超流水線處理機的最大效率是多少（假設這里的每條流水線是基于4段標準流水線的超標量流水線）A. 100%B. 97.09%C. 96.34%D. 96.15%答案：C21. 在不同結構的處理機上運行的矩陣乘法CA×B，假設A是m×n階的矩陣，B是n×l階的矩陣，則最少需要進行多少次乘法和多少次加法A

8、. mn, nlB. mnl, ml(n-1)C. mnl, mn(l-1)D. mnl, mnl答案：B22. 試比較在指令并行度較低的情況下，具有相同指令并行度的超標量處理機a和超流水線處理機b的效率A. a>bB. a=bC. a<bD. 不能確定（和指令數有關）答案：A23. 一條4個功能段的加乘靜態流水線，四個功能段如下所示，計算，最少需要經過多少時間，假設運算的結果必須先寫入到緩沖存儲器才能供輸入端使用。并且只有當一個流水線排空后流水線才可以發生另一種運算。(1) 取指(2) 譯碼、取數(3) 運算(4) 寫結果A. 19B. 23C. 25D. 27答案：C24. 一

9、條4個功能段的加乘靜態流水線，四個功能段如下所示，計算，最少需要經過多少時間，假設運算的結果有專門的輸出通路連接到輸入端。并且只有當一個流水線排空后流水線才可以發生另一種運算。(5) 取指(6) 譯碼、取數(7) 運算(8) 寫結果A. 16B. 23C. 25D. 27答案：B25. 一臺標量處理機，具有一條5級指令流水線，每級均耗時1個時鐘周期，執行一個具有20條指令的代碼序列。現將此標量處理機改為超流水線處理機，采用同樣基準的指令流水線，不同的是每隔1/4個時鐘周期發射1條指令，執行相同的代碼序列。問前后兩次執行的加速比。A. 2.4B. 2.46C. 2.67D. 2.75答案：B2

10、問答題1. 簡述流水線技術的特點答：流水線技術具有以下特點：流水過程由多個相聯系的子過程組成，每個過程稱為流水線的“級”或“段”。流水技術適合于大量重復的時序過程。2. 請寫出2種亂序流動方式中的數據相關，并舉例說明分別在什么情況下發生（采用設計程序段的方式來說明）答：寫讀相關：例如程序段R0=R1×R4; R2=R0×R3若第二條指令在第一條指令前執行則最終的結果與正確結果不同，此時發生寫讀相關讀寫相關例如程序段R2=R0×R3; R3=R4-1若第二條指令在第一條指令前執行則最終的結果與正確結果不同，此時發生寫讀數據相關寫寫相關例如程序段R2=R0×

11、R3; R3=R4-1; R2=R5若指令三在指令一前發生則最終的結果與正確結果不同，此時發生寫寫數據相關3. 在流水線處理機當中，可能有哪幾種操作數據相關？這幾種相關分別發生在什么情況下？解決操作數相關的基本方法有哪幾種？答：a. 寫讀相關（先讀后寫）例如程序段R0=R1×R4; R2=R0×R3若第二條指令在第一條指令前執行則最終的結果與正確結果不同，此時發生寫讀相關b. 寫寫相關例如程序段R2=R0×R3; R3=R4-1; R2=R5若指令三在指令一前發生則最終的結果與正確結果不同，此時發生寫寫數據相關c. 讀寫相關（先寫后讀）例如程序段R2=R0

12、5;R3; R3=R4-1若第二條指令在第一條指令前執行則最終的結果與正確結果不同，此時發生寫讀數據相關解決數據相關的方法可以分為2大類：延遲執行、建立專用路徑4. 解決流水線結構相關的方法有哪些？寫出2種答：(1) 流水化功能單元(2) 資源重復5. 降低流水線分支損失的方法有哪些？答：(1) 在流水線中盡早判斷出分支轉移是否成功(2) 盡早計算出分支轉移成功時的PC值（即分支的目標地址）“凍結”“排空”流水線的方法：l 預測分支失敗l 預測分支成功l 延遲分支6. 試寫出延遲分支的3種調度策略，并對其進行評價答：(1) 從前調動分支必須不依賴于被調度阿指令，總是可以有效提高流水線的性能(2

13、) 從目標處調度若分支轉移失敗，必須保證被調度的指令對程序的執行沒有影響，可能需要復制調度指令。分支轉移成功時，可提高流水線性能。單由于復制指令，可能加大程序空間(3) 從失敗處調度若分支轉移成功，必須保證被調度的指令對程序的執行無影響。分支轉移失敗時，可提高流水線性能7. 簡述單流水線標量處理機、超標量處理機、超流水線處理機、超標量超流水線處理機的特點答：具有標量數據表示和標量指令系統的處理機稱為標量處理機，通常只有一條流水線，一個時鐘周期內可以完成一條指令。超標量處理機一般具有多于一條的流水線，一臺m度的超標量處理機可同時發射m條指令，指令的發射等待時間為1個時鐘，指令的并行度為m。超流水

14、線處理機一般具有一條k段的超流水線，一臺n度的超流水處理機可以同時發射一條指令，指令的發射等待時間為1/n個時鐘周期，每個時鐘周期共發射n條指令。指令的并行度為n。超標量超流水處理機一般具有多余1條的超流水線，一臺度的超標量超流水處理機可以同時發射m條指令，指令的發射等待時間為1/n個時鐘周期，每個時鐘周期共發射mn條指令，指令的并行度為mn。8. 畫圖說明什么是流水線“瓶頸”簡述解決流水線瓶頸的方法答：S1S4S3t1=tt1=tt1=3tt1=t輸入輸出S2上圖中的S3段就是流水線瓶頸A. 將流水線的“瓶頸”部分再細分B. 重復設置瓶頸流水段，讓多個瓶頸流水段并行工作9. 什么是靜態流水線

15、？什么是動態流水線答：靜態流水線：在同一時間內，多功能流水線種的各個功能只能按照一種固定的方式連接，實現一種固定的功能。只有當按照這種連接方式工作的所有任務都流出流水線之后，多功能流水線才能重新盡心連接，以實現其他功能。動態流水線：在同一時間內，多功能流水線種的割斷可以按照不同的方式連接，同時執行多種功能。其中流水線種各個功能部件不能發生沖突。10. 程序中有哪兩類相關，分別可以采取什么方法來解決答：程序中可能出現下兩類相關(1) 數據相關數據相關指在執行本條指令的過程中，如果用到的指令、操作數、變址偏移量等是前面指令的執行結果，則必須等待前面的指令執行完成，并把結果寫道主存或通用寄存器中之后

16、，本條指令才能開始執行。可以采取設置專用數據通路、延遲執行等方法來解決數據相關。(2) 控制相關控制相關指由條件分支指令、轉子程序指令、中斷等引起的相關。可以采取靜態分支預測技術、動態分支預測技術、提前形成條件碼等來解決控制相關。3 演算題2. 一條流水線連接圖如下所示，畫出100條指令連續通過該流水線的時空圖，并計算該流水線的吞吐率和最大吞吐率。（其中）S1S4S3t1=tt1=3tt1=tt1=t輸入輸出S2解：321n321nn321n3210543216空間時間(ns)TP=100/(3*100+6-3)=0.3303MIPS（分母是305，300都不對）TPmax=1/3=0.333

17、333MIPS3. 一條流水線連接圖如下所示，畫出100條指令連續通過該流水線的時空圖，并計算該流水線的加速比。（其中）S1S4S3t1=tt1=tt1=tt1=3t輸入輸出S2解：0543216空間時間(ns)321n321nn321321n順序執行的時間為T06×100600ns采用流水方式執行的時間為T13×10061305ns加速比ST0/T1=600/305=1.974. 連續執行100條指令時，一臺2度的超標量超流水線處理機的最大效率是多少（假設這里的每條流水線是基于5段標準流水線的超標量流水線），畫出時空圖來說明解：n+4.51n321n32n321n321n

18、3211n3221n3321n321n3210543216空間時間(ns)n效率由以下方法計算100*5/(5*(100+4.5)=95.69%5. 用1條5個功能段的浮點加法器流水線計算。每個功能段的延時均相等，流水線的輸出端與輸入端之間有直接的數據通路，而且設置有足夠的緩沖寄存器。要求用盡可能短的時間完成計算工作，畫出流水線時空圖，計算流水線的實際吞吐率、加速比和效率解：假設每個功能段的延遲時間為，則上式中加法右下側地座標表示這是第幾個加法時空圖略吞吐率為：加速比為：6. 設有一個15000條指令地程序在一臺時鐘頻率為25MHz的線性處理機上執行。假設該指令流水線有5段，并且每個時鐘周期發

19、射一條指令。忽略由于轉移指令和無序執行造成的損失。(a) 用該流水線執行這一程序，并用通過延遲時間與其相等的一個等效非流水線處理機執行同一程序，將兩者加以比較，并計算其加速比。(b) 該流水線處理機的效率和吞吐率是多少？解：(a) 等效的非流水處理機執行一條指令需要的時間是5個時鐘周期。按照加速比定義，應有(b) 效率為(c) 吞吐率為7. 設有圖3.5所示的浮點加法流水部件，其中第2功能的延遲時間是，其余功能段都是S1S4S3t1=tt1=tt1=tt1=3t輸入輸出S2試提出改進這條流水線的2種方法，并計算改進后的效率（針對100個任務）。解：改進方案1：將S2細分為3個功能斷Z1，Z2，

20、Z3，分別有的延遲時間，則現在流水線有6個功能段，效率為改進方案2：另外補充與S2相同的2個功能段，如下圖所示t1=3tS2S2S1S4S3t1=tt1=tt1=t輸入輸出S2這樣，任務可以連續進入流水線，不存在瓶頸問題，效率為8. 某動態流水線有S1、S2、S3和S4段，其特性由下圖所示的預約表來表示t0t1t2t3t4t5t6S1S2S3S4確定禁止表F和沖突向量C畫出狀態圖，確定其最小平均等待時間和最大吞吐率解：由預約表可以看出，引起沖突的啟動時間是2，4，5，則沖突向量。此流水線的狀態圖如下所示要找出最小平均等待時間，首先要從狀態圖種找出迫切循環。迫切循環的定義是，從它們各自的初始狀態

21、輸出的邊緣都具有最小等待時間。從狀態圖中可以看出（3）和（1，6）是迫切循環，（1，6）平均為3.5。所以最小平均等待時間為3此時最大吞吐率為MAL的倒數為33.3%9. 下列匯編代碼在一臺3段流水線處理機上執行，每一段都有（相關）檢測和分解。這3段是取指令、取操作數（根據要求取一個或多個）和執行（包括寫回操作）。試說明在代碼執行中所有可能的相關情況。k:INCR0k+1:MULACC, R0k+2:STORER1, ACCk+3:ADDACC, R0k+4:STOREM, ACC其中，雙操作數指令，第1個操作數是目的寄存器，第2個操作數是源寄存器。答：1234567IFINCMULSTORE

22、ADDSTOREOFR0ACC,R0ACCACC,R0ACCEXR0ACCR1ACCM由此可以看出在t3時刻，發生先寫后讀相關在t4時刻，發生先寫后讀相關在t6時刻，發生先寫后讀相關。10. 某動態流水線有S1、S2、S3、S4和S5段，其特性由下圖所示的預約表來表示t0t1t2t3t4t5t6S1S2S3S4S5確定禁止表F和沖突向量C畫出狀態圖，確定其最小平均等待時間和最大吞吐率從簡單循環中找出迫切循環使用此流水線時，列出可允許的最小恒定循環如果使用最小恒定循環，則吞吐率是多少？解：禁止等待時間為：3,4,5沖突向量為：(11100)簡單循環如下(1,1,6)，(2,6)，(6)，(1,6

23、)迫切（最小啟動）循環為(1,1,6)最小平均等待時間為(1+1+6)/3=2.67最小恒定循環為(6)設該流水線的時鐘周期為，則最大吞吐率為使用最小恒定循環時，流水線的吞吐率為11. 在不同結構的處理機上運行8×8的矩陣乘法CA×B，計算所需要的最短時間。只計算乘法指令和加法指令的執行時間，不計算取操作數、數據傳送和程序控制等指令的執行時間。加法部件和乘法部件的延遲時間都是3個時鐘周期，另外，加法指令和乘法指令還要經過一個“取指令”和“指令譯碼”的時鐘周期，每個時鐘周期為20ns，C的初始值為0。各操作部件的輸出段有直接數據通路連接到有關操作部件的輸入端，在操作部件的輸出

24、端設置有足夠容量的緩沖寄存器。求：(a) 處理機那只有一個通用操作部件，采用順序方式執行指令的時間(b) 單流水線標量處理機，有一條2個功能的靜態流水線，流水線每個功能段的延遲時間均為1個時鐘周期，加法操作和乘法操作各經過3個功能段解：(a)共需要進行512次乘法和448次加法，需要時間(512+448)*20*(3+1+1)=96000ns(b)先進行所有的乘法，512次乘法，需要51251516個時鐘周期。再進行所有的乘法，每出一個C矩陣中的結果需要考慮時鐘相關，即8個數連加需要18個時鐘周期，出64個數就需要16×641152個時鐘周期，則供需要516+1152=1668個時鐘

25、周期，則需要166800ns12. 某RISC機有8個通用寄存器，有一條4級流水線(1) 取指(2) 譯碼、取數(3) 運算(4) 寫結果試編寫出8個通用寄存器那所存的數據之和的程序，要求此程序的執行時間最短，并計算出時間（假設，每級流水線的周期為50ns，加法運算的結果只能送回寄存器，而不能再傳送途中被截取，另外假設運算的結果可以直接送到輸出端）解：程序如下：ADD R1, R2ADD R3, R4ADD R5, R6ADD R7, R8ADD R1, R3ADD R5, R7ADD R1, R5指令的執行周期數為13，共需要13×50650ns13. 一條具有k個流水段的流水線，

26、由于條件轉移指令的影響，再最壞的情況下，每一次條件轉移將造成k-1個時鐘的“斷流”。另外，假設條件轉移指令再一般程序中所占的比例為p，轉移成功的概率為q。對于一個由n條指令組成的程序，總的執行時間是多少解：由于條件轉移需要額外增加的時鐘周期數是因此，這n條指令的總執行時間是：14. 某RISC機有16個通用寄存器A1A8，B1B8，有一條如下所示的加乘雙功能靜態流水線，加法時按照1、2、3、5連接，乘法時按照1、2、3、4、5連接。流水線的輸出可直接送到其輸入端或存入緩沖器，不計期間的傳送延遲，操作數可連續提供。(1) 取指(2) 譯碼、取數(3) 運算1(4) 運算2(5) 寫結果試編寫出求的程序，要求此程序的執行時間最短，并計算出時間（假設，每級流水線的周期為50ns）解：程序如下：FOR i=1 TO 8 DOMUL Ai, BiADD A1, A2ADD A3, A4ADD A5, A6ADD A7, A8ADD A1, A3ADD A5, A7ADD A1, A5乘法指令的執行周期數為8