計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第18章部分作業(yè)答案

1、第一章1.6某臺(tái)主頻為400MHz的計(jì)算機(jī)執(zhí)行標(biāo)準(zhǔn)測試程序，程序中指令類型、執(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=(45000X1+75000X2+8000X4+1500X2)/129500=1.776460(或259)5180MIPS速率=f/CPI=400/1.776=225.225MIPS(或-MIPS)（3）程序執(zhí)行時(shí)間=（45000X1+75000X2+8000X4+1500X2）/400=571.9假設(shè)某應(yīng)用程序中有4類操作，通

2、過改進(jìn)，各操作獲得不同的性能提高。具體數(shù)據(jù)如下表所示：解：根據(jù)Amdahl定律SnFe(1中忑可得操作類型程序中的數(shù)量（百萬條指令）改進(jìn)前的執(zhí)行時(shí)間（周期）改進(jìn)后的執(zhí)行時(shí)間（周期）操作11021操作2302015操作335103操作415411）改進(jìn)后，各類操作的加速比分別是多少？2）各類操作單獨(dú)改進(jìn)后，程序獲得的加速比分別是多少？3）4類操作均改進(jìn)后，整個(gè)程序的加速比是多少？操作類型各類操作的指令條數(shù)在程序中所占的比例Fi各類操作的加速比S.1各類操作單獨(dú)改進(jìn)后，程序獲得的加速比操作1111.1%21.06操作233.3%1.331.09操作338.9%3.331.37操作416.7%41.

3、14類操作均改進(jìn)后，整個(gè)程序的加速比-2.16n（1F.）孑i1.10第二章變長編碼，哈夫曼編碼第三章有一條指令流水線如下所示50ns50ns100ns200ns（1）求連續(xù)輸入10條指令的情況下，該流水線的實(shí)際吞吐率和效率。（2）該流水線的瓶頸在哪一段？請采用兩種不同的措施消除此瓶頸。對(duì)于你所給出的兩種新的流水線，連續(xù)輸入10條指令時(shí)，其實(shí)際吞吐率和效率各是多少？解：（1）本題主要考察對(duì)各功能段用時(shí)不等的線性流水線的性能計(jì)算公式的掌握情況。Tk（n）流水imax（5050100200）92002200（ns）TPnT】220(ns)/流水EIP害45-45%注意：對(duì)于公式不能死記硬背，需要充

4、分理解，注意公式的適用條件。2）瓶頸在3、4段。變成八級(jí)流水線（細(xì)分瓶頸段方法）to.k-2-Tkti(n1)tmax流水imaxi1508950850(ns)TP%5(ns)/Tz流水ETP曙10兔82%重復(fù)設(shè)置瓶頸段方法TPnT185(ns町/流水58.82%E.40010.-850.8有一個(gè)流水線由4段組成，其中每當(dāng)流過第三段時(shí)，總要在該段循環(huán)一次，然后才能流到第4段。如果每段經(jīng)過一次所需的時(shí)間都是，問：當(dāng)在流水線的輸入端連續(xù)地每時(shí)間輸入一個(gè)任務(wù)時(shí)，該流水線會(huì)發(fā)生什么情況？此流水線的最大吞吐率為多少？如果每24輸入一個(gè)任務(wù)，連續(xù)處理10個(gè)任務(wù)時(shí)，其實(shí)際吞吐率和效率是多少？當(dāng)每段時(shí)間不變時(shí)

5、，如何提高流水線的吞吐率？人連續(xù)處理10個(gè)任務(wù)時(shí)，其吞吐率提高多少？解：會(huì)發(fā)生流水線阻塞情況。當(dāng)任務(wù)流過第三段時(shí)要在該段循環(huán)一次，相當(dāng)于要占用第三段24時(shí)間，則該流水線可看成是具有瓶頸段的線性流水線，瓶頸段即第三段，所需時(shí)間為2。每24輸入一個(gè)任務(wù)，連續(xù)處理10個(gè)任務(wù)的時(shí)空圖如下：則：2311max2T23流水Tp坯/流水113)重復(fù)設(shè)置部件。重復(fù)的部件可并聯(lián)在流水線上，也可串聯(lián)于流水線中。如下圖所示：吞吐率提咼倍數(shù)=1.641023TPnT10/T流水11有一條靜態(tài)多功能流水線由5段組成，加法用1、3、4、5段，乘法用1、2、5段，第3段的時(shí)間為2，其余各段的時(shí)間均為，而且流水線的輸出可以直

6、接返回輸入端或暫存于相應(yīng)的流水線寄存器中?，F(xiàn)在該流水線上計(jì)算(AB)，畫出時(shí)空圖，并計(jì)算其吞吐iii解：此題容易出的問題是忽略靜態(tài)流水線的特點(diǎn)，當(dāng)加法任務(wù)流入流水線后緊跟著啟動(dòng)乘法任務(wù)。正確的做法是當(dāng)所有加法任務(wù)完成從流水線流出后再啟動(dòng)乘法任務(wù)，同時(shí)還應(yīng)注意到流水線中的第三段所用時(shí)間為山。（1）任務(wù)分析2）畫時(shí)空圖（3）計(jì)算流水線性能吞吐率畔18SF加速比：Sp串行T流水433t1W19效率：e實(shí)際占用面只433t29時(shí)空區(qū)總面積51890在機(jī)器上，按照鏈接方式執(zhí)行下述條向量指令括號(hào)中給出了相應(yīng)功能部件時(shí)間），如果向量寄存器和功能部件之間的數(shù)據(jù)傳送需要1拍，試求此鏈接流水線的通過時(shí)間是多少拍？

7、如果向量長度為，則需多少拍才能得到全部結(jié)果。-存儲(chǔ)器（從存儲(chǔ)器中取數(shù)：7拍）J0（向量加：3拍）一V（按左移：4拍）-3（向量邏輯乘：2拍）解：通過時(shí)間就是每條向量指令的第一個(gè)操作數(shù)執(zhí)行完畢需要的時(shí)間，也就是各功能流水線由空到滿的時(shí)間，具體過程如下圖所示。要得到全部結(jié)果，在流水線充滿之后，向T通過=(7+l)+(l+3+l)+(l+4+l)+(l+2+l)=23(拍)TT通過+(641)=23+63=86(拍)總共通過說明：若考慮數(shù)據(jù)從存儲(chǔ)器送訪存部件也有1拍延遲，則通過時(shí)間應(yīng)為24拍，完成全部任務(wù)所用時(shí)間相應(yīng)為87拍。3.l9某向量處理機(jī)有l(wèi)6個(gè)向量寄存器，其中V0-V5種分別存放有向量A,

8、B,C,D,E,F,向量的長度是8,向量各元素均為浮點(diǎn)數(shù)；處理部件采用兩個(gè)單功能流水線，加法功能部件時(shí)間為2拍，乘法功能部件時(shí)間為3拍。采用類似CRAY-l的鏈接技術(shù)，先計(jì)算(A+B)XC,在流水線不停的情況下，接著計(jì)算(D+E)XF。求此鏈接流水線的通過時(shí)間是多少拍？(設(shè)寄存器出入各需1拍)假如每排時(shí)間為50ns，完成這些計(jì)算并把結(jié)果存進(jìn)相應(yīng)寄存器，此處理部件的時(shí)間吞吐率為多少M(fèi)FLOPS？解：我們在這里假設(shè)A+B的中間結(jié)果放在V6中，(A+B)XC地最后結(jié)果放在V7中，D+E地中間結(jié)果放在V8中，(D+E)XF的最后結(jié)果放在V9中。具體實(shí)現(xiàn)參考下圖：通過時(shí)間應(yīng)該為前者(A+B)XC)通過的

9、時(shí)間：T通過1+2+1)+(1+3+1)=9(拍)在做完(A+B)XC之后，作(C+D)XE就不需要通過時(shí)間了。V6AB;V7V6C;V8DE;V9V8F;TT通址(8D824(拍)1200(ns)=1200X10-9(s)題目中所問為吞吐率是多少M(fèi)FLOPS,顯然是讓求以MFLOPS為單位的吞吐率。MFLOPS是指每秒完成多少百萬次浮點(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è)。所以：3232吞吐率.TP2667MFLOPST106120010106E第四章假設(shè)有一條長流水線,僅僅對(duì)條件轉(zhuǎn)移指令使用分支目標(biāo)緩沖。假

10、設(shè)分支預(yù)測錯(cuò)誤的開銷為4個(gè)時(shí)鐘周期,緩沖不命中的開銷為3個(gè)時(shí)鐘周期。假設(shè)：命中率為90%,預(yù)測精度為90%，分支頻率為15%，沒有分支的基本CPI為1。(1)求程序執(zhí)行的CPI。(2)相對(duì)于采用固定的2個(gè)時(shí)鐘周期延遲的分支處理，哪種方法程序執(zhí)行速度更快？解：(1)程序執(zhí)行的CPI=CPI基本+分支延遲基本=1+15%X90%X(1-90%)X4=(1-90%)X3=1.099(2)采用固定的2個(gè)時(shí)鐘周期延遲時(shí)，程序執(zhí)行的CPI=CPI基本+分支延遲基本=1+15%X2=1.3顯然采用分支目標(biāo)緩沖器時(shí)程序執(zhí)行時(shí)間更少，即速度更快。假設(shè)分支目標(biāo)緩沖的命中率為90%，程序中無條件轉(zhuǎn)移指令的比例為5%

11、，沒有無條件轉(zhuǎn)移指令的程序CPI值為1。假設(shè)分支目標(biāo)緩沖中包含分之目標(biāo)指令，允許無條件轉(zhuǎn)移指令進(jìn)入分支目標(biāo)緩沖，則程序的CPI值為多少？假設(shè)無條件分支指令不進(jìn)入分支目標(biāo)緩沖時(shí)程序執(zhí)行的CPI為1.1解：無條件分支指令的特點(diǎn)是只要執(zhí)行肯定分支成功。因此，對(duì)于進(jìn)入分支目標(biāo)緩沖器的無條件分支指令，分支預(yù)測的精度為100%，也就不會(huì)帶來分支延遲。而沒有進(jìn)入分支目標(biāo)緩沖器的無條件分支指令會(huì)帶來一定分支延遲。首先要求出一條無條件分支指令的分支延遲是多少，不妨設(shè)為x個(gè)時(shí)鐘周期。由題知無條件分支指令不進(jìn)入分支目標(biāo)緩沖時(shí)程序執(zhí)行的CPI為1.1，而程序中沒有無條件轉(zhuǎn)移指令的CPI為1,因此有CPI=CPI+無條

12、件分支延遲=1+5%x=1.1所以x=2無分支指令因此，允許無條件分支指令進(jìn)入分支目標(biāo)緩沖器時(shí)，CPI=CPI+5%X(1-90%)X2=1.01無分支指令第五章存儲(chǔ)層次解釋下列術(shù)語(不要求寫在作業(yè)本上，但應(yīng)作為復(fù)習(xí)內(nèi)容)存儲(chǔ)系統(tǒng)全相聯(lián)映像直接映像組相聯(lián)映像寫直達(dá)法寫回法強(qiáng)制性失效按寫分配法容量失效不按寫分配法命中時(shí)間失效率沖突失效2：1經(jīng)驗(yàn)規(guī)則相聯(lián)度答：（答案略）5.2簡述“Cache-主存”層次與“主存-輔存”層次的區(qū)別。_-一_存儲(chǔ)層次比較項(xiàng)目“Cache主存”層次“主存輔存”層次目的為了彌補(bǔ)主存速度的不足為了彌補(bǔ)主存容量的不足存儲(chǔ)管理實(shí)現(xiàn)全部由專用硬件實(shí)現(xiàn)主要由軟件實(shí)現(xiàn)訪問速度的比值（

13、第一級(jí)比第二級(jí)）幾比一幾百比一典型的塊（頁）大小幾十個(gè)字節(jié)幾百到幾千個(gè)字節(jié)CPU對(duì)第二級(jí)的訪問方式可直接訪問均通過第一級(jí)失效時(shí)CPU是否切換不切換切換到其它進(jìn)程5.3地址映像方法有哪些？它們各有什么優(yōu)缺點(diǎn)？答：（1）全相聯(lián)映像。實(shí)現(xiàn)查找的機(jī)制復(fù)雜，代價(jià)高，速度慢。Cache空間的利用率較高，塊沖突概率較低，因而Cache的失效率也低。（2）直接映像。實(shí)現(xiàn)查找的機(jī)制簡單，速度快。Cache空間的利用率較低，塊沖突概率較高，因而Cache的失效率也高。（3）組相聯(lián)映像。組相聯(lián)是直接映像和全相聯(lián)的一種折中。5.4降低cache失效率有哪幾種方法？答：（1）增加Cache塊大小（2）提高相聯(lián)度（3）增

14、加Cache的容量（4）VictimCache（5）偽相聯(lián)Cache（6）硬件預(yù)取技術(shù)（7）由編譯器控制的預(yù)取（8）編譯器優(yōu)化。5.5簡述減小cache失效開銷的幾種方法。答：（1）讓讀失效優(yōu)先于寫。（2）寫緩沖合并。（3）請求字處理技術(shù)。（4）非阻塞Cache或非鎖定Cache技術(shù)。采用二級(jí)Cache。5.8組相聯(lián)Cache的失效率比相同容量直接映像Cache的失效率低。由此能否得出結(jié)論：采用組相聯(lián)映像一定能帶來性能上的提高？為什么？答：不一定。因?yàn)榻M相聯(lián)命中率的提高是以增加命中時(shí)間為代價(jià)的，組相聯(lián)需要增加多路選擇開關(guān)。5.10假設(shè)對(duì)指令Cache的訪問站全部訪問的75%；而對(duì)數(shù)據(jù)Cache

15、的訪問占全部訪問的25%。Cache的命中時(shí)間為1個(gè)時(shí)鐘周期，失效開銷為50個(gè)時(shí)鐘周期，在混合Cache中一次load或store操作訪問Cache的命中時(shí)間都要增加一個(gè)時(shí)鐘周期,32KB的指令Cache的失效率為0.39%,32KB的數(shù)據(jù)Cache的失效率為4.82%,64KB的混合Cache的失效率為1.35%。又假設(shè)采用寫直達(dá)策略，且有一個(gè)寫緩沖器，并且忽略寫緩沖器引起的等待。試問指令Cache和數(shù)據(jù)Cache容量均為32KB的分離Cache和64KB的混合Cache相比，哪種Cache的失效率更低？兩種情況下平均訪存時(shí)間各是多少？解：（1）分離Cache的總體失效率：F訪存失效總次數(shù)分

16、離訪存總次數(shù)指令訪存失效次數(shù)數(shù)據(jù)訪存失效次數(shù)訪存總次數(shù)指令訪存次數(shù)指令訪存失效率數(shù)據(jù)訪存次數(shù)數(shù)據(jù)訪存失效率訪存總次數(shù)指令訪存次數(shù)訪存總次數(shù)指令訪存失效率數(shù)據(jù)訪存次數(shù)訪存總次數(shù)數(shù)據(jù)訪存失效率指令訪存比例指令訪存失效率數(shù)據(jù)訪存比例數(shù)據(jù)訪存失效率75%0.39%25%4.82%1.4975而容量為64KB的混合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ù)指令訪存比例平均指

17、令訪存時(shí)間數(shù)據(jù)訪存比例平均數(shù)據(jù)訪存時(shí)間所以：平均訪存時(shí)間=75%X(1+0.39%X50)+25%X(1+4.82%X50)分離=(75%X1.195)+(25%X3.41)=1.74875平均訪存時(shí)間=75%X(1+1.35%X50)+25%X(1+1+1.35%X50)混合=(75%X1.675)+(25%X2.675)=1.925因此，盡管分離Cache的實(shí)際失效率比混合Cache的高，但其平均訪存時(shí)間反而較低。5.11給定以下的假設(shè)，試計(jì)算直接映像Cache和2路組相聯(lián)Cache的平均訪問時(shí)間以及CPU的性能。由計(jì)算結(jié)果能得出什么結(jié)論？理想Cache情況下的CPI為2.0,時(shí)鐘周期為2

18、ns,平均每條指令訪存1.2次。兩者Cache容量均為64KB，塊大小都是32B。組相聯(lián)映像Cache中的多路選擇器使CPU的時(shí)鐘周期增加了10%。這兩種Cache的失效開銷都是80ns。命中時(shí)間為1個(gè)時(shí)鐘周期。64KB直接映像Cache的失效率為1.4%,64KB2路組相聯(lián)Cache的失效率為1.0%。解：平均訪問時(shí)間=命中時(shí)間+失效率X失效開銷平均訪問時(shí)間=2.0+1.4%x80=3.12ns路平均訪問時(shí)間=2.0 x(1+10%)+1.0%x80=3.0ns路兩路組相聯(lián)的平均訪問時(shí)間比較低CPU時(shí)間=(CPU執(zhí)行周期+存儲(chǔ)等待周期)X時(shí)鐘周期時(shí)間=IC(CPI執(zhí)行+總失效次數(shù)/指令總數(shù)X

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

20、絡(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)?，F(xiàn)在有32臺(tái)處理機(jī),其編號(hào)為0,1,2,假.,31。(1)分別計(jì)算下列互連函數(shù)E2(12)S(8)B(9)PM2I+3(28)E0(S(4)S(E0(18)(2)用E0和S構(gòu)成均勻洗牌交換網(wǎng)(每步只能使用E0和S一次)，網(wǎng)絡(luò)直徑是多少？從5號(hào)處理機(jī)發(fā)送數(shù)據(jù)到7號(hào)處理機(jī),最短路徑要經(jīng)過幾步？請列出經(jīng)過的處理幾號(hào)。采用移數(shù)網(wǎng)絡(luò)構(gòu)成互連網(wǎng)絡(luò),網(wǎng)絡(luò)直徑是多少？結(jié)點(diǎn)度是多少？與2號(hào)處理機(jī)距離最遠(yuǎn)的是幾號(hào)處理機(jī)？解：共有32臺(tái)處理機(jī)，因此用log232=5比特表示各處理器編號(hào)。TOC o 1-5 h zE(12)=E(01100)=(01000)(8)2十進(jìn)制2二進(jìn)制二進(jìn)制=十進(jìn)制S(8)=S(01000)=(10000)(16)十進(jìn)制二進(jìn)制二進(jìn)制=十進(jìn)制B(9)=B(01001)=(11000)(24)十進(jìn)制二進(jìn)制二進(jìn)制=十進(jìn)制PM2I+3(28)=(28+23)mod32=4E(S(4)=E(S(00100)=E(01000)=(01001)(