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

./1.假設有一條長流水線,僅僅對條件轉(zhuǎn)移指令使用分支目標緩沖。假設分支預測錯誤的開銷為4個時鐘周期,緩沖不命中的開銷為3個時鐘周期。假設：命中率為90%,預測精度為90%,分支頻率為15%,沒有分支的基本CPI為1。①求程序執(zhí)行的CPI。②相對于采用固定的2個時鐘周期延遲的分支處理,哪種方法程序執(zhí)行速度更快？參考答案：解：〔1程序執(zhí)行的CPI=沒有分支的基本CPI〔1+分支帶來的額外開銷分支帶來的額外開銷是指在分支指令中,緩沖命中但預測錯誤帶來的開銷與緩沖沒有命中帶來的開銷之和。分支帶來的額外開銷=15%*<90%命中×10%預測錯誤×4+10％沒命中×3>=0.099所以,程序執(zhí)行的CPI＝1＋0.099=1.099〔2采用固定的2個時鐘周期延遲的分支處理CPI=1+15%×2=1.3由〔1〔2可知分支目標緩沖方法執(zhí)行速度快。2.計算機系統(tǒng)中有三個部件可以改進,這三個部件的部件加速比為：部件加速比1=30；部件加速比2=20部件加速比3=10如果部件2和部件3的可改進比例均為30%,那么當部件1的可改進比例為多少時,系統(tǒng)加速比才可以達到10？②如果三個部件的可改進比例分別為20%、10%和30%,三個部件同時改進,那么系統(tǒng)中不可加速部分的執(zhí)行時間在總執(zhí)行時間中占的比例是多少？參考答案：解：〔1在多個部件可改進情況下,Amdahl定理的擴展：已知S1＝30,S2＝15,S3＝15,Sn＝10,F1＝0.3,F2＝0.3,得：得F3＝0.36,即部件3的可改進比例為36%?！?設系統(tǒng)改進前的執(zhí)行時間為T,則3個部件改進前的執(zhí)行時間為：〔0.3+0.3+0.2T=0.8T,不可改進部分的執(zhí)行時間為0.2T。已知3個部件改進后的加速比分別為S1＝30,S2＝20,S3＝10,因此3個部件改進后的執(zhí)行時間為：改進后整個系統(tǒng)的執(zhí)行時間為：Tn=0.045T+0.2T=0.245T那么系統(tǒng)中不可改進部分的執(zhí)行時間在總執(zhí)行時間中占的比例是：3.設指令流水線由取指令、分析指令和執(zhí)行指令3個部件構(gòu)成,每個部件經(jīng)過的時間為△t,連續(xù)流入12條指令。分別畫出標量流水處理機以及ILP均為4的超標量處理機、超長指令字處理機、超流水處理機的時空圖,并分別計算它們相對于標量流水處理機的加速比。參考答案：解：標量流水處理機的時空圖：執(zhí)行完12條指令需T1＝14△t。超標量流水處理機與超長指令字處理機的時空圖：超標量流水處理機中,每一個時鐘周期同時啟動4條指令。執(zhí)行完12條指令需T2＝5△t,相對于標量流水處理機的加速比為：超長指令字處理機中,每4條指令組成一條長指令,共形成3條長指令。執(zhí)行完12條指令需T3＝5△t,相對于標量流水處理機的加速比為：超流水處理機的時空圖：超流水處理機中,每1/4個時鐘周期啟動一條指令。執(zhí)行完12條指令需T4＝5.75△t,相對于標量流水處理機的加速比為：4.設一條指令的執(zhí)行過程分成取指令、分析指令和執(zhí)行指令三個階段,每個階段所需的時間分別為△t、△t和2△t。分別求出下列各種情況下,連續(xù)執(zhí)行N條指令所需的時間。只有"取指令"與"執(zhí)行指令"重疊；"取指令"、"分析指令"與"執(zhí)行指令"重疊。參考答案：①連續(xù)執(zhí)行N條指令所需的時間為：4△t＋3〔N-1△t＝〔3N＋1△t連續(xù)執(zhí)行N條指令所需的時間為：4△t＋2〔N-1△t＝〔2N＋2△t5.有一指令流水線如下所示求連續(xù)輸入10條指令,該流水線的實際吞吐率和效率；②該流水線的"瓶頸"在哪一段？請采取兩種不同的措施消除此"瓶頸"。對于你所給出的兩種新的流水線,連續(xù)輸入10條指令時,其實際吞吐率和效率各是多少？參考答案：〔1〔2瓶頸在3、4段。變成八級流水線〔細分重復設置部件1123-13-24-14-24-34-46.動態(tài)多功能流水線由6個功能段組成,如下圖：其中,S1、S4、S5、S6組成乘法流水線,S1、S2、S3、S6組成加法流水線,各個功能段時間均為50ns,假設該流水線的輸出結(jié)果可以直接返回輸入端,而且設置有足夠的緩沖寄存器,若以最快的方式用該流水計算：畫出時空圖；計算實際的吞吐率、加速比和效率。參考答案：7.某向量處理機有16個向量寄存器,其中V0~V5中分別放有向量A、B、C、D、E、F,向量長度均為8,向量各元素均為浮點數(shù)；處理部件采用兩條單功能流水線,加法功能部件時間為2拍,乘法功能部件時間為3拍。采用類似于CARY-1的技術(shù),先計算〔A+B*C,在流水線不停流的情況下,接著計算〔D+E*F。①求此流水線的通過時間？〔設寄存器入、出各需1拍②假如每拍時間為50ns,完成這些計算并把結(jié)果存進相應寄存器,此處理部件的實際吞吐率為多少MFLOPS？參考答案：解：〔1在這里假設A＋B的中間結(jié)果放在V6中,〔A＋B×C地最后結(jié)果放在V7中,D＋E地中間結(jié)果放在V8中,〔D＋E×F的最后結(jié)果放在V9中。具體實現(xiàn)參考下圖：通過時間應該為前者〔〔A＋B×C通過的時間：T通過=<1+2+1>+<1+3+1>=9〔拍〔2在做完〔A＋B×C之后,作〔C＋D×E就不需要通過時間了。V6←A＋BV7←V6×CV8←D＋EV9←V8×F8.假設分支目標緩沖的命中率為90%,程序中無條件轉(zhuǎn)移指令的比例為5%,沒有無條件轉(zhuǎn)移指令的程序CPI值為1。假設分支目標緩沖中包含分支目標指令,允許無條件轉(zhuǎn)移指令進入分支目標緩沖,則程序的CPI值為多少？參考答案：解：設每條無條件轉(zhuǎn)移指令的延遲為x,則有：1＋5%×x＝1.1x＝2當分支目標緩沖命中時,無條件轉(zhuǎn)移指令的延遲為0。所以程序的CPI＝1＋2×5%×<1－90%>＝1.019.一臺32個處理器的計算機,對遠程存儲器訪問時間為400ns。除了通信以外,假設計算中的訪問均命中局部存儲器。當發(fā)出一個遠程請求時,本處理器掛起。處理器時鐘時間為1GHz,如果指令基本的IPC為2<設所有訪存均命中Cache>,求在沒有遠程訪問的狀態(tài)下與有0.2%的指令需要遠程訪問的狀態(tài)下,前者比后者快多少?參考答案：解:沒有遠程訪問時,機器的CPI為1/基本IPC=1/2=0.5有0.2%遠程訪問的機器的實際CPI為CPI＝基本CPI＋遠程訪問率×遠程訪問開銷＝0.5＋0.2%×遠程訪問開銷遠程訪問開銷為：遠程訪問時間/時鐘周期時間＝400ns/1ns＝400個時鐘周期∴CPI＝0.5＋0.2%×400＝1.3因此在沒有遠程訪問的情況下的計算機速度是有0.2%遠程訪問的計算機速度的1.3/0.5=2.6倍。10.簡述Tomasulo算法的基本思想。參考答案：答：核心思想是：①記錄和檢測指令相關(guān),操作數(shù)一旦就緒就立即執(zhí)行,把發(fā)生RAW沖突的可能性減小到最少；②通過寄存器換名來消除WAR沖突和WAW沖突。寄存器換名是通過保留站來實現(xiàn),它保存等待流出和正在流出指令所需要的操作數(shù)?；舅枷耄褐灰僮鲾?shù)有效,就將其取到保留站,避免指令流出時才到寄存器中取數(shù)據(jù),這就使得即將執(zhí)行的指令從相應的保留站中取得操作數(shù),而不是從寄存器中。指令的執(zhí)行結(jié)果也是直接送到等待數(shù)據(jù)的其它保留站中去。因而,對于連續(xù)的寄存器寫,只有最后一個才真正更新寄存器中的容。一條指令流出時,存放操作數(shù)的寄存器名被換成為對應于該寄存器保留站的名稱〔編號。11.假定有一個處理機臺數(shù)為p的共享存儲器多處理機系統(tǒng)。設m為典型處理機每條指令執(zhí)行時對全局存儲器進行訪問的平均次數(shù)。設t為共享存儲器的平均存取時間,x為使用本地存儲器的單處理機MIPS速率。再假定在多處理機的每臺處理機上執(zhí)行n條指令。①根據(jù)參數(shù)m,t,x,n和p,確定多處理機的有效MIPS速率。②假設一臺多處理機有p=32臺RISC處理機,m=0.4,t=1us,要使多處理機的有效性能達到56MIPS,需要每臺處理機的MIPS速率是多少〔即x=？？③假設有p=32臺CISC處理機用在上述多處理機系統(tǒng)中,每臺處理機的x=2MIPS、m=1.6、t=1us,試問多處理機系統(tǒng)的有效MIPS速率是多少？參考答案：解：〔1有效MIPS速率=p*x/<1+m*x*t>〔232*x/<1－0.4*x*1>=56,得x=5.83〔3有效MIPS速率=p*x/<1+m*x*t>=32*2/<1+1.6*2*1>=15.2412.假設對指令Cache的訪問占全部訪問的75%；而對數(shù)據(jù)Cache的訪問占全部訪問的25%。Cache的命中時間為1個時鐘周期,失效開銷為50個時鐘周期,在混合Cache中一次load或store操作訪問Cache的命中時間都要增加一個時鐘周期,32KB的指令Cache的失效率為0.15%,32KB的數(shù)據(jù)Cache的失效率為3.77%,64KB的混合Cache的失效率為0.95%。又假設采用寫直達策略,且有一個寫緩沖器,并且忽略寫緩沖器引起的等待。試問指令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ù)所占的百分比×〔數(shù)據(jù)命中時間＋數(shù)據(jù)失效率×失效開銷所以,兩種結(jié)構(gòu)的平均訪存時間分別為：分離Cache的平均訪存時間＝75%×〔1＋0.15%×50＋25%×〔1＋3.77%×50＝〔75%×1.075＋〔25%×2.885＝1.5275混合Cache的平均訪存時間＝75%×〔1＋0.95%×50＋25%×〔1＋1＋0.95%×50＝〔75%×1.475＋〔25%×2.475＝1.725因此,盡管分離Cache的實際失效率比混合Cache的高,但其平均訪存時間反而較低。分離Cache提供了兩個端口,消除了結(jié)構(gòu)相關(guān)。13.給定以下的假設,試計算直接映象Cache和兩路組相聯(lián)Cache的平均訪問時間以及CPU的性能。由計算結(jié)果能得出什么結(jié)論？理想Cache情況下的CPI為2.0,時鐘周期為2ns,平均每條指令訪存1.2次；兩者Cache容量均為64KB,塊大小都是32字節(jié)；組相聯(lián)Cache中的多路選擇器使CPU的時鐘周期增加了10％；這兩種Cache的失效開銷都是80ns；命中時間為1個時鐘周期；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)的平均訪問時間比較低CPUtime=〔CPU執(zhí)行+存儲等待周期*時鐘周期CPUtime=IC〔CPI執(zhí)行+總失效次數(shù)/指令總數(shù)*失效開銷*時鐘周期=IC〔〔CPI執(zhí)行*時鐘周期+〔每條指令的訪存次數(shù)*失效率*失效開銷*時鐘周期CPUtime1-way=IC<2.0*2+1.2*0.014*80>＝5.344ICCPUtime2-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倍。因此這里選擇兩路組相聯(lián)。14.假設一臺計算機具有以下特性：95％的訪存在Cache中命中；塊大小為兩個字,且失效時整個塊被調(diào)入；CPU發(fā)出訪存請求的速率為109字/s；25％的訪存為寫訪問；存儲器的最大流量為109字/s〔包括讀和寫；主存每次只能讀或?qū)懸粋€字；在任何時候,Cache中有30％的塊被修改過；寫失效時,Cache采用按寫分配法?，F(xiàn)欲給該計算機增添一臺外設,為此首先想知道主存的頻帶已用了多少。試對于以下兩種情況計算主存頻帶的平均使用比例。寫直達Cache；寫回法Cache。參考答案：解：采用按寫分配〔1寫直達cache訪問命中,有兩種情況：讀命中,不訪問主存；寫命中,更新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.35×109/109=35.0%〔2寫回法cache訪問命中,有兩種情況：讀命中,不訪問主存；寫命中,不訪問主存。采用寫回法,只有當修改的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％*0＋28.5%*0+3.5%*2+1.5%*4=0.13已用帶寬＝0.13×109/109＝13%15.降低Cache失效率有哪幾種方法？簡述其基本思想。參考答案：答：常用的降低Cache失效率的方法有下面幾種：增加Cache塊大小。增加塊大小利用了程序的空間局部性。增加Cache的容量。提高相聯(lián)度,降低沖突失效。偽相聯(lián)Cache,降低沖突失效。當對偽相聯(lián)Cache進行訪問時,首先是按與直接映象相同的方式進行訪問。如果命中,則從相應的塊中取出所訪問的數(shù)據(jù),送給CPU,訪問結(jié)束。如果不命中,就將索引字段的最高位取反,然后按照新索引去尋找"偽相聯(lián)組"中的對應塊。如果這一塊的標識匹配,則稱發(fā)生了"偽命中"。否則,就訪問下一級存儲器。硬件預取技術(shù)。在處理器提出訪問請求前預取指令和數(shù)據(jù)。由編譯器控制的預取,硬件預取的替代方法,在編譯時加入預取的指令,在數(shù)據(jù)被用到之前發(fā)出預取請求。編譯器優(yōu)化,通過對軟件的優(yōu)化來降低失效率。"犧牲"Cache。在Cache和其下一級存儲器的數(shù)據(jù)通路之間增設一個全相聯(lián)的小Cache,存放因沖突而被替換出去的那些塊。每當發(fā)生不命中時,在訪問下一級存儲器之前,先檢查"犧牲"Cache中是否含有所需的塊。如果有,就將該塊與Cache中某個塊做交換,把所需的塊從"犧牲"Cache調(diào)入Cache。16.假設Cache失效開銷為50個時鐘周期,當不考慮存儲器停頓時,所有指令的執(zhí)行時間都是2.0個時鐘周期,Cache的失效率為2%,平均每條指令訪存1.33次。試分析Cache對性能的影響。解：CPU時間也增加為原來的1.67倍。但若不采用Cache,則：CPI＝2.0+50×1.33＝68.5