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

1、精品文檔3.12 有一指令流水線如下所示入1234出50ns50ns100ns200ns（1）求連續(xù)輸入 10 條指令，該流水線的實際吞吐率和效率；（2）該流水線的 “瓶頸 ”在哪一段？請采取兩種不同的措施消除此 “瓶頸 ”。對于你所給出的兩種新的流水線，連續(xù)輸入10 條指令時，其實際吞吐率和效率各是多少？解：（1）mT pipelineti( n 1)tmaxi1(5050100200)92002200(ns)n11TPT pipeline220 (ns)mt i4005E TPi1mTP445.45%11（2）瓶頸在 3、 4 段。變成八級流水線（細(xì)分）入23_13_24_1出14_450

2、ns50ns50ns50ns50ns50nsmTpipelinei1ti (n 1) tmax508950850(ns)n11TP(ns )Tpipeline85mti40010ETP i 1TP58.82%m817重復(fù)設(shè)置部件.精品文檔n11TP(ns)Tpipeline85E400 1081058.82%850173.134 段組成，3 段時，一次，然段。如果段4_4484_3374_226104_11593_22468103_1135792123456789104-1時間112345678910850ns3-14-2有一個流水線由12其中每當(dāng)流經(jīng)第3-24-3總要在該段循環(huán)后才能流到第

3、44-4每段經(jīng)過一次所需要的時間都是t ，問：（1）當(dāng)在流水線的輸入端連續(xù)地每t 時間輸入任務(wù)時，該流水線會發(fā)生什么情況？（2）此流水線的最大吞吐率為多少？如果每2 t 輸入一個任務(wù)，連續(xù)處理10 個任務(wù)時的實際吞吐率和效率是多少？（3） 當(dāng)每段時間不變時， 如何提高該流水線的吞吐率？仍連續(xù)處理 10 個任務(wù)時，其吞吐率提高多少？解：（1）會發(fā)生流水線阻塞情況。第 1個任務(wù)S1S2S3S3S4第 2個任S1S2stallS3S3S4務(wù)第 3個任S1stallS2stallS3S3S4務(wù)第 4個任S1stallS2stallS3 S3 S4務(wù)（2）.精品文檔段412345678910311223

4、34455667788991010212345678910時間11234567891023 tTPmax12 tTpipeline23tTpn10Tpipeline23tE TP5t5054.35%492（3）重復(fù)設(shè)置部件t3_1124tt3_2tt段4123456789103_22244668810103_11133557799212345678910112345678910時間14 tTPn10t5T pipeline147 t57t 1.64吞吐率提高倍數(shù)1023t3.14 有一條靜態(tài)多功能流水線由 5 段組成，加法用 1、3、4、5 段，乘法用1、2、5 段，第 3 段的時間為 2t，

5、其余各段的時間均為 t，而且流水線的輸出可以直接返回輸入端或4.( Ai Bi )i 1精品文檔暫存于相應(yīng)的流水寄存器中。現(xiàn)要在該流水線上計算，畫出其時空圖，并計算其吞吐率、加速比和效率。加法2 tt t12345 t t乘法解：首先，應(yīng)選擇適合于流水線工作的算法。對于本題，應(yīng)先計算 A 1 B1、A2B2、A3B3 和 A4B4；再計算 (A1B1) ×(A2B2)和(A 3B3) ×(A4B4)；然后求總的結(jié)果。其次，畫出完成該計算的時空圖， 如圖所示，圖中陰影部分表示該段在工作。段ABCDA×B C×DA× B×C×

6、D5A=A 1B14B=A 2 B23C=A 3 B3D=A 4B421輸0123456789101112131415161718時間A1 A2 A3 A4A CA × B入B1 B2 B3 B4B DC× D由圖可見，它在 18 個 t 時間中，給出了7 個結(jié)果。所以吞吐率為：TP718 t如果不用流水線，由于一次求積需3t，一次求和需5t，則產(chǎn)生上述 7個結(jié)果共需（ 4×5+3×3） t =29 t。所以加速比為：S29t1.6118t該流水線的效率可由陰影區(qū)的面積和5 個段總時空區(qū)的面積的比值求得：4533E5180.3223.15 動態(tài)多功能流水

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

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

9、周期？.精品文檔（3） 假設(shè)該流水線有正常的定向路徑和一個單周期延遲分支，請對該循環(huán)中的指令進(jìn)行調(diào)度，你可以重新組織指令的順序，也可以修改指令的操作數(shù)，但是注意不能增加指令的條數(shù)。請畫出該指令序列執(zhí)行的流水線時空圖，并計算執(zhí)行上述循環(huán)所需要的時鐘周期數(shù)。解：寄存器讀寫可以定向，無其他旁路硬件支持。排空流水線。指令12345678910111213141516171819202122LWIF IDEXMWBDADDIUIFSSIDEXMWBSWIFSSID EXM WBDADDIUIF IDEXMWBDSUBIFSSIDEXMWBBNEZIFSSIDEXMWBLWIFSSIF ID EXM WB

10、第 i 次迭代（ i0.98）開始周期： 1（ i ×17）總的時鐘周期數(shù)：（98×17） 18 1684有正常定向路徑，預(yù)測分支失敗。指令12345678910111131415LWIF IDEXMWBDADDIUIFIDSEXMWBSWIFSIDEXMWBDADDIUIFIDEXMWBDSUBIFIDEXMWBBNEZIFIDEXMWBLWIFmiss miss IFIDEX MWB第 i 次迭代（ i0.98）開始周期： 1（ i ×10）總的時鐘周期數(shù)：（98×10） 11991有正常定向路徑。單周期延遲分支。LOOP:LWR1，0(R2)DAD

11、DIUR2， R2， #4DADDIUR1， R1， #1DSUBR4，R3，R2BNEZR4，LOOPSWR1，-4(R2)第 i 次迭代（ i 0.98）開始周期： 1（ i ×6 ）總的時鐘周期數(shù)：（98× 6） 10 598.精品文檔指令1234567891011LWIFIDEXMWBDADDIUIFIDEXMWBDADDIUIFIDEXMWBDSUBIFIDEXMWBBNEZIFIDEXMWBSWIFIDEXMWBLWIFIDEXMWB3.17 假設(shè)各種分支指令數(shù)占所有指令數(shù)的百分比如下：條件分支20%（其中的 60%是分支成功的）跳轉(zhuǎn)和調(diào)用5%現(xiàn)有一條段數(shù)為 4

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

13、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.33（3）若使用預(yù)測分支失敗策略， 則對于成功的條件分支， 有兩個額外的 stall；對無條件分支，有一個額外的 stall；對不成功的條件分支，其目標(biāo)地址已經(jīng)由 PC 值給出，不必等待，所以無延遲：CPI = 1+20%*(60%*2 + 40%*0) +5%*1 = 1.29 加速比 S=CPI/1 =

14、 1.295.10 假設(shè)對指令 Cache的訪問占全部訪問的 75%；而對數(shù)據(jù) Cache 的訪問占全部訪問的 25%。Cache 的命中時間為 1 個時鐘周期，失效開銷為 50 個時鐘周期，在混合 Cache中一次 load 或 store 操作訪問 Cache 的命中時間都要增加一個時鐘周期， 32KB 的指令 Cache 的失效率為 0.39%，32KB 的數(shù)據(jù) Cache 的失效率為 4.82%，64KB 的混合 Cache的失效率為 1.35%。又假設(shè)采用寫直達(dá)策略，且有一個寫緩沖器，并且忽略寫緩沖器引起的等待。 試問指令 Cache和數(shù)據(jù) Cache 容量均為 32KB 的分離 C

15、ache和容量為 64KB 的混合 Cache相比，哪種 Cache的失效率更低？兩種情況下平均訪存時間各是多少？解：（1）根據(jù)題意，約 75%的訪存為取指令。.=IC（CPI精品文檔因此，分離 Cache 的總體失效率為：（75%× 0.15%）（ 25%× 3.77%）1.055%；容量為 128KB 的混合 Cache的失效率略低一些，只有0.95%。（2）平均訪存時間公式可以分為指令訪問和數(shù)據(jù)訪問兩部分：平均訪存時間指令所占的百分比× （讀命中時間讀失效率×失效開銷） 數(shù)據(jù)所占的百分比× （數(shù)據(jù)命中時間數(shù)據(jù)失效率×失效開銷）所

16、以，兩種結(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)相

17、關(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 直接映象 Cache 的失效率為 1.4， 64KB 兩路組相聯(lián) Cache的失效率為

18、 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ù) * 失效開銷）* 時鐘周期執(zhí)行 * 時鐘周期） +（每條指令的訪存次數(shù) * 失效率 * 失效開銷 * 時鐘周期）CPU time 1-way5.344ICCPU time 2-way5.36ICCPUtime2way相對性能比：5.36/5

19、.344=1.003CPU time 1way直接映象 cache的訪問速度比兩路組相聯(lián) cache要快 1.04 倍，而兩路組相聯(lián)Cache的平均性能比直接映象 cache要高 1.003 倍。因此這里選擇兩路組相聯(lián)。5.12 假設(shè)一臺計算機(jī)具有以下特性：.精品文檔（1）95的訪存在 Cache中命中；（2）塊大小為兩個字，且失效時整個塊被調(diào)入；（3）CPU 發(fā)出訪存請求的速率為109 字 /s；（4）25的訪存為寫訪問；（5）存儲器的最大流量為109 字 /s（包括讀和寫）；（6）主存每次只能讀或?qū)懸粋€字；（7）在任何時候， Cache中有 30的塊被修改過；（8）寫失效時， Cache采

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

21、3.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訪問命中 ,有兩種情況：讀命中，不訪問主存；寫命中，不訪問主存。采用寫回法，只有當(dāng)修改的 cache 塊被換出時，才寫入主存；訪問失效 ,有一個塊將被換出，這也有兩種情況：如果被替換的塊沒有修改過，將主存中的塊調(diào)入cache塊中，訪問主存兩次；如果被替換的塊修改過，則首先將修改的塊寫入主存，需要訪問主存兩次；然后將主存中的塊

22、調(diào)入 cache塊中，需要訪問主存兩次，共四次訪問主存。訪問命中塊為臟頻率訪存次數(shù)YN95%*70%=66.5%0YY95%*30%=28.5%0.精品文檔NN5%*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ù)進(jìn)行交換。這時只需要 1 個額外的周期。假設(shè)失效開銷為 50 個時鐘周期，2KB 直接映象 Cache的失效率為 9

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

24、#215;1交換或不交換內(nèi)容， 偽相聯(lián)的命中率都是由于在第一次失效時， 將地址取反，再在第二次查找?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

25、*50 ) =1.353 顯然是 128KB 的偽相聯(lián) Cache要快一些。5.14 假設(shè)采用理想存儲器系統(tǒng)時的基本 CPI 是 1.5，主存延遲是 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.精品文檔兩路組

26、相聯(lián)統(tǒng)一Cache和 32KB 直接映象統(tǒng)一Cache機(jī)器的實際 CPI；（ 2） 在實際 TLB 情況下，用（ 1）的結(jié)果，計算均采用寫回法 16KB 直接映象統(tǒng)一 Cache、16KB 兩路組相聯(lián)統(tǒng)一 Cache 和 32KB 直接映象統(tǒng)一 Cache機(jī)器的實際 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ù)存儲停頓由下列原因引起：從主存中取指令load 和 store 指令訪問數(shù)據(jù)由 T

27、LB 引起存儲停頓周期數(shù)取指令停頓數(shù)據(jù)訪問停頓 TLB 停頓指令數(shù)指令數(shù)指令數(shù)停頓周期數(shù)存儲訪問失效率失效開銷指令數(shù)指令數(shù)存儲停頓周期數(shù)R 指令 P指令 （ f 數(shù)據(jù) R 數(shù)據(jù) P數(shù)據(jù) ） TLB停頓指令數(shù)指令數(shù)（ 1）對于理想 TLB ，TLB 失效開銷為 0。而對于統(tǒng)一 Cache，R 指令 =R 數(shù)據(jù) P 指令 =主存延遲傳輸一個塊需要使用的時間 40 32/448（拍）若為讀失效， P 數(shù)據(jù) 主存延遲傳輸一個塊需要使用的時間4032/448（拍）若為寫失效，且塊是干凈的，P 數(shù)據(jù) 主存延遲傳輸一個塊需要使用的時間40 32/4 48（拍）若為寫失效，且塊是臟的，P 數(shù)據(jù) 主存延遲傳輸兩個塊需要使用的時間40 64/4 56（拍）CPI=1.5+RP+(RP*20%)+0 Load 或 Store 指令，指令訪存全是讀，而數(shù)據(jù)傳輸指令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ù) *