計算機體系結(jié)構(gòu)

1、1、有一條流水線如下所示。50ns50ns200ns(1)(2)100ns求連續(xù)輸入10條指令，該流水線的實際吞吐率和效率；該流水線的瓶頸在哪一段？請采取三種不同的措施消除此“瓶頸”。對于你所給出的新流水線，計算連續(xù)輸入10條指令時其實際吞吐率和效率。Tpipeline = EAti + (n - 1)Atmaxi=1解:(1)=(50 + 50 +100 + 200) + 9 x 200=2200(ns)TP = n. = 1220(ns- = TP -pipeline4=- = TP-400 =俐 45.45% m411(2)12*3_13_24_1h4_450ns瓶頸在3、4段。變成八級

2、流水線(細(xì)分)50ns 50ns 50ns 50ns 50nsTpipeline = EAti + (n - 1)Atmax i=1=50 x 8 + 9 x 50=850(ns)TP = nT .= 185(ns-1) pipelineE AtiE = TP- 4= = TP-400 =四牝 58.82%m817 變成兩級流水線(合并) g 4 5* 123Tpipeline200ns200ns=200=2200(ns)=Z A ti + (n - 1) A ti = 1x 2 + 9 x 200max1011牝 90.91%TP = nT. r = /220(ns-1)pipelineE

3、AtiE = TP- i=1= TP- 420重復(fù)設(shè)置部件TP= n.=魅赤-”。x 10.850 x8 =頂妄牝 58.82% pipeline2、如果流水線有m段，各段的處理時間分別是ti （i=1, 2,，m）,現(xiàn)在有n個任務(wù)需 要完成，且每個任務(wù)均需流水線各段實現(xiàn)，請計算：（1）流水線完成這n個任務(wù)所需要的時間；（2）和非流水線實現(xiàn)相比，這n個任務(wù)流水實現(xiàn)的加速比是多少？加速比的峰值是多 少？解：(1)Tpipeiine = 弓 + (n -1)-虹i=1(2)T nopipeline = n tiaxi = 1Speedup =T .nopipelineT pipelineSpeed

4、upmax = m , nm + n - 1(ti = t0)(n m, Speedup m)3、假設(shè)某應(yīng)用程序中有4類操作，通過改進(jìn)，各操作獲得不同的性能提高。具體數(shù)據(jù)如下 表所示：操作類型程序中的數(shù)量 （百萬條指令）改進(jìn)前的執(zhí)行時間（周期）改進(jìn)后的執(zhí)行時間（周期）操作11021操作2302015操作335103操作41541（1）改進(jìn)后，各類操作的加速比分別是多少？（2）各類操作單獨改進(jìn)后，程序獲得的加速比分別是多少?（3）4類操作均改進(jìn)后，整個程序的加速比是多少？解：根據(jù) Amdahl定律Sn = 可得(1 - Fe) + FeSe操作類型各類操作的指令條數(shù)在 程序中所占的比例F各類操作

5、的加速比，各類操作單獨改進(jìn)后， 程序獲得的加速比操作111.1%121.06操作233.3%1.331.09操作338.9%3.331.37操作416.7%41.14Sn4類操作均改進(jìn)后，整個程序的加速比:V V F. “ 216 (1 F.) + -.S.3、計算題：Amdahl定律：加快某部件執(zhí)行速度所能獲得的系統(tǒng)性能加速比，受限于該部件機器檔次的執(zhí)行時間占系統(tǒng)中總執(zhí)行時間的百分比（P7頁）。向上（下）兼容：按某檔機器編制的程序，不加修改就 能運行于比它高（低）檔的機器。向前（后）兼容：按某個時期投入市場的某種型號機器編制的程序，不加修改地就能運行于在它之前（后）投 入市場的機器。向后兼容

6、是系列機的根本特征。兼容機：由不同公司廠家生產(chǎn)的具有相同系統(tǒng)結(jié)構(gòu)的計 算機。4、計算題：哈夫曼樹哈弗曼編碼方法的計算（1）碼長表示法（2）碼點表示 法1）碼長表示法：2-4-6（有三種長度，兩位的、四位的、六位的） 2）碼點表示法：3/6/4 （最短的有三條，最長的有四條，中間長度對應(yīng)為6條）3）24最多碼點數(shù)：13 解釋：2可以有00、01、10、11四種，但是必須是2-4擴(kuò)展至少有一個為兩位，其他的可 以在前面擴(kuò)展兩位，每個可以對應(yīng)四種例如對于01可以變成：0001、0101、1001、1101，所以總共加起來最多只能是3*4+1=13種4）以下四種編碼中：不是2-4擴(kuò)展的是（D）A:1/

7、2B:2/8C:3/4D:4/8大題：有一臺模型機，有以下七種不同的指令，使用頻率表示如下:T1: 20% T2: 12%T3:11% T4: 15% T5: 8%T6:3%T7: 2% T8:18% T9: 10% T10: 1%（1）上圖為哈夫曼編碼圖：平均長度為 2*20%+3* (10%+11%+12%+15%+18%) +4*8%+5*3%+6*(1%+2%)=3.03 可以表示成：00、010、011、100、101、110、1110、11110、111110、111111（2）若用定長操作碼表示至少需要多少位？答：至少需要4位（3）用擴(kuò)展操作碼（只有兩位）可以有多種方式表示，要求

8、平均長度不能大于3.2,給出 最合理的編碼方式，并求出平均編碼長度？采用擴(kuò)展操作碼可以用24擴(kuò)展操作碼的碼點1/9表示：求得平均長度為：1*（20%）+4（80%）=3.43.2 不符合34 的 6/4 編碼方式：平均長度為 3*(10+11+12+15+18+20)%+4*(1+2+3+8)%=3.143.225 編碼中的 3/7 方式：2*（15+18+20）%+5*（1+2+3+8+10+11+12）%=3.413.2 不符合5、流水線指標(biāo)：吞吐率、加速比、效率A吞吐率是指單位時間內(nèi)流水線所完成的任務(wù)數(shù)或輸出結(jié)果的數(shù)量。最大吞吐率是指流水線在連續(xù)流動達(dá)到穩(wěn)定狀態(tài)后所得到的吞吐率。第一種情

9、況：各段時間相等（設(shè)為七。）假設(shè)流水線由m段組成，完成n個任務(wù)。完成n個任務(wù)所需的時間mnTP =T*術(shù)mA） zi te第二種情況:各段時間不等Z-ZvvvTP =. A ti + (n 1) A tjB加速比是指流水線的速度與等功能非流水線的速度之比。S = T非流水/ T流水 若流水線為m段，且各段時間相等，均為At。，則：T非流水=n mAt0T流水=mAt0+ （n1） At0（公式自己代入）C （1）若各段時間相等，則各段的效率ei相等，即e1 = e2 =e3 =、=em=nAt0/T 流水整個流水線的效率為:E=nAt0/T流水=n/ （n+m-1）（2）從時一空圖上看，效率實

10、際上就是n個任務(wù)所占的時空區(qū)與m個段總的時空區(qū)之比，即:n個任務(wù)占用的時空區(qū)E =m個段總的時空區(qū)實例分析:性能分析(分析法，時空圖法).例1.四段流水線，=t3=At4=, At2=3At,4個任務(wù)、10個任務(wù)時TP, n、SP。(1)分析法：各段時間不等n * Atii=l.iSp=Ati+(N-l)*Atj10*6口八zu- =1.8(6+3*9)11n=10T 卜 6*10Atn 4*6At+9*3*4At24+10845%11yp旦1一 6出t+3*9出 At +33*AtTp=4/(6+3*3) At)=4/(15At)-0.267(l/At)r|=24 At / (4*15At)

11、 =2/5=40%Sp=V6 At /15At=8/5=l. 6.n=10時；同上.比較說明:NM流水性能才發(fā)揮得更好的輸入端與輸出端之間的連接交換函數(shù)：實現(xiàn)二進(jìn)制地址編碼中第k位互Exx x x x x .xx一 1 一 2 k+1 k k-11 0 x x x x x x x n-1 n-2k+1 k k-11 0 x x換函數(shù)x1x1主要用于構(gòu)造立方體互連網(wǎng)絡(luò)和各種超立方體互連網(wǎng)絡(luò)。它共有n=log2N種互連函數(shù)。(N 為結(jié)點個數(shù))當(dāng)N=8時，n = 3,可得到常用的立方體互連函數(shù):C x x x x /N=8換函數(shù) 0 )xx )0 1 23 4 56 70 1 2 3 4 5 6 7

12、0 1 2 3 4 5 6 70 1 2 3 4 5 6 7C2交換函數(shù)（b） C1交換函數(shù)均勻洗牌函數(shù)：將輸入端分成數(shù)目相等的兩半，前一半和后一半按類似均勻混洗撲克牌的方 式交叉地連接到輸出端（輸出端相當(dāng)于混洗的結(jié)果） 函數(shù)關(guān)系S（X XXX ）= X XXXX n-1 n-21 0n-2 n-31 0 n-1(a)C0交換函數(shù)(c)即把輸入端的二進(jìn)制編號循環(huán)左移一位。N=8的均勻洗牌和逆均勻洗牌函數(shù)逆均勻洗牌函數(shù)：將輸入端的二進(jìn)制編號循環(huán)右移一位而得到所連接的輸出端編號?；ミB函數(shù)S-1 X X X X ）= X Xn-1 n - 21 00 1 23 4 56 70 1 2 3 4 5 6

13、 70 1 2 3 4 5 6 70 1 2 3 4 5 6 7（a）均勻洗牌函數(shù)X0 n-1 n 一 2（b）逆均勻洗牌函數(shù)逆均勻洗牌是均勻洗牌的逆函數(shù)6、三種通道類型，三種通道與CPU、設(shè)備控制器和外設(shè)的連接關(guān)系，三種類型通道的流量（1）字節(jié)多路通道a為多臺低速或中速的外設(shè)服務(wù)。b以字節(jié)交叉的方式分時輪流地為它 們服務(wù)。c字節(jié)多路通道可以包含多個子通道，每個子通道連接一臺設(shè)備控制器。（2）選擇通道a為多臺高速外圍設(shè)備服務(wù)。b在一段時間內(nèi)只為一臺高速外設(shè)獨占使用。c選擇通道的硬件包括5個寄存器、格式變換部件及通道控制部件（3）數(shù)組多路通道a適用于高速設(shè)備。b每次選擇一個高速設(shè)備后傳送一個數(shù)據(jù)塊，輪流 為多臺外圍設(shè)備服務(wù)。c數(shù)組多路通道之所以能夠并行地為多臺高速設(shè)備服務(wù)，是因為雖然 其所連設(shè)備的傳輸速率很高，但尋址等輔助操作時間很長。通道流量：一個通道在數(shù)據(jù)傳送期間，單位時間內(nèi)能夠傳送的最大數(shù)據(jù)量，一般用字節(jié)個數(shù)來表示。又稱為通道吞吐率，通道數(shù)據(jù)傳輸率等。通道最大流量，一個通道在滿負(fù)荷工作狀態(tài)下的流量。TS：設(shè)備選擇時間。TD：傳送一個字節(jié)所用的時