相关路数
现代缓存设计中相关路数还是考虑得比较多的。一般来说，相关路数较少会降低成本，速度也可以做得快一些，但命中率也会被降低一些（当然不是所有的情况：我们下面要分析的情况就是一个例外）。相关路数并不是一个很好测试的参数。下面的原理应用到我的机器上，对L2给出了满意的答案，而对L1的测试数据就很令人迷惑了。
由于我们在这之前已经解决了块大小的测试，根据缓存的工作原理，在这里就没有必要讨论缓存块内部的问题了，我们只要把每个缓存块当作一个整体来讨论就可以了。所以下面的讨论以块为单位，并且不用特别指明块的大小。
首先看一下全相关的情况。假设我们有一个4路全相关缓存，则该缓存共有4块。如果我们要访问的内存大小不超过4块则没有问题，所有数据都可以放到缓存中，命中率可以接近100％。但这显然不是普遍情况，数据容量超过缓存容量在所难免。我们就分析一下全相关缓存在这种情况下的性能。不失一般性，我们考虑数据容量超过缓存大小“最低限量”的情况：数据刚好5个块大小。如下图所示：
缓存共4块，编号0～3，数据共5块，编号0～4。我们假设用最普通也是很多缓存设计中经常假设的访问方式：顺序读操作。我们还假设缓存采用现代最常用的替换策略：LRU。首先缓存全空。我们按顺序访问数据0～3，很自然发生4次未命中事件，这是任何缓存和替换策略的都无法避免的。下面我们将访问数据块4。此时，根据LRU策略，块0将被替换出去。现在缓存情况如下：
接下来，根据访问顺序，我们将回到数据块0。而块0刚刚被替换出去。所以我们不得不再找一个位置来放块0。根据LRU策略，块1被替换出去。依此类推，我们可以知道，在这种情况下缓存的命中率为0！！虽然是不想看到的情况，但这是事实。在学术上这叫做“颠簸”。颠簸总是缓存设计上希望尽量避免的。我们总是希望缓存的命中率如下面的曲线：
而现在，数据容量刚超过缓存容量一个最小单位，命中率就降到了0。命中率降到0是最差情况了（可能有比0更低的命中率吗！！？？），任何改变都不可能变得更糟，所以我们总是要想办法改进。一个可能的改进是不采用LRU替换策略。比如，我们可以采用随机替换策略。上例中，如果采用随机替换策略，在访问块4的时候，0～3被替换出缓存的概率是相同的，则块0被留在缓存中的概率是75％，所以再回头访问块0的时候，期望的命中率将是75％。当然情况不是总是那么好。可以证明，在上面的访问顺序中，采用随机替换策略的命中率应该有：
75％×75％×75％×75％＝31.64％
这比LRU的0要好很多了。虽然优化替换策略可以提供60％的命中率，但是仅仅具有理论意义（如果采用“后进先出”替换策略，可以达到优化替换策略的60％，不过有谁会为此采用这样不合常理的替换策略？）。可以看到LRU不见得是最好的替换策略，虽然实现LRU需要很多硬件。
不过在我们使用的X86系列CPU中，大部分的缓存都是采用LRU的。所以上面的“改进”不符合实际情况。我们还有另外的“改进”方法，就是降低相关程度。先不要大惊小怪，看我们的分析。举例来说，我们从4路全相关“改进”到2路集相关，如下图所示：
根据缓存原理，此时数据块0、2和4将可以映射到缓存块0和2，而数据块1和3只能映射到缓存块1和3。可以看出，数据块0、2和4将争用2个缓存块，如果仍采用LRU策略，将会导致颠簸。而数据块1和3可以全部放在缓存中，不会颠簸。在这种情况下，很明显，命中率是40％。更进一步，我们可以采用直接映射缓存，可以证明其命中率为60％。可见，相关路数也不是越高越好。
说了这么多，并不是为了证明高的相关路数和LRU替换策略不好（在大多数正常使用的情况，这些都是好的），只是为了说明我们检测相关路数的原理。下面我们就具体来看基于LRU替换策略，4路集相关缓存在不同数据集大小下的性能表现。
根据缓存原理，4路集相关缓存可以看作是多个4路全相关缓存的结合。首先看一个问题：要让这样一个缓存发生完全的颠簸（命中率降到0），需要多大的连续数据集大小？根据前面的分析，只要其中的每个“全相关缓存”都发生颠簸，则整个缓存将发生完全颠簸。要让这些“全相关缓存”颠簸，就要为每个缓存找到5个相互竞争的数据块。从缓存原理可知，连续的（1＋1/4）倍缓存大小的数据集正好是这样的一个数据集。数据集再加大不会使性能继续降低（已经到最低点了，怎么可能再下降？），而数据集减小将会使性能上升。例如，取大小为（1＋1/8）倍缓存大小的数据集，其命中率将在40～50％。这是一个非常明显的差异了，完全可以通过测试发现。所以我们的测试原理出来了：设缓存大小为Size,则先测试2×Size大小的数据集的顺序读取速度，然后测试数据集大小为（1＋1/2）×Size时的顺序读取大小，然后是（1+1/4）×Size......，直到发现读取速度有明显的上升，或者不能再继续下去了（有多种原因可能导致无法进行下去）。于是就可以推测出相关路数了。
实际情况是不是这样，我们用测试数据来说明问题。下面是我的机器上的测试结果：
对应于缓存块的顺序访问，在数据单元上将是按缓存块大小为步长的块跳跃访问，所以这里的测试值比较低。事实上我们用数据单元上的顺序访问作过分析，也是可以说明问题的。
首先看L2的情况。把L2的数据画成曲线图如下：
可以明显地看出在数据集大小为288K处曲线转平，256/（288-258）＝8，说明L2是8路集相关。这与Intel的说明相符合。再看L1的曲线：
按Intel的说法，PIII的L1是4路集相关则曲线应该在（16＋16/4）＝20K的地方下降到最低点。应该说上图的3条曲线对此都体现得淋漓尽致。可以说，在使用LRU替换策略的缓存上，这里给出的测试方法应该是有理论根据的。
