計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)習(xí)題課萬繼光PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)習(xí)題課萬繼光計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)習(xí)題課萬繼光v 對(duì)于一臺(tái)400MHz計(jì)算機(jī)執(zhí)行標(biāo)準(zhǔn)測(cè)試程序，程序中指令類型，執(zhí)行數(shù)量和平均時(shí)鐘周期數(shù)如下：v 求該計(jì)算機(jī)的有效CPI、MIPS和程序執(zhí)行時(shí)間。指令類型指令執(zhí)行數(shù)量平均時(shí)鐘周期數(shù)整數(shù)450001數(shù)據(jù)傳送750002浮點(diǎn)80004分支15002ICCPIICCPIii/)(776.11295002150048000275000145000CPIMIPSCPIfMIPS225.22510776.11040010666速率2150048000275000145000解： 程序執(zhí)行時(shí)間=（）400=575ns程序執(zhí)行時(shí)間（CPIIC）/頻率

2、f第1頁/共51頁eeeoeSffTT)1 (eeeSffS)1 (1iiiiiSffS)1 (1第2頁/共51頁1332211321)(1 SfSfSffffS13330203 . 0303 . 0)3 . 03 . 0(1 10ff36.0180653f82.071609.0606.02.02.0102.0203.0303.02.02.0102.0203.0303.0)2.03.03.0(1TTTTTp第3頁/共51頁第4頁/共51頁第5頁/共51頁第6頁/共51頁emrmN第7頁/共51頁類型類型數(shù)符數(shù)符階碼階碼尾數(shù)尾數(shù)總位數(shù)總位數(shù)指數(shù)偏移指數(shù)偏移短實(shí)數(shù)1位8位

3、23位32位127長實(shí)數(shù)1位11位52位64位10230.5的二進(jìn)制表示：0.1=1.0*(10)-1尾數(shù)：(1).0000階碼：-1+1023=0 x3fe 0 x3fe00000000000001的二進(jìn)制表示：1.0=1.0*(10)0尾數(shù)(1).0000階碼：0+1023=0 x3ff 0 x3ff0000000000000第8頁/共51頁序號(hào)結(jié)果寄存器結(jié)果值（16進(jìn)制）1R100000000000000032F03fe00000000000003R200000000000000014F1100000000000000015F23ff00000000000006F23fe00000000

4、000007R100000000000000028無無9F23fd000000000000010R1000000000000000111無無12F23fc000000000000013R1000000000000000014無無第9頁/共51頁12345乘法加法tttt2t第10頁/共51頁如圖，在18個(gè)t時(shí)間中，給出了7個(gè)結(jié)果，所以TP=7/18 t如果不用流水線，一次求積3 t，一次求和5t，則T=(4*5+3*3) t=29 t,因此S=29 t/18 t=1.61E=(4*5+3*3)/5*18=0.322考慮改為動(dòng)態(tài)，怎么計(jì)算第11頁/共51頁 時(shí)間時(shí)間功能段功能段1234567S1

5、S2S3S4S5(1)畫出流水線任務(wù)調(diào)度的狀態(tài)轉(zhuǎn)移圖。(2)分別求出允許不等時(shí)間間隔調(diào)度和等時(shí)間間隔調(diào)度的兩種最優(yōu)調(diào)度策略，以及這兩種調(diào)度策略的流水線最大吞吐率。(3)若連續(xù)輸入10個(gè)任務(wù)，求這兩種調(diào)度策略的流水線實(shí)際吞吐率和加速比。第12頁/共51頁10010110110110011110111155225544第13頁/共51頁調(diào)度策略調(diào)度策略平均延遲時(shí)間平均延遲時(shí)間調(diào)度策略調(diào)度策略平均延遲時(shí)間平均延遲時(shí)間(2,2,5)3t(4,5)4.5t(2,5)3.5t(5)5t(4)4tu由上可知，允許不等時(shí)間間隔調(diào)度的最優(yōu)調(diào)度策略是(2,2,5)，流水線最大吞吐率為： 1/3t。u等時(shí)間間隔的調(diào)

6、度的最優(yōu)調(diào)度策略是(4)，流水線最大吞吐率為：1/4t。第14頁/共51頁第15頁/共51頁第16頁/共51頁第17頁/共51頁12345678910111213141516171819LOOP: LW R1 0(R2) IFIDEXMWBADDI R1 R1 #1IFIDSSEXMWBSW 0(R2) R1IFSSIDSSEXMWBADDI R2 R2 #4SSIFSSIDEXMWBSUB R4 R3 R2SSIFIDSSEXMWBBNZ R4 LOOPIFSSIDSS EXM WBIFSS S S IF第18頁/共51頁123456789101112LOOP: LW R1 0(R2) IF

7、IDEXMWBADDI R1 R1 #1IFIDSEXMWBSW 0(R2) R1IFSIDEXMWBADDI R2 R2 #4SIFIDEXMWBSUB R4 R3 R2IFIDEXMWBBNZ R4 LOOPIFIDEXMWBLW R1 0(R2)IFmissmissIF第19頁/共51頁LOOP:LWR1, 0(R2)ADDIR1, R1, #1SW0(R2), R1ADDIR2, R2, #4SUBR4, R3, R2BNZR4, LOOPLOOP:LWR1, 0(R2)ADDIR2, R2, #4ADDIR1, R1, #1SW0(R2), R1SUBR4, R3, R2BNZR4,

8、 LOOPLOOP:LWR1, 0(R2)ADDIR2, R2, #4ADDIR1, R1, #1SW-4(R2), R1SUBR4, R3, R2BNZR4, LOOPLOOP:LWR1, 0(R2)ADDIR2, R2, #4ADDIR1, R1, #1SUBR4, R3, R2BNZR4, LOOPSW-4(R2), R1第20頁/共51頁Instruction1234567891011lw r1,0(r2)IFIDEXMWBaddi r2,r2,#4IFIDEXMWBaddi r1,r1,#1IFIDEXMWBsub r4,r3,r2IFIDEXMWBbnz r4,loopIFIDEX

9、MWBsw r1,-4(r2)IFIDEXMWBlw r1,0(r2)IFIDEXMWB第21頁/共51頁第22頁/共51頁第23頁/共51頁第24頁/共51頁第25頁/共51頁第26頁/共51頁 表表6.16.1本節(jié)使用的浮點(diǎn)流水線的延遲本節(jié)使用的浮點(diǎn)流水線的延遲產(chǎn)生結(jié)果的指令產(chǎn)生結(jié)果的指令使用結(jié)果的指令使用結(jié)果的指令延遲延遲(cycles)浮點(diǎn)計(jì)算浮點(diǎn)計(jì)算另一個(gè)浮點(diǎn)計(jì)算另一個(gè)浮點(diǎn)計(jì)算3浮點(diǎn)計(jì)算浮點(diǎn)計(jì)算浮點(diǎn)浮點(diǎn)store(S.D)2浮點(diǎn)浮點(diǎn)Load(L.D)浮點(diǎn)計(jì)算浮點(diǎn)計(jì)算1浮點(diǎn)浮點(diǎn)Load(L.D)浮點(diǎn)浮點(diǎn)store(S.D)0整數(shù)運(yùn)算，分支延遲和load需要一個(gè)周期延遲，如果分支的寄存器

10、在前一條指令計(jì)算出，也需要一個(gè)周期延遲，因?yàn)檎麛?shù)計(jì)算在第3個(gè)周期完成，而分支第2個(gè)周期就用到DADDIU R1, R1, #-87(空轉(zhuǎn)空轉(zhuǎn))8BNE R1, R2, Loop9第27頁/共51頁在不進(jìn)行指令調(diào)度的情況下，程序的實(shí)際執(zhí)行情況如在不進(jìn)行指令調(diào)度的情況下，程序的實(shí)際執(zhí)行情況如下：下：指令流出時(shí)鐘指令流出時(shí)鐘Loop：L.D F0, 0(R1)1L.D F4, 0(R2)2(空轉(zhuǎn)空轉(zhuǎn))3MUI.D F0, F0, F44(空轉(zhuǎn)空轉(zhuǎn))5(空轉(zhuǎn)空轉(zhuǎn))6(空轉(zhuǎn)空轉(zhuǎn))7ADD.D F2, F0, F28DADDIU R1, R1, #-8 9DADDIU R2, R2, #-810BNE R

11、1, R3, Loop11(空轉(zhuǎn)空轉(zhuǎn))12計(jì)算原程序周期數(shù)：計(jì)算原程序周期數(shù)：每對(duì)元素所需的時(shí)鐘周期數(shù)每對(duì)元素所需的時(shí)鐘周期數(shù)=12，其中空轉(zhuǎn)數(shù)，其中空轉(zhuǎn)數(shù)=5；第28頁/共51頁新程序周期數(shù)：每對(duì)元素所需的時(shí)鐘周期數(shù)新程序周期數(shù)：每對(duì)元素所需的時(shí)鐘周期數(shù)=16/3=5.3，其中空轉(zhuǎn)數(shù)，其中空轉(zhuǎn)數(shù)=1/3=0.3第29頁/共51頁第30頁/共51頁給定以下的假設(shè)，試計(jì)算直接映象Cache和兩路組相聯(lián)Cache的平均訪問時(shí)間以及CPU的性能。由計(jì)算結(jié)果能得出什么結(jié)論？ (1)理想Cache情況下的CPI為2.0，時(shí)鐘周期為2ns，平均每條指令訪存1.2次； (2)兩者Cache容量均為64KB，

12、塊大小都是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。第31頁/共51頁第32頁/共51頁第33頁/共51頁v 命中時(shí)間偽相聯(lián)命中時(shí)間1路偽命中率偽相聯(lián)1v 因此 偽命中率偽相聯(lián)命中率2路命中率1路（1失效率2路）（1失效率1路）失效率1路失效率2路。v 平均訪存時(shí)間偽相聯(lián)命中時(shí)間1路（失效率1路失效率2路）1失效率2路失效開銷2路v 將題設(shè)中的數(shù)據(jù)帶入計(jì)算，得到：平均訪存時(shí)間2KB=

13、1+(0.098-0.076)*1+(0.076 *50 ) =4.822平均訪存時(shí)間128KB=1+(0.010-0.007)*1+(0.007 *50 ) =1.353顯然是128KB的偽相聯(lián)Cache要快一些。第34頁/共51頁第35頁/共51頁第36頁/共51頁第37頁/共51頁訪問命中訪問類型頻率訪存次數(shù)Y讀95%*75%=71.3%0Y寫95%*25%=23.8%1N讀5%*75%=3.8%2N寫5%*25%=1.3%3一次訪存請(qǐng)求最后真正的平均訪存次數(shù)=(71.3%*0)+(23.8%*1)+(3.8%*2)+(1.3%*3)0.35已用帶寬=0.35109/10 9 =35.0

14、%第38頁/共51頁v（2）寫回法cache訪問命中,有兩種情況：讀命中，不訪問主存；寫命中，采用寫回法，不訪問主存。訪問失效,有一個(gè)塊將被換出，這也有兩種情況：如果被替換的塊沒有修改過，將主存中的塊調(diào)入cache塊中，訪存兩次；如果被替換的塊修改過，則首先將修改的塊寫入主存，需要訪存兩次；然后將主存中的塊調(diào)入cache塊中，需要訪問主存兩次，共四次訪存。 訪問命中塊為臟頻率訪存次數(shù)YN95%*70%=66.5%0YY95%*30%=28.5%0NN5%*70%=3.5%2NY5%*30%=1.5%4所以：一次訪存請(qǐng)求最后真正的平均訪存次數(shù) =66.5*028.5%*0+3.5%*2+1.5%

15、*4=0.13 已用帶寬0.1310 9/10 913%第39頁/共51頁第40頁/共51頁第41頁/共51頁NIC陣列控制器SCSI通道適配器NICGGHHIIDDEEFFAABBCC第42頁/共51頁R1R1R2 R3R4R4R4R4R4R4串聯(lián)系統(tǒng)：串聯(lián)系統(tǒng)：并聯(lián)系統(tǒng)：并聯(lián)系統(tǒng)：第43頁/共51頁習(xí)題習(xí)題9.9（單級(jí)互連網(wǎng)絡(luò)）（單級(jí)互連網(wǎng)絡(luò)）第44頁/共51頁/2n 0 1 2 3 4 5 6 7第45頁/共51頁(2)25個(gè)結(jié)點(diǎn)的混洗交換網(wǎng)的直徑是2n-1 =25-1=9;從5號(hào)處理機(jī)（00101B）發(fā)送數(shù)據(jù)到7號(hào)處理機(jī)（00111B），最短路徑要經(jīng)過6步，包含5步左移和1步求反（因?yàn)?/p>

16、00101BXOR00111B=00010B），經(jīng)過的處理機(jī)編號(hào)為：00101B01010B 10100B 01001B 10010B 10011B 00111B（3）網(wǎng)絡(luò)直徑是5/2=3；結(jié)點(diǎn)度是2n-1 =25-1=9；與2號(hào)處理機(jī)距離最遠(yuǎn)的是13、15、21、23號(hào)處理機(jī)。 225330000(12)(01100 )010008(8)(01000 )1000016(9)(01001 )11000242(28)2(11100 )1110001000mod2001004( (4)( (00100 )010019(18)(10010 )CubeCubeBBBBBBPM IPM IBBBBCub

17、eCubeBBCubeCubeB 001117B 第46頁/共51頁 0 0 0 0 0 4 2 1 1 1 2 2 1 4 2 5 6 3 3 3 4 4 2 1 4 6 3 5 5 5 6 6 3 5 6 7 7 7 7 7 第47頁/共51頁第48頁/共51頁1.當(dāng)有N個(gè)處理器時(shí)，上述代碼執(zhí)行fetch-and-increment操作N次次；2.當(dāng)N-1個(gè)處理器第一次訪問release時(shí)候，有N-1個(gè)cache未命中。3.當(dāng)最后一個(gè)處理器到達(dá)柵欄條件后，release置為“1”，一次一次寫操作；4.此時(shí)有N-1個(gè)release 訪問cache未命中。5.所以，共有 3N-1次總線 傳輸操作。如果有10個(gè)處理器，則共有29次總線傳輸操作，總共需要2900個(gè)時(shí)鐘周期。第49頁/共51頁旋轉(zhuǎn)鎖實(shí)現(xiàn)的柵欄同步性能旋轉(zhuǎn)鎖實(shí)現(xiàn)的柵欄同步性能第i個(gè)處理器通過柵欄產(chǎn)生的事件序列 事件 數(shù)量 對(duì)應(yīng)源代碼 說明LL i Lock(counterlock)； 所有處理器搶鎖SC i Lock(counterlock)； 一個(gè)成功LD 1 count=count+1；