清華大學(xué)計算機(jī)系統(tǒng)結(jié)構(gòu)課后習(xí)題答案(參考版)
2025-06-25 16:47本頁面
【正文】 T傳=(30+350+310)ns=210ns17。T傳=(30+350+710)ns=250ns(4)在全互連網(wǎng)絡(luò)上，任意兩個結(jié)點(diǎn)之間的距離均為1步，所以任何置換都能在1步完成，故 10 10 10 傳送 乘法 50 50 50 加法 30T=T加+3 1 2 3 4 5 6 7 8 10 20 40 2 4 6 8 傳送 4 8 乘法 50 50 50 8 加法 30T=T加+3T加+7 為了充分利用加法器與乘法器的可并行性，盡量讓加法與乘法交替進(jìn)行，可自左向右順序運(yùn)算（見下圖）。T乘=(830+750)ns=590ns。(1) 在串行計算機(jī)上，共計15步運(yùn)算，T=8T加=(71+32)Δt=13Δt； 總時間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。T加=(44+32)Δt=22Δt； 然后用二叉樹并行算法將8個結(jié)點(diǎn)中的部分和相加（見下圖），其中并行加法需3次，每次時間相同，而并行傳送3次的每次時間卻隨距離倍增，依次為4步，所以有T2=(1+2+4) 首先在各結(jié)點(diǎn)用串行算法它們的相乘與求和，需時T1=4T加=(324+312)Δt=190Δt(2) 設(shè)此雙向環(huán)可以并行傳送（即為“移數(shù)環(huán)”，因?yàn)镾IMD系統(tǒng)各種數(shù)據(jù)操作都能并行）。T=32根據(jù)混洗函數(shù)的循環(huán)移位性質(zhì)，Shuffle10(j) = Shuffle2(j) = 11101101B = 237第八章(P498) 問題為S=A1B1+……+A32B32，其中T乘=4Δt，T加=2Δt，T傳=1Δt。 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) 求作超立方體貪心選播樹。要得到單一樹根對于多片樹葉的綜合最短路徑，可以先分別作出各條單播最短路徑，然后在不增加各路徑長度的前提下，盡可能地進(jìn)行路段合并。 (ii) 求由結(jié)點(diǎn)(3,5)出發(fā)的單源最短路徑生成樹（各距離最短），可考慮貪心算法。 (i) 求最小成本生成樹（通道數(shù)最少），可考慮Prim算法、Kruskal算法或標(biāo)記法。(3)一次通過實(shí)現(xiàn)的置換數(shù)為16 8 = 4294967296，全部置換數(shù)為N! = 20922789888000，%。 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(1) 共N!種；(2) 一次通過有種不同；(3) N = 8時，百分比 = (1)～(3)；(1)見下圖實(shí)線。(1) f(X2X1X0) = X0X1X2；(2) 至少需2次通過，每次都是N個數(shù)據(jù)同時發(fā)送，同時接收，中途不儲存；(3) 控制信號的設(shè)置有4種方案，如下所示。 網(wǎng)絡(luò)開關(guān)使用級控方式，控制信號為1011B（其中biti控制級i，“0”表示直連，“1”表示交換）。 已知N = 16，用多級立方體網(wǎng)絡(luò)或者多級混洗―交換網(wǎng)絡(luò)均能實(shí)現(xiàn)，兩者可以互相模擬，對同一置換的尋徑算法相同，控制信號也相同，下面以多級立方體網(wǎng)絡(luò)為例分析。 求單級立方體網(wǎng)絡(luò)和單級混洗―交換網(wǎng)絡(luò)的最大廣播步數(shù)，這兩種網(wǎng)絡(luò)的最大廣播步數(shù)與最大距離（即直徑）相同。 當(dāng)模擬Cube0功能時，只需一次交換即可完成；而模擬Cubei且i≠0時，需先作n – i步混洗，再作1步交換，最后作i步混洗才能完成，共計n + 1步。0函數(shù)功能是對結(jié)點(diǎn)編號加1或減1，其結(jié)果最多可將編號的4位都取反（如1111B + 1 = 0000B），所以用每步只能對1位取反的單級立方體網(wǎng)絡(luò)來模仿，最差情況下要4步。 由于N = 16，即n = 4，每個結(jié)點(diǎn)編號用4位二進(jìn)制數(shù)表示。22 mod 128，177。 最多5級，因?yàn)閷τ谌谓o的輸入結(jié)點(diǎn)編號j=X6X5X4X3X2X1X0，PM2I多級網(wǎng)絡(luò)中i=2級的功能是PM2177。按混洗函數(shù)的定義，3次混洗后，shuffle3(8i + j) = 8(8i + j) mod 63 = i + 8j，也就說將元素aij地址變換成aji的地址。 用單級混洗―交換網(wǎng)可實(shí)現(xiàn)，總共混洗3步。 輸入結(jié)點(diǎn)編號j = 9，f(j) = j⊕控制信號 = 1001B⊕1100B = 0101B = 5，答為5號處理機(jī)。(3) 已知Ra = ，解出 (4) 已知Ra = 2MFLOPS，α = ，解出 第七章(P446) 已知輸入端編號13 = 1101B。N和Ns = (1α)于是有平均速率Ra = 吞吐率TP = N/T。（若將向量速率Rv作為原速率，局部減速后的速率為標(biāo)量速率Rs，則局部加速比Se=，推出的全局加速比Sn同上式。(1) V0 ← 存儲器 V1 ← V2 + V3 并行 V4 ← V5 * V6訪存加乘 9 31總拍數(shù)=40（并行執(zhí)行，以最長指令為準(zhǔn)）(2) V2 ← V0 * V1 并行 V3 ← 存儲器 V4 ← V2 + V3 串行（P372）乘訪存 加 9 31 8 31總拍數(shù)=79（第3條錯過時機(jī)，不能鏈接）
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1