高級計算機系統(tǒng)結(jié)構(gòu)2015年復(fù)習(xí)題

1、1. 假設(shè)有一條長流水線，僅僅對條件轉(zhuǎn)移指令使用分支目標(biāo)緩沖。假設(shè)分支預(yù)測錯誤的開銷為4個時鐘周期，緩沖不命中的開銷為3個時鐘周期。假設(shè)：命中率為90%，預(yù)測精度為90%，分支頻率為15%，沒有分支的基本CPI為1。求程序執(zhí)行的CPI。相對于采用固定的2個時鐘周期延遲的分支處理，哪種方法程序執(zhí)行速度更快？參考答案：解：（1）程序執(zhí)行的CPI = 沒有分支的基本CPI（1） + 分支帶來的額外開銷分支帶來的額外開銷是指在分支指令中，緩沖命中但預(yù)測錯誤帶來的開銷與緩沖沒有命中帶來的開銷之和。分支帶來的額外開銷= 15% * (90%命中10%預(yù)測錯誤4 + 10沒命中3)= 0.099所以，程序執(zhí)

2、行的CPI 1 0.099 = 1.099（2）采用固定的2 個時鐘周期延遲的分支處理CPI = 1 + 15%2 = 1.3由（1）（2）可知分支目標(biāo)緩沖方法執(zhí)行速度快。2. 計算機系統(tǒng)中有三個部件可以改進(jìn)，這三個部件的部件加速比為：部件加速比1=30； 部件加速比2=20 部件加速比3=10 如果部件2和部件3的可改進(jìn)比例均為30%，那么當(dāng)部件 1的可改進(jìn)比例為多少時，系統(tǒng)加速比才可以達(dá)到10？如果三個部件的可改進(jìn)比例分別為20%、10%和30%，三個部件同時改進(jìn)，那么系統(tǒng)中不可加速部分的執(zhí)行時間在總執(zhí)行時間中占的比例是多少？ 參考答案：解：（1）在多個部件可改進(jìn)情況下，Amdahl定理的

3、擴展：已知S130，S215，S315，Sn10，F(xiàn)10.3，F(xiàn)20.3，得：得F30.36，即部件3的可改進(jìn)比例為36%。（2）設(shè)系統(tǒng)改進(jìn)前的執(zhí)行時間為T，則3個部件改進(jìn)前的執(zhí)行時間為：（0.3+0.3+0.2）T = 0.8T，不可改進(jìn)部分的執(zhí)行時間為0.2T。已知3個部件改進(jìn)后的加速比分別為S130，S220，S310，因此3個部件改進(jìn)后的執(zhí)行時間為： 改進(jìn)后整個系統(tǒng)的執(zhí)行時間為：Tn = 0.045T+0.2T = 0.245T那么系統(tǒng)中不可改進(jìn)部分的執(zhí)行時間在總執(zhí)行時間中占的比例是：3. 設(shè)指令流水線由取指令、分析指令和執(zhí)行指令3個部件構(gòu)成，每個部件經(jīng)過的時間為t，連續(xù)流入12條指令

4、。分別畫出標(biāo)量流水處理機以及ILP均為4的超標(biāo)量處理機、超長指令字處理機、超流水處理機的時空圖，并分別計算它們相對于標(biāo)量流水處理機的加速比。參考答案：解：標(biāo)量流水處理機的時空圖：執(zhí)行完12條指令需T114t。超標(biāo)量流水處理機與超長指令字處理機的時空圖：超標(biāo)量流水處理機中，每一個時鐘周期同時啟動4條指令。執(zhí)行完12條指令需T25t，相對于標(biāo)量流水處理機的加速比為：超長指令字處理機中，每4條指令組成一條長指令，共形成3條長指令。執(zhí)行完12條指令需T35t，相對于標(biāo)量流水處理機的加速比為：超流水處理機的時空圖：超流水處理機中，每1/4個時鐘周期啟動一條指令。執(zhí)行完12條指令需T45.75t，相對于標(biāo)

5、量流水處理機的加速比為：4. 設(shè)一條指令的執(zhí)行過程分成取指令、分析指令和執(zhí)行指令三個階段，每個階段所需的時間分別為t、t和2t 。分別求出下列各種情況下，連續(xù)執(zhí)行N條指令所需的時間。 只有“取指令”與“執(zhí)行指令”重疊； “取指令”、“分析指令”與“執(zhí)行指令”重疊。參考答案： 連續(xù)執(zhí)行N條指令所需的時間為：4t3（N-1）t（3N1）t 連續(xù)執(zhí)行N條指令所需的時間為：4t2（N-1）t（2N2）t5.有一指令流水線如下所示 求連續(xù)輸入10條指令，該流水線的實際吞吐率和效率； 該流水線的“瓶頸”在哪一段？請采取兩種不同的措施消除此“瓶頸”。對于你所給出的兩種新的流水線，連續(xù)輸入10條指令時，其實際

6、吞吐率和效率各是多少？ 參考答案：（1）（2）瓶頸在3、4段。n 變成八級流水線（細(xì)分）n 重復(fù)設(shè)置部件123-13-24-14-24-34-46. 動態(tài)多功能流水線由6個功能段組成，如下圖：其中，S1、S4、S5、S6組成乘法流水線，S1、S2、S3、S6組成加法流水線，各個功能段時間均為50ns，假設(shè)該流水線的輸出結(jié)果可以直接返回輸入端，而且設(shè)置有足夠的緩沖寄存器，若以最快的方式用該流水計算： 畫出時空圖； 計算實際的吞吐率、加速比和效率。參考答案： 7. 某向量處理機有16個向量寄存器，其中V0V5中分別放有向量A、B、C、D、E、F，向量長度均為8，向量各元素均為浮點數(shù)；處理部件采用兩

7、條單功能流水線，加法功能部件時間為2拍，乘法功能部件時間為3拍。采用類似于CARY-1的鏈接技術(shù)，先計算（A+B）*C，在流水線不停流的情況下，接著計算（D+E）*F。求此鏈接流水線的通過時間？（設(shè)寄存器入、出各需1拍）假如每拍時間為50ns，完成這些計算并把結(jié)果存進(jìn)相應(yīng)寄存器，此處理部件的實際吞吐率為多少MFLOPS？參考答案：解：（1）在這里假設(shè)AB的中間結(jié)果放在V6中，（AB）C地最后結(jié)果放在V7中，DE地中間結(jié)果放在V8中，（DE）F的最后結(jié)果放在V9中。具體實現(xiàn)參考下圖：通過時間應(yīng)該為前者（AB）C）通過的時間：T通過= (1+2+1)+(1+3+1) =9（拍）（2）在做完（AB）

8、C之后，作（CD）E就不需要通過時間了。V6AB V7V6C V8DE V9V8F8. 假設(shè)分支目標(biāo)緩沖的命中率為90%，程序中無條件轉(zhuǎn)移指令的比例為5%，沒有無條件轉(zhuǎn)移指令的程序CPI值為1。假設(shè)分支目標(biāo)緩沖中包含分支目標(biāo)指令，允許無條件轉(zhuǎn)移指令進(jìn)入分支目標(biāo)緩沖，則程序的CPI值為多少？ 參考答案： 解：設(shè)每條無條件轉(zhuǎn)移指令的延遲為x，則有：15%x1.1 x2當(dāng)分支目標(biāo)緩沖命中時，無條件轉(zhuǎn)移指令的延遲為0。所以 程序的CPI 1 2 5% (1 90%) 1.019. 一臺32個處理器的計算機，對遠(yuǎn)程存儲器訪問時間為400ns。除了通信以外，假設(shè)計算中的訪問均命中局部存儲器。當(dāng)發(fā)出一個遠(yuǎn)程

9、請求時，本處理器掛起。處理器時鐘時間為1GHz，如果指令基本的IPC為2(設(shè)所有訪存均命中Cache)，求在沒有遠(yuǎn)程訪問的狀態(tài)下與有0.2%的指令需要遠(yuǎn)程訪問的狀態(tài)下，前者比后者快多少?參考答案：解:沒有遠(yuǎn)程訪問時，機器的CPI為 1/基本IPC=1/2=0.5 有0.2%遠(yuǎn)程訪問的機器的實際CPI為 CPI基本CPI遠(yuǎn)程訪問率遠(yuǎn)程訪問開銷 0.50.2%遠(yuǎn)程訪問開銷 遠(yuǎn)程訪問開銷為 ：遠(yuǎn)程訪問時間/時鐘周期時間400 ns/1 ns400個時鐘周期 CPI0.50.2%4001.3 因此在沒有遠(yuǎn)程訪問的情況下的計算機速度是有0.2%遠(yuǎn)程訪問的計算機速度的1.3/0.5=2.6倍。10. 簡述

10、Tomasulo算法的基本思想。參考答案：答：核心思想是： 記錄和檢測指令相關(guān)，操作數(shù)一旦就緒就立即執(zhí)行，把發(fā)生RAW沖突的可能性減小到最少； 通過寄存器換名來消除WAR沖突和WAW沖突。寄存器換名是通過保留站來實現(xiàn)，它保存等待流出和正在流出指令所需要的操作數(shù)?；舅枷耄褐灰僮鲾?shù)有效，就將其取到保留站，避免指令流出時才到寄存器中取數(shù)據(jù)，這就使得即將執(zhí)行的指令從相應(yīng)的保留站中取得操作數(shù)，而不是從寄存器中。指令的執(zhí)行結(jié)果也是直接送到等待數(shù)據(jù)的其它保留站中去。因而，對于連續(xù)的寄存器寫，只有最后一個才真正更新寄存器中的內(nèi)容。一條指令流出時，存放操作數(shù)的寄存器名被換成為對應(yīng)于該寄存器保留站的名稱（編號

11、）。11. 假定有一個處理機臺數(shù)為p的共享存儲器多處理機系統(tǒng)。設(shè)m為典型處理機每條指令執(zhí)行時對全局存儲器進(jìn)行訪問的平均次數(shù)。設(shè)t為共享存儲器的平均存取時間，x為使用本地存儲器的單處理機MIPS速率。再假定在多處理機的每臺處理機上執(zhí)行n條指令。 根據(jù)參數(shù)m，t，x，n和p，確定多處理機的有效MIPS速率。 假設(shè)一臺多處理機有p=32臺RISC處理機，m=0.4，t=1us，要使多處理機的有效性能達(dá)到56MIPS，需要每臺處理機的MIPS速率是多少（即x=？）？ 假設(shè)有p=32臺CISC處理機用在上述多處理機系統(tǒng)中，每臺處理機的x=2MIPS、m=1.6、t=1us，試問多處理機系統(tǒng)的有效MIPS

12、速率是多少？參考答案： 解：（1）有效MIPS速率=p*x/(1+m*x*t) （2）32*x/(10.4*x*1)=56，得x=5.83 （3）有效MIPS速率=p*x/(1+m*x*t)=32*2/(1+1.6*2*1)=15.2412. 假設(shè)對指令Cache的訪問占全部訪問的75%；而對數(shù)據(jù)Cache的訪問占全部訪問的25%。Cache的命中時間為1個時鐘周期，失效開銷為50 個時鐘周期，在混合Cache中一次load或store操作訪問Cache的命中時間都要增加一個時鐘周期，32KB的指令Cache的失效率為0.15%，32KB的數(shù)據(jù)Cache的失效率為3.77%，64KB的混合Ca

13、che的失效率為0.95%。又假設(shè)采用寫直達(dá)策略，且有一個寫緩沖器，并且忽略寫緩沖器引起的等待。試問指令Cache和數(shù)據(jù)Cache容量均為32KB的分離Cache和容量為64KB的混合Cache相比，哪種Cache的失效率更低？兩種情況下平均訪存時間各是多少？參考答案：解：（1）根據(jù)題意，約75%的訪存為取指令。因此，分離Cache的總體失效率為：（75%0.15%）（25%3.77%）1.055%； 容量為128KB的混合Cache的失效率略低一些，只有0.95%。 （2）平均訪存時間公式可以分為指令訪問和數(shù)據(jù)訪問兩部分： 平均訪存時間指令所占的百分比（讀命中時間讀失效率失效開銷） 數(shù)據(jù)所占

14、的百分比（數(shù)據(jù)命中時間數(shù)據(jù)失效率失效開銷） 所以，兩種結(jié)構(gòu)的平均訪存時間分別為： 分離Cache的平均訪存時間75%（10.15%50）25%（13.77%50）（75%1.075）（25%2.885）1.5275 混合Cache的平均訪存時間75%（10.95%50）25%（110.95%50）（75%1.475）（25%2.475）1.725因此，盡管分離Cache的實際失效率比混合Cache的高，但其平均訪存時間反而較低。分離Cache提供了兩個端口，消除了結(jié)構(gòu)相關(guān)。13. 給定以下的假設(shè)，試計算直接映象Cache和兩路組相聯(lián)Cache的平均訪問時間以及CPU的性能。由計算結(jié)果能得出什么

15、結(jié)論？（1） 理想Cache情況下的CPI為2.0，時鐘周期為2ns，平均每條指令訪存1.2次；（2） 兩者Cache容量均為64KB，塊大小都是32字節(jié)；（3） 組相聯(lián)Cache中的多路選擇器使CPU的時鐘周期增加了10；（4） 這兩種Cache的失效開銷都是80ns；（5） 命中時間為1個時鐘周期；（6） 64KB直接映象Cache的失效率為1.4，64KB兩路組相聯(lián)Cache的失效率為1.0。參考答案：解： 平均訪問時間命中時間失效率失效開銷平均訪問時間1-路=2.0+1.4% *80=3.12ns平均訪問時間2-路=2.0*(1+10%)+1.0% *80=3.0ns兩路組相聯(lián)的平均訪

16、問時間比較低CPUtime=（CPU執(zhí)行+存儲等待周期）*時鐘周期CPU time=IC（CPI執(zhí)行+總失效次數(shù)/指令總數(shù)*失效開銷） *時鐘周期=IC（CPI執(zhí)行*時鐘周期）+（每條指令的訪存次數(shù)*失效率*失效開銷*時鐘周期）CPU time 1-way=IC(2.0*2+1.2*0.014*80)5.344ICCPU time 2-way=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倍。因此這里選擇兩路組相

17、聯(lián)。14. 假設(shè)一臺計算機具有以下特性：（1） 95的訪存在Cache中命中；（2） 塊大小為兩個字，且失效時整個塊被調(diào)入；（3） CPU發(fā)出訪存請求的速率為109字/s；（4） 25的訪存為寫訪問；（5） 存儲器的最大流量為109字/s（包括讀和寫）；（6） 主存每次只能讀或?qū)懸粋€字；（7） 在任何時候，Cache中有30的塊被修改過；（8） 寫失效時，Cache采用按寫分配法?，F(xiàn)欲給該計算機增添一臺外設(shè)，為此首先想知道主存的頻帶已用了多少。試對于以下兩種情況計算主存頻帶的平均使用比例。（1） 寫直達(dá)Cache；（2） 寫回法Cache。參考答案：解：采用按寫分配（1）寫直達(dá)cache訪問命

18、中，有兩種情況：讀命中，不訪問主存；寫命中，更新cache和主存，訪問主存一次。訪問失效，有兩種情況：讀失效，將主存中的塊調(diào)入cache中，訪問主存兩次；寫失效，將要寫的塊調(diào)入cache，訪問主存兩次，再將修改的數(shù)據(jù)寫入cache和主存，訪問主存一次，共三次。上述分析如下表所示。訪問命中訪問類型頻率訪存次數(shù)Y讀95%*75%=71.3%0Y寫95%*25%=23.8%1N讀5%*75%=3.8%2N寫5%*25%=1.3%3一次訪存請求最后真正的平均訪存次數(shù)=(71.3%*0)+(23.8%*1)+(3.8%*2)+(1.3%*3)0.35已用帶寬=0.35109/10 9 =35.0%（2）

19、寫回法cache訪問命中,有兩種情況：讀命中，不訪問主存；寫命中，不訪問主存。采用寫回法，只有當(dāng)修改的cache塊被換出時，才寫入主存；訪問失效,有一個塊將被換出，這也有兩種情況：如果被替換的塊沒有修改過，將主存中的塊調(diào)入cache塊中，訪問主存兩次；如果被替換的塊修改過，則首先將修改的塊寫入主存，需要訪問主存兩次；然后將主存中的塊調(diào)入cache塊中，需要訪問主存兩次，共四次訪問主存。訪問命中塊為臟頻率訪存次數(shù)YN95%*70%=66.5%0YY95%*30%=28.5%0NN5%*70%=3.5%2NY5%*30%=1.5%4所以：一次訪存請求最后真正的平均訪存次數(shù)=66.5*028.5%*

20、0+3.5%*2+1.5%*4=0.13已用帶寬0.1310 9/10 913%15. 降低Cache失效率有哪幾種方法？簡述其基本思想。參考答案：答：常用的降低Cache失效率的方法有下面幾種：（1） 增加Cache塊大小。增加塊大小利用了程序的空間局部性。（2） 增加Cache的容量。（3） 提高相聯(lián)度，降低沖突失效。（4） 偽相聯(lián)Cache，降低沖突失效。當(dāng)對偽相聯(lián)Cache進(jìn)行訪問時，首先是按與直接映象相同的方式進(jìn)行訪問。如果命中，則從相應(yīng)的塊中取出所訪問的數(shù)據(jù)，送給CPU，訪問結(jié)束。如果不命中，就將索引字段的最高位取反，然后按照新索引去尋找“偽相聯(lián)組”中的對應(yīng)塊。如果這一塊的標(biāo)識匹配

21、，則稱發(fā)生了“偽命中”。否則，就訪問下一級存儲器。（5） 硬件預(yù)取技術(shù)。在處理器提出訪問請求前預(yù)取指令和數(shù)據(jù)。（6） 由編譯器控制的預(yù)取，硬件預(yù)取的替代方法，在編譯時加入預(yù)取的指令，在數(shù)據(jù)被用到之前發(fā)出預(yù)取請求。（7） 編譯器優(yōu)化，通過對軟件的優(yōu)化來降低失效率。（8） “犧牲”Cache。在Cache和其下一級存儲器的數(shù)據(jù)通路之間增設(shè)一個全相聯(lián)的小Cache，存放因沖突而被替換出去的那些塊。每當(dāng)發(fā)生不命中時，在訪問下一級存儲器之前，先檢查“犧牲”Cache中是否含有所需的塊。如果有，就將該塊與Cache中某個塊做交換，把所需的塊從“犧牲”Cache 調(diào)入Cache。16.假設(shè)Cache失效開銷為50個時鐘周期，當(dāng)不考慮存儲器停頓時，所有指令的執(zhí)行時間都是2.0個時鐘周期， Cache的失效率為2%，平均每條指令訪存1.33次。試分析Cache對性能的影響。解： CPU時間也增加為原來的1.67倍。但若不采用Cache