計算機系統(tǒng)結(jié)構(gòu)第1-8章部分作業(yè)答案

計算機系統(tǒng)結(jié)構(gòu)第1-8章部分作業(yè)答案第一章1.6某臺主頻為400MHz的計算機執(zhí)行標(biāo)準(zhǔn)測試程序，程序中指令類型、執(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＝1.776(或)（2）MIPS速率＝f/CPI＝400/1.776＝225.225MIPS(或MIPS)（3）程序執(zhí)行時間=(45000×1＋75000×2＋8000×4＋1500×2)／400=575s1.9假設(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定律可得操作類型各類操作的指令條數(shù)在程序中所占的比例Fi各類操作的加速比Si各類操作單獨改進(jìn)后，程序獲得的加速比操作111.1%21.06操作233.3%1.331.09操作338.9%3.331.37操作416.7%41.144類操作均改進(jìn)后，整個程序的加速比：1.10第二章變長編碼，哈夫曼編碼第三章3.12有一條指令流水線如下所示：50ns50ns50ns100ns200ns1234（2）當(dāng)任務(wù)流過第三段時要在該段循環(huán)一次，相當(dāng)于要占用第三段2△t時間，則該流水線可看成是具有瓶頸段的線性流水線，瓶頸段即第三段，所需時間為2△t。每2△t輸入一個任務(wù)，連續(xù)處理10個任務(wù)的時空圖如下：則：（3）重復(fù)設(shè)置部件。重復(fù)的部件可并聯(lián)在流水線上，也可串聯(lián)于流水線中。如下圖所示：采用并聯(lián)方式時的時空圖如下：吞吐率提高倍數(shù)＝＝1.64△t△t2△t△t1△t△t2△t△t12345△t解：此題容易出的問題是忽略靜態(tài)流水線的特點，當(dāng)加法任務(wù)流入流水線后緊跟著啟動乘法任務(wù)。正確的做法是當(dāng)所有加法任務(wù)完成從流水線流出后再啟動乘法任務(wù)，同時還應(yīng)注意到流水線中的第三段所用時間為2△t。（1）任務(wù)分析（2）畫時空圖123456712341234567123456718△t（3）計算流水線性能吞吐率：加速比：效率：3.18在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拍。3.19某向量處理機有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é)果存進(jìn)相應(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個。所以：吞吐率：第四章4.4假設(shè)有一條長流水線，僅僅對條件轉(zhuǎn)移指令使用分支目標(biāo)緩沖。假設(shè)分支預(yù)測錯誤的開銷為4個時鐘周期，緩沖不命中的開銷為3個時鐘周期。假設(shè)：命中率為90%，預(yù)測精度為90%，分支頻率為15%，沒有分支的基本CPI為1。（1）求程序執(zhí)行的CPI。（2）相對于采用固定的2個時鐘周期延遲的分支處理，哪種方法程序執(zhí)行速度更快？解：（1）程序執(zhí)行的CPI=CPI基本+分支延遲=1+15%×[90%×（1-90%）×4=（1-90%）×3]=1.099（2）采用固定的2個時鐘周期延遲時，程序執(zhí)行的CPI=CPI基本+分支延遲=1+15%×2=1.3顯然采用分支目標(biāo)緩沖器時程序執(zhí)行時間更少，即速度更快。4.5假設(shè)分支目標(biāo)緩沖的命中率為90%，程序中無條件轉(zhuǎn)移指令的比例為5%，沒有無條件轉(zhuǎn)移指令的程序CPI值為1。假設(shè)分支目標(biāo)緩沖中包含分之目標(biāo)指令，允許無條件轉(zhuǎn)移指令進(jìn)入分支目標(biāo)緩沖，則程序的CPI值為多少？假設(shè)無條件分支指令不進(jìn)入分支目標(biāo)緩沖時程序執(zhí)行的CPI為1.1解：無條件分支指令的特點是只要執(zhí)行肯定分支成功。因此，對于進(jìn)入分支目標(biāo)緩沖器的無條件分支指令，分支預(yù)測的精度為100%，也就不會帶來分支延遲。而沒有進(jìn)入分支目標(biāo)緩沖器的無條件分支指令會帶來一定分支延遲。首先要求出一條無條件分支指令的分支延遲是多少，不妨設(shè)為x個時鐘周期。由題知無條件分支指令不進(jìn)入分支目標(biāo)緩沖時程序執(zhí)行的CPI為1.1，而程序中沒有無條件轉(zhuǎn)移指令的CPI為1，因此有CPI=CPI無分支指令+無條件分支延遲=1+5%x=1.1所以x=2因此，允許無條件分支指令進(jìn)入分支目標(biāo)緩沖器時，CPI=CPI無分支指令+5%×（1-90%）×2=1.01第五章存儲層次5.1解釋下列術(shù)語（不要求寫在作業(yè)本上，但應(yīng)作為復(fù)習(xí)內(nèi)容）存儲系統(tǒng)全相聯(lián)映像直接映像組相聯(lián)映像寫直達(dá)法寫回法按寫分配法不按寫分配法命中時間失效率強制性失效容量失效沖突失效2：1經(jīng)驗規(guī)則相聯(lián)度答：（答案略）5.2簡述“Cache-主存”層次與“主存-輔存”層次的區(qū)別。答：存儲層次比較項目“Cache—主存”層次“主存—輔存”層次目的為了彌補主存速度的不足為了彌補主存容量的不足存儲管理實現(xiàn)全部由專用硬件實現(xiàn)主要由軟件實現(xiàn)訪問速度的比值（第一級比第二級）幾比一幾百比一典型的塊（頁）大小幾十個字節(jié)幾百到幾千個字節(jié)CPU對第二級的訪問方式可直接訪問均通過第一級失效時CPU是否切換不切換切換到其它進(jìn)程5.3地址映像方法有哪些？它們各有什么優(yōu)缺點？答：（1）全相聯(lián)映像。實現(xiàn)查找的機制復(fù)雜，代價高，速度慢。Cache空間的利用率較高，塊沖突概率較低，因而Cache的失效率也低。（2）直接映像。實現(xiàn)查找的機制簡單，速度快。Cache空間的利用率較低，塊沖突概率較高，因而Cache的失效率也高。（3）組相聯(lián)映像。組相聯(lián)是直接映像和全相聯(lián)的一種折中。5.4降低cache失效率有哪幾種方法？答：（1）增加Cache塊大?。?）提高相聯(lián)度（3）增加Cache的容量（4）VictimCache（5）偽相聯(lián)Cache（6）硬件預(yù)取技術(shù)（7）由編譯器控制的預(yù)?。?）編譯器優(yōu)化。5.5簡述減小cache失效開銷的幾種方法。答：(1)讓讀失效優(yōu)先于寫。(2)寫緩沖合并。(3)請求字處理技術(shù)。(4)非阻塞Cache或非鎖定Cache技術(shù)。(5)采用二級Cache。5.8組相聯(lián)Cache的失效率比相同容量直接映像Cache的失效率低。由此能否得出結(jié)論：采用組相聯(lián)映像一定能帶來性能上的提高？為什么？答：不一定。因為組相聯(lián)命中率的提高是以增加命中時間為代價的，組相聯(lián)需要增加多路選擇開關(guān)。5.10假設(shè)對指令Cache的訪問站全部訪問的75%；而對數(shù)據(jù)Cache的訪問占全部訪問的25%。Cache的命中時間為1個時鐘周期，失效開銷為50個時鐘周期，在混合Cache中一次load或store操作訪問Cache的命中時間都要增加一個時鐘周期，32KB的指令Cache的失效率為0.39%，32KB的數(shù)據(jù)Cache的失效率為4.82%，64KB的混合Cache的失效率為1.35%。又假設(shè)采用寫直達(dá)策略，且有一個寫緩沖器，并且忽略寫緩沖器引起的等待。試問指令Cache和數(shù)據(jù)Cache容量均為32KB的分離Cache和64KB的混合Cache相比，哪種Cache的失效率更低？兩種情況下平均訪存時間各是多少？解：（1）分離Cache的總體失效率：而容量為64KB的混合Cache的失效率略低一些，只有1.35%。（2）平均訪存時間分析所以：平均訪存時間分離＝75%×(1+0.39%×50)+25%×(1+4.82%×50)＝(75%×1.195)+(25%×3.41)＝1.74875平均訪存時間混合＝75%×(1+1.35%×50)+25%×(1+1+1.35%×50)＝(75%×1.675)+(25%×2.675)＝1.925因此，盡管分離Cache的實際失效率比混合Cache的高，但其平均訪存時間反而較低。5.11給定以下的假設(shè)，試計算直接映像Cache和2路組相聯(lián)Cache的平均訪問時間以及CPU的性能。由計算結(jié)果能得出什么結(jié)論？（1）理想Cache情況下的CPI為2.0，時鐘周期為2ns，平均每條指令訪存1.2次。（2）兩者Cache容量均為64KB，塊大小都是32B。（3）組相聯(lián)映像Cache中的多路選擇器使CPU的時鐘周期增加了10%。（4）這兩種Cache的失效開銷都是80ns。（5）命中時間為1個時鐘周期。（6）64KB直接映像Cache的失效率為1.4%，64KB2路組相聯(lián)Cache的失效率為1.0%。解：（1）平均訪問時間＝命中時間＋失效率×失效開銷平均訪問時間1-路=2.0+1.4%×80=3.12ns平均訪問時間2-路=2.0×(1+10%)+1.0%×80=3.0ns兩路組相聯(lián)的平均訪問時間比較低（2）CPU時間=（CPU執(zhí)行周期+存儲等待周期）×?xí)r鐘周期時間=IC（CPI執(zhí)行+總失效次數(shù)/指令總數(shù)×失效開銷）×?xí)r鐘周期=IC（（CPI執(zhí)行×?xí)r鐘周期）+（每條指令的訪存次數(shù)×失效率×失效開銷×?xí)r鐘周期））所以：CPU時間1路=IC(2.0×2+1.2×0.014×80)＝5.344ICCPU時間2路=IC(2.2×2+1.2×0.01×80)＝5.36IC相對性能比：5.36/5.344=1.003直接映象cache的訪問速度比兩路組相聯(lián)cache要快1.04倍，而兩路組相聯(lián)Cache的平均性能比直接映象cache要高1.003倍。因此這里選擇兩路組相聯(lián)。第七章互連網(wǎng)絡(luò)7.1解釋下列術(shù)語（不要求寫在作業(yè)本上，但應(yīng)作為復(fù)習(xí)內(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ò)答：答案略7.3設(shè)E為交換函數(shù)，S為均勻洗牌函數(shù)，B為蝶式函數(shù)，PM2I為移數(shù)函數(shù)，函數(shù)的自變量是十進(jìn)制數(shù)表示的處理機編號?，F(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號處理機距離最遠(yuǎn)的是幾號處理機？解：（1）共有32臺處理機，因此用log232=5比特表示各處理器編號。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)mod32=4E0(S(4))十進(jìn)制=E0(S（00100））二進(jìn)制=E0（01000）=（01001）二進(jìn)制=(9)十進(jìn)制S(E0(18))十進(jìn)制=S(E0（10010））二進(jìn)制=S（10011）=（00111）二進(jìn)制=(7)十進(jìn)制（2）2n個結(jié)點的均勻洗牌交換網(wǎng)的網(wǎng)絡(luò)直徑是2n-1，32個結(jié)點的均勻洗牌交換網(wǎng)