計算機系統(tǒng)結(jié)構(gòu)第1-8章部分作業(yè)答案計算機系統(tǒng)結(jié)構(gòu)第1-8章部分作業(yè)答案計算機系統(tǒng)結(jié)構(gòu)第1-8章部分作業(yè)答案xxx公司計算機系統(tǒng)結(jié)構(gòu)第1-8章部分作業(yè)答案文件編號：文件日期：修訂次數(shù)：第1.0次更改批準審核制定方案設(shè)計，管理制度第一章某臺主頻為400MHz的計算機執(zhí)行標準測試程序，程序中指令類型、執(zhí)行數(shù)量和平均時鐘周期數(shù)如下：指令類型指令執(zhí)行數(shù)量平均時鐘周期數(shù)整數(shù)450001數(shù)據(jù)傳送750002浮點80004分支15002求該計算機的有效CPI、MIPS和程序執(zhí)行時間。解：（1）CPI＝(45000×1＋75000×2＋8000×4＋1500×2)/129500＝(或)（2）MIPS速率＝f/CPI＝400/＝(或MIPS)（3）程序執(zhí)行時間=(45000×1＋75000×2＋8000×4＋1500×2)／400=575s假設(shè)某應(yīng)用程序中有4類操作，通過改進，各操作獲得不同的性能提高。具體數(shù)據(jù)如下表所示：操作類型程序中的數(shù)量（百萬條指令）改進前的執(zhí)行時間（周期）改進后的執(zhí)行時間（周期）操作11021操作2302015操作335103操作41541（1）改進后，各類操作的加速比分別是多少（2）各類操作單獨改進后，程序獲得的加速比分別是多少（3）4類操作均改進后，整個程序的加速比是多少解：根據(jù)Amdahl定律可得操作類型各類操作的指令條數(shù)在程序中所占的比例Fi各類操作的加速比Si各類操作單獨改進后，程序獲得的加速比操作1%2操作2%操作3%操作4%44類操作均改進后，整個程序的加速比：第二章變長編碼，哈夫曼編碼第三章有一條指令流水線如下所示：50ns50ns50ns100ns200ns1234（1）求連續(xù)輸入10條指令的情況下，該流水線的實際吞吐率和效率。（2）該流水線的瓶頸在哪一段請采用兩種不同的措施消除此瓶頸。對于你所給出的兩種新的流水線，連續(xù)輸入10條指令時，其實際吞吐率和效率各是多少解：（1）本題主要考察對各功能段用時不等的線性流水線的性能計算公式的掌握情況。注意：對于公式不能死記硬背，需要充分理解，注意公式的適用條件。（2）瓶頸在3、4段。變成八級流水線（細分瓶頸段方法）重復設(shè)置瓶頸段方法1123-13-24-14-24-34-4有一個流水線由4段組成，其中每當流過第三段時，總要在該段循環(huán)一次，然后才能流到第4段。如果每段經(jīng)過一次所需的時間都是△t，問：（1）當在流水線的輸入端連續(xù)地每△t時間輸入一個任務(wù)時，該流水線會發(fā)生什么情況（2）此流水線的最大吞吐率為多少如果每2△t輸入一個任務(wù)，連續(xù)處理10個任務(wù)時，其實際吞吐率和效率是多少（3）當每段時間不變時，如何提高流水線的吞吐率人連續(xù)處理10個任務(wù)時，其吞吐率提高多少解：（1）會發(fā)生流水線阻塞情況。（2）當任務(wù)流過第三段時要在該段循環(huán)一次，相當于要占用第三段2△t時間，則該流水線可看成是具有瓶頸段的線性流水線，瓶頸段即第三段，所需時間為2△t。每2△t輸入一個任務(wù)，連續(xù)處理10個任務(wù)的時空圖如下：則：（3）重復設(shè)置部件。重復的部件可并聯(lián)在流水線上，也可串聯(lián)于流水線中。如下圖所示：采用并聯(lián)方式時的時空圖如下：吞吐率提高倍數(shù)＝＝△t△t2△t△t1△t△t2△t△t12345△t解：此題容易出的問題是忽略靜態(tài)流水線的特點，當加法任務(wù)流入流水線后緊跟著啟動乘法任務(wù)。正確的做法是當所有加法任務(wù)完成從流水線流出后再啟動乘法任務(wù)，同時還應(yīng)注意到流水線中的第三段所用時間為2△t。（1）任務(wù)分析（2）畫時空圖123456712341234567123456718△t（3）計算流水線性能吞吐率：加速比：效率：在CRAY-l機器上，按照鏈接方式執(zhí)行下述4條向量指令(括號中給出了相應(yīng)功能部件時間)，如果向量寄存器和功能部件之間的數(shù)據(jù)傳送需要1拍，試求此鏈接流水線的通過時間是多少拍如果向量長度為64，則需多少拍才能得到全部結(jié)果。V0←存儲器 （從存儲器中取數(shù)：７拍）V2←V0＋V1 （向量加：３拍）V3←V2＜A3 （按(A3)左移：４拍）V5←V3∧V4 （向量邏輯乘：２拍）解：通過時間就是每條向量指令的第一個操作數(shù)執(zhí)行完畢需要的時間，也就是各功能流水線由空到滿的時間，具體過程如下圖所示。要得到全部結(jié)果，在流水線充滿之后，向量中后繼操作數(shù)繼續(xù)以流水方式執(zhí)行，直到整組向量執(zhí)行完畢。說明：若考慮數(shù)據(jù)從存儲器送訪存部件也有1拍延遲，則通過時間應(yīng)為24拍，完成全部任務(wù)所用時間相應(yīng)為87拍。某向量處理機有16個向量寄存器，其中V0-V5種分別存放有向量A,B,C,D,E,F,向量的長度是8,向量各元素均為浮點數(shù)；處理部件采用兩個單功能流水線，加法功能部件時間為2拍，乘法功能部件時間為3拍。采用類似CRAY-1的鏈接技術(shù)，先計算(A+B)×C,在流水線不停的情況下，接著計算(D+E)×F。（1）求此鏈接流水線的通過時間是多少拍（設(shè)寄存器出入各需1拍）（2）假如每排時間為50ns，完成這些計算并把結(jié)果存進相應(yīng)寄存器，此處理部件的時間吞吐率為多少MFLOPS解：（1）我們在這里假設(shè)A＋B的中間結(jié)果放在V6中，（A＋B）×C地最后結(jié)果放在V7中，D＋E地中間結(jié)果放在V8中，（D＋E）×F的最后結(jié)果放在V9中。具體實現(xiàn)參考下圖：通過時間應(yīng)該為前者（（A＋B）×C）通過的時間：T通過=(1+2+1)+(1+3+1)=9（拍）（2）在做完（A＋B）×C之后，作（C＋D）×E就不需要通過時間了。=1200×10-9（s）題目中所問為吞吐率是多少MFLOPS，顯然是讓求以MFLOPS為單位的吞吐率。MFLOPS是指每秒完成多少百萬次浮點運算，因此要明確所有任務(wù)中共多少浮點運算。顯然共有4條浮點向量指令，而每條指令完成8個浮點運算，因此浮點運算總數(shù)為32個。所以：吞吐率：第四章假設(shè)有一條長流水線，僅僅對條件轉(zhuǎn)移指令使用分支目標緩沖。假設(shè)分支預測錯誤的開銷為4個時鐘周期，緩沖不命中的開銷為3個時鐘周期。假設(shè)：命中率為90%，預測精度為90%，分支頻率為15%，沒有分支的基本CPI為1。（1）求程序執(zhí)行的CPI。（2）相對于采用固定的2個時鐘周期延遲的分支處理，哪種方法程序執(zhí)行速度更快解：（1）程序執(zhí)行的CPI=CPI基本+分支延遲=1+15%×[90%×（1-90%）×4=（1-90%）×3]=（2）采用固定的2個時鐘周期延遲時，程序執(zhí)行的CPI=CPI基本+分支延遲=1+15%×2=顯然采用分支目標緩沖器時程序執(zhí)行時間更少，即速度更快。假設(shè)分支目標緩沖的命中率為90%，程序中無條件轉(zhuǎn)移指令的比例為5%，沒有無條件轉(zhuǎn)移指令的程序CPI值為1。假設(shè)分支目標緩沖中包含分之目標指令，允許無條件轉(zhuǎn)移指令進入分支目標緩沖，則程序的CPI值為多少假設(shè)無條件分支指令不進入分支目標緩沖時程序執(zhí)行的CPI為解：無條件分支指令的特點是只要執(zhí)行肯定分支成功。因此，對于進入分支目標緩沖器的無條件分支指令，分支預測的精度為100%，也就不會帶來分支延遲。而沒有進入分支目標緩沖器的無條件分支指令會帶來一定分支延遲。首先要求出一條無條件分支指令的分支延遲是多少，不妨設(shè)為x個時鐘周期。由題知無條件分支指令不進入分支目標緩沖時程序執(zhí)行的CPI為，而程序中沒有無條件轉(zhuǎn)移指令的CPI為1，因此有CPI=CPI無分支指令+無條件分支延遲=1+5%x=所以x=2因此，允許無條件分支指令進入分支目標緩沖器時，CPI=CPI無分支指令+5%×（1-90%）×2=第五章存儲層次解釋下列術(shù)語（不要求寫在作業(yè)本上，但應(yīng)作為復習內(nèi)容）存儲系統(tǒng)全相聯(lián)映像直接映像組相聯(lián)映像寫直達法寫回法按寫分配法不按寫分配法命中時間失效率強制性失效容量失效沖突失效2：1經(jīng)驗規(guī)則相聯(lián)度答：（答案略）簡述“Cache-主存”層次與“主存-輔存”層次的區(qū)別。答：存儲層次比較項目“Cache—主存”層次“主存—輔存”層次目的為了彌補主存速度的不足為了彌補主存容量的不足存儲管理實現(xiàn)全部由專用硬件實現(xiàn)主要由軟件實現(xiàn)訪問速度的比值（第一級比第二級）幾比一幾百比一典型的塊（頁）大小幾十個字節(jié)幾百到幾千個字節(jié)CPU對第二級的訪問方式可直接訪問均通過第一級失效時CPU是否切換不切換切換到其它進程地址映像方法有哪些它們各有什么優(yōu)缺點答：（1）全相聯(lián)映像。實現(xiàn)查找的機制復雜，代價高，速度慢。Cache空間的利用率較高，塊沖突概率較低，因而Cache的失效率也低。（2）直接映像。實現(xiàn)查找的機制簡單，速度快。Cache空間的利用率較低，塊沖突概率較高，因而Cache的失效率也高。（3）組相聯(lián)映像。組相聯(lián)是直接映像和全相聯(lián)的一種折中。降低cache失效率有哪幾種方法答：（1）增加Cache塊大?。?）提高相聯(lián)度（3）增加Cache的容量（4）VictimCache（5）偽相聯(lián)Cache（6）硬件預取技術(shù)（7）由編譯器控制的預取（8）編譯器優(yōu)化。簡述減小cache失效開銷的幾種方法。答：(1)讓讀失效優(yōu)先于寫。(2)寫緩沖合并。(3)請求字處理技術(shù)。(4)非阻塞Cache或非鎖定Cache技術(shù)。(5)采用二級Cache。組相聯(lián)Cache的失效率比相同容量直接映像Cache的失效率低。由此能否得出結(jié)論：采用組相聯(lián)映像一定能帶來性能上的提高為什么答：不一定。因為組相聯(lián)命中率的提高是以增加命中時間為代價的，組相聯(lián)需要增加多路選擇開關(guān)。假設(shè)對指令Cache的訪問站全部訪問的75%；而對數(shù)據(jù)Cache的訪問占全部訪問的25%。Cache的命中時間為1個時鐘周期，失效開銷為50個時鐘周期，在混合Cache中一次load或store操作訪問Cache的命中時間都要增加一個時鐘周期，32KB的指令Cache的失效率為%，32KB的數(shù)據(jù)Cache的失效率為%，64KB的混合Cache的失效率為%。又假設(shè)采用寫直達策略，且有一個寫緩沖器，并且忽略寫緩沖器引起的等待。試問指令Cache和數(shù)據(jù)Cache容量均為32KB的分離Cache和64KB的混合Cache相比，哪種Cache的失效率更低兩種情況下平均訪存時間各是多少解：（1）分離Cache的總體失效率：而容量為64KB的混合Cache的失效率略低一些，只有%。（2）平均訪存時間分析所以：平均訪存時間分離＝75%×(1+%×50)+25%×(1+%×50)＝(75%×+(25%×＝平均訪存時間混合＝75%×(1+%×50)+25%×(1+1+%×50)＝(75%×+(25%×＝因此，盡管分離Cache的實際失效率比混合Cache的高，但其平均訪存時間反而較低。給定以下的假設(shè)，試計算直接映像Cache和2路組相聯(lián)Cache的平均訪問時間以及CPU的性能。由計算結(jié)果能得出什么結(jié)論（1）理想Cache情況下的CPI為，時鐘周期為2ns，平均每條指令訪存次。（2）兩者Cache容量均為64KB，塊大小都是32B。（3）組相聯(lián)映像Cache中的多路選擇器使CPU的時鐘周期增加了10%。（4）這兩種Cache的失效開銷都是80ns。（5）命中時間為1個時鐘周期。（6）64KB直接映像Cache的失效率為%，64KB2路組相聯(lián)Cache的失效率為%。解：（1）平均訪問時間＝命中時間＋失效率×失效開銷平均訪問時間1-路=+%×80=平均訪問時間2-路=×(1+10%)+%×80=兩路組相聯(lián)的平均訪問時間比較低（2）CPU時間=（CPU執(zhí)行周期+存儲等待周期）×時鐘周期時間=IC（CPI執(zhí)行+總失效次數(shù)/指令總數(shù)×失效開銷）×時鐘周期=IC（（CPI執(zhí)行×時鐘周期）+（每條指令的訪存次數(shù)×失效率×失效開銷×時鐘周期））所以：CPU時間1路=IC×2+××80)＝CPU時間2路=IC×2+××80)＝相對性能比：=直接映象cache的訪問速度比兩路組相聯(lián)cache要快倍，而兩路組相聯(lián)Cache的平均性能比直接映象cache要高倍。因此這里選擇兩路組相聯(lián)。第七章互連網(wǎng)絡(luò)解釋下列術(shù)語（不要求寫在作業(yè)本上，但應(yīng)作為復習內(nèi)容）線路交換分組交換靜態(tài)網(wǎng)絡(luò)動態(tài)網(wǎng)絡(luò)互連網(wǎng)絡(luò)互連函數(shù)網(wǎng)絡(luò)直徑結(jié)點度網(wǎng)絡(luò)規(guī)模等分寬度對稱網(wǎng)絡(luò)答：答案略設(shè)E為交換函數(shù)，S為均勻洗牌函數(shù)，B為蝶式函數(shù)，PM2I為移數(shù)函數(shù)，函數(shù)的自變量是十進制數(shù)表示的處理機編號。現(xiàn)在有32臺處理機，其編號為0，1，2，….，31。（1）分別計算下列互連函數(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號處理機發(fā)送數(shù)據(jù)到7號處理機，最短路徑要經(jīng)過幾步請列出經(jīng)過的處理幾號。（3）采用移數(shù)網(wǎng)絡(luò)構(gòu)成互連網(wǎng)絡(luò)，網(wǎng)絡(luò)直徑是多少結(jié)點度是多少與2號處理機距離最遠的是幾號處理機解：（1）共有32臺處理機，因此用log232=5比特表示各處理器編號。E2(12)十進制=E2(01100)二進制=（01000）二進制=(8)十進制S(8)十進制=S（01000）二進制=（10000）二進制=(16)十進制B(9)十進制=B（01001）二進制=（11000）二進制=(24)十進制PM2I+3(28)=(28+23)mod32=4E0(S(4))十進制=E0(S（00100））二進制=E0（01000）=（01001）二進制=(9)十進制S(E0(18))十進制=S(E0（10010））二進制=S（1001