2014年4月30日 (三) 12:33的最后版本

[编辑] 1 缘起

受首席启发，补充点 cache 背景。再乱弹一下 Page Coloring

[编辑] 2 概述

Cache 是用来对内存数据的缓存。CPU 要访问的数据在Cache中有缓存，称为“命中” (Hit)，反之则称为“缺失” (Miss)

CPU 访问它的速度介于寄存器与内存之间（数量级的差别）。实现 Cache 的花费介于寄存器与内存之间。

现在 CPU 的 Cache 又被细分了几层，常见的有 L1 Cache, L2 Cache, L3 Cache，其读写延迟依次增加，实现的成本依次降低。

现代系统采用从 Register —> L1 Cache —> L2 Cache —> L3 Cache —> Memory —> Mass storage的层次结构，是为解决性能与价格矛盾所采用的折中设计。

引入 Cache 的理论基础是程序局部性原理，包括时间局部性和空间局部性。即最近被CPU访问的数据，短期内 CPU 还要访问（时间）；被 CPU 访问的数据附近的数据，CPU 短期内还要访问（空间）。因此如果将刚刚访问过的数据缓存在 Cache中，那下次访问时，可以直接从Cache中取，其速度可以得到数量级的提高。

[编辑] 3 结构

[编辑] 3.1 Cache 行

Cache 以行大小(Line size)为单位分成若干个行。行 (Line) 是 Cache 的数据存储和管理单元。一个典型的 Cache 行结构为：

其由 Tag 域、Status 域和数据域组成，

Tag 域存放该行数据对应地址的高位。CPU 在索引后，用相应地址与组内所有行的 Tag 相比较，以之区分具体的行。

数据域能容纳的字节数是为行大小 (Line Size)，其为 Cache 与内存之间数据交换的单位。

Status 域则为一些控制位信息（如Valid, Lock 以及Parity check 位等等），不同的Cache 类型，不同的 Cache 实现 Status 域稍有不同，具体的可以参考相应 CPU 手册。

[编辑] 3.2 相联方式

[编辑] 3.2.1 组相联

通俗地讲就是 Cache 行的分组，比如 4 路组相联，就是 4 行一组，4 行一组。。。。。。

比如 32KB 的 4 路组相联 Cache，行大小为 16Bytes 的话，他就有 32*1024/(16 * 4)= 512 组

CPU 访问组相联 Cache 时，就先用地址索引到组，然后组内同时匹配 Tag，进行路选。一个典型的组相联 Cache 如下：

内存逻辑上也按 Cache 行大小分块，按地址由低向高，依次编号。因此 Cache 与内存就会有个映射问题，如：第四个内存行中的数据被CPU访问时，该行将缓存于 Cache 中的哪一行？

组相联的 Cache 是先索引组，其规则为：

 Cache 组号 = 内存行号 % Cache 总组数

对于上图这个只有 2 个组的 Cache，假设其行大小为 16Bytes，这个组索引的过程，实际上就是用地址的第 5 位(ADDR[4]) 索引的过程，0 就在第一组，1 就在第二组。地址的低 4 位用于行内索引数据 (ADDR[3:0])

尔后，内存行可以映射到该组内的任意行上。缓存数据时，有空占空，如组内所有行被占用，则使用替换算法(LRU, Random, FIFO, LFU)替换掉一行。

[编辑] 3.2.2 直接相联

略. 或可参阅 The MIPS Cache Architecture 的相关部分

[编辑] 3.2.3 全相联

略. 或可参阅 The MIPS Cache Architecture 的相关部分

[编辑] 4 组相联工作方式

K 路组相联 Cache 的通常工作方式是：先用物理地址或虚拟地址索引组，然后用物理地址 (PA) 或虚拟地址 (VA) 同时与组内K 行之 Tag 域同时匹配，有匹配则为命中 (Hit)，尔后将命中的行中相应的字传给 Register。

以上述 32KB ，4 路组相联，行大小为 16Bytes 的 Cache 为例，正常工作时其对地址的划分如下所示：

Addr[12:4] 用来索引组，9 bit 可索引 512 组Addr[3:0] 用来行内索引字节，2^4 = 16 Bytes

VA 索引，PA 匹配 Cache 之工作方式图：

[编辑] 5 乱弹

在 OS 层面上，我们还有分页的概念，物理内存被分为若干个 Page Frame，其大小以 4KB 始。对 4KB 页大小的系统，其地址的低 12 位被用来索引页内数据

若系统采用 4KB 的 PAGE_SIZE，则第一个 Page Frame 总是会被索引到 cache 的前 256 组，第二个 Page Frame会被索引到 cache 的后 256 组，第三个又会到 cache 的前 256 组。。。。。。（给在前 256 的涂红色，给后 256 的涂黑色） 倘若系统在分别 PF 的时候，大多数的都跑到前 256 组去了，那就杯具了。在频繁换页的系统中，Cache的路数总是一定，用完了组内的行，系统就会复用一些行，原来的数据也就被替换，再访问时，就是 cache miss，性能就下来。那如何让系统在 “OS层面上物理页面（Page）的分配能够比较均匀的落在CPU层面上的SET中“？

通俗地说，就是让 OS 在分配页面的时候，让红色的页和黑色的页一样多。这个应该就是 Page Coloring

用颜色位更形式化地说：

作为一个理解的便利，请各位看官看看地址的组索引位和行内索引位所表示的空间大小是多少？ 2^13 ＝ 8KB，这个值正是 Cache 一路 (Way Array)的大小： 32KB/4 = 8KB (Way_Size)

因此拿到一个 Cache 在判断系统的 Color 位时，可以借助一个 Way Array 的概念，一路 Cache 的大小就是地址用来索引的低位空间，相当于用地址的低位访问 Cache 的一路内部存储

当 Way_Size > PAGE_SIZE 时，即 log2(Way_Size) > log2(PAGE_SIZE)， 则用于索引一路 Cache 的地址低位较用于页内偏移的低位多了 log2(Way_Size) – log2(PAGE_SIZE)，为了分析的方便，往往将这个多出的位称为颜色位 (color bit)。对于上述的 Cache，若系统采用 4KB 的 PAGE_SIZE，则Addr[12] 即为颜色位。则 OS 在分配页时，保证每种颜色的页一样多即可。如：Addr[13:12] 为颜色位的情形，00, 01, 10, 11 一样多即可。

若 log2(Way_Size) <= log2(PAGE_SIZE)，则数据可以很均衡地进入 Cache 没有谈论的必要的，但可以作为另外一个思路，即：提高系统的 Page Size

[编辑] 6 摘要

Way_Size ＝ Cache_Size / Ways

当 log2(Way_Size) > log2(PAGE_SIZE) 时，系统具有“颜色位”，其影响为：

1. 用 VA 索引，PA 匹配的 Cache，会存在 Cache alias 问题

2. 用 PA 索引，PA 匹配的 Cache，可以榨取更高的 Cache 命中率；方法可以用 Page Coloring，或者可以提高PAGE_SIZE以消除颜色位。

个人觉得在可能的前提下，提高 PAGE SIZE 比较靠谱，大页的影响，除了在 Cache 上外，在 RISC 的 CPU 上，还能提高 TLB 的命中效率