《計(jì)算機(jī)組織結(jié)構(gòu)》課后作業(yè)參考 答案-2013.pdf

計(jì)算機(jī)組織結(jié)構(gòu)課后作業(yè)習(xí)題參考答案計(jì)算機(jī)組織結(jié)構(gòu)課后作業(yè)習(xí)題參考答案 第一章第一章 1.6 某臺(tái)主頻為 400MHz 的計(jì)算機(jī)執(zhí)行標(biāo)準(zhǔn)測(cè)試程序，程序中指令類型、執(zhí)行數(shù)量和平均時(shí) 鐘周期數(shù)如下： 指令類型 指令執(zhí)行數(shù)量 平均時(shí)鐘周期數(shù) 整數(shù) 45000 1 數(shù)據(jù)傳送 75000 2 浮點(diǎn) 8000 4 分支 1500 2 求該計(jì)算機(jī)的有效 CPI、MIPS 和程序執(zhí)行時(shí)間。 解： （1）CPI (4500017500028000415002) / 1295001.776 （2）MIPS 速率f/ CPI 400/1.776 225.225MIPS （3）程序執(zhí)行時(shí)間= (4500017500028000415002)400=575s 1.7 將計(jì)算機(jī)系統(tǒng)中某一功能的處理速度加快 10 倍，但該功能的處理時(shí)間僅為整個(gè)系統(tǒng)運(yùn) 行時(shí)間的 40%，則采用此增強(qiáng)功能方法后，能使整個(gè)系統(tǒng)的性能提高多少？ 解解 由題可知： 可改進(jìn)比例 = 40% = 0.4 部件加速比 = 10 根據(jù) Amdahl 定律可知： 5625. 1 10 4 . 0 4 . 01 1 系統(tǒng)加速比 采用此增強(qiáng)功能方法后，能使整個(gè)系統(tǒng)的性能提高到原來的 1.5625 倍。 1.8 計(jì)算機(jī)系統(tǒng)中有三個(gè)部件可以改進(jìn)，這三個(gè)部件的部件加速比為： 部件加速比1=30； 部件加速比2=20； 部件加速比3=10 （1） 如果部件 1 和部件 2 的可改進(jìn)比例均為 30%， 那么當(dāng)部件 3 的可改進(jìn)比例為多少 時(shí)，系統(tǒng)加速比才可以達(dá)到 10？ （2） 如果三個(gè)部件的可改進(jìn)比例分別為 30%、30%和 20%，三個(gè)部件同時(shí)改進(jìn)，那么 系統(tǒng)中不可加速部分的執(zhí)行時(shí)間在總執(zhí)行時(shí)間中占的比例是多少？ 解： （1）在多個(gè)部件可改進(jìn)情況下，Amdahl 定理的擴(kuò)展： i i i n S F F S )1 ( 1 已知 S130，S220，S310，Sn10，F(xiàn)10.3，F(xiàn)20.3，得： ）（）（10/20/0.330/0.30.30.3-1 1 10 33 FF 得 F30.36，即部件 3 的可改進(jìn)比例為 36%。 （2） 設(shè)系統(tǒng)改進(jìn)前的執(zhí)行時(shí)間為 T， 則 3 個(gè)部件改進(jìn)前的執(zhí)行時(shí)間為：（0.3+0.3+0.2） T = 0.8T， 不可改進(jìn)部分的執(zhí)行時(shí)間為 0.2T。 已知 3 個(gè)部件改進(jìn)后的加速比分別為 S130，S220，S310，因此 3 個(gè)部件改進(jìn)后的 執(zhí)行時(shí)間為： T TTT Tn045. 0 10 2 . 0 20 3 . 0 30 3 . 0 改進(jìn)后整個(gè)系統(tǒng)的執(zhí)行時(shí)間為：Tn = 0.045T+0.2T = 0.245T 那么系統(tǒng)中不可改進(jìn)部分的執(zhí)行時(shí)間在總執(zhí)行時(shí)間中占的比例是： 82. 0 245. 0 2 . 0 T T 第三章第三章 3.9 列舉出下面循環(huán)中的所有相關(guān)，包括輸出相關(guān)、反相關(guān)、真相關(guān)。 for (i=2; i100; i=i+1) ai=bi+ai ;/* s1 */ ci+1=ai+di ; /* s2 */ ai1=2*bi ; /* s3 */ bi+1=2*bi ;/* s4 */ 解：展開循環(huán)兩次： ai = bi + ai ; /* s1 */ ci+1 = ai + di ; /* s2 */ ai1 = 2 * bi ; /* s3 */ bi+1 = 2 * bi ; /* s4 */ ai+1 = bi+1 + ai+1 ; /* s1 */ ci+2 = ai+1 + di+1 ; /* s2 */ ai = 2 * bi+1 ; /* s3 */ bi+2 = 2 * bi+1 ; /* s4 */ 第一次循環(huán)引入的相關(guān)： 輸出相關(guān)：無 反相關(guān)：無 真相關(guān)：S1&S2 由于第二次循環(huán)引入的相關(guān)：S4&S4 （真相關(guān)） 、S1&S4（真相關(guān)） 、S3&S4（真相關(guān)） 、 S1&S3 （輸出相關(guān)、反相關(guān)） 、S2&S3 （反相關(guān)） 。 3.12 有一指令流水線如下所示 入 1 2 3 4 出 50ns 50ns 100ns 200ns （1） 求連續(xù)輸入10條指令，該流水線的實(shí)際吞吐率和效率； （2） 該流水線的“瓶頸”在哪一段？請(qǐng)采取兩種不同的措施消除此“瓶頸”。對(duì)于你所給出的 兩種新的流水線，連續(xù)輸入10條指令時(shí)，其實(shí)際吞吐率和效率各是多少？ 解： （1） 2200(ns) 2009200)10050(50 t) 1n(tTmax m 1i ipipeline )(ns 220 1 T n TP 1 pipeline 45.45% 11 5 4 400 TP m t TPE m 1i i （2）瓶頸在3、4段。 變成八級(jí)流水線（細(xì)分） 850(ns) 509850 t1)(ntTmax m 1i ipipeline )(ns 85 1 T n TP 1 pipeline 58.82% 17 10 8 400 TP m ti TPE m 1i 重復(fù)設(shè)置部件 )(ns 85 1 T n TP 1 pipeline 58.82% 17 10 8850 10400 E 1 2 31 32 41 42 43 44 123_13_24_14_4 入出 50ns50ns50ns 50ns 50ns50ns 1 2 3_1 3_2 4_1 4_2 4_3 4_4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 9 9 10 10 8 9 10 8 9 10 850ns850ns 時(shí)間 段 3.14 有一條靜態(tài)多功能流水線由5段組成，加法用1、3、4、5段，乘法用1、2、5段，第 3段的時(shí)間為2t，其余各段的時(shí)間均為t，而且流水線的輸出可以直接返回輸入端或暫 存于相應(yīng)的流水寄存器中。現(xiàn)要在該流水線上計(jì)算 ，畫出其時(shí)空?qǐng)D，并計(jì)算 其吞吐率、加速比和效率。 解：首先，應(yīng)選擇適合于流水線工作的算法。對(duì)于本題，應(yīng)先計(jì)算A1B1、A2B2、A3B3 和A4B4；再計(jì)算(A1B1) (A2B2)和(A3B3) (A4B4)；然后求總的結(jié)果。 其次，畫出完成該計(jì)算的時(shí)空?qǐng)D，如圖所示，圖中陰影部分表示該段在工作。 由圖可見，它在18個(gè)t時(shí)間中，給出了7個(gè)結(jié)果。所以吞吐率為： t TP 81 7 如果不用流水線，由于一次求積需3t，一次求和需5t，則產(chǎn)生上述7個(gè)結(jié)果共需 （45+33）t =29t。所以加速比為： 該流水線的效率可由陰影區(qū)的面積和5個(gè)段總時(shí)空區(qū)的面積的比值求得： 3.15 動(dòng)態(tài)多功能流水線由6個(gè)功能段組成，如下圖： 1 2345 乘法 加法 t t 2ttt )( 4 1 i i i BA S1 S2 S3 S4 S5 乘法 加法 S6 時(shí)間 段 1 2 3 4 5 0 1 2 3 4 5 6 7891011 12131415 16 輸 入 A1 B1 A2 B2 A3 B3 A4 B4 A BCD A B C D AB ABCDABCD A=A1B1 B=A2B2 C=A3B3 D=A4B4 CD 17 18 61. 1 81 92 t t S 223 . 0 185 3354 E 其中，S1、S4、S5、S6組成乘法流水線，S1、S2、S3、S6組成加法流水線，各個(gè)功能段時(shí) 間均為50ns，假設(shè)該流水線的輸出結(jié)果可以直接返回輸入端，而且設(shè)置有足夠的緩沖寄存 器，若以最快的方式用該流水計(jì)算： 5 1i iii zyx （1） 畫出時(shí)空?qǐng)D； （2） 計(jì)算實(shí)際的吞吐率、加速比和效率。 解：機(jī)器一共要做10次乘法，4次加法。 3.17 假設(shè)各種分支指令數(shù)占所有指令數(shù)的百分比如下： 條件分支 20%（其中的60%是分支成功的） 跳轉(zhuǎn)和調(diào)用 5% 現(xiàn)有一條段數(shù)為4的流水線， 無條件分支在第二個(gè)時(shí)鐘周期結(jié)束時(shí)就被解析出來， 而條 件分支要到第三個(gè)時(shí)鐘周期結(jié)束時(shí)才能夠被解析出來。 第一個(gè)流水段是完全獨(dú)立于指令類型 的， 即所有類型的指令都必須經(jīng)過第一個(gè)流水段的處理。 請(qǐng)問在沒有任何控制相關(guān)的情況下， 該流水線相對(duì)于存在上述控制相關(guān)情況下的加速比是多少？ 解：沒有控制相關(guān)時(shí)流水線的平均CPI1 存在控制相關(guān)時(shí)： 由于無條件分支在第二個(gè)時(shí)鐘周期結(jié)束時(shí)就被解析出來， 而條件分支 要到第3個(gè)時(shí)鐘周期結(jié)束時(shí)才能被解析出來。所以： （1）若使用排空流水線的策略，則對(duì)于條件分支，有兩個(gè)額外的stall，對(duì)無條件分支，有 一個(gè)額外的stall： CPI = 1+20%*2+5%*1 = 1.45 加速比S=CPI/1 = 1.45 （2） 若使用預(yù)測(cè)分支成功策略，則對(duì)于不成功的條件分支，有兩個(gè)額外的stall，對(duì)無條件 分支和成功的條件分支，有一個(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ì)無條件分 支，有一個(gè)額外的stall；對(duì)不成功的條件分支，其目標(biāo)地址已經(jīng)由PC 值給出，不必等待， 所以無延遲： CPI = 1+20%*(60%*2 + 40%*0) +5%*1 = 1.29 加速比 S=CPI/1 = 1.29 第五章第五章 5.10 假設(shè)對(duì)指令Cache的訪問占全部訪問的75%； 而對(duì)數(shù)據(jù)Cache的訪問占全部訪問的25%。 Cache的命中時(shí)間為1個(gè)時(shí)鐘周期，失效開銷為50 個(gè)時(shí)鐘周期，在混合Cache中一次load 或store操作訪問Cache的命中時(shí)間都要增加一個(gè)時(shí)鐘周期，32KB的指令Cache的失效率為 0.39%，32KB的數(shù)據(jù)Cache的失效率為4.82%，64KB的混合Cache的失效率為1.35%。又假 設(shè)采用寫直達(dá)策略，且有一個(gè)寫緩沖器，并且忽略寫緩沖器引起的等待。試問指令Cache 和數(shù)據(jù)Cache容量均為32KB的分離Cache和容量為64KB的混合Cache相比，哪種Cache 的失效率更低？?jī)煞N情況下平均訪存時(shí)間各是多少？ 解： （1）根據(jù)題意，約75%的訪存為取指令。因此，分離Cache的總體失效率為： （75%0.39%）（25%4.82%）1.50% 根據(jù)題意，容量為128KB的混合Cache的失效率為1.35%。也就是說，混合Cache的失效率 比分離Cache的低一些。 （2）平均訪存時(shí)間公式可以分為指令訪問和數(shù)據(jù)訪問兩部分： 平均訪存時(shí)間指令所占的百分比 （讀命中時(shí)間讀失效率失效開銷） 數(shù)據(jù)所 占的百分比（數(shù)據(jù)命中時(shí)間數(shù)據(jù)失效率失效開銷） 根據(jù)這個(gè)公式，可求得兩種結(jié)構(gòu)的平均訪存時(shí)間，分別為： 分離Cache的平均訪存時(shí)間： 75%（10.39%50）25%（14.82%50）=1.7488（時(shí)鐘周期） 混合Cache的平均訪存時(shí)間： 75%（11.35%50）25%（111.35%50）=1.9250（時(shí)鐘周期） 因此，盡管分離Cache的實(shí)際失效率比混合Cache的高，但其平均訪存時(shí)間反而較低。分離 Cache提供了兩個(gè)端口，消除了結(jié)構(gòu)相關(guān)。 5.11 給定以下的假設(shè)， 試計(jì)算直接映象Cache和兩路組相聯(lián)Cache的平均訪問時(shí)間以及CPU 的性能。由計(jì)算結(jié)果能得出什么結(jié)論？ （1） 理想Cache情況下的CPI為2.0，時(shí)鐘周期為2ns，平均每條指令訪存1.2次； （2） 兩者Cache容量均為64KB，塊大小都是32字節(jié)； （3） 組相聯(lián)Cache中的多路選擇器使CPU的時(shí)鐘周期增加了10； （4） 這兩種Cache的失效開銷都是80ns； （5） 命中時(shí)間為1個(gè)時(shí)鐘周期； （6） 64KB直接映象Cache的失效率為1.4，64KB兩路組相聯(lián)Cache的失效率為1.0。 解：根據(jù)公式 平均訪問時(shí)間命中時(shí)間失效率失效開銷 可計(jì)算直接映像（即1路）和兩路組相聯(lián)（即2路）Cache的平均訪存時(shí)間。具體如下： 平均訪問時(shí)間1路=12.0+1.4%80=3.12 (ns) 平均訪問時(shí)間2路=2.0(1+10%)+1.0%80=3.0 (ns) 可見，兩路組相聯(lián)的平均訪問時(shí)間比較低。 為評(píng)估CPU的性能，需計(jì)算CPU時(shí)間，其公式為： CPUtime=（CPU執(zhí)行+存儲(chǔ)等待周期） 時(shí)鐘周期 CPU time=IC（CPI執(zhí)行+總失效次數(shù)/指令總數(shù)*失效開銷） 時(shí)鐘周期 =IC（ （CPI執(zhí)行時(shí)鐘周期）+（每條指令的訪存次數(shù)失效率失效開銷時(shí)鐘周期） ） 根據(jù)上述CPU時(shí)間公式，可得： CPU 1路=IC(2.02+1.21.4%80)5.344IC CPU 2路=IC(2.22+1.21.0%80)5.360IC 這兩種結(jié)構(gòu)的CPU相對(duì)性能比為： 2- 1- CPU CPU 路 路 5.36/5.344=1.003 因此，直接映象cache的訪問速度比兩路組相聯(lián)cache要快1.04倍，而兩路組相聯(lián)Cache的 平均性能比直接映象cache要高1.003倍。所以，這里選擇兩路組相聯(lián)。 5.12 假設(shè)一臺(tái)計(jì)算機(jī)具有以下特性： （1） 95的訪存在Cache中命中； （2） 塊大小為兩個(gè)字，且失效時(shí)整個(gè)塊被調(diào)入； （3） CPU發(fā)出訪存請(qǐng)求的速率為109字/s； （4） 25的訪存為寫訪問； （5） 存儲(chǔ)器的最大流量為109字/s（包括讀和寫） ； （6） 主存每次只能讀或?qū)懸粋€(gè)字； （7） 在任何時(shí)候，Cache中有30的塊被修改過； （8） 寫失效時(shí)，Cache采用按寫分配法。 現(xiàn)欲給該計(jì)算機(jī)增添一臺(tái)外設(shè)， 為此首先想知道主存的頻帶已用了多少。 試對(duì)于以下兩 種情況計(jì)算主存頻帶的平均使用比例。 （1） 寫直達(dá)Cache； （2） 寫回法Cache。 解：采用按寫分配 （1）若用寫直達(dá)法，每次CPU改變后的字，都要寫到Cache和主存中。根據(jù)題意，訪存的 情況如圖1所示： 訪存 25%寫 75%讀 5%訪主存 95%訪Cache95%訪Cache5%訪主存 讀2字，寫1字 寫1字 0字 讀2字 根據(jù)上圖的分析可知： A. 寫直達(dá)cache訪問命中，有兩種情況： 讀命中，不訪問主存； 寫命中，更新cache和主存，訪問主存一次。 B. 訪問失效，有兩種情況： 讀失效，將主存中的塊調(diào)入cache中，訪問主存兩次； 寫失效，將要寫的塊調(diào)入cache，訪問主存兩次，再將修改的數(shù)據(jù)寫入cache和主存， 訪問主存一次，共三次。上述分析如下表所示。 訪問命中 訪問類型 頻率 訪存次數(shù) Y 讀 95%*75%=71.3% 0 Y 寫 95%*25%=23.8% 1 N 讀 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.35109/109 =35.0% （2）若用寫回法，每次CPU改變后的字，都要寫到Cache中，但只有在該塊被替換出去的 時(shí)候，才需要將整塊都寫到主存中。根據(jù)題意，訪存的情況如圖2所示： 訪存 25%寫 75%讀 5%訪主存 95%訪Cache 95%訪Cache5%訪主存 30%需 寫回 70%無 需寫回 30%需 寫回 70%無 需寫回 30%需 寫回 70%無 需寫回 30%需 寫回 70%無 需寫回 讀2字 寫2字 讀2字 寫0字 讀/寫 0字 讀/寫0 字 讀/寫0 字 讀/寫0 字 讀2字 寫2字 讀2字 寫0字 根據(jù)上圖的分析可知： A. 寫回法cache訪問命中，有兩種情況： 讀命中，不訪問主存； 寫命中，不訪問主存。采用寫回法，只有當(dāng)修改的cache塊被換出時(shí)，才寫入主存； B. 訪問失效，有一個(gè)塊將被換出，這也有兩種情況： 如果被替換的塊沒有修改過，將主存中的塊調(diào)入cache塊中，訪問主存兩次； 如果被替換的塊修改過，則首先將修改的塊寫入主存，需要訪問主存兩次；然后將 主存中的塊調(diào)入cache塊中，需要訪問主存兩次，共四次訪問主存。 因此，可以生成下表： 訪問命中 塊為臟 頻率 訪存次數(shù) Y N 95%*70%=66.5% 0 Y Y 95%*30%=28.5% 0 N N 5%*70%=3.5% 2 N Y 5%*30%=1.5% 4 其中，讀/寫命中Cache，且塊是非臟（即沒有被修改過）的概率按下列方式計(jì)算得到（參 考圖2） ： 25%95%70% + 75%95%70% = 95%70% 其它情況亦可根據(jù)圖2來得到，詳見上表。 所以有： 一次訪存請(qǐng)求最后真正的平均訪存次數(shù)=66.5*028.5%*0+3.5%*2+1.5%*4=0.13 已用帶寬=0.1310 9/109=13% 5.13 在偽相聯(lián)中，假設(shè)在直接映象位置沒有發(fā)現(xiàn)匹配，而在另一個(gè)位置才找到數(shù)據(jù)（偽命 中）時(shí)，不對(duì)這兩個(gè)位置的數(shù)據(jù)進(jìn)行交換。這時(shí)只需要1個(gè)額外的周期。假設(shè)失效開銷為 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í)間。 解：