系統(tǒng)結(jié)構(gòu)答案(1)復(fù)習(xí)過程

學(xué)習(xí)學(xué)習(xí)--——好資料更多精品文檔更多精品文檔T解：根據(jù)T解：根據(jù)Amdahl定理有：Sn=Tn主存的5倍，相當(dāng)于改進(jìn)存儲(chǔ)器后獲得的加速比為1.26假設(shè)高速緩存Cache工作速度為主存的5倍，且Cache被訪問命中的概率為90%,那么，采用Cache后能使整個(gè)存儲(chǔ)系統(tǒng)獲得多高的加速比 ？1 ;結(jié)合題意：Cache工作速度為11-Fe)+Fe/Se5,即Se=5;Cache被訪問命中的概率為90%,相當(dāng)于訪問存儲(chǔ)器的時(shí)間有90%化在Cache±,即Fe=0.9。所以Sn=1/[(1-0.9)+0.9/5]=3.57設(shè)計(jì)指令存儲(chǔ)器有兩種不同方案： 一種是采用價(jià)格較貴的高速存儲(chǔ)器芯片， 另一種是采用價(jià)格便宜的低速存儲(chǔ)器芯片。采用后一方案時(shí)，用同樣的經(jīng)費(fèi)可使存儲(chǔ)器總線帶寬加倍，從而每隔 2個(gè)時(shí)鐘周期可取出2條指令(每條指令為單字長(zhǎng)32位)。而采用前一方案時(shí)，每一個(gè)時(shí)鐘周期取出一條單字長(zhǎng)指令。由于訪存局部性原理，當(dāng)取出 2個(gè)指令字時(shí)，通常這2個(gè)指令字都要使用，但仍有 25%的時(shí)鐘周期中，取出的2個(gè)指令字中僅有1個(gè)指令字是有用的。試問采用這兩種實(shí)現(xiàn)方案所構(gòu)成的存儲(chǔ)器帶寬是多少？解：帶寬是指單位時(shí)間內(nèi)處理的二進(jìn)制位數(shù) ，相當(dāng)于頻率，用f表示。采用方案A時(shí)，存取指令的CPIa=1時(shí)鐘周期/指令字，即：fa=1/CPIaX指令字長(zhǎng)=1X32=32位/時(shí)鐘周期。采用方案B時(shí)，存取指令的CPIb=0.75X2/2+0.25X2/1=1.25 時(shí)鐘周期/指令字，即：f a=1/CPIaX指令字長(zhǎng)=0.8X32=25.6位/時(shí)鐘周期。某工作站采用時(shí)鐘頻率為 15MHz處理速率為10MIPS的處理機(jī)來執(zhí)行一個(gè)測(cè)試程序。假定每次存儲(chǔ)器存取為1個(gè)時(shí)鐘周期，試問：(1)此計(jì)算機(jī)的有效CPI是多少？(2)假定將處理機(jī)的時(shí)鐘頻率提高到 30MHz但存儲(chǔ)器的工作速率不變，這樣，每次存儲(chǔ)器存取需要 2個(gè)時(shí)鐘周期。如果30%指令每條只需要一次存儲(chǔ)器存取操作， 另外5%指令每條需要二次存儲(chǔ)器存取操作，假定測(cè)試程序的指令數(shù)不變，并與原工作站兼容，試求改進(jìn)后的處理機(jī) CPI和MIPS解：(1)由MIPS=時(shí)鐘頻率/(CPIX106),則有：CPIa=時(shí)鐘頻率/(MIPSX106)=1.5。(2)當(dāng)時(shí)鐘頻率為15MHz時(shí)，假設(shè)不進(jìn)行存儲(chǔ)操作指令的 CPI為x,則要進(jìn)行一次存儲(chǔ)操作指令的CPI為1+x,要進(jìn)行二次存儲(chǔ)操作指令的 CPI為2+x,因此有：.5=xX65%+(1+x)X30%+(2+x)X5%解得x=1.1當(dāng)時(shí)鐘頻率為30MHz寸，不進(jìn)行存儲(chǔ)操作指令的 CPI不變?yōu)?.1,要進(jìn)行一次存儲(chǔ)操作指令的 CPI為2+x=3.1，要進(jìn)行二次存儲(chǔ)操作指令的 CPI為4+x=5.1，因此平均CPI為：CPI b=1.1X65%+3.1X30%+5.1X5%=1.9所以 MIPS b=時(shí)鐘頻率/(CPIbX106)=(30X106)/(1.9X106)=15.8MIPS某計(jì)算機(jī)Cache能存放2000條指令。假設(shè)10%勺指令承擔(dān)了90%寸間的指令訪問，而且這10%指令中每條指令的執(zhí)行時(shí)間相同。如果要執(zhí)行的某程序共50000條指令，當(dāng)計(jì)算機(jī)執(zhí)行該程序時(shí)，在Cache中能訪問到的指令的概率是多少？解：由題意可知：45000條指令承擔(dān)10%寸間的指令訪問，5000條指令承擔(dān)90%寸間的指令訪問。顯然5000條指令被頻繁使用，設(shè)平均使用次數(shù)為 X;另外45000條指令僅使用一次。則有：45000:0.1=5000X:0.9 解得X=81所以該程序執(zhí)行指令的條數(shù)為 Y=45000+5000X81=450000假設(shè)頻繁使用的5000條指令均勻分布于程序之中，即每次調(diào)入Cache的2000條指令有200條是頻繁使用的。另假設(shè)每次調(diào)入Cache的2000條指令中的1800條均被使用了一次。所以執(zhí)行該程序時(shí) Cache中能訪問到的指令的概率為：(450000-50000/2000)+450000?100%有一臺(tái)計(jì)算機(jī)，不同類型指令在理想 Cache(無訪問失敗)與實(shí)際Cache(有訪問失敗)兩種情況下的性能如下表。求理想 Cache相對(duì)于實(shí)際Cache的加速比？指令類型出現(xiàn)頻率理想CacheCPI實(shí)際CacheCPI運(yùn)算指令40%13取數(shù)指令120%28存數(shù)指令115%28控制指令125%24解：理想Cache情況下指令的平均時(shí)鐘周期數(shù) CPI為：nCPI理想=￡(CPii*Ii/Ic)=1X40%+2X20%+2X15%+2X25%=1.6i1實(shí)際Cache情況下指令的平均時(shí)鐘周期數(shù) CPI為：nCPI實(shí)際=z(CPIi*Ii/Ic)=3X40%+8X20%+涿15%+*25%=5.0i1S二實(shí)際CacheCPUM行時(shí)間/理想CacheCPUM行時(shí)間二(ICX時(shí)鐘周期xCPI實(shí)際)/(ICX時(shí)鐘周期xCPI理想)=CPI/CPIa=5.0/1.6=3.12假設(shè)在一臺(tái)40MHz處理機(jī)上運(yùn)行測(cè)試程序共有 200000條指令，由4類指令組成。已知指令的CPI和所各占比例如下表。指令類型指令比例CPI算邏運(yùn)算Cache命中存取控制指令Cache末命中訪主仔60% 118% 212% 410% 8(1)計(jì)算處理機(jī)運(yùn)行該程序的平均 CPI。(2)根據(jù)(1)所得CPI,計(jì)算相應(yīng)的MIPS速率。n解：(1)CPI=Z(CPIi*Ii/Ic)=1X60%+2X18%+4X12%+8X10%=2.2i1MIPS=時(shí)鐘頻率/(CPIX106)=40X106/(2.2X106)=18.19已知4個(gè)程序在AB、C三臺(tái)計(jì)算機(jī)上的執(zhí)行時(shí)間(秒)分別如下表，假設(shè)每個(gè)程序都有100X106條指令要執(zhí)行，計(jì)算這3臺(tái)計(jì)算機(jī)對(duì)每個(gè)程序的MIPS速率。根據(jù)這些速率值，你能否得出這 3臺(tái)計(jì)算機(jī)相對(duì)性能的明確結(jié)論？你能否找到一種將它們排序的方法？試說明理由。

程序計(jì)隼刑A計(jì)算機(jī)B計(jì)算機(jī)C程序11020程序2 ?00010020程序3 1)00100050程序4 ,00800100程序1 100 105程序2 ().1 15程序3 ().2 0.12程序4 ,0.1251(2)由于MIPS與指令值、指，令使用的頻率等后關(guān)，在同程序 計(jì)算機(jī)A計(jì)算機(jī)B計(jì)算機(jī)C率MIPS,程序1 100 105程序2 ().1 15程序3 ().2 0.12程序4 ,0.1251(2)由于MIPS與指令值、指，令使用的頻率等后關(guān)，在同程序 計(jì)算機(jī)A計(jì)算機(jī)B計(jì)算機(jī)C率MIPS,因此不能僅用MIPS來評(píng)價(jià)計(jì)算機(jī)性能的優(yōu)劣。而應(yīng)用執(zhí)行程序的算術(shù)平均臺(tái)機(jī)器上運(yùn)行不同的程序，得出不同的速Tcpu來評(píng)價(jià)比較好。所以性能排序?yàn)?epuA=epuB=TepuC=(1+1000+500+100)/4=400.25(10+100+1000+800)/4=477.5(20+20+50+100)/4=47.5根據(jù)上表中列出的Tcpu則可計(jì)算出相應(yīng)的MIPS如下表所示。浮點(diǎn)數(shù)系統(tǒng)使用的階碼基值 re=2,階值位數(shù)q=2,尾數(shù)基值rm=10,尾數(shù)位數(shù)p'=1,即按照使用的二進(jìn)制位數(shù)來說，等價(jià)于 p=4o計(jì)算在非負(fù)階、正尾數(shù)、規(guī)格化情況下的最小尾數(shù)值、最大尾數(shù)值、最大階值、可表示的最小值和最大值及可表示數(shù)的個(gè)數(shù)。解：最小尾數(shù)值：rm1=10-1=0.1最大尾數(shù)值：1-rmp'=1-10-1=0.9最大階值：2q-1=3可表示數(shù)的最小值：1xrm1=10-1=0.1可表示數(shù)的最大值： —q-1x(1-rmpj=103(1-10-1)=900可表示數(shù)的個(gè)數(shù)： 2qxrmp，(rm-1)/rm=22X101(10-1)/10=36一個(gè)處理機(jī)有I1?I10共10條指令，經(jīng)統(tǒng)計(jì)，各指令在程序中出現(xiàn)的概率如下：I1:0.25I2:0.20I3:0.15I4:0.10I5:0.08I6:0.08I7:0.05I8:0.04I9:0.03 I10 :0.02(1)計(jì)算這10條指令的操作碼最短平均長(zhǎng)度。(2)寫出這10條指令的Huffman編碼，并計(jì)算操作碼編碼的平均長(zhǎng)度和信息冗余量。(3)采用3/7擴(kuò)展編碼法和2/8擴(kuò)展編碼法編寫這10條指令的操作碼。并分別計(jì)算編碼的平均長(zhǎng)度和信息冗余量。說明哪一種擴(kuò)展編碼較好的理由。

n解：(1)二.操作碼編碼的最短平均長(zhǎng)度為： H=-￡piXlogzpii4H=—(0.25log20.25+0.20log20.20+0.15log20.15+0.10log20.10+0.08log20.08+0.08log20.08+0.05log20.05+0.04log20.04+0.03log20.03+0.02log20.02)=2.96 (位)1I9I8I7(2)根據(jù)給出的使用頻度，在構(gòu)造Huffman樹的過程中，有兩個(gè)結(jié)點(diǎn)可供合并，因此可生成不同的Huffman樹，其中給出一棵如圖所示，相應(yīng)的Huffman編碼如表所示。1I9I8I7I10IiPiHuffman編碼Li2-5編碼(3/7)Li2-4編碼(2/8)LiI10.25002002002I20.20102012012I30.15010310210004I40.10110311000510014I50.080110411001510104I60.081110411010510114I70.0501110511011511004I80.0401111511100510014I90.0311110511101511104I100.0211111511110511114nHuffman編碼的平均長(zhǎng)度為：l=Xpixli1l=0.25X2+0.20X2+0.15X3+0.10X3+0.08X4+0.08X4+0.05X5+0.04X5+0.03X5+0.02X5=2.99 (位)Huffman 編碼的信息冗余量為： R=1-H/l= (1—2.96/2.99)X100%=1.0%3/7擴(kuò)展編碼和2/8擴(kuò)展編碼如表所示。3/7擴(kuò)展編碼要求短碼碼點(diǎn)數(shù)為 3,長(zhǎng)碼碼點(diǎn)數(shù)為7。所以短碼長(zhǎng)取2位，有碼點(diǎn)22=4個(gè)，用一個(gè)作擴(kuò)展標(biāo)志；長(zhǎng)碼長(zhǎng)取 3位，有碼點(diǎn)23=8個(gè)，有一個(gè)未被利用，即有一個(gè) 余碼點(diǎn)。編碼的平均長(zhǎng)度為：學(xué)習(xí)學(xué)習(xí)--——好資料更多精品文檔更多精品文檔學(xué)習(xí)學(xué)習(xí)--——好資料l=(0.25 +0.20+0.15)X2+(0.10+0.08+0.08+0.05+0.04+0.03+0.02)X5=3.2 (位)3/7擴(kuò)展編碼的信息冗余量為： R=1—H/l=(1—2.96/3.2 )X100%=7.5%2/8擴(kuò)展編碼要求短碼碼點(diǎn)數(shù)為 2,長(zhǎng)碼碼點(diǎn)數(shù)為8。所以短碼長(zhǎng)取2位，有碼點(diǎn)22=4個(gè)，用二個(gè)作擴(kuò)展標(biāo)志；長(zhǎng)碼長(zhǎng)取 2位，有碼點(diǎn)22X2=8個(gè)，碼點(diǎn)全部被利用，即沒有多余碼點(diǎn)。l=(0.25 +0.20)X2+(0.15+0.10+0.08+0.08+0.05+0.04+0.03+0.02)X4=3.1 (位)2/8擴(kuò)展編碼的信息冗余量為： R=1—H/l=(1—2.96/3.1 )X100%=4.5%可見，2/8擴(kuò)展編碼優(yōu)于3/7擴(kuò)展編碼。7經(jīng)統(tǒng)計(jì)，某種處理機(jī) 14條指令的使用頻度分別為：0.01,0.15,0.12,0.03,0.02,0.04,0.02,0.04,0.01,0.13,0.15,0.14 ,0.11,0.03。分另給出它們的定長(zhǎng)碼、Huffman編碼、只能有兩種碼長(zhǎng)且平均長(zhǎng)度盡可能短的擴(kuò)展編碼， 并分別計(jì)算三種編碼的平均長(zhǎng)度。0.150.150.140.130.120.110.040.040.030.030.020.020.010.012.28用于文字處理的某專用機(jī),在對(duì)傳送的文字符和空格進(jìn)行統(tǒng)計(jì)后，i0.20 0:0.172.28用于文字處理的某專用機(jī),在對(duì)傳送的文字符和空格進(jìn)行統(tǒng)計(jì)后，i0.20 0:0.175:0.05 6:0.08每個(gè)文字符用 4位十進(jìn)制數(shù)字(得出它們的使用頻度如下：1:0.06 2:0.08 3:0.11 4:0.087:0.13 8:0.03 9:0.010?9)編碼表不，空格用J表不。(1)若對(duì)數(shù)字0?9和空格采用二進(jìn)制編碼，試設(shè)計(jì)編碼平均長(zhǎng)度最短的編碼。(2)若傳送106個(gè)文字符號(hào)，且每個(gè)文字符號(hào)后均自動(dòng)跟一個(gè)空格，按最短的編碼，共需傳送多少個(gè)二進(jìn)制位？若傳送波特率為 9600bPS,共需傳送多少時(shí)間？2)。(3)若對(duì)數(shù)字0?9和空格采用42)。解：(1);操作碼編碼的平均長(zhǎng)度最短為 Huffman編碼，生成的Huffman樹，如圖所示，相應(yīng)的Huffman編碼如表所示。l=編碼如表所示。l=￡P(guān)iXli=3.23 (位)。i1(2)根據(jù)題意，每個(gè)字符的二進(jìn)制碼的平均長(zhǎng)度為:3.23X(4+1)=16.15(位)。若要傳輸106個(gè)字符，則要傳輸二進(jìn)制位數(shù)為： 106X16.15=1.615X107(位)106X4(4+1)=2X107(位)，傳輸時(shí)間若波特率為56Kb/s,則傳輸時(shí)間為：1.615X107/(56X10106X4(4+1)=2X107(位)，傳輸時(shí)間(3)當(dāng)采用四位定長(zhǎng)編碼時(shí)，則需要傳輸二進(jìn)制位數(shù)為:為：2X107/(56X103)=357(s)。1.000.400.600.200.200.270.330.11更多精品文檔0.040.030.14片0.060.13為：2X107/(56X103)=357(s)。1.000.400.600.200.200.270.330.11更多精品文檔0.040.030.14片0.060.130.160.170.080.080.081 6 4 2ITPi20Huffman編碼Li00.17000370.13010330.11110320.080010440.080011460.080110410.060111450.051110480.0311110590.011111152.29—臺(tái)模型機(jī)共有 7條指令，各指令的使用頻度分別為： 35% 25% 20% 10% 5% 3% 2%有8個(gè)通用數(shù)據(jù)寄存器，2個(gè)變址寄存器。(1)要求操作碼的平均長(zhǎng)度最短，請(qǐng)?jiān)O(shè)計(jì)操作碼的編碼，并計(jì)算操作碼編碼的平均長(zhǎng)度。(2)設(shè)計(jì)8位字長(zhǎng)的寄存器一一寄存器型指令 3條，16位字長(zhǎng)的寄存器一存儲(chǔ)器型變址尋址方式指令4條，變址范圍不小于正、負(fù)127。請(qǐng)?jiān)O(shè)計(jì)指令格式，并給出指令各字段的長(zhǎng)度和操作碼的編碼。2.30 一臺(tái)模型機(jī)共有 7條指令，各指令的使用頻度分別為： 35% 25% 20% 10% 5%3%, 2%有8個(gè)通用數(shù)據(jù)寄存器，2個(gè)變址寄存器。(1)要求操作碼的平均長(zhǎng)度最短，請(qǐng)?jiān)O(shè)計(jì)操作碼的編碼，并計(jì)算操作碼編碼的平均長(zhǎng)度。(2)設(shè)計(jì)8位字長(zhǎng)的寄存器一寄存器型指令 3條，16位字長(zhǎng)的寄存器一存儲(chǔ)器型變址尋址方式指令4條，變址范圍不小于正、負(fù) 127。請(qǐng)?jiān)O(shè)計(jì)指令格式，并給出指令各字段的長(zhǎng)度和操作碼的編碼。解：(1);操作碼編碼的平均長(zhǎng)度最短為 Hufman編碼，生成的Huffman樹如圖所示，相應(yīng)的Huffman編碼如表所示。i1n編碼如表所示。i1nl=" PiIiPiHuffman編碼Li2-4編碼（3/4）LiI10.35002002I20.25012012I30.20102102I40.10110311004I50.051110411014I60.0311110511104I70.0211111511114（2）由于通用寄存器有8個(gè)，則指令中通用寄存器字段應(yīng)為 3位；操作碼字段2位可有4個(gè)碼點(diǎn),用三個(gè)碼點(diǎn)表示三條指令，另一個(gè)碼點(diǎn)則作為擴(kuò)展標(biāo)志。所以 3條8位長(zhǎng)的寄存器一寄存器型指令格式如下：操作碼（2位）寄存器1（3位）寄存器2（3位）由于變址寄存器有2個(gè)，則指令中變址寄存器字段應(yīng)為 1位；變址范圍-127?+127,則指令中相對(duì)位移字段應(yīng)為8位；操作碼字段前2位可有4個(gè)碼點(diǎn)，用三個(gè)碼點(diǎn)表示三條指令，另一個(gè)碼點(diǎn)則作為擴(kuò)展標(biāo)志。擴(kuò)展2位正好可表示四條指令，操作碼字段則為 4位。所以4條16位長(zhǎng)的寄存器一存儲(chǔ)器型指令格式如下：操作碼（4位）寄存器（3位）版址寄存器（1位）相對(duì)位移（8位）特別地，當(dāng)采用3/4擴(kuò)展編碼時(shí)，使用頻度高的用短碼表示，使用頻度低的用長(zhǎng)碼表示，其相應(yīng)的編碼如表所示。2.31某處理機(jī)的指令字長(zhǎng)為16位，有二地址指令、一地址指令和零地址指令 3類，每個(gè)地址字段的長(zhǎng)度土勻?yàn)?位。（1）如果二地址指令有15條，一地址指令和零地址指令的條數(shù)基本相等。問一地址指令和零地址指令各有多少條？并為這3類指令分配操作碼。（2）如果指令系統(tǒng)要求這3類指令條數(shù)的比例大致為1:9:9,問這3類指令各有多少條？并為這 3類指令分配操作碼。解：（1）操作碼字段取4位可有24=16個(gè)碼點(diǎn)，用15個(gè)碼點(diǎn)（0000?1110）表示15條二地址指令，另一個(gè)碼點(diǎn)（1111）則作為擴(kuò)展標(biāo)志。所以15條二地址指令格式如下：操作碼（4位）地址碼1（6位）：地址碼2（6位）由于要求一地址指令和零地址指令的條數(shù)基本相等。所以地址碼 1字段6位擴(kuò)展有26=64個(gè)碼點(diǎn)，用63個(gè)碼點(diǎn)（1111000000?1111111110）表示63條一地址指令，另一個(gè)碼點(diǎn)（1111111111）則作為擴(kuò)展標(biāo)志。而用地址碼2字段6位擴(kuò)展有26=64個(gè)碼點(diǎn)，64個(gè)碼點(diǎn)都用來表示零地址指令，共有 64條。（2）在一中指令條數(shù)的比例大約 1:4.2:4.2,因此若使一地址指令和零地址指令加大一倍，則三類指令條數(shù)的比例大約1：9:9。

操作碼字段取4位時(shí)的16個(gè)碼點(diǎn)，用14個(gè)碼點(diǎn)（0000?1101）表示14條二地址指令，另二個(gè)碼點(diǎn)（1110與1111）則作為擴(kuò)展標(biāo)志。擴(kuò)展標(biāo)志（1110）擴(kuò)展地址碼1字段6位的64個(gè)碼點(diǎn)（1110000000—1110111111）全部用來表示一地址指令，有64條。擴(kuò)展標(biāo)志（1111）擴(kuò)展地址碼1字段6位的64個(gè)碼點(diǎn)，用62個(gè)碼點(diǎn)（11110000001111111101）表示62條一地址指令，另二個(gè)碼點(diǎn)（1111111110與1111111111）則作為擴(kuò)展標(biāo)志。這樣一地址指令，共有126條。擴(kuò)展標(biāo)志（1111111110與1111111111）擴(kuò)展地址碼2字段6位，各有64個(gè)碼點(diǎn)全部用來表示零地址指令，則有128條零地址指令。2.32某模型機(jī)9條指令使用頻度為：ADD（加）30%SUB （減）24%JOM （按負(fù)轉(zhuǎn)移）6% STO （存）7%JMP（轉(zhuǎn)移）7%SHR （右移）2%CIL （循環(huán)左移）3% CLA （清除）20% STP（停機(jī)）1%要求有兩種指令字長(zhǎng)，都按雙操作數(shù)指令格式編排，采用擴(kuò)展操作碼，并限制只能有兩種操作碼碼長(zhǎng)。設(shè)該機(jī)有若干通用寄存器，主存為16位寬，按字節(jié)編址，采用按整數(shù)邊界存儲(chǔ)，任何指令都在一個(gè)主存周期中取得，短指令為寄存器--寄存器型，長(zhǎng)指令為寄存器--主存型，主存地址應(yīng)能變址尋址。（1）僅根據(jù)使用頻度，不考慮其它要求，設(shè)計(jì)出全 Huffman操作碼，計(jì)算其平均碼長(zhǎng)；（2）考慮題目全部要求，設(shè)計(jì)優(yōu)化實(shí)用的操作碼形式，并計(jì)算其操作碼的平均碼長(zhǎng)；（3）該機(jī)允許使用多少可編址的通用寄存器？（4）畫出該機(jī)兩種指令字格式，標(biāo)出各字段之位數(shù)；（5）指出訪存操作數(shù)地址尋址的最大相對(duì)位移量為多少個(gè)字節(jié)？解：（1）根據(jù)給出的使用頻度，在構(gòu)造 Huffman樹的過程中，有兩個(gè)結(jié)點(diǎn)可供合并，因此可生成不同的Huffman樹，其中給出一棵如圖所示，相應(yīng)的 Huffman編碼如表所示。Huffman編碼的平均長(zhǎng)度為:Huffman編碼的平均長(zhǎng)度為:nl=￡pixlii=1l=0.3X2+0.24X2+0.2X2+0.07X4+0.07X4+0.06X4+0.03X5+0.02X6+0.01X6=2.61（位）STPSHR指令STPSHR指令I(lǐng)iPiHuffman編碼Li2-5編碼(3/6)LiADDI10.30012002SUBI20.24112012CLAI30.20102102STOI40.0700114110015JMPI50.0700104110105JOMI60.0600014110115CILI70.03000015111005SHRI80.020000016111015STPI90.010000006111105（2）任何指令都在一個(gè)主存周期中取得，那么短指令字長(zhǎng)為 8位，長(zhǎng)指令字長(zhǎng)為16位。又指令都是二地址指令，所以短指令寄存器--寄存器型的格式為：操作碼（2位）寄存器1（3位）寄存器2（3位）長(zhǎng)指令為寄存器--主存型的格式為:操作碼（5位）寄存器（3位）聲址寄存器（3位）相對(duì)位移（5位）由題意可知：指令操作碼采用擴(kuò)展編碼，且只能有兩種碼長(zhǎng)。從指令使用頻度來看， ADDSU*口CLA三條指令的使用頻度與其它指令的使用頻度相差較大，所以用兩位操作碼的三個(gè)碼點(diǎn)來表示三條指令，一個(gè)碼點(diǎn)作為擴(kuò)展碼點(diǎn)，且擴(kuò)展三位來表示六條指令，即采用2--4擴(kuò)展編碼構(gòu)成3/6編碼，2--4擴(kuò)展編碼如表所示。n2--4擴(kuò)展編碼（3/6）的平均長(zhǎng)度為：l=￡piXli=2.78=1（4）由短指令寄存器―寄存器型的格式可知，寄存器號(hào)字段長(zhǎng)度為 3位，寄存器個(gè)數(shù)為8個(gè)。則各字段長(zhǎng)度如圖格式所標(biāo)識(shí)。而對(duì)于長(zhǎng)指令寄存器--主存型，一般變址寄存器是某通用寄存器， 則變址寄存器號(hào)的字段長(zhǎng)度為 3位,則各字段長(zhǎng)度如圖格式所標(biāo)識(shí)。（5）由于相對(duì)位移字段長(zhǎng)度為 5位，因此訪存地址尋址的最大相對(duì)位移量為 25=32字節(jié)。弟早弟早在一臺(tái)單流水線多操作部件的處理機(jī)上執(zhí)行下面的程序，每條指令的取指令、指令譯碼需要一個(gè)時(shí)鐘周期，MOVEADMMULB作分另需要2個(gè)、3個(gè)和4個(gè)時(shí)鐘周期，每個(gè)操作都在第一個(gè)時(shí)鐘周期從通用寄存器中讀操作數(shù)，在最后一個(gè)時(shí)鐘周期把運(yùn)算結(jié)果寫到通用寄存器中。k:MOVER1,R0;R1—(R0)k+1:MULR0,R2,R1;Rk(R2)X(R1)k+2：ADDR0，R2,R3;Rk(R2)+(R3)（1）就程序本身而言，可能有哪幾種數(shù)據(jù)相關(guān) ？（2）在程序?qū)嶋H執(zhí)行過程中，哪幾種數(shù)據(jù)相關(guān)會(huì)引起流水線停頓

（3）畫出指令執(zhí)行過程的流水線時(shí)空?qǐng)D，并計(jì)算完成這解：（1）就程序本身而言，可能有三種數(shù)據(jù)相關(guān)。若3條指令共需要多少個(gè)時(shí)鐘周期?3條指令順序流動(dòng)，則k指令對(duì)R1寄存器的寫33條指令共需要多少個(gè)時(shí)鐘周期?3條指令順序流動(dòng)，則k指令對(duì)R1寄存器的寫3條指令異步流動(dòng)，則k指令對(duì)R0寄存器的讀與k+1指令對(duì)R0寄存器的寫形成的“先讀后寫”相關(guān),k+2指令對(duì)R0寄存器的寫與k+1指令對(duì)R0寄存器的寫形成的“寫一寫”相關(guān)。（2）在程序?qū)嶋H執(zhí)行過程中，二種數(shù)據(jù)相關(guān)會(huì)引起流水線停頓。一是“先寫后讀”相關(guān)， k指令對(duì)R1的寫在程序執(zhí)行開始后的第四個(gè)時(shí)鐘； k+1指令對(duì)R1的讀對(duì)指令本身是第三個(gè)時(shí)鐘，但 k+1指令比k指令晚一個(gè)時(shí)鐘進(jìn)入流水線，則在程序執(zhí)行開始后的第四個(gè)時(shí)鐘要讀 R1。不能在同一時(shí)鐘周期內(nèi)讀寫同一寄存器，因此k+1指令應(yīng)推遲一個(gè)時(shí)鐘進(jìn)入流水線，產(chǎn)生了流水線停頓。二是“寫一寫”相關(guān)， k+1指令對(duì)R0的寫對(duì)指令本身是第六個(gè)時(shí)鐘，而要求該指令進(jìn)入流水線應(yīng)在程序執(zhí)行開始后的第三個(gè)時(shí)鐘，所以對(duì)R0的寫是在程序執(zhí)行開始后的第八個(gè)時(shí)鐘。 k+2指令對(duì)R0的寫對(duì)指令本身是第五個(gè)時(shí)鐘，而 k+2指令比k+1指令晚一個(gè)時(shí)鐘進(jìn)入流水線，則在程序執(zhí)行開始后的第四個(gè)時(shí)鐘，所以對(duì) R0的寫是在程序執(zhí)行開始后的第八個(gè)時(shí)鐘。不能在同一時(shí)鐘周期內(nèi)寫寫同一寄存器，因此 k+2指令應(yīng)推遲一個(gè)時(shí)鐘進(jìn)入流水線，產(chǎn)生了流水線停頓。另外，可分析“先讀后寫”相關(guān)不會(huì)產(chǎn)生流水線的停頓。（3）由題意可認(rèn)位該指令流水線由六個(gè)功能段取指、譯碼、取數(shù)、運(yùn)一、運(yùn)二和存數(shù)等組成，則程存數(shù)K存數(shù)K+1存數(shù)K+2存數(shù)運(yùn)二K+1運(yùn)二運(yùn)一K+1運(yùn)一 K+2運(yùn)一取數(shù)K 取數(shù)K+1取數(shù) K+2 取數(shù)譯碼K 譯碼 K+1譯碼K+2 譯碼取指1K取指 K+1 取指K+2取指時(shí)間0 12 3 4 5 67 893條指令順序流動(dòng)，共需要9個(gè)時(shí)鐘周期。序指令執(zhí)行過程的流水線時(shí)空?qǐng)D如下圖所示。若“空間某流水線由4個(gè)功能部件組成，每個(gè)功能部件的執(zhí)行時(shí)間都為△ t。當(dāng)輸入10個(gè)數(shù)據(jù)后，停頓5t,又輸入10個(gè)數(shù)據(jù)，如此重復(fù)。計(jì)算流水線的實(shí)際吞吐率、加速比和效率，并畫出時(shí)空?qǐng)D。解：該題中的流水線的任務(wù)是非連續(xù)流入的，因此不能直接應(yīng)用公式直接計(jì)算，要利用時(shí)空?qǐng)D。題意的流水線時(shí)空?qǐng)D如下圖所示。TP=10/15AtTP=10/15At=0.67/ At0/Tk=10X4At/15At=2.671234567891011212345678910122345(578/)10-234567891012S4S3S2S11“空間0123456789101112131415161718時(shí)間E=4X10At/4X15At=0.673.11有一個(gè)四段指令流水線為取指（IF）、譯碼（ID）、執(zhí)行（ER、寫回（WB,分支指令在第二個(gè)時(shí)鐘周期未決定是不是條件失敗分支，在第三個(gè)時(shí)鐘周期未決定是不是成功分支，還假定第一個(gè)時(shí)鐘周

期的操作和條件分支無關(guān)，并略去其它流水線停頓。要求：(1)分別畫出無條件分支、發(fā)生的條件分支、不發(fā)生的條件分支時(shí)指令執(zhí)行的時(shí)空?qǐng)D。(2)假設(shè)條件分支指令占所有指令的 20%且其中60%旨令可能執(zhí)行，無條件分支占 5%問實(shí)際的流水線加速比是多少。解：(1)根據(jù)題意，分支指令采用的是流水線停頓的方法來處理。 而判斷條件分支指令讓流水線停頓，應(yīng)在取指功能段后設(shè)計(jì)一個(gè)“指令分析器”來判斷流水線是否停頓。顯然，無條件分支指令與條件成功(發(fā)生條件)分支是一樣的，需要在第三個(gè)時(shí)鐘周期未決定下一條指令的地址，因此流水線要停頓二個(gè)時(shí)鐘周期。對(duì)于條件失敗(條件不成功)分支，需要在第二個(gè)時(shí)鐘周期未決定下一條指令的地址，因此流水線要停頓一個(gè)時(shí)鐘周期。(2)串行執(zhí)行N條指令的時(shí)間為：T1=N-k-At,流水線方式執(zhí)行N條指令的時(shí)間為：Tn=(k-1)At+(N+N-5%-2+N?20%-60%-1.5)AtSn=T1/Tn=k/1.28103.13用一條5個(gè)功能段的浮點(diǎn)加法器流水線計(jì)算 F=￡(Ai),每個(gè)功能段的延遲時(shí)間，每個(gè)功能段的延i1遲時(shí)間均相等，流水線的輸出端與輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。要求用盡可能短的時(shí)間完成計(jì)算，畫出流水線時(shí)空?qǐng)D，計(jì)算流水線的實(shí)際吞吐率、加速比和效率。解：為使計(jì)算過程充分利用流水線的性能，避免“先寫后讀”相關(guān)，需要將計(jì)算的算法改為：((((A+A2)+(A+A4))+(A9+A10))+((A5+A6)+(A7+A9)))且按括號(hào)的優(yōu)先次序計(jì)算九次加法，相應(yīng)的流水線時(shí)空?qǐng)D如下圖所示。t空間TP=9/21AtTP=9/21At=0.429/At0/Tk=9X5At/21At=2.143S51;?3456789S4123456789S3123456789S2123456789S112345(5789時(shí)間 0123456789101112131415161718192021E=5X9At/5X21At=0.4293.15有一條3個(gè)功能段的流水線如下圖所示，每個(gè)功能段的延遲時(shí)間均為△ t,但是，功能段險(xiǎn)的輸出要返回到它自己的輸入端循環(huán)執(zhí)行一次。輸入—LS_I HS2 H_SL_I―'輸出△t At At(1)如果每隔一個(gè)△t向流水線連續(xù)輸入任務(wù)，這條流水線會(huì)發(fā)生什么問題？(2)求這條流水線能夠正常工作的實(shí)際吞吐率、加速比和效率。(3)可用什么辦法來提高流水線的吞吐率，畫出改進(jìn)后的流水線結(jié)構(gòu)。解：(1)每個(gè)任務(wù)在段險(xiǎn)要反饋循環(huán)一次，執(zhí)行時(shí)間為 2At,其它各段的執(zhí)行時(shí)間為At,因此應(yīng)按

瓶頸段的執(zhí)行時(shí)間2At流入任務(wù)，才不會(huì)發(fā)生沖突現(xiàn)象，否則會(huì)發(fā)生流水線的阻塞。(2)若連續(xù)輸入n個(gè)任務(wù)，則流水線的實(shí)際吞吐率、加速比和效率分別為：TP=n/ (4At+2(n-1)At)=n/2(n+1)AtS=4nAt/(4At+2(n-1)At)=2n/(n+1)E=4n At/3(4At+2(n-1)At)=2n/3(n+1)(3)為提高流水線的吞吐率，可重復(fù)設(shè)置段S,并使兩個(gè)段S2串連在一起，從而消除瓶頸段 S2,而且各段執(zhí)行時(shí)間相等為At,流水線的段數(shù)為4。流水線的結(jié)構(gòu)如下圖所示。輸入輸出△t△t△t At3.16在一個(gè)5段的流水線處理機(jī)上需經(jīng)輸入輸出△t△t△t At3.16在一個(gè)5段的流水線處理機(jī)上需經(jīng)9At才能完成一個(gè)任務(wù)，其預(yù)約表為:(1)寫出流水線的初始沖突向量。(2)畫出流水線任務(wù)調(diào)度的狀態(tài)有向圖。(3)求出流水線的最優(yōu)調(diào)度策略及最小平均延遲時(shí)間和流水線的最大吞吐率。(4)按最優(yōu)調(diào)度策略連續(xù)輸入8個(gè)任務(wù)時(shí)，流水線的實(shí)際吞吐率是多少解：(1)解：(1)根據(jù)初始沖突向量的構(gòu)成方法,對(duì)預(yù)約表各行中打“X”的拍數(shù)求出差值，除去重復(fù)的后匯集在F={1,5,6,8}F={1,5,6,8}。由F可得到初始沖突向量為:C=(2)根據(jù)后繼沖突向量的遞推規(guī)則（10110001）Cj=SHR（k）（C）G四個(gè)后繼狀態(tài)：C=SHR⑵(Co)VC0:=10111101C2=SHR⑶（Q）VCo=:10110111C3=SHR”）（G）VCO=10111011C4=SHR⑺（Co）VC0:=10110001=C0C二個(gè)后繼狀態(tài)：C5=SHR⑵(C)VCo:=10111111C6=SHR⑺（G）VC0=:10110001=C0G二個(gè)后繼狀態(tài)：G=SHR⑷(G)VCo:=10111011=C3C8=SHR⑺（Q）VCd=10110001=C0G二個(gè)后繼狀態(tài)：G=SHR⑶(G)VCo:=10110111=C2Co=SHR7）（G）VC0=:10110001=C0。一個(gè)后繼狀態(tài)：C11=SHR：7)(C5)VCo=：10110001=C0起，即得到延遲禁止表為由后繼狀態(tài)和引起狀態(tài)轉(zhuǎn)移的時(shí)間間隔可得到狀態(tài)有向圖如上圖所示。(3)由狀態(tài)轉(zhuǎn)移有向圖可得到無沖突的任務(wù)調(diào)度策略及其平均延遲時(shí)間，如下表所示。調(diào)度策略平均延遲時(shí)間(2,2,7)(2+2+7)At/3=3.67At(2,7)(2+7)At/2=由后繼狀態(tài)和引起狀態(tài)轉(zhuǎn)移的時(shí)間間隔可得到狀態(tài)有向圖如上圖所示。(3)由狀態(tài)轉(zhuǎn)移有向圖可得到無沖突的任務(wù)調(diào)度策略及其平均延遲時(shí)間，如下表所示。調(diào)度策略平均延遲時(shí)間(2,2,7)(2+2+7)At/3=3.67At(2,7)(2+7)At/2=4.5At(3,4,7)(3+4+7)At/3=4.67At(3,7)(3+7)At/2=5At(4,3,7)(4+3+7)At/3=4.67At(4,7)(4+7)At/2=5.5At⑺ 7△t特別地，從C0出發(fā)的［3,(4,3)］也是一個(gè)任務(wù)調(diào)度策略，除第一條有向弧外，第二、三條有向組成一個(gè)環(huán)路，該調(diào)度策略為( 4,3)。從表中可以得到平均延遲時(shí)間最小的調(diào)度策略為( 4,3),該調(diào)度策略則為最優(yōu)調(diào)度策略，相應(yīng)的最小平均延遲時(shí)間為3.5At,所以流水線的最大吞吐率為：TPmax=1/ (3.5At)=0.286/At3,(4,3) (4+3)At/2=3.5At(4)按最優(yōu)調(diào)度策略[3,(4,3)]連續(xù)輸入8個(gè)任務(wù)時(shí)，流水線的實(shí)際吞吐率為:TP=8/[ (3+4+3+4+3+4+3+9 )At]=0.24/At3.17有一個(gè)5段流水線的預(yù)約表如下：(1)畫出流水線調(diào)度狀態(tài)有向圖。(2)分別求出允許不等間隔調(diào)度和等間隔調(diào)度的最優(yōu)調(diào)度策略以及這兩種調(diào)度策略的最大吞吐率。解：(1)根據(jù)初始沖突向量的構(gòu)成方法,對(duì)預(yù)約表各行中打“X”的拍數(shù)求出差值，除去重復(fù)的后匯集在起，即得到延遲禁止表為F={1,3,6}。由F可得到初始沖突向量為:根據(jù)后繼沖突向量的遞推規(guī)則C=SHRk)。G三個(gè)后繼狀態(tài)：0=SHR⑵(Q)VC0=101101C2=SHR(4)(Q)VC0:=100111C3=SHR'5)9)VG=:100101=C0C二個(gè)后繼狀態(tài)：C4=SHR2)(G)VC0=101111C5=SHR⑸(C)VG:=100101=C0C2二個(gè)后繼狀態(tài)：C6=SHR⑷(G)VC0=100111=C2C=SHR'5)9)VC0=:100101=C0C4一個(gè)后繼狀態(tài)：C8=SHR⑸(C4)VC0=100101=C0C 0=(100101)Co則可得出所有的后繼狀態(tài)，具體有:由后繼狀態(tài)和引起狀態(tài)轉(zhuǎn)移的時(shí)間間隔可得到狀態(tài)有向圖如上圖所示。(2)由狀態(tài)轉(zhuǎn)移有向圖可得到無沖突的任務(wù)調(diào)度策略及其平均延遲時(shí)間，如下表所示。調(diào)度策略平均延遲時(shí)間(2,5)(2+5)At/2=3.5At(4,5)(4+5)At/2=4.5At(5) 5△t(2,2,5)(2+2+5)At/3=3At4,(4)4 At特別地，從Co出發(fā)的［4,(4)］也是一個(gè)任務(wù)調(diào)度策略，除第一條有向弧外，第二條有向弧是一個(gè)環(huán)路，該調(diào)度策略為(4)。從表中可以得到平均延遲時(shí)間最小的等間隔和不等間隔的調(diào)度策略為［4,(4)］和(2,2,5),相應(yīng)的最小平均延遲時(shí)間為4At和3At,所以流水線的最大吞吐率為：Bmax=1/ (3At)=0.33/AtTPAmax=1/ (4At)=Bmax=1/ (3At)=0.33/At(3)按等間隔最優(yōu)調(diào)度策略［4,(4)］連續(xù)^^入10個(gè)任務(wù)時(shí)，流水線的實(shí)際吞吐率為:TP=10/[ (4+4+4+4+4+4+4+4+4+7 )△t]=10/43At按不等間隔最優(yōu)調(diào)度策略(2,2,5)連續(xù)輸入10個(gè)任務(wù)時(shí)，流水線的實(shí)際吞吐率為：TP=10/[ (2+2+5+2+2+5+2+2+5+7 )△t]=5/17At第四章習(xí)題4.13由3個(gè)訪問速度、存儲(chǔ)容量和每位價(jià)格都不相同的存儲(chǔ)器構(gòu)成一個(gè)存儲(chǔ)系統(tǒng)， 3個(gè)存儲(chǔ)器M1、M2和M3的訪問周期分別為R1、R2和R3,存儲(chǔ)容量分別為Sl、S2和S3,每位價(jià)格分別為C1、C2和C3,Ml靠近CPU(1)寫出這個(gè)三級(jí)存儲(chǔ)系統(tǒng)的等效訪問時(shí)間、等效存儲(chǔ)容量 S和等效每位價(jià)格C的表達(dá)式。TOC\o"1-5"\h\z(2)在什么條件下，整個(gè)存儲(chǔ)系統(tǒng)的每位平均價(jià)格接近于 C3?解：(1)設(shè)H為CPU^存在M中的概率，則存儲(chǔ)系統(tǒng)的等效訪問時(shí)間、存儲(chǔ)容量和每位價(jià)格分別為:3 3 3T=ZHi*Ti、S=S3C=(￡Ci*Si)/S,且￡Hi=1。i1 i1 i1(2)當(dāng)三個(gè)存儲(chǔ)器的存儲(chǔ)容量之間有 S3》S2?S1時(shí)，C=C&4.17在一個(gè)采用組相聯(lián)映象方式的 Cache存儲(chǔ)系統(tǒng)中，主存由Bo?B7共8塊組成，Cache有2組,每組2塊，每塊大小為16B。在一個(gè)程序執(zhí)行過程中，訪存的主存塊地址流為： Be, B2, B4, B1,區(qū)，Bs,Bo,B,B5, E3O(1)寫出主存地址的格式，并標(biāo)出各字段的長(zhǎng)度。(2)寫出Cache地址的格式，并標(biāo)出各字段的長(zhǎng)度。(3)指出主存與Cache之間各個(gè)塊的映象關(guān)系。(4)若Cache的4個(gè)塊號(hào)為Co、G、C2和G,列出程序執(zhí)行過程中的 Cache塊地址流。(5)若采用FIFO替換算法，計(jì)算Cache的塊命中率。(6)若采用LRU替換算法，計(jì)算Cache的塊命中率。(7)若改為全相聯(lián)映象方式，再做(5)和(6)。(8)若在程序執(zhí)行過程中，每從主存裝入一塊到 Cache,平均要對(duì)這個(gè)塊訪問 16次，計(jì)算在這種情況下的Cache命中率。解：(1)(2)采用組相聯(lián)映象時(shí)，主存和 Cache地址的格式分別為：區(qū)號(hào)E區(qū)號(hào)E區(qū)內(nèi)組號(hào)G主存組內(nèi)塊號(hào)E塊內(nèi)地址W組號(hào)g組內(nèi)塊號(hào)b塊內(nèi)地址w主存按Cache的大小分區(qū)，現(xiàn)主存有8個(gè)塊，Cache有2X2=4個(gè)塊，則主存分為8/4=2個(gè)區(qū)，區(qū)號(hào)E的長(zhǎng)度為1位。又每區(qū)號(hào)Gg的長(zhǎng)度都為1個(gè)塊，則塊號(hào)B、b的位。每塊大小為16個(gè)地址Ww的長(zhǎng)度都為4的長(zhǎng)度為1位。又每區(qū)號(hào)Gg的長(zhǎng)度都為1個(gè)塊，則塊號(hào)B、b的位。每塊大小為16個(gè)地址Ww的長(zhǎng)度都為4(3)根據(jù)組相聯(lián)存塊0?7與Cache塊象關(guān)系為：主存塊0、1、0、1之間全相聯(lián)，主存塊時(shí)間：567812主存塊地址流：Cache塊地址流:44*4*4*4*00*55511111*44*4*4*66*6*6*6*6*33333*3*222222*2*2*2*772、3、6、7與Cache塊2、3之間全相聯(lián)。9B7聯(lián)映象的規(guī)則，該主一種Cache塊地址流換算法為FIFO)。1234(4)根據(jù)組相存塊地址流相應(yīng)的如下表所示(組內(nèi)替6B21B4B6B3B0B4B51C0C2C2C0C0C0有2個(gè)組，則組位。而每組有2長(zhǎng)度又都為1存儲(chǔ)字，故塊內(nèi)位。映象的規(guī)則，主0?3之間的映4、5與Cache塊1011(5)組內(nèi)替換算法采用FIFO時(shí)，Cache塊0?3的使用過程如下表所示。時(shí)間： 123456789101112主存塊地址流： B6B2B4B1B4B6B3B0B4B5B7B3Cache塊0Cache塊1Cache塊2Cache塊3命中命中 命中可見命中三次，Cache塊命中率為H=3/12=0.25 。(6)組內(nèi)替換算法采用LRU時(shí)，Cache塊0?3的使用過程如下表所示。時(shí)間：123456789101112主存塊地址流： B6B2B4B1B4B6B3B0B4B5B7B3Cache塊0Cache塊1Cache塊2Cache塊3命中命中 命中 命中可見命中四次，Cache塊命中率為H=4/12=0.33 。(7)全相聯(lián)映象的規(guī)則是主存塊 0?7可裝入Cache塊0?3的任一塊上。當(dāng)替換算法采用FIFO時(shí)，Cache塊0?3的使用過程如下表所示。時(shí)間：123456789101112主存塊地址流： B6B2B4B1B4B6B3B0B4B5B7B3Cache塊0Cache塊1Cache塊2Cache塊3命中命中 命中 命中可見命中四次， Cache塊命中率為H=4/12=0.33 。當(dāng)替換算法采用LRU時(shí)，Cache塊0?3的使用過程如下表所示。時(shí)間：123456789101112主存塊地址流： B6B2B4B1B4B6B3B0B4B5B7B3Cache塊0Cache塊1Cache塊2Cache塊3命中命中 命中可見命中三次， Cache塊命中率為H=3/12=0.25 。(8)當(dāng)命中三次時(shí)， Cache的命中率為H=(12X16-9)/(12X16)=1,當(dāng)命中四次時(shí)， Cache的命中率為H= (12X16-8)/(12X16)=1。4.18在某聯(lián)目錄表實(shí)現(xiàn)地址6666*6*6*33333*3*222222*00000中，Cache的谷重是444444*4*555儲(chǔ)體組成的低位交總?cè)萘渴?MB,每一1111111*77位，。采用全相聯(lián)映象、相變換Cache存儲(chǔ)器2cB,主存是由m個(gè)存叉訪問存儲(chǔ)器，主存?zhèn)€存儲(chǔ)體的字長(zhǎng)是w(1)畫出地址變換圖。(2)寫出主存地址和Cache地址的格式，并標(biāo)出各字段的長(zhǎng)度。(3)說明目錄表的行數(shù)、相聯(lián)比較的位數(shù)和目錄表的寬度。解：(1)主存地址解：(1)主存地址目錄表共有Q個(gè)字Cache地址命中(2)采用全相聯(lián)映象時(shí)，主存和 Cache地址的格式分別為:

主存塊號(hào)B主存塊號(hào)B塊內(nèi)地址W組內(nèi)塊號(hào)b塊內(nèi)地址w主存和Cache單元數(shù)分別為：8X2Mw、8X2c/w,相應(yīng)的地址長(zhǎng)度分別為：log2(8X2Mw)=M+3-log2W、log2(2c/w)=C+3-log2W。塊的大小為m個(gè)存儲(chǔ)字，則主存和Cache的塊內(nèi)地址長(zhǎng)度均為：log2日所以主存和Cache的塊號(hào)長(zhǎng)度分別為：(M+3-log2w)-log2m=M+3-log2wm(C+3-log2w)-log2m=C+3-log2wm(3)相聯(lián)目錄表的行數(shù)為(3)相聯(lián)目錄表的行數(shù)為Cache的塊數(shù)，即Cb=2即M+3-log2wm，目錄表的寬度(位數(shù))為主存塊號(hào)長(zhǎng)度、C+3-log2wm+1=M+C+6-2log2wm+1(有效位一位)。(C+3-log2wm)=2C+3/wm；相聯(lián)比較的位數(shù)為主存塊號(hào)長(zhǎng)度，Cache塊號(hào)長(zhǎng)度和有效位的和，即 M+3-log2wm+麥人位王仔貝號(hào)13110203120110004.25某頁式虛擬存儲(chǔ)器的虛擬空間分為 8個(gè)虛頁,虛頁號(hào)為0?7,頁的大小為1024個(gè)字，主存容量為4096個(gè)字，頁表內(nèi)容如表所示。(1)列出會(huì)發(fā)生頁面失效的全部虛頁號(hào)。(2)按以下虛地址計(jì)算出變換的主存實(shí)地址：0 , 3728, 1023, 1024,2055 ,7800, 4096, 6800。解：(1)頁表的行號(hào)即是虛頁號(hào)，裝入位為“ 1”表示相應(yīng)虛頁已裝入主存中，實(shí)頁號(hào)指出的實(shí)頁位置；裝入位為“0”表示相應(yīng)虛頁未裝入主存中，該行實(shí)頁號(hào)無效。所以由給出的表可知，發(fā)生頁面失效的全部虛頁號(hào)是：2,3,5,7。(2)頁式管理的虛擬存儲(chǔ)器的虛、實(shí)地址變換的計(jì)算步驟如下：①由虛地址Av計(jì)算相應(yīng)的虛頁號(hào)P和頁內(nèi)地址D:P二 「虛地址Av/頁面長(zhǎng)度1024個(gè)字」 D=A vPX頁面長(zhǎng)度②由虛頁號(hào)查頁表的相應(yīng)行，若裝入位為“ 0”，則發(fā)生頁面失效，需調(diào)進(jìn)頁，無需地址變換；若裝入位為“1”，則取出相應(yīng)的實(shí)頁號(hào)p。③由于d=D,則可由實(shí)頁號(hào)p和頁內(nèi)地址D計(jì)算出實(shí)地址A=pX1024+D=按上述步驟，則可由虛地址計(jì)算出變換出主存實(shí)地址如下表所示。虛地址A虛頁號(hào)P頁內(nèi)地址D裝入位實(shí)貝號(hào)p頁內(nèi)地址d實(shí)地址a0001303072372836560貝囿失效無102301023131023409510241011010242055270貝囿失效無780076320貝囿失效無409640120204868006656106566564.26一個(gè)程序由1200條指令組成，每條指令的字長(zhǎng)均為 4個(gè)字節(jié)。假設(shè)這個(gè)程序訪問虛擬存儲(chǔ)器的字地址流為：12 ,40,260,280,180,800,500,560,600,1100,1200,1000采用FIFO替換算法，分配給這個(gè)程序的主存容量為 2048B。在下列不同的頁面大小情況下， 分別寫出這程序執(zhí)行過程中依次訪問的虛頁地址流，并計(jì)算主存實(shí)頁命中率。(1)頁的大小為1024B。 (2)頁的大小為512B。(3)頁的大小為2048B。 (4)比較(1)、(2)、(3)的結(jié)果，可得出什么結(jié)論？(5)假設(shè)把分配給該程序的主存容量增加到 4096B,頁的大小為1024B,再計(jì)算主存實(shí)頁命中率。由此又可以得出什么結(jié)論？解：題中給出了字虛地址流，由虛地址可得出其相應(yīng)的虛頁號(hào)為：虛頁號(hào)別地題中虛地址流是以字為單位，而頁面大小是以字節(jié)為單位，且字長(zhǎng)為另外，由給出的分配給主存容量和頁面大小可得出相應(yīng)的實(shí)頁數(shù)為：實(shí)頁數(shù)=「虛地址/頁面大小」；特4B解：題中給出了字虛地址流，由虛地址可得出其相應(yīng)的虛頁號(hào)為：虛頁號(hào)別地題中虛地址流是以字為單位，而頁面大小是以字節(jié)為單位，且字長(zhǎng)為另外，由給出的分配給主存容量和頁面大小可得出相應(yīng)的實(shí)頁數(shù)為：實(shí)頁數(shù)=「虛地址/頁面大小」；特4B。=「主存容量/頁面大小」。(1)頁面大小(1)頁面大小1024B=256字,實(shí)頁數(shù)=「2048B/1024B」=2。根據(jù)給出的程序訪存的字地址流對(duì)主存的使用過程為:虛頁地址流：0 0110312 244 3虛頁地址流：0 0110312 244 30頁000*0*0*333*3*441頁1111*1*222*2*虛字地址流： 12402602801808005005606001100120010004*3命中命中命中命中命中命中則有主存命中率為： Hi=6/12=0.5(2)則有主存命中率為： Hi=6/12=0.5(2)頁面大小512B=128字，根據(jù)給出的程序訪存的字地址流對(duì)主存的使用過程為:實(shí)頁數(shù)=「2048B/512B」二4。虛字地址流:虛頁地址流:124026028018080056060011001200100089 70*33虛字地址流:虛頁地址流:124026028018080056060011001200100089 70*33333*722*44444*111*1*88850040216*命中命中命中則有主存命中率為： Hb=3/12=0.25(3)則有主存命中率為： Hb=3/12=0.25(3)頁面大小1024B=512字，根據(jù)給出的程序訪存的字地址流對(duì)主存的使用過程為:實(shí)頁數(shù)=「2048B/2048B」二1。虛字地址流:虛頁地址流:1240026028018018000虛字地址流:虛頁地址流:12400260280180180005005601 1 260021100112001000命中 命中命中命中命中命中命中 命中則有主存命中率為： H3=6/12=0.5(4)當(dāng)主存容量不變時(shí)，①中的頁長(zhǎng)>②中的頁長(zhǎng)，且有H>H2,(4)當(dāng)主存容量不變時(shí)，①中的頁長(zhǎng)因在于頁長(zhǎng)減小，虛、實(shí)頁數(shù)增加，程序跨頁訪問的概率增大，導(dǎo)致主存命中率下降。另外，當(dāng)主存容量不變時(shí)，③中的頁長(zhǎng) >①中的頁長(zhǎng)，且有H=H2,說明頁長(zhǎng)加大，主存命中率不變。原因在于頁長(zhǎng)加大，虛、實(shí)頁數(shù)減??；一方面虛頁數(shù)減小，可降低跨頁訪問的概率，可提高主存命中率；另一方面實(shí)頁數(shù)減小，主存替換概率增大，導(dǎo)致主存命中率下降。(5)頁面大小1024B=256(5)頁面大小1024B=256字,實(shí)頁數(shù)二「4096B/1024B」二4。根據(jù)給出的程序訪存的字地址流對(duì)主存的使用過程為:虛字地址流:1240260280180800500560600110012001000虛字地址流:虛頁地址流：0 0 1 1 0 3 1 2 2 40*0*444111111*1*1*頁頁頁命中 命中命中則有主存命中率為111111*1*1*頁頁頁命中 命中命中則有主存命中率為： Hk=7/12=0.58命中命中命中命中當(dāng)頁長(zhǎng)不變時(shí)，主存容量增大，實(shí)頁數(shù)增加時(shí)，主存命中率增大。但不是總是如此。4.27采用頁式虛擬存儲(chǔ)器，分時(shí)運(yùn)行兩道程序，其中程序X為：DO50I=1,3B(I)=A(I) -C(I)IF (B(I).LE.0)GOTO40D(I)=2*C(I) -A(I)IF (D(I).EQ.0)GOTO5040E(I)=050CONTINUEDATA:A=(-4,3,0)C=(-3,0,1)2,每個(gè)數(shù)組分別存放在不同的頁面中； 而程序Y在運(yùn)行過程中，其數(shù)組將依次用到程序空間的第3,5,4,2,5, 3,1, 3, 2,5,1, 3, 1,5,2頁。如果采用LRU算法替換，實(shí)存只有 8頁位置可供存放數(shù)組之用。試問為這兩道程序的數(shù)組分配多少個(gè)實(shí)頁最為合理？為什么？解：程序Y運(yùn)行過程中要使用的數(shù)組虛頁地址流題中已給出， LRU算法是堆棧算法，用堆棧對(duì)其模擬處理一次的過程如下所示。時(shí)間：1234567時(shí)間：123456789101112131415虛頁地址流：3 5423 54353虛頁地址流：3 5423 5435335425 3 12 5 34 2 53 4 25313 2 51 3 25 1 32 5 132511 3 15 1 32 5 53 2 23152521 53 12 3S(1)StS(1)St(2)St(3)St(4)St⑸St(6)n=1n=2 命中n=3 命中 命中命中命中命中n=4 命中命中n=5 命中命中命中命中命中命中

命中命中命中命中命中命中命中命中

命中命中命中命中程序XSt⑸St(6)n=1n=2 命中n=3 命中 命中命中命中命中n=4 命中命中n=5 命中命中命中命中命中命中

命中命中命中命中命中命中命中命中

命中命中命中命中數(shù)組所在的虛頁號(hào)。E來表示E;第二CA、D、程序做三次循環(huán)。第一次循環(huán)B(1)=-1<0,轉(zhuǎn)40號(hào)語句E(1)=0,所以使用數(shù)組為A、CB、次循環(huán)B(2)=2>0,順序執(zhí)行D(2)=-2,又D(2)<>0,順序執(zhí)行E(2)=0,所以使用數(shù)組為A、CBE;第三次循環(huán)同第一次循環(huán)為A、E來表示E;第二CA、D、NHXH時(shí)間：1234567891010012131415ACB)EA2C5B(CADEACBE 虛頁地址流：A3A(3/153 E4A5C1BCADEACBBCADE4A8/1夕B1?15A/\BCADEACE510/1A)C10/15E1EEBCCDEAA、C、BE、A、C、BC、A、DE、A、C、BE用堆棧對(duì)其模擬處理一次的過程如下所示。EBBBDD11CASt(1)St(2)St(3)St(4)St⑸St(6)n=1n=3n=4 命中命命中命中 命中n=3n=4 命中命命中命中 命中命中命中 命中命中 命n=5 命中命命中命中 命中命中命中命中命由堆棧處理結(jié)果可得出相應(yīng)于 X和Y程程配衣W二加巍YHXHrHran/dr353/1510/156.5/15