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

Size: px

Start display at page:

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

施卜
4 years ago
Views:

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

2 存储层次

3 本章内容为什么需要 Cache? 性能结构 Cache 有效性的理论基础局部性影响 Cache 命中率的因素 Cache 的基本结构 Cache 的读写操作过程 Cache 一致性阻塞式 Cache Cache MEM 映射机制块放哪儿? Cache 控制器 Cache 的替换策略 Cache 性能分析主要见体系结构课 Cache Coherence 见体系结构课 the write policy (how the processor writes data to the cache so that main memory eventually gets updated); the mapping function (the link between a block's address in memory and its location in the cache); the replacement algorithm (the method used to figure out which block to remove from the cache in order to free up a line). COD4 5.2, 5.3, 5.5, 5.7, 5.9 COD5 5.3, 5.4, 5.8, 5.9, 5.12

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

4 问题的提出 (1) 主存速度始终跟不上 CPU(25MHz 的之后 ) 的发展 100MHz 的 Pentium 处理器平均 10ns 就执行一条指令, 而 DRAM 的典型访问时间是 60~120ns 流水线 : 单周期访存 Improvement (compared to year 0) 16x 14x 12x 10x 8x 6x 4x 2x 1x J. Rabaey, BWRC Processor (M MIPS) Hard Disk (capacity) Memory (capacity) Battery (energy stored) Time (years)

5 Cache 对系统性能的影响

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

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

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

9 Cache 结构 CPU 高速缓存控制器地址 CACHE 数据主存 Burst 模式

10 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

11 Division of Memory into Blocks

Cache Line Structure Cache Line = tag + block(

:cold start/process migration/first reference

12 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) 重写位 (overwrite,dirty): 行置换算法数据是否修改? 计数位 (Count): 行置换算法, 访问频度替换选择标识

13 例 :Cache 基本结构参数块 ( 行 ) 大小字节命中时间 1 2 时钟周期 ( 常规为 1) 失配时间时钟周期 ( 访问时间 ) (6 60 时钟周期 ) ( 传送时间 ) (2 40 时钟周期 ) 失配率 0.5% 10% Cache 容量 Cache line size match the width of the DRAM simplified the design. 1KB 1MB

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

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

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

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

18 Cache miss: 阻塞式 (stall 多个周期?)

19 Cache miss: 非阻塞式

20 写操作 : 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

!! 写回法 (Write back) 命中 : 只写 Cache,, 置 Dirty 位 ; 替换时再写回 MEM 缺失 : 写分配 (write allocate): 读入后再写 MIPS 采用写不分配 (no

21 write policy 写透法 (Write through Store though): 写直达命中 : 同时写入 Cache 和 MEM 写缓冲 (write buffer): 写 MEM 需要 100clk cycles 缺失 : 写分配 (write allocate): 读入后再写 MIPS 采用写不分配 (no write allocate,write around): 只写主存!!! 写回法 (Write back) 命中 : 只写 Cache,, 置 Dirty 位 ; 替换时再写回 MEM 缺失 : 写分配 (write allocate): 读入后再写 MIPS 采用写不分配 (no write allocate,write around): 只写主存!!! 写缓冲 (write buffer): 使无效法 (Invalidated): 多处理器信息只写入主存, 同时将相应的 Cache 块 Valid 位置 0 影响读操作

22 写操作 Write buffers 写透法写回法命中, 不命中? 何时写 MEM? 一致性问题? 流程图?

23 地址映射 : 主存块放哪儿? 主存块号字块 0 主存储器 m 位 n 位 b 位标记 Cache 字块 0 字块 1 主存块号 M 块块内字地址 B 个字字块 1 字块 2 c 1 字块 2 m 1 c 位块号 C 块 b 位块内字地址 B 个字如何判断是否命中? Cache line size:match the width of the DRAM simplified the design.

24 1. 全相联映射 : 字块位置任意 m=t+c 位标记标记标记主存 cache 第 0 块第 1 块第 0 块第 1 块第 2 c -1 块第 2 m - 1 块主存地址主存字块号块内字地址 m=t+c 位 b 位 Cache 标记位多, 比较位数长 (m 位 ) 比较次数多 ( 最坏 m 次 ), 或 c 个比较器 (CAM)

25 1. 全相联映像 ( 续 )

26 全相联映射数据访问过程比较 tag, 选行, 选字

A>B A<B I A=B A 0 B A B A B 3 3 2 2 1 A 1 B 0 A 0 F A=B F

F A>B A 1 I I I B A 0 A>B A<B A=B 0 F A=B B 2 F A<B 7485(1)

27 数值比较器? 1 位 2 位 B F F F A=B A<B A>B A3 B2 A2 B1 A1 B 0 I I A>B A<B I A=B A 0 B A B A B A 1 B 0 A 0 F A=B F A<B F A>B 7485:4 位, 级联 F A=B F A<B 7485(2) B3 A3 B2 A2 B 1 F A>B A 1 I I I B A 0 A>B A<B A=B 0 F A=B B 2 F A<B 7485(1) F 3 A3 B A B A 2 A>B 1 1 B 0 I I I A A>B A<B A=B B 4 A 7 A7 B6 A6 B5 A5 B 4 B 3 A 3 B 2 B A2 1 A1 B 0 A 0

28 全相联 Cache 的结构 address tag CAM data RAM mux 比较 tag, 选行, 选字内容访问的存储器 CAM: 完成比较, 选行 hit data

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

30 Associative Memory Structure 01xx 输入寄存器 0011 屏蔽寄存器匹配结果 0111 输出寄存器

31 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

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

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

34 例

35 Cache 实现?(COD4 5.7 & 5.9) 数据通路 + 控制器

36 A Simple Cache Direct mapped cache Write back using write allocate Block size is 4 words (16 bytes or 128 bits) Cache size is 16 KB, so it holds 1024 blocks 32 bit byte addresses includes a valid bit and dirty bit per block the fields of an address: Cache index is 10 bits Block offset is 4 bits Tag size is 32 (10 + 4) or 18 bits

37 Hit 输出时间 vs. Data 读出时间? FIGURE

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

39 DLX 直接映射控制器实现 CPU< >Cache 接口阻塞式 Cache:miss 时指令 stall Cache line 位置唯一 : 读写 miss 时都要替换 ( 脏要写回 ) 读命中 : 直接读入不命中 : 分配式换入再读 ( 脏 : 写回 Clean: 直接读入 ) 写 :Write back using write allocate 命中, 写回 : 写 cache, 置 dirty 位不命中, 写分配 : 换入 ( 同读操作 ) 再写

40 a Direct mapped Cache Controller 阻塞式 miss 时指令 stall 命中 CompTag 中完成读写? miss 分配 : 先换入, 再读写每次 miss 都需要替换 Write back using write allocate MEM Ready: 读写完成, 握手 MEM controller 可优化拆分 CompTag 状态增加 WriteBuf, 存脏块 Idle 必须? 与 IF 或 MEM 同步? 写透? COD4 图 5 34,Moore 机?

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

42 3. 组相联映象 (2 way set associated) Cache 分组, 主存分段, 段大小 = 组数 r = 组内块数 -1 相联度 Tag = 段号 r = 0? c 组, 直 r = c? 1 组, 全主存储器 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

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

44 Ex1:2 路组相联 cache

45 Ex2:2 路组相联 cache( 一组两行!) 内存大小?Cache 大小? 一组 2 路, 一路 4 data 需要比较所有 (2 个 )tag N way:n 个比较器段号组号字地址

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

47 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

48 N way Set Associative Cache 控制器?

) 先选 way, 再选 word:data comes AFTER Hit/Miss decision and set selection Direct Mapped Cache Cache

49 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?) 先选 way, 再选 word:data comes AFTER Hit/Miss decision and set selection 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

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

51 例 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

52 映象方式比较 Fully Associative mapping Direct mapping 1 ways Set Associative mapping 2 ways Set Associative mapping

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

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

55 替换以块 (line) 为单位全相连 : 任意行组相联 : 固定组, 任意路 ( 行 ) 直接映射 : 固定行

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

57 FIFO 替换算法

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

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

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

61 时间 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 次

62 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

63 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

64 Deeper Pipelines: MIPS R4000

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

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

67 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

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

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

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

71 提高 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

72 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 的容量为一行!

73 基于 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 73/62

74 Timing Anomaly:WCET a situation where the local worst case does not entail the global worst case Scheduling Anomaly Speculation Anomaly Cache Timing Anomalies

75 Intel Processor the CPUID Instruction

76 小结 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

77 77/94

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

计算机组成原理第四章存储器计算机组成原理第 5 章存储系统 -Cache llxx@ustc.edu.cn 本章内容高速缓冲存储器 Cache- 存储器映射读写操作替换算法相联存储器 COD5 5.3,5.4,5.8,5.9,5.12 问题为什么需要 Cache? 性能结构 Cache 有效性的理论基础局部性影响 Cache 命中率的因素 Cache 的读写操作过程 Cache 的基本结构和映射机制 Cache

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

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