Cache Index

在N路组相联的cache结构中，如何选择一个组（set）是很有重要的一个问题，最常用的算法是bit selection，这是最简单的实现方式。

在这个图中

Set (i) = f(r (i)) = Bit 12~6    即由第6～12位就可以确定它位于哪个组中。

虽然这是一种高效简介的实现方式，但其最大的问题在于不够随机。曾经有人 （参考1）尝试过使用pseudo-random算法来作为函数f() ，这种做法实际上是不可取的，原因在于：第一，设计芯片时，很难实现在短时间内产生一个随机数，即便最常用的LFSR(Liner Feedback Shift Register)机制也会有一个节拍的延时，而且还不是真正的随机数。第二，由于程序的 空间局部性，他们会有规律地使用这些cache，随机分配的结果反而会影响这种局部性。

实践表明（来源2）使用XOR-Mapping机制的Hash算法在效果上和Pseudo-random，但是实现起来非常简单，只需要简单的XOR门电路即可，使用这种算法选择cache 组时，冲突比Bit selection少。这种算法在容量较大的LLC层使用比较多，在追求HIT time的L1 Cache中，多数CPU使用还是bit selection。

Bit Selection最大的问题在于选择组时，冲突很厉害，这使得操作系统在选择物理内存时需要关注这个冲突，因此也产生了和物理内存分配相关的一系列Index感知的分配算法。

Linux使用分页机制管理内存，大部分情况下使用的都是4KB的页，应用程序需要使用内存时，Linux将从空闲的内存池中选取一个未使用的物理页分配给应用程序，不同的分配算法会选取出不同的物理页。

Bin Box

大部分情况下，操作系统以4K为单位分割内存页，如下图所示，4K的边界将Cache Line Index 分成两部分，在Page frame 中的部分被称为Bin index ，在Page offset中的部分被称为Offset index。因此，内存分配算法也相应地分成两种：Bin Index感知的和Offset Index 感知的分配算法。

Bin index优化算法的实现要点是，不同的物理页在使用cache时，尽量均匀分配到不同的bin box中。如下图所示，一个bin中通常含有若干组，每个组由若干个数据单元构成，当所有组中的所有数据单元都被占用时，新分配的物理页依然需要使用这个Bin box，便引发了cache冲突。也就是说，一个进程使用的虚地址空间虽然连续，但进行虚实转换之后，如果分配器没有进行优化，"随机"地选取物理页以之对应，如果随机函数选得不好，或者具有一定的规律性，那么就很容易出现本不应该有的冲突。

BSD和Solaris上叫常用的Bin-Index优化算法有 Page Coloring、Bin Hopping 、Best Bin和Hierarchical等，这几种算法均有他自己的优缺点，Linux没有使用并不代表它的性能低下。因为"从某种意义上说，不使用bin-index，也是一种bin-index算法"（参考1）

bin box

Virtual cache

程序每次访问内存都需要进行虚实地址转换，即使是容量小，结构简单的cache也必须完成这个步骤。和miss相比，cache命中的频度高得多，如果cache直接使用虚拟地址寻址，这样就可以省去地址转换的步骤，从而提高效率，这样的cache称为虚拟cache

几种Bin-Index算法中，Page Coloring算法是最简单的一种，它主要利用了virtual cache不需要染色的原理，因为在多数情况下连续的virtual page和很少在cache中冲突，因此在分配物理页时，其低位可以直接使用虚拟地址的低位，从而避免了cache冲突。

使用虚拟cache的问题在于，进程切换时，新进程的虚拟地址很可能和原进程相同，但他们使用的是不同的物理地址，因此每次都需要需要清空Cache，这对于再切换回来进程的影响是相对严重的，为了解决这个问题，分配算法往往选择使用添加进程PID一起Hash 或者XOR-Mapping。

Virtual Cache更多的是为了降低Hit time时使用，L1用得比较多，而L2或L3相对则用得很少。

Cache通道

现代处理器中，为了提高Cached数据带宽，通常设置了多个选路(Way-select)部件以组成多通道cache结构，参考Opteron的数据Cache 【上图】。CPU访问cache时，首先使用set Number访问组，在两路组相联的结构中，将有两个组被选中，之后这些数据同时进入选路部件，从两个中选取一个。

多通道的cache中，AGU（Address generation unit）也必须具备产生多套地址的能力，分别抵达不同的Tag阵列。每多使用一个通道，就得额外复制一个tag阵列，同时也带来了额外的同步开销，通道越多，越容易产生bank冲突，这使得多通道的实现代价很大，大部分CPU只在L1使用的多通道，其他层依然是单通道结构。

参考1：《Cache Memory》 Wang Qi, Yang xi等 [Mar. 2010]