高速缓冲存储器的组成与运行原理

1、1第三单元 层次存储器系统第三讲 高速缓冲存储器的组成与运行原理刘卫东2内容提要 Cache的目的 基本原理 Cache的三种映射方式 提高Cache性能3CPU与DRAM性能比较处理器性能每年处理器性能每年增长增长60%动态存储器性能每年增长9%110100100019801981198319841985198619871988198919901991199219931994199519961997199819992000DRAMCPU1982CPU与主存储器的性能差与主存储器的性能差异，每年增长异，每年增长50%性能性能摩尔定律年份年份4Cache的提出一直以来，CPU和主存储器的速度总是

2、有差距CPU的发展一直以速度为主，以提高速度为核心主存的发展一直以容量为主，以提高容量为核心如何解决这之间的矛盾？5这不是一个技术问题，而是一个经济问题。从技术上说，能制造出多高速度的CPU，就能制造出同样速度的存储器，只不过是我们是否愿意付出如此高的价格。有没有更好的办法？能否用廉价的高容量存储器实现相对的高速度呢？6程序的局部性原理 程序在一定的时间段内通常只访问较小的地址空间 两种局部性： 时间局部性 空间局部性地址空间访问概率7层次存储器系统 使用高速缓冲存储器Cache来提高CPU对存储器的平均访问速度。 时间局部性：最近被访问的信息很可能还要被访问。 将最近被访问的信息项装入到Ca

3、che中。 空间局部性：最近被访问的信息临近的信息也可能被访问。 将最近被访问的信息项临近的信息一起装入到Cache中。8MEMORY CACHE CONTROLCACHE的基本运行原理的基本运行原理数据总线数据总线译码选一单元译码选一单元比较选一行比较选一行读过程为例读过程为例地址总线地址总线ADDR DATA CACHE CPU 9要解决的主要问题1. 地址之间的映射关系：如何从主存地址得到Cache地址？2. Cache中的内容是否已经是主存对应地址的内容？3. Cache内容装入策略如何提高Cache的命中率？10几个参数 块（Line）：数据交换的最小单位 命中（Hit）：在较高层次

4、中发现要访问的内容 命中率（Hit Rate）：命中次数/访问次数 命中时间：访问在较高层次中数据的时间 失效（Miss）：需要在较低层次中访问块 失效率（Miss Rate）：1-命中率 失效损失（Miss Penalty）：替换较高层次数据块的时间+将该块交付给处理器的时间 命中时间失效损失11参数典型数值 块大小：4128Byte 命中时间：14周期 失效损失： 访问时间：610个周期 传输时间：222个周期 命中率：80%99% Cache容量：1KB256KB12全相联方式全相联方式C P U数据数据地址地址有效位有效位主存储器主存储器CACHE比较比较译码译码标志标志数据数据块号块

5、内地址主存地址13全相连映射硬件实现举例14全相联方式的地址映射特点1. 主存的字块可以和Cache的任何字块对应，利用率高，方式灵活。2. 标志位较长，比较电路的成本太高。如果主存空间有2m块，则标志位要有m位。同时，如果Cache有n块，则需要有n个比较电路。使用成本太高15直接映射方式直接映射方式C P U数据数据地址地址有效位有效位主存储器主存储器CACHE比较比较译码译码译码译码块块内内地地址址块块号号标志标志数据数据块号块内地址主存地址16Cache 举例 8 块 cache 每块16 字节 “直接映射”: 内存中的每个单元在Cache中只会有一个唯一的位置和它对应。 0-1532

6、-4716-31128-143160-175144-15917直接映射Cache 举例 假定有如下访问操作: Read location 0 Read location 16 Read location 32 Read location 4 Read location 8 Read location 36 Read location 32 Read location 128 Read location 148 cache中命中和缺失各有多少次?0-1532-4716-31128-143160-175144-1590-1516-3132-47XXX 128-143XXX 144-15918Cac

7、he 举例：续 Cache中命中和缺失次数? Read location 0: Miss Read location 16: Miss Read location 32: Miss Read location 4: Hit Read location 8: Hit Read location 36: Hit Read location 32: Hit Read location 128: Miss Read location 148: Miss 命中率 = 4/9 = 45% 注意:失效的原因 启动失效 冲突失效0-1532-4716-31128-143160-175144-1590-1516

8、-3132-47XXX 128-143XXX 144-15919直接映射 Cache:硬件实现Address (showing bit positions)2010ByteoffsetValid TagDataIndex012102110221023TagIndexHitData203231 30 13 12 11 2 1 020 增加块大小可以更好地利用空间局部性直接映射 Cache: 硬件实现 Address (showing bit positions)1612ByteoffsetVTagDataHitData16324Kentries16 bits128 bitsMux32323223

9、2Block offsetIndexTag31 16 15 4 32 1 021直接映射方式的地址映射特点1. 主存的字块只可以和固定的Cache字块对应，方式直接，利用率低。2. 标志位较短，比较电路的成本低。如果主存空间有2m块，Cache中字块有2c块，则标志位只要有m-c位。且仅需要比较一次。利用率低，命中率低，效率较低22两路组相联方式两路组相联方式C P U数据数据地址地址有效位有效位主存储器主存储器CACHE译码译码比较比较比较比较译码译码译码译码标志标志数据数据块号块内地址主存地址23两路组组相联方式的地址映射特点1. 前两种方式的折衷方案。组间为全相连，组内为直接映射。2.

10、集中了两个方式的优点。成本也不太高。是常用的方式24组相连Cache访问举例z 假设有下列访问主存顺序:yRead location 0: MissyRead location 16: MissyRead location 32: MissyRead location 4: HityRead location 8: HityRead location 36: HityRead location 32: HityRead location 128: MissyRead location 148: MissyRead location 0: HityRead location 128: HityR

11、ead location 4: HityRead location 132: Hit0-1564-790-1516-3132-47128-143144-15925四路组相连Cache实现Address228VTagIndex012253254255DataVTagDataVTagDataVTagData32224-to-1 multiplexorHitData123891011123031026三种映射方式比较 直接映射 主存中的一块只能映射到Cache中唯一的一个位置 定位时，不需要判断，只需替换 全相连映射 主存中的一块可以映射到Cache中任何一个位置 N路组相连映射 主存中的一块可以选

12、择映射到Cache中N个位置 全相连映射和N路组相连映射的失效处理 从主存中取出新块 为了腾出Cache空间，需要替换出一个Cache块 不唯一，则需要判断应替出哪块27提高Cache的性能1. 提高命中率 2. 缩短缺失后的处理时间3. 提高访问cache的速度28Cache缺失的原因 必然缺失 （开机或进程切换）：首次访问数据块 世事总是有缺憾 注意：如果我们运行几百万条指令，有点必然缺失又何妨？ 冲突缺失 多个 memory块映射到同一 cache块 解决办法 1：增大 cache 容量 解决办法 2：增加相连组数 容量冲突 Cache无法装入程序需要访问的所有块 方案：增大 cache

13、 容量 无效缺失：其它进程（如I/O）修改了主存29影响影响 CACHE 命中率的因素命中率的因素 从从 CACHE 本身诸因素看，可能：本身诸因素看，可能：1. CACHE 的容量，大一些好的容量，大一些好2. CACHE 与主存储器每次交换与主存储器每次交换 信息的单位量信息的单位量(Cache Line Size)适中适中3. CACHE 不同的组织方式，多路组相联更好不同的组织方式，多路组相联更好4. CACHE 的多级组织可提高命中率的多级组织可提高命中率5. CACHE 装满后的换字算法装满后的换字算法30Cache命中率0%20%40%60%80%100%181632641282

14、56512Cache Size in KBHit Rate31块大小和缺失率的关系1 K B8 K B1 6 K B6 4 K B2 56 K B25 64 0%3 5%3 0%2 5%2 0%1 5%1 0%5 %0 %Miss rate641 64B lock size (byte s)32块大小的权衡 一般来说，数据块较大可以更好地利用空间局部性，但是： 数据块大意味着缺失损失的增大： 需要花费更长的时间来装入数据块 若块大小相对Cache总容量来说太大的话，命中率将降低 Cache块数太少一般来说，平均访问时间 = 命中时间 x 命中率 + 失效损失 x 缺失率缺失损失缺失损失块大小块

15、大小缺失率缺失率利用空间局部性较少的数据块：弥补时间局部性平均访平均访问时间问时间增加了缺失损失和缺失率块大小块大小块大小块大小33Cache的替换算法1. 先进先出算法（FIFO）将最早调入Cache的字块替换出去。容易实现，开销小。2. 最近最少使用算法（LRU）需要计算字块的使用次数，开销大，但平均命中率比FIFO要高。3. 随机替换（RAND）34多级Cache 采用两级或更多级cache来提高命中率 将Cache分解为指令Cache和数据Cache35CACHE 接入系统的体系结构接入系统的体系结构1. 侧接法：像入出设备似的连接到侧接法：像入出设备似的连接到 总线上，优点是结构简单

16、，成本低，总线上，优点是结构简单，成本低， 缺点是不利于降低总线占用率缺点是不利于降低总线占用率。CPUMEMORYCACHEBus Master 1Bus Master 2总线总线36CACHE 接入系统的体系结构接入系统的体系结构2. 隔断法：把原来的总线打断为两段，隔断法：把原来的总线打断为两段， 使使 CACHE 处在两段之间，优点是有利处在两段之间，优点是有利于提高总线利用率，支持总线并发操作，于提高总线利用率，支持总线并发操作，缺点是结构复杂，成本较高。缺点是结构复杂，成本较高。CPUMEMORYCACHEBus Master 1Bus Master 2总线总线37改写主存储器的策

17、略改写主存储器的策略若 CPU 改写了 CACHE 一单元内容后且尚未改变主存相应单元内容，则出现数据不一致性。有两种解决办法：1.接下来直接改写主存单元内容（Write Through） 简便易行, 但可能带来系统运行效率不高的问题。需要写入缓冲存储器。2.拖后改写主存单元内容（Write Back）一直拖到有另外的设备要读该内容过时的主存单元时,则首先停止这一读操作，接下来改写主存内容，之后再起动已停下来的读操作。 矛盾是如何检查是否是读无效内存单元的操作，这是通过 监视地址总线完成的，记下无效单元地址用于比较。 控制复杂些，但可以提供更高的系统运行效率。38Pentium上的Cache

18、Intel的80386及更早的处理器芯片上并没有片上的高速缓冲存储器。 80486：引入一个8K字节的片上Cache，其块大小为16字节，采用的是四路组相连映象方式。 Pentium：芯片上已经有了两个8K字节的片上cache，一个用作指令缓存，另一个用作数据缓存。它们的块大小都为32字节，采用两路组相连的组织方式。3964位总线接口指令缓存（8 KB）指令分支预测预取缓冲器整型寄存器组数据缓存（8 KB）浮点算逻部件浮点寄存器组整型ALU整型ALU乘法器加法器除法器32位64位32位32位U流水线V流水线32位32位256位64位 Pentium结构简图40Pentium的数据缓存 数据缓存

19、由128组，每组两个cache块组成，从逻辑上可以看成是大小为4K字节的两“路”。 每个cache块都有20位的标记位和两位的状态位与其对应，标记位即存放在该cache块中的主存块的地址的高20位，两位状态位可以标记出4个不同的块状态。 替换算法采用的是最近最少使用法（LRU），所以对每组cache块还需要有1位的LRU位来表示CPU最近访问的是该组中的哪一块。 采用拖后写策略。 支持两级Cache。41Pentium Cache块的状态 修改态（M）：处于这个状态的cache块中的数据已经被修改过，和主存中对应的数据已不同，只能从cache中读到正确的数据。 独占态（E）：处于本状态的cache块的数据和主存中对应的数据块内容相同，而且在其它cache中没有副本。 共享态（S）：处于本状态的cache块的数据和主存中对应的数据块内容相同，而且可能在其它cache中有该块的副本。 非法态（I）：处于本状态的cache块中尚未装入数据。42两级Cache块的状态转换IL1:L2:SIEEMM读入数据读入数据第一次修改第二次修改多次修改访问主存第一次修改访问主存替换策略：S、E状态不需改写L243写主存顺序 L2监听到其它总线主设备写请求，