清華大學(xué)計算機系統(tǒng)結(jié)構(gòu)課后習(xí)題答案(完整版)
【正文】 (a)是加法的計算順序二叉樹，注意任務(wù)10應(yīng)該用前一級最早完成的任務(wù)7和8的結(jié)果，如果用任務(wù)9的結(jié)果則要推遲1拍啟動，使總時間增加1拍。 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)（注意閱讀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。N和Ns = (1α)按混洗函數(shù)的定義，3次混洗后，shuffle3(8i + j) = 8(8i + j) mod 63 = i + 8j，也就說將元素aij地址變換成aji的地址。0函數(shù)功能是對結(jié)點編號加1或減1，其結(jié)果最多可將編號的4位都取反（如1111B + 1 = 0000B），所以用每步只能對1位取反的單級立方體網(wǎng)絡(luò)來模仿，最差情況下要4步。 網(wǎng)絡(luò)開關(guān)使用級控方式，控制信號為1011B（其中biti控制級i，“0”表示直連，“1”表示交換）。 (i) 求最小成本生成樹（通道數(shù)最少），可考慮Prim算法、Kruskal算法或標(biāo)記法。根據(jù)混洗函數(shù)的循環(huán)移位性質(zhì)，Shuffle10(j) = Shuffle2(j) = 11101101B = 237第八章(P498) 問題為S=A1B1+……+A32B32，其中T乘=4Δt，T加=2Δt，T傳=1Δt。T加=(44+32)Δt=22Δt； 然后用二叉樹并行算法將8個結(jié)點中的部分和相加（見下圖），其中并行加法需3次，每次時間相同，而并行傳送3次的每次時間卻隨距離倍增，依次為4步，所以有T2=(1+2+4) 為了充分利用加法器與乘法器的可并行性，盡量讓加法與乘法交替進行，可自左向右順序運算（見下圖）。T傳=(30+350+310)ns=210ns17。T加+7T加=(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=32 (ii) 求由結(jié)點(3,5)出發(fā)的單源最短路徑生成樹（各距離最短），可考慮貪心算法。(1) f(X2X1X0) = X0X1X2；(2) 至少需2次通過，每次都是N個數(shù)據(jù)同時發(fā)送，同時接收，中途不儲存；(3) 控制信號的設(shè)置有4種方案，如下所示。 當(dāng)模擬Cube0功能時，只需一次交換即可完成；而模擬Cubei且i≠0時，需先作n – i步混洗，再作1步交換，最后作i步混洗才能完成，共計n + 1步。 最多5級，因為對于任給的輸入結(jié)點編號j=X6X5X4X3X2X1X0，PM2I多級網(wǎng)絡(luò)中i=2級的功能是PM2177。(3) 已知Ra = ，解出 (4) 已知Ra = 2MFLOPS，α = ，解出 第七章(P446) 已知輸入端編號13 = 1101B。(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條錯過時機，不能鏈接） (5) V0 ← 存儲器 V1 ← V2 + V3 并行 V4 ← V5 * V6 s0 ← s1 + s2 串行訪存加乘 9 31 8總拍數(shù)=48（標(biāo)量看成1個分量的向量）(6) V3 ← 存儲器 并行 V2 ← V0 + V1 串行 s0 ← s2 + s3 并行 V3 ← V1 * V4訪存加乘 8 31 9 31總拍數(shù)=79（標(biāo)量看成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 串行訪存加乘
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1