計(jì)算機(jī)體系結(jié)構(gòu)習(xí)題二及答案專升本高升專計(jì)算機(jī)高本下學(xué)期

計(jì)算機(jī)體系結(jié)構(gòu)習(xí)題二一、（5分）計(jì)算機(jī)系統(tǒng)設(shè)計(jì)中經(jīng)常使用的4個(gè)定量原理是什么？請簡要說明它們的含義。二、（15分）假設(shè)某應(yīng)用程序中有4類操作，通過改進(jìn)各類操作的功能部件，可獲得不同的性能提高。具體數(shù)據(jù)如下表所示：操作類型程序中的數(shù)量（百萬條指令）改進(jìn)前的執(zhí)行時(shí)間（周期）改進(jìn)后的執(zhí)行時(shí)間（周期）操作11021操作2302015操作335103操作41541（1）改進(jìn)后，各類操作的加速比分別是多少？（2）各類操作單獨(dú)改進(jìn)后，程序獲得的加速比分別是多少?（3）4類操作均改進(jìn)后，整個(gè)程序的加速比是多少？三、（5分）請簡述指令之間數(shù)據(jù)沖突的類型。四、（15分）有一指令流水線如下所示入一1i2-33 4-?出50ns50ns100ns 200ns（1）如果連續(xù)輸入10條指令，請計(jì)算該流水線的實(shí)際吞吐率和效率；（2） 該流水線的“瓶頸”在哪一段？請采取兩種不同的措施消除此“瓶頸”。對于你所給出的兩種新的流水線，連續(xù)輸入10條指令時(shí)，其實(shí)際吞吐率和效率各是多少？五、（15分）下面一段MIPS匯編程序是計(jì)算高斯消去法中的關(guān)鍵一步，用于完成下面公式的計(jì)算：Y=aX+Y其浮點(diǎn)指令延遲如下表所示:產(chǎn)生結(jié)果指令使用結(jié)果指令延遲時(shí)鐘周期數(shù)浮點(diǎn)計(jì)算另外的浮點(diǎn)計(jì)算3浮點(diǎn)計(jì)算浮點(diǎn)數(shù)據(jù)存操作（SD）2浮點(diǎn)數(shù)據(jù)取操作（LD）浮點(diǎn)計(jì)算1浮點(diǎn)數(shù)據(jù)取操作浮點(diǎn)數(shù)據(jù)存操作<SD）0整數(shù)指令均為1個(gè)時(shí)鐘周期完成，浮點(diǎn)和整數(shù)部件均采用流水。整數(shù)操作之間以及與其它所有浮點(diǎn)操作之間的延遲為0，轉(zhuǎn)移指令的延遲為0。X中的最后一個(gè)元素存放在存儲(chǔ)器中的地址為DONE。FOO:L.DF2,0（R1）MUT.DF4,F2,F0L.D F6,0（R2）ADD.DF6,F4,F6S.D F6,0[R2]DADDIUR1,R1,#8DADDIUR2,R2,#8DSUBIU R3,R1,#DONEBNEZR3,FOO（1）對于標(biāo)準(zhǔn)的MIPS單流水線，上述循環(huán)計(jì)算一個(gè)Y值需要多少時(shí)間？其中有多少空轉(zhuǎn)周期？（2）對于標(biāo)準(zhǔn)的MIPS單流水線，將上述循環(huán)順序展開4次，不進(jìn)行任何指令調(diào)度，計(jì)算一個(gè)Y值平均需要多少時(shí)間？加速比是多少？其加速是如何獲得的？（3）對于標(biāo)準(zhǔn)的MIPS單流水線，將上述循環(huán)順序展開4次，優(yōu)化和調(diào)度指令，使循環(huán)處理時(shí)間達(dá)到最優(yōu)，計(jì)算一個(gè)丫值平均需要多少時(shí)間？加速比是多少？六、（5分）寫出三級(jí)Cache的平均訪問時(shí)間的公式。七、（10分）高速緩存（Cache）是現(xiàn)代計(jì)算機(jī)存儲(chǔ)系統(tǒng)重要的層次之一。假設(shè)一個(gè)2GHz，32位的處理器有32KB的直接映射L1Cache和256KB的2路組相聯(lián)L2Cache。各級(jí)Cache都采用32B的塊大小。（1）請說明對于L1和L2Cache而言，32位的地址中標(biāo)記（tag），索引（index）和偏移（offset）字段分別是多少位；（2）假設(shè)L1Cache命中需要2個(gè)時(shí)鐘周期完成訪問操作，命中率為80%。L2Cache命中需要10個(gè)時(shí)鐘周期，命中率99%。若L2Cache缺失，則需100個(gè)時(shí)鐘周期從內(nèi)存獲取數(shù)據(jù)。請計(jì)算該機(jī)器存儲(chǔ)系統(tǒng)平均訪問時(shí)間。八、（10分）給定以下的假設(shè)，試計(jì)算直接映象Cache和兩路組相聯(lián)Cache的平均訪問時(shí)間以及CPU的性能。由計(jì)算結(jié)果能得出什么結(jié)論？（1）理想Cache情況下的CPI為2.0，時(shí)鐘周期為2^，平均每條指令訪存1.2次；（2）兩者Cache容量均為64KB，塊大小都是32字節(jié)；（3）組相聯(lián)Cache中的多路選擇器使CPU的時(shí)鐘周期增加了10%；（4）這兩種Cache的失效開銷都是80ns；（5）命中時(shí)間為1個(gè)時(shí)鐘周期；（6）64KB直接映象Cache的失效率為1.4%,64KB兩路組相聯(lián)Cache的失效率為1.0%。九、（5分）在有Cache的計(jì)算機(jī)系統(tǒng)中，當(dāng)I/O設(shè)備與主存直接交換數(shù)據(jù)時(shí)，可能會(huì)產(chǎn)生哪些數(shù)據(jù)不一致問題？如何解決？十、（5分）請簡述多處理機(jī)的Cache一致性問題，并簡要說明解決多處理機(jī)Cache一致性問題的監(jiān)聽協(xié)議和目錄協(xié)議的工作原理。十一、（5分）通道有哪幾種？請比較這幾種通道的優(yōu)缺點(diǎn)及適用場合。十二、（5分）請比較可用于動(dòng)態(tài)互連網(wǎng)絡(luò)的總線、交叉開關(guān)和多級(jí)開關(guān)的硬件復(fù)雜度和帶寬。計(jì)算機(jī)體系結(jié)構(gòu)習(xí)題二答案十三、（5分）計(jì)算機(jī)系統(tǒng)設(shè)計(jì)中經(jīng)常使用的4個(gè)定量原理是什么？請簡要說明它們的含義。答：（1）以經(jīng)常性事件為重點(diǎn)。在計(jì)算機(jī)系統(tǒng)的設(shè)計(jì)中，對經(jīng)常發(fā)生的情況，賦予它優(yōu)先的處理權(quán)和資源使用權(quán)，以得到更多的總體上的改進(jìn)。（2）Amdahl定律。加快某部件執(zhí)行速度所獲得的系統(tǒng)性能加速比，受限于該部件在系統(tǒng)中所占的重要性。（3）CPU性能公式。執(zhí)行一個(gè)程序所需的CPU時(shí)間=ICXCPIXT0（4）程序的局部性原理。程序在執(zhí)行時(shí)所訪問地址的分布不是隨機(jī)的，而是相對地簇聚。十四、（15分）假設(shè)某應(yīng)用程序中有4類操作，通過改進(jìn)各類操作的功能部件，可獲得不同的性能提高。具體數(shù)據(jù)如下表所示:操作類型程序中的數(shù)量（百萬條指令）改進(jìn)前的執(zhí)行時(shí)間（周期）改進(jìn)后的執(zhí)行時(shí)間（周期）操作11021操作2302015操作335103操作41541（1）改進(jìn)后，各類操作的加速比分別是多少？（2）各類操作單獨(dú)改進(jìn)后，程序獲得的加速比分別是多少?（3）4類操作均改進(jìn)后，整個(gè)程序的加速比是多少？答：根據(jù)Amdahl定律$二1于，其中f是可改進(jìn)部分在總運(yùn)行時(shí)間中所占’"a比例，a是可改進(jìn)部分的加速比，可得操作類型各類操作的指令條數(shù)在程序中所占的比例f各類操作的加速比S.各類操作單獨(dú)改進(jìn)后，程序獲得的加速比操作11.9%21.01操作258.2%1.331.17操作334.0%3.331.31操作45.8%41.044類操作均改進(jìn)后，整個(gè)程序的加速比:氏1.771氏1.77（1一￡F）+￡FiSi十五、（5分）請簡述指令之間數(shù)據(jù)沖突的類型。

答：指令之間的數(shù)據(jù)沖突有3種類型：真相關(guān)、反相關(guān)、輸出相關(guān)。真相關(guān)（數(shù)據(jù)依賴，有時(shí)候也稱為數(shù)據(jù)相關(guān)）：考慮兩條指令i和j,i在j的前面，指令k在指令i和指令j之間。如果下述條件之一成立，則稱指令j與指令i真相關(guān)：（1）指令j使用指令i產(chǎn)生的結(jié)果（寫后讀）；（2）指令j與指令k真相關(guān)，而指令k又與指令i真相關(guān)。（真相關(guān)的傳遞性）反相關(guān)：考慮兩條指令i和j，i在j的前面，如果指令j所寫的名與指令i所讀的寄存器名或存儲(chǔ)地址相同，則稱指令i和j發(fā)生了反相關(guān)。（讀后寫）輸出相關(guān)：考慮兩條指令i和j，i在j的前面，如果指令j和指令i所寫的寄存器名或存儲(chǔ)地址相同，則稱指令i和j發(fā)生了輸出相關(guān)。（寫后寫）其中反相關(guān)和輸出相關(guān)又合稱名相關(guān)。名相關(guān)的意思是兩條指令使用了相同的寄存器名或存儲(chǔ)地址,但是它們之間并沒有數(shù)據(jù)流動(dòng)，即沒有真正的數(shù)據(jù)依賴關(guān)系,則稱這兩條指令存在名相關(guān)。十六、（15分）有一指令流水線如下所示入一h ir2 3r4150ns50ns100ns 200ns（3）如果連續(xù)輸入10條指令，請計(jì)算該流水線的實(shí)際吞吐率和效率；（4）該流水線的“瓶頸”在哪一段？請采取兩種不同的措施消除此“瓶頸”。對于你所給出的兩種新的流水線，連續(xù)輸入10條指令時(shí)，其實(shí)際吞吐率和效率各是多少？答：⑴Tpipeline= Ati+(n-1)Atmaxi=1=(50+50+100+200)+9x200二2200(ns)TP=^Tpipeline=小，力AtE=TP.-4=1--=TP.400=—您45.45%m 4 11（2）瓶頸在3、4段。變成八級(jí)流水線（細(xì)分）——I出50ns50ns50ns50ns50ns50ns50ns50ns50ns50ns50ns50nsTpipeline=1Ati+(n-1)Atmaxi=1=50x8+9x50=850(ns)TP=nTpipeline'^3于AtiE=TP.-4=1一=TP.400=10氏58.82%m 8 17重復(fù)設(shè)置部件TP=＞「r=185(nsmpipelineE=400X10850x8=1017x58.82%4_44_44_34_24_13_23_121850ns十七、（15分）下面一段MIPS匯編程序是計(jì)算高斯消去法中的關(guān)鍵一步，用于完成下面公式的計(jì)算：Y=axX+Y

其浮點(diǎn)指令延遲如下表所示:產(chǎn)生結(jié)果指令使用結(jié)果指令延遲時(shí)鐘周期數(shù)浮點(diǎn)計(jì)算另外的浮點(diǎn)計(jì)算3浮點(diǎn)計(jì)算浮點(diǎn)數(shù)據(jù)存操作(SD)2浮點(diǎn)數(shù)據(jù)取操作(LD)浮點(diǎn)計(jì)算1浮點(diǎn)數(shù)據(jù)取操作(LD)浮點(diǎn)數(shù)據(jù)存操作<SD)0整數(shù)指令均為1個(gè)時(shí)鐘周期完成，浮點(diǎn)和整數(shù)部件均采用流水。整數(shù)操作之間以及與其它所有浮點(diǎn)操作之間的延遲為0，轉(zhuǎn)移指令的延遲為0。X中的最后一個(gè)元素存放在存儲(chǔ)器中的地址為DONE。F2,0(R1)F4,F2,F0F6,0(R2)F6,F4,F6F2,0(R1)F4,F2,F0F6,0(R2)F6,F4,F6F6,0[R2]L.DADD.DS.DDADDIUR1,R1,#8DADDIUR2,R2,#8DSUBIUR3,R1,#DONEBNEZR3,FOO對于標(biāo)準(zhǔn)的MIPS單流水線，上述循環(huán)計(jì)算一個(gè)Y值需要多少時(shí)間？其中有多少空轉(zhuǎn)周期？對于標(biāo)準(zhǔn)的MIPS單流水線，將上述循環(huán)順序展開4次，不進(jìn)行任何指令調(diào)度，計(jì)算一個(gè)Y值平均需要多少時(shí)間？加速比是多少？其加速是如何獲得的？(6)對于標(biāo)準(zhǔn)的MIPS單流水線，將上述循環(huán)順序展開4次，優(yōu)化和調(diào)度指令，使循環(huán)處理時(shí)間達(dá)到最優(yōu)，計(jì)算一個(gè)Y值平均需要多少時(shí)間？加速比是多少？答：(6)(1)L.DF2,0(R1)StallMUT.DF4,F2,F0L.DF6,0(R2)StallStallADD.DF6,F4,F64StallStallTOC\o"1-5"\h\z\o"CurrentDocument"S.DF6,0[R2] 5\o"CurrentDocument"DADDIUR1,R1,#8 6\o"CurrentDocument"DADDIUR2,R2,#8 7DSUBIUR3,R1,#DONE8BNEZR3,FOO9所以，共有14個(gè)時(shí)鐘周期，其中有5個(gè)空轉(zhuǎn)周期。(2)循環(huán)順序展開4次，不進(jìn)行任何指令調(diào)度，則指令1?5及其間的stall都是必要的，只是指令6?9只需執(zhí)行一次，因此，共有10義4+4=44個(gè)時(shí)鐘周期，計(jì)算出4個(gè)Y值，所以計(jì)算一個(gè)Y值需要11個(gè)時(shí)鐘周期，加速比為：14/11=1.27。加速主要是來自減少控制開銷，即減少對R1、R2的整數(shù)操作以及比較、分支指令而來的。(3)循環(huán)順序展開4次，優(yōu)化和調(diào)度指令，如下：L.D F2,0(R1)L.D F8,8(R1)L.D F14,16(R1)L.D F20,24(R1)MUT.D F4,F2,F0MUT.D F10,F8,F0MUT.D F16,F14,F0MUT.D F22,F20,F0L.D F6,0(R2)L.D F12,8(R2)L.D F18,16(R2)L.D F24,24(R2)ADD.D F6,F4,F6ADD.D F12,F10,F12ADD.D F18,F16,F18ADD.D F24,F22,F24S.D F6,0[R2]S.D F12,8[R2]S.D F18,16[R2]S.D F24,24[R2]DADDIU R1,R1,#32DADDIU R2,R2,#32DSUBIUR3,R1,#DONEBNEZR3,FOO共用了24個(gè)時(shí)鐘周期，則計(jì)算一個(gè)丫值平均需要24/4=6個(gè)時(shí)鐘周期，加速比：14/6=2.33十八、（5分）寫出三級(jí)Cache的平均訪問時(shí)間的公式。答：平均訪存時(shí)間=命中時(shí)間+失效率又失效開銷只有第I層失效時(shí)才會(huì)訪問第I+1。設(shè)三級(jí)Cache的命中率分別為HL1、HL2、HL3,失效率分別為ML1、ML2、乂匕3,第三級(jí)Cache的失效開銷為PL3。平均訪問時(shí)間TA=HL1+ML1X{HL2+ML2X（HL3+ML3XPL3）}十九、（10分）高速緩存（Cache）是現(xiàn)代計(jì)算機(jī)存儲(chǔ)系統(tǒng)重要的層次之一。假設(shè)一個(gè)2GHz,32位的處理器有32KB的直接映射L1Cache和256KB的2路組相聯(lián)L2Cache。各級(jí)Cache都采用32B的塊大小。（1）請說明對于L1和L2Cache而言，32位的地址中標(biāo)記（tag）,索引（index）和偏移（offset）字段分別是多少位；（2）假設(shè)L1Cache命中需要2個(gè)時(shí)鐘周期完成訪問操作，命中率為80%。L2Cache命中需要10個(gè)時(shí)鐘周期，命中率99%。若L2Cache缺失，則需100個(gè)時(shí)鐘周期從內(nèi)存獲取數(shù)據(jù)。請計(jì)算該機(jī)器存儲(chǔ)系統(tǒng)平均訪問時(shí)間。答：（1）（8分）見下表Cache地址中各字段L1Tag（17位），Index（10位），Offset（5位）L2Tag（15位），Index（12位），Offset（5位）（2）（2分）Ta=Th+（1-H）Tm,Ta為平均訪問時(shí)間，Th為命中時(shí)間，H為命中率，Tm為缺失開銷。本例：2+20%（10+1%*100）=4.2.Ta=4.2/2G=2.1*10-9s=2.1ns二十、（10分）給定以下的假設(shè)，試計(jì)算直接映象Cache和兩路組相聯(lián)Cache的平均訪問時(shí)間以及CPU的性能。由計(jì)算結(jié)果能得出什么結(jié)論？（7）理想Cache情況下的CPI為2.0,時(shí)鐘周期為2^,平均每條指令訪存1.2次；（8）兩者Cache容量均為64KB,塊大小都是32字節(jié)；（9）組相聯(lián)Cache中的多路選擇器使CPU的時(shí)鐘周期增加了10%；（10）這兩種Cache的失效開銷都是80ns；（11）命中時(shí)間為1個(gè)時(shí)鐘周期；（12）64KB直接映象Cache的失效率為1.4%,64KB兩路組相聯(lián)Cache的失效率為1.0%。答：平均訪問時(shí)間=命中時(shí)間+失效率又失效開銷平均訪問時(shí)間1-s=2.0+1.4%*80=3.12ns平均訪問時(shí)間2路=2.0*（1+10%）+1.0%*80=3.0ns兩路組相聯(lián)的平均訪問時(shí)間比較低CPUtime=（CPU行+存儲(chǔ)等待周期）*時(shí)鐘周期CPUtime=IC（cPF+總失效次數(shù)/指令總數(shù)*失效開銷）*時(shí)鐘周期=IC（（CPI*時(shí)鐘周期）+（每條指令的訪存次數(shù)*失效率*失效開銷*時(shí)鐘周期）） 執(zhí)行CPUtime1-wa=IC（2.0*2+1.2*0.014*80）=5.344ICCPUtime2：a：TC（2.2*2+1.2*0.01*80）=5.36IC相對性能比：CPUtime-2way=5.36/5.344=1.003CPUtime-1way直接映象cache的訪問速度比兩路組相聯(lián)cache要快1.04倍，而兩路組相聯(lián)Cache的平均性能是直接映象cache的1.003倍。因此這里選擇兩路組相聯(lián)。二十一、（5分）在有Cache的計(jì)算機(jī)系統(tǒng)中，當(dāng)I/O設(shè)備與主存直接交換數(shù)據(jù)時(shí)，可能會(huì)產(chǎn)生哪些數(shù)據(jù)不一致問題？如何解決？答：（1）存儲(chǔ)器中可能不是CPU產(chǎn)生的最新數(shù)據(jù)，所以I/O設(shè)備從存儲(chǔ)器中取出來的是陳舊數(shù)據(jù)。（2）I/O設(shè)備與存儲(chǔ)器交換數(shù)據(jù)之后，在Cache中，被CPU使用的可能就會(huì)是陳舊數(shù)據(jù)。第一個(gè)問題可以用寫直達(dá)Cache解決。第二個(gè)問題操作系統(tǒng)可以保證I/O設(shè)備操作的數(shù)據(jù)不在Cache中。如果不能，就作廢Cache中相應(yīng)的數(shù)據(jù)。二十二、（5分）請簡述多處理機(jī)的Cache一致性問題，并簡要說明解決多處理機(jī)Cache一致性問題的監(jiān)聽協(xié)議和目錄協(xié)議的工作原理。答：（1）多處理機(jī)中，當(dāng)共享數(shù)據(jù)進(jìn)入Cache，就可能出現(xiàn)多個(gè)處理器的Cache中都有同一存儲(chǔ)器塊的副本，要保證多個(gè)副本數(shù)據(jù)是一致的。多個(gè)處理機(jī)維護(hù)Cache一致性的協(xié)議稱為Cache一致性協(xié)議。監(jiān)聽協(xié)議和目錄協(xié)議是多處理機(jī)維護(hù)Cache一致性的兩種協(xié)議。（2）目錄協(xié)議的工作原理：采用一個(gè)集中的數(shù)