Q2(2/2)查找方法 原则:所有可能的标记并行查找, cache的速度至关重要 ,即并行查找 并行查找的方法 ·用相联存储器实现,按内容检索 用单体多字存储器和比较器实现 显然相联度N越大,实现查找的机制就越复杂,代价就越 高 无论直接映象还是组相联,查找时,只需比较tag, index 无需参加比较 计算机体系结构 Chapter52
计算机体系结构 Chapter5.21 Q2（2/2)查找方法 ▪ 原则：所有可能的标记并行查找，cache的速度至关重要 ，即并行查找 ▪ 并行查找的方法 • 用相联存储器实现，按内容检索 • 用单体多字存储器和比较器实现 ▪ 显然相联度 N越大，实现查找的机制就越复杂，代价就越 高 ▪ 无论直接映象还是组相联，查找时，只需比较 tag，index 无需参加比较
Example: 1 KB Direct Mapped Cache with 32 B Blocks 对于容量为2N字节的 cache: 最高(32N)位部分为 Cache Tag 最低M位为字节选择位( Block size=2M) Block address 31 4 Cache Tag Example: 0x50 Cache Index Byte Select Ex: OxO1 Ex: 0x00 Stored as part of the cache“ state” Ⅴ alid bit cache tag Cache data Byte 3 yte 1 Bytdo 0 0x50 Byte 63.. Byte 33 Bvte 32 1 Byte 1023 Byte992|31 计算机体系结构 Chapter522
计算机体系结构 Chapter5.22 Example: 1 KB Direct Mapped Cache with 32 B Blocks ▪ 对于容量为 2 N 字节的cache: • 最高(32-N)位部分 为 Cache Tag • 最低M位为字节选择位(Block Size = 2 M) Cache Index 0 1 2 3 : Cache Data Byte 0 31 4 0 : Cache Tag Example: 0x50 Ex: 0x01 0x50 Stored as part of the cache “state” Valid Bit : 31 Byte 31 Byte 1 : Byte 63 Byte 33 Byte 32 : Byte 1023 Byte 992 : Cache Tag Byte Select Ex: 0x00 9 Block address
Example: Set Associative Cache N-way set associative:每一个 cache索引对应N个 cache entries 这N个 cache项并行操作 Example: Two-way set associative cache Cache index选择 cache中的一组 这一组中的两块对应的Tags与输入的地址同时比较 根据比较结果选择数据 Cache Index Valid Cache tag Cache data Cache data Cache ta g Valid Cache block Cache block o Adr Ta Compare- Sell Mux 0 selo CI ompare OR Cache block 计算机体系结构 Chapter523
计算机体系结构 Chapter5.23 Example: Set Associative Cache ▪ N-way set associative: 每一个cache索引对应N个cache entries • 这N个cache项并行操作 ▪ Example: Two-way set associative cache • Cache index 选择cache中的一组 • 这一组中的两块对应的Tags与输入的地址同时比较 • 根据比较结果选择数据 Cache Data Cache Block 1 Valid Cache Tag : : : Cache Data Cache Block 0 Cache Tag Valid : : : Cache Index Mux 1 0 Sel1 Sel0 Cache Block Compare Adr Tag Compare OR Hit
Q3:替换算法 主存中块数一般比 cache中的块多,可能出现该块所对应的一组或一个 Cache 块已全部被占用的情况,这时需强制腾出其中的某一块,以接纳新调入的块 替换哪一块,这是替换算法要解决的问题: ·直接映象,因为只有一块,别无选择 ·组相联和全相联由多种选择 替换方法 ·随机法( Random),随机选择一块替换 优点:简单,易于实现 缺点:没有考虑 Cache块的使用历史,反映程序的局部性较差,失效率较高 F|FO一选择最早调入的块 优点:简单 虽然利用了同一组中各块进入 Cache的顺序,但还是反映程序局部性不够, 因为最先进入的块,很可能是经常使用的块 最近最少使用法( LRU Least Recent! 7 Used) 优点:较好的利用了程序的局部性,失效率较低 缺点:比较复杂,硬件实现较困难 计算机体系结构 Chapter524
计算机体系结构 Chapter5.24 Q3：替换算法 ▪ 主存中块数一般比cache中的块多，可能出现该块所对应的一组或一个Cache 块已全部被占用的情况，这时需强制腾出其中的某一块，以接纳新调入的块， 替换哪一块，这是替换算法要解决的问题： • 直接映象，因为只有一块，别无选择 • 组相联和全相联由多种选择 ▪ 替换方法 • 随机法（Random)，随机选择一块替换 - 优点：简单，易于实现 - 缺点：没有考虑Cache块的使用历史，反映程序的局部性较差，失效率较高 • FIFO－选择最早调入的块 - 优点：简单 - 虽然利用了同一组中各块进入Cache的顺序，但还是反映程序局部性不够， 因为最先进入的块，很可能是经常使用的块 • 最近最少使用法（LRU) (Least Recently Used) - 优点：较好的利用了程序的局部性，失效率较低 - 缺点：比较复杂，硬件实现较困难
LRU和 Random的比较(失效率) Associativity Two-way Four-way Eight-way Size LRU Random FIFo LRU Random FIFO LRU Random FIFO 16 KB l141 l1731155117 115111331090 lll81104 44 KB 1034 104310391024 1023103.1 097 100.51003 256KB 922 92.1 925 921 92192592.1 g2192.5 Data Cache misses per 1000 instructions comparing LRU, Random, FIFO replacement for serveral sizes and associativities These data were collected for a block size of 64 bytes for the alpha architecture using 10 SPEC2000 benchmarks. Five are from SPECint2000(gap, gcc, gzip, mcf and perl) and five are from SPECfp2000(applu, art, equake, lucas and swim) 观察结果(失效率) 相联度高,失效率较低。 · Cache容量较大,失效率较低。 LRU在 Cache容量较小时,失效率较低 随着 Cache容量的加大, Randon的失效率在降低 计算机体系结构 Chapter525
计算机体系结构 Chapter5.25 LRU和Random的比较（失效率） ▪ 观察结果（失效率） • 相联度高，失效率较低。 • Cache容量较大，失效率较低。 • LRU 在Cache容量较小时，失效率较低 • 随着Cache容量的加大，Random的失效率在降低 Data Cache misses per 1000 instructions comparing LRU, Random, FIFO replacement for serveral sizes and associativities. These data were collected for a block size of 64 bytes for the Alpha architecture using 10 SPEC2000 benchmarks. Five are from SPECint2000(gap, gcc, gzip, mcf and perl) and five are from SPECfp2000(applu, art, equake, lucas and swim)