计算机组成原理第四章存储器

Size: px

Start display at page:

Download "计算机组成原理第四章存储器"

亢计
5 years ago
Views:

1 计算机组成原理第 5 章存储系统 -Cache llxx@ustc.edu.cn

2 本章内容高速缓冲存储器 Cache- 存储器映射读写操作替换算法相联存储器 COD5 5.3,5.4,5.8,5.9,5.12

3 问题为什么需要 Cache? 性能结构 Cache 有效性的理论基础局部性影响 Cache 命中率的因素 Cache 的读写操作过程 Cache 的基本结构和映射机制 Cache 的替换策略

4 问题的提出 (1) 主存速度始终跟不上 CPU(25MHz 的之后 ) 的发展 100MHz 的 Pentium 处理器平均 10ns 就执行一条指令, 而 DRAM 的典型访问时间是 60~120ns 流水线 : 单周期访存

5 问题的提出 (2) 结构冲突总线占用 :CPU 和 I/O 争抢访问主存减少访存访存冲突 : 指令预取与数据读写

6 程序访问的局部性原理时间局部性 : 最近的访问项 ( 指令 / 数据 ) 很可能在不久的将来再次被访问 ( 往往会引起对最近使用区域的集中访问 ) 空间局部性 : 一个进程访问的各项其地址彼此很近 ( 往往会访问在存储器空间的同一区域 ) for i := 0 to 10 do A[i] := 0;

7 命中不命中命中率 Cache 命中 (hit) CPU 欲访问的数据已在缓存中, 即可直接访问 Cache Cache 不命中 (miss, 失配, 缺失 ) CPU 欲访问的数据不在 Cache 内, 此时需将该数所在的主存整个子块一次调入 Cache 中 CPU 被阻塞 (blocking), 等待数据调入命中率 (Hit rate) CPU 要访问的信息已在 Cache 内的比率通常用命中率来衡量 Cache 的效率不命中率 (Miss rate)

8 Cache 结构 CPU 高速缓存控制器数据 CACHE 地址数据主存 Burst 模式字传送块传送 CPU Cache 主存

9 Cache Line/Main Memory Structure Main memory - 2 n words - 2 n /K blocks Cache has C lines of K words each Cache < Memory Tag to identifies block

control bits 有效位 (Valid): 访问效率数据是否有效 : 无效数据 :cold start/process

10 Cache Line Structure Cache Line = tag + block( K words ) + control bits Tag: to identifies block,= 块号? control bits 有效位 (Valid): 访问效率数据是否有效 : 无效数据 :cold start/process migration/first reference 写操作的使无效法 (Invalidated) 重写位 (Dirty): 行置换算法数据是否修改? 计数位 (Count): 行置换算法, 访问频度替换选择标识

11 Cache 基本结构参数块 ( 行 ) 大小字节命中时间 1 2 时钟周期 ( 常规为 1) 失配时间时钟周期 ( 访问时间 ) (6 60 时钟周期 ) ( 传送时间 ) (2 40 时钟周期 ) 失配率 0.5% 10% Cache 容量 1KB 1MB

12 Cache 效率容量和块长是影响 Cache 效率的重要因素 Cache 容量越大, 命中率越高当 Cahce 容量达到一定值时, 命中率不会因容量的增大而明显提高 Cache 容量大, 成本增加

13 Cache 容量块 ( 行 ) 长命中率 H 命中率 1 容量大容量小 BC 块大小

14 例设 Cache 的速度是主存的 5 倍, 命中率为 95%, 则采用 Cache 后性能提升多少? 系统平均访问时间 =0.95*t+0.05*5t=1.5t 性能提升 =5t/1.5t=3.33 倍

15 Cache 的读操作 CPU 开始 CPU 发出访存地址 MEM Cache Y 命中? N Cache 满? Y N 访问 Cache 取出信息送 CPU 访问主存取出信息送 CPU 将新的主存块调入 Cache 中执行替换算法腾出空位结束

16 写操作流程图? 命中, 不命中? 何时写 MEM? 一致性问题? 图 5-31

17 写操作 : in single CPU system CPU CPU CPU a' cache 100 a' cache 550 a' cache 100 not coherent b' 200 memory b' 200 memory not coherent b' 200 memory a 100 a 100 a 100 b 200 b 200 b 440 I/O I/O I/O 1) CPU writes to a 2) IO writes b

Cache 的写操作命中写回法 (Write-back): 执行写操作时, 信息只写入 Cache, 置 Dirty 位 ; 当 Cache 块被替换时, 将该块内容写回主存, 然后再调入新页写直达法 (Write-through Store-though) 每次写入 Cache 的同时, 也写入主存使无效法 (Invalidated) 信息只写入主存, 同时将相应的 Cache 块

18 Cache 的写操作命中写回法 (Write-back): 执行写操作时, 信息只写入 Cache, 置 Dirty 位 ; 当 Cache 块被替换时, 将该块内容写回主存, 然后再调入新页写直达法 (Write-through Store-though) 每次写入 Cache 的同时, 也写入主存使无效法 (Invalidated) 信息只写入主存, 同时将相应的 Cache 块 Valid 位置 0 影响读操作不命中 : 阻塞式, 非阻塞式写分配 (write allocate): 读入后再写 MIPS 采用写不分配 (no write allocate,write around): 只写主存哪些策略可组合? 性能写回法的开销是在块替换时的回写时间写直达法在每次写入时, 都要附加一个比写 Cache 长得多的写主存时间 cache 与 mem 的一致性 : 写直达法一致性保持的要好一些

19 Cache 的基本结构主存地址查找 Cache 地址

20 Cache 存储体地址映象变换机构替换机构 Cache 存储体以块为单位和主存交换信息 Cache 访存的优先级最高地址映射变换机构实现主存块号和 Cache 块号之间的转换三种方式 : 全相联映射直接映射组相联映射替换机构 Cache 内容已满时, 无法接受来自主存块的信息, 需由 Cache 内的替换机构按一定的替换算法来确定从 Cache 内移出某个块写回主存

21 主存与 Cache 的单元编址模式主存块号字块 0 主存储器 m 位 n 位 b 位标记 Cache 字块 0 字块 1 主存块号 M 块块内字地址 B 个字字块 1 字块 2 c -1 字块 2 m -1 如何判断是否命中? c 位块号 C 块 b 位块内字地址 B 个字

22 1. 全相联映像 m=t+c 位标记标记标记 cache 第 0 块第 1 块第 2 c -1 块主存第 0 块第 1 块第 2 m - 1 块主存地址主存字块号块内字地址 m=t+c 位 b 位 Cache 标记位多, 比较位数长 (m 位 ) 比较次数多 (m 次 : 全部 tag), 多个比较器

23 1. 全相联映像 ( 续 )

B A B 3 3 2 2 1 A 1 B 0 A 0 F A =B F A <B F A >B F A =B F A B3 A3 B2 A2 F <B A 7485(2) B 1

24 数值比较器? 1 位 2 位 B 3 F A A 3 B =B 2 F 7485 A A 2 B <B 1 F A A 1 0 I I >B A B A I A A 0 >B <B =B B A B A B A 1 B 0 A 0 F A =B F A <B F A >B F A =B F A B3 A3 B2 A2 F <B A 7485(2) B 1 A 1 >BI A I A I A B A 0 0 >B <B =B F A =B B 2 F A F <B A 7485(1) 3 A3 B A B A B >B 0 I A I A I A A 0 >B <B =B B 4 A 7 A7 B6 A 6 B5 A5 B 4 B 3 A 3 B 2 B A2 1 A1 B 0 A 0

25 全相联 Cache 的结构 address tag CAM data RAM mux 比较 tag, 选行, 选字 CAM 同时完成比较, 选行 hit data

26 Associative Memory Structure 每行需要一个比较器! 26

27 2. 直接映象 : 主存按 Cache 大小分段 Cache 字块数为 :C=2 c 主存字块数为 :M=2 m 映射关系式 :i=j mod C 或 i=j mod 2 c 缓存块号 i 主存块号 j 0 0,C,,2 m -C 1 1, C+1,,2 m -C+1 C-1 C-1,2C-1,,2 m -1 Cache 字块 0 字块 1 字块 2 c -1 主存地址主存段号 Cache 行号块内字地址 m=t+c 位 b 位主存储器字块 0 字块 1 字块 2 c -1 字块 2 c 字块 2 c +1 字块 2 c+1-1 字块 2 c+1 字块 2 m -1

28 2. 直接映象 ( 续 ) 如果连续访问 26 和 18?

29 2. 直接映象命中比较过程主存分段, 段大小 =Cache 大小段内块号与 Cache 行号 (Cache 字块地址 c) 一一对应根据 c 位找到对应的 cache 块 ( 按 c 位 index) 主存字块标记 t 为主存的段号比较 t 位与 tag( 只需比较一次 )!

30 块容量 2B,cache 容量 4B, 主存容量 12B 主存地址 4 位, 其中 b=1,c=1,t=2 设访存地址为 0001( 内容为 BB), 命中否? c 0 1 t t AA BB CC DD t t c b 由 m 中的 c 位找到对应的 cache 块, 比较其 t 位与 tag, 判断是否命中! AA BB CC DD t t

31 直接映射 cache 体的结构 ( 数据通路 ) tag 为主存的段号只需比较一次!

32 DLX 直接映射控制器实现 CPU<->Cache 接口阻塞式 Cache:miss 时指令 stall, 先换入, 再读写 Cache line 位置唯一 : 读写 miss 时都需要替换 ( 脏要写回 ) 读命中 : 不命中 : 换入 ( 脏 : 先写后读 Clean: 直接读入 ) 再读写 : 采用 Writeback using write allocate 策略命中, 写回 : 写 cache, 置 dirty 位不命中, 写分配 : 换入 ( 同上 ) 再写 X

33 a Directmapped Cache Controller COD 图 5-40 Moore 机? 阻塞式 :miss 时指令 stall 先换入, 再读写 Ready: 一次读写完成写操作 Writeback using write allocate 可优化拆分 CompTag 状态增加 WriteBuf, 存脏块

34 Cache 实现? 数据通路 + 控制器

35 FIGURE

36 系统接口 CPU <-> Cache 1bit Read or Write signal 1bit Valid signal, a cache operation? 32bit address 32bit data from processor to cache 32bit data from cache to processor 1bit Ready signal, saying the cache operation is complete MEM <-> Cache 1bit Read or Write signal 1bit Valid signal, a memory operation? 32bit address 128bit data from cache to memory 128bit data from memory to cache 1bit Ready signal, saying the memory operation is complete CPU<->MEM? 阻塞式 :CPU 不直接访问 MEM?

37 直接映象特点优点 : 实现简单只需利用主存地址的某些位直接判断, 就可确定所需字块是否在缓存中缺点 : 冲突, 效率低因为每个主存块固定地对应某个缓存块 ( 有 2 t 个主存字块对应同一个 Cache 字块 ), 如果这 2 t 个字块中有两个或两个以上的主存字块要调入 Cache, 必然会发生冲突

38 指令流水线阻塞式 Cache:stall Cache miss 时, 处理器被阻塞等待 CPU 只能访问 cache, 不能直接访问 MEM? 流水线指令 cache 缺失时 PC 4 通知主存执行一次读操作, 等待主存访问完成写 cache 项, 设置有效位重新取指流水线数据 cache 缺失时类似 I$

39 3. 组相联映象 (2 way-set-associated) Cache 分组, 主存分段, 段大小 = 组数 r = 组内块数 -1 Tag = 段号 r = 0? 直 r = c? 全主存储器 Cache(r=1) 字块 0 字块 1 标记字块 0 第 0 组标记字块 1 标记字块 2 第 1 组字块 2 c-r -1 标记字块 3 字块 2 c-r 字块 2 c-r +1 标记字块 2 c -2 第 2 c-r -1 组标记字块 2 c -1 段主存地址主存子块标记组地址子块内地址 s=t+r 位 q=c-r 位 b 位 m 位字块 2 c-r+1 字块 2 m -1

40 3. 组相联映象 ( 续 ) 原理 : 把 Cache 分为 Q(=2 q ) 组, 每组有 R(=2 r ) 块, 且 i=j mod Q 其中,i 为缓存的组号,j 为主存的块号在主存块和 Cache 的组之间, 为直接映象关系 ; 主存块可以映射到对应组内的任何一块, 为全相联映象的关系相联度,degree of associativity r: 一组的块数 ( 路数 ) r=0, 直接相联 ;r=c, 全相联

41 Ex1:2 路组相联 cache( 仅一行!) 内存大小?Cache 大小? 一行一组, 一组 2 路, 一路多字需要比较所有 (2 个 )tag N way:n 个比较器段号组 / 行号字地址

42 Ex2:4-way set associative Cache COD 图 5-18 一行一组一组 4 路 ( 块 ) 一路一字定位 set 比较 tag 选路选字合二为一字地址未用图 5-18 块大小, 组大小,Cache 大小, 内存段大小, 内存大小?

43 N-way Set Associative Cache 实现 : 例一行一组, 一组多路, 一路多字定位 set, 比较 tag, 选 way, 选 word Parallel tag and data array access pipeline 访问 tag 与访问 data 并行, 即 tag 比较与选路并行控制器? Antonio Gonzalez, Processor Microarchitecture_ An Implementation Perspective,2010

44 Disadvantages of Set Associative Cache N-way Set Associative Cache vs. Direct Mapped Cache N comparators vs. 1 Extra MUX delay for the data( 需 Way mux?) Data comes AFTER Hit/Miss decision and set selection 先选 way, 再选 word Direct Mapped Cache Cache Block is available BEFORE Hit/Miss( 无需 Way mux) Full Associative Cache CAM 完成比较 tag 和选 line, 再选 word address tag CAM data RAM mux hit data

45 例 1: 某 PC 主存容量分 2048 块, 每块 512B,Cache 容量 8KB, 分为 16 块, 每块 512B 用直接映象时, 主存应被分几段?Cache 标记几位? 用全相联映象,Cache 标记几位? 用组相联映象,Cache 每组 2 块 ( 即 : 两路组相联 ), 主存应划分为几段? 每段几块?Cache 标记几位? 段号组 / 行号路 / 块号字 / 位地址

46 例 2: 设有一个 cache 的容量为 2K 字, 每个块为 16 字, 求 (1) 该 cache 可容纳多少个块? (2) 如果主存的容量是 256K 字, 则有多少个块? (3) 主存的地址有多少位?cache 地址有多少位? (4) 在直接映像方式下, 主存中的第 i 块映像到 cache 中哪一个块中? (5) 进行地址映像时, 存储器的地址分成哪几段? 各段分别有多少位解 :(1) cache 中有 2048/16=128 个块 (2) 主存有 256K/16=16384 个块 (3) 主存容量为 256K=2 18 字, 字地址有 18 位 cache 容量为 2K=2 11 字, 字地址为 11 位 (4) 在直接映像方式下, 主存中的第 i 块映像到 cache 中第 i mod 128 个块中 (5) 区号 7 位, 块号为 7 位, 块内字地址为 4 位区号块号块内地址 4

47 映象方式比较 Fully Associative mapping Direct mapping 2 ways Set-Associative mapping

48 Tag 访问冲突开销 Tag 访问过程 N-way Set? 全块号比较所有 tag, 选 line, 选 word X-way Set 直段号定位 line(index 块号 ), 比较 tag, 选 word One-way Set 组段号定位 set(index 组号 ), 比较 N 个 tag, 选 way, 选 word N-way Set

49 映象方式比较 : 命中率 4 路以上效果不显著

50 替换以块为单位全相连 : 任意块组相联 : 某行, 任意路直接映射 : 某行

51 替换算法随机法基于局部性原理最优替换算法 (OPT): 未来最不可能使用者置换最长时间中不会被使用的页 : 预知工作集 (work sets) FIFO: 实现方便, 但不能正确反映程序的局部性最先进入的字块也可能是目前经常要用的字块 LRU, 最少近期使用, 最近最久未使用计时法 ( 绝对 ): 替换计时最长的 cache line 计数法 ( 近似 ): 替换计数最大的 cache line 两位计数一位计数 :NRU( 最近未使用 ), 多用!» 组计数, 路计数堆栈法开销 : 具体实现比 FIFO 复杂

52 FIFO 替换算法

53 颠簸现象访问顺序地址块号块分配情况操作状态调进调进调进调进替换替换替换替换先进先出替换方式下的 cache 内容颠簸情况

54 近期最少使用算法 LRU 例 : 选最近 4 次访问期间最少使用 Cache 块作为被替换的块访问顺序地址块号块分配情况 * * * * 操作状态调进调进命中调进调进替换替换替换 * 表示将要被替换者计数法实现 : 各块的 LRU 位变化?

55 例 : 设程序有 5 个信息块,Cache 空间为 3 块, 地址流为 : P1, P2, P1, P5, P5, P1, P3, P4, P3, P4 给出 FIFO LRU 两种页面替换算法对这 3 块 Cache 的使用情况, 包括调入替换和命中等

56 时间 t 实际地址流 P1 P2 P1 P5 P4 P1 P3 P4 P2 P4 命中次数 * 4 4 4* 4* 2 2 先进先出算法 * * 4 (FIFO 算法 ) 5 5 5* * 调入调入命中调入替换替换替换命中替换替换 * 2 2 最近最少使用算法 2 2 2* 4 4 4* (LRU 算法 ) 5 5* 5* 3 3 3* 3* 调入调入命中调入替换命中替换命中替换命中 * 3* 3* 3 3 最优替换算法 * (OPT 算法 ) 5* 调入调入命中调入替换命中替换命中命中命中三种页面替换算法对同一个页地址流的调度过程 2 次 4 次 5 次

57 LRU stack 算法 stack distance 访问某 line 时其在栈中的位置第一次访问时 = 替换哪一行? histogram 局部性

Stack distance profiles:histogram Stack distance of an access in a cache set the position of the line in the LRU stack when this line is accessed ( 定义 : 访问此 line 时它在 LRU 栈中的位置 ) = number of distinct

58 Stack distance profiles:histogram Stack distance of an access in a cache set the position of the line in the LRU stack when this line is accessed ( 定义 : 访问此 line 时它在 LRU 栈中的位置 ) = number of distinct cache lines accessed since previous access to the same line( 访问同一 line 的间隔次数 ) Stack distance profile (histogram) of a cache set counts (frequencies) of accesses depending on their stack distance( 各距离的总数 ) Stack distance

59 Pentium 处理器框图指令 Cache(8KB) 分支预测 256 位 64 位总线接口预取指令缓冲区 U 管道 V 管道整数 ALU 整数 ALU 64 位浮点单元寄存器组位整数寄存器组乘法器加法器除法器数据 Cache(8KB)

60 Pentium 处理器的片内 Cache 两路组相连 : 共 128 组, 每路 8 个双字 ( 4X8=32B) 采用写回策略, 可动态重构支持写直达 LRU: 组计数, 路随机两条专用指令 : 清除或回写 Cache 状态位 :4 种状态, 在 Cache 一致性协议 (MESI) 中使用

61 Cache 对系统性能的影响

62 Cache Misses:4 种 (COD 为 3C ) Compulsory( 必然 ) cold start process migration first reference Cold fact of life: not a whole lot you can do about it Note: If you are going to run billions of instruction, Compulsory Misses are insignificant Capacity Cache cannot contain all blocks access by the program Solution: increase cache size Conflict (collision): Multiple memory locations mapped to the same cache location Solution 1: increase cache size Solution 2: increase associativity Coherence (Invalidation): other process (e.g., I/O) updates memory

63 多级 Cache 与哈佛结构两层存储结构的存储访问时间 H 为 Cache 命中率,T1 和 T2 分别为两层存储器的访问时间, 则系统访问时间 Ts Ts = T1 H + (1 - H) (T1 + T2)

64 多级 Cache 的影响 L1 Cache 容量几乎对 IPC 没有影响? L2 影响很大

65 多线程共享 Cache 的效果运行于不同处理器核, 但共享 L2 Cache 不同线程组合

66 提高 Cache 性能 :Write Buffer

67 提高 Cache 性能 :Victim Cache 对于 RISC 处理器, 缺失时损失 100 多个周期 Victim Cache: 介于 L1 Cache 和下一级存储器之间 L1 Cache 采用直接相连, 较大 Victim Cache 采用全相连, 较小, 存放由于失效而被替换出的块含有 4 个块的缺失 cache 可以使一个 4KB 的直接映像数据 cache 的冲突失效减少 20~90%

Cache Effects Cache affinity : 冷热预热尽可能多的对已读取的数据进行操作, 最大限度的发挥时间局部性 ; 注意循环 : 大部分计算和访存都发生在这里按照数据对象在存储器中的存放顺序读取数据, 从而最大限度的发挥空间局部性 ; Suppose storing

68 Cache Effects Cache affinity : 冷热预热尽可能多的对已读取的数据进行操作, 最大限度的发挥时间局部性 ; 注意循环 : 大部分计算和访存都发生在这里按照数据对象在存储器中的存放顺序读取数据, 从而最大限度的发挥空间局部性 ; Suppose storing multidimensional arrays in linear memory a program accesses the array one row at a time. How about column major? That would result in 16 cache misses 注意 :cache 的容量为一行!

69 基于 Cache 的代码优化循环交换 (Loop Interchange) 原程序 (column major) a[100][5000]=...// 初始化 for(j=0; j<5000; j=j+1) { for(i=0; i<100; i=i+1) { a[i][j] = 2 * a[i][j]; 每次都不命中 } } 改进 (row major) a[100][5000]=...// 初始化 for(i=0; i<100; i=i+1) { for(j=0; j<5000; j=j+1) { a[i][j] = 2 * a[i][j]; 可连续命中若干次 [cache 行大小 ] } } 循环合并 (Loop fusion) 循环分块 (Blocking) Cache-oblivious algorithm: 与 cache 结构无关的算法 llxx@ustc.edu.cn 69/62

70 Intel Processor the CPUID Instruction

71 小结 Cache 有效性 Cache 效率和局部性的度量指标? Cache miss 的原因? 发挥 Cache 的作用 : 利用局部性 Cache 的 Side effect 一致性 : 如何使 Cache 与主存内容保持一致单 CPU, 多 CPU,DMA 实时性 : 访存时间的确定性 Cache 组织结构, 读写过程, 映射机制, 替换策略为何需要不同的映射模式? 全相连 :Tag= 块号, 多次比较, 可使用 CAM 直接映射 :Tag= 段号, 按 line 数分段, 定位到 line, 一个比较器 N-way set: Tag= 段号, 按组数分段, 定位到组,N 个比较器三种映射方式各自需要哪种置换算法? 编程实现 LRU? 作业 :5.2.1~3,5.3.1,5.8.1~2

72 72/94

计算机组成原理第 5 章存储系统 Cache

计算机组成原理第 5 章存储系统 Cache 计算机组成原理第 5 章存储系统 Cache llxx@ustc.edu.cn 存储层次本章内容为什么需要 Cache? 性能结构 Cache 有效性的理论基础局部性影响 Cache 命中率的因素 Cache 的基本结构 Cache 的读写操作过程 Cache 一致性阻塞式 Cache Cache MEM 映射机制块放哪儿? Cache 控制器 Cache 的替换策略 Cache 性能分析

计算机组成原理 第四章 存储器

计算机组成原理第四章存储器