Cache地址映射

理解Cache地址映射之前补充一些基础知识，Cache的地址映射和MMU（内存管理单元）和TLB Cache（转译查找缓存）中的映射是有区别的。Cache、TLB Cache、MMU在CPU中结构如图1所示，图1展现的是Cortex A9 Processor内部结构，采用的指令和数据总线分开的哈佛结构。CPU访问内部存储和外部存储，以及各种外设空间在硬件层面上看都是物理地址（硬件总线），然后为了满足多进程脆弱的软件系统提出了虚拟地址，虚拟地址是针对应用程序所提出的概念，MMU负责虚拟地址到物理地址的映射工作，从虚拟地址到物理地址的转换过程可知：页表存储在内存中，使用一级页表进行地址转换时，每次读/写数据需要访问两次内存，第一次访问一级页表获得物理地址，第二次才是真正的读/写数据；使用两级页表时，每次读/写数据需要访问三次内存，访问两次页表（一级页表和二级页表）获得物理地址，第三次才是真正的读/写数据,由于这种机制速率很慢，才提出TLB Cache用于存储近期用到的页表条目（段/大页/小页/极小页描述符。TLB Cache是一个内存管理单元用于改进虚拟地址到物理地址转换速度的高速缓存，位于MMU中，本文章不深入分析MMU和TLB。Cache映射是硬件层面物理块与物理块之间建立的联系。

图 1

Cache的容量一般都很小，即使是最大的三级Cache（L3）也只有20MB～30MB。而当今内存的容量都是以GB作为单位，CPU对存储器的访问，通常是一次读写一个字单元。当CPU访Cache不命中时，需将存储在主存中的字单元连同其后若干个字一同调入Cache中，之所以这样做（write-back策略才会有这种机制），是为了使其后的访存能在Cache中命中。因此，主存和Cache之间一次交换的数据单位应该是一个数据块（以前文章中提到的cache line，一般大小为64 Byte）。数据块的大小是固定的，由若干个字组成，且主存和Cache的数据块大小是相同的。

从Cache-主存模型来看，一方面既要使CPU的访存速度接近于访Cache的速度，另一方面为用户程序提供的运行空间应保持为主存容量大小的存储空间。在采Cache-主存层次的系统中，Cache对用户程序而言是透明的，也就是说，用户程序可以不需要知道Cache的存在。因此，CPU每次访存时，依然和未使用Cache的情况一样，给出的是一个主存地址。但在Cache-主存层次中，CPU首先访问的是Cache，并不是主存。为此，需要一种机制将CPU的访主存地址转换成访Cache地址。而主存地址与Cache地址之间的转换是与主存块与Cache块之间的映射关系紧密联系的。如何把内存中的内容存放到Cache中去，这就需要一个映射算法和一个分块机制。

分块机制就是说，Cache和内存以块为单位进行数据交换，块的大小通常以在内存的一个存储周期中能够访问到的数据长度为限。当今主流块的大小都是64字节，因此一个Cache line就是指 64 个字节大小的数据块。Cache容量模型如图 2所示，图中展现了data cache: 32-KB, 8-way set associative（每个组里有8行）,64-byte line size的cache容量模型。

图 2

映射算法是指把内存地址空间映射到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共有m块，主存共有n块，当主存的某一块j需调进Cache中时，它可以存入Cache的块0、块1、…、块i、… 或块m的任意一块上,如图3所示，区别在于cache和主存块的对应关系不一样。

图3

在Cache中，需要建立一个目录表，目录表的每个表项都有三部分组成：内存地址、Cache块号和一个有效位。当处理器需要访问某个内存地址时，首先通过该目录表查询是否该内容缓存在Cache中，具体过程如图4所示。当一个主存块调入Cache中时，会同时在一个存储主存块号和Cache块号映射表的相联存储器中进行登记。CPU访存时，主存的块地址A在Cache的相联存储器目录表中进行查询，如果找到等值的内存块地址，检查有效位是否有效，只有有效的情况下，才能通过Cache块号在Cache中找到缓存的内存，并且加上块内地址 B，找到相应数据，这时则称为Cache命中，处理器拿到数据返回；否则称为不命中，处理器则需要在内存中读取相应的数据。使用全关联型 Cache，块的冲突最小，Cache的利用率也高，但是需要一个访问速度很快的相联存储器。随着Cache容量的增加，其电路设计变得十分复杂，因此只有容量很小的Cache才会设计成全关联型。

图 4

直接关联型Cache是指主存中的一块内存只能映射到Cache的一个特定的块中，Cache的目录表只有两部分组成：区号和有效位。其查找过程如图5所示。首先，内存地址被分成三部分：区号A、块号B和块内地址C，在这里区号A和区号B其实是全关联型中主存地址A。根据区号A在目录表中找到完全相等的区号，并且在有效位有效的情况下，说明该数据在Cache中，然后通过内存地址的块号B获得在Cache中的块地址，加上块内地址C，最终找到数据。如果在目录表中找不到相等的区号，或者有效位无效的情况下，则说明该内容不在Cache中，需要到内存中读取。直接相联映射方式的优点 是比较电路最简单，但缺点是Cache块冲突率较高，从而降低了Cache的利用率。

图 5

以上两种方式各有优缺点，而且非常有趣的是，它们的优缺点正好相反，所以组关联型映射就出现了，组关联型映射是目前用的最多的映射方式。组关联型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中去。图 6以4路组关联型 Cache 为例介绍其在Cache中的查找过程。目录表由三部分组成，分别是“区号+块号”、Cache块号和有效位。当收到一个内存地址时，该地址被分成四部分：区号A、组号B、块号C和块内地址D。首先，根据组号 B 按地址查找到一组目录表项，在4 路组关联中，则有四个表项，每个表项都有可能存放该内存块；然后，根据区号A和块号C在该组表项中进行关联查找（即并行查找，为了提高效率），如果匹配且有效位有效，则表明该数据块缓存在 Cache 中，得到Cache块号，加上块内地址D，可以得到该内存地址在Cache中映射的地址，得到数据；如果没有找到匹配项或者有效位无效，则表示该内存块不在Cache中，需要处理器到内存中读取。

图 6