清華第2版《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》 部分答案

《清華第2版《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》 部分答案》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《清華第2版《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》 部分答案（19頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》習(xí)題解答 目錄 第一章(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（浮點(diǎn)數(shù)性能），2.13、2.15（指令編碼） 第三章(P202) 3.3（存儲(chǔ)層次性能），3.5（并行主存系統(tǒng)），3.15-3.15加1題（堆棧模擬），3.19中(3)(4)(6)(8)問(wèn)（地址映象/替換算法--實(shí)存狀況圖） 第四章(P250) 4.5（中斷屏蔽字表/中斷過(guò)程示意圖），4.8（通道流量計(jì)算/通道時(shí)間圖） 第五章

2、(P343) 5.9（流水線(xiàn)性能/時(shí)空?qǐng)D），5.15（2種調(diào)度算法） 第六章(P391) 6.6（向量流水時(shí)間計(jì)算），6.10（Amdahl定律/MFLOPS） 第七章(P446) 7.3、7.29（互連函數(shù)計(jì)算），7.6-7.14（互連網(wǎng)性質(zhì)），7.4、7.5、7.26（多級(jí)網(wǎng)尋徑算法），7.27（尋徑/選播算法） 第八章(P498) 8.12（SISD/SIMD算法） 第九章(P562) 9.18（SISD/多功能部件/SIMD/MIMD算法） (注：每章可選1-2個(gè)主要知識(shí)點(diǎn)，每個(gè)知識(shí)點(diǎn)可只選1題。有下劃線(xiàn)者為推薦的主要知識(shí)點(diǎn)。) 第一章(P33

3、) 1.7 (1)從指定角度來(lái)看，不必要了解的知識(shí)稱(chēng)為透明性概念。 (2)見(jiàn)下表，“√”為透明性概念，“P”表示相關(guān)課文頁(yè)數(shù)。 模m交叉，√， 浮點(diǎn)數(shù)據(jù)，×，P4 通道與I/O處理機(jī)，×，P4 總線(xiàn)寬度，√， 陣列運(yùn)算部件，×， 結(jié)合型與獨(dú)立型通道，√， 單總線(xiàn)，√， 訪(fǎng)問(wèn)保護(hù)，×， 中斷，×， 指令控制方式，√， 堆棧指令，×， 最小編址單位，×， Cache存儲(chǔ)器，√， 1.8見(jiàn)下表，“√”為透明性概念，“P”表示相關(guān)課文頁(yè)數(shù)。 指令地址寄存器，×， 指令緩沖器，√， 時(shí)標(biāo)發(fā)生器，√， 條件碼寄存器，×， 乘法器，√， 主存地址寄存

4、器，√， 磁盤(pán)，×， 先行進(jìn)位鏈，√， 移位器，√， 通用寄存器 ，×， 中斷字寄存器，×， 1.9見(jiàn)下表，“√”表示都透明，“應(yīng)”表示僅對(duì)應(yīng)用程序員透明，“×”表示都不透明。 數(shù)據(jù)通路寬度，√， 虛擬存儲(chǔ)器，應(yīng)， Cache存儲(chǔ)器，√， 程序狀態(tài)字，×， “啟動(dòng)I/O”指令，應(yīng)， “執(zhí)行”指令，×， 指令緩沖寄存器，√， Sn 20 1 0 1 Fe 1.12 已知Se=20 , 求作Fe-Sn關(guān)系曲線(xiàn)。 將Se代入Amdahl定律得 1.13 上式中令Sn=2，解出Fe=10/19≈0.526

5、 1.14 上式中令Sn=10，解出Fe=18/19≈0.947 1.15 已知兩種方法可使性能得到相同的提高，問(wèn)哪一種方法更好。 (1)用硬件組方法，已知Se=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)結(jié)論：軟件組方法更好。因?yàn)橛布M需要將Se再提高100%（20→40），而軟件組只需將Fe再提高1.84%（0.7→0.7184）。 1.17 1.18 記f ── 時(shí)鐘頻率，T=1/f ── 時(shí)鐘

6、周期，B ── 帶寬（Byte/s）。 方案一： 方案二： 1.19 由各種指令條數(shù)可以得到總條數(shù)，以及各百分比，然后代公式計(jì)算。 (1) (2) (3) 1.21 (1) (2) 1.24 記Tc ── 新方案時(shí)鐘周期，已知CPI = CPIi = 1 原時(shí)間 = CPI × IC × 0.95Tc = 0.95IC×Tc 新時(shí)間 = （0.3×2/3+0.7）× IC × Tc = 0.9IC×Tc 二者比較，新時(shí)間較短。 第二章(P124) 2.3（忽略P124倒1行 ～ P125第8行文字，以簡(jiǎn)化題意）已知2種浮點(diǎn)數(shù)，求

7、性能指標(biāo)。 此題關(guān)鍵是分析階碼、尾數(shù)各自的最大值、最小值。 原圖為數(shù)據(jù)在內(nèi)存中的格式，階碼的小數(shù)點(diǎn)在其右端，尾數(shù)的小數(shù)點(diǎn)在其左端，遵守規(guī)格化要求。 由于尾數(shù)均為原碼，原碼的絕對(duì)值與符號(hào)位無(wú)關(guān)，所以最大正數(shù)與最小負(fù)數(shù)的絕對(duì)值相同，可用“±最大絕對(duì)值”回答；最小正數(shù)與最大負(fù)數(shù)的絕對(duì)值相同，可用“±最小絕對(duì)值”回答。 第1小問(wèn)中，階碼全部位數(shù)為8，作無(wú)符號(hào)數(shù)看待真值為0～255，作移-127碼看待真值為-127～+128；尾數(shù)（不計(jì)符號(hào)位）有23位小數(shù)，另加1位整數(shù)隱藏位，所以尾數(shù)絕對(duì)值為1.0～2.0 – 2-23，有效位數(shù)p=24； 第2小問(wèn)中，階碼全部位數(shù)為11，

8、作無(wú)符號(hào)數(shù)看待真值為0～2047，作移-1023碼看待真值為-1023～+1024；尾數(shù)（不計(jì)符號(hào)位）有52位小數(shù)，另加1位整數(shù)隱藏位，所以尾數(shù)絕對(duì)值為1.0～2.0 – 2-52，有效位數(shù)p=53。 最大絕對(duì)值為最大階碼與最大尾數(shù)絕對(duì)值的組合，最小絕對(duì)值為最小階碼與最小尾數(shù)絕對(duì)值的組合。代入相關(guān)公式后得最終結(jié)果如下表。 32位 64位 ±最大絕對(duì)值 ±(1-2-24)·2129 ±(1-2-53)·21025 ±最小絕對(duì)值 ±2-127 ±2-1023 表數(shù)精度δ 2-24 2-53 表數(shù)效率η 100% 100% 2.5 (1) rm = 2，

9、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.6 1位 7位 6位 0 0111111 333333 (1) 0.2 = 0.333333H×160 設(shè)階碼為移-63碼（即-26+1，原題未指明） 0.2 = 0.110011001100110011001101B×2-2 1位 8位 23位 0 01111101 10011001100110011001101 （其中最高有效

10、位需隱藏） 階碼為移-127碼（即-27+1） (2) 符號(hào)位不變，（階碼 – 63）×4 + 127；尾數(shù)左規(guī)，除去最高位； (3) 符號(hào)位不變，（階碼 – 127）/ 4 + 63；尾數(shù)補(bǔ)最高位，按除法余數(shù)右移若干位，左補(bǔ)0。 2.13 已知10條指令使用頻度，求3種編碼方法的平均碼長(zhǎng)與信息冗余量。 (1)此問(wèn)中的“最優(yōu)Huffman編碼法”實(shí)際是指碼長(zhǎng)下限，即信源的平均信息量──熵，代公式得H=2.9566。 (2)Huffman編碼性能如下表； (3)2/8擴(kuò)展編碼是8/64/512法的變種，第一組2條指令，碼長(zhǎng)為2（1位擴(kuò)展標(biāo)志，1位編碼）,第二組8條指令，碼

11、長(zhǎng)為4（1位擴(kuò)展標(biāo)志，與第一組區(qū)別，加3位編碼），編碼性能如下表； (4)3/7擴(kuò)展編碼是15/15/15法的變種，第一組3條指令，碼長(zhǎng)為2（共有4種組合，其中3種組合分別代表3條指令，留1種組合作為擴(kuò)展前綴標(biāo)志）,第二組7條指令，碼長(zhǎng)為5（2位固定的前綴擴(kuò)展標(biāo)志，與第一組區(qū)別，加3位編碼，只用其中7種組合），編碼性能如下表。 Huffman編碼 2/8擴(kuò)展編碼 3/7擴(kuò)展編碼 平均碼長(zhǎng)L 2.99 3.1 3.2 信息冗余量R 1.10% 4.61% 7.59% 2.15 (1) 15條/63條/64條 (2) 14條/126條/128條 第三章(

12、P202) 3.3 直接代公式計(jì)算存儲(chǔ)層次性能指標(biāo)。 (1)74ns，38ns，23.6ns (2)0.258，0.315，0.424 (3)T256K < T128K < T64K c256K > c128K > c64K (4)19.092，11.97，10.0064。答案是256K方案最優(yōu)。 3.5 已知，其中g(shù)=0.1 依題意有 整理得0.9n≥0.2，解出，向下取整，得15； 按另一種題意理解是向上取整，得16，也對(duì)。 3.15 欲知可能的最高命中率及所需的最少主存頁(yè)數(shù)，較好的辦法是通過(guò)“堆棧模擬法”，求得命中次數(shù)隨主存頁(yè)數(shù)變化的函數(shù)關(guān)系。下圖就是

13、“堆棧模擬圖”，其中“√”表示命中。 P= 4 5 3 2 5 1 3 2 3 5 1 3 命中次數(shù) 4 5 3 2 5 1 3 2 3 5 1 3 4 5 3 2 5 1 3 2 3 5 1 4 5 3 2 5 1 1 2 3 5 4 4 3 2 5 5 1 2 2 4 4 4 4 4 4 4 n=1

14、 0 n=2 √ 1 n=3 √ √ √ 3 n=4 √ √ √ √ √ √ √ 7 n=5 √ √ √ √ √ √ √ 7 (1)Hmax=7/12≈58.3% (2)n=4 (3)當(dāng)1次頁(yè)面訪(fǎng)問(wèn)代表連續(xù)1024次該頁(yè)內(nèi)存儲(chǔ)單元訪(fǎng)問(wèn)時(shí)，后1023次單元訪(fǎng)問(wèn)肯定是命中的，而第1次單元訪(fǎng)問(wèn)的命中情況與這1次頁(yè)面訪(fǎng)問(wèn)的命中情況相同。根據(jù)上圖中最高命中情況，共有7次頁(yè)命中（折算為7×1024次單元命中）

15、，5次頁(yè)不命中（折算為5×1023次單元命中，也可寫(xiě)為5×1024-5），單元訪(fǎng)問(wèn)總次數(shù)為12×1024，故有： Hcell=(12×1024-5)/(12×1024)=12283/12288≈99.96% 3.15加1題 一個(gè)二級(jí)存儲(chǔ)層次，采用全相聯(lián)映象和最久沒(méi)有使用算法，實(shí)存共5頁(yè)，為2道程序分享，頁(yè)地址流分別如下 P1 = 1 2 3 4 1 3 2 1 P2 = 1 2 3 4 2 2 3 3 試作2個(gè)實(shí)存分配方案，分別使2道程序滿(mǎn)足 (1)命中率相同； (2)命中次數(shù)之和最大。 P1 = 1 2 3 4 1 3 2 1

16、 命中次數(shù)N(1) 1 2 3 4 1 3 2 1 1 2 3 4 1 3 2 1 2 3 4 1 3 1 2 2 4 4 n1= 1 0 n1= 2 0 n1= 3 √ √ 2 n1= 4 √ √ √ √ 4 解：分別為2道程序作“堆棧模擬圖”，其中“√”表示命中。 P2 = 1 2 3 4 2

17、2 3 3 命中次數(shù)N(2) 1 2 3 4 2 2 3 3 1 2 3 4 4 2 2 1 2 3 3 4 4 1 1 1 1 1 n2= 1 √ √ 2 n2= 2 √ √ 2 n2= 3 √ √ √ √ 4 n2= 4 √ √ √ √ 4 6 5 N(1)+N(2) 4 3 2

18、 N(1) N(2) 1 1+4 2+3 3+2 4+1 將兩圖結(jié)果綜合，得到4個(gè)分配方案的命中率情況表如下 n1 1 2 3 4 N(1) 0 0 2 4 n2 4 3 2 1 N(2) 4 4 2 2 N(1)+N(2) 4 4 4 6 結(jié)論如下 (1)命中率相同的方案是n1= 3而n2= 2； (2)命中次數(shù)之和最大的方案是n1= 4而n2= 1。 3.19中(3)(4)(6)(8)問(wèn) 虛存 實(shí)

19、頁(yè) 0 1 2 3 虛組0 0 0 √ √ 1 實(shí)存 1 √ √ 虛組1 2 · 0 實(shí)組0 2 √ √ 3 · 1 虛 3 √ √ 虛組2 4 · 2 實(shí)組1 頁(yè) 4 √ √ 5 · 3 5 √ √ 虛組3 6 6 √ √ 7 7 √ √ (a) 虛頁(yè)集合與實(shí)頁(yè)集合的對(duì)應(yīng)關(guān)系 (b) 對(duì)應(yīng)關(guān)系表（√為有關(guān)系） (3)

20、(4)通過(guò)作“實(shí)存狀況圖”模擬各虛塊的調(diào)度情況，可獲得Cache的塊地址流序列。 P= 6 2 4 1 4 6 3 0 4 5 7 3 C0 4 4* 4 4 4 4* 4 4* 4* 4* C1 1 1* 1* 1* 0 0* 5 5 5 C2 6 6* 6* 6* 6* 6 6* 6* 6* 6* 7 7* C3 2 2 2 2 2* 3 3 3 3 3* 3 入 入 入 入 中 中 替 替 中 替 替 中 C= 2

21、 3 0 1 0 2 3 1 0 1 2 3 此問(wèn)最容易出錯(cuò)的地方是忽略“組相聯(lián)”地址約束，將虛頁(yè)裝錯(cuò)實(shí)組。另外沒(méi)有及時(shí)標(biāo)注“*”號(hào)也容易導(dǎo)致淘汰對(duì)象錯(cuò)誤。 (6)H=4/12≈33% (8)做法同3.15題(3)問(wèn)，Hcell=(12×16-8)/(12×16)≈95.8% 第四章(P250) 時(shí)間 中斷請(qǐng)求 主程序 1級(jí) 2級(jí) 3級(jí) 4級(jí) D1，D2 D3，D4 4.5 已知中斷服務(wù)次序?yàn)?-2-4-1，。 (1)中斷屏蔽字表如下圖； D1 D2 D3 D4 D1 0 1 1 1 D

22、2 0 0 1 0 D3 0 0 0 0 D4 0 1 1 0 (2)中斷過(guò)程示意圖如右圖。 4.8 (1)f=2×105字節(jié)/秒，T=5us (2)Ts+Td=5us，通道時(shí)間圖如下。作圖時(shí)注意：至少要畫(huà)到最慢設(shè)備的第二次請(qǐng)求出現(xiàn)，才能確定是否丟失數(shù)據(jù)（因?yàn)轫憫?yīng)優(yōu)先級(jí)低的設(shè)備較易丟失數(shù)據(jù)）。 設(shè) 優(yōu) 備 先 號(hào) 級(jí) D1 1 D2 4 D3 2 D4 3 時(shí)間 (us) 0 10 20 30 40 50 60 70 80 90 100 110 120 130 14

23、0 150 160 170 (3)5，160，20，40； (4)D2丟失第一次請(qǐng)求的數(shù)據(jù)； (5)參見(jiàn)P245。 第五章(P343) 5.9 為了縮短運(yùn)算時(shí)間，首先應(yīng)考慮“最少切換算法”，即先執(zhí)行完所有乘法（任務(wù)編號(hào)1-6）再執(zhí)行加法（任務(wù)編號(hào)7-11），其次在加法中采用“最少相關(guān)算法”（即二叉樹(shù)算法）。 記c1=A1×B1，……，c6=A6×B6，下圖(a)是加法的計(jì)算順序二叉樹(shù)，注意任務(wù)10應(yīng)該用前一級(jí)最早完成的任務(wù)7和8的結(jié)果，如果用任務(wù)9的結(jié)果則要推遲1拍啟動(dòng)，使總時(shí)間增加1拍。 F=c1+c2+c3+c4+c5+c6 6 1

24、2 3 4 5 6 7 8 9 10 11 5 1 2 3 4 5 6 7 8 9 4 1 2 3 4 5 6 3 7 8 9 10 11 10 2 7 8 9 10 11 1 1 2 3 4 5 6

25、 7 8 9 10 11 11 0 1 2 3 4 5 6 7 8 9 12 14 15 18 22 (a) (b) 根據(jù)時(shí)空?qǐng)D(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/3 5.15 Δt=10ns=10-8秒 (1)F={1，2，5}，C=(10011) (2)狀態(tài)轉(zhuǎn)移圖如下圖

26、(a)所示。 (3)最小啟動(dòng)循環(huán)=（3）,最小平均啟動(dòng)距離=3Δt。 (4)插入2個(gè)延遲，最小啟動(dòng)循環(huán)=（2）,最小平均啟動(dòng)距離=2Δt。 (5)新預(yù)約表如下圖(b)所示。 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 × ×

27、 2 5 D1 × 1 0 1 0 1 0 1 1 0 0 0 1 1 1 D2 × 2 5 (a) (b) (c) (6)F={1，3，7}，C=(1000101)，狀態(tài)轉(zhuǎn)移圖如下圖(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，如下圖所示。

28、 S4 1 1 2 2 3 10 10 S3 1 2 3 ……… 10 S2 1 1 2 2 3 10 10 S1 1 2 1 3 2 10 10 3 t (a) 插入前 9×3 6 D2

29、1 2 3 11 D1 1 2 3 4 10 S4 1 1 2 2 3 3 ……… 10 10 S3 1 2 3 4 10 S2 1 2 1 3 2 4 3 5 10 10 S1 1 2 3 4 1 5 2 10 10 2 t (b) 插入后

30、 9×2 8 第六章(P391) 6.6（注意閱讀P372倒數(shù)第9行－倒數(shù)第6行） (4) V0 ← 存儲(chǔ)器 鏈接 V1 ← 1 / V0 鏈接 V3 ← V1 + V2 鏈接 V5 ← V3 * V4 訪(fǎng)存 倒數(shù) 加 乘 8 16 8 9 31 總拍數(shù)=72（各條依次鏈接） (3) V0 ← 存儲(chǔ)器 并行 V3 ← V1 + V2 鏈接 V4 ← V0 * V3 V6 ← V4 + V5 串行 訪(fǎng)存

31、 加 乘 8 9 31 8 31 總拍數(shù)=87（第4條功能部件沖突） 已知n=32，k加=6，k乘=7，k訪(fǎng)存=6，k倒數(shù)=14，啟動(dòng)、輸出延遲各1。求各小題總拍數(shù)。 (1) V0 ← 存儲(chǔ)器 V1 ← V2 + V3 并行 V4 ← V5 * V6 訪(fǎng)存 加 乘 9 31 總拍數(shù)=40（并行執(zhí)行，以最長(zhǎng)指令為準(zhǔn)） (2) V2 ← V0 * V1 并行 V3 ← 存儲(chǔ)器 V4 ← V2 + V3 串行（P372） 乘 訪(fǎng)存

32、 加 9 31 8 31 總拍數(shù)=79（第3條錯(cuò)過(guò)時(shí)機(jī)，不能鏈接） (5) V0 ← 存儲(chǔ)器 V1 ← V2 + V3 并行 V4 ← V5 * V6 s0 ← s1 + s2 串行 訪(fǎng)存 加 乘 9 31 8 總拍數(shù)=48（標(biāo)量看成1個(gè)分量的向量） (6) V3 ← 存儲(chǔ)器 并行 V2 ← V0 + V1 串行 s0 ← s2 + s3 并行 V3 ← V1 * V4 訪(fǎng)存 加 乘 8 31 9 31 總

33、拍數(shù)=79（標(biāo)量看成1個(gè)分量的向量） (7) V3 ← 存儲(chǔ)器 并行 V2 ← V0 + V1 鏈接 V4 ← V2 * V3 存儲(chǔ)器 ← V4 串行 訪(fǎng)存 加 乘 8 9 31 8 31 總拍數(shù)=87（第4條功能部件沖突） (8) V0 ← 存儲(chǔ)器 鏈接 V2 ← V0 + V1 V3 ← V2 * V1 串行 V5 ← V3 * V4 串行 訪(fǎng)存 加 乘 8 8 31 9 31 9 31 總拍數(shù)=127（Vi沖突，功能部件沖突） 6.

34、10 已知向量速率Rv = 10MFLOPS，標(biāo)量速率Rs = 1MFLOPS，并記α為可向量化百分比。 (1) 推導(dǎo)法1：使用Amdahl定律，在這里可將標(biāo)量速率Rs作為原速率，局部加速后的速率為向量速率Rv，于是局部加速比Se=10，全局加速比為 再根據(jù)加速比的定義，，所以有。 （若將向量速率Rv作為原速率，局部減速后的速率為標(biāo)量速率Rs，則局部加速比Se=0.1，推出的全局加速比Sn同上式。） 推導(dǎo)法2：為了推導(dǎo)，定義T為總時(shí)間，N為總?cè)蝿?wù)數(shù)。于是有平均速率Ra = 吞吐率TP = N/T。記N = Nv + Ns，且，則，于是有Nv = α·N和Ns = (1-α

35、)·N 顯然：總時(shí)間 所以： 或者： Ra (MFLOPS) 10 1 0 1 α (2) 已知Rv = 10MFLOPS，Rs = 1MFLOPS， Ra與α的關(guān)系圖如右圖所示。 (3) 已知Ra = 7.5MFLOPS，解出 (4) 已知Ra = 2MFLOPS，α = 0.7，解出 第七章(P446) 7.3 已知輸入端編號(hào)13 = 1101B。 (1)Cube3(1101B) = 0101B = 5 (2)PM2+3(13) = (13 + 23)mod 16 = 21 mod 16 = 5

36、 (3)PM2+0(13) = (13 - 20)mod 16 = 12 (4)Shuffle(1101B) = 1011B = 11 (5)Shuffle(Shuffle(1101B)) = Shuffle(1011B) = 0111B = 7 7.4 用多級(jí)混洗―交換網(wǎng)絡(luò)，n = 4，拓?fù)浣Y(jié)構(gòu)同教材P410圖7.21(e)，控制信號(hào)=1010B，自左向右各級(jí)交換開(kāi)關(guān)狀態(tài)依次為交換―直連―交換―直連。 7.5 輸入結(jié)點(diǎn)編號(hào)j = 9，f(j) = j⊕控制信號(hào) = 1001B⊕1100B = 0101B = 5，答為5號(hào)處理機(jī)。 7.6 直連狀態(tài)時(shí)：編號(hào)在第i位不同的結(jié)

37、點(diǎn)之間不能通信； 交換狀態(tài)時(shí)：編號(hào)在第i位相同的結(jié)點(diǎn)之間不能通信。 7.7 用單級(jí)混洗―交換網(wǎng)可實(shí)現(xiàn)，總共混洗3步。 證：設(shè)矩陣A = (aij)8×8按行展開(kāi)依次存放在64個(gè)單元中，則任意元素aij的地址為8i + j，而aji的地址為8j + i。按混洗函數(shù)的定義，3次混洗后，shuffle3(8i + j) = 8×(8i + j) mod 63 = i + 8j，也就說(shuō)將元素aij地址變換成aji的地址。由于aij是矩陣中的任意元素，所以3次混洗可實(shí)現(xiàn)矩陣轉(zhuǎn)置(aij)T8×8=(aji)8×8。 7.8 最多5級(jí)，因?yàn)閷?duì)于任給的輸入結(jié)點(diǎn)編號(hào)j=X6X5X4X3X2X

38、1X0，PM2I多級(jí)網(wǎng)絡(luò)中i=2級(jí)的功能是PM2±2(j)=j±22 mod 128，±22運(yùn)算只有可能改變j中的X6～X2，所以最多使用Cube6～Cube2就能實(shí)現(xiàn)代換了。 7.9 由于N = 16，即n = 4，每個(gè)結(jié)點(diǎn)編號(hào)用4位二進(jìn)制數(shù)表示。PM2±0函數(shù)功能是對(duì)結(jié)點(diǎn)編號(hào)加1或減1，其結(jié)果最多可將編號(hào)的4位都取反（如1111B + 1 = 0000B），所以用每步只能對(duì)1位取反的單級(jí)立方體網(wǎng)絡(luò)來(lái)模仿，最差情況下要4步。 7.10 用混洗―交換網(wǎng)絡(luò)模擬Cube網(wǎng)。 當(dāng)模擬Cube0功能時(shí)，只需一次交換即可完成；而模擬Cubei且i≠0時(shí)，需先作n – i步混洗，再作1步

39、交換，最后作i步混洗才能完成，共計(jì)n + 1步。 綜上所述，下限為1步，上限為n + 1步。 7.11 求單級(jí)立方體網(wǎng)絡(luò)和單級(jí)混洗―交換網(wǎng)絡(luò)的最大廣播步數(shù)，這兩種網(wǎng)絡(luò)的最大廣播步數(shù)與最大距離（即直徑）相同。 (1)單級(jí)立方體網(wǎng)絡(luò)直徑 = n（Cuben-1～Cube0各1次）； (2)單級(jí)混洗―交換網(wǎng)絡(luò)直徑 = 2n-1（n-1次混洗，n次交換）。 7.12 已知N = 16，用多級(jí)立方體網(wǎng)絡(luò)或者多級(jí)混洗―交換網(wǎng)絡(luò)均能實(shí)現(xiàn)，兩者可以互相模擬，對(duì)同一置換的尋徑算法相同，控制信號(hào)也相同，下面以多級(jí)立方體網(wǎng)絡(luò)為例分析。 4組4元交換：f1 = Cube1Cube0； 2

40、組8元交換：f2 = Cube2Cube1Cube0； 1組16元交換：f3 = Cube3Cube2Cube1Cube0； 利用Cube函數(shù)的結(jié)合律、交換律以及同一律（又稱(chēng)自反律）可以推得 f = f1f2f3 = Cube3Cube1Cube0 拓?fù)浣Y(jié)構(gòu)圖略（可參考7.26題的多級(jí)混洗―交換網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖）。 網(wǎng)絡(luò)開(kāi)關(guān)使用級(jí)控方式，控制信號(hào)為1011B（其中biti控制級(jí)i，“0”表示直連，“1”表示交換）。 7.13 N = 8的蝶式置換。 (1) f(X2X1X0) = X0X1X2； (2) 至少需2次通過(guò)，每次都是N個(gè)數(shù)據(jù)同時(shí)發(fā)送，同時(shí)接收，中途不儲(chǔ)

41、存； (3) 控制信號(hào)的設(shè)置有4種方案，如下所示。其中“0”表示直連，“1”表示交換。 101 100 001 101 000 000 000 000 000 000 000 000 101 100 001 101 000 000 000 000 101 100 001 101 101 100 001 101 000 000 000 000 7.14 (1) 共N!種； (2) 一次通過(guò)有種不同； (3) N = 8時(shí)，百分比 = 7.2

42、6(1)～(3)； (1)見(jiàn)下圖實(shí)線(xiàn)。 (2)見(jiàn)下圖虛線(xiàn)；不會(huì)阻塞，因?yàn)閮蓷l路徑的控制信號(hào)都是1110，形成級(jí)控模式，所以不會(huì)阻塞。 (3)一次通過(guò)實(shí)現(xiàn)的置換數(shù)為16 8 = 4294967296，全部置換數(shù)為N! = 20922789888000，前者約占后者的0.02%。 級(jí)3 級(jí)2 級(jí)1 級(jí)0 0000 0000 0001 0001 0010 0010 0011 0011 0100

43、 0100 0101 0101 0110 0110 0111 0111 1000 1000 1001 1001 1010 1010 1011 1011 1100 1100 1101 1101 1110 1110 1111

44、 1111 7.27 (1) 已知N = 64，n = 6，源結(jié)點(diǎn)s = 101101B，目的結(jié)點(diǎn)d = 011010B，方向矢量r = s⊕d = 110111B，以低維度優(yōu)先順序?qū)?，路徑? s = 101101B → 101100B → 101110B → 101010B → 111010B → 011010B = d （下劃線(xiàn)為當(dāng)前尋徑維） (2) 求給定無(wú)向圖中2棵選播樹(shù)（即生成樹(shù)）。 (i) 求最小成本生成樹(shù)（通道數(shù)最少），可考慮Prim算法、Kruskal算法或標(biāo)記法。一個(gè)參考操作方法是：先對(duì)臨近結(jié)點(diǎn)群分別構(gòu)造最短子樹(shù)，然后在子

45、樹(shù)之間作最短互連。 (ii) 求由結(jié)點(diǎn)(3,5)出發(fā)的單源最短路徑生成樹(shù)（各距離最短），可考慮貪心算法。對(duì)X-Y網(wǎng)格圖來(lái)說(shuō)，從樹(shù)根到某一樹(shù)葉的任何路徑只要在各維均無(wú)反向移動(dòng)即為最短路徑（滿(mǎn)足此條件的最短路徑有多條）。要得到單一樹(shù)根對(duì)于多片樹(shù)葉的綜合最短路徑，可以先分別作出各條單播最短路徑，然后在不增加各路徑長(zhǎng)度的前提下，盡可能地進(jìn)行路段合并。 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

46、 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,2 Y 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 這兩小問(wèn)結(jié)果如下圖所示（其中b圖第一步必須選擇向下，而不能向右）。 0,7 1,7 2,7 3,7 4,7 5,7 6,7 7,7

47、 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,2 Y 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

48、 X (a) (b) (3) 求作超立方體貪心選播樹(shù)。 7.29 已知N = 256，n = 8，起始結(jié)點(diǎn)編號(hào)j = 123 = 01111011B。根據(jù)混洗函數(shù)的循環(huán)移位性質(zhì)，Shuffle10(j) = Shuffle2(j) = 11101101B = 237 第八章(P498) 8.12 問(wèn)題為S=A1×B1+……+A32×B32，其中T乘=4Δt，T加=2Δt，T傳=1Δt。 (1) 在串行計(jì)算機(jī)上，各操作不論是否相關(guān)均不能重疊，總時(shí)間恒等于各操作單獨(dú)時(shí)間之和，所以不必考慮運(yùn)算順序。T=32·T乘+31·T加=(32×4

49、+31×2)Δt=190Δt (2) 設(shè)此雙向環(huán)可以并行傳送（即為“移數(shù)環(huán)”，因?yàn)镾IMD系統(tǒng)各種數(shù)據(jù)操作都能并行）。 按平均分配原則，每個(gè)結(jié)點(diǎn)內(nèi)有4對(duì)數(shù)據(jù)。 首先在各結(jié)點(diǎn)用串行算法它們的相乘與求和，需時(shí)T1=4·T乘+3·T加=(4×4+3×2)Δt=22Δt； 然后用二叉樹(shù)并行算法將8個(gè)結(jié)點(diǎn)中的部分和相加（見(jiàn)下圖），其中并行加法需3次，每次時(shí)間相同，而并行傳送3次的每次時(shí)間卻隨距離倍增，依次為1、2、4步，所以有T2=(1+2+4)·T傳+3·T加=(7×1+3×2)Δt=13Δt； 總時(shí)間T=T1+T2=35Δt s = s1 + s2 + s3 +

50、 s4 + s5 + s6 + s7 + s8 ①.右傳20步 加法1步 ②.右傳21步 加法1步 ③.右傳22步 加法1步 第九章(P562) 9.18 問(wèn)題為S=(A1+B1)×……×(A8+B8)，其中T加=30ns，T乘=50ns，T傳=10ns。 將加法記為任務(wù)1-8，乘法記為任務(wù)9-15。 (1) 在串行計(jì)算機(jī)上，同8.12題1問(wèn)分析，共計(jì)15步運(yùn)算，T=8·T加+7·T乘=(8×30+7×50)ns=590ns。 (2) 多功能部件SISD計(jì)算機(jī)的工作方式可參考P346題18(3)。 為了充分利用加法器與乘法

51、器的可并行性，盡量讓加法與乘法交替進(jìn)行，可自左向右順序運(yùn)算（見(jiàn)下圖）。T=2·T加+7·T乘=(2×30+7×50)ns=410ns 15 8 14 7×50ns A8 B8 7 13 乘法 9 10 11 12 15 加法 1 2 3 4 5 6 7 8 A7 B7 8×30ns 9 2 1 A2 B2 A1 B1 (3) 同8.12題2問(wèn)，設(shè)單向環(huán)可以并行傳送（即為“移數(shù)環(huán)”，理由同

52、8.12題2問(wèn)）。 1 2 3 4 5 6 7 8 10 20 40 2 4 6 8 傳送 4 8 乘法 50 50 50 8 加法 30 T=T加+3·T乘+(1+2+4)·T傳=(30+3×50+7×10)ns=250ns (4)在全互連網(wǎng)絡(luò)上，任意兩個(gè)結(jié)點(diǎn)之間的距離均為1步，所以任何置換都能在1步完成，故 10 10 10 傳送 乘法 50 50 50 加法 30 T=T加+3·T乘+(1+1+1)·T傳=(30+3×50+3×10)ns=210ns 18