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

2、設(shè)僅有“取指令”和“分析”可重疊并假設(shè)n足夠大）：A. B. C. D. 答案B4. 假設(shè)一條指令的執(zhí)行過程可以分為“取指令”、“分析”和“執(zhí)行”三段，每一段的執(zhí)行時間分別為、和，連續(xù)執(zhí)行n條指令所需要花費的最短時間約為（假設(shè)僅有“取指令”和“執(zhí)行:”可重疊并假設(shè)n足夠大）：A. B. C. D. 答案B5. 假設(shè)一條指令的執(zhí)行過程可以分為“取指令”、“分析”和“執(zhí)行”三段，每一段分別只有一個部件可供使用并且執(zhí)行時間分別為、和，連續(xù)執(zhí)行n條指令所需要花費的最短時間約為（假設(shè)“取指令”、“分析”和“執(zhí)行”可重疊并假設(shè)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：下列哪個數(shù)據(jù)相關(guān)沒有在上述程序段中發(fā)生A. 先寫后讀相關(guān)B. 寫-寫相關(guān)C. 先讀后寫相關(guān)D. 以上都不對答案：D7. 看下述程序段：k：R5=R2k+1：R0=R1×R4k+2：R2=R51k+3：R4=R0×R3k+4：R3=R4-1K+5：k和k+2之間發(fā)生的是什么數(shù)據(jù)相關(guān)I. 先寫后讀相關(guān)II.寫-寫相關(guān)III. 先讀后寫相關(guān)A. 只有IB. 只有I、IIC. 只有I、IIID. 以上都不對答案：C8. 一條流水線可分為k段，各段的執(zhí)行時間都是，共向該流

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

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

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

7、C. (m-1)(n-1)D. mn19. 連續(xù)執(zhí)行100條指令時，一臺2度的超標量處理機的最大效率是多少（假設(shè)這里的每條流水線是4段標準流水線的流水線）A. 100%B. 97.1%C. 94.3%D. 92.6%答案：C20. 連續(xù)執(zhí)行100條指令時，一臺5度的超標量超流水線處理機的最大效率是多少（假設(shè)這里的每條流水線是基于4段標準流水線的超標量流水線）A. 100%B. 97.09%C. 96.34%D. 96.15%答案：C21. 在不同結(jié)構(gòu)的處理機上運行的矩陣乘法CA×B，假設(shè)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. 不能確定（和指令數(shù)有關(guān)）答案：A23. 一條4個功能段的加乘靜態(tài)流水線，四個功能段如下所示，計算，最少需要經(jīng)過多少時間，假設(shè)運算的結(jié)果必須先寫入到緩沖存儲器才能供輸入端使用。并且只有當一個流水線排空后流水線才可以發(fā)生另一種運算。(1) 取指(2) 譯碼、取數(shù)(3) 運算(4) 寫結(jié)果A. 19B. 23C. 25D. 27答案：C24. 一

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

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

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

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

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

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

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

16、，本條指令才能開始執(zhí)行。可以采取設(shè)置專用數(shù)據(jù)通路、延遲執(zhí)行等方法來解決數(shù)據(jù)相關(guān)。(2) 控制相關(guān)控制相關(guān)指由條件分支指令、轉(zhuǎn)子程序指令、中斷等引起的相關(guān)。可以采取靜態(tài)分支預(yù)測技術(shù)、動態(tài)分支預(yù)測技術(shù)、提前形成條件碼等來解決控制相關(guān)。3 演算題2. 一條流水線連接圖如下所示，畫出100條指令連續(xù)通過該流水線的時空圖，并計算該流水線的吞吐率和最大吞吐率。（其中）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條指令連續(xù)通過該流水線的時空圖，并計算該流水線的加速比。（其中）S1S4S3t1=tt1=tt1=tt1=3t輸入輸出S2解：0543216空間時間(ns)321n321nn321321n順序執(zhí)行的時間為T06×100600ns采用流水方式執(zhí)行的時間為T13×10061305ns加速比ST0/T1=600/305=1.974. 連續(xù)執(zhí)行100條指令時，一臺2度的超標量超流水線處理機的最大效率是多少（假設(shè)這里的每條流水線是基于5段標準流水線的超標量流水線），畫出時空圖來說明解：n+4.51n321n32n321n321n

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

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

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

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

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

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

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

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

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