計算機(jī)系統(tǒng)結(jié)構(gòu)(習(xí)題補(bǔ)充例題與練習(xí))

1、1v存在的問題存在的問題大多數(shù)同學(xué)較認(rèn)真，少數(shù)不太認(rèn)真、有抄襲現(xiàn)象大多數(shù)同學(xué)較認(rèn)真，少數(shù)不太認(rèn)真、有抄襲現(xiàn)象關(guān)于參考答案，要知其然，更要知其所以然關(guān)于參考答案，要知其然，更要知其所以然v第第5、7兩題兩題理解透明性的含義理解透明性的含義掌握計算機(jī)系統(tǒng)結(jié)構(gòu)、組成、實(shí)現(xiàn)研究的范圍，掌握計算機(jī)系統(tǒng)結(jié)構(gòu)、組成、實(shí)現(xiàn)研究的范圍，P4、5凡編寫機(jī)器語言和匯編語言程序要用到的（數(shù)據(jù)表示、指令凡編寫機(jī)器語言和匯編語言程序要用到的（數(shù)據(jù)表示、指令系統(tǒng)、寄存器系統(tǒng)、寄存器）對計算機(jī)系統(tǒng)結(jié)構(gòu)都是不透明的）對計算機(jī)系統(tǒng)結(jié)構(gòu)都是不透明的凡是只影響系統(tǒng)速度和價格的邏輯實(shí)現(xiàn)（計算機(jī)組成）和物凡是只影響系統(tǒng)速度和價格的邏輯實(shí)

2、現(xiàn)（計算機(jī)組成）和物理實(shí)現(xiàn)（計算機(jī)實(shí)現(xiàn)）對系統(tǒng)結(jié)構(gòu)都是透明的理實(shí)現(xiàn)（計算機(jī)實(shí)現(xiàn)）對系統(tǒng)結(jié)構(gòu)都是透明的2v第第5題：哪些對計算機(jī)系統(tǒng)結(jié)構(gòu)是透明的題：哪些對計算機(jī)系統(tǒng)結(jié)構(gòu)是透明的 存儲器的模存儲器的模m交叉存取：目的加快存儲器速度，交叉存?。耗康募涌齑鎯ζ魉俣?，透明透明 浮點(diǎn)數(shù)據(jù)表示：硬件可直接識別的數(shù)據(jù)類型，不透明浮點(diǎn)數(shù)據(jù)表示：硬件可直接識別的數(shù)據(jù)類型，不透明 I/O是通道方式還是處理機(jī)方式：是通道方式還是處理機(jī)方式：I/O方式選擇屬于系統(tǒng)結(jié)構(gòu)，不透明方式選擇屬于系統(tǒng)結(jié)構(gòu)，不透明 陣列運(yùn)算部件（多個相同運(yùn)算部件陣列排列）：加快運(yùn)算速度，陣列運(yùn)算部件（多個相同運(yùn)算部件陣列排列）：加快運(yùn)算速度，透明

3、透明 數(shù)據(jù)總線寬度：只影響數(shù)據(jù)傳輸速度，不影響功能，數(shù)據(jù)總線寬度：只影響數(shù)據(jù)傳輸速度，不影響功能，透明透明 通道類型（結(jié)合、獨(dú)立，通道類型（結(jié)合、獨(dú)立，P6）：功能相同、速度不同，）：功能相同、速度不同，透明透明 訪問方式保護(hù)：屬于系統(tǒng)結(jié)構(gòu)，不透明訪問方式保護(hù)：屬于系統(tǒng)結(jié)構(gòu)，不透明 程序性中斷：屬于系統(tǒng)結(jié)構(gòu)，不透明程序性中斷：屬于系統(tǒng)結(jié)構(gòu)，不透明 控制方式（串行、流水等）：僅影響速度，控制方式（串行、流水等）：僅影響速度，透明透明 堆棧指令：指令系統(tǒng)屬于系統(tǒng)結(jié)構(gòu)，不透明堆棧指令：指令系統(tǒng)屬于系統(tǒng)結(jié)構(gòu)，不透明 存儲器最小編址單位：屬于系統(tǒng)結(jié)構(gòu)，不透明存儲器最小編址單位：屬于系統(tǒng)結(jié)構(gòu)，不透明 Ca

4、che存儲器：為了提高存儲系統(tǒng)速度，組原課中細(xì)講的，存儲器：為了提高存儲系統(tǒng)速度，組原課中細(xì)講的，透明透明3v第第7題：從機(jī)器（匯編）語言看哪些是透明的題：從機(jī)器（匯編）語言看哪些是透明的指令地址寄存器：指的是程序計數(shù)器指令地址寄存器：指的是程序計數(shù)器PC，80X86中為中為IP，相對轉(zhuǎn)移指，相對轉(zhuǎn)移指令中用到，不透明令中用到，不透明指令緩沖器：緩沖和排隊技術(shù)屬于計算機(jī)組成指令緩沖器：緩沖和排隊技術(shù)屬于計算機(jī)組成P5，透明透明時標(biāo)發(fā)生器：產(chǎn)生系統(tǒng)時鐘，匯編語言不能控制的具體硬件，時標(biāo)發(fā)生器：產(chǎn)生系統(tǒng)時鐘，匯編語言不能控制的具體硬件，透明透明條件碼寄存器：存放轉(zhuǎn)移條件，也叫程序狀態(tài)字條件碼寄存器

5、：存放轉(zhuǎn)移條件，也叫程序狀態(tài)字PSW，是條件轉(zhuǎn)移指，是條件轉(zhuǎn)移指令的測試條件，不透明令的測試條件，不透明乘法器、移位器：匯編語言不能控制的具體硬件，乘法器、移位器：匯編語言不能控制的具體硬件，透明透明主存地址寄存器：也稱存儲器地址寄存器主存地址寄存器：也稱存儲器地址寄存器MAR，透明透明磁盤外設(shè)：磁盤外設(shè)：I/O指令可直接對其操作（通過端口號），不透明指令可直接對其操作（通過端口號），不透明先行進(jìn)位鏈：提高加法器運(yùn)算速度的，組原和數(shù)字邏輯中學(xué)到，匯編先行進(jìn)位鏈：提高加法器運(yùn)算速度的，組原和數(shù)字邏輯中學(xué)到，匯編語言不能控制的具體硬件，語言不能控制的具體硬件，透明透明通用寄存器、中斷字寄存器（中斷

6、響應(yīng)、優(yōu)先級、屏蔽等）：程序中通用寄存器、中斷字寄存器（中斷響應(yīng)、優(yōu)先級、屏蔽等）：程序中要用到，不透明要用到，不透明4v第第8題題掌握三個公式掌握三個公式11()iniiniiiNNCPIICPICPIIII661010NcEIfMIPSTCPIv第第12題題優(yōu)化之后各類指令所占比例，優(yōu)化之后各類指令所占比例，ALU指令的減少也導(dǎo)致總指令數(shù)減少指令的減少也導(dǎo)致總指令數(shù)減少優(yōu)化后算術(shù)運(yùn)算指令所占比例優(yōu)化后算術(shù)運(yùn)算指令所占比例從從MIPS之比得出的結(jié)論：之比得出的結(jié)論：減少減少ALU指令的比例會使速度變慢指令的比例會使速度變慢減少使用頻率高的指令會使速度變慢減少使用頻率高的指令會使速度變慢減少速

7、度快的指令的比例會使速度變慢減少速度快的指令的比例會使速度變慢610MIPSITNE43% 0.50.21527.39%1 43% 0.50.7855v第第13題題向量方式計算速度是標(biāo)量方式的向量方式計算速度是標(biāo)量方式的9倍倍測試程序測試程序P總時間總時間T，25%T為向量方式，為向量方式，75%T為標(biāo)量方式為標(biāo)量方式求測試程序求測試程序P中向量代碼占的比例中向量代碼占的比例v解：解：T向量向量：T標(biāo)量標(biāo)量=1：3T向量向量=x/9v， T標(biāo)量標(biāo)量=(1-x) /v 1:1:391xx方法二：方法二：190.250.75xxTT 6niiilpL1iniippH12logvOPOP編碼優(yōu)化的目

8、標(biāo)編碼優(yōu)化的目標(biāo)l平均長度短（冗余?。┢骄L度短（冗余?。﹍編碼規(guī)整（長度種類少）編碼規(guī)整（長度種類少）v最短平均長度最短平均長度（信息源熵信息源熵）：）：l v信息冗余量信息冗余量l（實(shí)際長度（實(shí)際長度-H-H）/ /實(shí)際長度實(shí)際長度vHuffmanHuffman編碼編碼l平均長度最短的方案平均長度最短的方案l編碼不唯一，但長度確定編碼不唯一，但長度確定l每次選擇兩個最小值節(jié)點(diǎn)每次選擇兩個最小值節(jié)點(diǎn)l l非葉子結(jié)點(diǎn)值相加非葉子結(jié)點(diǎn)值相加7v擴(kuò)展編碼擴(kuò)展編碼l等長、不等長等長、不等長lX-Y-ZX-Y-Z、X/Y/ZX/Y/Zl短編碼不能是長編碼的短編碼不能是長編碼的前綴前綴l一定要用短編碼表

9、示頻率高的指令一定要用短編碼表示頻率高的指令v變址位移量變址位移量l補(bǔ)碼表示（補(bǔ)碼表示（-2-2n-1n-12 2n-1n-1-1-1）v指令類型指令類型lR-RR-R：速度快，給頻率高的指令使用：速度快，給頻率高的指令使用lM-MM-M8v第第3題（題（10條指令）條指令）第第2問：要求問：要求OP平均長度最短，則一定是平均長度最短，則一定是Huffman編碼（畫編碼（畫Huffman樹時樹時要注意，確保每次選兩個概率最小的），要注意，確保每次選兩個概率最小的），2.7第第3問：問： OP平均長度最短的擴(kuò)展編碼（不一定是等長擴(kuò)展），究竟哪種最平均長度最短的擴(kuò)展編碼（不一定是等長擴(kuò)展），究竟哪

10、種最短，要一個一個去試，本題可以試一下短，要一個一個去試，本題可以試一下2-5、2-4、3-4，結(jié)果，結(jié)果2-5最短，最短，2.9第第4問：問： OP平均長度最短的平均長度最短的等長等長擴(kuò)展編碼，只需考慮擴(kuò)展編碼，只需考慮2-4（1-2不可能、不可能、3-6太長），太長），2.92v第第5題（三地址題（三地址12條，單地址條，單地址254條，總長條，總長16位，每個地址位，每個地址4位）位）4-8-12等長擴(kuò)展，等長擴(kuò)展，12/X/254若不考慮單地址指令，則二地址最多若不考慮單地址指令，則二地址最多416=64條條考慮單地址指令，每預(yù)留一個二地址指令碼點(diǎn)，則可以擴(kuò)展考慮單地址指令，每預(yù)留一個

11、二地址指令碼點(diǎn)，則可以擴(kuò)展16條單地址指條單地址指令，要使單地址指令達(dá)到令，要使單地址指令達(dá)到254條，則應(yīng)預(yù)留條，則應(yīng)預(yù)留254/16=15.9個二地址指令碼點(diǎn)個二地址指令碼點(diǎn)因此，二地址最多可以設(shè)計因此，二地址最多可以設(shè)計64-16=48條條9v第第6題（題（9條指令，條指令，8位（位（R-R）、）、16位（位（R-M）兩種）兩種指令字長）指令字長）第第1問：問：OP平均長度最短的擴(kuò)展編碼，與第平均長度最短的擴(kuò)展編碼，與第3題類似，題類似，2-4、2-5比較后可知，比較后可知，2-5平均長度最短，平均長度最短，2.9第第2問：為提高問：為提高速度速度，應(yīng)將使用頻率高的指令安排成，應(yīng)將使用頻

12、率高的指令安排成R-R型，型，為減少存儲為減少存儲容量容量，應(yīng)將使用頻率高的指令安排成短，應(yīng)將使用頻率高的指令安排成短OP（2位），因此位），因此R編碼占編碼占3位，可以表示位，可以表示8個通用寄存器個通用寄存器第第3、4問：通用寄存器做變址寄存器，則變址位移量只能是問：通用寄存器做變址寄存器，則變址位移量只能是5位（位（16位位-5位位OP-3位位R-3位位X），偏移范圍），偏移范圍-1615（補(bǔ)碼）（補(bǔ)碼）10v1、若某機(jī)要求有：、若某機(jī)要求有：3地址指令地址指令4條，單地址指令條，單地址指令255條，條，0地址地址指令指令16條。設(shè)指令字長為條。設(shè)指令字長為12位，每個地址碼為位，每個地

13、址碼為3位。問能否用擴(kuò)位。問能否用擴(kuò)展操作碼為其編碼？單地址指令為展操作碼為其編碼？單地址指令為254條呢？請說明理由。條呢？請說明理由。3-9-12不等長擴(kuò)展，不等長擴(kuò)展， 4/255/16； 4/254/16若不考慮若不考慮0地址指令，則單地址最多地址指令，則單地址最多426=256條條考慮考慮0地址指令，每預(yù)留一個單地址指令碼點(diǎn)，則可以擴(kuò)展地址指令，每預(yù)留一個單地址指令碼點(diǎn)，則可以擴(kuò)展8條條0地址指令，要使地址指令，要使0地址指令達(dá)到地址指令達(dá)到16條，則應(yīng)預(yù)留條，則應(yīng)預(yù)留16/8=2個個單地址指令碼點(diǎn)單地址指令碼點(diǎn)因此，單地址最多可以設(shè)計因此，單地址最多可以設(shè)計256-2=254條條4

14、/255/164/254/1611v2、某機(jī)指令字長為、某機(jī)指令字長為16位。設(shè)有單地址指令和雙地址指令兩類。位。設(shè)有單地址指令和雙地址指令兩類。若每個地址字段均為若每個地址字段均為6位，且雙地址指令有位，且雙地址指令有x條。問單地址指令條。問單地址指令可以有多少條？可以有多少條？4-10擴(kuò)展擴(kuò)展雙地址指令剩余雙地址指令剩余16-x個碼點(diǎn)作擴(kuò)展標(biāo)志個碼點(diǎn)作擴(kuò)展標(biāo)志共可擴(kuò)出單地址指令（共可擴(kuò)出單地址指令（16-x）26條條12v某處理機(jī)的指令字長為某處理機(jī)的指令字長為16位，有位，有2地址指令、地址指令、1地址地址指令和指令和0地址指令地址指令3類，每個地址字段的長度均為類，每個地址字段的長度均

15、為6位。位。如果如果2地址指令有地址指令有15條，條，0地址指令和地址指令和1地址指令的條數(shù)基本地址指令的條數(shù)基本相等，那么相等，那么0地址指令和地址指令和1地址指令各有多少條？為地址指令各有多少條？為3類指令分類指令分配操作碼。配操作碼。如果要求如果要求3類指令條數(shù)的比例為類指令條數(shù)的比例為1：9：9。那么。那么3類指令的條類指令的條數(shù)各有多少條？為數(shù)各有多少條？為3類指令分配操作碼。類指令分配操作碼。v解解4-10-1615/63/64、14/126/12813v用于文字處理的某專用機(jī)，每個文字字符用用于文字處理的某專用機(jī)，每個文字字符用4位十進(jìn)制數(shù)（位十進(jìn)制數(shù)（0-9）編碼表示，空格用編

16、碼表示，空格用-表示，在對傳送的文字符和空格進(jìn)行統(tǒng)計表示，在對傳送的文字符和空格進(jìn)行統(tǒng)計后，得出其出現(xiàn)的概率為：后，得出其出現(xiàn)的概率為：若上述數(shù)字和空格均用二進(jìn)制編碼，試設(shè)計二進(jìn)制信息位平均長度最短若上述數(shù)字和空格均用二進(jìn)制編碼，試設(shè)計二進(jìn)制信息位平均長度最短的編碼。的編碼。若傳送若傳送106個文字符號（每個文字符號后均跟一個空格），按最短編碼，個文字符號（每個文字符號后均跟一個空格），按最短編碼，共需傳送多少個二進(jìn)制位？共需傳送多少個二進(jìn)制位？若十進(jìn)制數(shù)字和空格均用若十進(jìn)制數(shù)字和空格均用4位二進(jìn)制碼表示，共需傳送多少個二進(jìn)制位？位二進(jìn)制碼表示，共需傳送多少個二進(jìn)制位？-01234567890

17、.20.170.060.080.110.080.050.080.130.030.01（文字）（文字）- （文字）（文字）- （文字）（文字）14v計算機(jī)中優(yōu)化使用的操作碼編碼方法是（計算機(jī)中優(yōu)化使用的操作碼編碼方法是（ ）A、Huffman編碼編碼 B、ASCII碼碼C、BCD碼碼 D、擴(kuò)展編碼、擴(kuò)展編碼v支持動態(tài)再定位的尋址方式是（支持動態(tài)再定位的尋址方式是（ ）A、基址尋址、基址尋址 B、間接尋址、間接尋址C、變址尋址、變址尋址 D、間接尋址、間接尋址v變址尋址的主要作用是（變址尋址的主要作用是（ ）A、支持程序的動態(tài)定位、支持程序的動態(tài)定位 B、支持訪存地址的越界檢查、支持訪存地址的越界

18、檢查C、支持向量、數(shù)組的運(yùn)算尋址、支持向量、數(shù)組的運(yùn)算尋址 D、支持、支持OS的進(jìn)程調(diào)度的進(jìn)程調(diào)度v對系統(tǒng)程序員不透明的是（對系統(tǒng)程序員不透明的是（ ）A、Cache B、系列機(jī)各檔不同的數(shù)據(jù)通路寬度、系列機(jī)各檔不同的數(shù)據(jù)通路寬度C、指令緩沖寄存器、指令緩沖寄存器 D、虛擬存儲器、虛擬存儲器15v對應(yīng)用程序員不透明的是（對應(yīng)用程序員不透明的是（ ）A、先行進(jìn)位鏈、先行進(jìn)位鏈 B、乘法器、乘法器C、指令緩沖寄存器、指令緩沖寄存器 D、條件碼寄存器、條件碼寄存器v計算機(jī)系統(tǒng)結(jié)構(gòu)不包括（計算機(jī)系統(tǒng)結(jié)構(gòu)不包括（ ）A、主存速度、主存速度 B、機(jī)器工作狀態(tài)、機(jī)器工作狀態(tài)C、信息保護(hù)、信息保護(hù) D、數(shù)據(jù)表

19、示、數(shù)據(jù)表示v判斷題判斷題系統(tǒng)是否設(shè)置浮點(diǎn)指令對計算機(jī)系統(tǒng)結(jié)構(gòu)是透明的。系統(tǒng)是否設(shè)置浮點(diǎn)指令對計算機(jī)系統(tǒng)結(jié)構(gòu)是透明的。存儲器采用單體單字，還是多體交叉存取，對系統(tǒng)結(jié)構(gòu)設(shè)計應(yīng)是透明的。存儲器采用單體單字，還是多體交叉存取，對系統(tǒng)結(jié)構(gòu)設(shè)計應(yīng)是透明的。系列機(jī)增加新型號時，為增加尋址靈活性和縮短平均指令字長，可以由系列機(jī)增加新型號時，為增加尋址靈活性和縮短平均指令字長，可以由原等長操作碼改為有多種碼長的擴(kuò)展操作碼。原等長操作碼改為有多種碼長的擴(kuò)展操作碼。對概率不等的事件用對概率不等的事件用Huffman編碼，其具體編碼不唯一，但平均長度肯編碼，其具體編碼不唯一，但平均長度肯定是唯一的，且是最短的。定是

20、唯一的，且是最短的。16v4、直接利用公式：、直接利用公式：P41Ta= fi(HiTc+(1- Hi)Tm)+(1- fi)( HdTc+(1- Hd) Tm)=22.16nsfi=20%、Tc=20ns、Tm=80ns、Hi=98%、Hd=96%v10、頁面失效的虛頁號：裝入位為頁面失效的虛頁號：裝入位為0的虛頁，的虛頁，1、2、5、6由虛地址計算實(shí)地址：由虛地址計算實(shí)地址：虛地址虛地址頁面大小虛頁號頁面大小虛頁號頁內(nèi)位移頁內(nèi)位移由虛頁號查頁表得實(shí)頁號由虛頁號查頁表得實(shí)頁號實(shí)地址實(shí)地址=實(shí)頁號實(shí)頁號頁面大小頁內(nèi)位移頁面大小頁內(nèi)位移809610247928310249284000頁面失效的無

21、實(shí)地址頁面失效的無實(shí)地址虛頁號虛頁號 0 1 2 3 4 5 6 7實(shí)頁號實(shí)頁號 2 3 1 0 1 0 2 3裝入位裝入位 1 0 0 1 1 0 0 117v10、方法二：、方法二：頁面失效的虛頁號：裝入位為頁面失效的虛頁號：裝入位為0的虛頁，的虛頁，1、2、5、6由虛地址計算實(shí)地址：由虛地址計算實(shí)地址：將虛地址用二進(jìn)制數(shù)表示，將虛地址用二進(jìn)制數(shù)表示，高高3位地址為虛頁號位地址為虛頁號，低，低10位地址為頁內(nèi)位移位地址為頁內(nèi)位移由虛頁號查頁表得實(shí)頁號由虛頁號查頁表得實(shí)頁號用實(shí)頁號替換二進(jìn)制虛地址中的虛頁號即得實(shí)地址用實(shí)頁號替換二進(jìn)制虛地址中的虛頁號即得實(shí)地址（8096）10=（111111

22、0100000）2，111為虛頁號為虛頁號7（0111110100000）2=（4000）10頁面失效的無實(shí)地址頁面失效的無實(shí)地址虛頁號虛頁號0 1 2 3 4 5 6 7實(shí)頁號實(shí)頁號2 3 1 0 1 0 2 3裝入位裝入位1 0 0 1 1 0 0 118v補(bǔ)充：補(bǔ)充：某段頁式虛擬存儲器，虛地址由某段頁式虛擬存儲器，虛地址由2位段號、位段號、2位頁號和位頁號和11位頁內(nèi)位移組成，主存容量位頁內(nèi)位移組成，主存容量32KB，每段可有訪問方式保護(hù)，每段可有訪問方式保護(hù)，其頁表和保護(hù)位如下表所示。其頁表和保護(hù)位如下表所示。此地址空間中共有多少虛頁此地址空間中共有多少虛頁當(dāng)程序中遇到下列情況時，由虛

23、地址計算實(shí)地址，說明哪個當(dāng)程序中遇到下列情況時，由虛地址計算實(shí)地址，說明哪個會發(fā)生段失效、頁失效和保護(hù)失效。會發(fā)生段失效、頁失效和保護(hù)失效。段號段號段段0段段1段段2段段3訪問方式訪問方式只讀只讀可讀可讀/執(zhí)行執(zhí)行可讀可讀/寫寫/執(zhí)行執(zhí)行可讀可讀/寫寫虛頁虛頁0所在位置所在位置實(shí)頁實(shí)頁9在輔存上在輔存上頁表不在內(nèi)頁表不在內(nèi)存存實(shí)頁實(shí)頁14虛頁虛頁1所在位置所在位置實(shí)頁實(shí)頁3實(shí)頁實(shí)頁0實(shí)頁實(shí)頁1虛頁虛頁2所在位置所在位置在輔存上在輔存上實(shí)頁實(shí)頁15實(shí)頁實(shí)頁6虛頁虛頁3所在位置所在位置實(shí)頁實(shí)頁12實(shí)頁實(shí)頁8在輔存上在輔存上19方式方式段段頁頁頁內(nèi)位移頁內(nèi)位移取數(shù)取數(shù)011取數(shù)取數(shù)1112取數(shù)取數(shù)3

24、32047存數(shù)存數(shù)014存數(shù)存數(shù)212存數(shù)存數(shù)1014轉(zhuǎn)移至此轉(zhuǎn)移至此13100取數(shù)取數(shù)0250取數(shù)取數(shù)205轉(zhuǎn)移至此轉(zhuǎn)移至此3060l由主存容量為由主存容量為32KB，可知實(shí)地址：，可知實(shí)地址：實(shí)頁號（實(shí)頁號（4） 頁內(nèi)位移（頁內(nèi)位移（11）l虛地址：虛地址：段號段號（2）頁號頁號（2）頁內(nèi)位移（頁內(nèi)位移（11）l頁面大?。喉撁娲笮。?11=2048Bl實(shí)地址計算方法同上實(shí)地址計算方法同上l頁表不在主存內(nèi)的段頁表不在主存內(nèi)的段2發(fā)生段失效發(fā)生段失效l頁面在輔存上的發(fā)生頁失效頁面在輔存上的發(fā)生頁失效l取數(shù)表示讀，取出的數(shù)不能作為取數(shù)表示讀，取出的數(shù)不能作為指令執(zhí)行；只讀單元不能寫、執(zhí)行；指令執(zhí)

25、行；只讀單元不能寫、執(zhí)行；轉(zhuǎn)移至此為執(zhí)行，不能讀、寫，訪轉(zhuǎn)移至此為執(zhí)行，不能讀、寫，訪問不當(dāng)?shù)臑楸Ｗo(hù)方式失效問不當(dāng)?shù)臑楸Ｗo(hù)方式失效20方式方式段段頁頁頁內(nèi)位移頁內(nèi)位移段失效段失效頁失效頁失效實(shí)頁號實(shí)頁號實(shí)地址實(shí)地址保護(hù)失效保護(hù)失效取數(shù)取數(shù)011無無無無36145無無取數(shù)取數(shù)1112無無無無010無無取數(shù)取數(shù)332047無無有有無無無無/存數(shù)存數(shù)014無無無無36148有有存數(shù)存數(shù)212有有/無無無無/存數(shù)存數(shù)1014無無有有無無無無/轉(zhuǎn)移至此轉(zhuǎn)移至此13100無無無無816484無無取數(shù)取數(shù)0250無無有有無無無無/取數(shù)取數(shù)205無無/無無無無/轉(zhuǎn)移至此轉(zhuǎn)移至此3060無無無無1428732有

26、有21v第第6題題vA1+A2+ A3+A4+ A5+A6+ A7+A8+ A9+A10123456789123456789123456789123456789123456789123456789TP=9/21t=3/7tSp=（95）/21=2.14E=（95）/（215）=42.9%81510152122v第第7題：靜態(tài)流水線題：靜態(tài)流水線A1B1+A2B2+A3B3+A4B4+A5B5+A6B612345678910111234561234567891011789101112345678910111234567891011122請改為動態(tài)流水線練習(xí)請改為動態(tài)流水線練習(xí)12345623v第

27、第8題題算法：算法：(a1+b1)c1+(a2+b2)c2 +(a3+b3)c3+ (a4+b4)c4總時間：（總時間：（3+31）+ （4+32）+（3+1） +3=23效率：效率：(73+44)/(234)=37/92=40.2%1234一一二二三三四四567一一 一一 二二 二二 三三 三三 四四 四四12345671234一一二二三三四四5672324v第第9題題動態(tài)流水線動態(tài)流水線a1b1+a2b2+a3b3+a4b4+a5b5+a6b6+a7b7+a8b812345678一一 二二 三三 四四五五六六七七一一 二二 三三 四四五五六六七七一一 二二 三三 四四五五六六七七12345

28、6781234567812345678一一 二二 三三 四四五五六六七七123請改為靜態(tài)流水線練習(xí)請改為靜態(tài)流水線練習(xí)ABCDEF25v第第10題題6個任務(wù)的總執(zhí)行時間為：個任務(wù)的總執(zhí)行時間為：8（第一個任務(wù)用（第一個任務(wù)用8個周期）個周期）+53（后（后5個任務(wù)，每個任務(wù)，每3周期執(zhí)行一個，周期執(zhí)行一個，取決于最慢部件取決于最慢部件）實(shí)際吞吐率實(shí)際吞吐率=6/23t效率效率=（86）/（235）=48/115=41.7%123111222333123112233123826v第第11題題禁止向量（延遲禁止表）禁止向量（延遲禁止表）=（1，3，4，8）原始沖突向量原始沖突向量=（1000110

29、1）狀態(tài)轉(zhuǎn)移圖略狀態(tài)轉(zhuǎn)移圖略最大吞吐率的調(diào)度方案（最大吞吐率的調(diào)度方案（2，5），吞吐率），吞吐率=1/3.5輸入輸入6個任務(wù)的實(shí)際吞吐率：個任務(wù)的實(shí)際吞吐率：6/（9+2+5+2+5+2）=6/25v補(bǔ)：有長度為補(bǔ)：有長度為8的向量的向量A和和B，分別畫出在下列，分別畫出在下列4中結(jié)構(gòu)的處理器上求點(diǎn)積的中結(jié)構(gòu)的處理器上求點(diǎn)積的時空圖時空圖有一個乘法部件和一個加法部件，不能同時工作，部件內(nèi)部采用順序方有一個乘法部件和一個加法部件，不能同時工作，部件內(nèi)部采用順序方式，完成一次加、乘需要式，完成一次加、乘需要5拍拍同上，只是乘法器和加法器可以并行工作同上，只是乘法器和加法器可以并行工作有一個乘、加

30、雙功能靜態(tài)流水線，均由有一個乘、加雙功能靜態(tài)流水線，均由5段組成，每段段組成，每段1拍拍有乘、加兩條流水線，可并行工作，每段有乘、加兩條流水線，可并行工作，每段1拍拍27v解解（1）（2）(a1b1+a2b2)+a3b3)+a4b4)+a5b5)+a6b6)+a7b7)+a8b8加加乘乘54075加加乘乘5404528（3）靜態(tài)雙功能流水線）靜態(tài)雙功能流水線(a1b1+ a2b2)+(a3b3+ a4b4)+(a5b5+ a6b6)+(a7b7 + a8b8)91011121314159101112131415910111213141591011121314159101112131415123

31、4567812345678123456781234567812345678123029（4）兩條流水線可同時工作）兩條流水線可同時工作(a1b1+ a2b2)+ a7b7+ (a5b5+ a6b6)+(a3b3+ a4b4)+ a8b8910111213141591011121314159101112131415910111213141591011121314151 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8122730v有一條靜態(tài)加、乘多功能流水線由有一條靜態(tài)加、乘多功能流水線由5段組成，

32、加法用段組成，加法用1、3、4、5段，乘法用段，乘法用1、2、5段，第段，第3段的時間為段的時間為2t，其余段為，其余段為t，而且流水線的輸出可以直接返回到輸入端或暫存于相應(yīng)的流水而且流水線的輸出可以直接返回到輸入端或暫存于相應(yīng)的流水線寄存器中，現(xiàn)在要在該流水線上計算線寄存器中，現(xiàn)在要在該流水線上計算 ，畫出其，畫出其時空圖，并計算其吞吐率、加速比和效率。時空圖，并計算其吞吐率、加速比和效率。v有一條動態(tài)多功能流水線由有一條動態(tài)多功能流水線由5段組成，加法用段組成，加法用1、3、4、5段，段，乘法用乘法用1、2、5段，第段，第2段的時間為段的時間為2t，其余段為，其余段為t，而且流，而且流水線

33、的輸出可以直接返回到輸入端或暫存于相應(yīng)的流水線寄存水線的輸出可以直接返回到輸入端或暫存于相應(yīng)的流水線寄存器中，現(xiàn)在要在該流水線上計算器中，現(xiàn)在要在該流水線上計算 ，畫出其時空圖，畫出其時空圖，并計算其吞吐率、加速比和效率。并計算其吞吐率、加速比和效率。41()iiiAB41iiiA B31v有一條動態(tài)多功能流水線由有一條動態(tài)多功能流水線由6段組成，其中段組成，其中1、4、5、6段組段組成乘法流水線，成乘法流水線，1、2、3、6段組成加法流水線，各流水段的時段組成加法流水線，各流水段的時間均為間均為50ns，假設(shè)流水線的輸出可以直接返回到輸入端，而，假設(shè)流水線的輸出可以直接返回到輸入端，而且有足

34、夠的緩沖寄存器，現(xiàn)在要用最快的方式在該流水線上計且有足夠的緩沖寄存器，現(xiàn)在要用最快的方式在該流水線上計算算 ，畫出其時空圖，并計算其吞吐率、加速比和，畫出其時空圖，并計算其吞吐率、加速比和效率。效率。51iiiix y z32v有一有一5段流水線，各段執(zhí)行時間均段流水線，各段執(zhí)行時間均t，其預(yù)約表如下：，其預(yù)約表如下：畫出流水線任務(wù)調(diào)度的狀態(tài)轉(zhuǎn)移圖畫出流水線任務(wù)調(diào)度的狀態(tài)轉(zhuǎn)移圖分別求出允許不等時間間隔的調(diào)度和等時間間隔的調(diào)度的兩種最優(yōu)調(diào)度分別求出允許不等時間間隔的調(diào)度和等時間間隔的調(diào)度的兩種最優(yōu)調(diào)度策略，以及這兩種調(diào)度策略的流水線最大吞吐率策略，以及這兩種調(diào)度策略的流水線最大吞吐率若連續(xù)輸入若

35、連續(xù)輸入10個任務(wù)，求這兩種調(diào)度策略的實(shí)際吞吐率和加速比個任務(wù)，求這兩種調(diào)度策略的實(shí)際吞吐率和加速比 時間時間功能段功能段1234567S1S2S3S4S533v下列關(guān)于標(biāo)量流水機(jī)的說法不正確的是（下列關(guān)于標(biāo)量流水機(jī)的說法不正確的是（ ）A、可對標(biāo)量進(jìn)行流水處理、可對標(biāo)量進(jìn)行流水處理 B、沒有向量數(shù)據(jù)表示、沒有向量數(shù)據(jù)表示C、不能對向量數(shù)據(jù)進(jìn)行運(yùn)算、不能對向量數(shù)據(jù)進(jìn)行運(yùn)算 D、可以對向量、數(shù)組進(jìn)行運(yùn)算、可以對向量、數(shù)組進(jìn)行運(yùn)算v以下說法不正確的是（以下說法不正確的是（ ）A、線性流水線是單功能流水線、線性流水線是單功能流水線 B、動態(tài)流水線是雙功能流水線、動態(tài)流水線是雙功能流水線C、靜態(tài)流水線

36、是多功能流水線、靜態(tài)流水線是多功能流水線 D、動態(tài)流水線只能是單功能流水線、動態(tài)流水線只能是單功能流水線v靜態(tài)流水線是指（靜態(tài)流水線是指（ ）A、只有一種功能的流水線、只有一種功能的流水線 B、可同時執(zhí)行多種功能的流水線、可同時執(zhí)行多種功能的流水線C、同時只能完成一種功能的多功能流水線、同時只能完成一種功能的多功能流水線 D、功能不能改變的流水線、功能不能改變的流水線v非線性流水線是指（非線性流水線是指（ ）A、一次運(yùn)算中使用流水線的多個功能段、一次運(yùn)算中使用流水線的多個功能段B、一次運(yùn)算中要多次使用流水線的某些功能段、一次運(yùn)算中要多次使用流水線的某些功能段C、流水線中某些功能段在各次運(yùn)算中的

37、作用不同、流水線中某些功能段在各次運(yùn)算中的作用不同D、流水線中的各個功能段在各種運(yùn)算中有不同的組合、流水線中的各個功能段在各種運(yùn)算中有不同的組合34v與流水線最大吞吐率高低有關(guān)的是（與流水線最大吞吐率高低有關(guān)的是（ ）A、各個子過程的時間、各個子過程的時間 B、最快子過程的時間、最快子過程的時間C、最慢子過程的時間、最慢子過程的時間 D、最后子過程的時間、最后子過程的時間v在流水線中，全局相關(guān)是指（在流水線中，全局相關(guān)是指（ ）A、先寫后讀相關(guān)、先寫后讀相關(guān) B、先讀后寫相關(guān)、先讀后寫相關(guān)C、指令相關(guān)、指令相關(guān) D、由轉(zhuǎn)移指令引起的相關(guān)、由轉(zhuǎn)移指令引起的相關(guān)v流水機(jī)器對全局相關(guān)的處理不包括（流

38、水機(jī)器對全局相關(guān)的處理不包括（ ）A、猜測法、猜測法 B、提前形成條件碼、提前形成條件碼C、加快短循環(huán)程序的執(zhí)行、加快短循環(huán)程序的執(zhí)行 D、設(shè)置相關(guān)專用通路、設(shè)置相關(guān)專用通路vCRAY-1向量機(jī)要實(shí)現(xiàn)指令的鏈接，必須滿足的條件是（向量機(jī)要實(shí)現(xiàn)指令的鏈接，必須滿足的條件是（ ）A、源向量相同，功能部件不沖突，有指令相關(guān)、源向量相同，功能部件不沖突，有指令相關(guān)B、源向量不同，功能部件相同，無指令相關(guān)、源向量不同，功能部件相同，無指令相關(guān)C、源向量、功能部件都不同，指令有先寫后讀相關(guān)、源向量、功能部件都不同，指令有先寫后讀相關(guān)D、源向量、功能部件都不同，指令有先讀后寫相關(guān)、源向量、功能部件都不同，指

39、令有先讀后寫相關(guān)35vCRAY-1機(jī)啟動存儲器、流水部件及寄存器打入各需機(jī)啟動存儲器、流水部件及寄存器打入各需1拍，拍，“加加”6拍、拍、“乘乘”7拍、拍、“訪存訪存”6拍，下列向量指令串中的向拍，下列向量指令串中的向量長度均為量長度均為N，則指令串最短的執(zhí)行時間是（，則指令串最短的執(zhí)行時間是（ ）拍）拍 V3存儲器存儲器 V4V0+V1 V2V4*V3A、N+19 B、N+18 C、N+17 D、N+16vCRAY-1的兩條向量指令屬于的兩條向量指令屬于 （）（） V1V2+V3 V4V1*V5A、沒有功能部件沖突和源向量沖突，可以并行、沒有功能部件沖突和源向量沖突，可以并行B、沒有功能部件

40、沖突和源向量沖突，可以鏈接、沒有功能部件沖突和源向量沖突，可以鏈接C、沒有源向量沖突，可以交換順序執(zhí)行、沒有源向量沖突，可以交換順序執(zhí)行D、有向量寄存器沖突，只能串行、有向量寄存器沖突，只能串行36v4、32個處理器，編號個處理器，編號031，11號處理器與哪個相連號處理器與哪個相連Cube3：11D=01011B，00011B = 3D，3號號PM2+3：（：（11+23）mod 32 = 19，19號號PM2-4：（：（11-24）mod 32 = 27，27號號Shuffle：01011B循環(huán)左移一位循環(huán)左移一位=10110B=22D，22號號Butterfly：01011B最高位與最低

41、位交換最高位與最低位交換=11010B=26D，26號號Shuffle(shuffle)： 01011B循環(huán)左移二位循環(huán)左移二位=01101B=13D，13號號Shuffle(Cube0 (PM2-1)： （11-21）mod 32 = 9D=01001B，再最低位，再最低位取反得取反得01000B，最后循環(huán)左移一位得：，最后循環(huán)左移一位得：10000B=16D，16號號v7、256個個PE的的SIMD機(jī)器，采用全混洗互連函數(shù)，混洗機(jī)器，采用全混洗互連函數(shù)，混洗10次后，次后，197號號PE與哪個與哪個PE相連相連197D=11000101B（8位，因?yàn)楣参?，因?yàn)楣?56個個PE）循環(huán)左移循環(huán)

42、左移10次（相當(dāng)于次（相當(dāng)于2次，因?yàn)楣泊?，因?yàn)楣?位）為：位）為：00010111B=23D，23號號37v20、32個處理器的個處理器的5（log232）級）級STARAN網(wǎng)，當(dāng)級控制信號網(wǎng)，當(dāng)級控制信號為為10110（從右至左分別控制第（從右至左分別控制第0級至第級至第4級）時，級）時，17號處理器連號處理器連接哪個處理器接哪個處理器根據(jù)根據(jù)STARAN網(wǎng)作為交換網(wǎng)絡(luò)的特點(diǎn)，某級控制信號為網(wǎng)作為交換網(wǎng)絡(luò)的特點(diǎn)，某級控制信號為1，就實(shí)現(xiàn)了某個，就實(shí)現(xiàn)了某個Cubei，因此本題實(shí)現(xiàn)，因此本題實(shí)現(xiàn)Cube4+Cube2+Cube1功能功能17D=10001B，第，第4、2、1位取反后為位取反后

43、為00111B=7D，7號號v21、16個處理器，先個處理器，先8組組2元交換、再元交換、再4組組4元交換，最后元交換，最后2組組8元交換，寫出互連函數(shù)元交換，寫出互連函數(shù)輸入：輸入： 0 1 2 3 4 5 6 7 8 9 A B C D E F8組組2元交換：元交換：1 0 3 2 5 4 7 6 9 8 B A D C F E4組組4元交換：元交換：2 3 0 1 6 7 4 5 A B 8 9 E F C D2組組8元交換：元交換：5 4 7 6 1 0 3 2 D C F E 9 8 B A（輸出）（輸出）可見實(shí)現(xiàn)了可見實(shí)現(xiàn)了Cube2+Cube0互連函數(shù)表達(dá)式：互連函數(shù)表達(dá)式：01

44、230123)(PPPPPPPPCube38v補(bǔ)：補(bǔ)：N=16的的STARAN網(wǎng)在級控制下實(shí)現(xiàn)分組交換置換，如果網(wǎng)在級控制下實(shí)現(xiàn)分組交換置換，如果實(shí)現(xiàn)的分組交換置換是：首先是實(shí)現(xiàn)的分組交換置換是：首先是4組組4元交換，然后是元交換，然后是2組組8元交元交換，最后是換，最后是1組組16元交換，請寫出網(wǎng)絡(luò)實(shí)現(xiàn)的互連函數(shù)。元交換，請寫出網(wǎng)絡(luò)實(shí)現(xiàn)的互連函數(shù)。0 1 2 3 4 5 6 7 8 9 A B C D E F3 2 1 0 7 6 5 4 B A 9 8 F E D C4 5 6 7 0 1 2 3 C D E F 8 9 A BB A 9 8 F E D C 3 2 1 0 7 6 5 4

45、 (0 B)(1 A)(2 9)(3 8)(4 F)(5 E)(6 D)(7 C)Cube3+Cube1+Cube0v補(bǔ)：用一個補(bǔ)：用一個N=8的的3級級Omega網(wǎng)絡(luò)連接網(wǎng)絡(luò)連接8個處理機(jī)個處理機(jī)P0P7，如，如果果P6要把數(shù)據(jù)廣播給要把數(shù)據(jù)廣播給P0P4，如果，如果P3要把數(shù)據(jù)廣播給要把數(shù)據(jù)廣播給P5P7，能否同時實(shí)現(xiàn)播送要求，畫出開關(guān)狀態(tài)圖。能否同時實(shí)現(xiàn)播送要求，畫出開關(guān)狀態(tài)圖。39v能能 0 0 2 2 1 1 3 3 4 4 6 6 5 5 7 7 0 0 2 2 1 1 3 3 4 4 6 6 5 5 7 7 0 0 4 4 1 1 5 5 2 2 6 6 3 3 7 7 0 0

46、1 1 2 2 3 3 4 4 5 5 6 6 7 7 I I J J K K L L 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 入入 端端 出出 端端 0 0 4 4 1 1 5 5 2 2 6 6 3 3 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 2 2 級級 1 1 級級 0 0 級級 A A B B C C D D E E F F G G H H 40v補(bǔ)：對于采用級控制的補(bǔ)：對于采用級控制的3級立方體互連網(wǎng)絡(luò)，當(dāng)?shù)诩壛⒎襟w互連網(wǎng)絡(luò)，當(dāng)?shù)趇級為直連狀級為直連狀態(tài)時，不能實(shí)

47、現(xiàn)哪些節(jié)點(diǎn)之間的通信？為什么？反之，當(dāng)?shù)趹B(tài)時，不能實(shí)現(xiàn)哪些節(jié)點(diǎn)之間的通信？為什么？反之，當(dāng)?shù)趇級級為交換狀態(tài)呢？為交換狀態(tài)呢？因?yàn)榈谝驗(yàn)榈趇級為交換狀態(tài)時，實(shí)現(xiàn)的是級為交換狀態(tài)時，實(shí)現(xiàn)的是cubei互連函數(shù)，所以互連函數(shù)，所以第第i級為直連狀態(tài)時，不能實(shí)現(xiàn)第級為直連狀態(tài)時，不能實(shí)現(xiàn)第i位取反的節(jié)點(diǎn)間的通信位取反的節(jié)點(diǎn)間的通信第第i級為交換狀態(tài)時，不能實(shí)現(xiàn)第級為交換狀態(tài)時，不能實(shí)現(xiàn)第i位不變的節(jié)點(diǎn)間的通信位不變的節(jié)點(diǎn)間的通信41v5、（1）3條指令全并行，條指令全并行，72拍（乘法最慢：拍（乘法最慢：1+7+1+63）（2）1、2并行與并行與3鏈接，鏈接，要求要求1比比2早啟動早啟動1拍，否則不

48、能與拍，否則不能與3鏈接鏈接， 80拍（拍（1+7+1+1+6+1+63）（3）1、2并行，并行，3、4鏈接，鏈接，1、2和和3、4之間串行。之間串行。 151拍（拍（1+6+1+63+1+6+1+1+7+1+63）（4）1、2、3兩級鏈接與兩級鏈接與4串，串， 166拍（拍（1+6+1+1+14+1+1+6+1+63+1+6+1+63）（5）1、2并與并與3鏈接，要求鏈接，要求2比比1早啟動早啟動1拍，否則不能與拍，否則不能與3鏈接，與鏈接，與4串串 151拍拍 （ 1+7+1+1+6+1+63+1+6+1+63）（6）1、2并，并，2與與3鏈接，鏈接，4與與3串行，串行， 152拍（拍（1

49、+6+1+1+7+1+63+1+7+1+63 ）42v8、參考例、參考例6.9設(shè)平均數(shù)度為設(shè)平均數(shù)度為Ra，可向量化比例為，可向量化比例為x，則有，則有要使要使Ra=6，則，則x=83.3%也可以直接利用也可以直接利用amdhal定律，定律， P15，fnew=x, rnew=10/2=5要使要使Ra=6，則，則Sp=6/2=3，則，則x=83.3%xxxRa4510)1 (211011xxxSp8 . 0115/)1 (143v9、設(shè)標(biāo)量速度為設(shè)標(biāo)量速度為Rs，平均速度為為，平均速度為為Ra，可向量化比例為，可向量化比例為x，加速比為，加速比為SP，則有則有要使要使SP=2，則，則X=55.6%也可以直接利用也可以直接利用Aamdhal定律，定律，P15，fnew=x, rnew=10 xRsxRsRsxRsxRsRsRaSp9101091010)1 (11011xxxSp