清華大學(xué)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)課后習(xí)題答案-資料下載頁
2025-06-22 16:47本頁面
【正文】 01010110 01100111 01111000 10001001 10011010 10101011 10111100 11001101 11011110 11101111 1111(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 （下劃線為當(dāng)前尋徑維）(2) 求給定無向圖中2棵選播樹（即生成樹）。 (i) 求最小成本生成樹（通道數(shù)最少），可考慮Prim算法、Kruskal算法或標(biāo)記法。一個(gè)參考操作方法是：先對(duì)臨近結(jié)點(diǎn)群分別構(gòu)造最短子樹，然后在子樹之間作最短互連。 (ii) 求由結(jié)點(diǎn)(3,5)出發(fā)的單源最短路徑生成樹（各距離最短），可考慮貪心算法。對(duì)XY網(wǎng)格圖來說，從樹根到某一樹葉的任何路徑只要在各維均無反向移動(dòng)即為最短路徑（滿足此條件的最短路徑有多條）。要得到單一樹根對(duì)于多片樹葉的綜合最短路徑，可以先分別作出各條單播最短路徑，然后在不增加各路徑長度的前提下，盡可能地進(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 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圖第一步必須選擇向下，而不能向右）。 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 (a) (b)(3) 求作超立方體貪心選播樹。 已知N = 256，n = 8，起始結(jié)點(diǎn)編號(hào)j = 123 = 01111011B。根據(jù)混洗函數(shù)的循環(huán)移位性質(zhì)，Shuffle10(j) = Shuffle2(j) = 11101101B = 237第八章(P498) 問題為S=A1B1+……+A32B32，其中T乘=4Δt，T加=2Δt，T傳=1Δt。(1) 在串行計(jì)算機(jī)上，各操作不論是否相關(guān)均不能重疊，總時(shí)間恒等于各操作單獨(dú)時(shí)間之和，所以不必考慮運(yùn)算順序。T=32T乘+31T加=(324+312)Δ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=4T乘+3T加=(44+32)Δt=22Δt； 然后用二叉樹并行算法將8個(gè)結(jié)點(diǎn)中的部分和相加（見下圖），其中并行加法需3次，每次時(shí)間相同，而并行傳送3次的每次時(shí)間卻隨距離倍增，依次為4步，所以有T2=(1+2+4)T傳+3T加=(71+32)Δt=13Δt； 總時(shí)間T=T1+T2=35Δts = s1 + s2 + s3 + s4 + s5 + s6 + s7 + s8①.右傳20步 加法1步②.右傳21步 加法1步③.右傳22步 加法1步第九章(P562) 問題為S=(A1+B1)……(A8+B8)，其中T加=30ns，T乘=50ns，T傳=10ns。 將加法記為任務(wù)18，乘法記為任務(wù)915。(1) 在串行計(jì)算機(jī)上，共計(jì)15步運(yùn)算，T=8T加+7T乘=(830+750)ns=590ns。(2) 多功能部件SISD計(jì)算機(jī)的工作方式可參考P346題18(3)。 為了充分利用加法器與乘法器的可并行性，盡量讓加法與乘法交替進(jìn)行，可自左向右順序運(yùn)算（見下圖）。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) ，設(shè)單向環(huán)可以并行傳送（即為“移數(shù)環(huán)”，）。 1 2 3 4 5 6 7 8 10 20 40 2 4 6 8 傳送 4 8 乘法 50 50 50 8 加法 30T=T加+3T乘+(1+2+4)T傳=(30+350+710)ns=250ns(4)在全互連網(wǎng)絡(luò)上，任意兩個(gè)結(jié)點(diǎn)之間的距離均為1步，所以任何置換都能在1步完成，故 10 10 10 傳送 乘法 50 50 50 加法 30T=T加+3T乘+(1+1+1)T傳=(30+350+310)ns=210ns17
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1