1.1 Cache不可不察也

在现代处理器中，CacheHierarchy一般由多级组成，处于CPU和主存储器之间，形成了一个层次结构，这个层次结构日趋复杂。Intel甚至放弃使用阿拉伯字母对Cache的各级层次编号，而直接使用LLC(Last-Level Cache)，MLC(Medium-Level Cache)这样的术语。

变化的称呼表明了一个事实，Cache层次结构在整个处理器系统中愈发重要，也越发复杂。Sandy Bridge处理器大约使用了十亿个晶体管，在其正中不再是传统的CPU，是Ring Bus包裹着的最后一级Cache [1]。

处理器的制作过程异常复杂。在人类历史上，其设计难度只有古埃及的金字塔可以与其媲美，即便是胡夫金字塔也只使用了230万个巨石，几十万个劳工而已。现代CPU的所耗的资源何止这些数字。在处理器这座金字塔中，Cache层次结构是最基本的框架。

几千年前，孙子曾经说过，“兵者，国之大事，死生之地，存亡之道，不可不察也”。对于有志于站在金字塔顶峰的，即便目标只有半山腰的系统程序员，也是Cache，不可不察也。在Intel的Values->Discipline中有一句话“Pay attention to detail”。

但是不要忘记Devil is in thedetail。准备深入理解Cache层次结构的读者需要时刻提醒自己真正了解什么是细节之后，才会重视细节，才能够避免因为忽视细节而引发的灾难。重视细节这个品质与你是否足够细心没有必然联系。

我们回到公式1‑3，简单探讨计算Hit time，Miss Rate和Miss Penalty这三个参数时所需要考虑的因素和相关的环境。

似乎Hit Time参数最容易获得。我们很快就可以从CPU的数据手册中找到各级Cache Hit后的访问时间，并从L1 Cache的访问时间开始计算Hit Time。可能我们上来就错了，现代处理器大多使用了Store-LoadForwarding技术。存储器读操作首先要查询的并不是L1 Cache，是在更前面执行的，还没有来得及提交的Store结果，这些结果保存在一段数据缓冲中，这个数据缓冲也是一种Cache，不过比L1 Cache更加快速一些，也更接近CPU。

除了数据Cache，在现代处理器中，在指令Cache前还有一个Line-Fill Buffer。Sandy Bridge微架构中还含有一个μops Cache[1]，计算指令Cache的Hit延时也没有想象中容易。精确计算指令与数据Cache Hit的延时需要注意很多细节。简而言之，在处理器系统存储层次中，L1 Cache并不是最快的，也不是第一级。如果进一步考虑到Load Speculation使用的各类算法和命中率，Hit Time参数并不容易计算清楚。

即便不考虑这些较为复杂的细节，我们仅从L1 Cache开始，Hit Time参数也很难用简单的公式描述。在单处理器环境中，L1 Miss后会逐级查找下级Cache，直到主存储器。但是在多处理器内核环境中，情况复杂得多，一次存储器访问在自己的内核中没有命中，可能会在其他内核的Cache中命中，在其他内核的Cache中命中后，又存在数据如何传递，延时如何计算这些问题。说清楚这些问题并不容易。如果我们再进一步讨论多个SMP系统间Cache的一致性，这个Hit Time的计算就更加复杂。我只能选择放弃在这一节内，能够清楚地描述如何计算Hit Time这个参数。

Miss Rate参数更加难以琢磨。我们真的可以用Vtune，Perf这样的工具精确计算出哪怕是单个任务的Miss Rate这样的参数吗，用这样的工具得到的统计数值有什么用途。同一片树叶，有的人一叶障目，有的人一叶知秋。不要为一叶障目而苦恼。多看几片后，必会发现春天的到来，也不要为一叶知秋而骄傲，少看几片，终会被最后一片树叶阻隔。

Miss Penalty参数的计算仿佛容易一些。最糟糕的情况莫过于CPU从主存储器中获取数据。我们可以将环境进一步简化，以便于读者计算这个参数。我们可以不讨论SMP系统间的Cache一致性，甚至不讨论SMP之内的Cache一致性，仅讨论单处理器。即便如此Miss Penalty参数也不容易轻易计算，即便在这种情况之下，我们只讨论存储器读。

我们忽略微架构在Cache前使用的各类Queue，让存储器读操作首先对L1 Cache进行尝试。如果没有命中这级Cache，这次数据访问一定可以到达L2 Cache吗，如果不是L2 Cache，又是哪一级Cache。这一切由L1和L2 Cache的关联结构决定。在一个处理器系统中，L1与L2 Cache之间可能是Inclusive，也可能是Exclusive。如果是Inclusive，存储器读操作将接着尝试L2 Cache，如果不是将会跨越这级Cache。事实并非如此简单，L1与L2 Cache并不会直接相连，之间依然存在着许多Buffer。

历经千辛万苦，数据访问最终到达最后一级Cache，如果没有命中，就可以从主存储器中获得数据。在这种情况之下，我们仿佛可以计算出最恶劣情况之下的Miss Penalty。但是这只是噩梦的开始。在现代处理器系统中，每一次存储器读写指令，都是由若干个步骤组成，这些步骤间具有相互联系，如果进一步考虑Memory Consistency层面，所涉及到的同步操作更多一些，这些操作并不能用几句话概括。

我们抛开这些复杂话题，讨论在L1和L2 Cache Miss之后从存储器获得数据这个模型。存储器读从存储器获得数据仅是一次读访问的步骤。从主存储器获得的宝贵数据不会轻易丢失，会存放在Cache中，需要将这些数据存放到哪一级Cache最为合理，LLC，MLCs还是FLC。

在一个正常运行的系统中，在每一个Cache Block中存放的数据都是有用的。新数据存放通常意味着旧数据的淘汰。值得思考的是如何进行这些淘汰操作，使用什么策略进行淘汰。从L1 Cache中淘汰的数据虽然暂时没有用途，但是不意味着可以轻易丢失，是否应该先进入到L2 Cache暂存。采用这种策略时，L2 Cache也需要相应的进行淘汰操作。

从上文的描述可以看到，一个简单的存储器读访问带来了一系列的问题。我们首先需要为这次存储器读做基础的准备，然后进行真正的存储器读，读完成之后，还有复杂的扫尾工作。貌似容易计算的Miss Penalty参数即便在简化到了不能再简化的现代处理器系统中，也很难计算清楚。

我们还没有讨论存储器写对Cache Block的的污染与破坏，写操作可能会改变Cache Block的状态，使存储器读操作更加举步维艰，写操作还会带来很多Bus Traffic，这些Traffic加大了存储器读的Miss Penalty，我们没有讨论多处理器内核环境下的Cache Coherence。

我们依然忽略了一个更加基本的细节，虚实地址转换。在现代操作系统中运行的任务，没有哪个任务可以直接使用PhysicalAddress(PA)，使用更多的是EffectiveAddress(EA)。在多数处理器系统中，EA首先被转换为VirtualAddress(VA)，之后再转化为PA。处理器微架构在更多的场景中直接使用的是PA，不是VA更不是EA。

虚拟化技术的引入，在略微有些复杂的VA，PA和EA的基础上又引入了MPA(Machine PhysicalAddress)和GPA(Guest PhysicalAddress)，带来了一系列地址Mapping机制，中断重定向等内容。虚拟化还带来了IOMMU和I/O虚拟化技术。为了能够在最小的篇幅完成这篇文章，我们忽略虚拟化技术，专注最基础的虚实地址转换。