cs61c-lec2

Lec24 Caches I

Binary Prefix

• 2^34 = 8(2^4) gibi(2^3)

Lec25 Caches II

Direct Mapped Caches

• 在直接映射缓存中，内存的每一地址都对应缓存中的某个block

• Cache Location 0 can be occupied by data from: Memory location 0, 4, 8, …

  

Direct Mapped Caches with Tag

• 更改cache 的 block size = 2，使用Tag确定cache 中的某个block 对应memory 中的位置

• Tag = Cache#

  

TIO

• Index 确定行位置

• Offset 确定列位置

• Tag IO确定后剩余位数，确定内存地址

  

example

缓存对应内存位置 (TIO)

缓存术语

• cache hit

• cache miss

• cache miss, block replacement

• hit rate

• miss rate

• miss penalty

• hit time

  

Valid Bit

• 判断缓存中的条目是否有用的指标

  

• 16 KB Direct-Mapped Cache, 16B blocks -> 2^14 B Cache, 4*4Block

  

Lec 26 Cache III

Direct Mapped Caches 读取

• 读取过程 16KB of data, direct-mapped, 4 word blocks

  

• address : 0x00000014

• 转换为 TIO (Tag, Index, Offset)

  

• 读取 0x00000014

  • 按照 IVTO 的顺序
  • 首先 Index 确定 行
  • 其次 Valid 确定 cache 此位置的条目是否有效，
    • 无效，正常进行
    • 有效，比较Tag，相同时，cache hit
  • Valid 无效 或者 Tag 不同时(cache miss)，从内存中读取Block 大小的数据，就是一行数据，而不仅仅是一个字
  • 根据offset 返回数据
  

直接映射缓存硬件实现

• address 的 Tag 与 Cache 的 Tag 比较，同时 Index Valid AND 比较结果，1 -> hit
• Cache 的 4 Block 通过 Mux (Block offset) 选择输出

Write-Back 处理 缓存中内存内容更新

• Wirte-through
  • 同时更新 内存 和 缓存
• Write-back
  • 更新缓存中的Block
  • 内存中的数据可以保持“陈旧”
  • 添加 “Dirty bit” 指标确认缓存中的数据是否改变
  • 当Block 被替换时需要更新缓存到内存
  • 操作系统在有I/O 时会提前刷新缓存到内存

更大的Block size

• Benefits
  • 空间局部性：如果我们访问一个给定的字，我们很可能尽快访问其他附近的字
  • 对连续的数组访问友好
• Drawbacks
  • 更大的Block size 导致 更大的 miss penalty
    • 每次miss，都要fecth 更多的数据到内存中
  • 一定的cache size 下，更大的 block size 导致 更少的blocks，导致miss rate high
    • 只有很少的block 导致缓存存不下什么东西，读取经常miss 经常刷新
    • ping pong effect

3 Cache Misses

Compulsory Misses 强制性失误

• 由于Cache cold 时无有效内容导致的必然的misses

Conflict Misses 冲突性失误

• 两个不同的内存条目映射到了相同的缓存地址

Capacity Misses 容量不足

• 容量不足导致的Misses 主要见于全关联缓存，接下来详述

Fully Associated Caches 全关联缓存

• 不设Index -> block 可以去cache 的任意行

• hardware

• Benefits
  • 没有conflict misses
• Drawbacks
  • 每个条目都需要硬件比较器：如果缓存中有 64KB 数据和 4B 条目，则需要 16K 比较器：infeasible