計算機組成原理 第17講_Cache

1、Principles of Computer Organization 廣義雙語教學(xué)課程 09/skyclass25/ 青島理工大學(xué) 校級精品課程 http:/ 盛建倫2 第第 7 章章 存儲系統(tǒng)存儲系統(tǒng) (2) Chapter 7 Storage System A CPU cache is a cache used by the central processing unit of a computer to reduce the average time to access memory. The cache is a smaller, faster m

2、emory which stores copies of the data from the most frequently used main memory locations. As long as most memory accesses are cached memory locations, the average latency of memory accesses will be closer to the cache latency than to the latency of main memory. 盛建倫3 Cache-主存層次工作原理主存層次工作原理 Cache 是位于

3、CPU與主存之間主存之間的一個高速小容量高速小容量的存儲器存儲器。 Cache一般采用和CPU相同的半導(dǎo)體工藝半導(dǎo)體工藝制成，在物理位置物理位置 上盡量靠近CPU，而不在主存模塊中，最好在處理器芯片內(nèi)。 其速度速度與CPU的速度相匹配的速度相匹配，即能夠在一個最短的存儲周期內(nèi)完 成一次讀/寫，約比主存速度高比主存速度高數(shù)倍數(shù)十倍以上。 72 高速緩沖存儲器高速緩沖存儲器 (Cache) Cache的管理全部用硬件實現(xiàn)管理全部用硬件實現(xiàn)。 Once the data is stored in the cache, future use can be made by accessing the c

4、ached copy rather than re-fetching the original data, so that the average access time is shorter. Small memories on or close to the CPU chip can be made faster than the much larger main memory. Most CPUs since the 1980s have used one or more caches. Cache和主存都分成若干行（塊，Block，Line，Slot），每 行有若干字（Word）或字節(jié)

5、組成。 （一）Cache-主存層次主存層次的基本結(jié)構(gòu) 裝入 Cache 直接通路 1個字 Cache地址 主存地址 塊 號 塊內(nèi)地址 主存- Cache 地址映射變換機構(gòu) 塊 號 塊內(nèi)地址 Cache 主存 Cache 替換策略 Address Mapping From Processor 地址總線 數(shù)據(jù)總線 To Processor Miss Hit 1行 已裝不進 This is accomplished by comparing the address of the memory location to all tags in the cache that might contain t

6、hat address. If the processor finds that the memory location is in the cache, we say that a cache hit has occurred; When the processor needs to read or write a location in main memory, it first checks whether that memory location is in the cache. 裝入 Cache 直接通路 1個字 Cache地址 主存地址 塊 號 塊內(nèi)地址 主存- Cache 地址映

7、射變換機構(gòu) 塊 號 塊內(nèi)地址 Cache 主存 Cache 替換策略 Address Mapping From Processor 地址總線 數(shù)據(jù)總線 To Processor Miss Hit 1行 已裝不進 otherwise, we speak of a cache miss. 如果在Cache中，稱為命中Hit，則訪問Cache。 如果不在Cache中，稱為不命中Miss（塊失效），則訪問主存。 同時，將包含該字的一行裝入Cache。 若Cache已滿，則按 照某種替換策略把該 行替換進Cache。 CPU訪問Cache， 每次1個字。 主存-Cache地址映射變換機構(gòu)將處理機發(fā)出的主

8、存地址變換 成Cache地址，判定該字所在行是否在Cache中。 裝入 Cache 直接通路 1個字 Cache地址 主存地址 塊 號塊內(nèi)地址 主存- Cache 地址映射變換機構(gòu) 塊 號塊內(nèi)地址 Cache 主存 Cache 替換策略 Address Mapping From Processor 地址總線 數(shù)據(jù)總線 To Processor Miss Hit 1行 已裝不進 主存與 Cache之間 的數(shù)據(jù)傳輸以數(shù)據(jù) 塊為單位。要求總 線和主存支持多字 （塊）同時傳輸。 盛建倫7 2345*程序計數(shù)器PC Cache Tag內(nèi)容 08 BD 主存儲器 2344 AB CD2345 30 CD2

9、346 9B 762347 C3 BD2348 0B CD2349 1F CD234A 90 71234B 訪問Cache 不命中 讀主存 并將從主存 讀出的字裝 入Cache 2345AB CD AB指令寄存器IR 以取指令為例 行地址 每行2個字 盛建倫8 2346*程序計數(shù)器PC Cache Tag內(nèi)容 08 BD 主存儲器 2344 AB CD2345 30 CD2346 9B 762347 C3 BD2348 0B CD2349 1F CD234A 90 71234B 訪問Cache 不命中 讀主存 并將從主存 讀出的字裝 入Cache 2345AB CD 30指令寄存器IR 234

10、630 CD 以取指令為例 盛建倫9 2345*程序計數(shù)器PC Cache Tag內(nèi)容 08 BD 主存儲器 2344 AB CD2345 30 CD2346 9B 762347 C3 BD2348 0B CD2349 1F CD234A 90 71234B 訪問Cache 命中 讀Cache 2345AB CD AB指令寄存器IR 234630 CD 以取指令為例 盛建倫10 2344*程序計數(shù)器PC Cache Tag內(nèi)容 08 BD 主存儲器 2344 AB CD2345 30 CD2346 9B 762347 C3 BD2348 0B CD2349 1F CD234A 90 71234

11、B 訪問Cache 不命中 讀主存 Cache已滿， 替換1行 2345ABCD 08指令寄存器IR 234630 CD 234A1F CD 234B90 71 234408 BD 以取指令為例 原理上，Cache-主存層次有兩種工作方式： 方式方式1. CPU對對Cache和主存都有直接訪問路徑。和主存都有直接訪問路徑。 方式方式2. CPU只直接訪問只直接訪問Cache，不直接訪問主存。，不直接訪問主存。 Cache既是Cache-主存層次中的 一層，也是一個旁路存儲器。 CPUCache主存 CPU Cache 主存 CPU發(fā)出的地址同時訪問同時訪問Cache和主存。如果Cache命中命

12、中，則 放棄對主存的訪問。如果Cache不命中不命中，則從主存讀出。 當(dāng)CPU需要訪問存儲器時，先檢查Cache，此時，地址不出現(xiàn) 在地址總線上。如果Cache不命中，才通過總線訪問主存。 標(biāo)準(zhǔn)的二級存儲層次。 TA= HTC +（1H）（TM） TA= HTC +（1H）（TM+ TC） 盛建倫12 （二）平均訪問時間平均訪問時間 TA=HTA1 +（1H）TA2 = 例如，主存的訪問時間為100ns，Cache的訪問時間為10ns， 命中率為90%。則Cache-主存層次的平均訪問時間為 使用Cache可明顯改進計算機系統(tǒng)的平均訪問時間。如果命 中率足夠高，則大多數(shù)的訪問時間都接近于快速的

13、Cache存儲器 的訪問時間。 如果Cache的速度與處理機相當(dāng)，容量足夠大，配上以合適 的調(diào)度算法為基礎(chǔ)的、全部硬化的地址映射變換部件，實現(xiàn)高的 命中率，則可能實現(xiàn)高主振頻率的CPU的零等待（在訪存時，不 插入TW）。 平均訪問時間受命中率命中率的影響很大。 HTC +（1H）（TM+ TC） = 0.910+（10.9）110 ns =20 ns 盛建倫13 Cache設(shè)計設(shè)計 影響命中率的因素：Cache的容量，行的容量，地址映射 變換，替換算法，Cache的個數(shù)，地址流，等。 1Cache的容量的容量 （Cache Size） Cache的容量每增加一倍增加一倍，不命中率減少不命中率減

14、少30%。 Cache的容量 越大命中率越高。 2行的容量行的容量（ Block Size ） 一般每行116字。每行48個可尋址單元似乎接近最好。 為什么我們不把Cache的容量做的和主存容量一樣大？ 盛建倫14 3主存主存-Cache地址映射變換（地址映射變換（ Mapping Function ） Cache存儲器的基本特點是快速的訪存。因此，在Cache中尋 找字的時間必須極短。 把主存地址變換成Cache地址稱為映射。實際使用的映射變 換有3種： 直接映射 Direct Mapping 相聯(lián)映射（全相聯(lián)） Fully Associative Mapping 組相聯(lián)映射 Set- as

15、sociative Mapping 盛建倫 Cache行i主存塊j 0 1 m-1 0，m，2m，2S-m 1，m+1，2 m+1，2 S-m+1 m-1，2 m-1，3 m-1，2 S-1 （1）直接映射直接映射 Direct Mapping 主存的每一塊只能映射到Cache的一個特定的行。 若Cache有m行，每行n字，主存有2S塊， 則直接映射可表示為 Cache的行號i =主存的塊號j（Modulo m） 0 1 2 m-1 Cache0 主存 1 2 m-1 m m+1 m+2 2m-1 km-1 km nm-1 2m 2m+1 盛建倫16 設(shè) m=2r ，n=2W若 Cache有m

16、行，每行n字，主存有2S塊， 主存地址（S+w位） Cache地址（r+w位） Tag 字 0 字 1 字 n-1 Cache的 內(nèi)容 選中1行選中行內(nèi)1個字 標(biāo)志Tag行地址Line字地址Word S r位r位w位 行地址Line字地址Word 直接映射直接映射 Direct Mapping 盛建倫17 S- r = 8位r = 14位w = 2位 主存容量16MB，按字節(jié)編址，Cache容量64KB，每行4個字節(jié)。 16M = 224，主存地址24位。 主存的行數(shù) S = 22， Cache的行數(shù) m = 16k行 = 214行， n = 4 ， 主存地址（S+w位） 選中1行選中行內(nèi)1個

17、字 Cache地址（r+w位） TagW0W1W2W3 8 位 8 位 8 位 8 位 8 位 Cache的內(nèi)容 例如： 標(biāo)志Tag行地址Line字地址Word 行地址Line字地址Word 直接映射直接映射 Direct Mapping 盛建倫18 S- r = 8位r = 14位w = 2位 主存容量16MB，按字節(jié)編址，Cache容量64KB，每行4個字節(jié) 主存地址（S+w位） 選中1行選中行內(nèi)1個字 Cache地址（r+w位） TagW0W1W2W3 8位8位8位8位8位 Cache 的內(nèi)容 CPU訪存時，用主存地址中間的r =14位作為Cache行地址，選 中1行Cache。把該行的

18、Tag與主存地址中的高8位Tag比較。 若相同，則命中，用主存地址最低2位作為字地址取出1個字 節(jié)數(shù)據(jù)。 若不命中，則22位地址S用于從主存中取出1個塊（4字節(jié)）數(shù) 據(jù)至Cache。 例如： 標(biāo)志Tag行地址Line字地址Word 行地址Line字地址Word 盛建倫19 直接映射技術(shù)簡單、廉價、 易于實現(xiàn)。 主要缺點： 對于任意給定的主存塊，都有 一個固定的Cache位置。 如果一個程序碰巧重復(fù)地訪問映射 到同一行Cache的2個主存塊，則這2個塊 需連續(xù)地交換進Cache，命中率很低。 塊沖突概率最高塊沖突概率最高。 0 1 2 m-1 Cache0 主存 1 2 m-1 m m+1 m+

19、2 2m-1 km-1 km nm-1 2m 2m+1 直接映射直接映射 Direct Mapping 盛建倫20 （2）相聯(lián)映射相聯(lián)映射 Associative Mapping （全相聯(lián)映射全相聯(lián)映射 Fully Associative Mapping） 主存的任何塊都能映象到Cache的任何行。 把主存地址作為標(biāo)志項和數(shù)據(jù)一道存入Cache。該標(biāo)志項唯 一地識別主存的一塊。為了確定1個塊是否在Cache中，Cache的 控制邏輯必須同時檢查每一行的標(biāo)志項是否相符。 例：主存容量16MB，Cache容量4KB，1K行，每行4個字節(jié)。 主存地址TagWord 22位2位 TagW0W1W2W3

20、 22位 8位 8位 8位 8位 Cache的內(nèi)容 盛建倫21 相聯(lián)存儲器是最快、最靈活的Cache組織，克服了直接映射的 缺點。允許主存的每一塊裝入Cache的任一行中。有相應(yīng)的替換 算法使其得到最大的命中率。 主要缺點：需要復(fù)雜的相聯(lián)比較電路來并行地檢查全部 Cache行的標(biāo)志項。成本高。容量難以做大。 The hardware for a fully-associative cache can be rather complex, which is why you dont see fully-associative caches (except for translation look

21、aside buffers). 相聯(lián)映射相聯(lián)映射 Associative Mapping 盛建倫22 主存的任一塊j只能映象到 Cache的組i。塊j可映射到 組i中任一行。 （3）組相聯(lián)映射組相聯(lián)映射 Set- associative Mapping 組相聯(lián)映射是對直接 映射和全相聯(lián)映射技術(shù)的折 中，避免了二者的缺點。組 間是直接映象，組內(nèi)各行間 是全相聯(lián)映象。 設(shè)Cache有m行，主存分成 與Cache行同樣大小的 2S塊， 每塊n字。 0 主存 1 2 6 7 8 4 5 3 Cache 0Tag 1 Set 0 0 1 Set 1 0 1 Set 2 0 1 Set 3 Cache分成

22、Q組，每組R行。m=QRQ=2d Cache的組號i = 主存塊號j（Modulo Q） 盛建倫23 （3）組相聯(lián)映射組相聯(lián)映射 Set- associative Mapping 設(shè)Cache有m行，主存分成 與Cache行同樣大小的 2S塊， 每塊n字。 0 主存 1 2 6 7 8 4 5 3 Cache 0Tag 1 Set 0 0 1 Set 1 0 1 Set 2 0 1 Set 3 Cache分成Q組，每組R行。 Q=2dm=QR 當(dāng)Q = m，R = 1時是直接映 射。 當(dāng)Q = 1，R = m時是全相 聯(lián)映射。 2路組相聯(lián)最常用，比直 接映射顯著改善命中率。 4路組相聯(lián)，命中率

23、略有 改善，成本略增。 R8，對命中率改善不明顯，成本顯著增加，速度下降。 主存容量16MB，Cache容量64KB，每行4個字節(jié)，2路組相聯(lián)。 Cache 行數(shù)= 16K行， R = 2，Q = 8K=2d 主存地址（S+w位） 選中1組選中行內(nèi)1個字 標(biāo)志Tag行地址Set字地址Word 9位13位2位 組地址Set字地址WordCache地址（d+w位） CPU訪存時，用主存地址中間的 d=13位作為Cache組地址，選中1組 Cache。把該組的2行的Tag同時與主 存地址中的高9位Tag比較。 若某行的Tag與主存地址中的Tag相符 合，則命中，用主存地址最低2位作為 字地址從該行中

24、取出1個字節(jié)數(shù)據(jù)。 若不命中，則用22位地址S從主存中 取出1個塊（4字節(jié)）數(shù)據(jù)至Cache。 0 主存 1 2 6 7 8 4 5 3 Cache 0Tag 1 Set 0 0 1 Set 1 0 1 Set 2 0 1 Set 3 例如： 盛建倫25 4替換算法替換算法 （Replacement Algorithm） 當(dāng)一個新的塊要裝入的Cache位置存在一個原有的塊時， 就要進行替換。 直接映射直接映射，只有一個可能的行，別無選擇。 全相聯(lián)全相聯(lián)和組相聯(lián)映射組相聯(lián)映射，需要一種替換算法，而且必須用硬件 實現(xiàn)。 為了達(dá)到高速的目標(biāo)，替換算法是高命中率的一個關(guān)鍵因素。 常用的Cache替換算

25、法有：LRU，F(xiàn)IFO，LFU，Random。 The hit rate of a cache describes how often a searched-for item is actually found in the cache. More efficient replacement policies keep track of more usage information in order to improve the hit rate (for a given cache size). 盛建倫26 替換算法替換算法 （Replacement Algorithm） LRU（Least

26、-Recently Used） 替換出Cache中時間最長未被訪問的行。 對2路組相聯(lián)是最容易實現(xiàn)的。每行設(shè)一個使用位使用位，當(dāng)一行 被訪問時，將該行的使用位使用位置1，而同組中另一行的使用位使用位置0。 當(dāng)要裝入一塊到該組時，使用位使用位為0的行被替換。 discards the least recently used items first. FIFO（First-In-First-Out） 把在Cache中存在最久的塊替換出去。 可用一種循環(huán)緩沖技術(shù)實現(xiàn)。 盛建倫27 LFU（Least-Frequently Used） 將Cache中經(jīng)歷了最少訪問次數(shù)的塊替換出去。 可在每行設(shè)置一個計

27、數(shù)器來實現(xiàn)。 Random 不是基于信息塊被使用的情況，而是隨機地選一個塊替換出 去。 模擬研究表明，性能略低于基于使用的替換算法。 LFU counts how often an item is needed. Those that are used least often are discarded first. 替換算法替換算法 （Replacement Algorithm） 盛建倫28 Cache是主存的部分內(nèi)容的副本副本，它們的內(nèi)容應(yīng)該是一致的。 當(dāng)處理機執(zhí)行寫操作時，如果只寫入Cache，則主存中對應(yīng) 部分仍然是原來的。 5Cache的寫策略（的寫策略（Write Policy）

28、有兩種主存修改算法：寫回法，寫直達(dá)法。 Cache和主存的一致性一致性Consistency問題。 寫直達(dá)法寫直達(dá)法 Write Through In a write-through cache, every write to the cache causes a write to main memory. 缺點缺點：每次寫Cache都要附加一個時間大得多的寫主存，增 大了主存信息交換量，可能產(chǎn)生瓶頸。 對Cache的所有寫操作也寫入主存，使主存中總是有效數(shù)據(jù)主存中總是有效數(shù)據(jù)。 盛建倫29 Cache的寫策略（的寫策略（Write Policy） 寫回法寫回法 Write Back In a

29、 write-back cache, writes are not immediately mirrored to memory. Instead, the cache tracks which locations have been written over (these locations are marked dirty). The data in these locations are written back to main memory when that data is evicted from the cache. 寫回法使主存寫操作最少?？蓽p少中間結(jié)果寫存。 存儲器寫操作約占

30、訪存總數(shù)存儲器寫操作約占訪存總數(shù)的1034%。 實現(xiàn)實現(xiàn)：每行有1個更新位。當(dāng)該行被寫時，將更新位置1。當(dāng) 該行被替換時，當(dāng)且僅當(dāng)其更新位為1時，才將該塊寫回主存。 問題問題：主存相應(yīng)塊中的內(nèi)容可能是無效的。 在執(zhí)行寫操作時，信息只寫入Cache，僅當(dāng)需要被替換時才 將該Cache行寫回主存。然后再調(diào)入新塊。 盛建倫30 當(dāng)出現(xiàn)寫不命中時，無論寫回法還是寫直達(dá)法都有一個在寫 時是否取的問題。 不按寫分配不按寫分配法 按寫分配按寫分配法 除了處理機的寫操作外，DMA、通道和I/O處理機向主存寫 也會造成主存與Cache內(nèi)容的不一致。 當(dāng)Cache寫不命中時，除寫入主存外，還把該寫地址單元所 在塊

31、從主存調(diào)入Cache。 寫回法一般采用。 當(dāng)Cache寫不命中時只寫入主存，該寫地址單元所在塊不從 主存調(diào)入Cache。 寫直達(dá)法一般采用。 盛建倫31 6 Cache的取算法的取算法 (1) 按需取進按需取進法 僅當(dāng)Cache不命中時取進。 (2) 預(yù)取法預(yù)取法 通常是預(yù)取直接順序的下一塊。 恒預(yù)?。褐灰L問第i塊，不論是否命中，恒發(fā)預(yù)取命令。 不命中時預(yù)?。褐挥挟?dāng)訪問第i塊不命中時才發(fā)預(yù)取命令。 盛建倫32 7 Cache的初始化的初始化（Initialization） 在初始時，Cache被認(rèn)為是空的，但實際上充滿無效數(shù)據(jù)。 當(dāng)計算機上電或從輔存向主存加載一個完整程序時，Cache 被初

32、始化初始化。 通常為Cache中的每個字加一個有效位有效位（Valid bit）來表示該 字是否包含有效數(shù)據(jù)有效數(shù)據(jù)。 一個字從主存裝入Cache就把其有效位有效位置1。 當(dāng)把所有的有效位清零就使Cache初始化初始化了。 (1) 統(tǒng)一統(tǒng)一/分離的分離的Cache (Unified / Split Cache) 早期的設(shè)計是一個Cache既保存數(shù)據(jù)又放指令?，F(xiàn)在多采用分 離的Cache。 一個指令指令Cache，一個數(shù)據(jù)數(shù)據(jù)Cache。 Pipelined CPUs access memory from multiple points in the pipeline: instruction

33、fetch, virtual-to-physical address translation, and data fetch The natural design is to use different physical caches for each of these points, so that no one physical resource has to be scheduled to service two points in the pipeline. 8Cache的個數(shù)的個數(shù) Number of Caches 在Cache初被引入時，典型系統(tǒng)只有一個Cache?，F(xiàn)在多采用多個C

34、ache。 Thus the pipeline naturally ends up with at least two separate caches (instruction and data), each specialized to its particular role. Pipelines with separate instruction and data caches are said to have a Harvard architecture. Originally, this phrase referred to machines with separate instruc

35、tion and data memories. 一個統(tǒng)一的Cache的優(yōu)點是，在Cache總?cè)萘恳欢〞r，有更高 的命中率。因為它自動平衡了指令和數(shù)據(jù)的負(fù)載。而且只需設(shè)計 并實現(xiàn)一個Cache。 分離的Cache的優(yōu)點是，消除了指令處理機與執(zhí)行單元之間 的競爭，使兩個操作可以并行進行。這對于流水線機器、超標(biāo)量 機器很重要。預(yù)取的指令可以充滿Cache。 Cache的個數(shù)的個數(shù) Number of Caches Another issue is the fundamental tradeoff between cache latency and hit rate. Larger caches ha

36、ve better hit rates but longer latency. To address this tradeoff, many computers use multiple levels of cache, with small fast caches backed up by larger slower caches. (2) 多級多級Cache （Multi-level Caches ） Multi-level caches generally operate by checking the smallest Level 1 (L1) cache first; if it h

37、its, the processor proceeds at high speed. If the smaller cache misses, the next larger cache (L2) is checked, and so on. 盛建倫35 兩級兩級Cache （Two-level Caches ） 處理機片內(nèi)的On-Chip Cache（L1）減少處理機的外部總線活 動，縮短執(zhí)行時間，提高總體系統(tǒng)性能。 當(dāng)所需的指令或數(shù)據(jù)在On-Chip Cache中找到時，就消除了總 線訪問。由于片內(nèi)的數(shù)據(jù)路徑短，On-Chip Cache的存取比零等待 狀態(tài)總線周期更快。同時，總線不被處理

38、機占用可支持其它傳輸。 片外的第二級Cache（L2） （On-Board Cache）是當(dāng)L1不命中 時，縮短訪存時間，并提高命中率。 如果L2的SRAM可與總線速度匹配， 則可實現(xiàn)零等待狀態(tài)傳輸。 CPU L1 Cache L2 Cache 主板 主存 Cache的地址映射變換地址映射變換和替換算替換算 法法的實現(xiàn)全部實現(xiàn)全部是硬件實現(xiàn)硬件實現(xiàn)的。 因此，Cache-主存層次對應(yīng)用 程序員和系統(tǒng)程序員應(yīng)該都是透透 明明的。 而且Cache對處理機和主存之間的 信息交往也是透明透明的。 By the time multiple processor cores became common, a

39、 tertiary level cache was added on to the CPU die, called the L3. It also became common to have the three levels be larger in size than the next so that it became not uncommon to find Level 3 cache sizes of eight megabytes. This trend appears to continue for the foreseeable future. CPU L0 Cache L2 C

40、ache 主板 主存 L1 Cache 封裝 在 CPU 上面 盛建倫37 Pentium的Cache結(jié)構(gòu)： Two-way Set-associative。每行32字節(jié)，128個兩行組。 每行有1個Tag和2個狀態(tài)位。Tag是邏輯地址的最高20位。 LRU替換算法，每個兩行組有1個LRU位。 數(shù)據(jù)Cache用Write Back?？梢詣討B(tài)配置成支持Write Through。 支持外部的第2級Cache，256KB或512KB。 1個8kB的數(shù)據(jù)Cache， 1個8kB的指令Cache。 With the 486 processor, an 8 KB cache was integrated directly into the CPU die. This cache was termed Level 1 or L1 cache to differentiate it from the