【正文】 B7 830ns 9 2 1 A2 B2 A1 B1(3) ，設(shè)單向環(huán)可以并行傳送（即為“移數(shù)環(huán)”，）。(2) 多功能部件SISD計(jì)算機(jī)的工作方式可參考P346題18(3)。 已知N = 256，n = 8，起始結(jié)點(diǎn)編號(hào)j = 123 = 01111011B。 4組4元交換：f1 = Cube1Cube0； 2組8元交換：f2 = Cube2Cube1Cube0； 1組16元交換：f3 = Cube3Cube2Cube1Cube0；利用Cube函數(shù)的結(jié)合律、交換律以及同一律（又稱自反律）可以推得 f = f1f2f3 = Cube3Cube1Cube0 拓?fù)浣Y(jié)構(gòu)圖略（―交換網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖）。證：設(shè)矩陣A = (aij)88按行展開依次存放在64個(gè)單元中，則任意元素aij的地址為8i + j，而aji的地址為8j + i。(8)插入前TP = 10/33Δt = 1/33ns，插入后TP = 10/26Δt = 1/26ns，如下圖所示。 3 5 √ √ 虛組3 6 6 √ √ 7 7 √ √ (a) 虛頁集合與實(shí)頁集合的對(duì)應(yīng)關(guān)系 (b) 對(duì)應(yīng)關(guān)系表（√為有關(guān)系）(3)(4)通過作“實(shí)存狀況圖”模擬各虛塊的調(diào)度情況，可獲得Cache的塊地址流序列。(1)此問中的“最優(yōu)Huffman編碼法”實(shí)際是指碼長下限，即信源的平均信息量──熵，代公式得H=。最大絕對(duì)值”回答；最小正數(shù)與最大負(fù)數(shù)的絕對(duì)值相同，可用“177。有下劃線者為推薦的主要知識(shí)點(diǎn)。 此題關(guān)鍵是分析階碼、尾數(shù)各自的最大值、最小值。21023表數(shù)精度δ224253表數(shù)效率η100%100%(1) rm = 2，re = 2，p = 24（隱藏最高位）,q = 7。 0 實(shí)組0 2 √ √ 3 (5)新預(yù)約表如下圖(b)所示。 輸入結(jié)點(diǎn)編號(hào)j = 9，f(j) = j⊕控制信號(hào) = 1001B⊕1100B = 0101B = 5，答為5號(hào)處理機(jī)。 求單級(jí)立方體網(wǎng)絡(luò)和單級(jí)混洗―交換網(wǎng)絡(luò)的最大廣播步數(shù)，這兩種網(wǎng)絡(luò)的最大廣播步數(shù)與最大距離（即直徑）相同。要得到單一樹根對(duì)于多片樹葉的綜合最短路徑，可以先分別作出各條單播最短路徑，然后在不增加各路徑長度的前提下，盡可能地進(jìn)行路段合并。(1) 在串行計(jì)算機(jī)上，共計(jì)15步運(yùn)算，T=8T傳=(30+350+710)ns=250ns(4)在全互連網(wǎng)絡(luò)上，任意兩個(gè)結(jié)點(diǎn)之間的距離均為1步，所以任何置換都能在1步完成，故 10 10 10 傳送 乘法 50 50 50 加法 30T=T加+3 首先在各結(jié)點(diǎn)用串行算法它們的相乘與求和，需時(shí)T1=4(3)一次通過實(shí)現(xiàn)的置換數(shù)為16 8 = 4294967296，全部置換數(shù)為N! = 20922789888000，%。 由于N = 16，即n = 4，每個(gè)結(jié)點(diǎn)編號(hào)用4位二進(jìn)制數(shù)表示。于是有平均速率Ra = 吞吐率TP = N/T。設(shè) 優(yōu)備 先號(hào) 級(jí)D1 1D2 4D3 2D4 3時(shí)間(us) 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170(3)5，160，20，40；(4)D2丟失第一次請(qǐng)求的數(shù)據(jù)；(5)參見P245。下圖就是“堆棧模擬圖”，其中“√”表示命中。(1224)(1)用硬件組方法，已知Se=40，F(xiàn)e=，解出Sn=40/≈（兩種方法得到的相同性能）(2)用軟件組方法，已知Se=20，Sn=40/，解出Fe=≈（第二種方法的百分比）(3)結(jié)論：軟件組方法更好。 將Se代入Amdahl定律得 上式中令Sn=2，解出Fe=10/19≈ 上式中令Sn=10，解出Fe=18/19≈ 已知兩種方法可使性能得到相同的提高，問哪一種方法更好。最大絕對(duì)值177。 欲知可能的最高命中率及所需的最少主存頁數(shù)，較好的辦法是通過“堆棧模擬法”，求得命中次數(shù)隨主存頁數(shù)變化的函數(shù)關(guān)系。作圖時(shí)注意：至少要畫到最慢設(shè)備的第二次請(qǐng)求出現(xiàn)，才能確定是否丟失數(shù)據(jù)（因?yàn)轫憫?yīng)優(yōu)先級(jí)低的設(shè)備較易丟失數(shù)據(jù)）。）推導(dǎo)法2：為了推導(dǎo)，定義T為總時(shí)間，N為總?cè)蝿?wù)數(shù)。22運(yùn)算只有可能改變j中的X6～X2，所以最多使用Cube6～Cube2就能實(shí)現(xiàn)代換了。(2)見下圖虛線；不會(huì)阻塞，因?yàn)閮蓷l路徑的控制信號(hào)都是1110，形成級(jí)控模式，所以不會(huì)阻塞。 按平均分配原則，每個(gè)結(jié)點(diǎn)內(nèi)有4對(duì)數(shù)據(jù)。T乘+(1+2+4)T加+7 0,7 1,7 2,7 3,7 4,7 5,7 6,7 7,7 0,6 1,6 2,6 3,6 4,6 5,6 6,6 7,6 0,5 1,5 2,5 3,5 4,5 5,5 6,5 7,5 0,4 1,4 2,4 3,4 4,4 5,4 6,4 7,4 0,3 1,3 2,3 3,3 4,3 5,3 6,3 7,3 0,2 1,2 2,2 3,2 4,2 5,2 6,2 7,2Y 0,1 1,1 2,1 3,1 4,1 5,1 6,1 7,1 0,0 1,0 2,0 3,0 4,0 5,0 6,0 7,0 X 這兩小問結(jié)果如下圖所示（其中b圖第一步必須選擇向下，而不能向右）。(1)單級(jí)立方體網(wǎng)絡(luò)直徑 = n（Cuben1～Cube0各1次）；(2)單級(jí)混洗―交換網(wǎng)絡(luò)直徑 = 2n1（n1次混洗，n次交換）。 直連狀態(tài)時(shí)：編號(hào)在第i位不同的結(jié)點(diǎn)之間不能通信； 交換狀態(tài)時(shí)：編號(hào)在第i位相同的結(jié)點(diǎn)之間不能通信。 1 2 3 4 5 6 7 8 初態(tài) 4，6，≥8 S1 1 2 初態(tài) 3，4，≥6 S2 1 1 0 0 0 1 0 1 S3 4，6，≥8 4，6，≥8 1 0 0 1 1 S4 1 2 5 D1 1 0 1 0 1 0 1 1 0 0 0 1 1 1 D2 2 5