第一章作業(yè)答案課件

1、第一章第一章1 、用一臺、用一臺40MHz處理機執(zhí)行標準測試處理機執(zhí)行標準測試程序，它含的混合指令數(shù)和相應所需的程序，它含的混合指令數(shù)和相應所需的時鐘周期數(shù)如下：時鐘周期數(shù)如下： 指令類型指令類型 指令數(shù)指令數(shù) 時鐘周期數(shù)時鐘周期數(shù) 整數(shù)運算整數(shù)運算 數(shù)據(jù)傳送數(shù)據(jù)傳送 浮點浮點 控制傳送控制傳送 45 000 45 000 32 000 32 000 15 000 15 000 8 000 8 000 1 1 2 2 2 2 2 2 求有效求有效CPICPI、MIPSMIPS速率和程序的執(zhí)行時間速率和程序的執(zhí)行時間 解：解：CPI=145%+245%+232%+232%+215%+215%+2

2、8%8%=1.55=1.55時鐘周期時鐘周期 M IPS=Rc / （ CP I*106） = (40*106)/ (1.55*106 )=25.81(百萬次百萬次/秒秒) T=IT=IN NCPICPITcTc =10 =105 51.551.55(1/40(1/4010106 6) ) =3.875ms =3.875ms 2、假定要在一個時鐘速率為40MHz處理機上執(zhí)行200000條指令的目標代碼，程序主要由四種指令組成。根據(jù)程序跟蹤實驗結果，已知指令混合比和每種指令所需的指令數(shù)如下： 要求計算：要求計算： （1 1） 在單處理機上用上述跟蹤數(shù)據(jù)運行程序的平均在單處理機上用上述跟蹤數(shù)據(jù)運行

3、程序的平均CPICPI。 （2 2） 根據(jù)（根據(jù)（1 1）所得到的）所得到的CPICPI值，計算相應的值，計算相應的MIPSMIPS速率。速率。 指令類型指令類型CPICPI指令混合比指令混合比 算術和邏輯算術和邏輯 高速緩存命中的加載高速緩存命中的加載/ /存儲存儲 轉移轉移高速緩存缺失的存儲器訪問高速緩存缺失的存儲器訪問1 12 24 48 860%60%18%18%12%12%10%10%答案：答案： Rc=40*106 IN =2* 105條條 (1) CPI=1*0.6+2*0.18+4*0.12+8*0.1=2.24 (2) MIPS= Rc/（CPI*106）=(40*106 )

4、/ (2.24*106 )=17.86(百萬次百萬次/秒秒) 指令Ii頻率Pi霍夫曼編碼霍夫曼擴展編碼普通編碼I10.300000000I20.300101001I30.201010010I40.1011011111011I50.05111011110100I60.021111011101101I70.0211111011100110I80.0111111111011111PiLi 2.382.63.00 減少0.62減少0.40 1、假設在一個采用組相聯(lián)映象方式的、假設在一個采用組相聯(lián)映象方式的Cache中，主中，主 存由存由B0B7共共8塊組成，塊組成，Cache有有2組，每組組，每組2塊

5、，每塊的大小塊，每塊的大小為為16個字節(jié)，采用個字節(jié)，采用LFU塊替換算法。在一個程序執(zhí)行過程塊替換算法。在一個程序執(zhí)行過程中依次訪問這個中依次訪問這個Cache的塊地址流如下的塊地址流如下: 6，2，4，1，4，6，3，0，4，5，7，3 (1) 寫出主存地址的格式，并標出各字段的長度。寫出主存地址的格式，并標出各字段的長度。 (2) 寫出寫出Cache地址的格式，并標出各字段的長度。地址的格式，并標出各字段的長度。 (3) 畫出主存與畫出主存與Cache之間各個塊的映象對應關系。之間各個塊的映象對應關系。 (4) 如果如果Cache的各個塊號為的各個塊號為C0、C1、C2和和C3，列出程，

6、列出程序執(zhí)行過程中序執(zhí)行過程中Cache的塊地址流情況。的塊地址流情況。 (5) 如果采用如果采用FIFO替換算法，計算替換算法，計算Cache的塊命中率。的塊命中率。 (6)采用采用LFU替換算法，計算替換算法，計算Cache的塊命中率。的塊命中率。 (1)主存地址：主存地址： 區(qū)號區(qū)號組號組號塊號塊號塊內(nèi)地址塊內(nèi)地址 6 5 4 3 0 (2) 緩存地址：緩存地址： 組號組號塊號塊號塊內(nèi)地址塊內(nèi)地址 5 4 3 0 區(qū)號區(qū)號Ei塊號塊號Bi緩存塊號緩存塊號bi 3 2 1 0 相關存儲器的格式：相關存儲器的格式：相關存儲器的容量，應與緩存的塊數(shù)相同，相關存儲器的容量，應與緩存的塊數(shù)相同，即

7、即: 組數(shù)組內(nèi)塊數(shù)組數(shù)組內(nèi)塊數(shù)=22 = 22=4個存儲單元。個存儲單元。 解：解：(3)對應關系：對應關系：主存主存0 1 4 52 3 6 7Cache0 12 3裝入位裝入位時間時間t 1 2 3 4 5 6 7 8 9 10 11 12塊地址流塊地址流 6 2 4 1 4 6 3 0 4 5 7 3666661606657LFU調調進進調調進進調調進進替替換換替替換換替替換換441144144064454命命中中命命中中命中命中4次次754C1C2C0C3222622333333調調進進命命中中命命中中替替換換命中率命中率H=4/12=33.3% 時間時間t 1 2 3 4 5 6 7

8、 8 9 10 11 12塊地址流塊地址流 6 2 4 1 4 6 3 0 4 5 7 3666661313343FIFO調調進進調調進進調調進進替替換換替替換換替替換換441144140430545命命中中命中命中3次次345C1C2C0C3222622222277調調進進命命中中命命中中替替換換替替換換命中率命中率H=3/12=25% 1、若有一靜態(tài)多功能流水線分為、若有一靜態(tài)多功能流水線分為6段，如下圖所示，段，如下圖所示，其中乘法流水線由其中乘法流水線由1、2、3、6段組成，加法流水線由段組成，加法流水線由1、4、5、6段組成。使用流水線時，要等某種功能（如加段組成。使用流水線時，要等

9、某種功能（如加法）操作都處理完畢后才能轉換成另一種功能（如乘法）操作都處理完畢后才能轉換成另一種功能（如乘法）。法）。若要計算：若要計算：AB=（a1+b1）（a2+b2）（a3+b3）問：（問：（1）在上述流水方式下，完成）在上述流水方式下，完成AB需多少時間需多少時間？畫出時空圖并計算此流水線的使用效率和吞吐率。？畫出時空圖并計算此流水線的使用效率和吞吐率。（2）與順序運算方式相比，加速比為多少？）與順序運算方式相比，加速比為多少？123456 2T解: (1)12341234455512312319 S6 1 2 345 4 5完成A*B需要的時間=19 114256195253195T

10、p 1925195253Sp效率為：吞吐率為：（2）加速比為：2、已知某單功能非線性流水線的預約表如下圖，要求：、已知某單功能非線性流水線的預約表如下圖，要求： （1）列出禁止表）列出禁止表F和沖突向量和沖突向量C。 （2）畫出該流水線狀態(tài)圖，確定其最小平均延遲以及此時的）畫出該流水線狀態(tài)圖，確定其最小平均延遲以及此時的調度方案？調度方案？ 當按此流水調度方案共輸入當按此流水調度方案共輸入8個任務時，則其實際吞吐率為個任務時，則其實際吞吐率為多少？多少？ 附圖附圖解：(1)禁止表F=4 沖突向量 C=(1000) (2)最佳調度策略(1，1，1，5) 吞吐率=8/17t 10001100101

11、010011110101111011111=5=5=5=5=5=5=5=5123233132112各種調度方案及其相應的平均延遲： 3、有一個雙輸入端的加、有一個雙輸入端的加-乘雙功能靜態(tài)流水線，由經(jīng)過時間為乘雙功能靜態(tài)流水線，由經(jīng)過時間為t、t、2t、t的的1、2、3、4四個子過程構成。加按四個子過程構成。加按1 2 4連接，乘按連接，乘按1 3 4連接，流水線輸出設有數(shù)據(jù)緩沖器，也可將連接，流水線輸出設有數(shù)據(jù)緩沖器，也可將數(shù)據(jù)直接返回輸入。現(xiàn)要執(zhí)行數(shù)據(jù)直接返回輸入?，F(xiàn)要執(zhí)行 A*（B+C*（D+E*F）+G*H的運算，請調整計算順序，畫出能獲得吞吐率盡量高的流水時空的運算，請調整計算順序，

12、畫出能獲得吞吐率盡量高的流水時空圖，標出流水線入、出端數(shù)據(jù)的變化情況，求出完成全部運算的圖，標出流水線入、出端數(shù)據(jù)的變化情況，求出完成全部運算的時間及此期間整個流水線吞吐率，效率，加速比？如對流水線瓶時間及此期間整個流水線吞吐率，效率，加速比？如對流水線瓶頸子過程再細分，最少只需多少時間可完成全部運算？若子過程頸子過程再細分，最少只需多少時間可完成全部運算？若子過程3不能再細分，只能用并聯(lián)方法改進，問流水線的效率為多少？不能再細分，只能用并聯(lián)方法改進，問流水線的效率為多少？ 解：根據(jù)題意，對算法經(jīng)調整后，能使流水吞吐率盡量高的流水時空圖如圖所示。圖中已標出了流水線入、出端的數(shù)據(jù)變化情況。S12

13、3412121233 31234564545 6 64567 87 87 8999輸入輸出ACEFABGHACDACEFABACDACEFGHACEF+GHACD+ABACEFABGHACDACEFACD+ABACEF+GHACEF+GH+ACD+AB21t S1231321 2132435 64 5 67 87 87 8999根據(jù)上圖的流水時空圖，可以看出，完成全部運算的時間為21t。28114213346ttt如果現(xiàn)在將瓶頸子過程3細分成兩個子過程，則時空圖如下圖所示。 41324 5 61324 5 616t tt73219Tp711213346SptttS1231321 2131335

14、 54 5 67 87 87 899942424 6 61324 5 616t 由上圖可見，完成全部運算最少需要16t的時間即可?，F(xiàn)在若子過程3不能再細分了，只能用2個子過程3通過并聯(lián)來改進，則其時空圖如下圖所示。 完成全部運算時的流水線效率8033165924ttt4、超級標量機和超級流水線機都能開發(fā)指令級的并、超級標量機和超級流水線機都能開發(fā)指令級的并行性，現(xiàn)假定這兩種機器的流水線都為行性，現(xiàn)假定這兩種機器的流水線都為4段，每段均段，每段均需需1個時鐘周期。若在超級標量機中，每個時鐘周期個時鐘周期。若在超級標量機中，每個時鐘周期可同時啟動可同時啟動3條指令，而超級流水線機中則是每隔條指令，

15、而超級流水線機中則是每隔1/3時鐘周期啟動一條指令?，F(xiàn)若要執(zhí)行時鐘周期啟動一條指令。現(xiàn)若要執(zhí)行6條指令的代碼條指令的代碼序列，問在兩種機器上各需用多少個時鐘周期方可執(zhí)序列，問在兩種機器上各需用多少個時鐘周期方可執(zhí)行完畢？行完畢？解：超級標量機需5個時鐘周期，超級流水線機需5.67個時鐘周期。 5、 在在CRAY-1機上，機上，V是向量寄存器，設向量長度均為是向量寄存器，設向量長度均為32。S是是標量寄存器，所用浮點功能執(zhí)行部件的執(zhí)行時間分別為：加法標量寄存器，所用浮點功能執(zhí)行部件的執(zhí)行時間分別為：加法需需6拍，相乘需拍，相乘需7拍，從存儲器讀存數(shù)需拍，從存儲器讀存數(shù)需6拍，求倒數(shù)近似值及除拍，

16、求倒數(shù)近似值及除法需法需14拍，寫入寄存器及啟動功能部件（包括存儲器）各需拍，寫入寄存器及啟動功能部件（包括存儲器）各需1拍。拍。問下列各指令組中的哪些指令可以鏈接？哪些指令不可鏈接？問下列各指令組中的哪些指令可以鏈接？哪些指令不可鏈接？哪些指令可以并行執(zhí)行？試說明其原因并分別計算出各指令組哪些指令可以并行執(zhí)行？試說明其原因并分別計算出各指令組全部完成所需的拍數(shù)。全部完成所需的拍數(shù)。（1）V0存儲器存儲器 （2）V2V0+V1 V1V2+V3 V3存儲器存儲器 V4V5*V6 V4V2*V3（3）V0存儲器存儲器 （4） V0存儲器存儲器 V3V1+V2 V11/V0 V4V0*V3 V3V1

17、+V2 V6V4+V5 V5V3*V4（5）V0存儲器存儲器 （6） V3存儲器存儲器 V1V2+V3 V2V0+V1 V4V5*V6 s0s2+s3 s0s1+s2 V3V1*V4（7）V3存儲器存儲器 （8） V0存儲器存儲器 V2V0+V1 V2V0+V1 V4V2*V3 V3V1+V2 存儲器存儲器V4 V5V3*V4 解：(1)三條指令可全并行執(zhí)行,需(1+7+1)+(32-1)=40(拍)(2)前兩條并行,和第三條鏈接，需(1+7+1)+(1+6+1)+(32-1)=48拍(3)前兩條并行和第三條鏈接,而第四條指令與第三條指令串行（因第二條和第四條功能部件沖突），需 (1+6+1)

18、+(1+7+1)+(32-1)+(1+6+1) +(32-1) =87拍(4)全部鏈接 (1+6+1)+(1+14+1)+(1+6+1)+(1+7+1)+(32-1)=72拍(5)全并行執(zhí)行，需(1+7+1)+(32-1)=40(拍)(6)前三條指令并行，與第四條指令串行（V1源操作數(shù)沖突），需(1+6+1)+(32-1)+(1+7+1)+(32-1)=79拍(7)前兩條指令并行，與第三條鏈接，再與第四條串行（因第一條和第四條沖突），需(1+6+1)+(1+7+1)+(32-1)+(1+6+1)+(32-1)=87拍(8)前兩條指令鏈接，與第三條串行（V1源操作數(shù)沖突），與第四條鏈接，需(1+

19、6+1)+(1+6+1)+(32-1)+(1+6+1)+(1+7+1)+(32-1) =95拍 1、若有一靜態(tài)多功能流水線分為、若有一靜態(tài)多功能流水線分為6段，如下圖所示，段，如下圖所示，其中乘法流水線由其中乘法流水線由1、2、3、6段組成，加法流水線由段組成，加法流水線由1、4、5、6段組成。使用流水線時，要等某種功能（如加段組成。使用流水線時，要等某種功能（如加法）操作都處理完畢后才能轉換成另一種功能（如乘法）操作都處理完畢后才能轉換成另一種功能（如乘法）。法）。若要計算：若要計算：AB=（a1+b1）（a2+b2）（a3+b3）問：（問：（1）在上述流水方式下，完成）在上述流水方式下，完

20、成AB需多少時間需多少時間？畫出時空圖并計算此流水線的使用效率和吞吐率。？畫出時空圖并計算此流水線的使用效率和吞吐率。（2）與順序運算方式相比，加速比為多少？）與順序運算方式相比，加速比為多少？123456 2T解: (1)12341234455512312319 S6 1 2 345 4 5完成A*B需要的時間=19 114256195253195Tp 1925195253Sp效率為：吞吐率為：（2）加速比為：2、已知某單功能非線性流水線的預約表如下圖，要求：、已知某單功能非線性流水線的預約表如下圖，要求： （1）列出禁止表）列出禁止表F和沖突向量和沖突向量C。 （2）畫出該流水線狀態(tài)圖，確

21、定其最小平均延遲以及此時的）畫出該流水線狀態(tài)圖，確定其最小平均延遲以及此時的調度方案？調度方案？ 當按此流水調度方案共輸入當按此流水調度方案共輸入8個任務時，則其實際吞吐率為個任務時，則其實際吞吐率為多少？多少？ 附圖附圖解：(1)禁止表F=4 沖突向量 C=(1000) (2)最佳調度策略(1，1，1，5) 吞吐率=8/17t 10001100101010011110101111011111=5=5=5=5=5=5=5=5123233132112各種調度方案及其相應的平均延遲： 3、有一個雙輸入端的加、有一個雙輸入端的加-乘雙功能靜態(tài)流水線，由經(jīng)過時間為乘雙功能靜態(tài)流水線，由經(jīng)過時間為t、t

22、、2t、t的的1、2、3、4四個子過程構成。加按四個子過程構成。加按1 2 4連接，乘按連接，乘按1 3 4連接，流水線輸出設有數(shù)據(jù)緩沖器，也可將連接，流水線輸出設有數(shù)據(jù)緩沖器，也可將數(shù)據(jù)直接返回輸入。現(xiàn)要執(zhí)行數(shù)據(jù)直接返回輸入?，F(xiàn)要執(zhí)行 A*（B+C*（D+E*F）+G*H的運算，請調整計算順序，畫出能獲得吞吐率盡量高的流水時空的運算，請調整計算順序，畫出能獲得吞吐率盡量高的流水時空圖，標出流水線入、出端數(shù)據(jù)的變化情況，求出完成全部運算的圖，標出流水線入、出端數(shù)據(jù)的變化情況，求出完成全部運算的時間及此期間整個流水線吞吐率，效率，加速比？如對流水線瓶時間及此期間整個流水線吞吐率，效率，加速比？如

23、對流水線瓶頸子過程再細分，最少只需多少時間可完成全部運算？若子過程頸子過程再細分，最少只需多少時間可完成全部運算？若子過程3不能再細分，只能用并聯(lián)方法改進，問流水線的效率為多少？不能再細分，只能用并聯(lián)方法改進，問流水線的效率為多少？ 解：根據(jù)題意，對算法經(jīng)調整后，能使流水吞吐率盡量高的流水時空圖如圖所示。圖中已標出了流水線入、出端的數(shù)據(jù)變化情況。S123412121233 31234564545 6 64567 87 87 8999輸入輸出ACEFABGHACDACEFABACDACEFGHACEF+GHACD+ABACEFABGHACDACEFACD+ABACEF+GHACEF+GH+ACD

24、+AB21t S1231321 2132435 64 5 67 87 87 8999根據(jù)上圖的流水時空圖，可以看出，完成全部運算的時間為21t。28114213346ttt如果現(xiàn)在將瓶頸子過程3細分成兩個子過程，則時空圖如下圖所示。 41324 5 61324 5 616t tt73219Tp711213346SptttS1231321 2131335 54 5 67 87 87 899942424 6 61324 5 616t 由上圖可見，完成全部運算最少需要16t的時間即可。現(xiàn)在若子過程3不能再細分了，只能用2個子過程3通過并聯(lián)來改進，則其時空圖如下圖所示。 完成全部運算時的流水線效率80

25、33165924ttt4、超級標量機和超級流水線機都能開發(fā)指令級的并、超級標量機和超級流水線機都能開發(fā)指令級的并行性，現(xiàn)假定這兩種機器的流水線都為行性，現(xiàn)假定這兩種機器的流水線都為4段，每段均段，每段均需需1個時鐘周期。若在超級標量機中，每個時鐘周期個時鐘周期。若在超級標量機中，每個時鐘周期可同時啟動可同時啟動3條指令，而超級流水線機中則是每隔條指令，而超級流水線機中則是每隔1/3時鐘周期啟動一條指令。現(xiàn)若要執(zhí)行時鐘周期啟動一條指令?，F(xiàn)若要執(zhí)行6條指令的代碼條指令的代碼序列，問在兩種機器上各需用多少個時鐘周期方可執(zhí)序列，問在兩種機器上各需用多少個時鐘周期方可執(zhí)行完畢？行完畢？解：超級標量機需5個時鐘周期，超級流水線機需5.67個時鐘周期。 5、 在在CRAY-1機上，機上，V是向量寄存器，設向量長度均為是向量寄存器，設向量長度均為32。S是是標量寄存器，所用浮點功能執(zhí)行部件的執(zhí)行時間分別為：加法標量寄存器，所用浮點功能執(zhí)行部件的執(zhí)行時間分別為：加法需需6拍，相乘需拍，相乘需7拍，從存儲器讀存數(shù)需拍，從存儲器讀存數(shù)需6拍，求倒數(shù)近似值及除拍，求倒數(shù)近似值及除法需法需14拍，寫入寄存器及啟動功能部件（包括存儲器）各需拍，寫入寄存器及啟動功能部件（包括存儲器）各需1拍。拍。問下列各指令組中的哪些指令可以鏈接？哪些