計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第1

1、計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第1-8章部分作 業(yè)答案第一章1.6某臺(tái)主頻為400MHz的計(jì)算機(jī)執(zhí)行標(biāo)準(zhǔn) 測(cè)試程序，程序中指令類型、執(zhí)行數(shù)量和平均時(shí) 鐘周期數(shù)如下：指令類型指令執(zhí)行數(shù)量平均時(shí)鐘周期數(shù)整數(shù)450001數(shù)據(jù)傳送750002浮點(diǎn)80004分支15002求該計(jì)算機(jī)的有效CPI、MIPS和程序 執(zhí)行時(shí)間。解：(1)CPI = (45000X 1 + 75000X 2+ 8000 X 4+ 1500X 2) / 129500= 1.776(2) MIPS 速率=f/ CPI = 400/1.776 =225.225MIPS(或 5180 mips)(3)程序執(zhí)行時(shí)間=(45000 X 1 + 75000

2、X 2+ 8000X 4+ 1500X 2)/400=575 s1.9假設(shè)某應(yīng)用程序中有4類操作，通過(guò)改 進(jìn)，各操作獲得不同的性能提高。具體數(shù)據(jù)如下 表所示：操作類型程序中的數(shù)量 （百萬(wàn)條指令）改進(jìn)前的執(zhí)行時(shí)間（周期）改進(jìn)后的執(zhí)行時(shí)間（周期）操作11021操作2302015操作335103操作41541（1）改進(jìn)后，各類操作的加速比分別是多少？(2)各類操作單獨(dú)改進(jìn)后，程序獲得的加 速比分別是多少？(3) 4類操作均改進(jìn)后，整個(gè)程序的加速比是多少?可得解：根據(jù)Amdahl定律囪=Fe (1 -Fe)=Se操作類型各類操作的指令條數(shù)在程序中所占的比例Fi各類操作的加速比Si各類操作單獨(dú)改進(jìn)后，

3、程序獲得的加速比操作111.1%21.06操作233.3%1.331.09操作338.9%3.331.37操作416.7%41.144類操作均改進(jìn)后，整個(gè)程序的加速比:Sn-2.16(1R)、Si1.10第二章變長(zhǎng)編碼，哈夫曼編碼第三章3.12有一條指令流水線如下所示：(1) 求連續(xù)輸入10條指令的情況下，該流水線 的實(shí)際吞吐率和效率。(2) 該流水線的瓶頸在哪一段？請(qǐng)采用兩種不 同的措施消除此瓶頸。對(duì)于你所給出的兩種新的 流水線，連續(xù)輸入10條指令時(shí)，其實(shí)際吞吐率 和效率各是多少？解：(1)本題主要考察對(duì)各功能段用時(shí)不等的線性 流水線的性能計(jì)算公式的掌握情況。kT流水八巾(n -1) tma

4、xi 二= (50 50 100 200) 9 200二 2200(ns)TnT 流水二 1220(ns_1)k545.45%11需要充分400Ef TP W注意：對(duì)于公式不能死記硬背，理解，注意公式的適用條件。(2)瓶頸在3、4段。變成八級(jí)流水線(細(xì)分瓶頸段方法)2?4_4巳kT 流水二' ti (n - 1) tmaxi =1=508950=850(ns)T P = n t= 1 85 (ns u )I流水85k':二 tiy400 10E =TP) TP58.82%k817重復(fù)設(shè)置瓶頸段方法58.82%E=400 10850 83.13有一個(gè)流水線由4段組成，其中每當(dāng)流過(guò)

5、 第三段時(shí)，總要在該段循環(huán)一次，然后才能流到 第4段。如果每段經(jīng)過(guò)一次所需的時(shí)間都是 4， 問(wèn)：（1）當(dāng)在流水線的輸入端連續(xù)地每 時(shí)間輸入 一個(gè)任務(wù)時(shí)，該流水線會(huì)發(fā)生什么情況？（2）此流水線的最大吞吐率為多少？如果每 2A t輸入一個(gè)任務(wù)，連續(xù)處理10個(gè)任務(wù)時(shí)，其實(shí)際 吞吐率和效率是多少？（3）當(dāng)每段時(shí)間不變時(shí)，如何提高流水線的吞 吐率？人連續(xù)處理10個(gè)任務(wù)時(shí)，其吞吐率提高 多少？解：（1）會(huì)發(fā)生流水線阻塞情況(2)當(dāng)任務(wù)流過(guò)第三段時(shí)要在該段循環(huán)一次， 相當(dāng)于要占用第三段24時(shí)間，則該流水線可 看成是具有瓶頸段的線性流水線，瓶頸段即第 三段，所需時(shí)間為24。每24輸入一個(gè)任務(wù), 連續(xù)處理10個(gè)

6、任務(wù)的時(shí)空?qǐng)D如下：則:TP12 tmaxT流水二23 tTP =%流水=1%3飢E = TP 5 4 = 509254.35%(3) 重復(fù)設(shè)置部件。重復(fù)的部件可并聯(lián)在流 水線上，也可串聯(lián)于流水線中。如下圖所示：tttttt采用并聯(lián)方式時(shí)的時(shí)空?qǐng)D如下:Stage43_23_12112345678910224466881010! i113355779912345678910i11123456789101tTime914 tTP =% 流水吞吐率提高倍數(shù)=57t =1023't1.643.14有一條靜態(tài)多功能流水線由 5段組成，加 法用1、3、4、5段，乘法用1、2、5段，第3 段的時(shí)間為2

7、牛其余各段的時(shí)間均為 ，而且 流水線的輸出可以直接_應(yīng)的流水線寄存器?，F(xiàn)在該流水線上計(jì)算'4: (Ai Bi)，畫出時(shí)空?qǐng)D，并計(jì)算其吞吐率、加速比i生和效率。解：此題容易出的問(wèn)題是忽略靜態(tài)流水線的特 點(diǎn)，當(dāng)加法任務(wù)流入流水線后緊跟著啟動(dòng)乘法任 務(wù)。正確的做法是當(dāng)所有加法任務(wù)完成從流水線 流出后再啟動(dòng)乘法任務(wù)，同時(shí)還應(yīng)注意到流水線中的第三段所用時(shí)間為24(1 )任務(wù)分析n（4 +爲(wèi)）=（4 + A）x （2+2） x（4 +53）x+尿）7(2 )畫時(shí)空?qǐng)D123456712341234567123456718 (3 )計(jì)算流水線性能吞吐率：TpT 18 t加速比：cT串行4沃5心t +

8、33t 29Sp -T流水18118效率：實(shí)際占用面積4 5.Vt 3 3t 29一時(shí)空區(qū)總面積5x18也t- 903.18 在CRAY-I機(jī)器上，按照鏈接方式執(zhí)行下 述4條向量指令（括號(hào)中給出了相應(yīng)功能部件時(shí) 間），如果向量寄存器和功能部件之間的數(shù)據(jù)傳 送需要1拍，試求此鏈接流水線的通過(guò)時(shí)間是多 少拍？如果向量長(zhǎng)度為64，則需多少拍才能得 到全部結(jié)果。Vg存儲(chǔ)器（從存儲(chǔ)器中取數(shù)：7拍）V2- V0+ V1（向量加：3拍）V*V2v A3（按（A3）左移：4 拍）V5 V3A V4（向量邏輯乘：2拍）解：通過(guò)時(shí)間就是每條向量指令的第一個(gè)操 作數(shù)執(zhí)行完畢需要的時(shí)間，也就是各功能流 水線由空到滿的

9、時(shí)間，具體過(guò)程如下圖所示。 要得到全部結(jié)果，在流水線充滿之后，向量 中后繼操作數(shù)繼續(xù)以流水方式執(zhí)行，直到整 組向量執(zhí)行完畢。T 通過(guò)=(7+1) + (1+3+1) + (1+4+1) + (1+2+1)= 2(拍)T 總共=T 通過(guò)+(64-1)= 23+63=8(拍)說(shuō)明：若考慮數(shù)據(jù)從存儲(chǔ)器送訪存部件也有 1拍 延遲，則通過(guò)時(shí)間應(yīng)為24拍，完成全部任務(wù)所 用時(shí)間相應(yīng)為87拍。3.佃 某向量處理機(jī)有16個(gè)向量寄存器，其中V0-V5種分別存放有向量A,B,C,D,E,F,向量的長(zhǎng) 度是8,向量各元素均為浮點(diǎn)數(shù)；處理部件采用兩 個(gè)單功能流水線，加法功能部件時(shí)間為2拍，乘 法功能部件時(shí)間為3拍。采

10、用類似CRAY-1的鏈 接技術(shù)，先計(jì)算(A+B) X C,在流水線不停的情況 下，接著計(jì)算(D+E) X F。(1) 求此鏈接流水線的通過(guò)時(shí)間是多少拍 ？(設(shè) 寄存器出入各需1拍(2) 假如每排時(shí)間為50ns,完成這些計(jì)算并把 結(jié)果存進(jìn)相應(yīng)寄存器，此處理部件的時(shí)間吞吐率 為多少M(fèi)FLOPS?解：(1) 我們?cè)谶@里假設(shè)A + B的中間結(jié)果放在V6 中，(A + B)X C地最后結(jié)果放在 V7中，D + E 地中間結(jié)果放在 V8中，(D + E)X F的最后結(jié)果放在V9中。具體實(shí)現(xiàn)參考下圖:V0AV1BEl=cV3DV4E向量加V6V2C11V8V5F向量乘V7V9通過(guò)時(shí)間應(yīng)該為前者（A + B）

11、x C）通過(guò)的 時(shí)間：T 通過(guò)=（1+2+1）+（1+3+1） =9（拍）（2）在做完（A+ B）xC之后，作（C + D）x E就不需要通過(guò)時(shí)間了。V6 =A B;V7 =V6 C;V8 = D E;V9 =V8 F;T =T通過(guò)+（81 + 8 = 24（拍）=12OO（ns）=1200X 10（ S）題目中所問(wèn)為吞吐率是多少M(fèi)FLOPS，顯然是讓求以MFLOPS為單位的吞吐率。MFLOPS是 指每秒完成多少百萬(wàn)次浮點(diǎn)運(yùn)算，因此要明確所 有任務(wù)中共多少浮點(diǎn)運(yùn)算。顯然共有4條浮點(diǎn)向 量指令，而每條指令完成8個(gè)浮點(diǎn)運(yùn)算，因此浮點(diǎn)運(yùn)算總數(shù)為32個(gè)。所以：吞吐率：TP = tE2；廠莎廠八 和7

12、MFLOPS第四章4.4假設(shè)有一條長(zhǎng)流水線，僅僅對(duì)條件轉(zhuǎn)移指令 使用分支目標(biāo)緩沖。假設(shè)分支預(yù)測(cè)錯(cuò)誤的開(kāi)銷為 4個(gè)時(shí)鐘周期，緩沖不命中的開(kāi)銷為 3個(gè)時(shí)鐘周 期。假設(shè)：命中率為90%，預(yù)測(cè)精度為90%， 分支頻率為15%，沒(méi)有分支的基本CPI為1。(1) 求程序執(zhí)行的CPI。(2) 相對(duì)于采用固定的2個(gè)時(shí)鐘周期延遲的分 支處理，哪種方法程序執(zhí)行速度更快？解：(1) 程序執(zhí)行的CPI = CPI基本+分支延遲=1+15% X 90% X(1-90%) X 4 =(1-90% ) X 3=1.099(2) 采用固定的2個(gè)時(shí)鐘周期延遲時(shí)， 程序執(zhí)行的CPI = CPI基本 +分支延遲=1 + 15% X

13、 2=1.3顯然采用分支目標(biāo)緩沖器時(shí)程序執(zhí)行時(shí)間更少，即速度更快4.5假設(shè)分支目標(biāo)緩沖的命中率為 90% ,程序中 無(wú)條件轉(zhuǎn)移指令的比例為5%，沒(méi)有無(wú)條件轉(zhuǎn)移 指令的程序CPI值為1。假設(shè)分支目標(biāo)緩沖中包 含分之目標(biāo)指令，允許無(wú)條件轉(zhuǎn)移指令進(jìn)入分支 目標(biāo)緩沖，則程序的 CPI值為多少？假設(shè)無(wú)條 件分支指令不進(jìn)入分支目標(biāo)緩沖時(shí)程序執(zhí)行的 CPI 為 1.1 解：無(wú)條件分支指令的特點(diǎn)是只要執(zhí)行肯定分支 成功。因此，對(duì)于進(jìn)入分支目標(biāo)緩沖器的無(wú)條件 分支指令，分支預(yù)測(cè)的精度為100%，也就不會(huì) 帶來(lái)分支延遲。而沒(méi)有進(jìn)入分支目標(biāo)緩沖器的無(wú) 條件分支指令會(huì)帶來(lái)一定分支延遲。首先要求出 一條無(wú)條件分支指令的

14、分支延遲是多少，不妨設(shè) 為x個(gè)時(shí)鐘周期。由題知無(wú)條件分支指令不進(jìn)入分支目標(biāo)緩沖 時(shí)程序執(zhí)行的CPI為1.1，而程序中沒(méi)有無(wú)條件 轉(zhuǎn)移指令的CPI為1,因此有CPI = CPI 無(wú)分支指令 +無(wú)條件分支延遲 =1 + 5%x =1.1 所以 x= 2因此，允許無(wú)條件分支指令進(jìn)入分支目標(biāo)緩沖 器時(shí)，CPI = CPI 無(wú)分支指令 + 5% X( 1-90% ) X 2 =1.01第五章存儲(chǔ)層次5.1解釋下列術(shù)語(yǔ)（不要求寫在作業(yè)本上，但應(yīng) 作為復(fù)習(xí)內(nèi)容存儲(chǔ)系統(tǒng)全相聯(lián)映像直接映像組相聯(lián)映像寫直達(dá)法寫回法按寫分配法不按寫分配法命中時(shí)間失效率強(qiáng)制性失效容量失效沖突失效2： 1經(jīng)驗(yàn)規(guī)則相聯(lián)度答：（答案略）5

15、.2簡(jiǎn)述"Cache-主存"層次與"主存-輔存"層 次的區(qū)別。答：存儲(chǔ)層次、 比較項(xiàng)目“ Cache主存"層次“主存一輔存” 層次目的為了彌補(bǔ)主存速 度的不足為了彌補(bǔ)主存容 量的不足存儲(chǔ)管理實(shí)現(xiàn)全部由專用硬件 實(shí)現(xiàn)主要由軟件實(shí)現(xiàn)訪問(wèn)速度的比值（第一級(jí)比第二 級(jí)）幾比一幾百比一典型的塊（頁(yè)） 大小幾十個(gè)字節(jié)幾百到幾千個(gè)字 節(jié)CPU對(duì)第二級(jí)的 訪問(wèn)方式可直接訪問(wèn)均通過(guò)第一級(jí)失效時(shí)CPU是否 切換不切換切換到其它進(jìn)程5.3地址映像方法有哪些？它們各有什么優(yōu)缺 點(diǎn)？答：（1）全相聯(lián)映像。實(shí)現(xiàn)查找的機(jī)制復(fù)雜，代價(jià) 高，速度慢。Cache空間的利用率較高，

16、塊沖突 概率較低，因而Cache的失效率也低。（2）直接映像。實(shí)現(xiàn)查找的機(jī)制簡(jiǎn)單，速度快。 Cache空間的利用率較低，塊沖突概率較高，因 而Cache的失效率也高。（3）組相聯(lián)映像。組相聯(lián)是直接映像和全相聯(lián)的一種折中5.4降低cache失效率有哪幾種方法?答：(1) 增加Cache塊大小(2) 提高相聯(lián)度(3) 增加Cache的容量(4) Victim Cache(5) 偽相聯(lián)Cache(6) 硬件預(yù)取技術(shù)(7) 由編譯器控制的預(yù)取(8) 編譯器優(yōu)化。5.5簡(jiǎn)述減小cache失效開(kāi)銷的幾種方法。答:(1) 讓讀失效優(yōu)先于寫。(2) 寫緩沖合并。(3) 請(qǐng)求字處理技術(shù)。(4) 非阻塞Cache

17、或非鎖定Cache技術(shù)。采用二級(jí)Cache。5.8組相聯(lián)Cache的失效率比相同容量直接映像Cache的失效率低。由此能否得出結(jié)論：采用組 相聯(lián)映像一定能帶來(lái)性能上的提高？為什么？ 答：不一定。因?yàn)榻M相聯(lián)命中率的提高是以增加 命中時(shí)間為代價(jià)的，組相聯(lián)需要增加多路選擇開(kāi) 關(guān)。5.10假設(shè)對(duì)指令 Cache的訪問(wèn)站全部訪問(wèn)的 75% ;而對(duì)數(shù)據(jù) Cache的訪問(wèn)占全部訪問(wèn)的 25%。Cache的命中時(shí)間為1個(gè)時(shí)鐘周期，失效 開(kāi)銷為50個(gè)時(shí)鐘周期，在混合Cache中一次load 或store操作訪問(wèn)Cache的命中時(shí)間都要增加一 個(gè)時(shí)鐘周期，32KB的指令Cache的失效率為0.39%，32KB的數(shù)

18、據(jù)Cache的失效率為4.82%， 64KB的混合Cache的失效率為1.35%。又假設(shè) 采用寫直達(dá)策略，且有一個(gè)寫緩沖器，并且忽略 寫緩沖器引起的等待。試問(wèn)指令 Cache和數(shù)據(jù)Cache容量均為32KB的分離Cache和64KB的 混合Cache相比，哪種Cache的失效率更低？?jī)煞N情況下平均訪存時(shí)間各是多少？解：(1)分離Cache的總體失效率:F分離訪存失效總次數(shù)訪存總次數(shù)指令訪存失效次數(shù)-數(shù)據(jù)訪存失效次數(shù) 訪存總次數(shù)指令訪存次數(shù)指令訪存失效率-數(shù)據(jù)訪存次數(shù)數(shù)據(jù)訪存失效率-訪存總次數(shù)二指令訪存次數(shù)指令訪存失效率數(shù)據(jù)訪存次數(shù)數(shù)據(jù)訪存失效率 訪存總次數(shù)訪存總次數(shù)=指令訪存比例指令訪存失效率

19、-數(shù)據(jù)訪存比例數(shù)據(jù)訪存失效率= 75% 0.39 %25% 4.8 2 % =1.4975而容量為64 KB的混合Cache的失效率略低一些，只有1.35%。(2) 平均訪存時(shí)間分析平均訪存時(shí)間二訪存總時(shí)間訪存總次數(shù)_指令訪存總時(shí)間-數(shù)據(jù)訪存總時(shí)間 訪存總次數(shù)_指令訪存次數(shù) 平均指令訪存時(shí)間-數(shù)據(jù)訪存次數(shù) 平均數(shù)據(jù)訪存時(shí)間-訪存總次數(shù)指令訪存次數(shù) 平均指令訪存時(shí)間 數(shù)據(jù)訪存次數(shù) 平均數(shù)據(jù)訪存時(shí)間 訪存總次數(shù)訪存總次數(shù)二指令訪存比例 平均指令訪存時(shí)間數(shù)據(jù)訪存比例 平均數(shù)據(jù)訪存時(shí)間所以：平均訪存時(shí)間分離 =75% X (1+0.39% X50)+25% X (1+4.82% X 50)=(75%

20、X1.195)+(25% X 3.41)平均訪存時(shí)間混合=1.74875二 75% X (1+1.35% X50)+25% X (1+1+1.35% X 50)=(75% X1.675）+（25% X 2.675）=1.925因此，盡管分離Cache的實(shí)際失效率比混合 Cache的高，但其平均訪存時(shí)間反而較低。5.11給定以下的假設(shè)，試計(jì)算直接映像 Cache 和2路組相聯(lián)Cache的平均訪問(wèn)時(shí)間以及 CPU 的性能。由計(jì)算結(jié)果能得出什么結(jié)論？（1）理想Cache情況下的CPI為2.0，時(shí)鐘周 期為2ns,平均每條指令訪存1.2次。（2）兩者Cache容量均為64KB，塊大小都是 32B。（3

21、）組相聯(lián)映像Cache中的多路選擇器使CPU 的時(shí)鐘周期增加了 10%。（4）這兩種Cache的失效開(kāi)銷都是80nso（5）命中時(shí)間為1個(gè)時(shí)鐘周期。（6）64KB直接映像Cache的失效率為1.4%， 64KB2路組相聯(lián)Cache的失效率為1.0%。解:（1）平均訪問(wèn)時(shí)間=命中時(shí)間+失效率X失效 開(kāi)銷平均訪問(wèn)時(shí)間 i-路 =2.0+1.4% >80=3.12ns平均訪問(wèn)時(shí)間2-路=2.0 X1+10%）+1.0% XJ0=3.0ns兩路組相聯(lián)的平均訪問(wèn)時(shí)間比較低（2）CPU時(shí)間=（CPU執(zhí)行周期+存儲(chǔ)等待周 期）x時(shí)鐘周期時(shí)間=IC （CPI執(zhí)行+總失效次數(shù)/指 令總數(shù)x失效開(kāi)銷）x時(shí)鐘

22、周期=IC （CPI執(zhí)行X時(shí)鐘周期）+ （每條指令的訪存次數(shù)X失效率X失效開(kāi)銷X時(shí)鐘周期）所以：CPU 時(shí) 間1 路=IC(2.0 X+1.2 X.014 X0)= 5.344ICCPU 時(shí)間 2 路=IC(2.2 X2+1.2 >0.01 X80)=5.36IC相對(duì)性能比 :CP時(shí)間2路CPU時(shí)間1路=5.36/5.344=1.003直接映象cache的訪問(wèn)速度比兩路組相 聯(lián)cache要快1.04倍，而兩路組相聯(lián)Cache的平均性能比直接映象cache要 高1.003倍。因此這里選擇兩路組相聯(lián)。第七章互連網(wǎng)絡(luò)7.1解釋下列術(shù)語(yǔ)(不要求寫在作業(yè)本上，但應(yīng)作為復(fù)習(xí)內(nèi)容)線路交換 分組交換

23、靜態(tài)網(wǎng)絡(luò) 動(dòng)態(tài)網(wǎng)絡(luò) 互連網(wǎng)絡(luò)互連函數(shù)網(wǎng)絡(luò)直徑結(jié)點(diǎn)度 網(wǎng)絡(luò)規(guī)模等分寬度對(duì)稱網(wǎng)絡(luò)答：答案略7.3設(shè)E為交換函數(shù)，S為均勻洗牌函數(shù)，B為 蝶式函數(shù)，PM2I為移數(shù)函數(shù)，函數(shù)的自變量是 十進(jìn)制數(shù)表示的處理機(jī)編號(hào)。現(xiàn)在有32臺(tái)處理機(jī)，其編號(hào)為0，1，2，.，31。(1) 分別計(jì)算下列互連函數(shù)E2(12)S(8)B(9) PM2I +3(28) Eo(S(4)S(Eo(18)(2) 用Eo和S構(gòu)成均勻洗牌交換網(wǎng)(每步只能 使用Eo和S 一次）,網(wǎng)絡(luò)直徑是多少？從5號(hào)處 理機(jī)發(fā)送數(shù)據(jù)到7號(hào)處理機(jī)，最短路徑要經(jīng)過(guò)幾 步？請(qǐng)列出經(jīng)過(guò)的處理幾號(hào)。（3）采用移數(shù)網(wǎng)絡(luò)構(gòu)成互連網(wǎng)絡(luò)，網(wǎng)絡(luò)直徑是 多少？結(jié)點(diǎn)度是多少？與 2號(hào)處理機(jī)距離最遠(yuǎn) 的是幾號(hào)處理機(jī)？解：（1）共有32臺(tái)處理機(jī)，因此用Iogz32 = 5比特 表示各處理器編號(hào)。E2（12） 十進(jìn)制 =E2（01100）二進(jìn)制=（01000）二進(jìn)制= （8） 十進(jìn)制S（8）十進(jìn)制=S（ 01000）二進(jìn)制=（10000）二進(jìn)制= （16） 十進(jìn)制B（9）十進(jìn)制=B （ 01001）二進(jìn)制=（11000）二進(jìn)制 =（24） 十進(jìn)制PM2I +3（28） = （28 +23） mod 32 = 4E0（S（4） 十進(jìn)制=E°（S （00100）二進(jìn)制=E0 （0