計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課后習(xí)題答案

計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課后習(xí)題答案PAGEPAGE47

第一章計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的基本概念1.有一個(gè)計(jì)算機(jī)系統(tǒng)可按功能分成4級(jí)，每級(jí)的指令互不相同，每一級(jí)的指令都比其下一級(jí)的指令在效能上強(qiáng)M倍，即第i級(jí)的一條指令能完成第i-1級(jí)的M條指令的計(jì)算量?，F(xiàn)若需第i級(jí)的N條指令解釋第i+1級(jí)的一條指令，而有一段第1級(jí)的程序需要運(yùn)行Ks，問在第2、3和4級(jí)上一段等效程序各需要運(yùn)行多長時(shí)間？

答：第2級(jí)上等效程序需運(yùn)行：(N/M)*Ks。第3級(jí)上等效程序需運(yùn)行：(N/M)*(N/M)*Ks。第4級(jí)上等效程序需運(yùn)行：(N/M)*(N/M)*(N/M)*Ks。

note:

由題意可知：第i級(jí)的一條指令能完成第i-1級(jí)的M條指令的計(jì)算量。而現(xiàn)在第i級(jí)有N條指令解釋第i+1級(jí)的一條指令，那么，我們就可以用N/M來表示N/M表示第i+1級(jí)需(N/M)條指令來完成第i級(jí)的計(jì)算量。所以，當(dāng)有一段第1級(jí)的程序需要運(yùn)行Ks時(shí)，在第2級(jí)就需要(N/M)Ks，以此類推

2.硬件和軟件在什么意義上是等效的？在什么意義上又是不等效的？試舉例說明。

答：軟件和硬件在邏輯功能上是等效的，原理上，軟件的功能可用硬件或固件完成，硬件的功能也可用軟件模擬完答：透明的有：指令緩沖器、時(shí)標(biāo)發(fā)生器、乘法器、先進(jìn)先出鏈、移位器、主存地址寄存器。

6.下列哪些對(duì)系統(tǒng)程序員是透明的？哪些對(duì)應(yīng)用程序員是透明的？

系列機(jī)各檔不同的數(shù)據(jù)通路寬度；虛擬存儲(chǔ)器；Cache存儲(chǔ)器；程序狀態(tài)字；“啟動(dòng)I/O”指令；“執(zhí)行”指令；指令緩沖寄存器。

答：對(duì)系統(tǒng)程序員透明的有：系列機(jī)各檔不同的數(shù)據(jù)通路寬度；Cache存儲(chǔ)器；指令緩沖寄存器；

對(duì)應(yīng)用程序員透明的有：系列機(jī)各檔不同的數(shù)據(jù)通路寬度；Cache存儲(chǔ)器；指令緩沖寄存器；虛擬存儲(chǔ)器；程序狀態(tài)字；“啟動(dòng)I/O”指令。

note:

系列機(jī)各檔不同的數(shù)據(jù)通路寬度、Cache存貯器、指令緩沖寄存器屬于計(jì)算機(jī)組成，對(duì)系統(tǒng)和程序員和應(yīng)用程序員都是透明的。

虛擬存貯器、程序狀態(tài)字、“啟動(dòng)I/O”指令，對(duì)系統(tǒng)程序員是不透明的，而對(duì)應(yīng)用程序員卻是透明的。

“執(zhí)行”指令則對(duì)系統(tǒng)程序員和應(yīng)用程序員都是不透明的。

7.想在系列機(jī)中發(fā)展一種新型號(hào)機(jī)器，你認(rèn)為下列哪些設(shè)想是可以考慮的，哪些則不行的？為什么？

（1）新增加字符數(shù)據(jù)類型和若干條字符處理指令，以支持事務(wù)處理程序的編譯。

（2）為增強(qiáng)中斷處理功能，將中斷分級(jí)由原來的4級(jí)增加到5級(jí)，并重新調(diào)整中斷響應(yīng)的優(yōu)先次序。

（3）在CPU和主存之間增設(shè)Cache存儲(chǔ)器，以克服因主存訪問速率過低而造成的系統(tǒng)性能瓶頸。

（4）為解決計(jì)算誤差較大，將機(jī)器中浮點(diǎn)數(shù)的下溢處理方法由原來的恒置“1”法，改為用ROM存取下溢處理結(jié)果的查表舍入法。

（5）為增加尋址靈活性和減少平均指令字長，將原等長操作碼指令改為有3類不同碼長的擴(kuò)展操作碼；將源操作數(shù)尋址方式由操作碼指明改成如VAX-11那種設(shè)尋址方式位字段指明。

（6）將CPU與主存間的數(shù)據(jù)通路寬度由16位擴(kuò)展成32位，以加快主機(jī)內(nèi)部信息的傳送。

（7）為減少公用總路線的使用沖突，將單總線改為雙總線。

（8）把原0號(hào)通用寄存器改作堆棧指示器。

答：可以考慮的有：1,3,4,6,7。不可以考慮的有：2,5,8。

原則是看改進(jìn)后能否保持軟件的可移植性。

P.S.為了能使軟件長期穩(wěn)定，就要在相當(dāng)長的時(shí)期里保證系統(tǒng)結(jié)構(gòu)基本不變，因此在確定系列結(jié)構(gòu)時(shí)要非常慎重。其中最主要是確定好系列機(jī)的指令系統(tǒng)、數(shù)據(jù)表示及概念性結(jié)構(gòu)。既要考慮滿足應(yīng)用的各種需要和發(fā)展，又要考慮能方便地采用從低速到高速的各種組成的實(shí)現(xiàn)技術(shù)，即使用復(fù)雜、昂貴的組成實(shí)現(xiàn)時(shí)，也還能充分發(fā)揮該實(shí)現(xiàn)方法所帶來的好處。

8.并行處理計(jì)算機(jī)除分布處理、MPP和機(jī)群系統(tǒng)外，有哪4種基本結(jié)構(gòu)？列舉它們各自要解決的主要問題。

答：除了分布處理，MPP和機(jī)群系統(tǒng)外，并行處理計(jì)算機(jī)按其基本結(jié)構(gòu)特征可分為流水線計(jì)算機(jī)，陣列處理機(jī)，多處理機(jī)和數(shù)據(jù)流計(jì)算機(jī)四種不同的結(jié)構(gòu)。

流水線計(jì)算機(jī)主要通過時(shí)間重疊，讓多個(gè)部件在時(shí)間上交劃重疊地并行招待運(yùn)算和處理，以實(shí)現(xiàn)時(shí)間上的并行。它主要應(yīng)解決：擁塞控制，沖突防止，流水線調(diào)度等問題。

陣列處理機(jī)主要通過資源重復(fù)實(shí)現(xiàn)空間上的并行。它主要應(yīng)解決：處理單元靈活、規(guī)律的互連模式和互連網(wǎng)絡(luò)設(shè)計(jì)，數(shù)據(jù)在存儲(chǔ)器中的分布算法等問題。

多處理機(jī)主要通過資源共享，讓一組計(jì)算機(jī)在統(tǒng)一的操作系統(tǒng)全盤控制下，實(shí)現(xiàn)軟件和硬件各級(jí)上的相互作用，達(dá)到時(shí)間和空間上的異步并行。它主要應(yīng)解決：處理機(jī)間互連等硬件結(jié)構(gòu)，進(jìn)程間的同上步和通訊，多處理機(jī)調(diào)度等問題。

數(shù)據(jù)流計(jì)算機(jī)設(shè)有共享變量的概念，指令執(zhí)行順序只受指令中數(shù)據(jù)的相關(guān)性制約。數(shù)據(jù)是以表示某一操作數(shù)或參數(shù)已準(zhǔn)備就緒的數(shù)據(jù)令牌直接在指令之間傳遞。它主要應(yīng)解決：研究合適的硬件組織和結(jié)構(gòu)，高效執(zhí)行的數(shù)據(jù)流語言等問題。

9.計(jì)算機(jī)系統(tǒng)的3T性能目標(biāo)是什么？

答：計(jì)算機(jī)系統(tǒng)的3T性能目標(biāo)是1TFLOPS計(jì)算能力，1TBYTE主存容量第二章數(shù)據(jù)表示與指令系統(tǒng)

1.數(shù)據(jù)結(jié)構(gòu)和機(jī)器的數(shù)據(jù)表示之間是什么關(guān)系？確定和引入數(shù)據(jù)表示的基本原則是什么？

答：數(shù)據(jù)表示是能由硬件直接識(shí)別和引用的數(shù)據(jù)類型。數(shù)據(jù)結(jié)構(gòu)反映各種數(shù)據(jù)元素或信息單元之間的結(jié)構(gòu)關(guān)系。

數(shù)據(jù)結(jié)構(gòu)要通過軟件映象變換成機(jī)器所具有的各種數(shù)據(jù)表示實(shí)現(xiàn)，所以數(shù)據(jù)表示是數(shù)據(jù)結(jié)構(gòu)的組成元素。不同的數(shù)據(jù)表示可為數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)提供不同的支持，表現(xiàn)在實(shí)現(xiàn)效率和方便性不同。數(shù)據(jù)表示和數(shù)據(jù)結(jié)構(gòu)是軟件、硬件的交界面。

除基本數(shù)據(jù)表示不可少外，高級(jí)數(shù)據(jù)表示的引入遵循以下原則：

（1）看系統(tǒng)的效率有否提高，是否養(yǎng)活了實(shí)現(xiàn)時(shí)間和存儲(chǔ)空間。

（2）看引入這種數(shù)據(jù)表示后，其通用性和利用率是否高。

2.標(biāo)志符數(shù)據(jù)表示與描述符數(shù)據(jù)表示有何區(qū)別？描述符數(shù)據(jù)表示與向量數(shù)據(jù)表示對(duì)向量數(shù)據(jù)結(jié)構(gòu)所提供的支持有什么不同？

答：標(biāo)志符數(shù)據(jù)表示與描述符數(shù)據(jù)表示的差別是標(biāo)志符與每個(gè)數(shù)據(jù)相連，合存于同一存儲(chǔ)單元，描述單個(gè)數(shù)據(jù)的類型特性;描述符是與數(shù)據(jù)分開存放，用于描述向量、數(shù)組等成塊數(shù)據(jù)的特征。

描述符數(shù)據(jù)表示為向量、數(shù)組的的實(shí)現(xiàn)提供了支持，有利于簡化高級(jí)語言程序編譯中的代碼生成，可以比變址法更快地形成數(shù)據(jù)元素的地址。但描述符數(shù)據(jù)表示并不支持向量、數(shù)組數(shù)據(jù)結(jié)構(gòu)的高效實(shí)現(xiàn)。而在有向量、數(shù)組數(shù)據(jù)表示的向量處理機(jī)上，硬件上設(shè)置有豐富的賂量或陣列運(yùn)算指令，配有流水或陣列方式處理的高速運(yùn)算器，不僅能快速形成向量、數(shù)組的元素地址，更重要的是便于實(shí)現(xiàn)把向量各元素成塊預(yù)取到中央處理機(jī)，用一條向量、數(shù)組指令流水或同時(shí)對(duì)整個(gè)向量、數(shù)組高速處理．如讓硬件越界判斷與元素運(yùn)算并行。這些比起用與向量、陣列無關(guān)的機(jī)器語言和數(shù)據(jù)表示串行實(shí)現(xiàn)要高效的多。

3.堆棧型機(jī)器與通用寄存器型機(jī)器的主要區(qū)別是什么？堆棧型機(jī)器系統(tǒng)結(jié)構(gòu)為程序調(diào)用哪些操作提供了支持？

答：通用寄存器型機(jī)器對(duì)堆棧數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的支持是較差的。表現(xiàn)在：(1)堆棧操作的指令少，功能單一；(2)堆棧在存儲(chǔ)器內(nèi)，訪問堆棧速度低；(3)堆棧通常只用于保存于程序調(diào)用時(shí)的返回地址，少量用堆棧實(shí)現(xiàn)程序間的參數(shù)傳遞。

而堆棧型機(jī)器則不同，表現(xiàn)在：(1)有高速寄存器組成的硬件堆棧，并與主存中堆棧區(qū)在邏輯上組成整體，使堆棧的訪問速度是寄存器的，容量是主存的；(2)豐富的堆棧指令可對(duì)堆棧中的數(shù)據(jù)進(jìn)行各種運(yùn)算和處理；(3)有力地支持高級(jí)語言的編譯；(4)有力地支持子程序的嵌套和遞歸調(diào)用。

堆棧型機(jī)器系統(tǒng)結(jié)構(gòu)有力地支持子程序的嵌套和遞歸調(diào)用。在程序調(diào)用時(shí)將返回地址、條件碼、關(guān)鍵寄存器的內(nèi)容等全部壓入堆棧，待子程序返回時(shí)，再從堆棧中彈出。

4.設(shè)某機(jī)階值6位、尾數(shù)48位，階符和數(shù)符不在其內(nèi)，當(dāng)尾數(shù)分別以2、8、16為基時(shí)，在非負(fù)階、正尾數(shù)、規(guī)格化數(shù)情況下，求出其最小階、最大階、階的個(gè)數(shù)、最小尾數(shù)值、最大尾數(shù)值、可表示的最小值和最大值及可表示的規(guī)格化數(shù)的總個(gè)數(shù)。

解：依題意知：p=6m=48rm=2,8,16，m'=m/log2(rm)，列下表：p=6,m=48,rm=2(m'=48)p=6,m=48,rm=8(m'=16)p=6,m=48,rm=16(m'=12)最小階(非負(fù)階，最小為0)000最大階(2^p-1)2^6-12^6-12^6-1最小尾數(shù)值(rm^(-1))1/21/81/16最大尾數(shù)值(1-rm^(-m'))1-2^(-48)1-8^(-16)，即(1-2^(-48))1-16^(-12)，即(1-2^(-48))可表示的最小值1/21/81/16可表示的最大值2^63*(1-2^(-48))8^63*(1-8^(-16))16^63*(1-16^(-12))階的個(gè)數(shù)(2^p)2^62^62^6可表示的尾數(shù)的個(gè)數(shù)2^48*(2-1)/28^16*(8-1)/816^12*(16-1)/16可表示的規(guī)格化數(shù)的個(gè)數(shù)2^6*2^48*(2-1)/22^6*8^16*(8-1)/82^6*16^12*(16-1)/16note:

可表示的最小值=rm^(最小階)*最小尾數(shù)值=rm^0*rm^(-1)=rm^(-1);

可表示的最大值=rm^(最大階)*最大尾數(shù)值=rm^(2^p-1)*(1-rm^(-m'));

可表示的尾數(shù)的個(gè)數(shù)=rm^m'*(rm-1)/rm;

可表示的規(guī)格化數(shù)的個(gè)數(shù)=階的個(gè)數(shù)*尾數(shù)的個(gè)數(shù)=2^p*rm^m'*(rm-1)/rm。

5.（1）浮點(diǎn)數(shù)系統(tǒng)使用的階基rp=2,階值位數(shù)p=2,尾數(shù)基值rm=10，以rm為基的尾數(shù)位數(shù)m''=1,按照使用的倍數(shù)來說，等價(jià)于m=4,試計(jì)算在非負(fù)階、正尾數(shù)、規(guī)格化情況下的最小尾數(shù)值、最大尾數(shù)值、最大階值、可表示的最小值和最大值及可表示數(shù)的個(gè)數(shù)。

（2）對(duì)于rp=2,p=2,rm=4,m'=2,重復(fù)以上計(jì)算。

解：依題意列下表：p=2,rm=10,m'=1p=2,rm=4,m'=2最小尾數(shù)值10^-1=0.14^-1=0.25最大尾數(shù)值1-10^-1=0.91-4^-2=15/16最大階值2p^-1=33可表示的最小值0.10.25可表示的最大值10^3*0.9=9004^3*15/16=60可表示數(shù)的個(gè)數(shù)3648

題中“按照使用的倍數(shù)來說，等價(jià)于m=4,”這個(gè)m=4,因?yàn)?^3<10<2^4,等價(jià)為實(shí)際要4個(gè)二進(jìn)制位，表示RM=10為基的一位

6.由4位數(shù)（其中最低位為下溢附加位）經(jīng)ROM查表舍入法，下溢處理成3位結(jié)果，設(shè)計(jì)使下溢處理平均誤差接近于零的ROM表，列出ROM編碼表地址與內(nèi)容的對(duì)應(yīng)關(guān)系。

解：ROM編碼表地址與內(nèi)容的對(duì)應(yīng)關(guān)系地址0000000100100011010001010110011110001001101010111100110111101111內(nèi)容000001001010010011011100100101101110110111111111

7.變址尋址和基址尋址各適用于何種場合？設(shè)計(jì)一種只用6位地址碼就可指向一個(gè)大地址空間中任意64個(gè)地址之一的尋址機(jī)構(gòu)。

答：基址尋址是對(duì)邏輯地址空間到物理地址空間變換的支持，以利于實(shí)現(xiàn)程序的動(dòng)態(tài)再定位。變址尋址是對(duì)數(shù)組等數(shù)據(jù)塊運(yùn)算的支持，以利于循環(huán)。將大地址空間64個(gè)地址分塊，用基址寄存器指出程序所在塊號(hào)，用指令中6位地址碼表示該塊內(nèi)64個(gè)地址之一，這樣基址和變址相結(jié)合可訪問大地址任意64個(gè)地址之一。比如地址空間很大，為0-1023，只用6位地址碼就可以指向這1024個(gè)地址中的任意64個(gè)。

剖析：比如地址空間很大，1024，就是分成16個(gè)塊，塊號(hào)放在寄存器中，塊內(nèi)地址放在地址位中，寄存器內(nèi)容和地址位結(jié)合，就能達(dá)到要求了。8.經(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。分別求出用等長碼、Huffman碼、只有兩種碼長的擴(kuò)展操作碼3種編碼方式的操作碼平均碼長。

解：等長操作碼的平均碼長=4位;Huffman編碼的平均碼長=3.38位;只有兩種碼長的擴(kuò)展操作碼的平均碼長=3.4位。

9.若某機(jī)要求：三地址指令4條，單地址指令255條，零地址指令16條。設(shè)指令字長為12位．每個(gè)地址碼長為3位。問能否以擴(kuò)展操作碼為其編碼?如果其中單地址指令為254條呢?說明其理由。

答：①不能用擴(kuò)展碼為其編碼。

∵指令字長12位，每個(gè)地址碼占3位；

∴三地址指令最多是2^(12-3-3-3)=8條，現(xiàn)三地址指令需4條,

∴可有4條編碼作為擴(kuò)展碼，

∴單地址指令最多為4×2^3×2^3=2^8=256條，

現(xiàn)要求單地址指令255條，∴可有一條編碼作擴(kuò)展碼

∴零地址指令最多為1×2^3＝8條

不滿足題目要求

∴不可能以擴(kuò)展碼為其編碼。

②若單地址指令254條，可以用擴(kuò)展碼為其編碼。

∵依據(jù)①中推導(dǎo)，單地址指令中可用2條編碼作為擴(kuò)展碼

∴零地址指令為2×2^3＝16條，滿足題目要求

note:三地址指令格式：操作碼地址碼地址碼地址碼3位3位3位3位單地址指令格式：操作碼地址碼9位3位

所以前面9位由于三地址指令用了最前面3位，還有中間6位可作為編碼（也就是總共可以有9位作為單地址指令的指令操作碼的編碼）。減去3地址指令的4條，有4*2^6=256條，但由于韙目要求要有255條，所以剩下一個(gè)編碼，已經(jīng)用了9位的全部編碼，最后零地址指令（全部12位都可作為操作碼的編碼）還有1*2^3=8(這是12位編碼中最后三位的）若只要求254種，則可以有（256-254）*2^3=16條

10.某機(jī)指令字長16位。設(shè)有單地址指令和雙地址指令兩類。若每個(gè)地址字段為6位.且雙地址指令有X條。問單地址指令最多可以有多少條?

答：

單地址指令最多為(16-X)×2^6

P.S.雙地址指令最多是2^(16-6-6)=2^4=16條，現(xiàn)雙地址指令有X條,

∴可有(16-X)條編碼作為擴(kuò)展碼，

∴單地址指令最多為(16-X)×2^6=256條

11.何謂指令格式的優(yōu)化?簡要列舉包括操作碼和地址碼兩部分的指令格式優(yōu)化可采用的各種途徑和思路。

答：指令格式的優(yōu)化指如何用最短位數(shù)表示指令的操作信息和地址信息，使程序中指令的平均字長最短。

①操作碼的優(yōu)化

采用Huffman編碼和擴(kuò)展操作碼編碼。

②對(duì)地址碼的優(yōu)化：

采用多種尋址方式;

采用0、1、2、3等多種地址制;

在同種地址制內(nèi)再采用多種地址形式，如寄存器-寄存器型、寄存器-主存型、主存-主存型等;

在維持指令字在存儲(chǔ)器內(nèi)按整數(shù)邊界存儲(chǔ)的前提下，使用多種不同的指令字長度。

12.某模型機(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%要求有兩種指令字長，都按雙操作數(shù)指令格式編排，采用擴(kuò)展操作碼，并限制只能有兩種操作碼碼長。設(shè)該機(jī)有若干通用寄存器，主存為16位寬，按字節(jié)編址，采用按整數(shù)邊界存儲(chǔ)。任何指令都在一個(gè)主存周期中取得，短指令為寄存器-寄存器型，長指令為寄存器-主存型，主存地址應(yīng)能變址尋址。

(1)僅根據(jù)使用頻率，不考慮其它要求，設(shè)計(jì)出全Huffman操作碼，計(jì)算其平均碼長;

(2)考慮題目全部要求，設(shè)計(jì)優(yōu)化實(shí)用的操作形式，并計(jì)算其操作碼的平均碼長;

(3)該機(jī)允許使用多少可編址的通用寄存器？

(4)畫出該機(jī)兩種指令字格式，標(biāo)出各字段之位數(shù);

(5)指出訪存操作數(shù)地址尋址的最大相對(duì)位移量為多少個(gè)字節(jié)？

解：

第(1)和(2)中Huffman和擴(kuò)展操作碼的編碼及平均碼長如下表：指令I(lǐng)i使用頻度PiHuffman編碼擴(kuò)展操作碼編碼I1

I2

I3

I4

I5

I6

I7

I8

I930%

24%

20%

7%

7%

6%

3%

2%

1%10

00

01

1100

1101

1110

11110

111110

11111100

01

10

11000

11001

11010

11011

11100

11101西個(gè)馬pili2.612.78

(3)8個(gè)。

(4)兩種指令格式如下圖所示：2位3位3位OPR1R2操作碼寄存器1寄存器25位3位3位5位OPR1Xd操作碼寄存器1變址寄存器相對(duì)位移主存邏輯地址(5)訪存操作數(shù)地址尋址的最大相對(duì)位移量為32個(gè)字節(jié)。

13.設(shè)計(jì)RISC機(jī)器的一般原則及可采用的基本技術(shù)有那些?

答：一般原則：

(1)確定指令系統(tǒng)時(shí)，只選擇使用頻度很高的指令及少量有效支持操作系統(tǒng)，高級(jí)語言及其它功能的指令；

(2)減少尋址方式種類，一般不超過兩種；

(3)讓所有指令在一個(gè)機(jī)器周期內(nèi)完成；

(4)擴(kuò)大通用寄存器個(gè)數(shù)，一般不少于32個(gè)，盡量減少訪存次數(shù)；

(5)大多數(shù)指令用硬聯(lián)實(shí)現(xiàn)，少數(shù)用微程序?qū)崿F(xiàn)；

(6)優(yōu)化編譯程序，簡單有效地支持高級(jí)語言實(shí)現(xiàn)。

基本技術(shù)：

(1)按RISC一般原則設(shè)計(jì)，即確定指令系統(tǒng)時(shí)，選最常用基本指令，附以少數(shù)對(duì)操作系統(tǒng)等支持最有用的指令，使指令精簡。編碼規(guī)整，尋址方式種類減少到1、2種。

(2)邏輯實(shí)現(xiàn)用硬聯(lián)和微程序相結(jié)合。即大多數(shù)簡單指令用硬聯(lián)方式實(shí)現(xiàn)，功能復(fù)雜的指令用微程序?qū)崿F(xiàn)。

(3)用重疊寄存器窗口。即：為了減少訪存，減化尋址方式和指令格式，簡單有效地支持高級(jí)語言中的過程調(diào)用，在RISC機(jī)器中設(shè)有大量寄存囂，井讓各過程的寄存器窗口部分重疊。

(4)用流水和延遲轉(zhuǎn)移實(shí)現(xiàn)指令，即可讓本條指令執(zhí)行與下條指令預(yù)取在時(shí)間上重疊。另外，將轉(zhuǎn)移指令與其前面的一條指令對(duì)換位置，讓成功轉(zhuǎn)移總是在緊跟的指令執(zhí)行之后發(fā)生，使預(yù)取指令不作廢，節(jié)省一個(gè)機(jī)器周期。

(5)優(yōu)化設(shè)計(jì)編譯系統(tǒng)。即盡力優(yōu)化寄存器分配，減少訪存次數(shù)。不僅要利用常規(guī)手段優(yōu)化編譯，還可調(diào)整指令執(zhí)行順序，以盡量減少機(jī)器周期等。

14.簡要比較CISC機(jī)器和RISC機(jī)器各自的結(jié)構(gòu)特點(diǎn)，它們分別存在哪些不足和問題?為什么說今后的發(fā)展應(yīng)是CISC和RISC的結(jié)合?

答：CISC結(jié)構(gòu)特點(diǎn)：機(jī)器指令系統(tǒng)龐大復(fù)雜。

RISC結(jié)構(gòu)特點(diǎn)：機(jī)器指令系統(tǒng)簡單，規(guī)模小，復(fù)雜度低。

CISC的問題：

(1)指令系統(tǒng)龐大，一般200條以上；

(2)指令操作繁雜，執(zhí)行速度很低；

(3)難以優(yōu)化生成高效機(jī)器語言程序，編譯也太長，太復(fù)雜；

(4)由于指令系統(tǒng)龐大，指令的使用頻度不高，降低系統(tǒng)性能價(jià)格比，增加設(shè)計(jì)人員負(fù)擔(dān)。

RISC的問題；

(1)由于指令少，在原CISC上一條指令完成的功能現(xiàn)在需多條RISC指令才能完成，加重匯編語言程序設(shè)計(jì)負(fù)擔(dān)，增加了機(jī)器語言程序長度，加大指令信息流量。

(2)對(duì)浮點(diǎn)運(yùn)算和虛擬存儲(chǔ)支持不很強(qiáng)。

(3)RISC編譯程序比CISC難寫。

由于RISC和CISC各有優(yōu)缺點(diǎn),在設(shè)計(jì)時(shí)，應(yīng)向著兩者結(jié)合，取長補(bǔ)短方向發(fā)展。第三章總線、中斷與輸入輸出系統(tǒng)

1.簡要舉出集中式串行鏈接，定時(shí)查詢和獨(dú)立請(qǐng)求3種總線控制方式的優(yōu)缺點(diǎn)。同時(shí)分析硬件產(chǎn)生故障時(shí)通訊的可靠性。

答：控制方式優(yōu)點(diǎn)缺點(diǎn)串行鏈接(1)選擇算法簡單。

(2)控制線數(shù)少，只需要3根，且不取決于部件數(shù)量。

(3)可擴(kuò)充性好。(1)對(duì)“總線可用”線及其有關(guān)電路失效敏感。

(2)靈活性差，如果高優(yōu)先級(jí)的部件頻繁要求使用總線，離總線控制器遠(yuǎn)的部件就難以獲得總線使用權(quán)。

(3)“總線可用”信號(hào)順序脈動(dòng)地通過各個(gè)部件，總線的分配速度慢。

(4)受總線長度的限制，增減和移動(dòng)部件受限制。定時(shí)查詢(1)靈活性強(qiáng)，部件的優(yōu)先次序由程序控制。

(2)可靠性高，不會(huì)因某個(gè)部件失效而影響其它部件使用總線。(1)總線的分配速度不能很高。

(2)控制較為復(fù)雜。

(3)控制線數(shù)多，需要2+log2N根。

(4)可擴(kuò)充性差。獨(dú)立請(qǐng)求(1)靈活性強(qiáng)，部件的優(yōu)先次序由程序控制。

(2)能方便地隔離失效部件的請(qǐng)求。

(3)總線的分配速度快。(1)控制較為復(fù)雜。

(2)控制線數(shù)多，要控制N個(gè)設(shè)備，需要有2N+1根控制線。2.設(shè)中斷級(jí)屏蔽位“1”對(duì)應(yīng)于開放，“0”中斷處理程序級(jí)別中斷級(jí)屏蔽位1級(jí)2級(jí)3級(jí)4級(jí)第1級(jí)0000第2級(jí)1010第3級(jí)1000第4級(jí)1010

(1)當(dāng)中斷響應(yīng)優(yōu)先次序?yàn)?→2→3→4時(shí)，其中斷處理次序是什么?

(2)如果所有的中斷處理都各需3個(gè)單位時(shí)間，中斷響應(yīng)和中斷返回時(shí)間相對(duì)中斷處理時(shí)間少得多。當(dāng)機(jī)器正在運(yùn)行用戶程序時(shí)，同時(shí)發(fā)生第2，3級(jí)中斷請(qǐng)求，過兩個(gè)單位時(shí)間，又同時(shí)發(fā)生第1，4級(jí)中斷請(qǐng)求，試畫出程序運(yùn)行過程示意圖。

答：

(1)當(dāng)中斷響應(yīng)優(yōu)先次序?yàn)?→2→3→4時(shí)，其中斷處理次序?yàn)?→3→4→2。

(2)

3.若機(jī)器共有5級(jí)中斷,中斷響應(yīng)優(yōu)先次序?yàn)?→2→3→4→5,要求其實(shí)際的中斷處理次求序1→4→5→2→3。

(1)設(shè)計(jì)各級(jí)中斷處理程序的中斷級(jí)屏蔽位(令“1”對(duì)應(yīng)于開放，“0”對(duì)應(yīng)于屏蔽);

(2)若在運(yùn)行用戶程序時(shí)，同時(shí)出現(xiàn)第4，2級(jí)中斷請(qǐng)求，而在處理第2級(jí)中斷未完成時(shí)，又同時(shí)出現(xiàn)第1，3，5級(jí)中斷請(qǐng)求，請(qǐng)畫出此程序運(yùn)行過程示意圖。

答：

(1)中斷級(jí)屏蔽位設(shè)置如下圖：中斷處理程序級(jí)別中斷級(jí)屏蔽位1級(jí)2級(jí)3級(jí)4級(jí)5級(jí)第1級(jí)11111第2級(jí)01100第3級(jí)00100第4級(jí)01111第5級(jí)01101

(2)中斷過程示意圖：如圖

2、4中斷同時(shí)出現(xiàn)，進(jìn)行排隊(duì)器。

首先響應(yīng)第2級(jí)中斷請(qǐng)求，屏蔽字為01100，表明其對(duì)第4級(jí)中斷請(qǐng)求開放，所以轉(zhuǎn)去響應(yīng)第4級(jí)中斷請(qǐng)求并進(jìn)行處理。

響應(yīng)4，中斷4運(yùn)行結(jié)束，回2。

1、3、5進(jìn)入排隊(duì)器。

第2級(jí)中斷請(qǐng)求的處理請(qǐng)求被中斷，轉(zhuǎn)去響應(yīng)第1級(jí)中斷請(qǐng)求并進(jìn)行處理。

響應(yīng)第5級(jí)中斷請(qǐng)求并進(jìn)行處理。

繼續(xù)響應(yīng)并處理第2級(jí)中斷處理請(qǐng)求，結(jié)束后返回用戶程序。

最后處理第3級(jí)中斷請(qǐng)求。

4.簡述字節(jié)多路，數(shù)組多路和選擇通道的數(shù)據(jù)傳送方式。

答:

字節(jié)多路通道適用于連接大量的像光電機(jī)等字符類低速設(shè)備。這些設(shè)備傳送一個(gè)字符(字節(jié))的時(shí)間很短，但字符(字節(jié))間的等待時(shí)間很長。通道“數(shù)據(jù)寬度”為單字節(jié)，以字節(jié)交叉方式輪流為多臺(tái)設(shè)備服務(wù)，使效率提高。字節(jié)多路通道可有多個(gè)子通道，同時(shí)執(zhí)行多個(gè)通道程序。

數(shù)組多路通道適合于連接多臺(tái)象磁盤等高速設(shè)備。這些設(shè)備的傳送速率很高，但傳送開始前的尋址輔助操作時(shí)間很長。通道“數(shù)據(jù)寬度”為定長塊，多臺(tái)設(shè)備以成組交叉方式工作，以充分利用并盡可能重疊各臺(tái)高速設(shè)備的輔助操作時(shí)間。傳送完K個(gè)字節(jié)數(shù)據(jù)，就重新選擇下個(gè)設(shè)備。數(shù)組多路通道可有多個(gè)子通道，同時(shí)執(zhí)行多個(gè)通道程序。

選擇通道適合于連接象磁盤等優(yōu)先級(jí)高的高速設(shè)備，讓它獨(dú)占通道，只能執(zhí)行一道通道程序。通道“數(shù)據(jù)寬度”為可變長塊，一次將N個(gè)字節(jié)全部傳送完，在數(shù)據(jù)傳送期只選擇一次設(shè)備。

5.如果通道在數(shù)據(jù)傳送期中，選擇設(shè)備需9.8μs，傳送一個(gè)字節(jié)數(shù)據(jù)需0.2μs。某低速設(shè)備每隔500μs發(fā)出一個(gè)字節(jié)數(shù)據(jù)傳送請(qǐng)求，問至多可接幾臺(tái)這種低速設(shè)備?對(duì)于如下A～F6種高速設(shè)備，一次通訊傳送的字節(jié)數(shù)不少于1024個(gè)字節(jié)，問哪些設(shè)備可以掛在此通道上?哪些則不能?其中A—F設(shè)備每發(fā)出一個(gè)字節(jié)數(shù)據(jù)傳送請(qǐng)求的時(shí)間間隔分別為(單位為μs)：

表3-5設(shè)備ABCDEF發(fā)申請(qǐng)間隔(μs)0.20.250.50.190.40.21

答:

(1)至多可連接50臺(tái)低速的外設(shè)。

剖析：

根據(jù)題意可知：低速設(shè)備應(yīng)掛接在字節(jié)多路通道上，字節(jié)多路通道的通道極限流量為：

fmax.byte=1/(TS+TD)>=fbyte

通道極限流量應(yīng)大于或等于設(shè)備對(duì)通道要求的流量fbyte。

如果字節(jié)多路通道上所掛設(shè)備臺(tái)數(shù)為m,設(shè)備的速率為fi，為了不丟失信息，應(yīng)滿足：

1/(TS+TD)>=m*fi

fi也就是設(shè)備發(fā)出字節(jié)傳送請(qǐng)求間隔時(shí)間(500μs)的倒數(shù)，所以：

m<=1/((TS+TD)*f)=500/(9.8+0.2)=50(臺(tái))

(2)設(shè)備B,C,E,F可以掛在此通道上，設(shè)備A,D則不能。

剖析：

思路一：從傳送字節(jié)速率上入手。

A~F是高速設(shè)備，應(yīng)掛接在選擇通道上，選擇通道的極限流量為：

fmax.select=N/(TS+N*TD)=1/((TS/N)+TD)=1/((9.8/1024)+0.2)=1/0.21(約)

通道上所掛設(shè)備的最大速率fi.max應(yīng)小于或等于通道的極限流量。

由表3-5可得出設(shè)備ABCDEF傳送速率(B/μs)1/0.21/0.251/0.51/0.191/0.41/0.21

所以，B、C、E、F可掛在該通道上。A、D不能。

思路二：從傳送字節(jié)時(shí)間上入手。

對(duì)于高速設(shè)備，由于一次傳送字節(jié)數(shù)不少于1024byte

∴該通道一次傳送數(shù)據(jù)的時(shí)間為9.8μs+1024×0.2μs＝214.6μs

由表3-5可得出每臺(tái)設(shè)備發(fā)送1024字節(jié)的時(shí)間間隔分別為:設(shè)備ABCDEF傳送時(shí)間(μs)204.8256512194.56409.6215.04

∴為使數(shù)據(jù)不丟失，B、C、E、F可掛在該通道上。A、D不能。

6.某字節(jié)多路通道連接6臺(tái)外設(shè)，某數(shù)據(jù)傳送速率分別如表中所列。設(shè)備123456傳送速率(KB/s)5015100254020

(1)計(jì)算所有設(shè)備都工作時(shí)的通道實(shí)際最大流量：

(2)如果設(shè)計(jì)的通道工作周期使通道極限流量恰好與通道最大流量相等，以滿足流量設(shè)計(jì)的基本要求，同時(shí)讓速率越高的設(shè)備被響應(yīng)的優(yōu)先級(jí)越高。當(dāng)6臺(tái)設(shè)備同時(shí)發(fā)出請(qǐng)求開始，畫出此通道在數(shù)據(jù)傳送期內(nèi)響應(yīng)和處理各外設(shè)請(qǐng)求的時(shí)間示意圖。由此你發(fā)現(xiàn)了什么問題?

(3)在(2)的基礎(chǔ)上，在哪臺(tái)設(shè)備內(nèi)設(shè)置多少個(gè)字節(jié)的緩沖器就可以避免設(shè)備信息丟失?那么，這是否說書中關(guān)于流量設(shè)計(jì)的基本要求是沒有必要的了呢?為什么?

解：

(1)實(shí)際最大流量＝50+15+l00+25+40+20＝250KB/S。

(2)通道響應(yīng)和處理各設(shè)備請(qǐng)求的時(shí)間示意圖

由此發(fā)現(xiàn)由于高速設(shè)備的響應(yīng)優(yōu)先級(jí)高，使低速設(shè)備2造成數(shù)據(jù)丟失。

(3)在2中各設(shè)兩個(gè)字節(jié)的緩沖區(qū)即可。這并不說明流量設(shè)計(jì)的基本條件是不必要的，因?yàn)槿艋緱l件不滿足，無論設(shè)備優(yōu)先級(jí)如何確定總有設(shè)備的信息會(huì)丟失。

剖析：

(2)由各設(shè)備的傳送字節(jié)速率可解其連續(xù)發(fā)出傳送請(qǐng)求的時(shí)間間隔分別為：設(shè)備123456發(fā)申請(qǐng)間隔(μs)2067(約)10402550

7.通道型I/O系統(tǒng)由一個(gè)字節(jié)多路通道A(其中包括兩個(gè)子通道Al和A2)，兩個(gè)數(shù)組多路通道B1和B2及一個(gè)選擇通道C構(gòu)成，各通道所接設(shè)備和設(shè)備的數(shù)據(jù)傳送速率如表所示。

(1)分別求出各通道應(yīng)具有多大設(shè)計(jì)流量才不會(huì)丟失信息；

(2)設(shè)I/O系統(tǒng)流量占主存流量的1/2時(shí)才算流量平衡，則主存流量應(yīng)達(dá)到多少?通道號(hào)所接設(shè)備的數(shù)據(jù)傳送速率(KB/s)字節(jié)多路通道子通道A15035202050352020子通道A25035202050352020數(shù)組多路通道B1500400350250數(shù)組多路通道B2500400350250選擇通道C500400350250

解：

(1)要不丟失信息，各通道需要達(dá)到的流量：字節(jié)多路通道子通道A1:0.25KB/S;字節(jié)多路通道子通道A2:0.25KB/S;數(shù)組多路通道B1:500KB/s;數(shù)組多路通道B2:500KB/s;選擇通道C:500KB/s。

(2)主存流量應(yīng)達(dá)到4MB/S。

剖析:

(1)設(shè)備要求字節(jié)多路通道或其子通道的實(shí)際最大流量，是該通道所接各設(shè)備的字節(jié)傳送速率之和;

設(shè)備要求數(shù)組多路通道或選擇通道的實(shí)際最大流量，是該通道所接各設(shè)備的字節(jié)傳送速率中的最大者。

(2)I/O系統(tǒng)中，各種通道和子通道可以并行工作，因此，I/O系統(tǒng)的最大流量應(yīng)等于各通道最大流量之和。第四章存儲(chǔ)體系1.設(shè)二級(jí)虛擬存儲(chǔ)器的TA1=10-7s、TA2=10-2s,為使存儲(chǔ)層次的訪問效率e達(dá)到最大值的80%以上，命中率H至少要求達(dá)到多少？實(shí)際上這樣高的命中率是很難達(dá)到的，那么從存儲(chǔ)層次上如何改進(jìn)？

解：e=TA1/TA=TA1/(H*TA1+(1-H)*TA2)≥80%，H≥(10^5-5/4)/(10^5-1)。

這樣的命中率很難達(dá)到。為了降低對(duì)H的要求，可以選擇高命中率的算法，可以減少相鄰兩級(jí)的訪問速度差和容量差(這樣做不利于降低存儲(chǔ)器的平均每位價(jià)格)，可在主、輔存儲(chǔ)器間加一層電子磁盤，使存儲(chǔ)體系中相鄰兩級(jí)的訪問時(shí)間比不太大。

2、程序存放在模32單字交叉存儲(chǔ)器中，設(shè)訪存申請(qǐng)隊(duì)的轉(zhuǎn)移概率λ為25%,求每個(gè)存儲(chǔ)周期能訪問到的平均字?jǐn)?shù)。當(dāng)模數(shù)為16呢？由此你可得到什么結(jié)論？解：B=[1-(1-λ)^m]/λ

解：

由λ=0.25,m=32求得：B=4-4*(3/4)^32

同理，m=16時(shí),B=4-4*(3/4)^16

可得出，在λ=0.25時(shí)，m=32的平均訪問字?jǐn)?shù)大于m=16時(shí)的平均訪問字?jǐn)?shù)。

3、設(shè)主存每個(gè)分體的存取周期為2μs，寬度為4個(gè)字節(jié)。采用模m多分體交叉存取，但實(shí)際頻寬只能達(dá)到最大頻寬的0.6倍。現(xiàn)要求主存實(shí)際頻寬為4MB/S,問主存模數(shù)m應(yīng)取多少方能使兩者速度基本適配？其中m取2的冪。

解：

m=4

剖析：

根據(jù)題意，模m多分體交叉的最大頻寬為：分體數(shù)*單體頻寬=m*分體的寬度/分體的存取周期=m*4B/2μs，所以有0.6*m*4/2>=4。

4.某虛擬存儲(chǔ)器共8個(gè)頁面，每頁1024個(gè)字，實(shí)際主存為4096個(gè)字，采用頁表法進(jìn)行地址映象。映象表的內(nèi)容如下表所示。虛頁號(hào)01234567實(shí)頁號(hào)31232100裝入位11001010注：我把虛頁號(hào)加上了。

(1)列出會(huì)發(fā)生頁面失效的全部虛頁號(hào)；

(2)按以下虛地址計(jì)算主存實(shí)地址：0，3728，1023，1024，2055，7800，4096，6800。

解:

(1)會(huì)發(fā)生頁面失效的全部虛頁號(hào)為：2,3,5,7。

(2)虛地址虛頁號(hào)頁內(nèi)位移裝入位實(shí)頁號(hào)頁內(nèi)位移實(shí)地址0001303072327836560頁面失效頁面失效無102301023131023409510241011010242055270頁面失效頁面失效無780076320頁面失效頁面失效無40964012020486800665610656656

剖析：

(1)根據(jù)頁表法列出表2，當(dāng)裝入位為0時(shí)，即為頁面失效，再找出相對(duì)應(yīng)的虛頁號(hào)即可。

(2)虛頁號(hào)=虛地址/頁面大小

頁內(nèi)位移量=虛地址－虛頁號(hào)*頁面大小

實(shí)地址＝實(shí)頁號(hào)*頁面大?。搩?nèi)位移量

由于可以用替換算法解決頁面失效的問題，所以，發(fā)生頁面失效的虛頁2,3,5,7仍然可以有相應(yīng)的實(shí)地址，但這樣要在頁表中建立新的虛實(shí)地址對(duì)應(yīng)關(guān)系，新的虛實(shí)地址對(duì)應(yīng)關(guān)系和原來的對(duì)應(yīng)關(guān)系相同的可能性就很小了。

5、一個(gè)段頁式虛擬存儲(chǔ)器。虛地址有2位段號(hào)、2位頁號(hào)、11位頁內(nèi)位移（按字編址），主存容量為32K字。每段可有訪問方式保護(hù)，其頁表和保護(hù)位如下表所示。段號(hào)0123訪問方式只讀可讀/執(zhí)行可讀/寫/執(zhí)行可讀/寫虛頁0所在位置實(shí)頁9在輔存上頁表不在主存內(nèi)實(shí)頁14虛頁1所在位置實(shí)頁3實(shí)頁0頁表不在主存內(nèi)實(shí)頁1虛頁2所在位置在輔存上實(shí)頁15頁表不在主存內(nèi)實(shí)頁6虛頁3所在位置實(shí)頁12實(shí)頁8頁表不在主存內(nèi)在輔存上(1)此地址空間中共有多少個(gè)虛頁？

(2)當(dāng)程序中遇到下列情況時(shí)方式段頁頁內(nèi)位移取數(shù)

取數(shù)

取數(shù)

存數(shù)

存數(shù)

存數(shù)

轉(zhuǎn)移至此

取數(shù)

取數(shù)

轉(zhuǎn)移至此0

1

3

0

2

1

1

0

2

31

1

3

1

1

0

3

2

0

01

10

2047

4

2

14

100

50

5

60寫出由虛地址計(jì)算出實(shí)地址。說明哪個(gè)會(huì)發(fā)生段失效、頁面或保護(hù)失效失效。

解答:(1)該地址空間中共有16個(gè)虛頁。

(2)程序中遇到上表中各情況時(shí)，是否會(huì)發(fā)生段失效、頁失效或保護(hù)失效及相應(yīng)的主存實(shí)地址的情況如下表所示：方式段頁頁內(nèi)位移段失效頁失效實(shí)頁號(hào)實(shí)地址保護(hù)失效取數(shù)

取數(shù)

取數(shù)

存數(shù)

存數(shù)

存數(shù)

轉(zhuǎn)移至此

取數(shù)

取數(shù)

轉(zhuǎn)移至此0

1

3

0

2

1

1

0

2

31

1

3

1

1

0

3

2

0

01

10

2047

4

2

14

100

50

5

60無

無

無

無

有

無

無

無

有

無無

無

有

無

/

有

無

有

/

無3

0

無

3

無

無

8

無

無

146145

10

無

6184

無

無

16484

無

無

28732無

無

/

有

/

/

無

/

/

有剖析：

(1)虛地址中段號(hào)有2位，頁號(hào)有2位，也就是每個(gè)程序最多只能有2^2=4個(gè)段，每個(gè)段至多只能有2^2=4頁，所以該地址空間中共有4*4=16個(gè)虛頁。

(2)先從題意得知：

實(shí)地址：15位，其中實(shí)頁號(hào)4位，頁內(nèi)位移11位

頁大小為2K字（由頁內(nèi)位移得知）

6.設(shè)某程序包含5個(gè)虛頁，其頁地址為4，5，3，2，5，1，3，2，2，5，1，3。當(dāng)使用LRU算法替換時(shí)，為獲得最高命中率，至少應(yīng)分配給該程序幾個(gè)實(shí)頁？其可能的最高命中率為多少？

7.采用頁式管理的虛擬存儲(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,+2,0)C=(-3,0,+1)每個(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í)頁最為合適？為什么？

解答：

分別分配給程序X和Y的數(shù)組4個(gè)實(shí)頁最為合適。

根據(jù)題意，程序X依次調(diào)用數(shù)組A,C,B,B,E,A,C,B,B,C,A,D,D,E,A,C,B,B,E中的數(shù)據(jù)。

設(shè)程序X中的數(shù)組A,B,C,D,E分別存放于程序空間的第1,2,3,4,5頁，則程序的頁地址流為：1，3，2，2，5，1，3，2，2，3，1，4，4，5，1，3，2，2，5。

分析使用LRU算法對(duì)程序X的頁地址流進(jìn)行堆棧處理的過程可知，分配給程序X的數(shù)組5個(gè)實(shí)頁最為合適;分析使用LRU算法對(duì)程序Y的頁地址流進(jìn)行堆棧處理的過程可知，分配給程序Y的數(shù)組4個(gè)實(shí)頁最為合適。

但實(shí)存只有8頁位置可供存放數(shù)組之用，所以，分別分配給程序X和Y的數(shù)組4個(gè)實(shí)頁。

note:

分時(shí)運(yùn)行在微觀上是串行的，就是說，分時(shí)運(yùn)行時(shí)把時(shí)間劃分為若干時(shí)間片，每個(gè)程序輪流占用時(shí)間片;在宏觀上是并行的，就是說，每個(gè)程序在一個(gè)時(shí)間片內(nèi)并不能運(yùn)行完。總的來看，是同時(shí)運(yùn)行的，所以兩個(gè)程序分配的實(shí)頁和不能大于8。

我不了解FORTRAN，找朋友把上面的源代碼轉(zhuǎn)成C了：main(){intA[]={-4,2,0};intC[]={-3,0,1};for(i=0,i<>0)E[i]=0;};};}

8.設(shè)一個(gè)按位編址的虛擬存儲(chǔ)器，它應(yīng)可對(duì)應(yīng)1K個(gè)任務(wù)，但在一段較長時(shí)間內(nèi)，一般只有4個(gè)任務(wù)在使用，故用容量為4行的相聯(lián)寄存器組硬件來縮短被變換的虛地址中的用戶位位數(shù)；每個(gè)任務(wù)的程序空間最大可達(dá)4096頁，每頁為512個(gè)字節(jié)，實(shí)主存容量為2＾20位；設(shè)快表用按地址訪問存儲(chǔ)器構(gòu)成，行數(shù)為32，快表的地址是經(jīng)散列形成；為減少散列沖突，配有兩套獨(dú)立相等比較電路。請(qǐng)?jiān)O(shè)計(jì)該地址變換機(jī)構(gòu)，內(nèi)容包括：

(1)畫出其虛、實(shí)地址經(jīng)快表變換之邏輯結(jié)構(gòu)示意圖；

(2)相聯(lián)寄存器組中每個(gè)寄存器的相聯(lián)比較位數(shù)；

(3)相聯(lián)寄存器組中每個(gè)寄存器的總位數(shù)；

(4)散列變換硬件的輸入位數(shù)和輸出位數(shù)；

(5)每個(gè)相等比較器的位數(shù)；

(6)快表的總?cè)萘浚ㄒ晕粸閱挝唬?/p>

解:

(1)依題意得知：

虛地址為34位，其中用戶號(hào)為10位（對(duì)應(yīng)1K的任務(wù)）、虛頁號(hào)12位（每個(gè)任務(wù)4096頁）、頁內(nèi)位移12位（每頁512字節(jié)，512字節(jié)=512*8=1024*4=2^12）

實(shí)地址為20位，其中實(shí)頁號(hào)8位，頁內(nèi)位移12位（與虛頁頁內(nèi)位移對(duì)應(yīng)）

相聯(lián)寄存器的作用：把10位的用戶號(hào)轉(zhuǎn)換為2位的ID（因?yàn)橐话阒挥?個(gè)任務(wù)在使用），并把ID與虛地址的虛頁號(hào)合并到快表中查實(shí)頁號(hào)。

快表的作用：相當(dāng)于頁表，即虛頁號(hào)對(duì)實(shí)頁號(hào)的對(duì)應(yīng)關(guān)系。但又有所簡化（原因是如果用用戶號(hào)和虛頁號(hào)與實(shí)頁號(hào)對(duì)應(yīng)，前者就有22位，現(xiàn)改進(jìn)后虛頁號(hào)只有14位了）

(2)相聯(lián)寄存器組中每個(gè)寄存器的相聯(lián)比較位數(shù)為10（與虛地址中的用戶號(hào)寬度對(duì)應(yīng)）

(3)相聯(lián)寄存器組中每個(gè)寄存器的總數(shù)為12（用戶號(hào)寬度+ID寬度）

(4)散列變換硬件的輸入位數(shù)為14位（虛頁號(hào)寬度+相聯(lián)寄存器中ID的寬度），輸出位數(shù)為8位（與主存中的實(shí)頁號(hào)寬度對(duì)應(yīng)）

(5)每個(gè)相等比較器的位數(shù)=ID+用戶虛頁號(hào)nv'=2+12=14(位)。

(6)快表的總?cè)萘浚?2行*（14(輸入位數(shù))+8（輸出位數(shù)））*2=32*22*2

9.考慮一個(gè)920個(gè)字的程序，其訪問虛存的地址流為20，22，208，214，146，618，370，490，492，868，916，728。

(1)若頁面大小為200字，主存容量為400字，采用FIFO替換算法，請(qǐng)按訪存的各個(gè)時(shí)刻，寫出其虛頁地址流，計(jì)算主存的命中率；

(2)若頁面大小為100字，再做一遍；

(3)若頁面大小為400字，再做一遍；

(4)由(1)、(2)、(3)的結(jié)果可得出什么結(jié)論？

(5)若把主存容量增加到800字，按第(1)小題再做一遍，又可得出什么結(jié)論？

解：

(1)主存容量400字，頁面大小200字，所以主存實(shí)頁數(shù)為2；

把地址流轉(zhuǎn)換為頁地址流，以第一個(gè)虛地址流轉(zhuǎn)換為頁地址流為例說明：求模公式為：INT（地址/頁面大?。?，就是把地址整除于頁面大小，得INT（20/200）=0，下同，所以頁地址流為：0,0,1,1,0,3,1,2,2,4,4,3

按FIFO算法得出替換過程為：0（調(diào)入），0（命中），1（調(diào)入），1（命中），0（命中），3（替換0，0比1先入隊(duì)，所以被替換，下同），1（命中），2（替換1），2（命中），4（替換3），4（命中），3（替換2），所以總共命中6次。

故命中率H=6/12=50%

(2)方法同（1）H=25%

(3)H=50%

(4)由以上結(jié)論可得，F(xiàn)IFO算法的條件下，當(dāng)頁面大小發(fā)生變化時(shí)，其命中率變化是：一開始隨頁面大小增大命中率（第一步與第二步比較），但當(dāng)頁面大小增到一定時(shí)，命中率不再增加（第一步與第三步比較）。

(5)命中率為58%，結(jié)論是如果分配給主存容量增加時(shí)可以搞高命中率。

10.在一個(gè)頁式二級(jí)虛擬存儲(chǔ)器中，采用FIFO算法進(jìn)行頁面替換，發(fā)現(xiàn)命中率H太低，因此有下列建議：

(1)增大輔存容量;

(2)增大主存容量(頁數(shù));

(3)FIFO改為LRU;

(4)FIFO改為LRU，并增大主存容量(頁數(shù));

(5)FIFO改為LRU，并增大頁面大小。

試分析上述各建議對(duì)命中率的影響情況。

解答：

(1)增大輔存容量，對(duì)命中率H無影響。

(2)增大主存容量(頁數(shù))，可普遍提高命中率。

(3)FIFO改為LRU，一般可提高命中率。

(4)FIFO改為LRU，并增大主存容量(頁數(shù))，一般可使命中率有較大提高。

(5)FIFO改為LRU，并增大頁面大小，如果原來頁面很小，則會(huì)使命中率顯著上升，如果原來頁面很大，則會(huì)使命中率下降。

11.采用組相聯(lián)映象的Cache存儲(chǔ)器，Cache為1KB，要求Cache的每一塊在一個(gè)主存周期內(nèi)能從主存取得。主存模4交叉，每個(gè)分體寬為32位，總?cè)萘繛?56KB。用按地址訪問存儲(chǔ)器構(gòu)成相聯(lián)目錄表實(shí)現(xiàn)主存地址到Cache地址的變換，并約定用4個(gè)外相等比較電路。請(qǐng)?jiān)O(shè)計(jì)此相聯(lián)目錄表，求出該表之行數(shù)、總位數(shù)及每個(gè)比較電路的位數(shù)。

解答：

設(shè)Cache地址中的組內(nèi)塊號(hào)為s，相聯(lián)目錄表的行數(shù)是2^(13-s)，總位數(shù)是(8+2s)*2^(15-s)，每個(gè)比較電路的位數(shù)為8+s。

剖析：

在一個(gè)主存周期內(nèi)主存能訪問到的字節(jié)數(shù)為mW=4*32/8=16(Byte)。要求Cache的每一塊在一個(gè)主存周期內(nèi)能從主存取得，所以，Cache中每塊的塊內(nèi)字?jǐn)?shù)不能大于16Bytes。為了加速調(diào)塊，一般讓每塊的大小等于在一個(gè)主存周期內(nèi)主存能訪問到的字?jǐn)?shù)，即16Bytes。

設(shè)Cache地址中的組內(nèi)塊號(hào)為s，相聯(lián)目錄表的行數(shù)=Cache地址內(nèi)的組數(shù)Q=Cache容量/(每組塊數(shù)*每塊大小)=1KB/(S*4*32)=2^13/(2^s*2^7)=2^(6-s)。

主存塊數(shù)/Cache塊數(shù)=256=2*8，所以，主存地址中的區(qū)號(hào)nd=8。每個(gè)比較電路的位數(shù)=nd+s'=nd+s=8+s。

相聯(lián)目錄表的總位數(shù)=表中子目錄表的個(gè)數(shù)*每個(gè)子目錄表的位數(shù)*相聯(lián)目錄表的行數(shù)=4*(nd+s'+s)*Q=4*(8+2s)*2^(6-s)=(8+2s)*2^(8-s)。

note：

若認(rèn)為相等比較電路的個(gè)數(shù)=組內(nèi)塊數(shù)，則相聯(lián)目錄表的行數(shù)=2^4，每個(gè)比較電路的位數(shù)=10，相聯(lián)目錄表的總位數(shù)=12*2^6。

12.有一個(gè)Cache存儲(chǔ)器。主存共分8個(gè)塊(0~7),Cache為4個(gè)塊(0~3),采用組相聯(lián)映象，組內(nèi)塊數(shù)為2塊，替換算法為近期最少使用算法(LRU)。

(1)畫出主存、Cache地址的各字段對(duì)應(yīng)關(guān)系(標(biāo)出位數(shù))圖;

(2)畫出主存、Cache空間塊的映象對(duì)應(yīng)關(guān)系示意圖;

(3)對(duì)于如下主存塊地址流：1,2,4,1,3,7,0,1,2,5,4,6,4,7,2,如主存中內(nèi)容一開始未裝入Cache中，請(qǐng)列出Cache中各塊隨時(shí)間的使用狀況;

(4)對(duì)于(3),指出塊失效又發(fā)生塊爭用的時(shí)刻;

(5)對(duì)于(3),求出此期間Cache的命中率。

解答：

(1)主存地址、Cache地址的各字段的位數(shù)及其對(duì)應(yīng)關(guān)系如下圖所示

(2)主存塊、Cache塊的映象對(duì)應(yīng)關(guān)系如下圖所示

(3)Cache中各塊隨時(shí)間的使用狀況如下圖所示。圖中標(biāo)*號(hào)的是候選替換塊的塊號(hào)，H：命中;R：替換;L：失效。

(4)發(fā)生塊失效又發(fā)生塊爭用的時(shí)刻有6、7、9、10、11、12、14、15。

(5)Cache的塊命中率Hc=3/15=0.2。

剖析：

由于主存塊、Cache塊之間存在上述的映象對(duì)應(yīng)關(guān)系，主存的第0、1、4、5塊只能映象裝入或替換物理Cache的第0、1塊;主存的第2、3、6、7塊只能映象裝入或替換物理Cache的第2、3塊。

13.采用組相聯(lián)映象，LRU替換算法的Cache存儲(chǔ)器，發(fā)現(xiàn)等效訪問速度不高，為此建議：

(1)增大主存容量;

(2)增大Cache的塊數(shù)(塊的大小不變);

(3)增大組相聯(lián)組的大小(塊的大小不變);

(4)增大塊的大小(組的大小和Cache總?cè)萘坎蛔?;

(5)提高Cache本身器件的訪問速度。

解答：(1)增大主存容量對(duì)Cache的訪問時(shí)間ta基本不影響，從而對(duì)Cache的等效訪問速度基本不影響。

(2)增大Cache的塊數(shù)(塊的大小不變)一般將使Cache的命中率Hc上升，從而使ta下降，從而提高Cache的等效訪問速度。

(3)增大組相聯(lián)組的大小(塊的大小不變)一般將使Cache的命中率Hc上升，從而使ta下降，從而提高Cache的等效訪問速度。

(4)增大塊的大小(組的大小和Cache總?cè)萘坎蛔?一般將使ta下降，從而提高Cache的等效訪問速度。

(5)提高Cache本身器件的訪問速度一般將縮短ta，從而提高Cache的等效訪問速度。

14.你對(duì)Cache存儲(chǔ)器的速度不滿，于是申請(qǐng)到一批有限的經(jīng)費(fèi)，為能發(fā)揮其最大經(jīng)濟(jì)效益，有人建議你再買一些同樣速度的Cache片子以擴(kuò)充其容量;而另有人建議你干脆去買更高速的Cache片子將現(xiàn)有的低速Cache片子全部換掉。你認(rèn)為哪種建議可?。磕闳绾巫鰶Q定？為什么？

解答：

Cache本身的速度與容量都會(huì)影響Cache存儲(chǔ)器的等效訪問速度。如果對(duì)Cache存儲(chǔ)器的等效訪問速度不滿，需要改進(jìn)的話，就要作具體分析，看看現(xiàn)在Cache存儲(chǔ)器的等效訪問速度是否已接近于Cache本身的速度。如果差得較遠(yuǎn)，說明Cache的命中率低，應(yīng)從提高Cache命中率著手，包括調(diào)整組的大小、塊的大小、替換算法以及增大Cache容量等。如果Cache存儲(chǔ)器的等效訪問速度已經(jīng)非常接近于Cache本身的速度還不能滿足需要，就應(yīng)該更換更高速的Cache片子。

第五章重疊、流水和向量處理機(jī)

1.假設(shè)指令的解釋分取指、分析與執(zhí)行3步，每步的時(shí)間相應(yīng)為t取指、t分析、t執(zhí)行,

(1)分別計(jì)算下列幾種情況下，執(zhí)行完100條指令所需時(shí)間的一般關(guān)系式：

a.順序方式;

b.僅“執(zhí)行k”與“取指k+1”重疊;

c.僅“執(zhí)行k”、“分析k+1”、“取指k+2”重疊;

(2)分別在t取指=t分析=2、t執(zhí)行=1及t取指=t執(zhí)行=5、t分析=2兩種情況下，計(jì)算出上述各結(jié)果。

解：

(1)執(zhí)行完100條指令所需時(shí)間：

a.100*(t取指+t分析+t執(zhí)行);

b.t取指+100*t分析+99*max(t取指+t執(zhí)行)+t執(zhí)行;

c.t取指+max(t取指+t分析)+98*max(t取指+t分析+t執(zhí)行)+max(t分析+t執(zhí)行)+t執(zhí)行。

(2)在t取指=t分析=2、t執(zhí)行=1的情況下，執(zhí)行完100條指令所需時(shí)間：

a.500

b.401

c.203

在t取指=t執(zhí)行=5、t分析=2的情況下，執(zhí)行完100條指令所需時(shí)間：

a.1200

b.705

c.510

2.流水線有4個(gè)功能部件組成，每個(gè)功能部件的延遲時(shí)間為△t，當(dāng)輸入10個(gè)數(shù)據(jù)后間歇5△t又輸入10個(gè)數(shù)據(jù)，如此周期性地工作，求此時(shí)流水線的吞吐率，并畫出時(shí)空?qǐng)D。

解：

TP=10/14△t=5/7△t

時(shí)空?qǐng)D：

圖5.35(a)

圖5.35(b)

解：

按圖5.35(a)組織的流水線時(shí)，TP=3/13△t;η=3/11。

實(shí)現(xiàn)A*B*C*D的時(shí)空?qǐng)D如圖0504所示：

圖0504

按圖5.35(a)組織的流水線時(shí)，TP=3/13△t;η=3/11。

實(shí)現(xiàn)A*B*C*D的時(shí)空?qǐng)D如圖0504所示：

圖0505

剖析：

為了減少運(yùn)算過程中的操作數(shù)相關(guān)，A*B*C*D應(yīng)改為((A*B)*(C*D))進(jìn)行運(yùn)算。

4.一個(gè)4段的雙輸入端規(guī)格化浮點(diǎn)加法流水線，每段經(jīng)過時(shí)間10ns,輸出可直接返回輸入或?qū)⒔Y(jié)果暫存于相應(yīng)緩沖器中，問最少需經(jīng)多少時(shí)間能求(10)∑(i=1)Ai，并畫出時(shí)空?qǐng)D。

答:

時(shí)空?qǐng)D如下：

求(10)∑(i=1)Ai需要的最知時(shí)間是170ns。

剖析：

為了避免先寫后讀相關(guān)，使流水線性能盡可能高，需將(10)∑(i=1)Ai調(diào)整成((((A1+A2)+(A3+A4))+(A9+A10))+((A5+A6)+(A7+A8)))。

5.為提高流水線效率可采用哪兩種主要途徑來克服速度瓶頸？現(xiàn)有3段流水線，各段經(jīng)過時(shí)間依次為△t、3△t、△t，

(1)分別計(jì)算在連續(xù)輸入3條指令時(shí)和30條指令時(shí)的吞吐率和效率。

(2)按兩種途徑之一改進(jìn)，畫出你的流水線結(jié)構(gòu)示意圖，同時(shí)計(jì)算連續(xù)輸入3條指令和30條指令時(shí)的吞吐率。

(3)通過對(duì)(1)、(2)兩小題的計(jì)算比較可得出什么結(jié)論？

解答:

為提高流水線效率可采用瓶頸希再細(xì)分和瓶頸段并聯(lián)兩種主要途徑來克服速度瓶頸。

(1)連續(xù)輸入3條指令時(shí)的吞吐率TP3=3/11△t;效率η3=5/11。

連續(xù)輸入30條指令時(shí)的吞吐率TP30=15/46△t;效率η3=25/46。

(2)改進(jìn)后的流水線結(jié)構(gòu)示意圖大體如圖5.35(a)和圖5.35(b)。

連續(xù)輸入3條指令時(shí)的吞吐率TP3=3/7△t;效率η3=3/7。

連續(xù)輸入30條指令時(shí)的吞吐率TP30=15/17△t;效率η3=15/17。

(3)只有當(dāng)連續(xù)輸入流水線的指令足夠多時(shí)，流水線的實(shí)際吞吐率和效率才會(huì)提高。

6.有一個(gè)雙輸入端的加-乘雙功能靜態(tài)流水線，由經(jīng)過時(shí)間為△t、2△t、2△t,△t的1、2、3、4四個(gè)子過程構(gòu)成。加按1->2->4連接，乘按1->3->4連接，流水線輸出設(shè)有數(shù)據(jù)緩沖器，也可將數(shù)據(jù)直接返回輸入?，F(xiàn)要執(zhí)行A*(B+C*(D+E*F))+G*H的運(yùn)算，請(qǐng)調(diào)整計(jì)算順序畫出能獲得盡量高的吞吐率的流水時(shí)空?qǐng)D，標(biāo)出流水線入、出端數(shù)的變化情況，求出完成全部運(yùn)算的時(shí)間及此期間流水線的效率。如對(duì)流水線瓶頸子過程再細(xì)分，最少只需多少時(shí)間可完成全部運(yùn)算？若子過程3不能再細(xì)分，只能用并聯(lián)方法改進(jìn)，問流水線的效率為多少？

解:

根據(jù)題意，畫出流水線吞吐率盡可能高的時(shí)空?qǐng)D如圖0507：

圖0507

在此期間的流水線效率η=(6*4△t+3*4△t)/4*24△t=3/8

如果將瓶頸子過程2和3均細(xì)分成兩個(gè)子過程，則時(shí)空?qǐng)D如圖0508所示：

圖0508

由圖可見，完成全部運(yùn)算最少需要18△t。

若子過程3不能再細(xì)分，只能用并聯(lián)方法改進(jìn)，則則時(shí)空?qǐng)D如圖0509所示：

圖0509

這種情況下，流水線效率η=(24△t+12△t)/6*18△t=1/3

剖析：

因?yàn)槭请p功能靜態(tài)流水線，為了能有高的吞吐率，應(yīng)減少流水線的功能切換次數(shù)。因此，應(yīng)將算法調(diào)整成先作一連串的乘，然后再切換成一連串的加。原式展開成A*B+A*C*D+A*C*E*F+G*H，先進(jìn)行乘法流水，為了減少因先寫后讀相關(guān)而等待的時(shí)間，應(yīng)盡量安排對(duì)計(jì)算式子項(xiàng)數(shù)最多的乘法先進(jìn)行操作，即先計(jì)算A*C*E*F，再計(jì)算A*C*D，...

7.現(xiàn)有長度為8的向量A和B，請(qǐng)分別畫出下列4種結(jié)構(gòu)的處理器上求點(diǎn)積A*B的時(shí)空?qǐng)D，并求完成全部結(jié)果的最少時(shí)鐘拍數(shù)。設(shè)處理器中每個(gè)部件的輸出均可直接送到任何部件的輸入或存入緩沖器中去，其間的傳送延時(shí)不計(jì)，指令和源操作數(shù)均能連續(xù)提供。

(1)處理器有一個(gè)乘法部件和一個(gè)加法部件，不能同時(shí)工作，部件內(nèi)也只能以順序方式工作，完成一次加法或乘法均需5拍;

(2)與(1)基本相同，只是乘法部件和加法部件可并行;

(3)處理器有一個(gè)乘、加法雙功能靜態(tài)流水線，乘、加法均由5個(gè)流水段構(gòu)成，各段經(jīng)過時(shí)間要1拍;

(4)處理器有乘、加法兩條流水線，可同時(shí)工作，各由5段構(gòu)成，每段經(jīng)過時(shí)間為1拍。

解答：

(1)在這種結(jié)構(gòu)的處理器上求點(diǎn)積A*B的時(shí)空?qǐng)D如圖0510所示：

圖0510

完成全部運(yùn)算最少需要75拍。

(2)在這種結(jié)構(gòu)的處理器上求點(diǎn)積A*B的時(shí)空?qǐng)D如圖0511所示：

圖0511

完成全部運(yùn)算最少需要45拍。

(3)在這種結(jié)構(gòu)的處理器上求點(diǎn)積A*B的時(shí)空?qǐng)D如圖0512所示：

圖0512

完成全部運(yùn)算最少需要30拍。

(4)在這種結(jié)構(gòu)的處理器上求點(diǎn)積A*B的時(shí)空?qǐng)D如圖0513所示：

圖0513

完成全部運(yùn)算最少需要26拍。剖析：向量A*B的點(diǎn)積為A*B=(8)∑(i=1)ai*bi=a1*b1+a2*b2+a3*b3+a4*b4+a5*b*+a6*b*+a7*b7+a8*b8,共需8次乘法和7次加法。

8.試總結(jié)IBM360/91解決流水線控制的一般方法、途徑和特點(diǎn)。

在流水線中設(shè)置相關(guān)直接通路解決局部相關(guān)；

用猜測法解決全局相關(guān)；

設(shè)置"向后8條"檢查，加快短循環(huán)程序的處理；

對(duì)流水線的中斷處理用"不精確斷點(diǎn)法"。

9.在一個(gè)5段的流水線處理機(jī)上需經(jīng)9拍才能完成一個(gè)任務(wù)，其預(yù)約表為：t0t1t2t3t4t5t6t7t8s1∨∨s2∨∨s3∨∨∨s4∨∨s5∨∨分別寫出延遲禁止表F、沖突向量C;畫出流水線狀態(tài)轉(zhuǎn)移圖;求出最小平均延遲及流水線的最大吞吐率及其高度方案。按此流水高度方案輸入6個(gè)任務(wù)，求實(shí)際吞吐率。

解：

根據(jù)預(yù)約表，延遲禁止表F={1，3，4，8}

沖突向量為C:10001101

狀態(tài)轉(zhuǎn)移圖如圖0514所示

圖0514

各種方案的平均延遲表：調(diào)度方案(2,5)(2,7)5(5,6)(6)(6,7)(7)平均延遲3.54.555.566.57

最小延遲為3.5拍，其調(diào)度方案為（2，5）。

按調(diào)度方案（2，5）輸入6個(gè)任務(wù)時(shí)的時(shí)空?qǐng)D如圖0515所示：

圖0515

實(shí)際吞吐率TP=6/25(任務(wù)/拍)。

剖析：

求延遲禁止表F={1，3，4，8}，第一行間隔8，第二行間隔1，第三行間隔1，3，4，然后間隔都為1，合并。

求沖突向量，寫一個(gè)8位兩進(jìn)制數(shù)，根據(jù)禁止表倒著寫。

由于初始沖突向量的c2,c5,c6,c7為0，所以第二個(gè)任務(wù)可以距第一個(gè)任務(wù)2，5，6或7拍流入流水線。

10.求向量D=A*(B+C)，各向量元素均為N，參照CRAY－1方式分解為3條向量指令：

1：V3＜-存儲(chǔ)器｛訪存取A送入V3寄存器組｝

2：V2＜-V0＋V1｛B＋C-＞K｝

3：V4＜-V2＋V3｛K＊A-＞D｝

當(dāng)采用下列3種方式工作時(shí)需多少拍才能得到全部結(jié)果？

（1）1、2、3、串行執(zhí)行;

（2）1和2并行執(zhí)行完后，再執(zhí)行3;

（3）采用鏈接技術(shù)。

解:（1）每條指令所需拍數(shù)為：

指令1：1（啟動(dòng)訪存）+6（訪存）+1（存V3）+N-1（第一個(gè)分量后每隔1拍出一個(gè)結(jié)果）=7+N

指令2：1（送浮加部件）+6（浮加）+1（存V2）+N-1=7+N

指令3：1（送浮乘部件）+7（浮乘）+1（存V4）+N-1=8+N

串行：7+N+7+N+8+N=22+3N

（2）指令1和2并行執(zhí)行：1（啟動(dòng)訪存，送浮加部件）+6（訪存，浮加）+1（存V3，存V2）+N-1=7+N

1，2并行：7+N+8+N=15+2N

（3）1+6+1+1++7+1+N-1=16+N

11.設(shè)向量長度為64，以CRAY-1機(jī)上所用浮點(diǎn)功能部件的執(zhí)行時(shí)間分別為：相加6拍，相乘7拍，求倒數(shù)近似值14拍;從存儲(chǔ)器讀數(shù)6拍，打入寄存器及啟動(dòng)功能部件各1拍。問下列各指令組內(nèi)的哪些指令可以鏈接？哪些指令不能鏈接？不能鏈接的原因是什么？分別計(jì)算出各指令組全部完成所需的拍數(shù)。(1)(2)(3)(4)V0←存儲(chǔ)器

V1←V2+V3

V4←V5*V6V2←V0*V1

V3←存儲(chǔ)器

V4←V2+V3V0←存儲(chǔ)器

V2←V0*V1

V3←V2+V0

V5←V3+V4V0←存儲(chǔ)器

V1←1/V0

V3←V1*V2

V5←V3+V4

解：

(1)3條向量指令之間既沒有發(fā)生源Vi沖突，也沒有Vi的先寫后讀相關(guān)，又不存在功能部件的使用沖突，所以這3條向量指令可以同時(shí)并行流水。max{(1+6(訪存)+1+64-1),(1+6(浮加)+1+64-1),(1+(7浮乘)+1+64-1)}=72拍。所以向量指令組全部完成需要72(拍)。

(2)3條向量指令之間沒有功能部件的使用沖突，但是在第1、2兩條向量指令與第3條向量指令之間有V2及V3的先寫后讀相關(guān)。只要讓第1條向量指令較第2條向量指令提前1拍啟動(dòng)，則第1,2兩條向量指令的第1個(gè)結(jié)果元素就可以被同時(shí)鏈接到第3條向量指令中。max{(1+(7浮乘)+1+64-1),(1+6(訪存)+1+64-1)}+(1+6(浮加)+1+64-1)=80(拍)。

(3)第1條向量指令與第2條向量指令之間有V0的先寫后讀相關(guān)，兩者可以鏈接。第3條向量指令與第2條向量指令之間有源向量寄存器V0的沖突，它們之間只能串行。第3條向量指令與第4條向量指令之間有加法功能部件的使用沖突，它們之間也只能串行。(1+6(訪存)+1+1+(7浮乘)+1+64-1)+(1+6(訪存)+1+64-1)(1+6(浮加)+1+64-1)=222(拍)。

(4)4條向量指令均依次有Vi的先寫后讀相關(guān)，但無源Vi沖突，也無功能部件的使用沖突，所以，這4條向量指令可以全部鏈接在一直，進(jìn)行流水。(1+6(訪存)+1)+(1+14(求倒數(shù))+1)+(1+(7浮乘)+1)+(1+6(浮加)+1)+64-1=104拍。

12.設(shè)指令由取指、分析、執(zhí)行三個(gè)子部件組成。每個(gè)子部件經(jīng)過時(shí)間為△t，連續(xù)執(zhí)行12條指令。請(qǐng)分別畫出在常規(guī)標(biāo)量流水處理機(jī)及度m均為4的超標(biāo)量處理機(jī)、超長指令字處理機(jī)、超流水線處理機(jī)上工作的時(shí)空?qǐng)D，分別計(jì)算它們相對(duì)常規(guī)標(biāo)量流水處理機(jī)的加速比Sp。

解：

常規(guī)標(biāo)量處理機(jī)的時(shí)空?qǐng)D：

度m為4的超標(biāo)量處理機(jī)的時(shí)空?qǐng)D：

其相對(duì)于常規(guī)標(biāo)量流水處理機(jī)的加速比Sp=14△t/5△t=2.8

度m為4的超長指令字處理機(jī)的時(shí)空?qǐng)D：

其相對(duì)于常規(guī)標(biāo)量流水處理機(jī)的加速比Sp=14△t/5△t=2.8

度m為4的超流水線處理機(jī)的時(shí)空?qǐng)D：

其相對(duì)于常規(guī)標(biāo)量流水處理機(jī)的加速比Sp=14△t/5.75△t=56/23≈2.8

第六章陣列處理機(jī)

1.畫出16臺(tái)處理器仿ILLIACⅣ的模式進(jìn)行互連的互連結(jié)構(gòu)圖，列出PE0分別只經(jīng)一步、二步和三步傳送能將信息傳送到的各處理器號(hào)。

答：

6臺(tái)處理器仿ILLIACⅣ處理單元的互連結(jié)構(gòu)如圖所示：

圖中第個(gè)PU中包含PE、PEM和MLU。

PE0(PU0)經(jīng)一步可將信息傳送至PU1、PU4、PU12、PU15。

PE0(PU0)至少需經(jīng)二步才能將信息傳送至PU2、PU3、PU5、PU8、PU11、PU13、PU14。

PE0(PU0)至少需經(jīng)三步步才能將信息傳送至PU6、PU7、PU9、PU10。

2.編號(hào)為0、1、...、15的16個(gè)處理器，用單級(jí)互連網(wǎng)互連。當(dāng)互連函數(shù)分別為

(1)Cube3

(2)PM2+3

(3)PM2-0

(4)Shuffle

(5)Shuffle(Shuffle)

時(shí)，第13號(hào)處理器各連至哪一個(gè)處理器？

解答：

(1)5號(hào)處理器

(2)5號(hào)處理器

(3)12號(hào)處理器

(4)11號(hào)處理器

(5)7號(hào)處理器

剖析：

由題意知，有16個(gè)處理器，即N=16,n=log2(N)=log2(16)=4。

Cube3(13)=Cube3(1101)=0101=5

PM2+3(13)=(13+2^3)mod16=5

PM2-0(13)=(13-2^0)mod16=12

Shuffle(13)=Shuffle(1101)=1011=11

Shuffle(Shuffle)=Shuffle(11)=Shuffle(1011)=0111=7

3.編號(hào)分別為0、1、2、...、F的16個(gè)處理器之間要求按下列配對(duì)通信：(B、1)，(8、2)，(7、D)，(6、C)，(E、4)，(A、0)，(9、3)，(5、F)。試選擇所用互連網(wǎng)絡(luò)類型、控制方式，并畫出該互連網(wǎng)絡(luò)的拓補(bǔ)結(jié)構(gòu)和各級(jí)交換開關(guān)狀態(tài)圖。

解答：

采用4級(jí)立方體網(wǎng)絡(luò)，級(jí)控制。該互連網(wǎng)絡(luò)的拓補(bǔ)結(jié)構(gòu)和各級(jí)交換開關(guān)狀態(tài)圖如下圖所示：

剖析：

從處理器號(hào)的配對(duì)傳送關(guān)系可以轉(zhuǎn)成處理器二進(jìn)制編號(hào)的配對(duì)傳送關(guān)系：

(B,1)(1011,0001)

(8,2)(1000,0010)

(7,D)(0111,1101)

(6,C)(0110,1100)

(E,4)(1110,0100)

(A,0)(1010,0000)

(9,3)(1001,0011)

(5,F)(0101,1111)

不難得出其一般規(guī)律是：二進(jìn)制編號(hào)為P3P2P1P0的處理器與(￣P3)P2(￣P1)P0的處理器配對(duì)交換數(shù)據(jù)。由于實(shí)現(xiàn)的都是交換函數(shù)的功能，采用成本最低的級(jí)控制多級(jí)立方體互聯(lián)網(wǎng)絡(luò)就可以實(shí)現(xiàn)。

N=16的多級(jí)立方體網(wǎng)絡(luò)，由n=log2(16)=4組成。每一級(jí)均使用N/2=8個(gè)二功能交換開關(guān)。多級(jí)網(wǎng)絡(luò)各級(jí)的級(jí)號(hào)由入端到出端依次為0、1、2、3.第i級(jí)的每個(gè)交換單元的配對(duì)用的是Cubei(P3...Pi...P0)=P3...(￣Pi)...P0函數(shù)。根據(jù)本題的要求，應(yīng)當(dāng)讓第1、3級(jí)的各交換單元處于“交換”狀態(tài)，第0、2級(jí)的各交換單元處于“直連”狀態(tài)。

4.畫出編號(hào)為0、1、...、F共16個(gè)處理器之間實(shí)現(xiàn)多級(jí)立方體互連的互連網(wǎng)絡(luò)，采用級(jí)控制信號(hào)為1100(從右至左分別控制第0級(jí)至第3級(jí))時(shí)，9號(hào)處理器連向哪個(gè)處理器？

解答：

多級(jí)立方體互連網(wǎng)絡(luò)的圖和第3題的圖基本一致，不同之處在于，第0、1級(jí)的開關(guān)狀態(tài)為直連，第2、3級(jí)的開關(guān)狀態(tài)為交換。

9號(hào)處理器在經(jīng)過0級(jí)和1級(jí)交換開關(guān)后，連向哪第10個(gè)處理器;在經(jīng)過2級(jí)交換開關(guān)后，連向第4個(gè)處理器;在經(jīng)過3級(jí)交換開關(guān)后，連向第9個(gè)處理器。

5.對(duì)于采用級(jí)控制的三級(jí)立方體網(wǎng)絡(luò)，當(dāng)?shù)趇級(jí)(0<=i<=2)為直連狀態(tài)時(shí)，不能實(shí)現(xiàn)哪些結(jié)點(diǎn)之間的通信？為什么？反之，當(dāng)?shù)趇級(jí)為交換狀態(tài)呢？

解答：

當(dāng)?shù)趇級(jí)為直連狀態(tài)時(shí)，不能實(shí)現(xiàn)入、出兩端的處理器二進(jìn)制編碼的編號(hào)中，第Pi位取反的處理器之間的連接。例如，第0級(jí)為直連狀態(tài)時(shí)，入端號(hào)為××0的處理器僅能與出端號(hào)為××0的處理器進(jìn)行數(shù)據(jù)傳送，不能與出端號(hào)為××1的處理器進(jìn)行數(shù)據(jù)傳送。因?yàn)榻粨Q開關(guān)的直連狀態(tài)被定義為i入連i出，j入連j出，所以，反映出實(shí)現(xiàn)互連的入、出端號(hào)的二進(jìn)制碼中的Pi位是不能變反的，其它的各位可以不變，也可以變反。

當(dāng)?shù)趇級(jí)為交換狀態(tài)時(shí)，不能實(shí)現(xiàn)入、出兩端的處理器二進(jìn)制編碼的編號(hào)中，第Pi位相同的處理器之間的連接。例如，第0級(jí)為交換狀態(tài)時(shí)，入端號(hào)為××0的處理器僅能與出端號(hào)為××1的處理器進(jìn)行數(shù)據(jù)傳送，不能與出端號(hào)為××0的處理器進(jìn)行數(shù)據(jù)傳送。因?yàn)榻粨Q開關(guān)的直連狀態(tài)被定義為i入連j出，j入連i出，所以，反映出實(shí)現(xiàn)互連的入、出端號(hào)的二進(jìn)制碼中的Pi位必須變反，其它的各位可以不變，也可以變反。

6.假定8*8矩陣A=(aij)，順序存放在存儲(chǔ)器的64個(gè)單元中，用什么機(jī)關(guān)報(bào)單級(jí)互連網(wǎng)絡(luò)可實(shí)現(xiàn)對(duì)該矩陣的轉(zhuǎn)置變換？總共需要傳送多少