实验原理

1. Cache结构测量

1.1 测量Cache容量

  测量Cache容量的基本思路是依次连续访问主存中不同大小的数据块，观察平均访存时间。数据块大小的范围需包括Cache的大小，比如从2KB到2MB，然后记录并观察不同数据块大小下的平均访存时间。

  现代计算机系统往往采用多级存储系统来缓解存储墙问题，而不同层次的存储器存在不同的访问延迟。因此当数据块大小超过L1 Cache的大小后，将出现频繁的L1 Cache读缺失，因此平均访存时间会突然增加。同理，当数据块大小超过L2 Cache的大小后，平均访存时间也会突然增加，如图1-1所示。

图1-1 各级Cache的平均访问时间示意图

  在一个循环当中不停地访问数组，若数组的大小不超过Cache的大小，则在首次循环结束时，整个数组将被完全缓存在Cache中；后续每次访问数组，都将发生Cache命中，故此时的平均访存时间较短。当数组的大小超过Cache的大小后，程序循环访问数组时，必将周期性地发生多次Cache访问缺失，而Cache缺失意味着不仅需要访问下一级存储器，还需要替换相应的Cache块、更新Cache元数据等等，故此时的平均访问时间较长。

1.2 测量Cache块大小

  CPU与Cache之间以字为单位进行数据交换，而Cache与主存之间则以数据块为单位进行数据交换。CPU访问Cache中的字数据时，如果发生Cache缺失，则主存中的某个数据块将被读取并填充到发生缺失的Cache块中。

  想象这样的情形：CPU需要连续访问内存中的数组$A$，且Cache中不存在数组$A$任何元素的副本。当CPU访问数组的第一个元素$a_0$时，将发生Cache缺失。此时，$a_0$所在的数据块$Block_0$将被填充到Cache中。假设数组$A$的元素是连续存放的，且一个数据块最多存放$k$个元素，则此后CPU访问$a_1$、$a_2$、$\cdots$、$a_{k-1}$时，都将发生Cache命中。同理，当CPU访问元素$a_k$时，将发生Cache缺失。此时，数据块$Block_1$将被填充到Cache中，此后CPU访问$a_{k+1}$、$a_{k+2}$、$\cdots$、$a_{2k-1}$时，都将发生Cache命中。不难发现，如果CPU连续访问数组中的元素，则Cache命中率为$\frac{k-1}{k}$。

  假设现在CPU需要以$m-1$为间隔顺序访问数组$A$，$m$和$k$都是2的正整数次幂，且Cache中不存在数组$A$任何元素的副本。当$m<k$时，易知Cache命中率为$\frac{k-m}{k} = 1-\frac{m}{k}$，即随着访问间隔$m$的增加，Cache命中率将降低。当$m \geq k$时，显然每次访问都将发生Cache缺失。根据以上Cache访问规律的理论分析，可令程序以逐渐增大的间隔来顺序访问数组，记录每个访问间隔下的平均访存时间。当访问间隔增大到某个值时，平均访存时间将突然增加，该临界点即为Cache块大小的值。

1.3 测量Cache相联度

  测量Cache相联度的基本方法是建立一个2倍于Cache大小的数组，将数组平均分成$2^n$块，只访问其中的奇数块。不断增大$n$的值，记录每个$n$值下的平均访存时间。当$n$增大到某个临界值$n'$时，平均访存时间将突然增加，则$2^{n'-2}$即为Cache的相联度。

  假设现有一个2路组相联Cache和一个2倍于Cache大小的数组，如图1-2所示。根据组相联映射规则，将主存中的数组分成$s_0$~$s_3$四个区，每个区包含的数据块数量等于Cache的组数，且每个区内的第$i$块映射到Cache的第$i$组$g_i$。

图1-2 Cache和数组的数据块映射关系

  假设现在将数组平均分成2块，访问第1块，则Cache能够完整装下第1块，此时访存命中率较高，如图1-3所示。

图1-3 将数组分成2块，访问第1块

  接着将数组平均分成4块，依次访问第1、3块，此时Cache仍然能够完整装下所有被访问的数据块，此时访存命中率较高，如图1-4所示。

图1-4 将数组分成4块，访问第1、3块

  然后将数组平均分成8块，依次访问第1、3、5、7块。CPU访问第1、3块后，按照组相联映射规则，第1、3块都将被装入Cache的第1组$g_1$。当CPU继续访问第5、7块时，由于第5、7块仍然映射到$g_1$，而此时$g_1$已经没有空闲的Cache块，故将发生Cache替换，如图1-5所示。显然，此种情形下，循环访问第1、3、5、7块，将不断发生Cache替换，命中率较低，平均访存时间较长。

图1-5 将数组分成8块，访问第1、3、5、7块

  此时，临界值$n'=3$，则测得相联度应为$2^{n'-2} = 2^{3-2} = 2$。

2. TLB测量

  CPU发出的访存地址是虚拟地址，需要先经页表转换成物理地址，才能访问存储器。页表一般存储在内存中，这意味着每次访问内存数据，实际上至少都要访问两次内存 —— 第一次访问页表获得物理地址，第二次才是访问数据。为了减少访存次数从而提高访存性能，处理器中往往增加了一个特殊的Cache，即TLB，用于缓存部分页表。TLB由若干条entry组成，每条entry记录了一个内存页的虚实页号映射关系以及其他必要的元数据。

  访存时，若TLB命中，则只需访问一次内存即可完成CPU的数据访问请求；若TLB缺失，则至少需要访问两次内存才能完成CPU的数据访问请求。在内存中申请一段足够大的空间，每次均以页为单位访存，连续访问若干页。若访问的页数不超过TLB的entry数，则理想情况下每次访存都将命中TLB；否则，TLB将发生缺失；分别记录TLB命中时和缺失时的平均访存时间，就能测出TLB有几条entry。