計算機系統(tǒng)結構第2版課后習題答案

PAGE1目錄第一章(P33)1.7-1.9（透明性概念），1.12-1.18（Amdahl定律），1.19、1.21、1.24（CPI/MIPS）第二章(P124)2.3、2.5、2.6（浮點數(shù)性能），2.13、2.15（指令編碼）第三章(P202)3.3（存儲層次性能），3.5（并行主存系統(tǒng)），3.15-3.15加1題（堆棧模擬），3.19中(3)(4)(6)(8)問（地址映象/替換算法--實存狀況圖）第四章(P250)4.5（中斷屏蔽字表/中斷過程示意圖），4.8（通道流量計算/通道時間圖）第五章(P343)5.9（流水線性能/時空圖），5.15（2種調度算法）第六章(P391)6.6（向量流水時間計算），6.10（Amdahl定律/MFLOPS）例,習題第一章(P33)1.1解釋下列術語層次結構，計算機系統(tǒng)結構，計算機組成，計算機實現(xiàn)，透明性，由上而下設計，由下而上設計，由中間向兩邊設計，軟件兼容，向上兼容，固件，系列機，兼容機，模擬，仿真，虛擬機，宿主機，指令流，數(shù)據(jù)流，單指令流單數(shù)據(jù)流，多指令流多數(shù)據(jù)流，Amdahl定律，CPI，MIPS，MFLOPS。1.2每一級為了執(zhí)行一條指令需要下一級的N條指令解釋，若執(zhí)行第一級的一條指令需kns，那么執(zhí)行第2級、第3級、第4級的指令需要多少時間？第1級1條1級指令kns第2級1條2級指令N條1級指令1·N·kns=Nkns第3級1條3級指令N條2級指令1·N·N·kns=N2kns第4級1條4級指令N條3級指令1·N·N·N·kns=N3kns1.4每一級指令能完成下一級的M條指令的工作量，且每一級指令需要下一級的N條指令解釋，若執(zhí)行第一級的一條指令需kns，那么執(zhí)行第2級、第3級、第4級的等效程序需要多少時間？第1級1條1級指令kns第2級等效程序為1/M條2級指令需N/M條1級指令解釋N/M·kns第3級等效程序為1/M/M條3級指令需NN/M/M條1級指令解釋N2/M2ns第4級等效程序為1/M/M/M條4級指令需NNN/M/M/M條1級指令解釋N3/M3ns1.6試以實例說明計算機系統(tǒng)結構、計算機組成與計算機實現(xiàn)之間的相互關系與相互影響。系統(tǒng)結構、組成和實現(xiàn)是三個不同的概念，它們各自包含不同的內容，但又有緊密的關系。以存儲系統(tǒng)為例，主存儲器容量和尋址方式的確定屬計算機系統(tǒng)結構，主存的速度應多高，在邏輯結構上采用什么措施屬計算機組成，而主存的物理實現(xiàn)，如存儲器采用什么樣器件，邏輯電路設計和微組裝技術則屬計算機實現(xiàn)。1.7什么是透明性概念？對計算機系統(tǒng)結構，下列哪些是透明的？哪些是不透明的？存貯器的模m交叉存??；透明（組成）浮點數(shù)據(jù)表示；不透明（系統(tǒng)結構）I/O系統(tǒng)是采用通道方式還是I/O處理機方式；不透明數(shù)據(jù)總線寬度；透明（組成）陣列運算部件；透明（組成）通道是采用結合型的還是獨立型的；透明（組成）PDP-11系列中的單總線結構；不透明（系統(tǒng)結構）訪問方式保護；不透明（系統(tǒng)結構）程序性中斷；不透明（系統(tǒng)結構）串行、重疊還是流水控制方式；透明（組成）堆棧指令；存貯最小編址單位；不透明（系統(tǒng)結構）Cache存貯器。透明（組成）(1)從指定角度來看，不必要了解的知識稱為透明性概念。(2)見下表，“√”為透明性概念。模m交叉，√，浮點數(shù)據(jù)，×，P4通道與I/O處理機，×，P4總線寬度，√，陣列運算部件，×，結合型與獨立型通道，√，單總線，√，訪問保護，×，中斷，×，指令控制方式，√，堆棧指令，×，最小編址單位，×，Cache存儲器，√，1.8從機器（匯編）語言程序員看，以下哪些是透明的？指令地址寄存器；指令緩沖器；時標發(fā)生器；條件碼寄存器；乘法器；主存地址寄存器；磁盤外設；先行進位鏈；移位器；通用寄存器；中斷字寄存器。見下表，“√”為透明性概念指令地址寄存器，×，指令緩沖器，√，時標發(fā)生器，√，條件碼寄存器，×，乘法器，√，主存地址寄存器，√，磁盤，×，先行進位鏈，√，移位器，√，通用寄存器，×，中斷字寄存器，×，1.9見下表，“√”表示都透明，“應”表示僅對應用程序員透明，“×”表示都不透明。數(shù)據(jù)通路寬度，√，虛擬存儲器，應，Cache存儲器，√，程序狀態(tài)字，×，“啟動I/O”指令，應，“執(zhí)行”指令，×，指令緩沖寄存器，√，1.12如果某一計算任務用向量方式求解比用標量方式求解要快20倍，稱可用向量方式求解部分所花費時間占總的時間的百分比為可向量化百分比。請畫出加速比與可向量化比例兩者關系的曲線。解：可向量化百分比為Fe,Se=20，根據(jù)Amdahl定律將Se代入Amdahl定律得1.13在題1.12中，為達到加速比2，可向量化的百分比應為多少？=2則可向量化的百分比Fe=0.5261.14在題1.12中，為獲得采用向量方式最大加速比的半值（即10）時，所需可向量化的百分比為多少。=10則可向量化的百分比Fe=0.9471.15在題1.12中，如果某程序可向量化部分為70%，硬件設計組認為可以通過加大工程投資，使向量處理速度加倍來進一步增加性能；而編譯程序編寫組認為只需設法增加向量工作方式的百分比就同樣可使性能得到相同的提高，問：此時需使可向量化成分再增加多少百分比就可實現(xiàn)。你認為上述硬、軟件兩種方法中，哪一種方法更好？(1)用硬件組方法，已知Se=2X20=40，F(xiàn)e=0.7解出Sn=40/12.7≈3.1496(2)用軟件組方法，已知Se=20，得到硬件組方法的相同性能Sn=40/12.7解出Fe=27.3/38≈0.7184(3)結論：軟件組方法更好。因為硬件組需要將Se再提高100%（20→40），而軟件組只需將Fe再提高1.84%（0.7→0.7184）。1.16某計算機的高速小容量存儲器能存儲2000條指令。假設10％的指令承擔了90%的指令訪問且對這10％的指令的使用是均勻的（即其中每條指令的執(zhí)行時間相同）。如果要執(zhí)行的某程序共有50000條指令且已知其中的10%是頻繁使用的，則當該計算機執(zhí)行該程序時，在高速小容量存儲器中能訪問到的指令會占多少百分比？

解:對該應用程序來說，在90%的時間里，只有50000*10%=5000條指令在運行，其他的45000條指令的平均運行次數(shù)很少，因此，可以假設對它們來說，Cache總是缺失的．對頻繁訪問的這10%的指令，假設它們訪問均勻，這樣，Cache的行為便可以認為是均勻覆蓋了這些指令．所以， 10％的指令承擔了90%的指令訪問,指令訪問次數(shù)(50000*10%)/90% 命中次數(shù)2000 Cache的命中率為：H=2000/[(50000*10%)/90%]=0.361.17假設高速緩存Cache工作速度為主存的5倍，且Cache被訪問命中的概率為90%，則采用Cache后，能使整個存儲系統(tǒng)獲得多高的加速比？解：1.18設計指令存儲器有兩種不同方案：一是采用價格較貴的高速存儲器芯片，另一是采用價格便宜的低速存儲芯片。采用后一方案時，用同樣的經(jīng)費可使存儲器總線帶寬加倍，從而每隔2個時鐘周期就可取出2條指令（每條指令為單字長32位）；而采用前一方案時，每個時鐘周期存儲器總線僅取出1條單字長指令。由于訪存空間局部性原理，當取出2個指令字時，通常這2個指令字都要使用，但仍有25%的時鐘周期中，取出的2個指令字中僅有1個指令字是有用的。試問采用這兩種實現(xiàn)方案所構成的存儲器帶寬為多少？解：方案一：采用高速緩沖存儲器，使每個時鐘周期存儲器總線取出1條指令，則存儲器帶寬=1字/時鐘周期=32位/時鐘周期方案二：使存儲器總線帶寬加倍，從而每隔2個時鐘周期就可取出2條指令（每條指令為單字長32位），但仍有25%的時鐘周期中，取出的2個指令字中僅有1個指令字是有用的，則1.19用一臺40MHz處理機執(zhí)行標準測試程序，它含的混合指令數(shù)和相應所需的時鐘周期數(shù)如下：指令類型指令數(shù)時鐘周期數(shù)整數(shù)運算450001數(shù)據(jù)傳送320002浮點150002控制傳送80002求有效CPI、MIPS速率和程序的執(zhí)行時間。1.20某工作站采用時鐘頻率為15MHz、處理速率為10MIPS的處理機來執(zhí)行一個已知混合程序。假定每次存儲器存取為1周期延遲、試問：(a)此計算機的有效CPI是多少？(b)假定將處理機的時鐘提高到30MHz，但存儲器子系統(tǒng)速率不變。這樣，每次存儲器存取需要兩個時鐘周期。如果30%指令每條只需要一次存儲存取，而另外5%每條需要兩次存儲存取，還假定已知混合程序的指令數(shù)不變，并與原工作站兼容，試求改進后的處理機性能。解：(a)f==15MHz,MIPS=10,每次存取時間為2個時鐘周期(b)30%指令每條只需要一次存儲存取，改進前共需1周期，改進后共需2周期而另外5%每條需要兩次存儲存取，改進前共需2周期，改進后共需4周期1.21假設在一臺40MHz處理機上運行200000條指令的目標代碼，程序主要由四種指令組成。根據(jù)程序跟蹤實驗結果，已知指令混合比和每種指令所需的指令數(shù)如下：指令類型CPI指令混合比算術和邏輯160%高速緩存命中的加載/存儲218%轉移412%高速緩存缺失的存儲器訪問810%(a)計算在單處理機上用上述跟蹤數(shù)據(jù)運行程序的平均CPI(b)根據(jù)(a)所得CPI，計算相應的MIPS速率。解：(1)(2)1.24假定你是一個計算機設計者，對高級語言結構的使用研究表明，過程調用是最常用的操作之一。你已設想了一個優(yōu)化設計方案，它能減少過程調用和返回所需的取/存指令次數(shù)。為了進行驗證，對未加優(yōu)化和已優(yōu)化的方案進行實驗測試，假定所使用的是相同的優(yōu)化編譯器。實驗測得的結果如下：(1)未優(yōu)化的時鐘周期比優(yōu)化的快5%；(2)未優(yōu)化方案中的取/存指令數(shù)占總指令數(shù)的30%；(3)優(yōu)化方案中的取/存指令數(shù)比未優(yōu)化的少1/3，對于其他指令，兩種方案的動態(tài)執(zhí)行數(shù)沒有變化；(4)所有指令，包括取/存指令，均只需要1個時鐘周期。要求你定量地判斷，哪一種設計方案的計算機工作速度更快。解：記新方案時鐘周期為Tc，已知CPI=CPIi=1原時間=CPI×IC×0.95Tc=0.95IC×Tc新時間=（0.3×2/3+0.7）×IC×Tc=0.9IC×Tc二者比較，新時間較短。1.A1某臺計算機只有Load/Store指令能對存儲器進行讀/寫操作，其它指令只對寄存器進行操作。根據(jù)程序跟蹤實驗結果，已知每種指令所占的比例及CPI數(shù)如下：指令類型指令所占比例CPI算邏指令43％1Load指令21％2Store指令12％2轉移指令24％2(1)求上述情況下的平均CPI。(2)假設程序有M條指令組成。算邏運算中25%的指令的兩個操作數(shù)中的一個已在寄存器中，另一個必須在算邏指令執(zhí)行前用Load指令從存儲器取到寄存器。因此有人建議增加另一種算邏指令，其特點是一個操作數(shù)取自寄存器，另一個操作數(shù)取自存儲器，即寄存器?存儲器類型，假設這種指令的CPI等于2。同時，轉移指令的CPI變?yōu)?。求新指令系統(tǒng)的平均CPI。解：(1)CPI舊＝(0.43×1＋0.21×2＋0.12×2+0.24×2)=1.57(2)原算邏指令中的25％變成了寄存器?存儲器型指令，所以算邏指令(寄存器?寄存器型)少了(0.25×0.43)M條，Load指令少了(0.25×0.43)M條，而(0.25×0.43)M條的新指令為寄存器?存儲器型指令。指令總數(shù)少了(0.25×43%)M條。設執(zhí)行算邏指令(寄存器?寄存器型)、Load指令、算邏指令(寄存器?存儲器型)、Store指令和轉移指令的周期總數(shù)分別為C1，C2，C3，C4，C5，所以:C1=(0.43-(0.25×0.43))M×1=0.3225MC2=(0.21-(0.25×0.43))M×2=0.205MC3=(0.25×0.43)M×2=0.215MC4=0.12M×2=0.24MC5=0.24×3M=0.72M新指令總數(shù)N=（1-(0.25×0.43)）M=0.892CPI新=（C1+C2+C3+C4+C5）/N=1.7025M/0.8925M=1.9081.A2計算機系統(tǒng)中有三個部件可以改進，這三個部件的部件加速比如下：部件加速比1=30部件加速比2=20部件加速比3=10（1）如果部件1和部件2的可改進比例均為30%，那么當部件3的可改進比例為多少時，系統(tǒng)加速比才可以達到10？（2）如果三個部件的可改進比例分別為30%、30%和20%，三個部件同時改進，那么系統(tǒng)中不可加速部分的執(zhí)行時間在總執(zhí)行時間中占的比例是多少？（3）如果相對某個測試程序三個部件的可改進比例分別為20%，20%和70%，要達到最好改進效果，僅對一個部件改進時，要選擇哪個部件？如果允許改進兩個部件，又如何選擇？1.A3在某個程序中，簡單指令占80%，復雜指令占20%，在CISC機中簡單指令執(zhí)行需4個機器周期，復雜指令執(zhí)行需8個機器周期。RISC機中簡單指令執(zhí)行只需1個機器周期，而復雜指令要通過一串指令來實現(xiàn)。假定復雜指令平均需要14條簡單指令，即需要14個周期，若該程序中需要執(zhí)行的總指令數(shù)為1000000，Tc為100ns，那么（1）RISC機需執(zhí)行的指令數(shù)為多少？（2）CISC和RISC機的CPU時間分別為多少？（3）RISC機對CISC的加速比為多少？第二章(P124)2.3忽略P124倒1行～P125第8行文字，以簡化題意）已知2種浮點數(shù)，求性能指標。此題關鍵是分析階碼、尾數(shù)各自的最大值、最小值。原圖為數(shù)據(jù)在內存中的格式，階碼的小數(shù)點在其右端，尾數(shù)的小數(shù)點在其左端，遵守規(guī)格化要求。由于尾數(shù)均為原碼，原碼的絕對值與符號位無關，所以最大正數(shù)與最小負數(shù)的絕對值相同，可用“±最大絕對值”回答；最小正數(shù)與最大負數(shù)的絕對值相同，可用“±最小絕對值”回答。第1小問中，階碼全部位數(shù)為8，作無符號數(shù)看待真值為0～255，作移-127碼看待真值為-127～+128；尾數(shù)（不計符號位）有23位小數(shù)，另加1位整數(shù)隱藏位，所以尾數(shù)絕對值為1.0～2.0–2-23，有效位數(shù)p=24；第2小問中，階碼全部位數(shù)為11，作無符號數(shù)看待真值為0～2047，作移-1023碼看待真值為-1023～+1024；尾數(shù)（不計符號位）有52位小數(shù)，另加1位整數(shù)隱藏位，所以尾數(shù)絕對值為1.0～2.0–2-52，有效位數(shù)p=53。最大絕對值為最大階碼與最大尾數(shù)絕對值的組合，最小絕對值為最小階碼與最小尾數(shù)絕對值的組合。代入相關公式后得最終結果如下表。32位64位±最大絕對值±(1-2-24)·2129±(1-2-53)·21025±最小絕對值±2-127±2-1023表數(shù)精度δ2-242-53表數(shù)效率η100%100%2.5(1)rm=2，re=2，p=24（隱藏最高位）,q=7。(2)Nmax=1.7×1038，-|N|min=-1.47×10-39 δ≤5.96×10-8≈10-7.22，η=100%2.61位7位6位00111111333333(1)0.2=0.333333H×160 設階碼為移-63碼（即-26+1，原題未指明） 0.2=0.110011001100110011001101B×2-21位8位23位00111110110011001100110011001101 （其中最高有效位需隱藏） 階碼為移-127碼（即-27+1）(2)符號位不變，（階碼–63）×4+127；尾數(shù)左規(guī)，除去最高位；(3)符號位不變，（階碼–127）/4+63；尾數(shù)補最高位，按除法余數(shù)右移若干位，左補0。2.13已知10條指令使用頻度，求3種編碼方法的平均碼長與信息冗余量。(1)此問中的“最優(yōu)Huffman編碼法”實際是指碼長下限，即信源的平均信息量──熵，代公式得H=2.9566。(2)Huffman編碼性能如下表；(3)2/8擴展編碼是8/64/512法的變種，第一組2條指令，碼長為2（1位擴展標志，1位編碼）,第二組8條指令，碼長為4（1位擴展標志，與第一組區(qū)別，加3位編碼），編碼性能如下表；(4)3/7擴展編碼是15/15/15法的變種，第一組3條指令，碼長為2（共有4種組合，其中3種組合分別代表3條指令，留1種組合作為擴展前綴標志）,第二組7條指令，碼長為5（2位固定的前綴擴展標志，與第一組區(qū)別，加3位編碼，只用其中7種組合），編碼性能如下表。Huffman編碼2/8擴展編碼3/7擴展編碼平均碼長L2.993.13.2信息冗余量R1.10%4.61%7.59%2.14一臺模型機共有7條指令，各指令的使用頻率分別為35%，25%，20%，10%，5%，3%和2%，有8個通用數(shù)據(jù)寄存器，2個變址寄存器。(1)要求操作碼的平均長度最短，請設計操作碼的編碼，并計算所設計操作碼的平均長度。(2)設計8字長的寄存器-寄存器型指令3條，16位字長的寄存器-存儲器型變址尋址方式指令4條，變址范圍不小于±127。請設計指令格式，并給出各字段的長度和操作碼的編碼。解：(1)要使得到的操作碼長度最短，應采用Huffman編碼，構造Huffman樹如下：由此可以得到7條指令的編碼分別如下：這樣，采用Huffman編碼法得到的操作碼的平均長度為：H=2×(0.35+0.25+0.20)+3×0.10+4×0.05+5×(0.03+0.02)=1.6+0.3+0.2+0.25=2.35(2)設計8位字長的寄存器-寄存器型變址尋址方式指令如下，因為只有8個通用寄存器，所以寄存器地址需3位，操作碼只有兩位，設計格式如下：三條指令的操作碼分別為00，01，10設計16位字長的寄存器-存儲器型變址尋址方式指令如下：四條指令的操作碼分別為1100，1101，1110，11112.15某處理機的指令字長為16位，有雙地址指令、單地址指令和零地址指令三類，并假設每個地址字段的長度均為6位。(1)如果雙地址指令有15條，單地址指令和零地址指令的條數(shù)基本相同，問單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。(2)如果要求三類指令的比例大致為1：9：9，問雙地址指令、單地址指令和零地址指令各有多少條？并且為這三類指令分配操作碼。解：(1)15條/63條/64條(2)14條/126條/128條(1)根據(jù)指令地址的數(shù)量來決定各種指令在指令空間上的分布：如果我們按照從小到大的順序分配操作碼，這樣，按照指令數(shù)值從小到大的順序，分別為雙地址指令、單地址指令和零地址指令。其次可以根據(jù)指令的條數(shù)來大致的估計操作碼的長度：雙指令15條，需要4位操作碼來區(qū)分，剩下的12位操作碼平均分給單地址和零地址指令，每種指令可以用6位操作碼來區(qū)分，這樣，各指令的條數(shù)為：雙地址指令15條，操作碼：0000~1110；單地址指令2^6-1=63條，操作碼：1111000000~1111111110；零地址指令64條，操作碼：1111111111000000~1111111111111111。(2)與上面的分析相同，可以得出答案：雙地址指令14條，操作碼：0000~1101；單地址指令2^6x2-2=126條，1110000000~1110111110，1111000000~1111111110；零地址指令128條1110111111000000~1110111111111111,1111111111000000~1111111111111111(2)B雙地址指令同上,14條，操作碼：0000~1101；單地址指令64+62=126條，64條單地址指令操作碼1110000000~1110111111，62條單地址指令操作碼1111000000~1111111101；零地址指令128條1111111110000000~1110111110111111,1111111111000000~1111111111111111第三章(P202)3.3直接代公式計算存儲層次性能指標。(1)74ns，38ns，23.6ns(2)0.258，0.315，0.424(3)T256K<T128K<T64Kc256K>c128K>c64K(4)19.092，11.97，10.0064。答案是256K方案最優(yōu)。3.5已知，其中g=0.1依題意有整理得0.9n≥0.2，解出，向下取整，得15；按另一種題意理解是向上取整，得16，也對。3.7方式1：16個模塊高位交叉方式2：16個模塊并行訪問方式3：16個模塊低位交叉方式4：2路高位交叉8路低位交叉16個存儲模塊每8個組成一個大的模塊：方式5：4路高位交叉4路低位交叉16個存儲模塊每4個組成一個大的模塊：方式6：4路并行訪問4路低位交叉（1）這幾種存儲器都能夠并行工作，因此可以提高頻帶寬度?？偟膩碚f，并行訪問存儲器的優(yōu)點是實現(xiàn)簡單、容易，缺點是訪問沖突大；高位交叉訪問存儲器的優(yōu)點是擴充方便，缺點是訪問效率不高；低位交叉訪問存儲器可以用分時的方法來提高速度，但擴充不方便。

（2）各種存儲器的頻帶寬度和他們的工作頻率有關，在不考慮沖突的情況下，如果有足夠多的獨立控制電路和寄存器，那么，他們的頻帶寬度是相同的。（3）存儲器的邏輯示意圖略。注意，并行訪問存儲器和低位交叉訪問存儲器很相象，只不過，并行訪問存儲器使用存儲模塊號（存儲體號）來對已經(jīng)輸出的結果進行選擇，而低位交叉訪問存儲器則用來生成對存儲模塊（存儲體）的片選信號，他通過流水的方式來提高訪問的速度。3.14在頁式虛擬存儲器中，一個程序由P1~P5共5個虛頁組成。在程序執(zhí)行過程中依次訪問到的頁面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2假設系統(tǒng)分配給這個程序的主存有3個頁面，分別采用FIFO、LRU和OPT三種替換算法對這三頁主存進行調度。（1） 畫出主存頁面調入、替換和命中的情況表。（2） 統(tǒng)計三種頁面替換算法的頁命中率。3.15（1）在分配的主存頁面數(shù)目大于等于5的情況下，這時，除了第一次調入不命中，以后的訪問均命中，可以達到最高的頁面命中率：實際命中的次數(shù)為7次，所以可能達到的最高頁面命中率為：（2）由于在頁面數(shù)大于等于5的情況下，肯定可以達到最高命中率，所以我們來看頁面數(shù)小于5時能否達到該命中率：分配的主存頁面數(shù)等于4時，調度過程如下：LFU算法LFU算法44444*11111*11命中7次

555*55555*555

3333*33*333*3

2222*22222調入調入調入調入命中調入命中命中命中命中命中命中此時也可以達到最高命中率；分配的主存頁面等于3時，調度過程如下：LFU算法LFU算法444*222*33*333*3命中3次

555*555*222*11

333*1111*555調入調入調入調入命中調入調入調入命中調入調入命中此時不能達到最高命中率。所以至少應該分配4個主存頁面。（3)我們假設程序每次只訪問一個存儲單元，這樣，對每一個特定頁面的訪問過程可以描述如下：因為第一次總是不命中的，而平均起來，隨后的1023次總是命中的，然后再次被調出主存，并再次重復先前的過程。所以訪問存儲單元的命中率為：欲知可能的最高命中率及所需的最少主存頁數(shù)，較好的辦法是通過“堆棧模擬法”，求得命中次數(shù)隨主存頁數(shù)變化的函數(shù)關系。下圖就是“堆棧模擬圖”，其中“√”表示命中。P=453251323513命中次數(shù)4532513235134532513235145325112354432551224444444n=10n=2√1n=3√√√3n=4√√√√√√√7n=5√√√√√√√7(1)Hmax=7/12≈58.3%(2)n=4(3)當1次頁面訪問代表連續(xù)1024次該頁內存儲單元訪問時，后1023次單元訪問肯定是命中的，而第1次單元訪問的命中情況與這1次頁面訪問的命中情況相同。根據(jù)上圖中最高命中情況，共有7次頁命中（折算為7×1024次單元命中），5次頁不命中（折算為5×1023次單元命中，也可寫為5×1024-5），單元訪問總次數(shù)為12×1024，故有：Hcell=(12×1024-5)/(12×1024)=12283/12288≈99.96%3.15A加1題一個二級存儲層次，采用全相聯(lián)映象和最久沒有使用算法，實存共5頁，為2道程序分享，頁地址流分別如下P1=12341321P2=12342233試作2個實存分配方案，分別使2道程序滿足(1)命中率相同；(2)命中次數(shù)之和最大。P1=12341321命中次數(shù)N(1)12341321123413212341312244n1=10n1=20n1=3√√2n1=4√√√√4解：分別為2道程序作“堆棧模擬圖”，其中“√”表示命中。P2=12342233命中次數(shù)N(2)12342233123442212334411111n2=1√√2n2=2√√2n2=3√√√√4n2=4√√√√465N(1)+N(2)432N(1)N(2)11+42+33+24+1將兩圖結果綜合，得到4個分配方案的命中率情況表如下n11234N(1)0024n24321N(2)4422N(1)+N(2)4446結論如下(1)命中率相同的方案是n1=3而n2=2；(2)命中次數(shù)之和最大的方案是n1=4而n2=1。3.19

（1）主存共有2個區(qū)，每個區(qū)2組，每個組2塊，每塊16個字節(jié)，如果按字節(jié)尋址，那么主存需要7位，如下圖所示：（2）Cache地址需要6位，如下圖所示：中(3)(4)(6)(8)問 虛存 實頁 0 1 2 3虛組0 0 0 √ √ 1 實存 1 √ √ 虛組1 2 · 0 實組0 2 √ √ 3 · 1 虛 3 √ √虛組2 4 · 2 實組1 頁 4 √ √ 5 · 3 5 √ √ 虛組3 6 6 √ √ 7 7 √ √ (a)虛頁集合與實頁集合的對應關系 (b)對應關系表（√為有關系）(3)(4)通過作“實存狀況圖”模擬各虛塊的調度情況，可獲得Cache的塊地址流序列。P=624146304573C044*4444*44*4*4*C111*1*1*00*555C266*6*6*6*66*6*6*6*77*C322222*33333*3入入入入中中替替中替替中C=230102310123此問最容易出錯的地方是忽略“組相聯(lián)”地址約束，將虛頁裝錯實組。另外沒有及時標注“*”號也容易導致淘汰對象錯誤。(6)H=4/12≈33%(8)做法同3.15題(3)問，Hcell=(12×16-8)/(12×16)≈95.8%第四章(P250)4.5已知中斷服務次序為3-2-4-1，。(1)中斷屏蔽字表如下圖；D1D2D3D4D10111D20010D30000D40110(2)中斷過程示意圖如右圖。時間中斷請求 主程序 1級2級3級4級D1，D2D3，D44.8(1)f=2×105字節(jié)/秒，T=5us(2)Ts+Td=5us，通道時間圖如下。作圖時注意：至少要畫到最慢設備的第二次請求出現(xiàn)，才能確定是否丟失數(shù)據(jù)（因為響應優(yōu)先級低的設備較易丟失數(shù)據(jù)）。(3)5，160，20，40；(4)D2丟失第一次請求的數(shù)據(jù)；(5)參見P245。第五章(P343)5.3假設一條指令的執(zhí)行過程分為“取指令”、“分析”和“執(zhí)行”三段，每一段的執(zhí)行時間分別為Δt、2Δt和3Δt。在下列各種情況下，分別寫出連續(xù)執(zhí)行n條指令所需要的時間表達式。（1）順序執(zhí)行方式。（2）僅“取指令”和“執(zhí)行”重疊。（3）先行控制方式。[解答]順序方式：執(zhí)行n條指令的時間=n×(t取指+t分析+t執(zhí)行)“執(zhí)行”和“取指”重疊：執(zhí)行n條指令的時間=t取指+n×t分析+(n-1)×MAX{t取指,t執(zhí)行}+t執(zhí)行“執(zhí)行”、“分析”和“取指”重疊：執(zhí)行n條指令的時間=t取指+MAX{t取指,t分析}+(n-2)×MAX{t取指,t分析,t執(zhí)行}+MAX{t分析,t執(zhí)行}+t執(zhí)行先行控制：執(zhí)行n條指令的時間=t取指+t分析+n×t執(zhí)行（1）順序執(zhí)行需要的時間如下：（2）取指令和執(zhí)行重疊，即一次重疊執(zhí)行方式，我們假設第n+1條指令的取指令和第n條指令的執(zhí)行同時結束，那么所需要的時間為：（3）采用先行控制以后：5.6在一臺單流水線多操作部件上執(zhí)行下面的程序，取指令、指令譯碼各需要一個時鐘周期，MOVE、ADD和MUL操作各需要2個、3個、和4個時鐘周期。每個操作都在第一個時鐘周期從通用寄存器中讀操作數(shù)，在最后一個時鐘周期把運算結果寫到通用寄存器中。k：MOVER1，R0；R1←（R0）k+1：MULR0，R2，R1；R0←(R2)×(R1)k+2：ADDR0，R2，R3；R0←(R2)+(R3)就程序本身而言，可能有哪幾種數(shù)據(jù)相關？在程序實際執(zhí)行過程中，有哪幾種數(shù)據(jù)相關會引起流水線停頓？畫出指令執(zhí)行過程的流水線時空圖，并計算執(zhí)行完這三條指令共使用了多少各時鐘周期？答：（1）K與K+1：先寫后讀相關K+1與K+2：寫寫相關由流水線時空圖看，K與K+1：先寫后讀相關在第4時鐘周期會引起流水線停頓，而K+1與K+2：寫寫相關在第8時鐘周期會引起流水線停頓。K+2K+2K+1KIFIDRREXEXWB*IFIDRR*EXEXEXWBIFIDRREXWB123456789（3）由流水線時空圖看，共插入了3個時鐘周期的停頓，執(zhí)行完這三條指令共使用了11個時鐘周期。K+2K+2K+1KIFIDidleidleRREXEXidleWBIFIDidleidleRREXEXEXWBIFIDRREXWB12345678910115.7一條線性流水線有4個功能段組成，每個功能段的延遲時間都相等，都為Δt。開始5個Δt，每間隔一個Δt向流水線輸入一個任務，然后停頓2個Δt，如此重復。求流水線的實際吞吐率、加速比和效率。[解答]流水線的時空圖如下：我們可以看出，在（11n+1）Δt的時間內，可以輸出5n個結果，如果指令的序列足夠長（n→∞），并且指令間不存在相關，那么，吞吐率可以認為滿足：加速比為：從上面的時空圖很容易看出，效率為：5.8用一條5個功能段的浮點加法器流水線計算每個功能段的延遲時間均相等，流水線的輸出端和輸入端之間有直接數(shù)據(jù)通路，而且設置有足夠的緩沖寄存器。要求用盡可能短的時間完成計算，畫出流水線時空圖，并計算流水線的實際吞吐率、加速比和效率。[解答]首先需要考慮的是，10個數(shù)的的和最少需要做幾次加法。我們可以發(fā)現(xiàn)，加法的次數(shù)是不能減少的：9次；于是我們要盡可能快的完成任務，就只有考慮如何讓流水線盡可能充滿，這需要消除前后指令之間的相關。由于加法滿足交換率和結合率，我們可以調整運算次序如以下的指令序列，我們把中間結果寄存器稱為R，源操作數(shù)寄存器稱為A，最后結果寄存器稱為F，并假設源操作數(shù)已經(jīng)在寄存器中，則指令如下：I1： R1←A1+A2I2： R2←A3+A4I3： R3←A5+A6I4： R4←A7+A8I5： R5←A9+A10I6： R6←R1+R2I7： R7←R3+R4I8： R8←R5+R6I9： F←R7+R8這并不是唯一可能的計算方法。假設功能段的延遲為Δt。時空圖如下，圖中的數(shù)字是指令號。整個計算過程需要21Δt，所以吞吐率為：加速比為：效率為：5.9一條線性靜態(tài)多功能流水線由6個功能段組成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每個功能段的延遲時間均相等。流水線的輸入端與輸出端之間有直接數(shù)據(jù)通路，而且設置有足夠的緩沖寄存器?，F(xiàn)在用這條流水線計算：畫出流水線時空圖，并計算流水線的實際吞吐率、加速比和效率。為了取得較高的速度，我們需要一次將乘法作完，設源操作數(shù)存放在寄存器A、B中，中間結果存放在寄存器R中，最后結果存放在寄存器F中，則執(zhí)行的指令序列如下所示：I1： R1←A1*B1I2： R2←A2*B2I3： R3←A3*B3I4： R4←A4*B4I5： R5←A5*B5I6： R6←A6*B6I7： R7←R1+R2I8： R8←R3+R4I9： R9←R5+R6I10： R10←R7+R8I11： F←R9+R10這并不是唯一可能的計算方法。假設功能段的延遲為Δt。時空圖（不完全）如下，圖中的數(shù)字是指令號。整個計算過程需要22Δt，所以吞吐率為：加速比為：效率為：為了縮短運算時間，首先應考慮“最少切換算法”，即先執(zhí)行完所有乘法（任務編號1-6）再執(zhí)行加法（任務編號7-11），其次在加法中采用“最少相關算法”（即二叉樹算法）。記c1=A1×B1，……，c6=A6×B6，下圖(a)是加法的計算順序二叉樹，注意任務10應該用前一級最早完成的任務7和8的結果，如果用任務9的結果則要推遲1拍啟動，使總時間增加1拍。F=c1+c2+c3+c4+c5+c6 61234567891011 5123456789 4123456 37891011 10 27891011 11234567891011 11 01234567891214151822 (a) (b)根據(jù)時空圖(b)得 TP=11/(22Δt)=1/(2Δt) S=(6×4Δt+5×4Δt)/(22Δt)=2 E=(6×4Δt+5×4Δt)/(6×22Δt)=1/35.10一條有3個功能段的流水線如圖，每個功能段的延遲時間都相等，為△t。功能段S2的輸出返回到它自己的輸入端循環(huán)一次。如果每隔一個△t向流水線輸入端連續(xù)輸入新任務，問這條流水線會發(fā)生什么情況？求這條流水線能夠正常工作的最大吞吐率。加速比和效率？有什么辦法能夠提高這條流水線的吞吐率？畫出新的流水線。SS1S2S3輸入輸出△t△t△t5.11一條4個功能段的非線性流水線，每個功能段的延遲時間都相等，都為20ns，它的預約表如下：

(1)寫出流水線的禁止向量F和初始沖突向量C。

(2)畫出調度流水線的狀態(tài)圖。

(3)求流水線的最小啟動循環(huán)和最小平均啟動距離。

(4)求平均啟動距離最小的恒定循環(huán)。

(5)求流水線的最大吞吐率。

照最小啟動循環(huán)連續(xù)輸入10個任務，求流水線的實際吞吐率。畫出該流水線各功能段之間的連接圖。答：解：

(1)

禁止向量F=(2，4，6)

初始沖突向量C=(101010）

(2)狀態(tài)圖

(3)

簡單循環(huán)平均啟動距離

(1，7) 4

(3，7) 5

(3，5，7) 5

(5，7) 6

(5) 5

(7) 7

最小平均啟動距離4

最小啟動循環(huán)(1，7)

(4)平均啟動距離最小的恒循環(huán)(5)

(5)流水線的最大吞吐率

假設用此流水線完成N個任務(N為偶數(shù)):

TPMAX=N/(N/2*12*△T)=1/(6△T)

其中：N/2*12表示每執(zhí)行2個任務需要12個△T時間，平均每6個△T完成一個任務。

假設用此流水線完成N個任務(N為奇數(shù)):

TPMAX=N/[((N-1)/2*12+5)*△T]

其中：(N-1)/2*12表示每執(zhí)行2個任務需要12個△T時間，5為最后一個任務多執(zhí)行的周期數(shù)。（1）禁止向量：（2，4，6），初始沖突向量：（101010）。（2）狀態(tài)圖1010101111111010101111111011117*151010117*3537*7*（3）簡單循環(huán)平均啟動距離45565（7）7最小平均啟動距離4最小啟動循環(huán)（1，7）（4）平均啟動距離最小的恒循環(huán)（5）（5）流水線的最大吞吐率假設用此流水線完成N個任務（N為偶數(shù)）：TPMAX=N/（N/2*12*△T）=1/（6△T）其中：N/2*12表示每執(zhí)行2個任務需要12個△T時間，平均每6個△T完成一個任務。假設用此流水線完成N個任務（N為奇數(shù)）：TPMAX=N/[（（N-1）/2*12+5）*△T]其中：（N-1）/2*12表示每執(zhí)行2個任務需要12個△T時間，5為最后一個任務多執(zhí)行的周期數(shù)。時間功能段1234567891011121314151617S1╳△╳3△3S2╳╳△△33S3╳△3S4╳╳△△335.12一條3個功能段的非線性流水線及其預約表如圖：(1)寫出流水線的禁止向量和初始沖突向量，并畫出調度流水線的狀態(tài)轉換圖。

(2)求流水線的最小啟動循環(huán)和最小平均啟動距離。

(3)通過插入非計算延遲功能段使該流水線達到最優(yōu)調度，確定該流水線的最佳啟動循環(huán)及其最小平均啟動距離。

(4)畫出插入非計算延遲功能段后的流水線連接圖及其預約表。

(5)畫出插入非計算延遲功能段后的流水線狀態(tài)轉換圖。

(6)在插入非計算延遲功能段前后，分別計算流水線的最大吞吐率，并計算最大吞吐率改進的百分比。

5.15Δt=10ns=10-8秒(1)F={1，2，5}，C=(10011)(2)狀態(tài)轉移圖如下圖(a)所示。(3)最小啟動循環(huán)=（3）,最小平均啟動距離=3Δt。(4)插入2個延遲，最小啟動循環(huán)=（2）,最小平均啟動距離=2Δt。(5)新預約表如下圖(b)所示。 12345678 初態(tài)4，6，≥8 S1×12×初態(tài) 3，4，≥6 S2 ×1× 1000101 S3× 4，6，≥8 4，6，≥810011 S41×× 2 5 D1× 1010101 1000111 D2× 2 5 (a) (b) (c)(6)F={1，3，7}，C=(1000101)，狀態(tài)轉移圖如下圖(c)所示。(7)插入前TPmax=1/3Δt=1/30ns，插入后TPmax=1/2Δt=1/20ns。(8)插入前TP=10/33Δt=1/33ns，插入后TP=10/26Δt=1/26ns，如下圖所示。 S411223 1010 S3123 ……… 10 S21122310 10 S11213210 10 3 t(a)插入前 9×3 6 D2 123 11 D1 1234 10 S4112233 ……… 1010 S31234 10 S212132435 1010 S11234152 10 10 2 t(b)插入后 9×2 85.18在下列不同結構的處理機上運行8×8的矩陣乘法C=A×B，計算所需要的最短時間。只計算乘法指令和加法指令的執(zhí)行時間，不計算取操作數(shù)、數(shù)據(jù)傳送和程序控制等指令的執(zhí)行時間。加法部件和乘法部件的延遲時間都是3個時鐘周期，另外，加法指令和乘法指令還要經(jīng)過一個“取指令”和“指令譯碼”的時鐘周期，每個時鐘周期為20ns，C的初始值為“0”。各操作部件的輸出端有直接數(shù)據(jù)通路連接到有關操作部件的輸入端，在操作部件的輸出端設置有足夠容量的緩沖寄存器。（a）處理機內只有一個通用操作部件，采用順序方式執(zhí)行指令。（b）單流水線標量處理機，有一條兩個功能的靜態(tài)流水線，流水線每個功能段的延遲時間均為一個時鐘周期，加法操作和乘法操作各經(jīng)過3個功能段。（c）多操作部件處理機，處理機內有獨立的乘法部件和加法部件，兩個操作部件可以并行工作。只有一個指令流水線，操作部件不采用流水線結構。（d）單流水線標量處理機，處理機內有兩條獨立的操作流水線，流水線每個功能段的延遲時間均為一個時鐘周期。（e）超標量處理機，每個時鐘周期同時發(fā)射一條乘法指令和一條加法指令，處理機內有兩條獨立的操作流水線，流水線的每個功能段的延遲時間均為一個時鐘周期。（f）超流水線處理機，把一個時鐘周期分為兩個流水級，加法部件和乘法部件的延遲時間都為6個流水級，每個時鐘周期能夠分時發(fā)射兩條指令，即每個流水級能夠發(fā)射一條指令。（g）超標量超流水線處理機，把一個時鐘周期分為兩個流水級，加法部件和乘法部件延遲時間都為6個流水級，每個流水級能夠同時發(fā)射一條乘法指令和一條加法指令。要完成上面的矩陣乘法，我們可以計算需要完成的各種操作的數(shù)量（假定A和B都是8×8的矩陣。C語言代碼如下：intk;for(inti=0;i<8;i++) for(intj=0;j<8;j++) { sum=0; for(k=0;k<8;k++) { sum+=A[i][k]×B[k][j] } C[i][j]=sum; }需要完成的乘法數(shù)目為8×8×8=512次；需要完成的加法數(shù)目為8×8×7=448次；下面我們分析處理機的結構會給性能帶來什么樣的影響。（1）順序執(zhí)行時，每個乘法和加法指令都需要5個時鐘周期（取指令、指令分析、指令執(zhí)行）；所以所需要的時間為：（2）單流水線標量處理機，采用兩功能靜態(tài)流水線時；因為有足夠的緩沖寄存器，所以我們可以首先把所有的乘法計算完，并通過調度使加法流水線不出現(xiàn)停頓，所以所需要的時間為：（3）多操作部件處理機，只有一條指令流水線。由于只有一條指令流水線，所以只能一個時鐘周期發(fā)射一條指令，我們可以