微處理器結(jié)構(gòu)與設(shè)計(jì)--第13次課-2013-05-29_400107128

1、 微電子學(xué)研究所李樹(shù)國(guó)1微處理器結(jié)構(gòu)與設(shè)計(jì)微處理器結(jié)構(gòu)與設(shè)計(jì)第第13次課次課2013.05.29 存儲(chǔ)器組織結(jié)構(gòu)存儲(chǔ)器組織結(jié)構(gòu) 微電子學(xué)研究所李樹(shù)國(guó)2實(shí)例運(yùn)行實(shí)例運(yùn)行SPEC2000的缺失率的缺失率盡管缺失率可以衡量盡管缺失率可以衡量cache的設(shè)計(jì)性能，但最終的衡量是存儲(chǔ)器系統(tǒng)對(duì)程序執(zhí)行的設(shè)計(jì)性能，但最終的衡量是存儲(chǔ)器系統(tǒng)對(duì)程序執(zhí)行時(shí)間的影響時(shí)間的影響一個(gè)聯(lián)合一個(gè)聯(lián)合cache，比，比2個(gè)分離的個(gè)分離的cache有略微好的命中率。原因是聯(lián)合的有略微好的命中率。原因是聯(lián)合的cache對(duì)數(shù)對(duì)數(shù)據(jù)項(xiàng)條目和指令項(xiàng)條目不進(jìn)行區(qū)分。盡管如此，許多處理器的設(shè)計(jì)仍然采用分據(jù)項(xiàng)條目和指令項(xiàng)條目不進(jìn)行區(qū)分。盡管

2、如此，許多處理器的設(shè)計(jì)仍然采用分離的指令離的指令cache和數(shù)據(jù)和數(shù)據(jù)cache，以提高，以提高cache的帶寬（的帶寬（bandwidth）對(duì)對(duì)FastMATH采用聯(lián)合采用聯(lián)合cache與采用分離與采用分離cache的，測(cè)試情況：的，測(cè)試情況：Total size: 32 KBSplit cache miss rate: 3.24%Combined cache miss rate: 3.18%分離式分離式cache的缺失率稍微比聯(lián)合的缺失率稍微比聯(lián)合cache的缺失率壞一點(diǎn)的缺失率壞一點(diǎn)分離式分離式cache的帶寬，會(huì)很容易彌補(bǔ)缺失率的落差的帶寬，會(huì)很容易彌補(bǔ)缺失率的落差不能把缺失率作為不能

3、把缺失率作為cache性能評(píng)價(jià)的唯一指標(biāo)性能評(píng)價(jià)的唯一指標(biāo)3.2%=0.4%Frequency111.4Frequency2 微電子學(xué)研究所李樹(shù)國(guó)3不同帶寬下支持不同帶寬下支持cache的存儲(chǔ)器系統(tǒng)性能分析的存儲(chǔ)器系統(tǒng)性能分析 發(fā)送一個(gè)地址需要發(fā)送一個(gè)地址需要1個(gè)存儲(chǔ)器總線訪問(wèn)周期個(gè)存儲(chǔ)器總線訪問(wèn)周期 每次訪問(wèn)每次訪問(wèn)DRAM初始化需要初始化需要15個(gè)存儲(chǔ)器總線訪問(wèn)周期個(gè)存儲(chǔ)器總線訪問(wèn)周期 發(fā)送一個(gè)發(fā)送一個(gè)word需要需要1存儲(chǔ)器總線訪問(wèn)周期存儲(chǔ)器總線訪問(wèn)周期 微電子學(xué)研究所李樹(shù)國(guó)4帶寬為帶寬為1個(gè)個(gè)word 的情況的情況左圖為每個(gè)左圖為每個(gè)block為為4個(gè)個(gè)word，主存儲(chǔ)器的帶寬為，主存

4、儲(chǔ)器的帶寬為1個(gè)個(gè)word一次一次Miss Penalty 時(shí)間為：時(shí)間為： 14154165 個(gè)存儲(chǔ)器總線訪問(wèn)周期個(gè)存儲(chǔ)器總線訪問(wèn)周期發(fā)生缺失時(shí)，每個(gè)周期傳送的字節(jié)數(shù)為：發(fā)生缺失時(shí)，每個(gè)周期傳送的字節(jié)數(shù)為：(44)/65=0.25 字節(jié)字節(jié)/周期周期 微電子學(xué)研究所李樹(shù)國(guó)5帶寬為帶寬為4個(gè)個(gè)word的情況的情況左圖每個(gè)左圖每個(gè)block為為4個(gè)個(gè)word，主存儲(chǔ)器的，主存儲(chǔ)器的帶寬為帶寬為4個(gè)個(gè)word一次一次Miss Penalty 時(shí)間為：時(shí)間為： 115117 個(gè)存儲(chǔ)器總線訪問(wèn)周期個(gè)存儲(chǔ)器總線訪問(wèn)周期發(fā)生缺失時(shí)，每個(gè)周期傳送的字節(jié)數(shù)為：發(fā)生缺失時(shí)，每個(gè)周期傳送的字節(jié)數(shù)為：(44)/17

5、=0.94 字節(jié)字節(jié)/周期周期 微電子學(xué)研究所李樹(shù)國(guó)6 以以Bank方式組織存儲(chǔ)器結(jié)構(gòu)，一次啟動(dòng)連續(xù)讀或?qū)懚鄠€(gè)字方式組織存儲(chǔ)器結(jié)構(gòu)，一次啟動(dòng)連續(xù)讀或?qū)懚鄠€(gè)字左圖左圖4個(gè)個(gè)bank需要一個(gè)地址，允許存儲(chǔ)器連續(xù)地需要一個(gè)地址，允許存儲(chǔ)器連續(xù)地讀出或?qū)懭胱x出或?qū)懭?個(gè)個(gè)bank一次一次Miss Penalty 時(shí)間為：時(shí)間為： 1154120個(gè)存儲(chǔ)器總線訪問(wèn)周期個(gè)存儲(chǔ)器總線訪問(wèn)周期發(fā)生缺失時(shí)，每個(gè)周期傳送的字節(jié)數(shù)為：發(fā)生缺失時(shí)，每個(gè)周期傳送的字節(jié)數(shù)為：(44)/20=0.80 字節(jié)字節(jié)/周期周期這種傳送方式的優(yōu)點(diǎn)：這種傳送方式的優(yōu)點(diǎn)：0.80的傳送率是帶寬為的傳送率是帶寬為1個(gè)個(gè)word的的3倍倍

6、微電子學(xué)研究所李樹(shù)國(guó)7DDR SDRAM特點(diǎn)特點(diǎn)DDR SDRAM (Double data rate synchronous DRAM）提供一個(gè)起始地址，采用提供一個(gè)起始地址，采用burst模式，在模式，在clock控制信號(hào)下，利用時(shí)鐘的上升控制信號(hào)下，利用時(shí)鐘的上升沿和下降沿，每個(gè)沿和下降沿，每個(gè)clock周期傳送周期傳送2個(gè)個(gè)data2個(gè)優(yōu)點(diǎn)個(gè)優(yōu)點(diǎn) （1）采用時(shí)鐘控制，刪除了同步控制邏輯采用時(shí)鐘控制，刪除了同步控制邏輯 （2）Burst 模式，刪除了后續(xù)的地址模式，刪除了后續(xù)的地址 微電子學(xué)研究所李樹(shù)國(guó)8 結(jié)論：盡管增加結(jié)論：盡管增加block的容量可以降低缺失率，的容量可以降低缺失率，

7、但會(huì)導(dǎo)致但會(huì)導(dǎo)致miss penalty（block替換時(shí)間）時(shí)間變替換時(shí)間）時(shí)間變長(zhǎng)，因此增加帶寬長(zhǎng)，因此增加帶寬 可以降低可以降低miss penalty 微電子學(xué)研究所李樹(shù)國(guó)9 Cache性能的評(píng)價(jià)和提高性能的評(píng)價(jià)和提高 提高提高cache性能的性能的2個(gè)技術(shù)個(gè)技術(shù) 降低降低2個(gè)個(gè)block爭(zhēng)奪爭(zhēng)奪cache中的同一個(gè)位置的概率中的同一個(gè)位置的概率 通過(guò)添加一級(jí)通過(guò)添加一級(jí)cache即多級(jí)即多級(jí)cache降低缺失處理時(shí)間降低缺失處理時(shí)間 CPU時(shí)間可分為以下時(shí)間可分為以下2種時(shí)間之和：種時(shí)間之和： CPU執(zhí)行程序的時(shí)間執(zhí)行程序的時(shí)間 CPU等待存儲(chǔ)器操作的時(shí)間等待存儲(chǔ)器操作的時(shí)間CPU

8、時(shí)間（時(shí)間（CPU執(zhí)行程序的周期數(shù)存儲(chǔ)器停頓的周期數(shù)）執(zhí)行程序的周期數(shù)存儲(chǔ)器停頓的周期數(shù)）時(shí)鐘周期時(shí)鐘周期 通常認(rèn)為通常認(rèn)為CPU訪問(wèn)訪問(wèn)cache命中時(shí)間是命中時(shí)間是CPU執(zhí)行程序時(shí)間執(zhí)行程序時(shí)間的一部分的一部分 存儲(chǔ)器停頓的周期數(shù)存儲(chǔ)器停頓的周期數(shù):存儲(chǔ)器停頓的周期數(shù)讀停頓周期數(shù)寫(xiě)停頓周期數(shù)存儲(chǔ)器停頓的周期數(shù)讀停頓周期數(shù)寫(xiě)停頓周期數(shù) 讀停頓的周期數(shù)讀停頓的周期數(shù)(reads/Program)Read miss rate Read miss penalty 寫(xiě)停頓的周期數(shù)（寫(xiě)停頓的周期數(shù)（Writes/Program）Write miss rate Write miss penaltyWri

9、te buffer stalls;由于可增加的由于可增加的write buffer的深度，因此存儲(chǔ)器接收的的深度，因此存儲(chǔ)器接收的writes的速率比程序產(chǎn)生的的速率比程序產(chǎn)生的writes的次數(shù)要快，因此的次數(shù)要快，因此write buffer stalls的時(shí)間占的比例很少的時(shí)間占的比例很少，因此，此部分可忽略。，因此，此部分可忽略。 這樣，在這樣，在Write-through模式中，模式中，read和和write miss penalty時(shí)間是時(shí)間是相同的，都是從主存儲(chǔ)器中取相同的，都是從主存儲(chǔ)器中取block的時(shí)間的時(shí)間 于是存儲(chǔ)器停頓的周期數(shù)于是存儲(chǔ)器停頓的周期數(shù) Memory-st

10、all clock cycles= (Memory access/Program)Miss rateMiss penalty 更進(jìn)一步地寫(xiě)為：更進(jìn)一步地寫(xiě)為： Memory-stall clock cycles=(Instructions/Program)(Misses/Instructions) Miss penalty 微電子學(xué)研究所李樹(shù)國(guó)12例例1： 一個(gè)程序的一個(gè)程序的I-cache的缺失率為的缺失率為2，D-cahce的缺失率為的缺失率為4，假定處理器在沒(méi)有任何存儲(chǔ)，假定處理器在沒(méi)有任何存儲(chǔ)器停頓時(shí)的器停頓時(shí)的CPI為為2，發(fā)生缺失時(shí)處理時(shí)間為，發(fā)生缺失時(shí)處理時(shí)間為100個(gè)個(gè)cycl

11、es，請(qǐng)問(wèn)處理器從不發(fā)生，請(qǐng)問(wèn)處理器從不發(fā)生cache miss性能是發(fā)生性能是發(fā)生cache miss的性能的多少倍？的性能的多少倍？解：解：設(shè)程序的指令條數(shù)為設(shè)程序的指令條數(shù)為I； 發(fā)生發(fā)生I-cache缺失的時(shí)鐘周期數(shù)為：缺失的時(shí)鐘周期數(shù)為： Instruction miss cycles=I21002I； 由由P228頁(yè)知，頁(yè)知，SPECINT2000中中,load和和store的出現(xiàn)頻率為的出現(xiàn)頻率為36，因此：，因此：D-cache miss Data miss cyclesI3641001.44I那么，總的那么，總的memory stall cycles1.44I2I3.44I而

12、由于指令本身的而由于指令本身的CPI為為2，那么，那么，CPI with memory stall 23.445.44 又知：又知：CPI without stall=2 5.442.722CPU performanceperfectICPI with stallclockcyclesCPU performance with stallICPI without stallclockcyclesCPI stallCPI withoutstall 例例2： 若上面的例子中程序若上面的例子中程序CPI由由2改為改為1，請(qǐng)問(wèn)存儲(chǔ)器所占的時(shí)間比例，請(qǐng)問(wèn)存儲(chǔ)器所占的時(shí)間比例是多少？是多少？解：因?yàn)椴还芙猓?/p>

13、因?yàn)椴还蹸PI如何變化，其如何變化，其memory stall cycles不會(huì)改變不會(huì)改變 其其 Instruction miss cycles=I21002I； 和和 Data miss cyclesI3641001.44I 總的總的memory stall cycles1.44I2I3.44ICPI由由2改為改為1 這時(shí)這時(shí) CPI with miss=1+3.44=4.44 CPI without miss=1 CPI with miss/CPI without miss= 4.44/1=4.44對(duì)一個(gè)對(duì)一個(gè)CPI=1的處理器，其存儲(chǔ)器占的時(shí)間比例為的處理器，其存儲(chǔ)器占的時(shí)間比例為 3

14、.44/4.44=77%而對(duì)一個(gè)而對(duì)一個(gè)CPI2的處理器，其存儲(chǔ)器占的時(shí)間比例為的處理器，其存儲(chǔ)器占的時(shí)間比例為 3.44/5.44=63 也就是說(shuō)，也就是說(shuō)，CPI越小，對(duì)存儲(chǔ)器的影響就越大越小，對(duì)存儲(chǔ)器的影響就越大 例例3： 在例在例1例子基礎(chǔ)上，時(shí)鐘頻率提高例子基礎(chǔ)上，時(shí)鐘頻率提高1倍，請(qǐng)問(wèn)處理器提高倍，請(qǐng)問(wèn)處理器提高1倍頻率倍頻率后的性能是原來(lái)不提高的多少倍后的性能是原來(lái)不提高的多少倍?（在（在cache miss的情況下）的情況下）解：解： 不論處理器的速度多快，存儲(chǔ)器訪存的絕對(duì)時(shí)間不會(huì)改變：不論處理器的速度多快，存儲(chǔ)器訪存的絕對(duì)時(shí)間不會(huì)改變：這樣原來(lái)訪存的這樣原來(lái)訪存的100個(gè)周期

15、，由于時(shí)鐘頻率的提高就變成了個(gè)周期，由于時(shí)鐘頻率的提高就變成了200個(gè)周期。個(gè)周期。 total_miss_CPI=(2%200)+36%(4%200)=6.88 這樣這樣,頻率提高后頻率提高后CPI with cache miss=2+6.88=8.88 25.441.2318.882performance wtih fastICPI with slowclockclock cyclesclock cyclesperformance with slowICPI with fast clockCPI stallCPI without stall也就是說(shuō)，在考慮存儲(chǔ)器的情況下，時(shí)鐘頻率提高也就是

16、說(shuō)，在考慮存儲(chǔ)器的情況下，時(shí)鐘頻率提高1倍后，其性倍后，其性能僅提高了能僅提高了1.2倍，并不是所想象的倍，并不是所想象的2倍倍上面的例子說(shuō)明，當(dāng)處理器降低上面的例子說(shuō)明，當(dāng)處理器降低CPI（例（例2）或者提高時(shí)）或者提高時(shí)鐘頻率后（例鐘頻率后（例3），存儲(chǔ)器與處理器的關(guān)系是：），存儲(chǔ)器與處理器的關(guān)系是：CPI越小，對(duì)存儲(chǔ)器的影響就越大（例越小，對(duì)存儲(chǔ)器的影響就越大（例2）頻率越高，存儲(chǔ)器的缺失損失就越大（例頻率越高，存儲(chǔ)器的缺失損失就越大（例3）也就是說(shuō)，頻率越高，也就是說(shuō)，頻率越高，CPI越低，在評(píng)價(jià)處理器的性能越低，在評(píng)價(jià)處理器的性能時(shí)，忽視時(shí)，忽視cache的行為，其風(fēng)險(xiǎn)就越大。的行為

17、，其風(fēng)險(xiǎn)就越大。前面的例子和等式說(shuō)明，命中時(shí)間并不是確定前面的例子和等式說(shuō)明，命中時(shí)間并不是確定cache性性能的主要因素，如果命中時(shí)間增加，那么訪存的時(shí)間就能的主要因素，如果命中時(shí)間增加，那么訪存的時(shí)間就要增加，進(jìn)而時(shí)鐘周期就要變長(zhǎng)。最后導(dǎo)致要增加，進(jìn)而時(shí)鐘周期就要變長(zhǎng)。最后導(dǎo)致Cache體積變體積變大，大的大，大的cache勢(shì)必增加訪存的時(shí)間，也就導(dǎo)致了流水線勢(shì)必增加訪存的時(shí)間，也就導(dǎo)致了流水線的級(jí)數(shù)變多（因?yàn)樵L存一個(gè)周期不夠）。在這種情況下的級(jí)數(shù)變多（因?yàn)樵L存一個(gè)周期不夠）。在這種情況下，計(jì)算比較復(fù)雜，在某種程度上，命中時(shí)間的增加，最，計(jì)算比較復(fù)雜，在某種程度上，命中時(shí)間的增加，最終導(dǎo)致

18、處理器的性能下降終導(dǎo)致處理器的性能下降 微電子學(xué)研究所李樹(shù)國(guó)17通過(guò)更加靈活的放置通過(guò)更加靈活的放置Blocks，減少，減少cache缺失缺失 微電子學(xué)研究所李樹(shù)國(guó)18放置放置Blocks方法方法 直接映射直接映射cache， direct-mapped 一個(gè)一個(gè)Block只能精確地放在只能精確地放在cache中的一個(gè)位置中的一個(gè)位置 其映射關(guān)系其映射關(guān)系（Block number）modulo （number of cache blocks）例如：右圖例如：右圖12 modulo 8=4 微電子學(xué)研究所李樹(shù)國(guó)19 全相聯(lián)全相聯(lián)cache； （fully associative cache）

19、一個(gè)一個(gè)Block可以放在可以放在cache中的中的任意位置任意位置 因?yàn)榭梢苑旁谝驗(yàn)榭梢苑旁赾ache中的任意中的任意位置，所以要找到給定的位置，所以要找到給定的Block，必須在所有的，必須在所有的entry（條目）進(jìn)行對(duì)比查找，這就條目）進(jìn)行對(duì)比查找，這就大大地增加了全相聯(lián)映射的大大地增加了全相聯(lián)映射的硬件成本，因此，該方法適硬件成本，因此，該方法適合于較小容量的合于較小容量的cache應(yīng)用應(yīng)用 組相聯(lián)組相聯(lián)cache， set-associative cache 介于直接映射和全相聯(lián)映射的一介于直接映射和全相聯(lián)映射的一種方法種方法 先把先把cache中分成若干組，每組可中分成若干組，每

20、組可有若干個(gè)位置（至少應(yīng)為有若干個(gè)位置（至少應(yīng)為2）可放）可放Block 在組相聯(lián)在組相聯(lián)cache中，如果每組有中，如果每組有n個(gè)位置可放個(gè)位置可放Block，就稱為，就稱為n路組相路組相聯(lián)聯(lián)cache 其映射的公式：其映射的公式：（Block number）modulo （Number of sets in the cache ）例如：右圖組數(shù)為例如：右圖組數(shù)為4，每組有，每組有2個(gè)位置可放個(gè)位置可放Block的的2路組相聯(lián)路組相聯(lián)cache， 所以所以12 modulo 4=0 事實(shí)上，我們可以把每一種放置方法看作是組相聯(lián)的變體事實(shí)上，我們可以把每一種放置方法看作是組相聯(lián)的變體 直接映射

21、就是直接映射就是1路組相聯(lián)映射，即每組僅有一個(gè)位置可放路組相聯(lián)映射，即每組僅有一個(gè)位置可放Block，這時(shí)，組數(shù)（這時(shí)，組數(shù)（set 數(shù)）就為數(shù)）就為cache中的中的Block數(shù)。數(shù)。 全相聯(lián)全相聯(lián)cache，相當(dāng)于，相當(dāng)于cache中僅有中僅有1組，每組有組，每組有m路相聯(lián)映射路相聯(lián)映射 Direct-mapped 直觀容易，效率低；直觀容易，效率低；Set-associative 適中可適中可用；用； Fully-associative 成本較大，可適用小成本較大，可適用小cache1個(gè)個(gè)set2個(gè)個(gè)set4個(gè)個(gè)set每組有每組有4路，其中的路，其中的1路路共共2組，其中組，其中1組組

22、微電子學(xué)研究所李樹(shù)國(guó)24舉例舉例 有有1個(gè)個(gè)cache，每個(gè)，每個(gè)cache包含包含4個(gè)個(gè)Block，每個(gè)，每個(gè)Block包含一個(gè)包含一個(gè)word，若該，若該cache采用全相聯(lián)，采用全相聯(lián)，2路組相聯(lián)和直接映射來(lái)組織路組相聯(lián)和直接映射來(lái)組織cache，請(qǐng)問(wèn)當(dāng)，請(qǐng)問(wèn)當(dāng)Blocks訪問(wèn)序列是訪問(wèn)序列是0，8，0，6，8，會(huì)有多少，會(huì)有多少miss和和hit產(chǎn)生？產(chǎn)生？解：采用直接映射的情形解：采用直接映射的情形 HitOr Miss contents of cache blocks after reference0123missMemory0Address of memory block add

23、ress 0 mod 4=0 8 mod 4=0 0 mod 4=0 6 mod 4=2 8 mod 4=0missMemory8missMemory0missMemory0Memory6missMemory812345發(fā)生發(fā)生5次次Miss藍(lán)色表示添加藍(lán)色表示添加黑色表示老的項(xiàng)黑色表示老的項(xiàng)空白格表示無(wú)數(shù)據(jù)空白格表示無(wú)數(shù)據(jù) 微電子學(xué)研究所李樹(shù)國(guó)26 2路組相聯(lián)路組相聯(lián)發(fā)生發(fā)生4次次Miss，1次次hit藍(lán)色表示添加藍(lán)色表示添加黑色表示老的項(xiàng)黑色表示老的項(xiàng)空白格表示無(wú)數(shù)據(jù)空白格表示無(wú)數(shù)據(jù)替換規(guī)則：替換規(guī)則：the least recently used block 被替換掉被替換掉 微電子學(xué)研

24、究所李樹(shù)國(guó)27發(fā)生發(fā)生3次次Miss，2次次hit藍(lán)色表示添加藍(lán)色表示添加黑色表示老的項(xiàng)黑色表示老的項(xiàng)空白格表示無(wú)數(shù)據(jù)空白格表示無(wú)數(shù)據(jù)全相聯(lián)映射全相聯(lián)映射 下圖顯示的是一個(gè)下圖顯示的是一個(gè)64KB data Cache ，每個(gè)，每個(gè)Block擁有擁有16個(gè)個(gè)word，關(guān)聯(lián)映射從，關(guān)聯(lián)映射從1路（直接映射）到路（直接映射）到8路組路組相聯(lián)映射，運(yùn)行的程序是相聯(lián)映射，運(yùn)行的程序是SPEC2000的的Benchmarks 表中可以看出從表中可以看出從1路到路到2路，其缺失率從路，其缺失率從10.3變變到到8.6，缺失率降低了，缺失率降低了(10.3-8.6)/10.3 15%而繼續(xù)從而繼續(xù)從2路到路

25、到4路再到路再到8路的組相聯(lián)，性能改進(jìn)路的組相聯(lián)，性能改進(jìn)微乎其微。微乎其微。 微電子學(xué)研究所李樹(shù)國(guó)29作業(yè)（二選一）作業(yè)（二選一） 題題1：某個(gè)：某個(gè)cache，每個(gè)，每個(gè)cache包含包含8個(gè)個(gè)Block，每個(gè)，每個(gè)Block包含一個(gè)包含一個(gè)word，若該，若該cache分別采用全相聯(lián)分別采用全相聯(lián)，2路組相聯(lián)和直接映射來(lái)組織路組相聯(lián)和直接映射來(lái)組織cache，請(qǐng)問(wèn)，請(qǐng)問(wèn)Blocks訪問(wèn)序列訪問(wèn)序列0，8，0，6，8會(huì)有多少會(huì)有多少miss和和hit產(chǎn)生？產(chǎn)生？題題2：某個(gè)：某個(gè)cache，每個(gè)，每個(gè)cache包含包含16個(gè)個(gè)Block，每個(gè)，每個(gè)Block包含一個(gè)包含一個(gè)word，若該，

26、若該cache分別采用全相聯(lián)分別采用全相聯(lián)，2路組相聯(lián)和直接映射來(lái)組織路組相聯(lián)和直接映射來(lái)組織cache，請(qǐng)問(wèn)，請(qǐng)問(wèn)Blocks訪問(wèn)序列訪問(wèn)序列0，8，0，6，8會(huì)有多少會(huì)有多少miss和和hit產(chǎn)生？產(chǎn)生？一個(gè)一個(gè)4路組相聯(lián)路組相聯(lián)cache的實(shí)現(xiàn)的實(shí)現(xiàn)(每個(gè)每個(gè)Block有有1個(gè)個(gè)word)請(qǐng)問(wèn)有多少個(gè)組？請(qǐng)問(wèn)有多少個(gè)組？ 微電子學(xué)研究所李樹(shù)國(guó)31在在Cache中定位中定位Block 確定了確定了set或組后，每一個(gè)或組后，每一個(gè)set中，有若干個(gè)中，有若干個(gè)tag（一個(gè)（一個(gè)tag/Block），），set中所有的中所有的tag的比較一定是并行進(jìn)行的的比較一定是并行進(jìn)行的用來(lái)選取那一組用

27、來(lái)選取那一組或哪一個(gè)或哪一個(gè)set確定組確定組set后，用來(lái)后，用來(lái)選取哪一個(gè)選取哪一個(gè)Block12確定確定Block后，后，在在Block中選哪中選哪一個(gè)一個(gè)word3 微電子學(xué)研究所李樹(shù)國(guó)32舉例舉例 增加關(guān)聯(lián)性意味著增加關(guān)聯(lián)性意味著set中中Block的數(shù)目增加，相應(yīng)的的數(shù)目增加，相應(yīng)的就需要更多的比較器來(lái)進(jìn)行就需要更多的比較器來(lái)進(jìn)行tag的比較。的比較。 例：假定例：假定cache的大小為的大小為4K blocks，一個(gè)，一個(gè)4-word的的Block，32位的地址，請(qǐng)問(wèn)在直接映射，位的地址，請(qǐng)問(wèn)在直接映射，2路組相路組相聯(lián)，聯(lián)，4路組相聯(lián)和全相聯(lián)情況下，路組相聯(lián)和全相聯(lián)情況下，se

28、t的數(shù)目和的數(shù)目和tag所占所占bit數(shù)為多少？數(shù)為多少？解：因?yàn)槊總€(gè)解：因?yàn)槊總€(gè)Block有有4個(gè)個(gè)word，每個(gè)，每個(gè)word有有4個(gè)字節(jié)，個(gè)字節(jié)，在在Block中尋址字節(jié)需要中尋址字節(jié)需要4個(gè)地址位（因?yàn)閭€(gè)地址位（因?yàn)?22224）。也就是說(shuō)，。也就是說(shuō)，32位的地址，還剩（位的地址，還剩（324）28位被位被用來(lái)作為用來(lái)作為tag和和index。 在直接的地址映射下，在直接的地址映射下，Set的個(gè)數(shù)與的個(gè)數(shù)與Block的個(gè)數(shù)相同，的個(gè)數(shù)相同，（相當(dāng)于（相當(dāng)于1路組相聯(lián)）。路組相聯(lián)）。 所以所以set的數(shù)目為的數(shù)目為4K。 而而4K個(gè)個(gè)Blocks，需要地址位，需要地址位12 bit ，

29、因?yàn)?，因?yàn)閘og2（4210）12。這時(shí)，每個(gè)這時(shí)，每個(gè)tag位長(zhǎng)為位長(zhǎng)為28-12=16 位位bits，總共的，總共的tag的比的比特?cái)?shù)為特?cái)?shù)為164K64K bits在在2路組相聯(lián)下，即每路組相聯(lián)下，即每2個(gè)個(gè)Blocks組成一個(gè)組成一個(gè)set，因此，因此Set的的數(shù)目為數(shù)目為4K/2=2K個(gè)。識(shí)別個(gè)。識(shí)別2K個(gè)個(gè)sets地址位長(zhǎng)就為地址位長(zhǎng)就為 log2（2210）11bits.這時(shí)，這時(shí)，tag的位長(zhǎng)為的位長(zhǎng)為28-11=17 bits，總，總的的tag的比特?cái)?shù)為的比特?cái)?shù)為1722K68Kbits在在4路組相聯(lián)下，即每路組相聯(lián)下，即每4個(gè)個(gè)Blocks組成一個(gè)組成一個(gè)set，因此，因此

30、Set的數(shù)目為的數(shù)目為4K/4=1K個(gè)。識(shí)別個(gè)。識(shí)別1K個(gè)個(gè)sets地址位長(zhǎng)就為地址位長(zhǎng)就為 log2（1210）10bits.這這時(shí)，時(shí)，tag的位長(zhǎng)為的位長(zhǎng)為28-10=18 bits，總的，總的tag的的比特?cái)?shù)為比特?cái)?shù)為1841K72Kbits在全相聯(lián)的情況下，也就是整個(gè)在全相聯(lián)的情況下，也就是整個(gè)cache只有一只有一個(gè)個(gè)set，set有有4K個(gè)個(gè)Blocks，這時(shí)，檢索，這時(shí)，檢索set的地址位為的地址位為0，tag的位長(zhǎng)為的位長(zhǎng)為28bits，整個(gè)的，整個(gè)的tag比特?cái)?shù)為比特?cái)?shù)為284K1112K bits 微電子學(xué)研究所李樹(shù)國(guó)35 上一個(gè)例子說(shuō)明，關(guān)聯(lián)度越高，上一個(gè)例子說(shuō)明，關(guān)聯(lián)

31、度越高，tag所占的所占的存儲(chǔ)空間就越大存儲(chǔ)空間就越大 微電子學(xué)研究所李樹(shù)國(guó)36選擇哪一個(gè)選擇哪一個(gè)Block替換替換 直接映射的直接映射的cache中，由于每一個(gè)位置只有一個(gè)中，由于每一個(gè)位置只有一個(gè)Block，因此，發(fā)生，因此，發(fā)生miss時(shí)，當(dāng)前的時(shí)，當(dāng)前的Block無(wú)條件的無(wú)條件的將被替換掉。將被替換掉。 在組相聯(lián)的在組相聯(lián)的cache中，每個(gè)中，每個(gè)set中有多個(gè)中有多個(gè)Blocks，發(fā)生，發(fā)生Miss時(shí)，需要利用一種替換規(guī)則來(lái)選擇一個(gè)時(shí)，需要利用一種替換規(guī)則來(lái)選擇一個(gè)Block被被替換替換 在全相聯(lián)的在全相聯(lián)的cache中，所有的中，所有的Blocks都是被替換的候都是被替換的候選

32、對(duì)象，更需要替換的規(guī)則。選對(duì)象，更需要替換的規(guī)則。 最常用的替換機(jī)制就是最近最少使用算法最常用的替換機(jī)制就是最近最少使用算法LRU（The Least Recently used ） 在在2路組相聯(lián)的路組相聯(lián)的cache中，通常設(shè)置一個(gè)中，通常設(shè)置一個(gè)bit位，用來(lái)位，用來(lái)指明哪一個(gè)指明哪一個(gè)block被最近引用或訪問(wèn)被最近引用或訪問(wèn) 微電子學(xué)研究所李樹(shù)國(guó)37使用多級(jí)使用多級(jí)cache降低降低Miss penalty Cache與微處理器的與微處理器的IP核做在一個(gè)核做在一個(gè)die上形成處理器。上形成處理器。 由于處理器的時(shí)鐘頻率較快，而訪問(wèn)片外由于處理器的時(shí)鐘頻率較快，而訪問(wèn)片外DRAM的時(shí)

33、間較的時(shí)間較慢，為了消除這種差異，大多數(shù)處理器都支持添加二級(jí)慢，為了消除這種差異，大多數(shù)處理器都支持添加二級(jí)cache。 二級(jí)二級(jí)cache可以做在片內(nèi)，也可以做在片外可以做在片內(nèi)，也可以做在片外 當(dāng)當(dāng)primary cache發(fā)生發(fā)生miss時(shí)，就會(huì)訪問(wèn)時(shí)，就會(huì)訪問(wèn)secondary cache 如果如果secondary cache中包含所期望的數(shù)據(jù)，中包含所期望的數(shù)據(jù)， primary cache 的的Miss penalty就是就是secondary cache的訪問(wèn)時(shí)間的訪問(wèn)時(shí)間 如果所期望的數(shù)據(jù)，既不在如果所期望的數(shù)據(jù)，既不在primary cache，也不在，也不在seconda

34、ry cache，就不得不訪問(wèn)主存儲(chǔ)器（，就不得不訪問(wèn)主存儲(chǔ)器（DRAM） ,因此因此較大的較大的Miss penalty就會(huì)產(chǎn)生。就會(huì)產(chǎn)生。 微電子學(xué)研究所李樹(shù)國(guó)38舉例舉例 假定在所有訪問(wèn)假定在所有訪問(wèn)Primary cache命中時(shí)，基本的命中時(shí)，基本的CPI1，這時(shí)處理器時(shí)鐘頻率為，這時(shí)處理器時(shí)鐘頻率為5GHz。而訪問(wèn)。而訪問(wèn)主存儲(chǔ)器（主存儲(chǔ)器（main memory ）的時(shí)間為）的時(shí)間為100 ns。若。若訪問(wèn)訪問(wèn)Primary cache的每條指令的缺失率為的每條指令的缺失率為2?，F(xiàn)在要添加一個(gè)現(xiàn)在要添加一個(gè)secondary cache，其命中或缺失，其命中或缺失訪問(wèn)時(shí)間是訪問(wèn)時(shí)

35、間是5ns，且容量大到足夠使訪問(wèn)主存（，且容量大到足夠使訪問(wèn)主存（DRAM）的可能性為）的可能性為0.5，請(qǐng)問(wèn)添加前和添加，請(qǐng)問(wèn)添加前和添加后，處理器的性能提高了多少倍？后，處理器的性能提高了多少倍？解：解： clock時(shí)鐘周期為時(shí)鐘周期為1/5=0.2ns 則，訪問(wèn)主存儲(chǔ)器（則，訪問(wèn)主存儲(chǔ)器（DRAM）的）的miss Penalty： 100 ns/ (0.2 ns/clock cycles)=500 clock cycles 處理器未添加處理器未添加secondary cache時(shí)時(shí) 總的總的CPIBase CPIMemory-stall cycles per instruction 12

36、50011添加添加secondary cache后，后， Primary cache的發(fā)生缺失后，可通過(guò)訪的發(fā)生缺失后，可通過(guò)訪問(wèn)問(wèn)secondary cache或主存儲(chǔ)器（或主存儲(chǔ)器（DRAM）得到滿足。）得到滿足。訪問(wèn)訪問(wèn)secondary cache時(shí)，時(shí)，5ns/ (0.2 ns)=25 clock cycles，如果，如果secondary cache找到期望的數(shù)據(jù)，這就是整個(gè)的找到期望的數(shù)據(jù)，這就是整個(gè)的Miss penalty如果還需要訪問(wèn)主存儲(chǔ)器（如果還需要訪問(wèn)主存儲(chǔ)器（DRAM） ，總的總的Miss penalty=secondary cache的訪問(wèn)時(shí)間的訪問(wèn)時(shí)間+主存儲(chǔ)器

37、（主存儲(chǔ)器（DRAM）的訪問(wèn)時(shí)間）的訪問(wèn)時(shí)間因此，添加因此，添加secondary cache后，后， 總的總的CPI1Primary stalls per instruction + Secondary stalls per instruction=1+2%250.55001+0.52.5=4這樣，添加后與添加前的性能之比為這樣，添加后與添加前的性能之比為11/4=2.8 倍倍另一個(gè)解的方法，另一個(gè)解的方法，首先在首先在secondary cache缺失時(shí)，訪問(wèn)主存儲(chǔ)器（缺失時(shí)，訪問(wèn)主存儲(chǔ)器（DRAM）是）是0.5%，于是同時(shí)訪問(wèn)，于是同時(shí)訪問(wèn)secondary cache和主存儲(chǔ)器（和主存

38、儲(chǔ)器（DRAM）的訪問(wèn)時(shí)間是）的訪問(wèn)時(shí)間是 0.5（25500）2.6那么訪問(wèn)那么訪問(wèn)secondary cache命中的時(shí)間，也是命中的時(shí)間，也是primary cache缺失時(shí)間，于是缺失時(shí)間，于是 （20.5）250.4 所以，總的所以，總的CPI=1+0.4+2.6=4這樣，添加后與添加前的性能之比為這樣，添加后與添加前的性能之比為11/4=2.8 倍倍 微電子學(xué)研究所李樹(shù)國(guó)作業(yè)作業(yè)4 41假假 定在所有訪問(wèn)定在所有訪問(wèn)Primary cachePrimary cache命中時(shí)，基本的命中時(shí)，基本的CPICPI1 1，這時(shí)處理器時(shí)鐘頻率為，這時(shí)處理器時(shí)鐘頻率為4GHz4GHz。而。而訪

39、問(wèn)主問(wèn)主存儲(chǔ)器（存儲(chǔ)器（main memory main memory ）的時(shí)間為）的時(shí)間為150 ns150 ns。若訪。若訪問(wèn)問(wèn)Primary cachePrimary cache的每條指令的缺失率為的每條指令的缺失率為1.51.5?，F(xiàn)在要添加一個(gè)現(xiàn)在要添加一個(gè)secondary cachesecondary cache，其命中或缺失，其命中或缺失訪問(wèn)時(shí)間是訪問(wèn)時(shí)間是4 ns4 ns，且容量大到足夠使訪問(wèn)主存（，且容量大到足夠使訪問(wèn)主存（main memorymain memory）的缺失率為）的缺失率為0.40.4，請(qǐng)問(wèn)添加后與，請(qǐng)問(wèn)添加后與添加前相比，處理器的性能提高了多少倍？添加前相

40、比，處理器的性能提高了多少倍？ 微電子學(xué)研究所李樹(shù)國(guó)42多級(jí)多級(jí)cache的設(shè)計(jì)考慮的設(shè)計(jì)考慮 Primary cache和和secondary cache共同存在，改變了單級(jí)共同存在，改變了單級(jí)cache設(shè)計(jì)所追求的目標(biāo)設(shè)計(jì)所追求的目標(biāo) 在一個(gè)在一個(gè)2級(jí)級(jí)cache結(jié)構(gòu)中，結(jié)構(gòu)中， Primary cache 的設(shè)計(jì)目標(biāo)為縮短命中時(shí)間的設(shè)計(jì)目標(biāo)為縮短命中時(shí)間 Secondary cache的設(shè)計(jì)目標(biāo)縮短長(zhǎng)的存儲(chǔ)器訪問(wèn)時(shí)間（訪問(wèn)主存儲(chǔ)器的設(shè)計(jì)目標(biāo)縮短長(zhǎng)的存儲(chǔ)器訪問(wèn)時(shí)間（訪問(wèn)主存儲(chǔ)器（DRAM） ） 由于由于secondary cache的存在，使得的存在，使得Primary cache的的Mi

41、ss penalty時(shí)間大大地減少，這樣可使時(shí)間大大地減少，這樣可使Primary cache容量變小，容量變小，缺失率增加。因?yàn)樾〉娜萘烤蜁?huì)有一個(gè)快的存儲(chǔ)器訪問(wèn)時(shí)間缺失率增加。因?yàn)樾〉娜萘烤蜁?huì)有一個(gè)快的存儲(chǔ)器訪問(wèn)時(shí)間(命中時(shí)間）命中時(shí)間） 對(duì)對(duì)secondary cache來(lái)說(shuō)，由于來(lái)說(shuō)，由于Primary cache的存在，的存在，Secondary cache的訪問(wèn)時(shí)間變得不重要。因?yàn)榈脑L問(wèn)時(shí)間變得不重要。因?yàn)閟econdary cache的訪問(wèn)時(shí)間只影響的訪問(wèn)時(shí)間只影響primary cache的的miss penalty，而不直接影，而不直接影響響Primary cache命中時(shí)間或

42、處理器的時(shí)鐘周期命中時(shí)間或處理器的時(shí)鐘周期 與單級(jí)與單級(jí)cache的優(yōu)化目標(biāo)相比，的優(yōu)化目標(biāo)相比，2級(jí)級(jí)cache設(shè)設(shè)計(jì)中，每個(gè)計(jì)中，每個(gè)cache的側(cè)重點(diǎn)不同的側(cè)重點(diǎn)不同 多級(jí)多級(jí)cache中，中，Primary cache有一個(gè)較小的有一個(gè)較小的Block size，較小的，較小的cache size和較短的和較短的miss penalty 而而secondary cache擁有一個(gè)大的擁有一個(gè)大的Cache容量，大容量，大的的Block及相對(duì)于訪問(wèn)主存儲(chǔ)器（及相對(duì)于訪問(wèn)主存儲(chǔ)器（DRAM）短的）短的訪問(wèn)時(shí)間。訪問(wèn)時(shí)間。隨著隨著item size增加，增加，Quicksort的的cache

43、缺失數(shù)幾乎成正比的增加，缺失數(shù)幾乎成正比的增加，即即(k3 item _size )/item_size而而Radix sort的隨著的隨著item size的增加，的增加， cache的缺失數(shù)急劇地減少的缺失數(shù)急劇地減少，但過(guò)了，但過(guò)了64后。又急劇上升，這表明后。又急劇上升，這表明64前，缺失數(shù)似乎是一個(gè)前，缺失數(shù)似乎是一個(gè)常量，過(guò)了常量，過(guò)了64后，缺失數(shù)又急劇增大似乎非線性的增加。后，缺失數(shù)又急劇增大似乎非線性的增加。結(jié)論：結(jié)論：Radix sort在處理大數(shù)據(jù)量排序時(shí)，考慮到在處理大數(shù)據(jù)量排序時(shí)，考慮到cache缺失數(shù)的缺失數(shù)的非線性的增加，導(dǎo)致處理器的性能，與非線性的增加，導(dǎo)致處理

44、器的性能，與Quick sort相比沒(méi)有明顯相比沒(méi)有明顯的優(yōu)勢(shì)的優(yōu)勢(shì)變化點(diǎn)變化點(diǎn)從排序程序看從排序程序看cache缺失對(duì)應(yīng)用程序的影響缺失對(duì)應(yīng)用程序的影響上圖表明，橫坐標(biāo)的上圖表明，橫坐標(biāo)的item size表示參與排序數(shù)的個(gè)數(shù)表示參與排序數(shù)的個(gè)數(shù)隨著隨著item size的增加，的增加，Quicksort的代碼量幾乎成正比的增加，的代碼量幾乎成正比的增加，即即(k1item _size )/item_sizek1而而Radix sort隨著隨著item size的增加，其代碼量急劇地減少，似乎代的增加，其代碼量急劇地減少，似乎代碼量是一個(gè)常量。代碼量碼量是一個(gè)常量。代碼量/item_size

45、常數(shù)才會(huì)逐漸變小。常數(shù)才會(huì)逐漸變小。結(jié)論：結(jié)論：Radix sort在處理大數(shù)據(jù)量排序時(shí)，從算法上來(lái)講，應(yīng)該在處理大數(shù)據(jù)量排序時(shí)，從算法上來(lái)講，應(yīng)該比比Quick sort有優(yōu)勢(shì)有優(yōu)勢(shì)該圖是從執(zhí)行的時(shí)間上看該圖是從執(zhí)行的時(shí)間上看2個(gè)算法執(zhí)行時(shí)間的不同個(gè)算法執(zhí)行時(shí)間的不同隨著隨著item size的增加，的增加，Quiksort的指令周期數(shù)幾乎成正比的增加，即的指令周期數(shù)幾乎成正比的增加，即(k2 item _size )/item_size而而Radix sort隨著隨著item size的增加，時(shí)鐘周期數(shù)急劇地減少，似乎執(zhí)行時(shí)的增加，時(shí)鐘周期數(shù)急劇地減少，似乎執(zhí)行時(shí)間是一個(gè)常量。即（時(shí)間常量間是一個(gè)常量。即（時(shí)間常量/item_size）才會(huì)逐漸變小。）才會(huì)逐漸變小。結(jié)論：結(jié)論：Radix sort在處理大數(shù)據(jù)量排序時(shí)，從算法上來(lái)講，其執(zhí)行時(shí)間應(yīng)在處理大數(shù)據(jù)量排序時(shí)，從算法上來(lái)講，其執(zhí)行時(shí)間應(yīng)該比該比Quick sort要快，但從圖上來(lái)講，要快，但從圖上來(lái)講，并非所期望的那樣？為什么？并非所期望的那樣？為什么？多級(jí)多級(jí)cache產(chǎn)生的復(fù)雜性產(chǎn)生的復(fù)雜性 global miss rate（全局缺失率）（全局缺失率）