全相联 Cache查找过程 Data-in byte offset write b Aligner word select Tag 0 Data block o enable Tag 1 g Data block 1 enable Tag m-1 Data Block(m-1 enable byte offset*/ Aligner m-way associative Hit Data-out 2021/2/4 计算机体系结构
全相联Cache查找过程 2021/2/4 计算机体系结构 27
Example: 1 KB Direct Mapped Cache with 32 B Blocks ·对于容量为2N字节的 cache: 最高(32N位部分为 Cache Tag 最低M位为字节选择位(B| ock size=2M Block address 4 Cache Tag Example: 0x50 Cache Index Byte Select Ex: 0x01 Ex: Oxo Stored as part of the cache“ state” Valid bit Cache Tag Cache data Byte 31 Byte 1 Bytdo o 0x50 Byte 63 .. Byte 33 Byte 32 1 Byte 1023 BYte992|31 2021/2/4 计算机体系结构
Example: 1 KB Direct Mapped Cache with 32 B Blocks • 对于容量为 2 N 字节的cache: • 最高(32-N)位部分 为 Cache Tag • 最低M位为字节选择位 (Block Size = 2 M) 2021/2/4 计算机体系结构 28 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 Ⅴalid Cache Tag Cache data Cache data Cache tag Valid Cache block 1 Cache block o Adr tag Compare Sell Mux 0 Selo ompa LOR Cache block Hit 2021/2/4 计算机体系结构
Example: Set Associative Cache • N-way set associative: 每一个cache索引对应N个cache entries • 这N个cache项并行操作 • Example: Two-way set associative cache • Cache index 选择cache中的一组 • 这一组中的两块对应的Tags与输入的地址同时比较 • 根据比较结果选择数据 2021/2/4 计算机体系结构 29 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块的使用历史,反映程序的局部性较差,失效率较高 ·FIFO一选择最早调入的块 优点:简单 虽然利用了同一组中各块进入 Cache的顺序,但还是反映程序局部性不够,因为 最先进入的块,很可能是经常使用的块 最近最少使用法(LRU)( Least Recently Used 优点:较好的利用了程序的局部性,失效率较低 缺点:比较复杂,硬件实现较困难 2021/2/4 计算机体系结构
Q3：替换算法 • 主存中块数一般比cache中的块多，可能出现该块所对应的一组或一个Cache块已 全部被占用的情况，这时需强制腾出其中的某一块，以接纳新调入的块，替换哪 一块，这是替换算法要解决的问题： • 直接映象，因为只有一块，别无选择 • 组相联和全相联有多种选择 • 替换方法 • 随机法（Random)，随机选择一块替换 • 优点：简单，易于实现 • 缺点：没有考虑Cache块的使用历史，反映程序的局部性较差，失效率较高 • FIFO－选择最早调入的块 • 优点：简单 • 虽然利用了同一组中各块进入Cache的顺序，但还是反映程序局部性不够，因为 最先进入的块，很可能是经常使用的块 • 最近最少使用法（LRU) (Least Recently Used) • 优点：较好的利用了程序的局部性，失效率较低 • 缺点：比较复杂，硬件实现较困难 2021/2/4 计算机体系结构 30
LRU和 Random的比较(失效率) Associativity Two-way Four-way Eight-way Size LRU Random FIFo LRU Random FIFo LRU Random FIFo 16 KB 114. l17311551117 l15.l11331090 ll181104 64 KB 1034 104310391024 1023103.1997 10051003 256KB 922 92192592.1 92.1925921 921925 Data Cache misses per 1000 instructions comparing LRU, Random, FIFO replacement for several 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容量的加大, Random的失效率在降低 2021/2/4 计算机体系结构
LRU和Random的比较（失效率） • 观察结果（失效率） • 相联度高，失效率较低。 • Cache容量较大，失效率较低。 • LRU 在Cache容量较小时，失效率较低 • 随着Cache容量的加大，Random的失效率在降低 2021/2/4 计算机体系结构 31 Data Cache misses per 1000 instructions comparing LRU, Random, FIFO replacement for several 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)