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

1、3.12 有一指令流水線如下所示（1） 求連續(xù)輸入10條指令，該流水線的實際吞吐率和效率；（2） 該流水線的“瓶頸”在哪一段？請采取兩種不同的措施消除此“瓶頸”。對于你所給出的兩種新的流水線，連續(xù)輸入10條指令時，其實際吞吐率和效率各是多少？解：（1）（2）瓶頸在3、4段。n 變成八級流水線（細分）n 重復(fù)設(shè)置部件123-13-24-14-24-34-43.13有一個流水線由4段組成，其中每當流經(jīng)第3段時，總要在該段循環(huán)一次，然后才能流到第4段。如果每段經(jīng)過一次所需要的時間都是，問：（1） 當在流水線的輸入端連續(xù)地每時間輸入任務(wù)時，該流水線會發(fā)生什么情況？（2） 此流水線的最大吞吐率為多少？如

2、果每輸入一個任務(wù)，連續(xù)處理10個任務(wù)時的實際吞吐率和效率是多少？（3） 當每段時間不變時，如何提高該流水線的吞吐率？仍連續(xù)處理10個任務(wù)時，其吞吐率提高多少？解：（1）會發(fā)生流水線阻塞情況。第1個任務(wù)S1S2S3S3S4第2個任務(wù)S1S2stallS3S3S4第3個任務(wù)S1stallS2stallS3S3S4第4個任務(wù)S1stallS2stallS3S3S4（2）（3）重復(fù)設(shè)置部件吞吐率提高倍數(shù)1.643.14 有一條靜態(tài)多功能流水線由5段組成，加法用1、3、4、5段，乘法用1、2、5段，第3段的時間為2t，其余各段的時間均為t，而且流水線的輸出可以直接返回輸入端或暫存于相應(yīng)的流水寄存器中?，F(xiàn)

3、要在該流水線上計算 ，畫出其時空圖，并計算其吞吐率、加速比和效率。解：首先，應(yīng)選擇適合于流水線工作的算法。對于本題，應(yīng)先計算A1B1、A2B2、A3B3和A4B4；再計算(A1B1) ×(A2B2)和(A3B3) ×(A4B4)；然后求總的結(jié)果。其次，畫出完成該計算的時空圖，如圖所示，圖中陰影部分表示該段在工作。由圖可見，它在18個t時間中，給出了7個結(jié)果。所以吞吐率為： 如果不用流水線，由于一次求積需3t，一次求和需5t，則產(chǎn)生上述7個結(jié)果共需（4×5+3×3）t =29t。所以加速比為： 該流水線的效率可由陰影區(qū)的面積和5個段總時空區(qū)的面積的比值求得

4、： 3.15 動態(tài)多功能流水線由6個功能段組成，如下圖：其中，S1、S4、S5、S6組成乘法流水線，S1、S2、S3、S6組成加法流水線，各個功能段時間均為50ns，假設(shè)該流水線的輸出結(jié)果可以直接返回輸入端，而且設(shè)置有足夠的緩沖寄存器，若以最快的方式用該流水計算：（1） 畫出時空圖；（2） 計算實際的吞吐率、加速比和效率。解：機器一共要做10次乘法，4次加法。3.16 在MIPS流水線上運行如下代碼序列：LOOP： LW R1，0（R2） DADDIU R1，R1，#1 SW R1， 0（R2） DADDIU R2，R2，#4 DSUB R4，R3，R2 BNEZ R4，LOOP 其中：R3的

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

6、支，請對該循環(huán)中的指令進行調(diào)度，你可以重新組織指令的順序，也可以修改指令的操作數(shù)，但是注意不能增加指令的條數(shù)。請畫出該指令序列執(zhí)行的流水線時空圖，并計算執(zhí)行上述循環(huán)所需要的時鐘周期數(shù)。解：寄存器讀寫可以定向，無其他旁路硬件支持。排空流水線。第i次迭代（i0.98）開始周期：1（i×17）總的時鐘周期數(shù)：（98×17）181684有正常定向路徑，預(yù)測分支失敗。第i次迭代（i0.98）開始周期：1（i×10）總的時鐘周期數(shù)：（98×10）11991有正常定向路徑。單周期延遲分支。LOOP: LW R1，0(R2)DADDIU R2，R2，#4DADDIU R

7、1，R1，#1DSUB R4，R3，R2BNEZ R4，LOOPSW R1，-4(R2)第i次迭代（i 0.98）開始周期：1（i ×6 ）總的時鐘周期數(shù)：（98×6）105983.17 假設(shè)各種分支指令數(shù)占所有指令數(shù)的百分比如下：條件分支20%（其中的60%是分支成功的）跳轉(zhuǎn)和調(diào)用5%現(xiàn)有一條段數(shù)為4的流水線，無條件分支在第二個時鐘周期結(jié)束時就被解析出來，而條件分支要到第三個時鐘周期結(jié)束時才能夠被解析出來。第一個流水段是完全獨立于指令類型的，即所有類型的指令都必須經(jīng)過第一個流水段的處理。請問在沒有任何控制相關(guān)的情況下，該流水線相對于存在上述控制相關(guān)情況下的加速比是多少？解

8、：沒有控制相關(guān)時流水線的平均CPI1存在控制相關(guān)時：由于無條件分支在第二個時鐘周期結(jié)束時就被解析出來，而條件分支要到第3個時鐘周期結(jié)束時才能被解析出來。所以：（1）若使用排空流水線的策略，則對于條件分支，有兩個額外的stall，對無條件分支，有一個額外的stall：CPI = 1+20%*2+5%*1 = 1.45 加速比S=CPI/1 = 1.45（2） 若使用預(yù)測分支成功策略，則對于不成功的條件分支，有兩個額外的stall，對無條件分支和成功的條件分支，有一個額外的stall 1：CPI = 1+20%*(60%*1+40%*2) +5%*1 = 1.33 加速比S=CPI/1 = 1.3

9、3（3）若使用預(yù)測分支失敗策略，則對于成功的條件分支，有兩個額外的stall；對無條件分支，有一個額外的stall；對不成功的條件分支，其目標地址已經(jīng)由PC 值給出，不必等待，所以無延遲：CPI = 1+20%*(60%*2 + 40%*0) +5%*1 = 1.29 加速比S=CPI/1 = 1.295.10 假設(shè)對指令Cache的訪問占全部訪問的75%；而對數(shù)據(jù)Cache的訪問占全部訪問的25%。Cache的命中時間為1個時鐘周期，失效開銷為50 個時鐘周期，在混合Cache中一次load或store操作訪問Cache的命中時間都要增加一個時鐘周期，32KB的指令Cache的失效率為0.3

10、9%，32KB的數(shù)據(jù)Cache的失效率為4.82%，64KB的混合Cache的失效率為1.35%。又假設(shè)采用寫直達策略，且有一個寫緩沖器，并且忽略寫緩沖器引起的等待。試問指令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ù)

11、據(jù)訪問兩部分： 平均訪存時間指令所占的百分比×（讀命中時間讀失效率×失效開銷） 數(shù)據(jù)所占的百分比×（數(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%×

12、;2.475）1.725因此，盡管分離Cache的實際失效率比混合Cache的高，但其平均訪存時間反而較低。分離Cache提供了兩個端口，消除了結(jié)構(gòu)相關(guān)。5.11 給定以下的假設(shè)，試計算直接映象Cache和兩路組相聯(lián)Cache的平均訪問時間以及CPU的性能。由計算結(jié)果能得出什么結(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直

13、接映象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í)行+存儲等待周期）*時鐘周期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.344ICCP

14、U 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倍。因此這里選擇兩路組相聯(lián)。5.12 假設(shè)一臺計算機具有以下特性：（1） 95的訪存在Cache中命中；（2） 塊大小為兩個字，且失效時整個塊被調(diào)入；（3） CPU發(fā)出訪存請求的速率為109字/s；（4） 25的訪存為寫訪問；（5） 存儲器的最大流量為109字/s（包括讀和寫）；（6） 主存每次只能讀或?qū)懸粋€字；（7） 在任何時候，Cache

15、中有30的塊被修改過；（8） 寫失效時，Cache采用按寫分配法?，F(xiàn)欲給該計算機增添一臺外設(shè)，為此首先想知道主存的頻帶已用了多少。試對于以下兩種情況計算主存頻帶的平均使用比例。（1） 寫直達Cache；（2） 寫回法Cache。解：采用按寫分配（1）寫直達cache訪問命中，有兩種情況：讀命中，不訪問主存；寫命中，更新cache和主存，訪問主存一次。訪問失效，有兩種情況：讀失效，將主存中的塊調(diào)入cache中，訪問主存兩次；寫失效，將要寫的塊調(diào)入cache，訪問主存兩次，再將修改的數(shù)據(jù)寫入cache和主存，訪問主存一次，共三次。上述分析如下表所示。訪問命中訪問類型頻率訪存次數(shù)Y讀95%*75%=

16、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/10 9 =35.0%（2）寫回法cache訪問命中,有兩種情況：讀命中，不訪問主存；寫命中，不訪問主存。采用寫回法，只有當修改的cache塊被換出時，才寫入主存；訪問失效,有一個塊將被換出，這也有兩種情況：如果被替換的塊沒有修改過，將主存中的塊調(diào)入cache塊中，訪問主存兩次；如果被替換的塊修改過，則首先將修改的塊寫入主存，需要訪問主存兩次

17、；然后將主存中的塊調(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%*0+3.5%*2+1.5%*4=0.13已用帶寬0.13×10 9/10 913%5.13 在偽相聯(lián)中，假設(shè)在直接映象位置沒有發(fā)現(xiàn)匹配，而在另一個位置才找到數(shù)據(jù)（偽命中）時，不對這兩個位置的數(shù)據(jù)進行交換。這時只需要1個額外的周期。假設(shè)失效開銷為50個時鐘周期，2KB直接映象Cache的失效率為9.8%，2

18、路組相聯(lián)的失效率為7.6%；128KB直接映象Cache的失效率為1.0%，2路組相聯(lián)的失效率為0.7%。（1） 推導(dǎo)出平均訪存時間的公式。（2） 利用（1）中得到的公式，對于2KBCache和128KBCache，計算偽相聯(lián)的平均訪存時間。解：不管作了何種改進，失效開銷相同。不管是否交換內(nèi)容，在同一“偽相聯(lián)”組中的兩塊都是用同一個索引得到的，因此失效率相同，即：失效率偽相聯(lián)失效率2路。偽相聯(lián)cache的命中時間等于直接映象cache的命中時間加上偽相聯(lián)查找過程中的命中時間*該命中所需的額外開銷。命中時間偽相聯(lián)命中時間1路偽命中率偽相聯(lián)×1交換或不交換內(nèi)容，偽相聯(lián)的命中率都是由于在第

19、一次失效時，將地址取反，再在第二次查找?guī)淼?。因?偽命中率偽相聯(lián)命中率2路命中率1路（1失效率2路）（1失效率1路）失效率1路失效率2路。交換內(nèi)容需要增加偽相聯(lián)的額外開銷。平均訪存時間偽相聯(lián)命中時間1路（失效率1路失效率2路）×1失效率2路×失效開銷1路將題設(shè)中的數(shù)據(jù)帶入計算，得到：平均訪存時間2Kb=1+(0.098-0.076)*1+(0.076 *50 ) =4.822平均訪存時間128Kb=1+(0.010-0.007)*1+(0.007 *50 ) =1.353顯然是128KB的偽相聯(lián)Cache要快一些。5.14 假設(shè)采用理想存儲器系統(tǒng)時的基本CPI是1.5，主

20、存延遲是40個時鐘周期；傳輸速率為4字節(jié)/時鐘周期，且Cache中50%的塊是修改過的。每個塊中有32字節(jié)，20%的指令是數(shù)據(jù)傳送指令。并假設(shè)沒有寫緩存，在TLB失效的情況下需要20時鐘周期，TLB不會降低Cache命中率。CPU產(chǎn)生指令地址或Cache失效時產(chǎn)生的地址有0.2%沒有在TLB中找到。（1） 在理想TLB情況下，計算均采用寫回法16KB直接映象統(tǒng)一Cache、16KB兩路組相聯(lián)統(tǒng)一Cache和32KB直接映象統(tǒng)一Cache機器的實際CPI；（2） 在實際TLB情況下，用（1）的結(jié)果，計算均采用寫回法16KB直接映象統(tǒng)一Cache、16KB兩路組相聯(lián)統(tǒng)一Cache和32KB直接映象

21、統(tǒng)一Cache機器的實際CPI；其中假設(shè)16KB直接映象統(tǒng)一Cache、16KB兩路組相聯(lián)統(tǒng)一Cache和32KB直接映象統(tǒng)一Cache的失效率分別為2.9%、2.2%和2.0%；25%的訪存為寫訪問。解： CPI=CPI 執(zhí)行+存儲停頓周期數(shù)/指令數(shù)存儲停頓由下列原因引起：l 從主存中取指令l load和store指令訪問數(shù)據(jù)l 由TLB引起（1）對于理想TLB，TLB失效開銷為0。而對于統(tǒng)一Cache，R指令=R數(shù)據(jù)P指令=主存延遲傳輸一個塊需要使用的時間4032/448（拍）若為讀失效，P數(shù)據(jù)主存延遲傳輸一個塊需要使用的時間4032/448（拍）若為寫失效，且塊是干凈的，P數(shù)據(jù)主存延遲傳輸一個塊需要使用的時間4032/448（拍）若為寫失效，且塊是臟的，P數(shù)據(jù)主存延遲傳輸兩個塊需要使用的時間4064/456（拍）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ù)*其對應(yīng)的百分比f數(shù)據(jù)*P臟數(shù)據(jù)*其對應(yīng)的百分比）20%*（75×4825*（50*48+50*（4816）=50（拍）代入上述公式計算出結(jié)果為：配置失效率CPI16KB 直接統(tǒng)一映象0.029