cache原理簡(jiǎn)介學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1cache原理原理(yunl)簡(jiǎn)介簡(jiǎn)介第一頁(yè)，共46頁(yè)。2第2頁(yè)/共46頁(yè)第1頁(yè)/共46頁(yè)第二頁(yè)，共46頁(yè)。3CPU安裝容量安裝容量單位成本下降單位成本下降安裝容量上升安裝容量上升Level 1Level 2Level nLevel 3. . .層次下降層次下降速度下降速度下降第3頁(yè)/共46頁(yè)第2頁(yè)/共46頁(yè)第三頁(yè)，共46頁(yè)。4n比磁盤(pán)更低的層次？nCDROM、磁帶、Internet第4頁(yè)/共46頁(yè)第3頁(yè)/共46頁(yè)第四頁(yè)，共46頁(yè)。5n短時(shí)間內(nèi)，只需要看少數(shù)幾本n如果要看某本書(shū)的某一頁(yè)，該書(shū)其它頁(yè)也很有可能在最近要看第5頁(yè)/共46頁(yè)第4頁(yè)/共46頁(yè)第五頁(yè)，共46頁(yè)。6第6頁(yè)/共46頁(yè)第

2、5頁(yè)/共46頁(yè)第六頁(yè)，共46頁(yè)。7nn不同的層次用不同的解決方案第7頁(yè)/共46頁(yè)第6頁(yè)/共46頁(yè)第七頁(yè)，共46頁(yè)。8內(nèi)存內(nèi)存內(nèi)存地址內(nèi)存地址0123456789ABCDEF4單元直接映射單元直接映射cache0123第8頁(yè)/共46頁(yè)第7頁(yè)/共46頁(yè)第八頁(yè)，共46頁(yè)。9ttttttttttttttttt iiiiiiiiii ooootagindexoffset是否是是否是選擇選擇Cache塊塊塊內(nèi)塊內(nèi)需要需要(xyo)的塊的塊偏移偏移第9頁(yè)/共46頁(yè)第8頁(yè)/共46頁(yè)第九頁(yè)，共46頁(yè)。10第10頁(yè)/共46頁(yè)第9頁(yè)/共46頁(yè)第十頁(yè)，共46頁(yè)。11第11頁(yè)/共46頁(yè)第10頁(yè)/共46頁(yè)第十一頁(yè)，共46

3、頁(yè)。12=21424=210 行n需要10bits第12頁(yè)/共46頁(yè)第11頁(yè)/共46頁(yè)第十二頁(yè)，共46頁(yè)。13第13頁(yè)/共46頁(yè)第12頁(yè)/共46頁(yè)第十三頁(yè)，共46頁(yè)。14地址地址(dzh)內(nèi)容內(nèi)容內(nèi)存內(nèi)存0000001000000014000000180000001Cabcd.0000003000000034000000380000003Cefgh0000801000008014000080180000801Cijkl.第14頁(yè)/共46頁(yè)第13頁(yè)/共46頁(yè)第十四頁(yè)，共46頁(yè)。15000000000000000000 0000000001 0100000000000000000000 00000

4、00001 1100000000000000000000 0000000011 0100000000000000000010 0000000001 0100 Tag Index Offset第15頁(yè)/共46頁(yè)第14頁(yè)/共46頁(yè)第十五頁(yè)，共46頁(yè)。16第16頁(yè)/共46頁(yè)第15頁(yè)/共46頁(yè)第十六頁(yè)，共46頁(yè)。17.ValidTag0 x0-30 x4-70 x8-b0 xc-f0123456710221023.第17頁(yè)/共46頁(yè)第16頁(yè)/共46頁(yè)第十七頁(yè)，共46頁(yè)。18讀0 x00000014.ValidTag0 x0-30 x4-70 x8-b0 xc-f0123456710221023.Ind

5、exTagIndexOffset000000000010000000001第18頁(yè)/共46頁(yè)第17頁(yè)/共46頁(yè)第十八頁(yè)，共46頁(yè)。19.ValidTag0 x0-30 x4-70 x8-b0 xc-f0123456710221023.10abcdIndexTagIndexOffset000000000第19頁(yè)/共46頁(yè)第18頁(yè)/共46頁(yè)第十九頁(yè)，共46頁(yè)。20從Cache讀數(shù)據(jù)l 000000000000000000 0000000001 0100.ValidTag0 x0-30 x4-70 x8-b0 xc-f0123456710221023.10abcdIndexTagIndexOffse

6、t000000000第20頁(yè)/共46頁(yè)第19頁(yè)/共46頁(yè)第二十頁(yè)，共46頁(yè)。21.ValidTag0 x0-30 x4-70 x8-b0 xc-f0123456710221023.10abcdIndexTagIndexOffset000000000l 000000000000000000 0000000001 110010l 000000000000000000 0000000001 1100l 000000000000000000 0000000001 11001第21頁(yè)/共46頁(yè)第20頁(yè)/共46頁(yè)第二十一頁(yè)，共46頁(yè)。22讀0 x00000034.ValidTag0 x0-30 x4-70

7、 x8-b0 xc-f0123456710221023.10abcdl 000000000000000000 0000000011 0100IndexTagIndexOffset00000000030efgh1第22頁(yè)/共46頁(yè)第21頁(yè)/共46頁(yè)第二十二頁(yè)，共46頁(yè)。23.ValidTag0 x0-30 x4-70 x8-b0 xc-f0123456710221023.10abcd10efghIndexTagIndexOffset0000000010l 000000000000000010 0000000001 010012ijkll 000000000000000010 0000000001

8、 0100第23頁(yè)/共46頁(yè)第22頁(yè)/共46頁(yè)第二十三頁(yè)，共46頁(yè)。24自己(zj)練習(xí)l事件事件(shjin)：Hit, Miss, Miss w. replace 返回值：返回值：a ,b, c, d, e, ., k, ll讀讀0 x00000030 ? 000000000000000000 0000000011 0000l讀讀0 x0000001c ? 000000000000000000 0000000001 1100.ValidTag0 x0-30 x4-70 x8-b0 xc-f01234567.12ijkl10efghIndex000000第24頁(yè)/共46頁(yè)第23頁(yè)/共46頁(yè)第

9、二十四頁(yè)，共46頁(yè)。25第25頁(yè)/共46頁(yè)第24頁(yè)/共46頁(yè)第二十五頁(yè)，共46頁(yè)。26Average Access Time = Hit Time Miss Penalty Miss Rate不是(b shi)Miss Time第26頁(yè)/共46頁(yè)第25頁(yè)/共46頁(yè)第二十六頁(yè)，共46頁(yè)。27n第27頁(yè)/共46頁(yè)第26頁(yè)/共46頁(yè)第二十七頁(yè)，共46頁(yè)。28第28頁(yè)/共46頁(yè)第27頁(yè)/共46頁(yè)第二十八頁(yè)，共46頁(yè)。29nCache第29頁(yè)/共46頁(yè)第28頁(yè)/共46頁(yè)第二十九頁(yè)，共46頁(yè)。30第30頁(yè)/共46頁(yè)第29頁(yè)/共46頁(yè)第三十頁(yè)，共46頁(yè)。31MissPenaltyBlock SizeMiss

10、 Penalty 和 Miss Rate增加導(dǎo)致AverageAccessTimeBlock Size空間局部特性塊太少：影響時(shí)間局部特性發(fā)揮作用MissRateBlock Size后面假設(shè)塊大小已經(jīng)(y jing)確定第31頁(yè)/共46頁(yè)第30頁(yè)/共46頁(yè)第三十一頁(yè)，共46頁(yè)。32第32頁(yè)/共46頁(yè)第31頁(yè)/共46頁(yè)第三十二頁(yè)，共46頁(yè)。33第33頁(yè)/共46頁(yè)第32頁(yè)/共46頁(yè)第三十三頁(yè)，共46頁(yè)。34l 全相關(guān)全相關(guān)Cache例：例：32字節(jié)塊字節(jié)塊l 并行比較并行比較(bjio)所有所有TagOffset: Cache DataB 00431:Tag (27 bits)Valid:B 1B

11、 31: Cache Tag=:第34頁(yè)/共46頁(yè)第33頁(yè)/共46頁(yè)第三十四頁(yè)，共46頁(yè)。35n第35頁(yè)/共46頁(yè)第34頁(yè)/共46頁(yè)第三十五頁(yè)，共46頁(yè)。36第36頁(yè)/共46頁(yè)第35頁(yè)/共46頁(yè)第三十六頁(yè)，共46頁(yè)。37第37頁(yè)/共46頁(yè)第36頁(yè)/共46頁(yè)第三十七頁(yè)，共46頁(yè)。38第38頁(yè)/共46頁(yè)第37頁(yè)/共46頁(yè)第三十八頁(yè)，共46頁(yè)。39第39頁(yè)/共46頁(yè)第38頁(yè)/共46頁(yè)第三十九頁(yè)，共46頁(yè)。40Used）n字面含義更象前一種算法n但一般(ybn)是這種含義n其它替換算法第40頁(yè)/共46頁(yè)第39頁(yè)/共46頁(yè)第四十頁(yè)，共46頁(yè)。41第41頁(yè)/共46頁(yè)第40頁(yè)/共46頁(yè)第四十一頁(yè)，共46頁(yè)。

12、420lru1lruloc 0loc 1set 0set 102lruset 0set 1lruset 0set 1041lru 0: miss, 載入載入(set0, loc 0) 2: miss, 載入載入(set 0, loc 1) 0: hit 1: miss, 載入載入(set 1, loc 0) 4: miss, 載入載入(set 0, loc 1)，替換，替換(t hun)2 0: hit02set 0set 1lru0set 0set 1lrulru2lru2set 0set 101lrulrulru4lru第42頁(yè)/共46頁(yè)第41頁(yè)/共46頁(yè)第四十二頁(yè)，共46頁(yè)。43相關(guān)程度 2-way4-way8-way替換算法LRU Ran LRU Ran LRU Ran16 KB5.20% 5.70% 4.70% 5.30% 4.40% 5.00%64 KB1.90% 2.00% 1.50% 1.70% 1.40% 1.50%256 KB1.15% 1.17% 1.13% 1.13% 1.12% 1.12%l 還有其它優(yōu)化手段還有其它優(yōu)化手段?l 減少未命中附加開(kāi)銷(xiāo)減少未命中附加開(kāi)銷(xiāo)l 更大的內(nèi)存帶寬更大的內(nèi)存帶寬(di kun)l 還有其它方法還有其它方法?第43頁(yè)/共46頁(yè)第42頁(yè)/共46頁(yè)第四十三