《計算機系統(tǒng)結(jié)構(gòu)》往年考題答案

《《計算機系統(tǒng)結(jié)構(gòu)》往年考題答案》由會員分享，可在線閱讀，更多相關(guān)《《計算機系統(tǒng)結(jié)構(gòu)》往年考題答案（17頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、《計算機系統(tǒng)結(jié)構(gòu)》往年考題參考答案 僅供參考！ 一、簡答題 L指令流水計算機中，采用獨立的指令緩存與數(shù)據(jù)緩存對系統(tǒng)性能有什么好處。 【答】①解決訪存和村又指的結(jié)構(gòu)沖突，加速流水線：②數(shù)據(jù)和指令的訪問有所不問，設(shè)置單獨 的Cache有利于提高命中率，減少平均訪存時間。 2?什么是指令動態(tài)調(diào)度？使用寄存器重命名能夠解決哪些數(shù)據(jù)沖突？ 【答】指令動態(tài)調(diào)度是指在程序執(zhí)行過程中，依靠專門的碩件隊代碼進行調(diào)度。使用寄存器重 命名能夠解決名相關(guān)(反相關(guān)、輸出相關(guān)). 3 ?從數(shù)據(jù)和指令的角度，分別說明引起時間與空間局部性的原因。 【答】數(shù)據(jù)：對于剛被訪問過的數(shù)據(jù)，很有可能再次訪問它或者它附近

2、的數(shù)據(jù)。指令：順序執(zhí) 行的可能性較大。 4 .直接用虛擬地址索引緩存會存在什么問題？ 【答】多個虛擬地址可能指向同一物理地址。 5?多處理機為什么耍維護緩存一致性？ 【答】每個處理機都有一份自己的Cache,但是這些Cache都映射同一個物理主存，當(dāng)一個處 理 機修改□己Cache的數(shù)據(jù)時，其他處理機中該部分的數(shù)據(jù)就不是最新的，造成不一致性。 二.填空題 1 ? 16個處理器組成的網(wǎng)絡(luò)，使用洸牌函數(shù)相聯(lián)，那么與10號相聯(lián)的是 【答】10= (1010) 2,循環(huán)左移一位得(0101) 2=5o 2 ?有16個處理器，編號為0,1,…，15,先經(jīng)過 +3*Pl2+3,再經(jīng)過混洗變

3、換后，11號處理器連 向一號處理器。 【答】H經(jīng)過PM2*3得到(H + 2")modI6=3, 3再經(jīng)過混洗變換得6。 3?使用混洙交換單級網(wǎng)絡(luò)將一個PE中的數(shù)據(jù)播送到所有16個PE中，需耍一次交換，需要一混洗。 假設(shè)每步只能進行混洗或交換中的一種變換。 【答】4次交換，3次混洗0 4 ? 16個處理器組成的網(wǎng)絡(luò)，采用PM2切PM22鏈接，網(wǎng)絡(luò)直徑為，結(jié)點度為 【答】有結(jié)論：2”個處理器組成的網(wǎng)絡(luò)，采用PM2兇，PM2如2鏈接，實現(xiàn)各處理單元之間上 下左右互聯(lián)。網(wǎng)絡(luò)直徑為3,結(jié)點度為4 (?)o 5?可以在向量與標(biāo)量工作模式中切換的處理器，處理向量時效率是處理標(biāo)量的9倍。已知運

4、行一 段程序時有1/4的時間在運行向量指令，向量指令的比例為 【答】設(shè)向量指令占比I則一-一二-.解得x = x+9(i-x) 4 4 6 .向量處理器在串行模式執(zhí)行以下指令需耍 拍，使用鏈接技術(shù)需要. 拍。 v3 <- A (load. 6 拍) v2 <- v0 + vl (add. 6 拍) v4 <- v2 * v3 (muL 7 拍) 【答】串行模式下需要a +6 + 1) +仆+ 6 + 1) + (1 + 7 + 1)=25拍： 使用鏈接技術(shù)需要1+6+1 + 1 + 7 + 1=17拍。 7 ?處理器P1和P2執(zhí)行A, B, C三種指令的周期如下 Pl

5、 P2 A I 2 B 2 3 C 4 4 一段程序中A占60%, B占30%, C占10%,分別求P1和P2運行該程序時的CPL 【答】P1運行該程序的CPI為0. 6x1 + 03x2 + 0, 1x4 = 1, 6 . P?運行該程序的CPI為0. 6x2 + 03x3 + 0, 1x4 = 2. 5 o 13 &己知一處理器指令緩存不命中率為2%,數(shù)據(jù)緩存不命中率為4%,不命中代價為100周期。命中 時，CPI為2,那么執(zhí)行一段含有Load/Save指令各15%的程序時，其CPI為。 【答】每條指令出現(xiàn)不命中的概率是0,02+是x0. 04=0-03

6、2.故其CPI為0.032為00 + 2 = 5. 2 o 9?五段流水線CPU,各段延遲時間分別為2 - 2ns25ns, 2 - 2ns23ns23ns連續(xù)執(zhí)行10條指令，需要 的時間為一，該CPU最高頻率為 MHzo 【答】各段不等長的流水線計算公式參見 教材 58 頁(時空圖如如 38),需要的時間為 max {222 ? 5222323} x (10-1) + (2-2 + 2- 5 + 2- 2 + 2 ? 3+2 - 3) = 34ns,最大周期為2 ? 5ns,即頻率 為400MHz 10?采用預(yù)留算法實現(xiàn)的非線性流水線優(yōu)化調(diào)度，其啟動循環(huán)為(1,3),則該流水線周期P

7、為一調(diào)度 后的禁止集F(niodP)為 0 【答】周期尸= 1 + 3=4, F(modP) = {2}o 11 ?有一指令系統(tǒng)，共有7條指令。有兩種類型，一種為寄存器一寄存器型，一種為寄存器一存儲 器型。指令字長為8位或16位，不同類型指令字長不同。耍求變址范圍一 127到128。則該指令 系統(tǒng)最多可以編址一個通用寄存器，這時，最多可以編址一個變址寄存器。 【答】考慮寄存器一寄存器型指令字長為8位，有3條指令，除去2位操作碼，剩下各3位編 址8個通用寄存器。寄存器一存儲器型指令字長為16位，有4條指令，除去8位立即數(shù)，3位 寄 存器，4位操作碼，剩下1位用來編址2個變址寄存器。(所給答

8、案可能不是最優(yōu)的，但是掌握這 種指令的各個部分的長度如何計算的方法即可) 12?在100次內(nèi)存訪問中，一級cache缺失10次，二級cache缺失5次。則一級cache的全局命 中率為,二級cache的全局命中率為 0 【答】90%； 95%。 13?分別在以下條件時計算塊地址0110的索引(index),緩存有8塊，主存有16塊： a)二路組相聯(lián)一： b)直接映射0 【答】二路組相聯(lián)共8/2二4紐索引為2位。直接映射索引為3位。答案分別是10、H0o 14?緩存共有4塊，每塊Ibytc,采用LRU策略。訪問字序列0, L 4, 1.0, 4在下列情況下的命 中 率分別是： a

9、)直接映射 ： b)二路組相聯(lián)―O 【答】宜接映射 0 1 4 1 0 4 0 缺失(0) 缺失⑷ 缺失(0) 缺失⑷ 1 缺失⑴ 命中 2 3 命中率為1/6。二路組相聯(lián) 0 1 4 1 0 4 0A 缺失(0) 命中 0B 缺失⑷ 命中 1A 缺失⑴ 命中 1B 命中率為1/2。 三、判斷題：以下對MIPS架構(gòu)CPU的各改進方案，哪些修改了系統(tǒng)結(jié)構(gòu)(Archi

10、(cclurc),哪 些只 修改了實現(xiàn)(Implementation) ?填寫A或者h(yuǎn) ⑴將32位指令改為64位指令 ⑵加入指令Cache (3)增加流水線的段數(shù) (4)減去某些定向(forwarding)相關(guān)邏輯的實現(xiàn) (5)取消氣泡 ⑹增加16個額外的通用寄存器 (7)增加對某指令集的支持 [ft?] (DA (2)1 ⑶I (4)1 (5)1 (6)A (7) A四、解答題。 1 ?設(shè)計了一種優(yōu)化方案。 ? 優(yōu)化后的時鐘周期比未優(yōu)化的快15%； ? 未優(yōu)化的取/存指令占總數(shù)的30%： ? 優(yōu)化后的取/存指令比未優(yōu)化的少1/3,其它無變化： ? 未優(yōu)化

11、的所有指令均用1個時鐘周期：優(yōu)化的取/存指令用2個時鐘周期，其它指令用1個時 鐘周期。 (I)求優(yōu)化方案的平均CPI： <2)通過計算加速比，判斷哪個方案速度更快？ 【解】⑴不妨設(shè)優(yōu)化前共10條指令，取/存指令有3條。優(yōu)化后的取/存指令減少了 1條，即還 有2條取/存指令，其他7條不變，則總指令數(shù)變?yōu)?條。 7 7 優(yōu)化方案的半均CPI為fx2 + fxl = 1 - 22。 (2)假設(shè)我們考慮這10條指令運行的總時間。以未優(yōu)化的1個時鐘周期作為單位1,優(yōu)化前的 運 行時間為10,優(yōu)化后的總時間為(7 + 2x2)x6 85 = 935.說明優(yōu)化后的更快。但是如果考慮 平均每 條指

12、令的運行時間，那么優(yōu)化前的更快(因為優(yōu)化后平均每條指令的運行時間大于1)。 2?在有32個處理機的并行機上運行一段程序，獲得加速比26,己知該程序只有兩種運行方式：在所 有32個處理機上同時運行，或者只能由一個處理機執(zhí)行。請問程序中只能由一個處理機 執(zhí)行的部 分占多大比例？ 【解】設(shè)程序中只能由一個處理機執(zhí)行的部分占X,根據(jù)加速比定義有 —— =26 n X = 0. 007 3?某指令系統(tǒng)，有三地址指令4條，單地址指令255條，零地址指令16條。其指令字長12位， 地址碼3位。請問擴展編碼是否可行？如果單地址指令是254條呢？ 【解】(作業(yè)題》三地址指令共需耍9位地址碼，所以剩下

13、3位編碼操作碼，用4個碼點編碼 三 地址指令，剩余4個用于擴展。單地址指令操作碼有9位，可提供4X2〃=256個碼點，用其中255 個編碼單地址指令，剩下1個用于擴展。這時零地址指令只有8個碼點可用，所以擴展 編碼不可 行。 如果單地址指令是254條，那么還剩下2個用丁?擴展零地址指令，零地址指令口身的最低3位 各 可以編碼8條指令，共計16條。因此可以實現(xiàn)擴展編碼。 4?指令字長16位，有雙地址指令、單地址指令、零地址指令。地址都是6位。雙地址指令15條。 單地址與零地址條數(shù)相同。 (1)單地址與零地址指令最多能有多少條？ (2)給這三種指令分配操作碼。 【解】(1)雙地址指令地

14、址碼占12位，故操作碼有4位，共16個碼點，剩下1個碼點作擴展。 單地址指令的操作碼最長10位，零地址指令最長16位。對于單地址指令來說，最多有26-1 = 63 條，零地址指令也必須是63條。 (2) 雙地址指令：0000-1110： 單地址指令：I1H 000000-1H1 II1110： 零地址指令:I1H 1IHI1 000000-1IH 11H1I I111I0. 分別對按寫分配和不按寫分配兩種策略, 命中、缺失、命中、命中，命中率為60%。 缺失，命中率為20%0 5 ?全相聯(lián)Cache采用寫直達(dá)策略。初始Cache為空。 計算以下操作執(zhí)行后的命中率。 Write M

15、emElOO] Write MemElOO] Read Mein[200] Write Mem[200] Write MeinElOO] 【解】(PPT上的題)按寫分配：結(jié)果分別是缺失、 不按寫分配：結(jié)果分別是缺失、缺失、缺失.命中. 6, Cache采用組相連映像及變換。主存1MB, Cache 32KB.塊大小64B, Cache分為8組。 (I)寫出主存地址和緩存地址的格式(寫出各域及位數(shù))； ⑵若Cache的訪問周期為20ns,命中率0. 95,耍使加速比大于10,主存的訪問周期應(yīng)大于多少？ 【解】(1)Cache共有32KB/64B=5I2塊,分為8路,共有512/

16、8=64組。 主存地址：標(biāo)識8位，索引6位，塊內(nèi)地址6位。 . 緩存地址：？ 0⑵設(shè)主存訪問周期知，則加速比產(chǎn) 1皿皿。 7 ? Cache有4塊，每塊4字，采用直接映像法。初始時Cache為空。訪問的字地址序列為：0 ? 7」2 ? 9」6 ? 8」7Q12 ? 2。求cache命中率。 【解】訪問過程如下： 0 7 !2 9 16 8 17 0 12 2 0 Miss 0-3 Miss 16-19 Hit Miss 0~3 Hit 1 Miss 4~7 Hit 2 Miss

17、 8-11 3 Miss 12-15 Hit 命中率為40%o &一段程序有1000條指令，每條指令平均訪問存儲器L 5次，一級Cache訪問需要1ns.二級 Cache訪問需要10ns,主存訪問需要100nso這段程序運行完后共訪問二級Cache 90次，訪問主存 27次。 (1)求一級Cache和二級Cache命中率； (2)求存儲器等效訪問時間： (3)求每條指令因為訪問存儲器造成的半均延遲。 【解】(1)程序一共訪存1000x15 = 1500次，一級Cache缺失了 90次，故 on 一級Cache (

18、全局和局部)命中率為I——二0,91: 1000 二級Cache的局部命中率為1-*0. 7； 77二級Cache的全局命中率為1——=0, 973. 1000 ⑵平均訪存時間 1+0.09x(10+03x100) = 46nso ⑶每條指令因為訪問存儲器造成的平均延遲為1 ? 5x4 ? 6二6 ? 9nso 9?某系統(tǒng)Cache為4路組相聯(lián)，Cache大小為16K字節(jié)，塊大小為64字節(jié)。按寫分配。對于如 下 代碼： intM[4096]JJ; for(i = 0J< 10; i++) { for (j = 0; j < 4096; j++) { MLi]二 i+j;

19、(1)當(dāng)i=0時，發(fā)生的Cache缺失是屬于什么類型的缺失？發(fā)生了多少次？(4分) (2)運行完這段代碼，求整體缺失率。(4分) 【解】(1) 4096長度的整型數(shù)組為16K字節(jié)，每個塊為64字節(jié)，對應(yīng)16個整數(shù)。當(dāng)時， 對M各元素均是首次訪問，屬于必然缺失。發(fā)生警二256次。 16 (2)當(dāng)不再發(fā)生缺失。總訪存次數(shù)為40960次，故整體缺失率為2- = 0 - 00625o 40960 10.一個緩存，采用m路組相聯(lián)，順序訪問一個元素大小和緩存塊大小相等的數(shù)組，求數(shù)組長度 N a) >m b)

20、都是0,因為一個元素大小和緩存塊大小相等，而每次訪問一個元素時也只會載入一個 塊 大小的數(shù)據(jù)到Cache,故每次訪問都必然會缺失。 11.有以下指令(假設(shè)第一個操作數(shù)為寫回的寄存器) N1 ： load r0 a N2: add rl rO N3: load r2 b N4: inu] r3 r4 N5： and r4 r5 N6： add r2 r5 (1)請列出所有可能的數(shù)據(jù)沖突與結(jié)構(gòu)沖突。 (2)假設(shè)該處理器一個周期僅能進行一次訪存操作，畫出其執(zhí)行上述指令的時空圖?！窘狻?1)數(shù) 據(jù)沖突： N1 與 N2:rORAW N4 與 N5: r4 WAR N3 與 N6

21、: r2 WAW 結(jié)構(gòu)沖突：讀取內(nèi)存與取指沖突。 (2)假設(shè)數(shù)據(jù)沖突需耍插一個氣泡。 I 2 3 4 5 6 7 8 9 10 1; 12 !3 1 IF ID EXE MEM WB 2 IF ID stall EXE \IEM WB 3 IF ID EXE MEM WB 4 IF ID EXE MEM WB 5 stall IF ID EXE MEM

22、 WB 6 IF ID EXE MEM WB 說明：本答案中幾乎所有給出的時空圖與教材和課件上的形式不一樣，建議考試中嚴(yán)格遵循 教材和課件的標(biāo)準(zhǔn)(如教材圖3  8) I 一一 12?某CPU指令的運行分為取指?譯碼、執(zhí)行.寫結(jié)果四個階段，每段延遲均為5ns。 運行程序如下： K! M0VRLS4; R1G 向量長度 4 K2 Loop: MOV R2,A(R1); R2

23、!=0,則轉(zhuǎn)向 Loop K5 MOV SUM RO; SUM <- (RO) ?保存結(jié)果 (1)列出所有的數(shù)據(jù)相關(guān)。 (2)采用預(yù)測轉(zhuǎn)移不成功的靜態(tài)分支預(yù)測法，畫出流水線的時空圖，求吞吐率、加速比、譯碼段 的效率。 (3)采用預(yù)測轉(zhuǎn)移成功的靜態(tài)分支預(yù)測法，畫出流水線的時空圖，求吞吐率、加速比.執(zhí)行段的效 率。 【解】(1)K1 與 K2: RI RAW K2 9K3:R2 RAW KI 與 K4: RI WAW K2 與 K4: RI WAR K3 與 K5:R0 RAW (2)這里都假設(shè)只有分支預(yù)測出錯才會造成流水線暫停。 1 2 3 4 5 6 ?

24、? ? 16 17 18 19 20 KI IF ID EXE WB K2 IF ID EXE WB K3 IF ID EXE WB K4 IF ID EXE K2 stall IF ? ? K4 IF ID EXE WB K5 IF ID

25、EXE WB 吞吐率護。皿汽加速比斜E譯碼段的效率齊0.7。 ⑶ I 2 3 4 5 6 ? ? ? 13 14 !5 16 17 18 KI IF ID EXE WB K2 IF ID EXE WB K3 IF ID EXE WB K4 IF ID EXE K2 IF ID

26、 K4 IF ID EXE WB K5 Stall IF ID EXE WB 14 91 14 吞吐率礦0. 156n〃加速比礦1. 67,執(zhí)行段的效率茂二0. 78。 13.計算/二 加法需耍2個時鐘周期，乘法需要4個時鐘周期。 /~0 (1)串行處理器，有1個加法單元，1個乘法單元，但不能同時工作，求總的時鐘周期： ⑵SIMD處理器，有8個PE,標(biāo)號為0~7,連接為單向環(huán)，初始時和所在的處理機標(biāo)號 為j ? mod8, 每個PE向相鄰的PE轉(zhuǎn)移(數(shù)據(jù)傳輸)需耍1個周期，問最小

27、要多少個周期完成計算0 (3)一個SISD流水線，S4的輸出可以直接到輸入。一個乘法指令順序執(zhí)行SIS2s3 S4 一個加法指令執(zhí)行SlS4o每個1個周期。 (a)求最短運行時間? (b)畫出流水線的時空圖； (C)求S4的利用率。 【解】(1)10x4+9x2 = 58: (2)似乎今年沒有講到這里？ (3)這里假設(shè)流水線不能同時做加法和乘法，并11二者進行切換時必須排空流水線。如果該流水 線可以這樣的話，結(jié)果應(yīng)該更優(yōu)一點. (a) 10+(4-1) + 9 + (2-1) = 23： (b) I 2 3 4 5 6 ? ? ? !3 14 1

28、5 16 ? ? ? 22 23 !x Si s S3 S4 2x Si S2 S3 S4 3x Si Sz S3 S4 4x Si s： S3 5x Si S2 ■ ? !0x S4 ! +

29、 s. S4 2+ s2 S4 ■ ? 9— Si S4 (c) 10次乘法和9次加法都用了 S4,故利用率為19/23。 14.預(yù)約表如下: ? 2 3 4 5 Si 7 7 Sz V 7 S3 7 7 7 (1)求禁止集； (2)求初始沖突向量； (3)用預(yù)留算法實現(xiàn)優(yōu)化調(diào)度，若流水線時鐘周期I為30ns,求該流水線的最

30、大吞吐率。 【解】⑴禁I上集為｛1,2.4)： ⑵由 禁 止 集 得 到 初 始 沖 突 向 量 1011； (3)最小半均啟動距離為3,最小啟動循環(huán)為(3),插入非計算延遲得到最優(yōu)調(diào)度的預(yù)約表為 1 2 3 4 5 S, 7 7 Sz V S3 7 I 2 3 4 5 6 7 8 9 10 li Si i ■ 2 1 3 2 3 s. I 1 2 2 3 3 S3 I I I 2 2

31、 2 3 3 3 S4 I D 1 執(zhí)彳亍，味指令的吞吐率為^礦最大為塑喬礦礦亦- 77 15?一條有4個功能段的非線性流水線，每個功能段的延遲時間都相等，它的預(yù)約表如下 I 2 3 4 5 6 7 Si 1 7 S2 7 S3 7 V S4 V (1)求禁止集合和初始沖突向量： (2)畫出狀態(tài)圖； (3)找出最小啟動循環(huán)，求最小半均啟動時間：

32、 (4)如果用上一問的啟動循環(huán)連續(xù)完成10條指令，求實際的吞吐率： (5)用插入非計算延遲的方法可以得到最優(yōu)調(diào)度，求最優(yōu)調(diào)度的最大吞吐率?！窘狻?前兒問是 PPT上的例子) (1)禁止集合⑵4. 6}?初始沖突向量101010。 (2)第一輪： 初始沖突向量右移1位:010101vl0!010=llll!l； 初始沖突向量右移3位：000101vl01010=101111； 初始沖突向量右移5位:0000017101010=1010! 1： 初始沖突向量右移大于等于7位：OOOOOOvIOIOIO=101010。 第二輪： 對于中間沖突向量1IHI1,不做任何處理； 中間沖

33、突向量 10H11 右移 5 位:000001vl01010=1010!l： 中間沖突向量 101011 右移 3 位：000101vl01010=101111： 中間沖突向量 10I01I 右移 5 位：000001vl01010=1010!u 畫出狀態(tài)圖如下：  ⑶最小的啟動循環(huán)為(1. 7)秋3, 5),半均啟動距離為4。 ⑷采用循環(huán)(1.7)時, I 2 3 4 5 6 7 8 9 10 11 12 ? 39 40 s, 1 2 1 2 3 4 ? 一 ? 9 10 Sz I 2

34、 I 2 3 4 ? 一 ? 10 S3 I 2 1 2 3 4 ? ? Sj I 2 3 ? 必指令執(zhí)行的總用時為4。個周期，吞吐率為籍二吉 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ??? S, 1 2 3 4 1 5 2 6 3 7 4 .■ s. I 2 3 1 4 2 5 3 5 4 7 ■ S3

35、 1 2 I 3 2 4 3 5 4 6 5 ■— S4 I 2 3 4 5 5 ■ D 1 2 3 4 5 I 2 3 4 5 6 7 8 S, V s. S3 S4 D 16.在一臺每個時鐘周期發(fā)射兩條指令的超標(biāo)量處理機上運行下而一段程序，所有指令都要經(jīng) 過”

36、取指令S 〃譯碼”、〃執(zhí)行”和“寫結(jié)果〃4個階段，其中取指令譯碼〃和〃寫結(jié)果”三個階段 各為一個流水段，其延遲時間都為2ns。在“執(zhí)行”階段，LOAD操作和AND操作各延遲2ns, A加 操作延遲4ns, MUL操作延遲6ns. 4種操作部件各設(shè)置一個。ADD部件和MUL部件都采用流水線 結(jié)構(gòu)，每一級流水線的延遲時間都為2ns。 ;R01主存(A)單 執(zhí)行”條指令的吞吐鉗城遹忸麻的塑(6)+ 2)7■存〃 nl: LOAD RO. A ；J2-主存(B)單 n2: ADD RhRO 元；R3-(R3) x (R4) n3: LOAD R2 - B ：R41 & 依5) : R n4

37、: MUL R3 - R4 2-(R2) + (R5) n5: AND R4. R5 n6: ADD R2 ? R5 (1)列出這個程序中所有的數(shù)據(jù)相關(guān)，包括寫讀數(shù)據(jù)相關(guān)、讀寫數(shù)據(jù)相關(guān)和寫寫數(shù)據(jù)相關(guān)。 (2)如果所有運算型指令都在〃譯碼”流水段讀寄存器，在“寫結(jié)果?流水段寫寄存器，采用順序 發(fā)射順序完成調(diào)度方法，畫出流水線的時空圖，并計算執(zhí)行這個程序所用的時間。 (3)如果所有運算型指令都在〃譯碼”流水段讀寄存器，在〃寫結(jié)果〃流水段寫寄存器，采用順序發(fā) 射亂序完成調(diào)度方法，畫出流水線的時空圖和各條指令完成的時間圖，并計算執(zhí)行這個程序所用 的時間。 (4)如果每個操作部件的輸出端都有

38、直接數(shù)據(jù)通路與輸入端相連，采用順序發(fā)射亂序完成調(diào)度方 法，畫出流水線的時空圖和各條指令完成的時間圖，并計算執(zhí)行這個程序所用的時間。 【解】(1)指令nl與n2之間有關(guān)丁?寄存器R0的寫讀數(shù)據(jù)相關(guān)， 指令n3與n6之間有關(guān)于寄存器R2的寫讀數(shù)據(jù)相關(guān)， 指令n4與n5之間有關(guān)于寄存器R4的讀寫數(shù)據(jù)相關(guān)， 指令n3與n6之間有關(guān)于寄存器R2的寫寫數(shù)據(jù)相關(guān)。 ⑵采用順序發(fā)射順序完成調(diào)度方法的流水線時空圖。 執(zhí)行這個程序共用261VS0 1 2 3 4 5 6 7 5 IF1 XD1 LS WRI 1 > W2 n)2

39、 ADD ADD yw2 IF1 W1 LS WRI IF2 m2 MUL MUL MUL WR2 m W1 AND WRI ] IF2 DD2 ADD ADD WR2 (3)采用順序發(fā)射亂序完成調(diào)度方法的流水線時空圖。 N1 M2 H3 N4 N5 各條指令完成的時間圖 時鐘周期 4 5 6 7 8 9 流水線1 nl n3 n5 流水線2 n4 n2 n6 執(zhí)行這個程序共用18ns。 ⑷采用

40、順序發(fā)射亂序完成調(diào)度方法的流水線時空圖。 1 1 2 3 4 5 7 8 n W1 LS W1 > in n>2 搟 ADD QD WR2 IF1 W1 LS W1 1F2 0)2 MUL MUL MOL WK2 1 IF3 ID1 AND WEI f ff2 nw 砂 ADD WRI 1 17?下面一段程序是計算浮點向量運算Y=a*X + Y的，其中X和Y都是100維向量。采用循 環(huán) 展開的方式使得執(zhí)行過程沒有stalk那么最少需要展

41、開兒次？寫出展開的程序。 LOOP: L  D MUL.D L ? D ADD.D S ? D DSUBI DSUBI BNEZ F0 ? O(R1) FOJO, F2 F4 ? 0 (R2) FOJO, F4 F0 ? 0(R2) RLRh#8 R2R2#8 RLLOOP 注意：本題原來的題干有錯，大家只要掌握循環(huán)展開的方法即可，一種可能的答案如下 0本題 在PPT匕也有，可以看一下PPT上的題目和答案。 【解】將循環(huán)展開兩次，進行指令調(diào)度，即可以消除延遲，代碼如下： LOOP： L  D FO, 0 CRD L - D FIO, -8 (RD MUL

42、.D FO, FO, F2 MUL.D FIO, FIO, F2 L - D F4, 0 (R2) L - D F14, -8 (R2) ADD.D FO, FO, F4 ADD.D FIO, FIO, FI4 DSUBI RH Rb #16 SQ 0 CR2) , FO DSUBI R2> R2, #16 BNEZ RH LOOP S - D 8 CR2) , FIO 假設(shè)：LOOP: LD FO.O(Rl) (stall) MUL.D FOJO, F2 L ? D F4J (R2) (stall) ADD.D FO. F

43、O, F4 (stall) (stall) S ? D FO - 0 (R2) DSUBI RLRh#8 DSUBI R2R2#8 BNEZ RLLOOP (stall) 1&分支預(yù)測。 (1)畫出2位飽和計數(shù)器的狀態(tài) 圖。 (2)已知如下指令序列 地址 目標(biāo)地址 是否跳轉(zhuǎn) bl 否 **??01 bl 否 bl 是 b2 否 b2 是 己知初始BHT歷史為00, BHT項全為01,求執(zhí)行完上述程序后的BHT。 (3)簡要說明為何引入BTB會使得CPI下降。 【解】⑴見教材134頁圖5」Oo (2

44、)BHT一般就用PC的后幾位作為表格的索引，查出里面的預(yù)測位。這里的預(yù)測當(dāng)長度為2時就是 上題中的飽和計數(shù)器，用 00. 01. 10、H 分別表示 strongly not takenweakly not taken weakly taken> strongly takeno 可參考某中文 b! oghttp：//blog, csdn. net/edonlii/article/details/8754724o 執(zhí)行完上述程序后的 BHT 為 索引 值(計數(shù)器) 01 01 10 0! (3)在經(jīng)典的5段流水線中，ID段宋尾才能獲得分支口標(biāo)地址。而采用BTB可以提前在IF段 就

45、 知道這些信息，分支開銷就可以減少為0。 19?一個含有8個輸入端的系統(tǒng)采用三層<7-開關(guān)鏈接，使用開關(guān)控制。(可參見教材286頁圖 921) 如開關(guān)處在0,則會不交換，如開關(guān)為1,則會發(fā)生交換。 (1)若開關(guān)處在000狀態(tài)，則0號鏈接？ (2)若最左開關(guān)為0,那么1號不可能鏈接到哪些處理器？ 【解】(1)0號； M010 J011 —000 J 001 (2)分類討論后面兩個開關(guān)的狀態(tài)，得出i號的變換圖： >101— 001—^010—*010—^100~ ^100—00b I號不可能鏈接到4、7號處理器。 20?在多處理機系統(tǒng)中，采用寫回法的寫作廢(write

46、invalidate)總線監(jiān)聽協(xié)議，參見教材310頁 圖106的狀態(tài)機。 (1)給出L S狀態(tài)的定義，并說明什么時候可以確定發(fā)生了 Cache不一致的情況。 (2)假設(shè)有兩個地址A和B (映射到不同的Cache塊中)，兩個處理機R和P2,初始時Cache全為 空，根據(jù)特定的訪問序列，補全下表(無消息用丫代替，CPU事件RdM = Read Miss> RdH =Read Hib WrM = Write Miss WrH = Write Hit；總線消息 WrMs = Write Miss RdMs = Read Miss) 操作 A B 消息/操作 Pl P2 Pl P2

47、 Pl P2 Pj： R A S I I I RdM/RdMs RdMs/- P2： W A 10 P2： R A Pl： W A20 Pl： WB 10 P2： WB20 【解】(1)M表示該塊已經(jīng)被修改過，并11未寫入存儲器。【表示該塊內(nèi)容無效。S表示該塊婆 么處于共享狀態(tài)，即多個處理器中都有其副本且都與存儲器相同，或者該塊只在一個處理器中有 副本且與存儲器相同。 ⑵ 操作 A B 消息/操作 Pi P2 Pl P2 Pl P2 Pl； R A s I I I RdM/RdMs RdMs/- P2： W A 10 I M I I WrMs/- WrM/WrMs  P2： RA I M I I RdHA Pl： W A20 M I I I WrM/WrMs WrMs/寫回 PI： WB 10 M I M I WrM/WrMs WrMs/- Pz： WB20 M I I M WrMs/寫回 WrM/WrMs