復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院《計(jì)算機(jī)體系結(jié)構(gòu)》期末考試試卷B卷共4頁(yè)課程代碼：3.72.073.1考試形式：口開卷□閉卷2010年7月（本試卷答卷時(shí)間為120分鐘，答案必須寫在試卷上，做在草稿紙上無效）專業(yè)學(xué)號(hào)姓名成績(jī)題號(hào)一二三總分得分—、選擇題（30%）請(qǐng)?jiān)诳崭駜?nèi)填上最合適的字母序號(hào)（如A、B、C、D等）RISC機(jī)器采用的“延遲分支”技術(shù)，指的是通過由編譯器選擇合適的指令放入“延遲槽”內(nèi)，從而對(duì)程序中的指令次序進(jìn)行調(diào)度.下列的哪一種調(diào)度方法從性能改善角度來講是最有效的：-C.供選擇的答案：A)從失敗處調(diào)度（自轉(zhuǎn)移不發(fā)生處移入）B)從成功處調(diào)度（自轉(zhuǎn)移發(fā)生處移入）C)從前調(diào)度（把條轉(zhuǎn)之前的指令調(diào)入）D)從目標(biāo)處調(diào)度（復(fù)制目標(biāo)指令）指令的動(dòng)態(tài)調(diào)度算法可用來解決指令間的數(shù)據(jù)相關(guān)，Tomasulo算法的寄存器重命名技術(shù)主要用于解決CD類的數(shù)據(jù)相關(guān)。（可填入一個(gè)或多個(gè)答案）供選擇的答案：A）RAWB）RARC）WAWD）WARCache的失效大體上可分成為強(qiáng)制性失效、容量失效和沖突失效三種，以下的三個(gè)方案：―B、C和_A可分別用于減少這三種失效。供選擇的答案：A）提高相聯(lián)度B）塊預(yù)取C）增加Cache容量D）采用更高速的Cache一個(gè)具有100個(gè)處理器的多處理機(jī)系統(tǒng)如果要達(dá)到80的加速比，則計(jì)算程序中串行部分所占比例需大概為工。.供選擇的答案：A）20%B）80%C）1%D）0.25%E）0.75%在多處理機(jī)系統(tǒng)中，為實(shí)現(xiàn)同步機(jī)制而設(shè)置的基本硬件原語通常為：C。供選擇的答案：A）讀出存儲(chǔ)單元B）修改存儲(chǔ)單元

C)C)讀出并修改存儲(chǔ)單元D)讀出或修改存儲(chǔ)單元直接映象Cache的替換算法一般采用以下哪一種選擇D。供選擇的答案：A)隨機(jī)法B)FIFOC)LRUD)無選擇發(fā)生寫失效時(shí)，在是否調(diào)入相應(yīng)塊時(shí)，寫直達(dá)Cache一般采用也；寫回法Cache一般采用：A。供選擇的答案：A)按寫分配不按寫分配兩者皆可其它方法在采用虛擬存儲(chǔ)器的計(jì)算機(jī)系統(tǒng)中，對(duì)于A和―E—都存在使用虛地址還是物理地址的問題。供選擇的答案：A)CacheB)主存C)外存D)I/O設(shè)備E)DMARAID3采用位交叉奇偶校驗(yàn)盤陣列，RAID4采用塊交叉方式專用奇偶校驗(yàn)獨(dú)立存取盤陣列。假定有四個(gè)數(shù)據(jù)盤和一個(gè)冗余盤，RAID3讀一個(gè)數(shù)據(jù)需F數(shù)磁盤讀操作;RAID4讀一個(gè)數(shù)據(jù)需次磁盤讀操作；RAID3寫一個(gè)數(shù)據(jù)需D或C次磁盤讀操作和一C數(shù)磁盤寫操作；RAID4寫一個(gè)數(shù)據(jù)需C數(shù)磁盤讀操作和_C次磁盤寫操作。供選擇的答案：A)0;B)1;C)2;D)3;E)4;F)5。某一臺(tái)機(jī)器的虛地址為56位，物理地址為40位，頁(yè)面大小為64KB，每個(gè)頁(yè)面的各類有效位和保護(hù)位等共8位.采用一個(gè)全相聯(lián)的快表(TLB)共有128個(gè)表項(xiàng).那么，該快表(TLB)中的每一項(xiàng)的長(zhǎng)度—BByte(字節(jié)).供選擇的答案：A)8B)9C)10D)12集群計(jì)算機(jī)屬于(1)D，它的通信機(jī)制為(2)C。答案：A)SISDB)SIMDC)MISDD)MIMD答案：A)SMPB)NUMAC)網(wǎng)絡(luò)通信二、計(jì)算(40%)1.設(shè)有一個(gè)直接映象Cache，其Cache索引的訪問時(shí)間是2ns，標(biāo)識(shí)比較的時(shí)間是1ns，處理機(jī)訪問Cache中數(shù)據(jù)的時(shí)間是4ns，主存的讀寫時(shí)間為50ns，寫緩沖器寫入時(shí)間為4ns。如寫緩沖器未滿，試問對(duì)寫策略為寫回法的Cache，讀、寫數(shù)據(jù)的命中訪問時(shí)間各至少多少？對(duì)寫策略為寫直達(dá)法的Cache，讀、寫數(shù)據(jù)的命中訪問時(shí)間各至少多少？解：讀max(2ns+1ns,4ns)=4ns寫2ns+1ns+4ns=7ns讀max(2ns+1ns,4ns)=4ns寫max(2ns+1ns+4ns,4ns)=7ns2.試分析下列程序段中的WAR和WAW相關(guān)，需要增加多少個(gè)寄存器才能通過寄存器重命名技術(shù)消除這些相關(guān)？LDR1,0(R2)DADDR3,R4,R1DSUBR4,R5,R6DMULR7,R4,R8DSLTR8,R9,R10DSUBR11,R8,R12DDIVR12,R13,R14SD0(R15),R12解：3個(gè)WAR：DADDR3,R4,R1->DSUBR4,R5,R6DSUBR4,R5,R6->DSLTR8,R9,R10DSUBR11,R8,R12->DDIVR12,R13,R14無WAW要增加3個(gè)寄存器.有一個(gè)長(zhǎng)流水線，僅對(duì)條件轉(zhuǎn)移指令使用分支目標(biāo)緩沖。假設(shè)分支預(yù)測(cè)錯(cuò)誤的開銷為4個(gè)時(shí)鐘周期，緩沖不命中的開銷為3個(gè)時(shí)鐘周期。根據(jù)下面的假設(shè)，計(jì)算分支目標(biāo)緩沖的性能：（1）對(duì)于BTB中的指令，預(yù)測(cè)準(zhǔn)確率80%（2）緩沖區(qū)命中率90%（3）不在BTB中分支轉(zhuǎn)移成功的比例為60%（4）分支頻率為15%（5）沒有分支的基本CPI為1。解：在BTB中，預(yù)測(cè)成功，實(shí)際成功，此時(shí)延遲為0。在BTB中，預(yù)測(cè)成功，實(shí)際不成功，此時(shí)延遲為BTB命中率X預(yù)測(cè)錯(cuò)誤率X4=90%X20%X4=0.72不在BTB中，實(shí)際成功，此時(shí)延遲為（1-BTB命中率）X不在BTB中分支轉(zhuǎn)移成功率X3=10%X60%X3=0.18不在BTB中，實(shí)際不成功，此時(shí)延遲為0。所以總延遲0.72+0.18=0.9CPI=1*85%+1.9*15%=1.135在Cray-1機(jī)上，按鏈接方式執(zhí)行下面4條向量指令（括號(hào)中給出相應(yīng)功能部件時(shí)間），如果向量寄存器和功能部件之間的數(shù)據(jù)傳輸需要1拍，試求此鏈接流水線的流過時(shí)間為多少拍？如果向量長(zhǎng)度為N，則需要多少拍能得到全部結(jié)果。V0-存儲(chǔ)器（存儲(chǔ)器取數(shù)：7拍）V2-V0+V1（向量加：3拍）V3-V2VA3（按照A3左移：4拍）V5^V3AV4(向量邏輯乘：2拍)解：流水線經(jīng)過時(shí)間為(1+7+1)+(1+3+1)+(1+4+1)+(1+2+1)=24。如果向量長(zhǎng)度為N,則需24+(N-1)=N+23拍能得到全部結(jié)果。某RISC機(jī)的數(shù)據(jù)Cache由L1級(jí)和L2級(jí)組成，其工作方式是判別失效后再訪問下級(jí)存儲(chǔ)器，假定：L1級(jí)的失效率為1%,命中時(shí)間為一個(gè)時(shí)鐘周期；L2級(jí)的失效率為0.4%，命中時(shí)間為2個(gè)時(shí)鐘周期，未命中訪問主存的時(shí)間為10個(gè)時(shí)鐘周期。試計(jì)算數(shù)據(jù)訪問的平均時(shí)鐘周期數(shù)。解：數(shù)據(jù)訪問的平均時(shí)鐘周期數(shù)=命中時(shí)間L1+失效率L1*失效開銷L1+失效率L1*失效率L2(局部)*失效開銷L2=1+0.01*2+0.004*10=1.06三、綜合(30%)1.在第三章改進(jìn)的MIPS流水線上運(yùn)行如下代碼序列：LOOP：LWR3,0(R1)DADDR4,R3,R2SW0(R1),R4DSUBIR1,R1,#4BNEZR1,LOOP其中，R1的初值為100。假設(shè):在整個(gè)代碼序列執(zhí)行過程中，所有的存儲(chǔ)器訪問都命中Cache，并且在一個(gè)時(shí)鐘周期中對(duì)同一個(gè)寄存器的寫操作和讀操作可在一拍內(nèi)完成。在沒有任何定向硬件的支持下，請(qǐng)畫出該代碼序列執(zhí)行的流水線時(shí)空?qǐng)D。假設(shè)采用排空流水線的策略處理分支指令，那么執(zhí)行上述循環(huán)需多少個(gè)時(shí)鐘周期？如有正常的定向硬件的支持，請(qǐng)畫出該代碼序列執(zhí)行的流水線時(shí)空?qǐng)D。假設(shè)采用預(yù)測(cè)分支失敗的策略處理分支指令，那么執(zhí)行上述循環(huán)需多少個(gè)時(shí)鐘周期？(注：設(shè)在分支成功時(shí)需延遲一拍)解：1)時(shí)空?qǐng)D：123456789101112131415LWIFIDEXMEMWBDADDIFstallstallIDEXMEMWBSWIFstallstallIDEXMEMWBDSUBIIFIDEXMEMWBBNEZIFstallstallIDEXMEMWBLWIFstallstallID25次循環(huán)，(25-1、14+15=351(周期)2)時(shí)空?qǐng)D：1234567891011LWIFIDEXMEMWBDADDIFstallIDEXMEMWBSWIFIDEXMEMWBDSUBIIFIDEXMEMWBBNEZIFstallIDEXMEMWBLWIFIDEXMEM25次循環(huán)，(25-1)x8+11=203凋期)2.旋轉(zhuǎn)鎖是多處理機(jī)實(shí)現(xiàn)同步的一個(gè)重要手段。它在存儲(chǔ)器中保存鎖變量(1加鎖，0開鎖)，各處理器可以不斷地通過一個(gè)原子操作請(qǐng)求加鎖。釋放鎖的時(shí)候，處理器可簡(jiǎn)單地將鎖置為“0”。將鎖緩沖進(jìn)入Cache，并通過一致性機(jī)制使鎖值保持一致，可減少對(duì)存儲(chǔ)器的訪問。⑴如果R1中保存鎖的地址，試在支持Cache一致性的處理機(jī)上使用LLR2,0(R1)和SCR2,0(R1)指令對(duì)來編寫實(shí)現(xiàn)旋轉(zhuǎn)鎖的查詢和加鎖程序。(2)設(shè)總線上有4個(gè)處理器同時(shí)準(zhǔn)備對(duì)同一變量加鎖。假設(shè)每個(gè)總線事務(wù)處理(讀失效或?qū)懯?是100個(gè)時(shí)鐘周期，忽略實(shí)際的Cache塊鎖的讀寫時(shí)間以及加鎖的時(shí)間，求4個(gè)處理器請(qǐng)求加鎖所需的總線事務(wù)數(shù)目。