Training

Size: px

Start display at page:

Download "Training"

庭宅寿
5 years ago
Views:

1 计算机组织与系统结构高速缓冲存储器系统 Cache System ( 第十八讲 ) 程旭

2 本讲提纲复习存储层次和 Cache 引论进一步考察 Cache 的操作 Cache 写入策略和替换策略 SPARCstation 20 的存储系统总结

3 存储系统的扩展图示处理器控制 Memory Memory 数据通路 Memory Memory Memory 速度最快最慢容量最小最大每位成本最高最低

4 容量访问时间成本 CPU 寄存器 100s Bytes <10s ns Cache K Bytes 10~100 ns $0.01~0.001/bit 主存 M Bytes 100ns-1us $0.01~0.001 磁盘 G Bytes 毫秒 10-3 ~10-4 美分磁带无限秒 ~ 分 10-6 存储层次的级别寄存器堆 Cache 存储器磁盘磁带指令操作数块 (Blocks) 页 (Pages) 文件 (Files) 分段传输单位程序 / 编译器 1-8 字节 Cache 控制字节操作系统 512-4K 字节较高级别较快用户 / 操作员 Mbytes 较大较低级别

5 局部性原理访问的可能性局部性原理程序在一定的时间段内通常只会访问地址空间较小的部分例如 10% 的代码将耗费 90% 的程序执行时间两种不同类型的局部性时间局部性 (Temporal Locality) 如果一个信息项正在被访问, 那么在近期她很可能还会被再次访问空间局部性 (Spatial Locality) 在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的 0 地址空间 2

6 存储层次工作原理在任何给定时间, 数据只会在相邻两级之间拷贝较高级 (Cache) 与处理器较近的层次 - 较小较快, 并且使用很昂贵的工艺实现较低级 ( 主存 ) 与处理器较远的层次 - 较大较慢, 并且使用较便宜的工艺实现数据块在两级存储层次中, 要么出现, 要么不出现的信息的最小单位至处理器来自处理器较高级存储器 (cache) X 块较低级存储器 ( 主存 ) Y 块

需要从较低层中的块中找回数据 (Y 块 ) 失效率 (Miss Rate) = 1 - ( 命中率 ) 失效损失 (Miss Penalty)

7 存储层次参数命中 (Hit) 数据在较高层的某一块中出现 ( 例如 X 块 ) 命中率 (Hit Rate) 在较高层发现存储访问的比率命中时间 (Hit Time) 访问在较高层命中数据的时间 RAM 访问时间 + 确定命中 / 失效的时间失效 (Miss) 需要从较低层中的块中找回数据 (Y 块 ) 失效率 (Miss Rate) = 1 - ( 命中率 ) 失效损失 (Miss Penalty) 替换较高层存储的一个数据块的时间 + 将该块交付给处理器的时间命中时间 << 失效损失至处理器来自处理器较高级存储器 (cache) X 块较低级存储器 ( 主存 ) Y 块

基本参数典型数值典型数值块 ( 行 ) 大小 4-128 字节命中时间 1-4 字节失效损失 8-32 周期 ( 访问时间

8 基本参数典型数值典型数值块 ( 行 ) 大小字节命中时间 1-4 字节失效损失 8-32 周期 ( 访问时间 ) (6-10 周期 ) ( 传输时间 ) (2-22 周期 ) 失效率 1% - 20% Cache 容量 1 KB KB

9 Cache 如何工作? 时间局部性 (Temporal Locality) 如果一个信息项正在被访问, 那么在近期她很可能还会被再次访问将最近被访问的信息项放在离处理器较近的地方空间局部性 (Spatial Locality) 在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的将包括临近存储字的数据块一起移动到较高层存储中至处理器来自处理器较高级存储器 (Cache) X 块较低级存储器 ( 主存 ) Y 块

10 最简单的 Cache 直接映射 Cache 主存地址 A B C D E F 主存 4 字节直接映射 Cache Cache 索引 (Index) 位置 0 可以被来自以下位置的数据占用主存位置 0 4 8,... 等等一般情况任何地址最低两位为 0 的主存位置地址 <10> cache 索引我们应该将哪一个放置在 cache 中? 我们如何知道到底哪一个在 cache 中呢?

11 Cache 标签 (Tag) 和 Cache 索引 (Index) 假设存储器字节地址为 32 位 2 N 字节的直接映射 cache - Cache 索引存储器地址的较低 N 位 31 - Cache 标签存储器地址的较高 (32 - N) 位 Cache 标签假设为 0x50 N Cache 索引假设为 0x03 0 有效位 Valid Bit 作为 cache 状态的一部分保存起来 0x50 2 N 字节的直接映射 cache 字节 0 字节 0 字节 0 字节字节 2 N -1 2 N - 1

12 Cache 访问示例开始 Cache 空访问 ( 失效 ) V 标签数据访问 ( 命中 ) 000 M [00001] 010 M [01010] 写 Tag & Set V 失效处理装载数据访问 ( 失效 ) 000 M [00001] 访问 ( 命中 ) 000 M [00001] 010 M [01010] 装载数据写 Tag & Set V 000 M [00001] 010 M [01010] 人生名言失败是成功之母义务失效 (Compulsory Misses) - ( 冷启失效 )

13 Cache 数据块的定义 Cache 块相同的 cache 标志所指明的 cache 数据进一步分析前面介绍的示例 4 字节直接映射 cache 块大小 = 1 Byte 可以利用时间局部性如果正在访问某一字节, 那么在最近的将来还可能再次访问这一字节不能利用空间局部性如果正在访问某一字节, 那么在最近的将来还可能访问这一字节邻近的字节为了利用空间局部性增加数据块的大小有效位 Cache 标签直接映射 Cache 数据字节 0 字节 1 字节 2 字节 3

14 示例 32B 数据块的 1KB 直接映射 Cache 对于 2 N 字节 cache 最高的 (32 - N) 位总是 Cache 标签最低的 M 位是字节选择 ( 块大小 = 2 M ) 31 9 有效位 Cache 标签示例 0x50 Cache 标签作为 Cache 状态的一部分存储 0x50 Cache 索引示例 0x01 Cache 数据 Byte 31 Byte 63 4 Byte 1 Byte 33 Byte 0 Byte 32 0 字节选择示例 0x Byte 1023 Byte

15 块大小的权衡一般而言, 数据块较大有利于利用空间局部性的优势, 但是较大的数据块较大的失效损失 - 需要较长的时间来填充数据块如果数据块的大小相对于 cache 大小而言太大了, 那么失效率也将增加平均访问时间等于命中时间 x (1 - 失效率 ) + 失效损失 x 失效率失效损失失效率开发空间局部性数据块较少弥补了时间局部性平均访问时间增加了失效损失和失效率块大小块大小块大小

16 另一个极端的示例有效位 Cache 标签 Cache 数据 Byte 3 Byte 2 Byte 1 Byte 0 0 Cache 大小 = 4 bytes 块大小 = 4 bytes cache 中只能有唯一一个数据块真如果正在访问一个信息项, 那么很可能在最近的将来还将访问该信息项但是, 通常却不会立即再次使用该信息项!!! 那么, 再次访问该信息项时, 仍然很可能会失效 - 继续向 cache 中装入数据, 但是在它们被再次使用之前会被强行排出 cache - cache 设计人员最害怕出现的事情乒乓现象冲突失效 (Conflict Misses) 是下述原因导致的失效不同的存储位置映射到同一 cache 索引 - 解决方案 1 增大 cache 容量 - 解决方案 2 对同一 Cache 索引可以有多个信息项

17 两路组相联 Cache 有效位 N 路组相联对每个 Cache 索引有 N 个数据块 (entries) N 个直接映射 cache 并行工作示例两路组相联 cache Cache 索引来选择 cache 中的某一组该组种的两个标签进行并行比较根据标签比较的结果来选择数据 Cache 标签 Cache 数据 Cache 块 0 Cache 索引 Cache 数据 Cache 块 0 Cache 标签有效位地址标签比较 Sel1 1 Mux 0 Sel0 比较或 Cache 块 Hit

18 组相联 Cache 缺点 N 路组相联 Cache 与直接映射 Cache N 个比较器与 1 个比较器在输出数据时, 增加了额外的多路选择延迟在判断命中 / 失效时候, 才可以得到数据在直接映射 Cache 中, Cache 块在命中 / 失效之前就可以得到可以先假设命中并继续执行, 如果以后发现失效再恢复有效位 Cache 标签 Cache 数据 Cache 块 0 Cache 索引 Cache 数据 Cache 块 0 Cache 标签有效位地址标签比较 Sel1 1 Mux 0 Sel0 比较或 Cache 块 Hit

19 另一个极端的示例全相联全相联 Cache -- 将组相联的思想推广到极限! 完全不要 Cache 索引并行地比较所有的 Cache 标签示例块大小 = 32 字节, 需要 N 个 27 位的比较器根据定义对于全相联 cache, 冲突失效 = 0 31 Cache 标签 (27 位长 ) 4 0 字节选择示例 0x01 X X X X X Cache 标签有效位 Cache 数据字节 31 字节 1 字节 0 字节 63 字节 33 字节 32

20 Cache 失效原因小结义务失效 (Compulsory cold start first reference) 第一次访问某一信息块人生名言失败是成功之母冲突失效 (Conflict collision) 多个存储器位置映射到同一 cache 位置解决方案 1 增加 cache 容量解决方案 2 增加相联度容量失效 (Capacity) Cache 并不能保存程序访问所需的所有数据块解决方案增加 cache 容量无效 (Invalidation) 其他进程 ( 例如, I/O) 修改存储器

21 Cache 失效原因问答直接映射 N 路组相联全相联 Cache 容量义务失效冲突失效容量失效无效失效大中小高中低高中无低中高相同相同相同注释如果我们运行上百万条的指令, 那么义务失效就微不足道了!

22 三种映射策略比较直接映射 Cache 每个存储器位置只能映射到为一一个 cache 位置在定位时, 不需要进行任何判断 - 当前的信息项替换掉 Cache 中该位置上的前一个信息项 N 路组相联 Cache 每个存储器位置可以选择 N 个 cache 位置之一全相联 Cache 每个 memory 位置可以存放在任何 cache 位置 N 路组相联或全相联 Cache 中的访问失效从存储器中取出新的信息块为给新块腾出空间, 替换出一个 cache 数据块于是, 就必须确定到底需要替换掉 Cache 中的哪个数据块!

23 Cache 块替换策略随机替换策略硬件随机选择一个 Cache 数据项替换出去最近最少使用策略 (Least Recently Used) 硬件纪录访问历史信息替换出离现在最长时间没有使用的数据项一种简单的伪 LRU 策略的实现假设有 64 个全相联的数据块替换指针硬件替换指针指向一个 cache 数据块每次对该数据块进行了一次访问, 就将该指针 - 移向下一个数据项否则不移动该指针数据块 0 数据块 1 数据块 63

24 Cache 写入策略写穿透与写返回 Cache 读操作比 cache 写操作更容易处理指令 cache 比数据 cache 更容易设计 Cache 写操作如何保证 Cache 和存储器中数据的一致性? 两种选择写返回 (Write Back) 只写入 Cache 当出现 Cache 失效某 Cache 数据块需要替换出 Cache 时, 才将该 Cache 块的数据回写到存储器中 - 对每个 Cache 数据块, 需要增加一个脏位 ( Dirty bit) - 极大地减小存储器的带宽需求 - 控制可能很复杂写穿透 (Write Through) 同时写入 cache 和存储器 - 什么!!! 这样可以吗? 这样, 存储器不是太慢了吗?

写缓冲器就像一个先进先出栈 (FIFO) 典型数据项的数目 4 可以很好地工作, 如果存储操作的频率 ( 写时间

25 写穿透的写缓冲器 Processor Cache DRAM Write Buffer 在 Cache 和存储器之间需要一个写缓冲器处理器将数据写入 cache 和写缓冲器存储器控制器将缓冲器中的内容写入存储器写缓冲器就像一个先进先出栈 (FIFO) 典型数据项的数目 4 可以很好地工作, 如果存储操作的频率 ( 写时间 ) << 1 / DRAM 写周期存储器设计人员最害怕的事情存储频率 ( 写时间 ) 1 / DRAM 写操作写缓冲器饱和

26 写缓冲器饱和 Processor Cache DRAM Write Buffer 存储操作频率 ( 写时间 ) 1 / DRAM 写周期时间如果这种情况持续很长时间 (CPU 周期时间太快和 / 或连续来了很多存储指令 ) - 无论设置了多大的写缓冲器, 它都有可能溢出 - CPU 时钟周期时间 <= DRAM 写周期时间对写缓冲器饱和的解决方案使用一个写返回 cache 安装一个第二级 (L2) cache Processor Cache L2 Cache DRAM Write Buffer

27 写分配与写不分配假设将一个 16 位数据写到存储器位置 0x0, 它产生了失效那么, 我们是否需要读取该块 ( 字节 ) 的其他数据? 是的写分配 (Write Allocate) 不是写不分配 ( Write Not Allocate) 31 Cache Tag Example 0x00 9 Cache Index Ex 0x00 4 Byte Select Ex 0x00 0 Valid Bit Cache Tag 0x00 Cache Data Byte 31 Byte 1 Byte 63 Byte 33 Byte 0 Byte Byte 1023 Byte

28 SB3 s V Bit SB2 s V Bit SB1 s V Bit SB0 s V Bit 什么是一个子块? 子块 (Sub-block) 一个数据块中具有自己的有效位的单位数据例如 1 KB 直接映射 Cache 32-B 数据块 8-B 子块 - 每个 cache 数据项将具有 32/8 = 4 个有效位写失效只引进该子块中的数据 Cache 标签 Cache 数据 B31 B24 Sub-block3 Sub-block2 Sub-block1 B7 B0 Sub-block Byte 1023 Byte

29 减少存储器传输时间 CPU CPU CPU Cache bus M mux cache bus M Cache bus M M M M 第一种解决方案高带宽 DRAM 例如页模式 DRAM SDRAM DDRRAM RAMbus 第二种解决方案存储器和 Cache 之间宽数据通路 Cost 第三种解决方案存储模块交叉访问

30 总结程序局部性原理在任何一段时间内, 程序都趋于访问较小的一段地址空间 - 时间局部性 (Temporal Locality) - 空间局部性 (Spatial Locality) 三种主要的 Cache 失效类型义务失效 (Compulsory Misses) 例如, 冷启失效冲突失效 (Conflict Misses) 增加 cache 容量和 / 或相联度最要命的现象颠簸现象! 容量失效 (Capacity Misses) 增加 cache 容量写入策略 (Write Policy) 写穿透 (Write Through) 需要一个写缓冲器要命的现象写缓冲器饱和! 写返回控制复杂

Training

Training 计算机组织与系统结构存储器系统 Memory System ( 第十七讲 ) 程旭易江芳 2012.12.19 本讲提纲存储系统引论存储系统 : 全貌存储工艺技术 : SRAM 和寄存器堆存储工艺技术 :DRAM 总结教学目标 : 已经掌握的内容计算机的五个基本部件处理器输入控制存储器数据通路输出本讲主题 : 存储系统 1980 1981 1982 1983 1984 1985