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