第1页：高速缓冲存储器
高速缓冲存储器
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现Cache的映射方式、替换算法与命中率相关问题。
第2页：内容提要：Cache的目的、基本原理
- Cache的目的
- 基本原理
- Cache的三种映射方式
- 提高Cache性能
第3页：CPU与DRAM性能比较
CPU与DRAM性能比较
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现动态存储器芯片的读写原理与刷新要求。
第4页：高速缓冲存储器
高速缓冲存储器
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现Cache的映射方式、替换算法与命中率相关问题。
第5页：这不是一个技术问题
这不是一个技术问题，而是一个经济问题
从技术上说，能制造出多高速度的CPU，就能制造出同样速度的存储器，只不过是我们是否愿意付出如此高的价格。有没有更好的办法？能否用廉价的高容量存储器实现相对的高速度呢？。
第6页：程序的局部性原理
程序的局部性原理
- 程序在一定的时间段内通常只访问较小的地址空间
- 两种局部性：–时间局部性
第7页：层次存储器系统
7层次存储器系统
- 使用高速缓冲存储器Cache来提高CPU对存储器的平均访问速度。
- 时间局部性：最近被访问的信息很可能还要被访问。–将最近被访问的信息项装入到Cache中。
- 空间局部性：最近被访问的信息临近的信息也可能被访问。–将最近被访问的信息项临近的信息一起装入到Cache中。
第8页：计算机总线
计算机总线
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现总线的概念、分类、仲裁与通讯方式。
第9页：要解决的主要问题1.地址之间的映射关系
要解决的主要问题1.地址之间的映射关系
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现Cache的映射方式、替换算法与命中率相关问题。
第10页：几个参数
- 块（Line）：数据交换的最小单位
- 命中（Hit）：在较高层次中发现要访问的内容
- 命中率（Hit Rate）：命中次数/访问次数
- 命中时间：访问在较高层次中数据的时间
- 失效（Miss）：需要在较低层次中访问块
- 失效率（Miss Rate）：1-命中率
- 失效损失（Miss Penalty）：替换较高层次数据块的时间+将该块交付给处理器的时间
- 命中时间<<失效损失
第11页：参数典型数值
参数典型数值
- 块大小：4~128Byte
- 命中时间：1~4周期
- 失效损失：–访问时间：6~10个周期
- 命中率：80%~99%
- Cache容量：1KB~256KB
第12页：全相联方式
全相联方式
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现主存储器的组成、读写过程与字位扩展方案。
第13页：全相连映射硬件实现举例
全相连映射硬件实现举例
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现Cache的映射方式、替换算法与命中率相关问题。
第14页：全相联方式的地址映射特点1.主存
全相联方式的地址映射特点1.主存的字块可以和Cache的任何字块对应，利用率高，方式灵活
2.标志位较长，比较电路的成本太高。如果主存空间有2m块，则标志位要有m位。
同时，如果Cache有n块，则需要有n个比较电路。使用成本太高。
第15页：直接映射方式
直接映射方式
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现Cache的映射方式、替换算法与命中率相关问题。
第16页：高速缓冲存储器
16Cache举例
- 8块cache
- 每块16字节
- “直接映射”:内存中的每个单元在Cache中只会有一个唯一的位置和它对应。0-1532-4716-31…128-143160-175144-159…
第17页：直接映射Cache举例
直接映射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-31…128-143160-175144-159…0-1516-3132-47XXX 128-143XXX 144-159
第18页：高速缓冲存储器
18Cache举例：续
- 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-31…128-143160-175144-159…0-1516-3132-47XXX 128-143XXX 144-159
第19页：直接映射Cache
直接映射Cache
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现Cache的映射方式、替换算法与命中率相关问题。
第20页：高速缓冲存储器
- 增加块大小可以更好地利用空间局部性直接映射Cache:硬件实现Address(showingbitpositions)1612ByteoffsetVTagDataHitData16324Kentries16bits128bitsMux323232232BlockoffsetIndexTag31161543210
第21页：直接映射方式的地址映射特点1.主存
直接映射方式的地址映射特点1.主存的字块只可以和固定的Cache字块对应，方式直接，利用率低。2.标志位较短，比较电路的成本低。
如果主存空间有2m块，Cache中字块有2c块，则标志位只要有m-c位。且仅需要比较一次。
利用率低，命中率低，效率较低。
第22页：两路组相联方式
两路组相联方式
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现主存储器的组成、读写过程与字位扩展方案。
第23页：两路组组相联方式
两路组组相联方式的地址映射特点1.前两种方式的折衷方案
组间为全相连，组内为直接映射。2.集中了两个方式的优点。
成本也不太高。是常用的方式。
第24页：组相连Cache访问举例
24组相连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
- Read location 0: Hit
- Read location 128: Hit
- Read location 4: Hit
- Read location 132: Hit0-1564-79…0-1516-3132-47128-143144-159
第25页：路组相连Cache实现
路组相连Cache实现
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现Cache的映射方式、替换算法与命中率相关问题。
第26页：种映射方式比较
三种映射方式比较
- 直接映射
- 主存中的一块只能映射到Cache中唯一的一个位置
- 定位时，不需要判断，只需替换
- 全相连映射
- N路组相连映射
- 全相连映射和N路组相连映射的失效处理
- 从主存中取出新块
- 为了腾出Cache空间，需要替换出一个Cache块
- 不唯一，则需要判断应替出哪块
第27页：提高Cache
提高Cache
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现Cache的映射方式、替换算法与命中率相关问题。
第28页：缺失的原因
28Cache缺失的原因
- 必然缺失（开机或进程切换）：首次访问数据块
- 世事总是有缺憾
- 注意：如果我们运行几百万条指令，有点必然缺失又何妨？
- 冲突缺失
- 多个memory块映射到同一cache块
- 解决办法1：增大cache容量
- 解决办法2：增加相连组数
- 容量冲突
- Cache无法装入程序需要访问的所有块
- 方案：增大cache容量
- 无效缺失：其它进程（如I/O）修改了主存
第29页：影响CACHE命中率
影响CACHE命中率
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现Cache的映射方式、替换算法与命中率相关问题。
第30页：高速缓冲存储器
高速缓冲存储器
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现Cache的映射方式、替换算法与命中率相关问题。
第31页：块大小和缺失率的关系
块大小和缺失率的关系
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现Cache的映射方式、替换算法与命中率相关问题。
第32页：块大小的权衡
32块大小的权衡
- 一般来说，数据块较大可以更好地利用空间局部性，但是：–数据块大意味着缺失损失的增大：
- 需要花费更长的时间来装入数据块
- 若块大小相对Cache总容量来说太大的话，命中率将降低
- Cache块数太少
- 一般来说，平均访问时间=命中时间x命中率+失效损失x缺失率缺失损失块大小缺失率利用空间局部性较少的数据块：弥补时间局部性平均访问时间增加了缺失损失和缺失率块大小块大小
第33页：高速缓冲存储器
33Cache的替换算法1.先进先出算法（FIFO）将最早调入Cache的字块替换出去
容易实现，开销小。2.最近最少使用算法（LRU）需要计算字块的使用次数，开销大，但平均命中率比FIFO要高。
3.随机替换（RAND）。
第34页：多级Cache
多级Cache
- 采用两级或更多级cache来提高命中率
- 将Cache分解为指令Cache和数据Cache
第35页：接入系统的体系结构1.侧接法
接入系统的体系结构1.侧接法
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现输入输出系统的作用、功能、组成与需要解决的主要问题。
第36页：接入系统的体系结构2.隔断法
接入系统的体系结构2.隔断法
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现总线的概念、分类、仲裁与通讯方式。
第37页：改写主存储器
改写主存储器的策略若CPU改写了CACHE一单元内容后且尚未改变主存相应单元内容，则出现数据不一致性。有两种解决办法：1.接下来直接改写主存单元内容（Write Through）简便易行,但可能带来系统运行效率不高的问题。
需要写入缓冲存储器。2.拖后改写主存单元内容（Write Back）一直拖到有另外的设备要读该内容过时的主存单元时,则首先停止这一读操作，接下来改写主存内容，之后再起动已停下来的读操作。
矛盾是如何检查是否是读无效内存单元的操作，这是通过监视地址总线完成的，记下无效单元地址用于比较。控制复杂些，但可以提供更高的系统运行效率。
第38页：上的Cache
38Pentium上的Cache
- Intel的80386及更早的处理器芯片上并没有片上的高速缓冲存储器。
- 80486：引入一个8K字节的片上Cache，其块大小为16字节，采用的是四路组相连映象方式。
- Pentium：芯片上已经有了两个8K字节的片上cache，一个用作指令缓存，另一个用作数据缓存。它们的块大小都为32字节，采用两路组相连的组织方式。
第39页：高速缓冲存储器
高速缓冲存储器
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现Cache的映射方式、替换算法与性能提升。
第40页：高速缓冲存储器
40Pentium的数据缓存
- 数据缓存由128组，每组两个cache块组成，从逻辑上可以看成是大小为4K字节的两“路”。
- 每个cache块都有20位的标记位和两位的状态位与其对应，标记位即存放在该cache块中的主存块的地址的高20位，两位状态位可以标记出4个不同的块状态。
- 替换算法采用的是最近最少使用法（LRU），所以对每组cache块还需要有1位的LRU位来表示CPU最近访问的是该组中的哪一块。
- 采用拖后写策略。
- 支持两级Cache。
第41页：块的状态
41Pentium Cache块的状态
- 修改态（M）：处于这个状态的cache块中的数据已经被修改过，和主存中对应的数据已不同，只能从cache中读到正确的数据。
- 独占态（E）：处于本状态的cache块的数据和主存中对应的数据块内容相同，而且在其它cache中没有副本。
- 共享态（S）：处于本状态的cache块的数据和主存中对应的数据块内容相同，而且可能在其它cache中有该块的副本。
- 非法态（I）：处于本状态的cache块中尚未装入数据。
第42页：两级Cache块的状态转换IL1
两级Cache块的状态转换IL1
本页为结构/流程示意图，图中标注的主要部件与信号如下，重点体现Cache的映射方式、替换算法与命中率相关问题。
第43页：写主存顺序
写主存顺序
- L2监听到其它总线主设备写请求，并要求该设备等待；
- L2将要被写的地址传给L1，如果L1中的数据在一次写之后有了新的修改（状态为M），则需要将L1中该块的数据写回到主存中。任何情况下，都将该块的状态标记为非法态（I）。
- 如果L1中的数据与L2相同，则无须L1将数据写回主存中，而只要L2把自己的块的内容写回即可。但还是要把该块的状态标记为非法态（I）。
- L2唤醒总线主设备，由它完成写操作。
第44页：高速缓冲存储器
44Cache
第45页：高速缓冲存储器
45Cache
第46页：局部性原理
46Cache
- 局部性原理：–任何时候，程序需要访问的只是相对较小的一些地址空间。
- 时间局部性
- 空间局部性
- 三类主要的Cache缺失原因：–无法避免的缺失：如：第一次装入
- 块冲突：增大Cache容量、改进组织方式避免不断的块冲突
- 容量冲突：增大Cache容量
- Cache设计
- 总容量、块大小、组织方式
- 替换算法
- 写策略（命中时）：写直达、拖后写
- 写策略（不命中时）：是否装入到Cache？
第47页：设计Cache
设计Cache
- 有关方案
- 方案优化
- 海量数据处理
- 指令数据平衡(I-cache, D-cache)
- 简单化常常就是优化关联度Cache容量块大小BadGoodLessMoreFactor AFactor B
