1、有一指令流水線如下所示出50ns 50ns 100ns 200ns（1）求連續(xù)輸入 10 條指令，該流水線的實際吞吐率和效率；（2）該流水線的“瓶頸”在哪一段？請采取兩種不同的措施消除此“瓶 頸”。對于你所給出的兩種新的流水線，連續(xù)輸入 10 條指令時，其實 際吞吐率和效率各是多少？TPtiTP i 1解：（1）T pipelinemti (n 1) tmaxi1(5050 100 200) 9 2002200(ns)1220 (ns )400 5TP 45.45%4 112）瓶頸在 3、 4 段。變成八級流水線（細分）50ns50ns50ns50ns50ns出4_450nsmT pipeli

2、neti (n 1) tmaxi150 8 9 50850(ns)TP nTT pipelinemtii 1400 10E TP i 1 TP 58.82% m 817重復(fù)設(shè)置部件TP nTpipeline 185(ns 1)374_4E 400 10850 8 1017 58.82%4_34_2104_13_21524681026915912345678910123456789103_124-13-1850ns有一 組成，其 段時，總 次，然后 段。如果1214-23-24-34-4時間個流水線由 4 段 中每當流經(jīng)第 3 要在該段循環(huán)一 才 能 流 到 第 4 每段經(jīng)過一次所需要的時間都是

3、 t ，問：（1）當在流水線的輸入端連續(xù)地每 t 時間輸入任務(wù)時，該流水線會發(fā)生 什么情況？（2）此流水線的最大吞吐率為多少？如果每 2 t 輸入一個任務(wù)，連續(xù)處理 10 個任務(wù)時的實際吞吐率和效率是多少？（3）當每段時間不變時， 如何提高該流水線的吞吐率？仍連續(xù)處理 10 個 任務(wù)時，其吞吐率提高多少？解：（1）會發(fā)生流水線阻塞情況第1個 任務(wù)S1S2S3S3S4第2個 任務(wù)S1S2stallS3S3S4第3個 任務(wù)S1stallS2stallS3S3S4第4個 任務(wù)S1stallS2stallS3S3S42）123456789 1011223344556677889910 10時間1234

4、56789101234567891023 tTPmaxpipeline12t23 tTpE TP 5 t4 5092 54.35%3）重復(fù)設(shè)置部件tttt段4123456789103_22244668810103_11133557799212345678910112345678910時間14 tTP吞吐率提高倍數(shù)57 t有一條靜態(tài)多功能流水線由 5 段組成，加法用 1、3、4、5 段，乘法用 1、 2、5段，第 3段的時間為 2t ，其余各段的時間均為 t ，而且流水線的輸出可 以直接返回輸入端或4(Ai Bi )i1，畫出其時暫存于相應(yīng)的流水寄存器中?，F(xiàn)要在該流水線上計算空圖，并計算其吞吐率

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

6、 t1.61該流水線的效率可由陰影區(qū)的面積和 5 個段總時空區(qū)的面積的比值求得：4 5 3 35 180.322動態(tài)多功能流水線由 6 個功能段組成，如下圖：加法S1S2S3S4S5S6乘法其中， S1、S4、S5、S6組成乘法流水線， S1、S2、S3、S6組成加法流水線， 各個功能段時間均為 50ns，假設(shè)該流水線的輸出結(jié)果可以直接返回輸入端，而5且設(shè)置有足夠的緩沖寄存器，若以最快的方式用該流水計算：xi yizii1（1）畫出時空圖；（2）計算實際的吞吐率、加速比和效率。解：機器一共要做 10次乘法， 4次加法。在 MIPS 流水線上運行如下代碼序列：LOOP： LWR1， 0（ R2）

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

8、假設(shè)采用預(yù)測分支失敗的策略處理分支指令，且所有的存儲 器訪問都命中 Cache，那么執(zhí)行上述循環(huán)需要多少個時鐘周期？（3）假設(shè)該流水線有正常的定向路徑和一個單周期延遲分支，請對該循 環(huán)中的指令進行調(diào)度，你可以重新組織指令的順序，也可以修改指令 的操作數(shù)，但是注意不能增加指令的條數(shù)。請畫出該指令序列執(zhí)行的 流水線時空圖，并計算執(zhí)行上述循環(huán)所需要的時鐘周期數(shù)。解：寄存器讀寫可以定向，無其他旁路硬件支持。排空流水線。指令1234567891011 12 1314 15 16 17 18 19 20 21 22LWIF IDEX MWBDADDIUIFSSID EX M WBSWIF S S IDEX

9、MWBDADDIUIFIDEXM WBDSUBIFSS ID EX MWBBNEZIF S SID EX M WBLWIF S S IF ID EX M WB第i次迭代（ i 0.98 ）開始周期： 1（ i×17）總的時鐘周期數(shù)：（98×17） 18 1684有正常定向路徑，預(yù)測分支失敗。指令12345678910 111 1314 15LWIF IDEXMWBDADDIUIFIDSEXMWBSWIFSIDEXMWBDADDIUIFIDEXMWBDSUBIFIDEXMWBBNEZIFIDEXM WBLWIFmiss miss IFID EXM WB第 i 次迭代（ i 0

10、.98 ）開始周期： 1（ i ×10） 總的時鐘周期數(shù)：（98×10）11991 有正常定向路徑。單周期延遲分支。LOOP: LW R1 ，0（R2）DADDIU R2，R2，#4DADDIU R1，R1，#1DSUB R4 ，R3，R2BNEZ R4 ，LOOPSW R1 ，-4（R2）第 i 次迭代（ i 0.98 ）開始周期： 1（ i ×6 ） 總的時鐘周期數(shù)：（98× 6） 10 598DADDIUIF IDEXMWBDADDIUIFIDEXMWBDSUBIFIDEXMWBBNEZIFIDEXMWBSWIFIDEXMWBLWIFIDEXM W

11、B123 4 5 6 7 8 9 10 11指令LWIF ID EX M WB假設(shè)各種分支指令數(shù)占所有指令數(shù)的百分比如下：條件分支20%（其中的 60%是分支成功的）跳轉(zhuǎn)和調(diào)用5%現(xiàn)有一條段數(shù)為 4 的流水線，無條件分支在第二個時鐘周期結(jié)束時就被解析 出來，而條件分支要到第三個時鐘周期結(jié)束時才能夠被解析出來。 第一個流水段 是完全獨立于指令類型的，即所有類型的指令都必須經(jīng)過第一個流水段的處理。 請問在沒有任何控制相關(guān)的情況下， 該流水線相對于存在上述控制相關(guān)情況下的 加速比是多少？解：沒有控制相關(guān)時流水線的平均 CPI1 存在控制相關(guān)時：由于無條件分支在第二個時鐘周期結(jié)束時就被解析出來， 而條

12、件分支要到第 3 個時鐘周期結(jié)束時才能被解析出來。所以：（1）若使用排空流水線的策略，則對于條件分支，有兩個額外的stall ，對無條件分支，有一個額外的 stall ：CPI = 1+20%*2+5%*1 =加速比 S=CPI/1 =（2） 若使用預(yù)測分支成功策略， 則對于不成功的條件分支， 有兩個額外的 stall ，對無條件分支和成功的條件分支，有一個額外的 stall 1 ：CPI = 1+20%*（60%*1+40%*2） +5%*1 =加速比 S=CPI/1 =（3）若使用預(yù)測分支失敗策略，則對于成功的條件分支，有兩個額外的 stall ；對無條件分支，有一個額外的 stall ；

13、對不成功的條件分支，其目標地 址已經(jīng)由 PC 值給出，不必等待，所以無延遲：CPI = 1+20%*（60%*2 + 40%*0） +5%*1 =加速比 S=CPI/1 =假設(shè)對指令 Cache 的訪問占全部訪問的 75%；而對數(shù)據(jù) Cache 的訪問占全 部訪問的 25%。Cache的命中時間為 1 個時鐘周期，失效開銷為 50 個時鐘周期， 在混合 Cache中一次 load 或 store 操作訪問 Cache的命中時間都要增加一個時 鐘周期，32KB的指令 Cache 的失效率為 %，32KB的數(shù)據(jù) Cache的失效率為 %，64KB 的混合 Cache的失效率為 %。又假設(shè)采用寫直達

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

15、百分比× （數(shù)據(jù)命中時間數(shù)據(jù)失效率×失效開 銷）所以，兩種結(jié)構(gòu)的平均訪存時間分別為：分離 Cache的平均訪存時間 75%×（ 1%×50）25%×（1%×50）（ 75%×）（ 25%×）混合 Cache的平均訪存時間 75%×（1%×50） 25%×（ 11%×50） （ 75%×）（ 25%×）因此，盡管分離 Cache 的實際失效率比混合 Cache的高，但其平均訪存時間 反而較低。分離 Cache提供了兩個端口，消除了結(jié)構(gòu)相關(guān)。給定以下的假設(shè)，試

16、計算直接映象 Cache和兩路組相聯(lián) Cache 的平均訪問 時間以及 CPU的性能。由計算結(jié)果能得出什么結(jié)論？（1） 理想 Cache情況下的 CPI 為，時鐘周期為 2ns，平均每條指令訪存次；（2） 兩者 Cache容量均為 64KB，塊大小都是 32 字節(jié)；（ 3） 組相聯(lián) Cache中的多路選擇器使 CPU的時鐘周期增加了 10；（ 4） 這兩種 Cache的失效開銷都是 80ns；（5）命中時間為 1 個時鐘周期；（ 6） 64KB直接映象 Cache的失效率為， 64KB兩路組相聯(lián) Cache 的失效 率為。解： 平均訪問時間命中時間失效率×失效開銷 平均訪問時間 1-

17、 路=+% *80= 平均訪問時間 2-路=*（1+10%）+% *80= 兩路組相聯(lián)的平均訪問時間比較低CPUtime=（CPU執(zhí)行+存儲等待周期） *時鐘周期CPU time=IC（CPI執(zhí)行+總失效次數(shù) / 指令總數(shù) *失效開銷） * 時鐘周期 =IC（CPI 執(zhí)行*時鐘周期） +（每條指令的訪存次數(shù) *失效率*失效開銷 *時鐘 周期）CPU time 1-way =IC*2+*80） CPU time 2-way =IC*2+*80） 相對性能比：CPUtime2wayCPU time1way直接映象 cache 的訪問速度比兩路組相聯(lián) cache 要快倍，而兩路組相聯(lián) Cache的平

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

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

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

21、訪存次數(shù) = *0%*0+%*2+%*4=已用帶寬× 10 /10 13%在偽相聯(lián)中，假設(shè)在直接映象位置沒有發(fā)現(xiàn)匹配，而在另一個位置才找到 數(shù)據(jù)（偽命中）時，不對這兩個位置的數(shù)據(jù)進行交換。這時只需要 1 個額外的周 期。假設(shè)失效開銷為 50 個時鐘周期， 2KB直接映象 Cache的失效率為 %，2 路組 相聯(lián)的失效率為 %；128KB直接映象 Cache的失效率為 %，2 路組相聯(lián)的失效率為 %。（1） 推導(dǎo)出平均訪存時間的公式。（2） 利用（ 1）中得到的公式，對于 2KBCache和 128KBCach，e 計算偽相 聯(lián)的平均訪存時間。解： 不管作了何種改進，失效開銷相同。不管

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

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

24、址有 %沒有在 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直接映象統(tǒng)一 Cache機器 的實際 CPI；其中假設(shè) 16KB直接映象統(tǒng)一 Cache、16KB兩路組相聯(lián)統(tǒng)一 Cache 和 32KB 直接映象統(tǒng)一 Cache 的失效率分別為 %、%和%；25%的訪存為寫訪問。解： CPI=CPI 執(zhí)行

25、+存儲停頓周期數(shù) / 指令數(shù)存儲停頓由下列原因引起： 從主存中取指令 load 和 store 指令訪問數(shù)據(jù) 由 TLB 引起存儲停頓周期數(shù) 取指令停頓 數(shù)據(jù)訪問停頓 TLB 停頓指令數(shù) 指令數(shù) 指令數(shù)停頓周期數(shù)指令數(shù)存儲訪問指令數(shù)失效率 失效開銷存儲停頓周期數(shù)指令數(shù)R 指令 P指令 （ f 數(shù)據(jù) R 數(shù)據(jù) P數(shù)據(jù) ）TLB停頓指令數(shù)（1）對于理想 TLB，TLB 失效開銷為 0。而對于統(tǒng)一 Cache，R指令=R數(shù)據(jù) P指令=主存延遲傳輸一個塊需要使用的時間 4032/4 48（拍） 若為讀失效， P 數(shù)據(jù)主存延遲傳輸一個塊需要使用的時間 4032/4 48（拍）若為寫失效，且塊是干凈的，P 數(shù)據(jù)主存延遲傳輸一個塊需要使用的時間 4032/4 48 （拍）若為寫失效，且塊是臟的，P 數(shù)據(jù) 主存延遲傳輸兩個塊需要使用的時間 4064/4 56 （拍）CPI=+RP+（RP*20%）+0 指令訪存全是讀，而數(shù)據(jù)傳輸指令 Load 或 Store 指令，f 數(shù)據(jù)*P 數(shù)據(jù)讀百分比 * （f 數(shù)據(jù)*P 數(shù)據(jù)）寫百分比 * （f 數(shù)據(jù)*P 干