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