Cache Memory and Pipelining

1. Introduction – Memory Cache

1.1 Cache Memory

  • main memory用于储存程序和数据,容量较大但速度较慢,通常使用DRAM
  • cache memory是一种缓冲区,可以让电脑在lower DRAM speeds的情况下更高效的运行,容量较小但速度较快,通常使用SRAM
  • 对于需要多次访问的数据,高速缓存可以提高内存系统的整体性能

1.2 Memory Hierarchy

  1. Register - 位于CPU内部,容量最小速度最快
  2. L1 Cache - 离CPU核心最近,访问速度很快
  3. L2 Cache - 容量通常大于L1,但速度较慢
  4. Main memory - 容量更大,速度更慢
  5. Magnetic Disk - 容量大,速度最慢

2. Locality of Reference

2.1 Locality Principle of Reference

  • temporal locality(时间局限性):在短时间内程序很可能再次访问之前使用过的数据或指令
  • space locality(空间局限性):程序在访问某个内存地址后,很可能接着访问附近的内存地址

2.2 Locality and Cache Memory

  • 出于这种处理器在短时间内反复访问同一组内存位置的倾向:当首次需要某个信息项时,将其放入缓存(时间局限性),同时获取相邻地址处的整个数据块(空间局限性)

3. Cache Design

3.1 Cache Hit and Miss

  • 当data requested by CPU is available in cache时则判定为cache hit(缓存命中)/反之则cache miss(缓存未命中)

3.2 Elements of Cache Design

Cache Size

  • 在成本和性能之间寻找平衡,cache size太小虽然成本低但会导致命中率低;cache size大命中率高但成本高
  • 通常位于1K-512K words之间(words通常等于寄存器宽度,如32位处理器中1 word=32 bits=4 bytes)

Mapping Function

  • 决定了block如何映射到cache中
  • Direct Mapped: 每个main memory block只能映射到缓存中的固定位置
    • direct mapped会将内存地址分割为三段: tag,line/block和word/byte offset
    • 通常使用 i = j (mod m) 对line/block取模操作计算位置,其中i是缓存block number,j是主存block number,m是缓存的总块数
    • 但容易产生 conflict miss(两个数据块挤占同一个 cache 分区)
  • Fully Associative: 可以存入缓存的任意行,但CPU查找时必须比较所有的标签
  • Set Associative: 折中方案,将cache分为若干个set,每个set包含若干way,main memory block先通过地址映射到set中(direct)再自由存放(fully)
    • 使用m = v * k计算缓存总行数,v是block总数,k是way总数
    • 使用i = j (mod v),i是缓存set number,j是主存block number,v是block总数

Replacement Algorithms

  • 当缓存已满需要存放新的block时,必须决定替换掉哪一个旧block
  • Least Recently Used (LRU): 最常用且最有效的算法,替换掉缓存集中最长时间未被使用过的block
    • 2 way set associative: 每个set固定2 way,每条way带有有效位,当其中一条get referenced时候将其有效位设为1,同组另一条way的有效位设为0,替换时优先替换有效位为0的way
    • 4 way set associative: 每个set固定4 way,在cache directory entry中配置3位LRU状态位记录最近调用的3 way,替换最久没被使用的那一个
  • 除此之外还有FIFO(先进先出), LFU(最不经常使用),Random(随机)等

Read and Write Policies

Line Size

  • line size增大时能提高缓存命中率
  • 但当line size过大时,同样size的缓存所能容纳的line总数就会变少,引发更频繁的conflict从而降低效率

Number of Caches

  • single cache:结构简单实现简单,但指令处理单元和执行单元容易产生资源竞争
  • multiple caches:将缓存进行分离/分级,可以消除指令处理单元和执行单元对缓存的访问冲突

链接