计算机组成原理第17讲_Cache

1、Principles of Computer Organization广义双语教学课程09/skyclass25/青岛理工大学 校级精品课程http:/ 7 章章 存储系统存储系统(2)Chapter 7 Storage SystemA 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 memory which stor

2、es 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.盛建伦3Cache-主存层次工作原理主存层次工作原理Cache 是位于CPU与主存之间主存之间的一个高速小容

3、量高速小容量的存储器存储器。 Cache一般采用和CPU相同的半导体工艺半导体工艺制成，在物理位置物理位置上尽量靠近CPU，而不在主存模块中，最好在处理器芯片内。其速度速度与CPU的速度相匹配的速度相匹配，即能够在一个最短的存储周期内完成一次读/写，约比主存速度高比主存速度高数倍数十倍以上。72 高速缓冲存储器高速缓冲存储器 (Cache)Cache的管理全部用硬件实现管理全部用硬件实现。Once the data is stored in the cache, future use can be made by accessing the cached copy rather than re

4、-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）或字节组成。（一）Cache-主存层次主存层次的基本结构装入

5、Cache直接通路1个字Cache地址主存地址块 号块内地址主存- Cache地址映射变换机构块 号块内地址Cache主存Cache替换策略AddressMappingFrom Processor地址总线数据总线To ProcessorMissHit1行已装不进This is accomplished by comparing the address of the memory location to all tags in the cache that might contain that address. If the processor finds that the memory loc

6、ation 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地址主存地址块 号块内地址主存- Cache地址映射变换机构块 号块内地址Cache主存Cache替换策略AddressMappingFrom Processor地址总线数据总线

7、To ProcessorMissHit1行已装不进otherwise, we speak of a cache miss. 如果在Cache中，称为命中Hit，则访问Cache。 如果不在Cache中，称为不命中Miss（块失效），则访问主存。同时，将包含该字的一行装入Cache。若Cache已满，则按照某种替换策略把该行替换进Cache。 CPU访问Cache，每次1个字。 主存-Cache地址映射变换机构将处理机发出的主存地址变换成Cache地址，判定该字所在行是否在Cache中。装入Cache直接通路1个字Cache地址主存地址块 号块内地址主存- Cache地址映射变换机构块 号块内地

8、址Cache主存Cache替换策略AddressMappingFrom Processor地址总线数据总线To ProcessorMissHit1行已装不进 主存与 Cache之间的数据传输以数据块为单位。要求总线和主存支持多字（块）同时传输。盛建伦72345*程序计数器PCCacheTag内容08 BD主存储器2344AB CD234530 CD23469B 762347C3 BD23480B CD23491F CD234A90 71234B访问Cache不命中读主存并将从主存读出的字装入Cache2345AB CDAB指令寄存器IR以取指令为例行地址每行2个字盛建伦82346*程序计数器P

9、CCacheTag内容08 BD主存储器2344AB CD234530 CD23469B 762347C3 BD23480B CD23491F CD234A90 71234B访问Cache不命中读主存并将从主存读出的字装入Cache2345AB CD30指令寄存器IR234630 CD以取指令为例盛建伦92345*程序计数器PCCacheTag内容08 BD主存储器2344AB CD234530 CD23469B 762347C3 BD23480B CD23491F CD234A90 71234B访问Cache命中读Cache2345AB CDAB指令寄存器IR234630 CD以取指令为例盛

10、建伦102344*程序计数器PCCacheTag内容08 BD主存储器2344AB CD234530 CD23469B 762347C3 BD23480B CD23491F CD234A90 71234B访问Cache不命中读主存Cache已满，替换1行2345ABCD08指令寄存器IR234630 CD234A1F CD234B90 71234408 BD以取指令为例原理上，Cache-主存层次有两种工作方式：方式方式1. CPU对对Cache和主存都有直接访问路径。和主存都有直接访问路径。方式方式2. CPU只直接访问只直接访问Cache，不直接访问主存。，不直接访问主存。Cache既是C

11、ache-主存层次中的一层，也是一个旁路存储器。CPUCache主存CPUCache主存 CPU发出的地址同时访问同时访问Cache和主存。如果Cache命中命中，则放弃对主存的访问。如果Cache不命中不命中，则从主存读出。 当CPU需要访问存储器时，先检查Cache，此时，地址不出现在地址总线上。如果Cache不命中，才通过总线访问主存。标准的二级存储层次。TA= HTC +（1H）（TM）TA= HTC +（1H）（TM+ TC）盛建伦12（二）平均访问时间平均访问时间TA=HTA1 +（1H）TA2 = 例如，主存的访问时间为100ns，Cache的访问时间为10ns，命中率为90%。

12、则Cache-主存层次的平均访问时间为 使用Cache可明显改进计算机系统的平均访问时间。如果命中率足够高，则大多数的访问时间都接近于快速的Cache存储器的访问时间。 如果Cache的速度与处理机相当，容量足够大，配上以合适的调度算法为基础的、全部硬化的地址映射变换部件，实现高的命中率，则可能实现高主振频率的CPU的零等待（在访存时，不插入TW）。平均访问时间受命中率命中率的影响很大。HTC +（1H）（TM+ TC）= 0.910+（10.9）110 ns =20 ns盛建伦13Cache设计设计 影响命中率的因素：Cache的容量，行的容量，地址映射变换，替换算法，Cache的个数，地址

13、流，等。1Cache的容量的容量 （Cache Size） Cache的容量每增加一倍增加一倍，不命中率减少不命中率减少30%。 Cache的容量越大命中率越高。2行的容量行的容量（ Block Size ）一般每行116字。每行48个可寻址单元似乎接近最好。 为什么我们不把Cache的容量做的和主存容量一样大？盛建伦143主存主存-Cache地址映射变换（地址映射变换（ Mapping Function ） Cache存储器的基本特点是快速的访存。因此，在Cache中寻找字的时间必须极短。 把主存地址变换成Cache地址称为映射。实际使用的映射变换有3种： 直接映射 Direct Mappi

14、ng 相联映射（全相联） Fully Associative Mapping 组相联映射 Set- associative Mapping盛建伦Cache行i主存块j01m-10，m，2m，2S-m1，m+1，2 m+1，2S-m+1m-1，2 m-1，3 m-1，2S-1（1）直接映射直接映射 Direct Mapping主存的每一块只能映射到Cache的一个特定的行。若Cache有m行，每行n字，主存有2S块，则直接映射可表示为Cache的行号i =主存的块号j（Modulo m）012m-1Cache0主存12m-1mm+1m+22m-1km-1kmnm-12m2m+1盛建伦16设 m=

15、2r ，n=2W若 Cache有m行，每行n字，主存有2S块，主存地址（S+w位）Cache地址（r+w位）Tag字 0字 1字 n-1Cache的内容选中1行选中行内1个字标志Tag行地址Line字地址WordS r位r位w位行地址Line字地址Word直接映射直接映射 Direct Mapping盛建伦17S- r = 8位r = 14位w = 2位主存容量16MB，按字节编址，Cache容量64KB，每行4个字节。16M = 224，主存地址24位。 主存的行数 S = 22， Cache的行数 m = 16k行 = 214行， n = 4 ，主存地址（S+w位）选中1行选中行内1个字C

16、ache地址（r+w位）TagW0W1W2W38 位8 位8 位8 位8 位Cache的内容例如：标志Tag行地址Line字地址Word行地址Line字地址Word直接映射直接映射 Direct Mapping盛建伦18S- r = 8位r = 14位w = 2位主存容量16MB，按字节编址，Cache容量64KB，每行4个字节主存地址（S+w位）选中1行选中行内1个字Cache地址（r+w位）TagW0W1W2W38位8位8位8位8位Cache 的内容 CPU访存时，用主存地址中间的r =14位作为Cache行地址，选中1行Cache。把该行的Tag与主存地址中的高8位Tag比较。 若相同，

17、则命中，用主存地址最低2位作为字地址取出1个字节数据。 若不命中，则22位地址S用于从主存中取出1个块（4字节）数据至Cache。例如：标志Tag行地址Line字地址Word行地址Line字地址Word盛建伦19 直接映射技术简单、廉价、易于实现。主要缺点：对于任意给定的主存块，都有一个固定的Cache位置。 如果一个程序碰巧重复地访问映射到同一行Cache的2个主存块，则这2个块需连续地交换进Cache，命中率很低。块冲突概率最高块冲突概率最高。012m-1Cache0主存12m-1mm+1m+22m-1km-1kmnm-12m2m+1直接映射直接映射 Direct Mapping盛建伦20

18、（2）相联映射相联映射 Associative Mapping（全相联映射全相联映射 Fully Associative Mapping）主存的任何块都能映象到Cache的任何行。 把主存地址作为标志项和数据一道存入Cache。该标志项唯一地识别主存的一块。为了确定1个块是否在Cache中，Cache的控制逻辑必须同时检查每一行的标志项是否相符。例：主存容量16MB，Cache容量4KB，1K行，每行4个字节。主存地址TagWord22位2位TagW0W1W2W322位8位8位8位8位Cache的内容盛建伦21 相联存储器是最快、最灵活的Cache组织，克服了直接映射的缺点。允许主存的每一块装

19、入Cache的任一行中。有相应的替换算法使其得到最大的命中率。 主要缺点：需要复杂的相联比较电路来并行地检查全部Cache行的标志项。成本高。容量难以做大。The hardware for a fully-associative cache can be rather complex, which is why you dont see fully-associative caches (except for translation lookaside buffers). 相联映射相联映射 Associative Mapping盛建伦22主存的任一块j只能映象到Cache的组i。块j可映射到组

20、i中任一行。（3）组相联映射组相联映射 Set- associative Mapping 组相联映射是对直接映射和全相联映射技术的折中，避免了二者的缺点。组间是直接映象，组内各行间是全相联映象。设Cache有m行，主存分成与Cache行同样大小的 2S块，每块n字。0主存12678453Cache0Tag1Set 001Set 101Set 201Set 3Cache分成Q组，每组R行。m=QRQ=2dCache的组号i = 主存块号j（Modulo Q）盛建伦23（3）组相联映射组相联映射 Set- associative Mapping 设Cache有m行，主存分成与Cache行同样大小的

21、 2S块，每块n字。0主存12678453Cache0Tag1Set 001Set 101Set 201Set 3Cache分成Q组，每组R行。Q=2dm=QR当Q = m，R = 1时是直接映射。当Q = 1，R = m时是全相联映射。 2路组相联最常用，比直接映射显著改善命中率。 4路组相联，命中率略有改善，成本略增。R8，对命中率改善不明显，成本显著增加，速度下降。主存容量16MB，Cache容量64KB，每行4个字节，2路组相联。Cache 行数= 16K行， R = 2，Q = 8K=2d主存地址（S+w位）选中1组选中行内1个字标志Tag行地址Set字地址Word9位13位2位组地

22、址Set字地址WordCache地址（d+w位） CPU访存时，用主存地址中间的d=13位作为Cache组地址，选中1组Cache。把该组的2行的Tag同时与主存地址中的高9位Tag比较。若某行的Tag与主存地址中的Tag相符合，则命中，用主存地址最低2位作为字地址从该行中取出1个字节数据。若不命中，则用22位地址S从主存中取出1个块（4字节）数据至Cache。0主存12678453Cache0Tag1Set 001Set 101Set 201Set 3例如：盛建伦254替换算法替换算法 （Replacement Algorithm） 当一个新的块要装入的Cache位置存在一个原有的块时，就要

23、进行替换。直接映射直接映射，只有一个可能的行，别无选择。 全相联全相联和组相联映射组相联映射，需要一种替换算法，而且必须用硬件实现。为了达到高速的目标，替换算法是高命中率的一个关键因素。常用的Cache替换算法有：LRU，FIFO，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 o

24、rder to improve the hit rate (for a given cache size).盛建伦26替换算法替换算法 （Replacement Algorithm） LRU（Least-Recently Used）替换出Cache中时间最长未被访问的行。 对2路组相联是最容易实现的。每行设一个使用位使用位，当一行被访问时，将该行的使用位使用位置1，而同组中另一行的使用位使用位置0。当要装入一块到该组时，使用位使用位为0的行被替换。discards the least recently used items first. FIFO（First-In-First-Out）把在Ca

25、che中存在最久的块替换出去。可用一种循环缓冲技术实现。盛建伦27 LFU（Least-Frequently Used）将Cache中经历了最少访问次数的块替换出去。可在每行设置一个计数器来实现。 Random 不是基于信息块被使用的情况，而是随机地选一个块替换出去。模拟研究表明，性能略低于基于使用的替换算法。LFU counts how often an item is needed. Those that are used least often are discarded first.替换算法替换算法 （Replacement Algorithm）盛建伦28Cache是主存的部分内容的副

26、本副本，它们的内容应该是一致的。 当处理机执行写操作时，如果只写入Cache，则主存中对应部分仍然是原来的。5Cache的写策略（的写策略（Write Policy）有两种主存修改算法：写回法，写直达法。Cache和主存的一致性一致性Consistency问题。 写直达法写直达法 Write ThroughIn a write-through cache, every write to the cache causes a write to main memory. 缺点缺点：每次写Cache都要附加一个时间大得多的写主存，增大了主存信息交换量，可能产生瓶颈。对Cache的所有写操作也写入主存

27、，使主存中总是有效数据主存中总是有效数据。盛建伦29Cache的写策略（的写策略（Write Policy） 写回法写回法 Write BackIn a 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 memo

28、ry when that data is evicted from the cache.写回法使主存写操作最少。可减少中间结果写存。存储器写操作约占访存总数存储器写操作约占访存总数的1034%。 实现实现：每行有1个更新位。当该行被写时，将更新位置1。当该行被替换时，当且仅当其更新位为1时，才将该块写回主存。问题问题：主存相应块中的内容可能是无效的。 在执行写操作时，信息只写入Cache，仅当需要被替换时才将该Cache行写回主存。然后再调入新块。盛建伦30 当出现写不命中时，无论写回法还是写直达法都有一个在写时是否取的问题。 不按写分配不按写分配法 按写分配按写分配法 除了处理机的写操作外，

29、DMA、通道和I/O处理机向主存写也会造成主存与Cache内容的不一致。 当Cache写不命中时，除写入主存外，还把该写地址单元所在块从主存调入Cache。 写回法一般采用。 当Cache写不命中时只写入主存，该写地址单元所在块不从主存调入Cache。 写直达法一般采用。盛建伦316 Cache的取算法的取算法(1) 按需取进按需取进法仅当Cache不命中时取进。(2) 预取法预取法通常是预取直接顺序的下一块。 恒预取：只要访问第i块，不论是否命中，恒发预取命令。 不命中时预取：只有当访问第i块不命中时才发预取命令。盛建伦327 Cache的初始化的初始化（Initialization）在初始

30、时，Cache被认为是空的，但实际上充满无效数据。 当计算机上电或从辅存向主存加载一个完整程序时，Cache被初始化初始化。 通常为Cache中的每个字加一个有效位有效位（Valid bit）来表示该字是否包含有效数据有效数据。一个字从主存装入Cache就把其有效位有效位置1。当把所有的有效位清零就使Cache初始化初始化了。(1) 统一统一/分离的分离的Cache (Unified / Split Cache) 早期的设计是一个Cache既保存数据又放指令。现在多采用分离的Cache。 一个指令指令Cache，一个数据数据Cache。Pipelined CPUs access memory

31、from multiple points in the pipeline: instruction 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的个数的个数 Nu

32、mber of Caches 在Cache初被引入时，典型系统只有一个Cache。现在多采用多个Cache。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 ph

33、rase referred to machines with separate instruction and data memories. 一个统一的Cache的优点是，在Cache总容量一定时，有更高的命中率。因为它自动平衡了指令和数据的负载。而且只需设计并实现一个Cache。 分离的Cache的优点是，消除了指令处理机与执行单元之间的竞争，使两个操作可以并行进行。这对于流水线机器、超标量机器很重要。预取的指令可以充满Cache。Cache的个数的个数 Number of CachesAnother issue is the fundamental tradeoff between cac

34、he latency and hit rate. Larger caches have 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 sma

35、llest Level 1 (L1) cache first; if it hits, 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 ） 处理机片内的On-Chip Cache（L1）减少处理机的外部总线活动，缩短执行时间，提高总体系统性能。 当所需的指令或数据在On-Chip Cache中找到时，就消除了总线访问。由于片内的数据路径短，On-C

36、hip Cache的存取比零等待状态总线周期更快。同时，总线不被处理机占用可支持其它传输。 片外的第二级Cache（L2）（On-Board Cache）是当L1不命中时，缩短访存时间，并提高命中率。如果L2的SRAM可与总线速度匹配，则可实现零等待状态传输。CPUL1 CacheL2 Cache主板主存Cache的地址映射变换地址映射变换和替换算替换算法法的实现全部实现全部是硬件实现硬件实现的。 因此，Cache-主存层次对应用程序员和系统程序员应该都是透透明明的。而且Cache对处理机和主存之间的信息交往也是透明透明的。 By the time multiple processor cor

37、es became common, a 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

38、.CPUL0 CacheL2 Cache主板主存L1 Cache封装在CPU上面盛建伦37Pentium的Cache结构：Two-way Set-associative。每行32字节，128个两行组。每行有1个Tag和2个状态位。Tag是逻辑地址的最高20位。LRU替换算法，每个两行组有1个LRU位。数据Cache用Write Back。可以动态配置成支持Write Through。支持外部的第2级Cache，256KB或512KB。1个8kB的数据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 slower on-motherboard, or Level 2 (L2) cache. These on-motherboard