清華第2版《計算機系統(tǒng)結構》習題解答.doc

《清華第2版《計算機系統(tǒng)結構》習題解答.doc》由會員分享，可在線閱讀，更多相關《清華第2版《計算機系統(tǒng)結構》習題解答.doc（17頁珍藏版）》請在裝配圖網(wǎng)上搜索。

《計算機系統(tǒng)結構》習題解答 目錄 第一章(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） 第七章(P446) 7.3、7.29（互連函數(shù)計算），7.6-7.14（互連網(wǎng)性質），7.4、7.5、7.26（多級網(wǎng)尋徑算法），7.27（尋徑/選播算法） 第八章(P498) 8.12（SISD/SIMD算法） 第九章(P562) 9.18（SISD/多功能部件/SIMD/MIMD算法） (注：每章可選1-2個主要知識點，每個知識點可只選1題。有下劃線者為推薦的主要知識點。) 第一章(P33) 1.7 (1)從指定角度來看，不必要了解的知識稱為透明性概念。 (2)見下表，“√”為透明性概念，“P”表示相關課文頁數(shù)。 模m交叉，√， 浮點數(shù)據(jù)，，P4 通道與I/O處理機，，P4 總線寬度，√， 陣列運算部件，√， 結合型與獨立型通道，√， 單總線，√， 訪問保護，， 中斷，， 指令控制方式，√， 堆棧指令，， 最小編址單位，， Cache存儲器，√， 1.8見下表，“√”為透明性概念，“P”表示相關課文頁數(shù)。 指令地址寄存器，， 指令緩沖器，√， 時標發(fā)生器，√， 條件碼寄存器，， 乘法器，√， 主存地址寄存器，√， 磁盤，， 先行進位鏈，√， 移位器，√， 通用寄存器 ，， 中斷字寄存器，， 1.9見下表，“√”表示都透明，“應”表示僅對應用程序員透明，“”表示都不透明。 數(shù)據(jù)通路寬度，√， 虛擬存儲器，應， Cache存儲器，√， 程序狀態(tài)字，， “啟動I/O”指令，應， “執(zhí)行”指令，， 指令緩沖寄存器，√， Sn 20 1 0 1 Fe 1.12 已知Se=20 , 求作Fe-Sn關系曲線。 將Se代入Amdahl定律得 1.13 上式中令Sn=2，解出Fe=10/19≈0.526 1.14 上式中令Sn=10，解出Fe=18/19≈0.947 1.15 已知兩種方法可使性能得到相同的提高，問哪一種方法更好。 (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)結論：軟件組方法更好。因為硬件組需要將Se再提高100%（20→40），而軟件組只需將Fe再提高1.84%（0.7→0.7184）。 1.17 1.18 記f ── 時鐘頻率，T=1/f ── 時鐘周期，B ── 帶寬（Byte/s）。 方案一： 方案二： 1.19 由各種指令條數(shù)可以得到總條數(shù)，以及各百分比，然后代公式計算。 (1) (2) (3) 1.21 (1) (2) 1.24 記Tc ── 新方案時鐘周期，已知CPI = CPIi = 1 原時間 = CPI IC 0.95Tc = 0.95ICTc 新時間 = （0.32/3+0.7） IC Tc = 0.9ICTc 二者比較，新時間較短。 第二章(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-24 2-53 表數(shù)效率η 100% 100% 2.5 (1) rm = 2，re = 2，p = 24（隱藏最高位）,q = 7。 (2) Nmax = 1.71038，-|N|min = -1.4710-39 δ ≤ 5.9610-8 ≈ 10-7.22，η = 100% 2.6 1位 7位 6位 0 0111111 333333 (1) 0.2 = 0.333333H160 設階碼為移-63碼（即-26+1，原題未指明） 0.2 = 0.110011001100110011001101B2-2 1位 8位 23位 0 01111101 10011001100110011001101 （其中最高有效位需隱藏） 階碼為移-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擴展編碼 平均碼長L 2.99 3.1 3.2 信息冗余量R 1.10% 4.61% 7.59% 2.15 (1) 15條/63條/64條 (2) 14條/126條/128條 第三章(P202) 3.3 直接代公式計算存儲層次性能指標。 (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=0.1 依題意有 整理得0.9n≥0.2，解出，向下取整，得15； 按另一種題意理解是向上取整，得16，也對。 3.15 欲知可能的最高命中率及所需的最少主存頁數(shù)，較好的辦法是通過“堆棧模擬法”，求得命中次數(shù)隨主存頁數(shù)變化的函數(shù)關系。下圖就是“堆棧模擬圖”，其中“√”表示命中。 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 0 n=2 √ 1 n=3 √ √ √ 3 n=4 √ √ √ √ √ √ √ 7 n=5 √ √ √ √ √ √ √ 7 (1)Hmax=7/12≈58.3% (2)n=4 (3)當1次頁面訪問代表連續(xù)1024次該頁內存儲單元訪問時，后1023次單元訪問肯定是命中的，而第1次單元訪問的命中情況與這1次頁面訪問的命中情況相同。根據(jù)上圖中最高命中情況，共有7次頁命中（折算為71024次單元命中），5次頁不命中（折算為51023次單元命中，也可寫為51024-5），單元訪問總次數(shù)為121024，故有： Hcell=(121024-5)/(121024)=12283/12288≈99.96% 3.15加1題 一個二級存儲層次，采用全相聯(lián)映象和最久沒有使用算法，實存共5頁，為2道程序分享，頁地址流分別如下 P1 = 1 2 3 4 1 3 2 1 P2 = 1 2 3 4 2 2 3 3 試作2個實存分配方案，分別使2道程序滿足 (1)命中率相同； (2)命中次數(shù)之和最大。 P1 = 1 2 3 4 1 3 2 1 命中次數(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 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 N(1) N(2) 1 1+4 2+3 3+2 4+1 將兩圖結果綜合，得到4個分配方案的命中率情況表如下 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 結論如下 (1)命中率相同的方案是n1= 3而n2= 2； (2)命中次數(shù)之和最大的方案是n1= 4而n2= 1。 3.19中(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= 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 3 0 1 0 2 3 1 0 1 2 3 此問最容易出錯的地方是忽略“組相聯(lián)”地址約束，將虛頁裝錯實組。另外沒有及時標注“*”號也容易導致淘汰對象錯誤。 (6)H=4/12≈33% (8)做法同3.15題(3)問，Hcell=(1216-8)/(1216)≈95.8% 第四章(P250) 時間 中斷請求 主程序 1級 2級 3級 4級 D1，D2 D3，D4 4.5 已知中斷服務次序為3-2-4-1，。 (1)中斷屏蔽字表如下圖； D1 D2 D3 D4 D1 0 1 1 1 D2 0 0 1 0 D3 0 0 0 0 D4 0 1 1 0 (2)中斷過程示意圖如右圖。 4.8 (1)f=2105字節(jié)/秒，T=5us (2)Ts+Td=5us，通道時間圖如下。作圖時注意：至少要畫到最慢設備的第二次請求出現(xiàn)，才能確定是否丟失數(shù)據(jù)（因為響應優(yōu)先級低的設備較易丟失數(shù)據(jù)）。 設 優(yōu) 備 先 號 級 D1 1 D2 4 D3 2 D4 3 時間 (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丟失第一次請求的數(shù)據(jù)； (5)參見P245。 第五章(P343) 5.9 為了縮短運算時間，首先應考慮“最少切換算法”，即先執(zhí)行完所有乘法（任務編號1-6）再執(zhí)行加法（任務編號7-11），其次在加法中采用“最少相關算法”（即二叉樹算法）。 記c1=A1B1，……，c6=A6B6，下圖(a)是加法的計算順序二叉樹，注意任務10應該用前一級最早完成的任務7和8的結果，如果用任務9的結果則要推遲1拍啟動，使總時間增加1拍。 F=c1+c2+c3+c4+c5+c6 6 1 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 7 8 9 10 11 11 0 1 2 3 4 5 6 7 8 9 12 14 15 18 22 (a) (b) 根據(jù)時空圖(b)得 TP = 11/(22Δt) = 1/(2Δt) S = (64Δt + 54Δt)/(22Δt) = 2 E = (64Δt + 54Δt)/(622Δt) = 1/3 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)所示。 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 (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，如下圖所示。 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) 插入前 93 6 D2 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) 插入后 92 8  第六章(P391) 6.6（注意閱讀P372倒數(shù)第9行－倒數(shù)第6行） (4) V0 ← 存儲器 鏈接 V1 ← 1 / V0 鏈接 V3 ← V1 + V2 鏈接 V5 ← V3 * V4 訪存 倒數(shù) 加 乘 8 16 8 9 31 總拍數(shù)=72（各條依次鏈接） (3) V0 ← 存儲器 并行 V3 ← V1 + V2 鏈接 V4 ← V0 * V3 V6 ← V4 + V5 串行 訪存 加 乘 8 9 31 8 31 總拍數(shù)=87（第4條功能部件沖突） 已知n=32，k加=6，k乘=7，k訪存=6，k倒數(shù)=14，啟動、輸出延遲各1。求各小題總拍數(shù)。 (1) V0 ← 存儲器 V1 ← V2 + V3 并行 V4 ← V5 * V6 訪存 加 乘 9 31 總拍數(shù)=40（并行執(zhí)行，以最長指令為準） (2) V2 ← V0 * V1 并行 V3 ← 存儲器 V4 ← V2 + V3 串行（P372） 乘 訪存 加 9 31 8 31 總拍數(shù)=79（第3條錯過時機，不能鏈接）  (5) V0 ← 存儲器 V1 ← V2 + V3 并行 V4 ← V5 * V6 s0 ← s1 + s2 串行 訪存 加 乘 9 31 8 總拍數(shù)=48（標量看成1個分量的向量） (6) V3 ← 存儲器 并行 V2 ← V0 + V1 串行 s0 ← s2 + s3 并行 V3 ← V1 * V4 訪存 加 乘 8 31 9 31 總拍數(shù)=79（標量看成1個分量的向量） (7) V3 ← 存儲器 并行 V2 ← V0 + V1 鏈接 V4 ← V2 * V3 存儲器 ← V4 串行 訪存 加 乘 8 9 31 8 31 總拍數(shù)=87（第4條功能部件沖突） (8) V0 ← 存儲器 鏈接 V2 ← V0 + V1 V3 ← V2 * V1 串行 V5 ← V3 * V4 串行 訪存 加 乘 8 8 31 9 31 9 31 總拍數(shù)=127（V1沖突，功能部件沖突） 6.10 已知向量速率Rv = 10MFLOPS，標量速率Rs = 1MFLOPS，并記α為可向量化百分比。 (1) 推導法1：使用Amdahl定律，在這里可將標量速率Rs作為原速率，局部加速后的速率為向量速率Rv，于是局部加速比Se=10，全局加速比為 再根據(jù)加速比的定義，，所以有。 （若將向量速率Rv作為原速率，局部減速后的速率為標量速率Rs，則局部加速比Se=0.1，推出的全局加速比Sn同上式。） 推導法2：為了推導，定義T為總時間，N為總任務數(shù)。于是有平均速率Ra = 吞吐率TP = N/T。記N = Nv + Ns，且，則，于是有Nv = αN和Ns = (1-α)N 顯然：總時間 所以： 或者： Ra (MFLOPS) 10 1 0 1 α (2) 已知Rv = 10MFLOPS，Rs = 1MFLOPS， Ra與α的關系圖如右圖所示。 (3) 已知Ra = 7.5MFLOPS，解出 (4) 已知Ra = 2MFLOPS，α = 0.7，解出 第七章(P446) 7.3 已知輸入端編號13 = 1101B。 (1)Cube3(1101B) = 0101B = 5 (2)PM2+3(13) = (13 + 23)mod 16 = 21 mod 16 = 5 (3)PM2+0(13) = (13 - 20)mod 16 = 12 (4)Shuffle(1101B) = 1011B = 11 (5)Shuffle(Shuffle(1101B)) = Shuffle(1011B) = 0111B = 7 7.4 用多級混洗―交換網(wǎng)絡，n = 4，拓撲結構同教材P410圖7.21(e)，控制信號=1010B，自左向右各級交換開關狀態(tài)依次為交換―直連―交換―直連。 7.5 輸入結點編號j = 9，f(j) = j⊕控制信號 = 1001B⊕1100B = 0101B = 5，答為5號處理機。 7.6 直連狀態(tài)時：編號在第i位不同的結點之間不能通信； 交換狀態(tài)時：編號在第i位相同的結點之間不能通信。 7.7 用單級混洗―交換網(wǎng)可實現(xiàn)，總共混洗3步。 證：設矩陣A = (aij)88按行展開依次存放在64個單元中，則任意元素aij的地址為8i + j，而aji的地址為8j + i。按混洗函數(shù)的定義，3次混洗后，shuffle3(8i + j) = 8(8i + j) mod 63 = i + 8j，也就說將元素aij地址變換成aji的地址。由于aij是矩陣中的任意元素，所以3次混洗可實現(xiàn)矩陣轉置(aij)T88=(aji)88。 7.8 最多5級，因為對于任給的輸入結點編號j=X6X5X4X3X2X1X0，PM2I多級網(wǎng)絡中i=2級的功能是PM22(j)=j22 mod 128，22運算只有可能改變j中的X6～X2，所以最多使用Cube6～Cube2就能實現(xiàn)代換了。 7.9 由于N = 16，即n = 4，每個結點編號用4位二進制數(shù)表示。PM20函數(shù)功能是對結點編號加1或減1，其結果最多可將編號的4位都取反（如1111B + 1 = 0000B），所以用每步只能對1位取反的單級立方體網(wǎng)絡來模仿，最差情況下要4步。 7.10 用混洗―交換網(wǎng)絡模擬Cube網(wǎng)。 當模擬Cube0功能時，只需一次交換即可完成；而模擬Cubei且i≠0時，需先作n – i步混洗，再作1步交換，最后作i步混洗才能完成，共計n + 1步。 綜上所述，下限為1步，上限為n + 1步。 7.11 求單級立方體網(wǎng)絡和單級混洗―交換網(wǎng)絡的最大廣播步數(shù)，這兩種網(wǎng)絡的最大廣播步數(shù)與最大距離（即直徑）相同。 (1)單級立方體網(wǎng)絡直徑 = n（Cuben-1～Cube0各1次）； (2)單級混洗―交換網(wǎng)絡直徑 = 2n-1（n-1次混洗，n次交換）。 7.12 已知N = 16，用多級立方體網(wǎng)絡或者多級混洗―交換網(wǎng)絡均能實現(xiàn)，兩者可以互相模擬，對同一置換的尋徑算法相同，控制信號也相同，下面以多級立方體網(wǎng)絡為例分析。 4組4元交換：f1 = Cube1Cube0； 2組8元交換：f2 = Cube2Cube1Cube0； 1組16元交換：f3 = Cube3Cube2Cube1Cube0； 利用Cube函數(shù)的結合律、交換律以及同一律（又稱自反律）可以推得 f = f1f2f3 = Cube3Cube1Cube0 拓撲結構圖略（可參考7.26題的多級混洗―交換網(wǎng)絡拓撲結構圖）。 網(wǎng)絡開關使用級控方式，控制信號為1011B（其中biti控制級i，“0”表示直連，“1”表示交換）。 7.13 N = 8的蝶式置換。 (1) f(X2X1X0) = X0X1X2； (2) 至少需2次通過，每次都是N個數(shù)據(jù)同時發(fā)送，同時接收，中途不儲存； (3) 控制信號的設置有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) 一次通過有種不同； (3) N = 8時，百分比 = 7.26(1)～(3)； (1)見下圖實線。 (2)見下圖虛線；不會阻塞，因為兩條路徑的控制信號都是1110，形成級控模式，所以不會阻塞。 (3)一次通過實現(xiàn)的置換數(shù)為16 8 = 4294967296，全部置換數(shù)為N! = 20922789888000，前者約占后者的0.02%。 級3 級2 級1 級0 0000 0000 0001 0001 0010 0010 0011 0011 0100 0100 0101 0101 0110 0110 0111 0111 1000 1000 1001 1001 1010 1010 1011 1011 1100 1100 1101 1101 1110 1110 1111 1111 7.27 (1) 已知N = 64，n = 6，源結點s = 101101B，目的結點d = 011010B，方向矢量r = s⊕d = 110111B，以低維度優(yōu)先順序尋徑，路徑為 s = 101101B → 101100B → 101110B → 101010B → 111010B → 011010B = d （下劃線為當前尋徑維） (2) 求給定無向圖中2棵選播樹（即生成樹）。 (i) 求最小成本生成樹（通道數(shù)最少），可考慮Prim算法、Kruskal算法或標記法。一個參考操作方法是：先對臨近結點群分別構造最短子樹，然后在子樹之間作最短互連。 (ii) 求由結點(3,5)出發(fā)的單源最短路徑生成樹（各距離最短），可考慮貪心算法。對X-Y網(wǎng)格圖來說，從樹根到某一樹葉的任何路徑只要在各維均無反向移動即為最短路徑（滿足此條件的最短路徑有多條）。要得到單一樹根對于多片樹葉的綜合最短路徑，可以先分別作出各條單播最短路徑，然后在不增加各路徑長度的前提下，盡可能地進行路段合并。 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,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 這兩小問結果如下圖所示（其中b圖第一步必須選擇向下，而不能向右）。 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,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 (a) (b) (3) 求作超立方體貪心選播樹。 7.29 已知N = 256，n = 8，起始結點編號j = 123 = 01111011B。根據(jù)混洗函數(shù)的循環(huán)移位性質，Shuffle10(j) = Shuffle2(j) = 11101101B = 237 第八章(P498) 8.12 問題為S=A1B1+……+A32B32，其中T乘=4Δt，T加=2Δt，T傳=1Δt。 (1) 在串行計算機上，各操作不論是否相關均不能重疊，總時間恒等于各操作單獨時間之和，所以不必考慮運算順序。T=32T乘+31T加=(324+312)Δt=190Δt (2) 設此雙向環(huán)可以并行傳送（即為“移數(shù)環(huán)”，因為SIMD系統(tǒng)各種數(shù)據(jù)操作都能并行）。 按平均分配原則，每個結點內有4對數(shù)據(jù)。 首先在各結點用串行算法它們的相乘與求和，需時T1=4T乘+3T加=(44+32)Δt=22Δt； 然后用二叉樹并行算法將8個結點中的部分和相加（見下圖），其中并行加法需3次，每次時間相同，而并行傳送3次的每次時間卻隨距離倍增，依次為1、2、4步，所以有T2=(1+2+4)T傳+3T加=(71+32)Δt=13Δt； 總時間T=T1+T2=35Δt s = s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8 ①.右傳20步 加法1步 ②.右傳21步 加法1步 ③.右傳22步 加法1步 第九章(P562) 9.18 問題為S=(A1+B1)……(A8+B8)，其中T加=30ns，T乘=50ns，T傳=10ns。 將加法記為任務1-8，乘法記為任務9-15。 (1) 在串行計算機上，同8.12題1問分析，共計15步運算，T=8T加+7T乘=(830+750)ns=590ns。 (2) 多功能部件SISD計算機的工作方式可參考P346題18(3)。 為了充分利用加法器與乘法器的可并行性，盡量讓加法與乘法交替進行，可自左向右順序運算（見下圖）。T=2T加+7T乘=(230+750)ns=410ns 15 8 14 750ns A8 B8 7 13 乘法 9 10 11 12 15 加法 1 2 3 4 5 6 7 8 A7 B7 830ns 9 2 1 A2 B2 A1 B1 (3) 同8.12題2問，設單向環(huán)可以并行傳送（即為“移數(shù)環(huán)”，理由同8.12題2問）。 1 2 3 4 5 6 7 8 10 20 40 2 4 6 8 傳送 4 8 乘法 50 50 50 8 加法 30 T=T加+3T乘+(1+2+4)T傳=(30+350+710)ns=250ns (4)在全互連網(wǎng)絡上，任意兩個結點之間的距離均為1步，所以任何置換都能在1步完成，故 10 10 10 傳送 乘法 50 50 50 加法 30 T=T加+3T乘+(1+1+1)T傳=(30+350+310)ns=210ns