Cache地址映射和变换

这章的重点是：Cache和内存的 数据交换，关系Cache和内存的读写。

底层细节和术语

为了进行Cache和内存的数据交换，这里介绍一点底层细节和术语：

分块机制

这里的分“块”指的“块”也叫“CacheLine”，Cache和内存以块为单位进行数据交换，块的大小通常以在内存的一个存储周期中能够访问到的数据长度为限。

Note

(GPT) 术语：Cache Line (缓存行)

• 概念：缓存行是内存中基本单位/最小的数据单位，它可以被加载到缓存中。
• 包含内容：一个缓存行通常包含：
  • 实际的数据
  • 一些元数据（例如有效位、脏位、共享状态等）
• 大小：是最小数据单位。且其大小通常是固定的，并且因不同的处理器架构而异。常见的有：
  • 32字节： 较早的ARM、1990年~2000年早期的x86和PowerPC
  • 64字节： 较新的ARM和x86
  • 128字节： 较新的Power ISA机器
• 机制 - 整个加载以利用局部性原理：每次从主内存读取数据时，不仅仅是请求的特定字节会被加载，而是整个缓存行都会被加载到缓存中。
  这样做的目的是为了利用局部性原理（Locality Principle），即程序往往连续访问内存中的数据或在短时间内重复访问相同的数据。
• 机制 - 缓存行对齐以确保高效加载：数据在内存中的位置需要与缓存行边界对齐

Note

(GPT) 术语：Cache Entry (缓存条目)

• 概念：缓存条目是指缓存中用于存储数据的一个位置。

• 被组织方式：缓存可以按照多种方式组织缓存条目：

  • 直接映射（Direct Mapped）
  • 全相联（Fully Associative）
  • 组相联（Set Associative）

• 包含内容：每个缓存条目通常包括：

  • 数据部分（Data）
  • 标记部分（Tag）
  • 控制信息（如有效位、脏位等）

  另外。一个缓存条目可以包含一个或多个缓存行，具体取决于缓存的设计。

• 机制 - 替换策略：当缓存满了需要加载新数据时，会根据某种替换策略来决定哪个缓存条目将被替换掉，常见的策略有：

  • LRU（Least Recently Used 最近最少使用）
  • FIFO（First In First Out 先进先出
  • 等

映射算法

而映射算法是指把内存地址空间映射到Cache地址空间。

具体来说，就是把存放在内存中的内容按照某种规则装入到Cache中，并建立内存地址与Cache地址之间的对应关系。当内容已经装入到Cache之后，在实际运行过程中，当处理器需要访问这个数据块内容时，则需要把内存地址转换成Cache地址，从而在Cache中找到该数据块，最终返回给处理器。

三类Cache (粗)

三类Cache

根据Cache和内存之间的映射关系的不同，Cache可以分为三类：

• 第一类：全关联型 Cache（full associative cache）
• 第二类：直接关联型 Cache（direct mapped cache）
• 第三类：组关联型 Cache（N-ways associative cache）

提前总结、比较

共同点：

• 无论哪种都会在Cache中建立一个目录表，根据不同的映射方案，目录表内容不同

不同点：

	全关联型Cache	直接关联型Cache	组关联型Cache
目录表	内存地址 Cache块号 有效位	区号 _ 有效位	“区号+块号” Cache块号 有效位
映射数
优点	无块冲突，利用率高	实现简单，匹配快	(各取所长)
缺点	大容量导致电路设计复杂	Cache命中率低
选用	小容量Cache

全关联型Cache（full associative cache）

• 特点：全关联型Cache是指主存中的任何一块内存都可以映射到Cache中的任意一块位置上。

• 原理 - 目录表：三部分组成：

  • 内存地址
  • Cache块号
  • 有效位

• 原理 - 查找：

  当处理器需要访问某个内存地址时，首先通过该目录表查询是否该内容缓存在Cache中，具体过程如下图所示：

  

  首先，用内存的块地址A在Cache的目录表中进行查询，如果找到等值的内存块地址，检查有效位是否有效

  • 有效的情况下，能通过Cache块号在Cache中找到缓存的内存，并且加上块内地址B，找到相应数据，这时则称为Cache命中，处理器拿到数据返回；
  • 否则为Cache Miss，处理器则需要在内存中读取相应的数据。

• 优点：块的冲突最小（没有冲突），Cache的利用率也高，但是需要一个访问速度很快的相联存储器。

• 缺点：随着Cache容量的增加，其电路设计变得十分复杂

• 场景：因此只有容量很小的Cache才会设计成全关联型的（如一些英特尔处理器中的TLB Cache）

直接关联型Cache（direct mapped cache）

• 特点：直接关联型Cache是指主存中的一块内存只能映射到Cache的一个特定的块中。

  假设一个Cache中总共存在N个Cache line，那么内存被分成N等分，其中每一等分对应一个Cache line。举个简单的例子，假设Cache的大小是2K，而一个Cache line的大小是64B，那么就一共有 $2K/64B=32个$ Cache line，那么对应我们的这些内存：

  $$\begin{align} 第~1块~地址：& 0\sim63\\ 第33块~地址：& 64*32\sim64*33-1\\ 第(N*32+1)块~地址：& 64*(N-1)\sim 64*N-1\\ \end{align}$$

  都被映射到Cache第一块中；

  同理，第2块，第34块，以及第（N*32+2）块都被映射到Cache第二块中；可以依次类推其他内存块。

• 原理 - 目录表：两部分组成：

  • 区号

  • 有效位

• 原理 - 查找：

  其查找过程如下图所示。

  首先，内存地址被分成三部分：区号A、块号B和块内地址C。根据区号A在目录表中找到完全相等的区号，

  • 并且在有效位有效的情况下，说明该数据Cache命中，然后通过内存地址的块号B获得在Cache中的块地址，加上块内地址C，最终找到数据。
  • 如果在目录表中找不到相等的区号，或者有效位无效的情况下，则说明该内容Cache Miss，需要到内存中读取。

  图2-6　直接相联Cache查找过程

  

  可以看出，直接关联是一种很“死”的映射方法，当映射到同一个Cache块的多个内存块同时需要缓存在Cache中时，只有一个内存块能够缓存，其他块需要被“淘汰”掉。

• 优点：其实现方式最为简单，匹配速度也最快。

• 缺点：但直接关联型命中率是最低的

组关联型Cache（N-ways associative cache）

• 特点

  组关联型Cache是目前Cache中用的比较广泛的一种方式，是前两种Cache的折中形式。

  在这种方式下，内存被分为很多组，一个组的大小为多个Cache line的大小，一个组映射到对应的多个连续的Cache line，也就是一个Cache组，并且该组内的任意一块可以映射到对应Cache组的任意一个。可以看出：

  • 在组外，其采用直接关联型Cache的映射方式
  • 在组内，其采用全关联型Cache的映射方式。

  假设有一个4路组关联型Cache，其大小为1M，一个Cache line的大小为64B，那么总共有16K个Cache line，但是在4路组关联的情况下，我们并不是简简单单拥有16K个Cache line，而是拥有了4K个组，每个组有4个Cache line。一个内存单元可以缓存到它所对应的组中的任意一个Cache line中去。

• 原理 - 目录表：三部分组成：

  • “区号+块号”
  • Cache块号
  • 有效位

• 原理 - 查找

  图2-7以4路组关联型Cache为例介绍其在Cache中的查找过程。当收到一个内存地址时，该地址被分成四部分：区号A、组号B、块号C和块内地址D。首先，根据组号B按地址查找到一组目录表项，在4路组关联中，则有四个表项，每个表项都有可能存放该内存块；然后，根据区号A和块号C在该组表项中进行关联查找（即并行查找，为了提高效率），如果匹配且有效位有效，则表明该数据块缓存在Cache中，得到Cache块号，加上块内地址D，可以得到该内存地址在Cache中映射的地址，得到数据；如果没有找到匹配项或者有效位无效，则表示该内存块不在Cache中，需要处理器到内存中读取。

  图2-7　4路组关联型Cache查找过程

  

  实际上，直接关联型Cache和全关联型Cache只是组关联型Cache的特殊情况。

  • 当组内Cache Line数目为1时，即为直接关联型Cache。
  • 而当组内Cache Line数目和Cache大小相等时，即整个Cache只有一个组，这成为全关联型Cache。