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

計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)往年考題參考答案僅供參考！一、簡(jiǎn)答題L指令流水計(jì)算機(jī)中，采用獨(dú)立的指令緩存與數(shù)據(jù)緩存對(duì)系統(tǒng)性能有什么好處?！敬稹拷鉀Q訪(fǎng)存和村又指的結(jié)構(gòu)沖突，加速流水線(xiàn)：數(shù)據(jù)和指令的訪(fǎng)問(wèn)有所不問(wèn)，設(shè)置單獨(dú) 的Cache有利于提高命中率，減少平均訪(fǎng)存時(shí)間。2什么是指令動(dòng)態(tài)調(diào)度？使用寄存器重命名能夠解決哪些數(shù)據(jù)沖突？【答】指令動(dòng)態(tài)調(diào)度是指在程序執(zhí)行過(guò)程中，依靠專(zhuān)門(mén)的碩件隊(duì)代碼進(jìn)行調(diào)度。使用寄存器重 命名能夠解決名相關(guān)(反相關(guān)、輸出相關(guān)).3 從數(shù)據(jù)和指令的角度，分別說(shuō)明引起時(shí)間與空間局部性的原因?！敬稹繑?shù)據(jù)：對(duì)于剛被訪(fǎng)問(wèn)過(guò)的數(shù)據(jù)，很有可能再次訪(fǎng)問(wèn)它或者它附近的數(shù)據(jù)。指令：順序執(zhí) 行的可能性較大。4 .直接用虛擬地址索引緩存會(huì)存在什么問(wèn)題？【答】多個(gè)虛擬地址可能指向同一物理地址。5多處理機(jī)為什么耍維護(hù)緩存一致性？【答】每個(gè)處理機(jī)都有一份自己的Cache,但是這些Cache都映射同一個(gè)物理主存，當(dāng)一個(gè)處 理 機(jī)修改己Cache的數(shù)據(jù)時(shí)，其他處理機(jī)中該部分的數(shù)據(jù)就不是最新的，造成不一致性。二.填空題1 16個(gè)處理器組成的網(wǎng)絡(luò)，使用洸牌函數(shù)相聯(lián)，那么與10號(hào)相聯(lián)的是【答】10= (1010) 2,循環(huán)左移一位得(0101) 2=5o2 有16個(gè)處理器，編號(hào)為0,1,，15,先經(jīng)過(guò)+3*Pl2+3,再經(jīng)過(guò)混洗變換后，11號(hào)處理器連向一號(hào)處理器。【答】H經(jīng)過(guò)PM2*3得到(H + 2")modI6=3, 3再經(jīng)過(guò)混洗變換得6。3使用混洙交換單級(jí)網(wǎng)絡(luò)將一個(gè)PE中的數(shù)據(jù)播送到所有16個(gè)PE中，需耍一次交換，需要一混洗。 假設(shè)每步只能進(jìn)行混洗或交換中的一種變換?！敬稹?次交換，3次混洗04 16個(gè)處理器組成的網(wǎng)絡(luò)，采用PM2切PM22鏈接，網(wǎng)絡(luò)直徑為，結(jié)點(diǎn)度為 【答】有結(jié)論：2”個(gè)處理器組成的網(wǎng)絡(luò)，采用PM2兇，PM2如2鏈接，實(shí)現(xiàn)各處理單元之間上 下左右互聯(lián)。網(wǎng)絡(luò)直徑為3,結(jié)點(diǎn)度為4 (?)o5可以在向量與標(biāo)量工作模式中切換的處理器，處理向量時(shí)效率是處理標(biāo)量的9倍。已知運(yùn)行一 段程序時(shí)有1/4的時(shí)間在運(yùn)行向量指令，向量指令的比例為 【答】設(shè)向量指令占比I則一-一二-.解得x =x+9(i-x) 446 .向量處理器在串行模式執(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三種指令的周期如下PlP2AI2B23C44一段程序中A占60%, B占30%, C占10%,分別求P1和P2運(yùn)行該程序時(shí)的CPL【答】P1運(yùn)行該程序的CPI為0. 6x1 + 03x2 + 0, 1x4 = 1, 6 . P?運(yùn)行該程序的CPI為0. 6x2 +03x3 + 0, 1x4 = 2. 5 o13&己知一處理器指令緩存不命中率為2%,數(shù)據(jù)緩存不命中率為4%,不命中代價(jià)為100周期。命中 時(shí)，CPI為2,那么執(zhí)行一段含有Load/Save指令各15%的程序時(shí)，其CPI為。【答】每條指令出現(xiàn)不命中的概率是0,02+是x0. 04=0-032.故其CPI為0.032為00 + 2 = 5. 2 o9五段流水線(xiàn)CPU,各段延遲時(shí)間分別為2 - 2ns25ns, 2 - 2ns23ns23ns連續(xù)執(zhí)行10條指令，需要 的時(shí)間為一，該CPU最高頻率為MHzo【答】各段不等長(zhǎng)的流水線(xiàn)計(jì)算公式參見(jiàn)教材 58 頁(yè)(時(shí)空?qǐng)D如如 38),需要的時(shí)間為 max 222 5222323 x (10-1) + (2-2 + 2- 5 + 2- 2 + 2 3+2 - 3) = 34ns,最大周期為2 5ns,即頻率 為400MHz10采用預(yù)留算法實(shí)現(xiàn)的非線(xiàn)性流水線(xiàn)優(yōu)化調(diào)度，其啟動(dòng)循環(huán)為(1,3),則該流水線(xiàn)周期P為一調(diào)度 后的禁止集F(niodP)為 0【答】周期尸= 1 + 3=4, F(modP) = 2o11 有一指令系統(tǒng)，共有7條指令。有兩種類(lèi)型，一種為寄存器一寄存器型，一種為寄存器一存儲(chǔ) 器型。指令字長(zhǎng)為8位或16位，不同類(lèi)型指令字長(zhǎng)不同。耍求變址范圍一 127到128。則該指令 系統(tǒng)最多可以編址一個(gè)通用寄存器，這時(shí)，最多可以編址一個(gè)變址寄存器?！敬稹靠紤]寄存器一寄存器型指令字長(zhǎng)為8位，有3條指令，除去2位操作碼，剩下各3位編 址8個(gè)通用寄存器。寄存器一存儲(chǔ)器型指令字長(zhǎng)為16位，有4條指令，除去8位立即數(shù)，3位 寄 存器，4位操作碼，剩下1位用來(lái)編址2個(gè)變址寄存器。(所給答案可能不是最優(yōu)的，但是掌握這 種指令的各個(gè)部分的長(zhǎng)度如何計(jì)算的方法即可)12在100次內(nèi)存訪(fǎng)問(wèn)中，一級(jí)cache缺失10次，二級(jí)cache缺失5次。則一級(jí)cache的全局命 中率為,二級(jí)cache的全局命中率為 0【答】90%； 95%。13分別在以下條件時(shí)計(jì)算塊地址0110的索引(index),緩存有8塊，主存有16塊：a)二路組相聯(lián)一：b)直接映射0【答】二路組相聯(lián)共8/2二4紐索引為2位。直接映射索引為3位。答案分別是10、H0o14緩存共有4塊，每塊Ibytc,采用LRU策略。訪(fǎng)問(wèn)字序列0, L 4, 1.0, 4在下列情況下的命 中 率分別是：a)直接映射 ：b)二路組相聯(lián)O【答】宜接映射0141040缺失(0)缺失缺失(0)缺失1缺失命中23命中率為1/6。二路組相聯(lián)0141040A缺失(0)命中0B缺失命中1A缺失命中1B命中率為1/2。三、判斷題：以下對(duì)MIPS架構(gòu)CPU的各改進(jìn)方案，哪些修改了系統(tǒng)結(jié)構(gòu)(Archi(cclurc),哪 些只 修改了實(shí)現(xiàn)(Implementation) ?填寫(xiě)A或者h(yuǎn)將32位指令改為64位指令加入指令Cache(3)增加流水線(xiàn)的段數(shù)(4)減去某些定向(forwarding)相關(guān)邏輯的實(shí)現(xiàn)(5)取消氣泡增加16個(gè)額外的通用寄存器(7)增加對(duì)某指令集的支持ft? (DA(2)1I(4)1(5)1(6)A(7) A四、解答題。1 設(shè)計(jì)了一種優(yōu)化方案。 優(yōu)化后的時(shí)鐘周期比未優(yōu)化的快15%； 未優(yōu)化的取/存指令占總數(shù)的30%： 優(yōu)化后的取/存指令比未優(yōu)化的少1/3,其它無(wú)變化： 未優(yōu)化的所有指令均用1個(gè)時(shí)鐘周期：優(yōu)化的取/存指令用2個(gè)時(shí)鐘周期，其它指令用1個(gè)時(shí) 鐘周期。(I)求優(yōu)化方案的平均CPI：<2)通過(guò)計(jì)算加速比，判斷哪個(gè)方案速度更快？【解】不妨設(shè)優(yōu)化前共10條指令，取/存指令有3條。優(yōu)化后的取/存指令減少了 1條，即還 有2條取/存指令，其他7條不變，則總指令數(shù)變?yōu)?條。77優(yōu)化方案的半均CPI為fx2 + fxl = 1 - 22。(2)假設(shè)我們考慮這10條指令運(yùn)行的總時(shí)間。以未優(yōu)化的1個(gè)時(shí)鐘周期作為單位1,優(yōu)化前的 運(yùn) 行時(shí)間為10,優(yōu)化后的總時(shí)間為(7 + 2x2)x6 85 = 935.說(shuō)明優(yōu)化后的更快。但是如果考慮 平均每 條指令的運(yùn)行時(shí)間，那么優(yōu)化前的更快(因?yàn)閮?yōu)化后平均每條指令的運(yùn)行時(shí)間大于1)。2在有32個(gè)處理機(jī)的并行機(jī)上運(yùn)行一段程序，獲得加速比26,己知該程序只有兩種運(yùn)行方式：在所 有32個(gè)處理機(jī)上同時(shí)運(yùn)行，或者只能由一個(gè)處理機(jī)執(zhí)行。請(qǐng)問(wèn)程序中只能由一個(gè)處理機(jī) 執(zhí)行的部 分占多大比例？【解】設(shè)程序中只能由一個(gè)處理機(jī)執(zhí)行的部分占X,根據(jù)加速比定義有=26 n X = 0. 0073某指令系統(tǒng)，有三地址指令4條，單地址指令255條，零地址指令16條。其指令字長(zhǎng)12位， 地址碼3位。請(qǐng)問(wèn)擴(kuò)展編碼是否可行？如果單地址指令是254條呢？【解】(作業(yè)題三地址指令共需耍9位地址碼，所以剩下3位編碼操作碼，用4個(gè)碼點(diǎn)編碼 三 地址指令，剩余4個(gè)用于擴(kuò)展。單地址指令操作碼有9位，可提供4X2=256個(gè)碼點(diǎn)，用其中255 個(gè)編碼單地址指令，剩下1個(gè)用于擴(kuò)展。這時(shí)零地址指令只有8個(gè)碼點(diǎn)可用，所以擴(kuò)展 編碼不可 行。如果單地址指令是254條，那么還剩下2個(gè)用丁擴(kuò)展零地址指令，零地址指令口身的最低3位 各 可以編碼8條指令，共計(jì)16條。因此可以實(shí)現(xiàn)擴(kuò)展編碼。4指令字長(zhǎng)16位，有雙地址指令、單地址指令、零地址指令。地址都是6位。雙地址指令15條。 單地址與零地址條數(shù)相同。(1)單地址與零地址指令最多能有多少條？(2)給這三種指令分配操作碼。【解】(1)雙地址指令地址碼占12位，故操作碼有4位，共16個(gè)碼點(diǎn)，剩下1個(gè)碼點(diǎn)作擴(kuò)展。單地址指令的操作碼最長(zhǎng)10位，零地址指令最長(zhǎng)16位。對(duì)于單地址指令來(lái)說(shuō)，最多有26-1 = 63 條，零地址指令也必須是63條。(2) 雙地址指令：0000-1110：?jiǎn)蔚刂分噶睿篒1H 000000-1H1 II1110： 零地址指令:I1H 1IHI1 000000-1IH 11H1I I111I0.分別對(duì)按寫(xiě)分配和不按寫(xiě)分配兩種策略,命中、缺失、命中、命中，命中率為60%。 缺失，命中率為20%05 全相聯(lián)Cache采用寫(xiě)直達(dá)策略。初始Cache為空。 計(jì)算以下操作執(zhí)行后的命中率。Write MemElOOWrite MemElOORead Mein200Write Mem200Write MeinElOO【解】(PPT上的題)按寫(xiě)分配：結(jié)果分別是缺失、 不按寫(xiě)分配：結(jié)果分別是缺失、缺失、缺失.命中.6, Cache采用組相連映像及變換。主存1MB, Cache 32KB.塊大小64B, Cache分為8組。(I)寫(xiě)出主存地址和緩存地址的格式(寫(xiě)出各域及位數(shù))；若Cache的訪(fǎng)問(wèn)周期為20ns,命中率0. 95,耍使加速比大于10,主存的訪(fǎng)問(wèn)周期應(yīng)大于多少？【解】(1)Cache共有32KB/64B=5I2塊,分為8路,共有512/8=64組。主存地址：標(biāo)識(shí)8位，索引6位，塊內(nèi)地址6位。.緩存地址：？ 0設(shè)主存訪(fǎng)問(wèn)周期知，則加速比產(chǎn) 1皿皿。7 Cache有4塊，每塊4字，采用直接映像法。初始時(shí)Cache為空。訪(fǎng)問(wèn)的字地址序列為：0 72 96 87Q12 2。求cache命中率。【解】訪(fǎng)問(wèn)過(guò)程如下：07!291681701220Miss 0-3Miss 16-19HitMiss 03Hit1Miss 47Hit2Miss8-113Miss 12-15Hit命中率為40%o&一段程序有1000條指令，每條指令平均訪(fǎng)問(wèn)存儲(chǔ)器L 5次，一級(jí)Cache訪(fǎng)問(wèn)需要1ns.二級(jí)Cache訪(fǎng)問(wèn)需要10ns,主存訪(fǎng)問(wèn)需要100nso這段程序運(yùn)行完后共訪(fǎng)問(wèn)二級(jí)Cache 90次，訪(fǎng)問(wèn)主存 27次。(1)求一級(jí)Cache和二級(jí)Cache命中率；(2)求存儲(chǔ)器等效訪(fǎng)問(wèn)時(shí)間：(3)求每條指令因?yàn)樵L(fǎng)問(wèn)存儲(chǔ)器造成的半均延遲?！窘狻?1)程序一共訪(fǎng)存1000x15 = 1500次，一級(jí)Cache缺失了 90次，故on一級(jí)Cache (全局和局部)命中率為I二0,91: 1000二級(jí)Cache的局部命中率為1-*0. 7；77二級(jí)Cache的全局命中率為1=0, 973.1000平均訪(fǎng)存時(shí)間 1+0.09x(10+03x100) = 46nso每條指令因?yàn)樵L(fǎng)問(wèn)存儲(chǔ)器造成的平均延遲為1 5x4 6二6 9nso9某系統(tǒng)Cache為4路組相聯(lián)，Cache大小為16K字節(jié)，塊大小為64字節(jié)。按寫(xiě)分配。對(duì)于如 下 代碼：intM4096JJ;for(i = 0J< 10; i+) for (j = 0; j < 4096; j+) MLi二 i+j;(1)當(dāng)i=0時(shí)，發(fā)生的Cache缺失是屬于什么類(lèi)型的缺失？發(fā)生了多少次？(4分)(2)運(yùn)行完這段代碼，求整體缺失率。(4分)【解】(1) 4096長(zhǎng)度的整型數(shù)組為16K字節(jié)，每個(gè)塊為64字節(jié)，對(duì)應(yīng)16個(gè)整數(shù)。當(dāng)時(shí)，對(duì)M各元素均是首次訪(fǎng)問(wèn)，屬于必然缺失。發(fā)生警二256次。16(2)當(dāng)不再發(fā)生缺失?？傇L(fǎng)存次數(shù)為40960次，故整體缺失率為2- = 0 - 00625o4096010.一個(gè)緩存，采用m路組相聯(lián)，順序訪(fǎng)問(wèn)一個(gè)元素大小和緩存塊大小相等的數(shù)組，求數(shù)組長(zhǎng)度Na) >mb) <ni且緩存采用a) LRUb) OPT時(shí)的命中率?！窘狻慷际?,因?yàn)橐粋€(gè)元素大小和緩存塊大小相等，而每次訪(fǎng)問(wèn)一個(gè)元素時(shí)也只會(huì)載入一個(gè) 塊 大小的數(shù)據(jù)到Cache,故每次訪(fǎng)問(wèn)都必然會(huì)缺失。11.有以下指令(假設(shè)第一個(gè)操作數(shù)為寫(xiě)回的寄存器)N1 ： load r0 aN2: add rl rON3: load r2 bN4: inu r3 r4N5： and r4 r5N6： add r2 r5(1)請(qǐng)列出所有可能的數(shù)據(jù)沖突與結(jié)構(gòu)沖突。(2)假設(shè)該處理器一個(gè)周期僅能進(jìn)行一次訪(fǎng)存操作，畫(huà)出其執(zhí)行上述指令的時(shí)空?qǐng)D?！窘狻?1)數(shù) 據(jù)沖突：N1 與 N2:rORAWN4 與 N5: r4 WARN3 與 N6: r2 WAW結(jié)構(gòu)沖突：讀取內(nèi)存與取指沖突。(2)假設(shè)數(shù)據(jù)沖突需耍插一個(gè)氣泡。I23456789101;12!31IFIDEXEMEMWB2IFIDstallEXEIEMWB3IFIDEXEMEMWB4IFIDEXEMEMWB5stallIFIDEXEMEMWB6IFIDEXEMEMWB說(shuō)明：本答案中幾乎所有給出的時(shí)空?qǐng)D與教材和課件上的形式不一樣，建議考試中嚴(yán)格遵循教材和課件的標(biāo)準(zhǔn)(如教材圖3 8) I一一12某CPU指令的運(yùn)行分為取指譯碼、執(zhí)行.寫(xiě)結(jié)果四個(gè)階段，每段延遲均為5ns。運(yùn)行程序如下：K!M0VRLS4;R1G 向量長(zhǎng)度 4K2 Loop: MOV R2,A(R1); R2 < A 向量的一個(gè)元素K3ADD RO. R2:RO <- (R0) + (R2)K4DNE RhLoop;Rl一(RI)-h 若(RI) !=0,則轉(zhuǎn)向 LoopK5MOV SUM RO; SUM <- (RO) 保存結(jié)果(1)列出所有的數(shù)據(jù)相關(guān)。(2)采用預(yù)測(cè)轉(zhuǎn)移不成功的靜態(tài)分支預(yù)測(cè)法，畫(huà)出流水線(xiàn)的時(shí)空?qǐng)D，求吞吐率、加速比、譯碼段 的效率。(3)采用預(yù)測(cè)轉(zhuǎn)移成功的靜態(tài)分支預(yù)測(cè)法，畫(huà)出流水線(xiàn)的時(shí)空?qǐng)D，求吞吐率、加速比.執(zhí)行段的效 率。【解】(1)K1 與 K2: RI RAWK2 9K3:R2 RAWKI 與 K4: RI WAWK2 與 K4: RI WARK3 與 K5:R0 RAW(2)這里都假設(shè)只有分支預(yù)測(cè)出錯(cuò)才會(huì)造成流水線(xiàn)暫停。123456 1617181920KIIFIDEXEWBK2IFIDEXEWBK3IFIDEXEWBK4IFIDEXEK2stallIF K4IFIDEXEWBK5IFIDEXEWB吞吐率護(hù)。皿汽加速比斜E譯碼段的效率齊0.7。 I23456 1314!5161718KIIFIDEXEWBK2IFIDEXEWBK3IFIDEXEWBK4IFIDEXEK2IFIDK4IFIDEXEWBK5StallIFIDEXEWB149114吞吐率礦0. 156n加速比礦1. 67,執(zhí)行段的效率茂二0. 78。13.計(jì)算/二加法需耍2個(gè)時(shí)鐘周期，乘法需要4個(gè)時(shí)鐘周期。/0(1)串行處理器，有1個(gè)加法單元，1個(gè)乘法單元，但不能同時(shí)工作，求總的時(shí)鐘周期：SIMD處理器，有8個(gè)PE,標(biāo)號(hào)為07,連接為單向環(huán)，初始時(shí)和所在的處理機(jī)標(biāo)號(hào) 為j mod8, 每個(gè)PE向相鄰的PE轉(zhuǎn)移(數(shù)據(jù)傳輸)需耍1個(gè)周期，問(wèn)最小要多少個(gè)周期完成計(jì)算0(3)一個(gè)SISD流水線(xiàn)，S4的輸出可以直接到輸入。一個(gè)乘法指令順序執(zhí)行SIS2s3 S4一個(gè)加法指令執(zhí)行SlS4o每個(gè)1個(gè)周期。(a)求最短運(yùn)行時(shí)間?(b)畫(huà)出流水線(xiàn)的時(shí)空?qǐng)D；(C)求S4的利用率?！窘狻?1)10x4+9x2 = 58:(2)似乎今年沒(méi)有講到這里？(3)這里假設(shè)流水線(xiàn)不能同時(shí)做加法和乘法，并11二者進(jìn)行切換時(shí)必須排空流水線(xiàn)。如果該流水 線(xiàn)可以這樣的話(huà)，結(jié)果應(yīng)該更優(yōu)一點(diǎn).(a) 10+(4-1) + 9 + (2-1) = 23：(b)I23456 !3141516 2223!xSisS3S42xSiS2S3S43xSiSzS3S44xSis：S35xSiS2 !0xS4! +s.S42+s2S4 9SiS4(c) 10次乘法和9次加法都用了 S4,故利用率為19/23。14.預(yù)約表如下:2345Si77SzV7S3777(1)求禁止集；(2)求初始沖突向量；(3)用預(yù)留算法實(shí)現(xiàn)優(yōu)化調(diào)度，若流水線(xiàn)時(shí)鐘周期I為30ns,求該流水線(xiàn)的最大吞吐率?！窘狻拷鸌上集為1,2.4)：由 禁 止 集 得 到 初 始 沖 突 向 量 1011；(3)最小半均啟動(dòng)距離為3,最小啟動(dòng)循環(huán)為(3),插入非計(jì)算延遲得到最優(yōu)調(diào)度的預(yù)約表為12345S,77SzVS37I2345678910liSii21323s.I12233S3III222333S4ID1執(zhí)彳亍，味指令的吞吐率為礦最大為塑喬礦礦亦- 7715一條有4個(gè)功能段的非線(xiàn)性流水線(xiàn)，每個(gè)功能段的延遲時(shí)間都相等，它的預(yù)約表如下I234567Si17S27S37VS4V(1)求禁止集合和初始沖突向量：(2)畫(huà)出狀態(tài)圖；(3)找出最小啟動(dòng)循環(huán)，求最小半均啟動(dòng)時(shí)間：(4)如果用上一問(wèn)的啟動(dòng)循環(huán)連續(xù)完成10條指令，求實(shí)際的吞吐率：(5)用插入非計(jì)算延遲的方法可以得到最優(yōu)調(diào)度，求最優(yōu)調(diào)度的最大吞吐率?！窘狻?前兒?jiǎn)柺?PPT上的例子)(1)禁止集合4. 6初始沖突向量101010。(2)第一輪：初始沖突向量右移1位:010101vl0!010=llll!l；初始沖突向量右移3位：000101vl01010=101111；初始沖突向量右移5位:0000017101010=1010! 1：初始沖突向量右移大于等于7位：OOOOOOvIOIOIO=101010。第二輪：對(duì)于中間沖突向量1IHI1,不做任何處理；中間沖突向量 10H11 右移 5 位:000001vl01010=1010!l：中間沖突向量 101011 右移 3 位：000101vl01010=101111：中間沖突向量 10I01I 右移 5 位：000001vl01010=1010!u畫(huà)出狀態(tài)圖如下：最小的啟動(dòng)循環(huán)為(1. 7)秋3, 5),半均啟動(dòng)距離為4。采用循環(huán)(1.7)時(shí),I234567891011123940s,121234 一 910SzI2I234 一 10S3I21234 SjI23必指令執(zhí)行的總用時(shí)為4。個(gè)周期，吞吐率為籍二吉1234567891011121314S,12341526374.s.I2314253547S312I32435465S4I23455D12345I2345678S,Vs.S3S4D16.在一臺(tái)每個(gè)時(shí)鐘周期發(fā)射兩條指令的超標(biāo)量處理機(jī)上運(yùn)行下而一段程序，所有指令都要經(jīng) 過(guò)”取指令S 譯碼”、執(zhí)行”和“寫(xiě)結(jié)果4個(gè)階段，其中取指令譯碼和寫(xiě)結(jié)果”三個(gè)階段 各為一個(gè)流水段，其延遲時(shí)間都為2ns。在“執(zhí)行”階段，LOAD操作和AND操作各延遲2ns, A加 操作延遲4ns, MUL操作延遲6ns. 4種操作部件各設(shè)置一個(gè)。ADD部件和MUL部件都采用流水線(xiàn) 結(jié)構(gòu)，每一級(jí)流水線(xiàn)的延遲時(shí)間都為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) : Rn4: MUL R3 - R4 2-(R2) + (R5)n5: AND R4. R5n6: ADD R2 R5(1)列出這個(gè)程序中所有的數(shù)據(jù)相關(guān)，包括寫(xiě)讀數(shù)據(jù)相關(guān)、讀寫(xiě)數(shù)據(jù)相關(guān)和寫(xiě)寫(xiě)數(shù)據(jù)相關(guān)。(2)如果所有運(yùn)算型指令都在譯碼”流水段讀寄存器，在“寫(xiě)結(jié)果流水段寫(xiě)寄存器，采用順序 發(fā)射順序完成調(diào)度方法，畫(huà)出流水線(xiàn)的時(shí)空?qǐng)D，并計(jì)算執(zhí)行這個(gè)程序所用的時(shí)間。(3)如果所有運(yùn)算型指令都在譯碼”流水段讀寄存器，在寫(xiě)結(jié)果流水段寫(xiě)寄存器，采用順序發(fā) 射亂序完成調(diào)度方法，畫(huà)出流水線(xiàn)的時(shí)空?qǐng)D和各條指令完成的時(shí)間圖，并計(jì)算執(zhí)行這個(gè)程序所用 的時(shí)間。(4)如果每個(gè)操作部件的輸出端都有直接數(shù)據(jù)通路與輸入端相連，采用順序發(fā)射亂序完成調(diào)度方 法，畫(huà)出流水線(xiàn)的時(shí)空?qǐng)D和各條指令完成的時(shí)間圖，并計(jì)算執(zhí)行這個(gè)程序所用的時(shí)間。【解】(1)指令nl與n2之間有關(guān)丁寄存器R0的寫(xiě)讀數(shù)據(jù)相關(guān)，指令n3與n6之間有關(guān)于寄存器R2的寫(xiě)讀數(shù)據(jù)相關(guān)，指令n4與n5之間有關(guān)于寄存器R4的讀寫(xiě)數(shù)據(jù)相關(guān)，指令n3與n6之間有關(guān)于寄存器R2的寫(xiě)寫(xiě)數(shù)據(jù)相關(guān)。采用順序發(fā)射順序完成調(diào)度方法的流水線(xiàn)時(shí)空?qǐng)D。執(zhí)行這個(gè)程序共用261VS012345675IF1XD1LSWRI 1>W2n)2ADDADDyw2IF1W1LSWRIIF2m2MULMULMULWR2mW1ANDWRIIF2DD2ADDADDWR2(3)采用順序發(fā)射亂序完成調(diào)度方法的流水線(xiàn)時(shí)空?qǐng)D。N1M2H3N4N5各條指令完成的時(shí)間圖時(shí)鐘周期456789流水線(xiàn)1nln3n5流水線(xiàn)2n4n2n6執(zhí)行這個(gè)程序共用18ns。采用順序發(fā)射亂序完成調(diào)度方法的流水線(xiàn)時(shí)空?qǐng)D。1123457 8nW1LSW1>inn>2搟ADDQDWR2IF1W1LSW11F20)2MULMULMOLWK2 1 IF3ID1ANDWEIfff2nw砂ADDWRI 117下面一段程序是計(jì)算浮點(diǎn)向量運(yùn)算Y=a*X + Y的，其中X和Y都是100維向量。采用循 環(huán) 展開(kāi)的方式使得執(zhí)行過(guò)程沒(méi)有stalk那么最少需要展開(kāi)兒次？寫(xiě)出展開(kāi)的程序。LOOP: L D MUL.D L D ADD.D S D DSUBI DSUBI BNEZF0 O(R1)FOJO, F2F4 0 (R2)FOJO, F4F0 0(R2)RLRh#8R2R2#8RLLOOP注意：本題原來(lái)的題干有錯(cuò)，大家只要掌握循環(huán)展開(kāi)的方法即可，一種可能的答案如下 0本題 在PPT匕也有，可以看一下PPT上的題目和答案?！窘狻繉⒀h(huán)展開(kāi)兩次，進(jìn)行指令調(diào)度，即可以消除延遲，代碼如下：LOOP： L DFO, 0 CRDL - DFIO, -8 (RDMUL.DFO, FO, F2MUL.DFIO, FIO, F2L - DF4, 0 (R2)L - DF14, -8 (R2)ADD.DFO, FO, F4ADD.DFIO, FIO, FI4DSUBIRH Rb #16SQ0 CR2) , FODSUBIR2> R2, #16BNEZRH LOOPS - D8 CR2) , FIO假設(shè)：LOOP: LDFO.O(Rl)(stall)MUL.DFOJO, F2L DF4J (R2)(stall)ADD.DFO. FO, F4(stall)(stall)S DFO - 0 (R2)DSUBIRLRh#8DSUBIR2R2#8BNEZRLLOOP(stall)1&分支預(yù)測(cè)。(1)畫(huà)出2位飽和計(jì)數(shù)器的狀態(tài)圖。(2)已知如下指令序列地址目標(biāo)地址是否跳轉(zhuǎn)bl否*01bl否bl是b2否b2是己知初始BHT歷史為00, BHT項(xiàng)全為01,求執(zhí)行完上述程序后的BHT。(3)簡(jiǎn)要說(shuō)明為何引入BTB會(huì)使得CPI下降。【解】見(jiàn)教材134頁(yè)圖5Oo(2)BHT一般就用PC的后幾位作為表格的索引，查出里面的預(yù)測(cè)位。這里的預(yù)測(cè)當(dāng)長(zhǎng)度為2時(shí)就是 上題中的飽和計(jì)數(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 為索引值(計(jì)數(shù)器)0101100!(3)在經(jīng)典的5段流水線(xiàn)中，ID段宋尾才能獲得分支口標(biāo)地址。而采用BTB可以提前在IF段 就 知道這些信息，分支開(kāi)銷(xiāo)就可以減少為0。19一個(gè)含有8個(gè)輸入端的系統(tǒng)采用三層<7-開(kāi)關(guān)鏈接，使用開(kāi)關(guān)控制。(可參見(jiàn)教材286頁(yè)圖921) 如開(kāi)關(guān)處在0,則會(huì)不交換，如開(kāi)關(guān)為1,則會(huì)發(fā)生交換。(1)若開(kāi)關(guān)處在000狀態(tài)，則0號(hào)鏈接？(2)若最左開(kāi)關(guān)為0,那么1號(hào)不可能鏈接到哪些處理器？ 【解】(1)0號(hào)；M010J011000J 001(2)分類(lèi)討論后面兩個(gè)開(kāi)關(guān)的狀態(tài)，得出i號(hào)的變換圖：>101001010*01010010000bI號(hào)不可能鏈接到4、7號(hào)處理器。20在多處理機(jī)系統(tǒng)中，采用寫(xiě)回法的寫(xiě)作廢(write invalidate)總線(xiàn)監(jiān)聽(tīng)協(xié)議，參見(jiàn)教材310頁(yè) 圖106的狀態(tài)機(jī)。(1)給出L S狀態(tài)的定義，并說(shuō)明什么時(shí)候可以確定發(fā)生了 Cache不一致的情況。(2)假設(shè)有兩個(gè)地址A和B (映射到不同的Cache塊中)，兩個(gè)處理機(jī)R和P2,初始時(shí)Cache全為 空，根據(jù)特定的訪(fǎng)問(wèn)序列，補(bǔ)全下表(無(wú)消息用丫代替，CPU事件RdM = Read Miss> RdH =Read Hib WrM = Write Miss WrH = Write Hit；總線(xiàn)消息 WrMs = Write Miss RdMs = Read Miss)操作AB消息/操作PlP2PlP2PlP2Pj： R ASIIIRdM/RdMsRdMs/-P2： W A 10P2： R APl： W A20Pl： WB 10P2： WB20【解】(1)M表示該塊已經(jīng)被修改過(guò)，并11未寫(xiě)入存儲(chǔ)器。【表示該塊內(nèi)容無(wú)效。S表示該塊婆 么處于共享狀態(tài)，即多個(gè)處理器中都有其副本且都與存儲(chǔ)器相同，或者該塊只在一個(gè)處理器中有 副本且與存儲(chǔ)器相同。操作AB消息/操作PiP2PlP2PlP2Pl； R AsIIIRdM/RdMsRdMs/-P2： W A 10IMIIWrMs/-WrM/WrMsP2： RAIMIIRdHAPl： W A20MIIIWrM/WrMsWrMs/寫(xiě)回PI： WB 10MIMIWrM/WrMsWrMs/-Pz： WB20MIIMWrMs/寫(xiě)回WrM/WrMs