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

1、 微電子學(xué)研究所李樹國1微處理器結(jié)構(gòu)與設(shè)計(jì)微處理器結(jié)構(gòu)與設(shè)計(jì)第第13次課次課2013.05.29 存儲器組織結(jié)構(gòu)存儲器組織結(jié)構(gòu) 微電子學(xué)研究所李樹國2實(shí)例運(yùn)行實(shí)例運(yùn)行SPEC2000的缺失率的缺失率盡管缺失率可以衡量盡管缺失率可以衡量cache的設(shè)計(jì)性能，但最終的衡量是存儲器系統(tǒng)對程序執(zhí)行的設(shè)計(jì)性能，但最終的衡量是存儲器系統(tǒng)對程序執(zhí)行時間的影響時間的影響一個聯(lián)合一個聯(lián)合cache，比，比2個分離的個分離的cache有略微好的命中率。原因是聯(lián)合的有略微好的命中率。原因是聯(lián)合的cache對數(shù)對數(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）對對FastMATH采用聯(lián)合采用聯(lián)合cache與采用分離與采用分離cache的，測試情況：的，測試情況：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的帶寬，會很容易彌補(bǔ)缺失率的落差的帶寬，會很容易彌補(bǔ)缺失率的落差不能把缺失率作為不能

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

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

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

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

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

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

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

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

11、es，請問處理器從不發(fā)生，請問處理器從不發(fā)生cache miss性能是發(fā)生性能是發(fā)生cache miss的性能的多少倍？的性能的多少倍？解：解：設(shè)程序的指令條數(shù)為設(shè)程序的指令條數(shù)為I； 發(fā)生發(fā)生I-cache缺失的時鐘周期數(shù)為：缺失的時鐘周期數(shù)為： Instruction miss cycles=I21002I； 由由P228頁知，頁知，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，請問存儲器所占的時間比例，請問存儲器所占的時間比例是多少？是多少？解：因?yàn)椴还芙猓?/p>

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

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

15、，由于時鐘頻率的提高就變成了個周期，由于時鐘頻率的提高就變成了200個周期。個周期。 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也就是說，在考慮存儲器的情況下，時鐘頻率提高也就是

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

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

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

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

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

21、就是直接映射就是1路組相聯(lián)映射，即每組僅有一個位置可放路組相聯(lián)映射，即每組僅有一個位置可放Block，這時，組數(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個個set2個個set4個個set每組有每組有4路，其中的路，其中的1路路共共2組，其中組，其中1組組

22、微電子學(xué)研究所李樹國24舉例舉例 有有1個個cache，每個，每個cache包含包含4個個Block，每個，每個Block包含一個包含一個word，若該，若該cache采用全相聯(lián)，采用全相聯(lián)，2路組相聯(lián)和直接映射來組織路組相聯(lián)和直接映射來組織cache，請問當(dāng)，請問當(dāng)Blocks訪問序列是訪問序列是0，8，0，6，8，會有多少，會有多少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)空白格表示無數(shù)據(jù)空白格表示無數(shù)據(jù) 微電子學(xué)研究所李樹國26 2路組相聯(lián)路組相聯(lián)發(fā)生發(fā)生4次次Miss，1次次hit藍(lán)色表示添加藍(lán)色表示添加黑色表示老的項(xiàng)黑色表示老的項(xiàng)空白格表示無數(shù)據(jù)空白格表示無數(shù)據(jù)替換規(guī)則：替換規(guī)則：the least recently used block 被替換掉被替換掉 微電子學(xué)研

24、究所李樹國27發(fā)生發(fā)生3次次Miss，2次次hit藍(lán)色表示添加藍(lán)色表示添加黑色表示老的項(xiàng)黑色表示老的項(xiàng)空白格表示無數(shù)據(jù)空白格表示無數(shù)據(jù)全相聯(lián)映射全相聯(lián)映射 下圖顯示的是一個下圖顯示的是一個64KB data Cache ，每個，每個Block擁有擁有16個個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é)研究所李樹國29作業(yè)（二選一）作業(yè)（二選一） 題題1：某個：某個cache，每個，每個cache包含包含8個個Block，每個，每個Block包含一個包含一個word，若該，若該cache分別采用全相聯(lián)分別采用全相聯(lián)，2路組相聯(lián)和直接映射來組織路組相聯(lián)和直接映射來組織cache，請問，請問Blocks訪問序列訪問序列0，8，0，6，8會有多少會有多少miss和和hit產(chǎn)生？產(chǎn)生？題題2：某個：某個cache，每個，每個cache包含包含16個個Block，每個，每個Block包含一個包含一個word，若該，

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

27、來選取那一組或哪一個或哪一個set確定組確定組set后，用來后，用來選取哪一個選取哪一個Block12確定確定Block后，后，在在Block中選哪中選哪一個一個word3 微電子學(xué)研究所李樹國32舉例舉例 增加關(guān)聯(lián)性意味著增加關(guān)聯(lián)性意味著set中中Block的數(shù)目增加，相應(yīng)的的數(shù)目增加，相應(yīng)的就需要更多的比較器來進(jìn)行就需要更多的比較器來進(jìn)行tag的比較。的比較。 例：假定例：假定cache的大小為的大小為4K blocks，一個，一個4-word的的Block，32位的地址，請問在直接映射，位的地址，請問在直接映射，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)槊總€解：因?yàn)槊總€Block有有4個個word，每個，每個word有有4個字節(jié)，個字節(jié)，在在Block中尋址字節(jié)需要中尋址字節(jié)需要4個地址位（因?yàn)閭€地址位（因?yàn)?22224）。也就是說，。也就是說，32位的地址，還剩（位的地址，還剩（324）28位被位被用來作為用來作為tag和和index。 在直接的地址映射下，在直接的地址映射下，Set的個數(shù)與的個數(shù)與Block的個數(shù)相同，的個數(shù)相同，（相當(dāng)于（相當(dāng)于1路組相聯(lián)）。路組相聯(lián)）。 所以所以set的數(shù)目為的數(shù)目為4K。 而而4K個個Blocks，需要地址位，需要地址位12 bit ，

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

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

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

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

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

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

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

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

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

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

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

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

41、ss penalty時間大大地減少，這樣可使時間大大地減少，這樣可使Primary cache容量變小，容量變小，缺失率增加。因?yàn)樾〉娜萘烤蜁幸粋€快的存儲器訪問時間缺失率增加。因?yàn)樾〉娜萘烤蜁幸粋€快的存儲器訪問時間(命中時間）命中時間） 對對secondary cache來說，由于來說，由于Primary cache的存在，的存在，Secondary cache的訪問時間變得不重要。因?yàn)榈脑L問時間變得不重要。因?yàn)閟econdary cache的訪問時間只影響的訪問時間只影響primary cache的的miss penalty，而不直接影，而不直接影響響Primary cache命中時間或

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

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

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

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