計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)考試計(jì)算題

1、精品文檔3.12有一指令流水線如下所示入50ns 50ns 100ns200ns出(2)(1) 求連續(xù)輸入10條指令，該流水線的實(shí)際吞吐率和效率；(2) 該流水線的 瓶頸”在哪一段？請(qǐng)采取兩種不同的措施消除此瓶頸” 對(duì)于你所給出的兩種新的流水線，連續(xù)輸入 10條指令時(shí)，其實(shí)際吞吐 率和效率各是多少？解：(1)T pipeli nemti (n 1) tmaxi 1(5050 100 200) 9 2002200( ns)tiTP丄TP /Tpipeline220 (s4005TP45.45%411(2)瓶頸在3、4段。 變成八級(jí)流水線(細(xì)分)50ns50ns50ns50ns50ns出4_4 5

2、0 nsmT pipeli neti (n 1) tmaxi 150 8 9 50850( ns)TP nTI pipelinemtii 140010E TP 一 TP58.82%m817重復(fù)設(shè)置部件TPnTpipe-E 410850 81017 呢82%4_1153_22468 |103_1159212345678910112345678910_4-14_44_34 2432 6109時(shí)間3.134段組成, 3段時(shí)， 一次，然 段。如果* 3-2* 4-2 4-4850ns有一個(gè)流水線由 其中每當(dāng)流經(jīng)第 總要在該段循環(huán) 后才能流到第 4 每段經(jīng)過(guò)一次所需要的時(shí)間都是t，問(wèn)：(1) 當(dāng)在流水線

3、的輸入端連續(xù)地每 t時(shí)間輸入任務(wù)時(shí)，該流水線會(huì)發(fā)生 什么情況？(2) 此流水線的最大吞吐率為多少？如果每 2 t輸入一個(gè)任務(wù)，連續(xù)處理 10個(gè)任務(wù)時(shí)的實(shí)際吞吐率和效率是多少？(3) 當(dāng)每段時(shí)間不變時(shí)，如何提高該流水線的吞吐率？仍連續(xù)處理 10個(gè) 任務(wù)時(shí)，其吞吐率提高多少？解：(1)會(huì)發(fā)生流水線阻塞情況第1個(gè)任 務(wù)S1S2S3S3S4第2個(gè)任 務(wù)S1S2stallS3S3S4第3個(gè)任 務(wù)S1stallS2stallS3S3S4第4個(gè)任 務(wù)S1stallS2stallS3S3S4精品文檔Q345Q81|1|223344556677889910|10時(shí)間12345678910123456789104

4、32123 tTPmaxpipeli ne12 t23 tTpi 1E TP 5 t459254.35%(3)重復(fù)設(shè)置部件TPttt t5 吞吐率提高倍數(shù)=證=1-643.14有一條靜態(tài)多功能流水線由5段組成，加法用1、3、4、5段，乘法用1、2、5段，第3段的時(shí)間為2t,其余各段的時(shí)間均為 t,而且流水線的輸出 可以直接返回輸入端或4(Ai Bi)精品文檔暫存于相應(yīng)的流水寄存器中?，F(xiàn)要在該流水線上計(jì)算，畫出其時(shí)空?qǐng)D，并計(jì)算其吞吐率、加速比和效率。加法乘法乘法解：首先，應(yīng)選擇適合于流水線工作的算法。對(duì)于本題，應(yīng)先計(jì)算 Ai+ Bi、 A2 + B2、A3+ B3 和 A4+ B4；再計(jì)算(Ai

5、 + Bi) X (A2 + B2)和(A3+ B3)X (A4 + B4)； 然后求總的結(jié)果。其次，畫出完成該計(jì)算的時(shí)空?qǐng)D，如圖所示，圖中陰影部分表示該段在工作。B1 B2 B3 B4B DC X D由圖可見(jiàn)，它在18個(gè)厶t時(shí)間中，給出了7個(gè)結(jié)果。所以吞吐率為:TP718 t如果不用流水線，由于一次求積需3 t，一次求和需5A t,則產(chǎn)生上述7個(gè)結(jié)果共需(4X5+3X3) t =29At。所以加速比為：29 t18 t1.61該流水線的效率可由陰影區(qū)的面積和 5個(gè)段總時(shí)空區(qū)的面積的比值求得:4 5 3 35 180.3223.15動(dòng)態(tài)多功能流水線由6個(gè)功能段組成，如下圖:加法S1S2S3S4

6、*S5S6精品文檔其中，S1、S4、S5、S6組成乘法流水線，S1、S2、S3、S6組成加法流水線, 各個(gè)功能段時(shí)間均為 50ns,假設(shè)該流水線的輸出結(jié)果可以直接返回輸入端，而5且設(shè)置有足夠的緩沖寄存器，若以最快的方式用該流水計(jì)算：XiyjZii 1（1）畫出時(shí)空?qǐng)D；（2） 計(jì)算實(shí)際的吞吐率、加速比和效率 解：機(jī)器一共要做10次乘法，4次加法TP =22At加速比=22 At=2. 55=42.3.16在MIPS流水線上運(yùn)行如下代碼序列:LOOP:LWR1,0（ R2）DADDIUR1,R1, #1SWR1,0（ R2）DADDIUR2,R2, #4DSUBR4,R3, R2BNEZR4,LO

7、OP其中：R3的初值是R2+396。假設(shè):在整個(gè)代碼序列的運(yùn)行過(guò)程中，所有的存儲(chǔ)器訪問(wèn)都是命中的，并且在一個(gè)時(shí)鐘周期中對(duì)同一個(gè)寄存器的讀操作和寫 操作可以通過(guò)寄存器文件 定向”問(wèn)：（1）在沒(méi)有任何其它定向（或旁路）硬件的支持下，請(qǐng)畫出該指令序列 執(zhí)行的流水線時(shí)空?qǐng)D。假設(shè)采用排空流水線的策略處理分支指令，且 所有的存儲(chǔ)器訪問(wèn)都命中Cache那么執(zhí)行上述循環(huán)需要多少個(gè)時(shí)鐘周 期？（2）假設(shè)該流水線有正常的定向路徑，請(qǐng)畫出該指令序列執(zhí)行的流水線 時(shí)空?qǐng)D。假設(shè)采用預(yù)測(cè)分支失敗的策略處理分支指令，且所有的存儲(chǔ) 器訪問(wèn)都命中Cache那么執(zhí)行上述循環(huán)需要多少個(gè)時(shí)鐘周期？(3) 假設(shè)該流水線有正常的定向路徑

8、和一個(gè)單周期延遲分支，請(qǐng)對(duì)該循環(huán)中的指令進(jìn)行調(diào)度，你可以重新組織指令的順序，也可以修改指令 的操作數(shù)，但是注意不能增加指令的條數(shù)。請(qǐng)畫出該指令序列執(zhí)行的 流水線時(shí)空?qǐng)D，并計(jì)算執(zhí)行上述循環(huán)所需要的時(shí)鐘周期數(shù)。解：寄存器讀寫可以定向，無(wú)其他旁路硬件支持。排空流水線。指令123456789 10 1112 13 14 15 16 17 18 19 20 21 22LWIF ID EX M WBDADDIUIF S S ID EX M WBSWIF S S IDEX MWBDADDIUIFIDEXMWBDSUBIFSSIDEXMWBBNEZIFSSIDEXMWBLWIFSSIF ID EX M WB第

9、i次迭代(i = 0.98)開(kāi)始周期：1+( i x 17) 總的時(shí)鐘周期數(shù)：(98 x 17)+ 18= 1684有正常定向路徑，預(yù)測(cè)分支失敗。指令12345678910 111 131415LWIF IDEXMWBDADDIUIFIDSEXMWBSWIFSIDEXMWBDADDIUIFIDEXMWBDSUBIFIDEXMWBBNEZIFIDEXM WBLWIFmiss miss IFID EXM WB第i次迭代(i = 0.98)開(kāi)始周期：1+( i x 10)總的時(shí)鐘周期數(shù)：(98 x 10)+ 11 = 991有正常定向路徑。單周期延遲分支。LOOP:LWR1，0(R2)DADDIU

10、R2，R2，#4DADDIU R1，R1，#1 DSUB R4，R3，R2BNEZR4，LOOPSWR1，-4(R2)第i次迭代(i = 0.98)開(kāi)始周期：1+( i x 6 )總的時(shí)鐘周期數(shù)：(98x 6)+ 10= 598指令1 234567891011LWIF IDEXMWBDADDIUIFIDEXMWBDADDIUIFIDEXMWBDSUBIFIDEXMWBBNEZIFIDEXMWBSWIFIDEXMWBLWIFIDEXMWB3.17假設(shè)各種分支指令數(shù)占所有指令數(shù)的百分比如下:條件分支20% (其中的60%是分支成功的)跳轉(zhuǎn)和調(diào)用5%現(xiàn)有一條段數(shù)為4的流水線，無(wú)條件分支在第二個(gè)時(shí)鐘周

11、期結(jié)束時(shí)就被解析 出來(lái)，而條件分支要到第三個(gè)時(shí)鐘周期結(jié)束時(shí)才能夠被解析出來(lái)。第一個(gè)流水段是完全獨(dú)立于指令類型的，即所有類型的指令都必須經(jīng)過(guò)第一個(gè)流水段的處理。 請(qǐng)問(wèn)在沒(méi)有任何控制相關(guān)的情況下，該流水線相對(duì)于存在上述控制相關(guān)情況下的 加速比是多少？解：沒(méi)有控制相關(guān)時(shí)流水線的平均 CPI= 1存在控制相關(guān)時(shí)：由于無(wú)條件分支在第二個(gè)時(shí)鐘周期結(jié)束時(shí)就被解析出來(lái)， 而條件分支 要到第3個(gè)時(shí)鐘周期結(jié)束時(shí)才能被解析出來(lái)。所以：(1) 若使用排空流水線的策略，則對(duì)于條件分支，有兩個(gè)額外的stall，對(duì) 無(wú)條件分支，有一個(gè)額外的stall:CPI = 1+20%*2+5%*1 = 1.45加速比 S=CPI/1

12、 = 1.45(2) 若使用預(yù)測(cè)分支成功策略，則對(duì)于不成功的條件分支，有兩個(gè)額外的stall，對(duì)無(wú)條件分支和成功的條件分支，有一個(gè)額外的stall 1：CPI = 1+20%*(60%*1+40%*2) +5%*1 = 1.33 加速比 S=CPI/1 = 1.33(3) 若使用預(yù)測(cè)分支失敗策略，則對(duì)于成功的條件分支，有兩個(gè)額外的stall;對(duì)無(wú)條件分支，有一個(gè)額外的stall;對(duì)不成功的條件分支，其目標(biāo)地址已經(jīng)由PC值給出，不必等待，所以無(wú)延遲：CPI = 1+20%*(60%*2 + 40%*0) +5%*1 = 1.29加速比 S=CPI/1 = 1.295.10假設(shè)對(duì)指令Cache的訪

13、問(wèn)占全部訪問(wèn)的75%;而對(duì)數(shù)據(jù)Cache的訪問(wèn) 占全部訪問(wèn)的25%。Cache的命中時(shí)間為1個(gè)時(shí)鐘周期，失效開(kāi)銷為50個(gè)時(shí)鐘 周期，在混合Cache中一次load或store操作訪問(wèn)Cache的命中時(shí)間都要增加一 個(gè)時(shí)鐘周期，32KB的指令Cache的失效率為0.39%, 32KB的數(shù)據(jù)Cache的失 效率為4.82%, 64KB的混合Cache的失效率為1.35%。又假設(shè)采用寫直達(dá)策略， 且有一個(gè)寫緩沖器，并且忽略寫緩沖器引起的等待。試問(wèn)指令Cache和數(shù)據(jù)Cache 容量均為32KB的分離Cache和容量為64KB的混合Cache相比，明附Cache的 失效率更低？?jī)煞N情況下平均訪存時(shí)間各

14、是多少？解：(1 )根據(jù)題意，約75%的訪存為取指令。因此，分離 Cache的總體失效率為：(75%X 0.15%) + ( 25%X 3.77%) = 1.055%;容量為128KB的混合Cache的失效率略低一些，只有 0.95%。(2)平均訪存時(shí)間公式可以分為指令訪問(wèn)和數(shù)據(jù)訪問(wèn)兩部分：平均訪存時(shí)間二指令所占的百分比X (讀命中時(shí)間+讀失效率X失效開(kāi)銷) +數(shù)據(jù)所占的百分比X (數(shù)據(jù)命中時(shí)間+數(shù)據(jù)失效率X失效開(kāi)銷)所以，兩種結(jié)構(gòu)的平均訪存時(shí)間分別為：分離 Cache的平均訪存時(shí)間=75%X( 1 + 0.15%X 50)+25%X( 1 + 3.77% X 50)=(75%X 1.075)

15、 + ( 25% X 2.885)= 1.5275混合 Cache的平均訪存時(shí)間=75%X (1 + 0.95%X 50)+ 25%X (1 + 1 + 0.95%X 50)=(75% X 1.475) + ( 25%X 2.475)= 1.725因此，盡管分離Cache的實(shí)際失效率比混合Cache的高，但其平均訪存時(shí)間 反而較低。分離Cache提供了兩個(gè)端口，消除了結(jié)構(gòu)相關(guān)。5.11給定以下的假設(shè)，試計(jì)算直接映象Cache和兩路組相聯(lián)Cache的平均訪問(wèn)時(shí)間以及CPU的性能。由計(jì)算結(jié)果能得出什么結(jié)論？(1) 理想Cache情況下的CPI為2.0,時(shí)鐘周期為2ns,平均每條指令訪 存1.2次；

16、(2) 兩者Cache容量均為64KB，塊大小都是32字節(jié)；(3) 組相聯(lián)Cache中的多路選擇器使CPU的時(shí)鐘周期增加了 10%;(4) 這兩種Cache的失效開(kāi)銷都是80ns；(5) 命中時(shí)間為1個(gè)時(shí)鐘周期；(6) 64KB直接映象Cache的失效率為1.4%，64KB兩路組相聯(lián) Cache 的失效率為1.0%。解：平均訪問(wèn)時(shí)間=命中時(shí)間+失效率X失效開(kāi)銷平均訪問(wèn)時(shí)間1-路=2.0+1.4% *80=3.12 ns平均訪問(wèn)時(shí)間 2-路=2.0*(1+10%)+1.0% *80=3.0ns兩路組相聯(lián)的平均訪問(wèn)時(shí)間比較低CPUtime= ( CPU執(zhí)行+存儲(chǔ)等待周期)*時(shí)鐘周期CPU time

17、=IC ( CPI執(zhí)行+總失效次數(shù)/指令總數(shù)*失效開(kāi)銷)*時(shí)鐘周期=IC ( CPI執(zhí)行*時(shí)鐘周期)+ (每條指令的訪存次數(shù)*失效率*失效開(kāi)銷*時(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.36ICCPU相對(duì)性能比：毀5.36/5.344=1.003CPUtime 1way直接映象cache的訪問(wèn)速度比兩路組相聯(lián)cache要快1.04倍，而兩路組相聯(lián) Cache的平均性能比直接映象cache要高1.003倍。因此這里選擇兩路組相聯(lián)。5.12假設(shè)一臺(tái)計(jì)算機(jī)

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

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

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

21、 +28.5%*0+3.5%*2+1.5%*4=0.13已用帶寬=0.13X 10 9/io 9= 13%5.13在偽相聯(lián)中，假設(shè)在直接映象位置沒(méi)有發(fā)現(xiàn)匹配，而在另一個(gè)位置才找到數(shù)據(jù)(偽命中)時(shí)，不對(duì)這兩個(gè)位置的數(shù)據(jù)進(jìn)行交換。這時(shí)只需要1個(gè)額外的周期。假設(shè)失效開(kāi)銷為50個(gè)時(shí)鐘周期，2KB直接映象Cache的失效率為9.8%, 2路組相聯(lián)的失效率為7.6%; 128KB直接映象Cache的失效率為1.0%，2路組 相聯(lián)的失效率為0.7%。(1) 推導(dǎo)出平均訪存時(shí)間的公式。(2) 利用(1)中得到的公式，對(duì)于 2KBCache和128KBCache,計(jì)算偽 相聯(lián)的平均訪存時(shí)間。解：不管作了何種改進(jìn)

22、，失效開(kāi)銷相同。不管是否交換內(nèi)容，在同一“偽相聯(lián)” 組中的兩塊都是用同一個(gè)索引得到的，因此失效率相同，即：失效率 偽相聯(lián)二失效 率2路。偽相聯(lián)cache的命中時(shí)間等于直接映象cache的命中時(shí)間加上偽相聯(lián)查找過(guò) 程中的命中時(shí)間*該命中所需的額外開(kāi)銷。命中時(shí)間偽相聯(lián)=命中時(shí)間1路+偽命中率偽相聯(lián)X 1交換或不交換內(nèi)容，偽相聯(lián)的命中率都是由于在第一次失效時(shí)，將地址取反，再在第二次查找?guī)?lái)的。因此偽命中率偽相聯(lián)=命中率2路一命中率1路=(1失效率2路)一(1 失效 率1路)=失效率1路一失效率2路。交換內(nèi)容需要增加偽相聯(lián)的額 外開(kāi)銷。平均訪存時(shí)間偽相聯(lián)=命中時(shí)間1路+(失效率1路一失效率2路) X

23、1+失效率2路X失效開(kāi)銷1路將題設(shè)中的數(shù)據(jù)帶入計(jì)算，得到：平均訪存時(shí)間 2Kb=1+(0.098-0.076)*1+(0.076 *50 ) =4.822 平均訪存時(shí)間 128Kb=1+(0.010-0.007)*1+(0.007 *50 ) =1.353 顯然是128KB的偽相聯(lián)Cache要快一些。5.14假設(shè)采用理想存儲(chǔ)器系統(tǒng)時(shí)的基本 CPI是1.5,主存延遲是40個(gè)時(shí)鐘 周期；傳輸速率為4字節(jié)/時(shí)鐘周期，且Cache中50%的塊是修改過(guò)的。每個(gè)塊 中有32字節(jié)，20%的指令是數(shù)據(jù)傳送指令。并假設(shè)沒(méi)有寫緩存，在 TLB失效的 情況下需要20時(shí)鐘周期，TLB不會(huì)降低Cache命中率。CPU產(chǎn)

24、生指令地址或 Cache失效時(shí)產(chǎn)生的地址有0.2%沒(méi)有在TLB中找到。(1)在理想TLB情況下，計(jì)算均采用寫回法16KB直接映象統(tǒng)一 Cache 16KB精品文檔兩路組相聯(lián)統(tǒng)一 Cache和32KB直接映象統(tǒng)一 Cache機(jī)器的實(shí)際CPI;（2）在實(shí)際TLB情況下，用（1）的結(jié)果，計(jì)算均采用寫回法16KB直接映象 統(tǒng)一 Cache 16KB兩路組相聯(lián)統(tǒng)一 Cache和32KB直接映象統(tǒng)一 Cache 機(jī)器的實(shí)際CPI ；其中假設(shè)16KB直接映象統(tǒng)一 Cache 16KB兩路組相聯(lián)統(tǒng)一 Cache和32KB 直接映象統(tǒng)一 Cache的失效率分別為2.9%、2.2%和2.0%; 25%的訪存為寫訪

25、問(wèn)。解：CPI=CPI執(zhí)行+存儲(chǔ)停頓周期數(shù)/指令數(shù)存儲(chǔ)停頓由下列原因引起：從主存中取指令load和store指令訪問(wèn)數(shù)據(jù)由TLB引起存儲(chǔ)停頓周期數(shù)取指令停頓丄數(shù)據(jù)訪問(wèn)停頓+ TLB停頓=十指令數(shù)指令數(shù)指令數(shù)停頓周期數(shù)指令數(shù)存儲(chǔ)訪問(wèn)指令數(shù)失效率失效開(kāi)銷存儲(chǔ)停頓周期數(shù)指令數(shù)R指令P指令十（f數(shù)據(jù)R數(shù)據(jù)P數(shù)據(jù)）十TLB停頓指令數(shù)（1）對(duì)于理想TLB , TLB失效開(kāi)銷為0。而對(duì)于統(tǒng)一 Cache, R指令=R數(shù)據(jù) P指令=主存延遲十傳輸一個(gè)塊需要使用的時(shí)間=40+ 32/4= 48 （拍）若為讀失效，P數(shù)據(jù)=主存延遲十傳輸一個(gè)塊需要使用的時(shí)間=40 + 32/4=48 （拍）若為寫失效，且塊是干凈的， P數(shù)據(jù)=主存延遲十傳輸一個(gè)塊需要使用的時(shí)間=40+ 32/4= 48（拍）若為寫失效，且塊是臟的， P數(shù)據(jù)=主存延遲十傳輸兩個(gè)塊需要使用的時(shí)間=40+ 64/4= 56（拍）CPI=1.5+RP+（RP*20%）+0 指令訪存全是讀，而數(shù)據(jù)傳輸指令 Load或Store指令，f數(shù)據(jù)*P數(shù)據(jù)=讀百分比* （f數(shù)據(jù)*P數(shù)據(jù)）十寫百分比* （f數(shù)據(jù)*P干凈數(shù)據(jù)*其對(duì)應(yīng)的 百分比十f數(shù)據(jù)*P臟數(shù)據(jù)*其對(duì)應(yīng)的百分比）=