1、主 存 与 Cache 的 地 址 映 射CPU 对存储器的访问，通常是一次读写一个字单元。当 CPU 访Cache 不命中时，需将存储在主存中的字单元连同其后若干个字一同调入Cache 中，之所以这样做，是为了使其后的访存能在 Cache 中命中。因此，主存和 Cache 之间一次交换的数据单位应该是一个数据块。数据块的大小是固定的，由若干个字组成，且主存和 Cache 的数据块大小是相同的。从 Cache-主存层次实现的目标看，一方面既要使 CPU 的访存速度接近于访 Cache 的速度，另一方面为用户程序提供的运行空间应保持为主存容量大小的存储空间。在采用 Cache-主存层次的系统中，
2、Cache 对用户程序而言是透明的，也就是说，用户程序可以不需要知道 Cache 的存在。因此，CPU 每次访存时，依然和未使用 Cache 的情况一样，给出的是一个主存地址。但在 Cache-主存层次中，CPU 首先访问的是 Cache，并不是主存。为此，需要一种机制将 CPU 的访主存地址转换成访 Cache 地址。而主存地址与 Cache 地址之间的转换是与主存块与 Cache 块之间的映射关系紧密联系的，也就是说，当 CPU 访 Cache 未命中时，需要将欲访问的字所在主存中的块调入 Cache 中，按什么样的策略调入，直接影响到主存地址与 Cache 地址的对应关系，这也就是本小节
3、要解决的主存与 Cache 的地址映射问题。主要有三种地址映射方式，分别为全相联映射、直接相联映射和组相联映射。1. 全相联映射全相联映射是指主存中任一块都可以映射到 Cache 中任一块的方式，也就是说，当主存中的一块需调入 Cache 时，可根据当时 Cache 的块占用或分配情况，选择一个块给主存块存储，所选的 Cache 块可以是 Cache 中的任意一块。例如，设 Cache 共有 2C 块，主存共有 2M 块，当主存的某一块 j 需调进 Cache 中时，它可以存入 Cache 的块 0、块 1、块 i、 或块 2C -1 的任意一块上。如图 4-28 所示。图 4-28 全相联映
4、射方式在全相联映射方式下，CPU 的访主存地址为如下形式：其中，M 为主存的块号，W 为块内的字号。而 CPU 访 Cache 的地址形式为：其中，C 为 Cache 的块号， W 为块内的字号。主存地址到 Cache 地址的转换是通过查找一个由相联存储器实现的块表来完成的，其形成过程如图 4-29 示。图 4-29 全相联映射的地址转换当一个主存块调入 Cache 中时，会同时在一个存储主存块号和 Cache块号映射表的相联存储器中进行登记。CPU 访存时，首先，根据主存地址中的主存块号 M 在相联存储器中查找 Cache 块号，若找到，则本次访Cache 命中，于是将对应的 Cache 块
5、号取出，并送访 Cache 地址的块号 C字段；紧接着将主存地址的块内字号 W 直接送 Cache 地址的块内字号 W字段，从而形成一个访 Cache 的地址；最后根据该地址完成对 Cache 单元的访问.全相联映射方式的优点是 Cache 的空间利用率高，但缺点是相联存储器庞大，比较电路复杂，因此只适合于小容量的 Cache 之用。 2. 直接相联映射直接相联映射方式是指主存的某块 j 只能映射到满足如下特定关系的Cache 块 i 中：ij mod 2C （4.2）图 4-30 直接相联映射方式上图中，主存的第 0、2 C、2 C1 、 块只能映射到 Cache 的第 0 块，主存的第 1
6、、2 C+1、2 C1 +1、 块只能映射到 Cache 的第 1 块， ，主存的第 2C-1、2 C1 -1、2 M-1 块只能映射到 Cache 的第 2C-1 块。在直接相联映射方式下，CPU 的访主存地址为如下形式：其中，T 为标志号，C 为 Cache 的块号，W 为块内的字号。在这里，原主存的块号 M 实际上被分成了两个字段：T 和 C，其中 C 用于指出主存的块可以映射的 Cache 的块。一般来讲，主存的块数是 Cache 的块数的整数倍，也就是说主存的块数 2M 和 Cache 的块数 2C 满足关系式：2M n2C在直接相联映射方式下，标志号 T 是随 Cache 的每个块
7、一起存储的，其地址转换过程如图 4-31 所示。图 4-31 直接相联映射的地址转换当一个主存块调入 Cache 中时，会同时将主存地址的 T 标志存入Cache 块的标志字段中。当 CPU 送来一个访存地址时，首先，根据该主存地址的 C 字段找到 Cache 的相应块，然后将该块标志字段中存放的标志与主存地址的 T 标志进行比较，若相符，说明主存的块目前已调入该Cache 块中，则命中，于是使用主存地址的 W 字段访问该 Cache 块的相应字单元；若不相符，则未命中，于是使用主存地址直接访主存。直接相联映射方式的优点是比较电路最简单，但缺点是 Cache 块冲突率较高，从而降低了 Cach
8、e 的利用率。由于主存的每一块只能映射到Cache 的一个特定块上，当主存的某块需调入 Cache 时，如果对应的Cache 特定块已被占用，而 Cache 中的其它块即使空闲，主存的块也只能通过替换的方式调入特定块的位置，不能放置到其它块的位置上。3. 组相联映射以上两种方式各有优缺点，而且非常有趣的是，它们的优缺点正好相反，也就是说，对于全相联映射方式来说为优点的恰是直接相联映射方式的缺点，而对于全相联映射方式来说为缺点的恰是直接相联映射方式的优点。那么，可否找到一种能较好地兼顾这两种方式的优点的映射方式呢？下面我们就来看看组相联映射方式 在这种方式下，将 Cache 分成 2u 组，每组
9、包含 2v 块。主存的块与 Cache 的组之间采用直接相联映射，而与组内的各块则采用全相联映射。也就是说，主存的某块只能映射到 Cache 的特定组中的任意一块。主存的某块 j 与 Cache 的组 k 之间满足如下关系：kj mod 2 u （4.3）设主存共有 2s2u 块（即 Ms+u），则它们的映射关系如下图 4-32示。图 4-32 组相联映射方式 图中，主存的块 0、2 u、2 u1 、(2 s-1)2u可以映射到 Cache 的第 0 组的任意一块，主存的块 1、2 u+1、2 u1 +1、(2 s-1)2u+1 可以映射到 Cache 的第 1 组的任意一块， ，主存的块 2
10、u-1、2 u1 -1、2 M-1 可以映射到Cache 的第 2u-1 组的任意一块。在组相联映射方式下，CPU 的访主存地址和访 Cache 地址分别为如下形式：其中，u 为 Cache 的组号， v 为组内的块号。 Cache 的块号 Cu+v，而主存的块号 Ms+u。也就是说，主存块地址的后 u 位指出了主存的这一块所能映射的 Cache 的组。 与全相联映射方式类似的是，在组相联映射方式下，主存地址到Cache 地址的转换也是通过查找一个由相联存储器实现的块表来完成的，其形成过程如图 4-33 所示。图 4-33 组相联映射的地址转换当一个主存块调入 Cache 中时，会同时将其主存
11、块地址的前 s 位写入一个由相联存储器实现的快表的对应 Cache 块项的 s 字段中。例如，设主存的某块调入 Cache 的第 1 组的第 2 块中，则在快表的组 1 第 3 项的 s 字段会登记下该主存块地址的前 s 位。CPU 访存时，首先，根据主存地址中的主存块号中的 u 字段找到快表的相应组，然后将该组的所有项的前 s 位同时与主存地址的 s 字段作比较，若相符，则说明主存块在 Cache 中，于是将 Cache 中该项的 v 字段取出，作为 Cache 地址的 v 字段，而 Cache 地址的 u、W 字段直接由主存地址的 u、W 字段形成，最后形成一个完整的访 Cache 地址。当然，若比较结果是没有相符项，则未命中，由主存地址直接访主存。其实，全相联映射和直接相联映射可以看成是组相联映射的两个极端情况。若 u0，vC，则 Cache 只包含 1 组，此即全相联映射方式；若uC， v0 ，则组内的块数等于 1，此即直接相联映射。在实际应用中，相联映射方式每组的块数一般取值较小，典型值为2、4、8、16 等，分别称为两路组相联、四路组相联等。这样一方面使得比较器的规模较小，实现较容易，例如两路组相联采用两路比较，四路组相联采用四路比较等；另一方面，Cache 每组增加的可映射块数可有效减少冲突，提高 Cache 访问的命中率。
