在N-Ways Set-Associative方式的Cache中，CPU如何选用函数f映射Cache中的Set是一个值得讨论的话题。其中最常用的算法是Bit Selection。这是一种最快，最简洁的实现方式，使用这种方法带来的最大质疑莫过于Set的选择不够随机。历史上曾经有人试图使用某些pseudo-random算法作为函数f，但是需要明确的是在Set Selection中，严格意义上的Random算法并不可取。
一是因为在Silicon Design中，很难在较短时间内产生一个随机数，即便使用最常用的LFSR(Linear Feedback Shift Register)机制也至少需要一拍的延时，而且也并不是真正随机的。二是因为多数程序具有Spatial Locality特性，依然在有规律地使用Cache，采用严格意义的Random很容易破坏这种规律性。
在许多实现中，Set Selection时选用的pseudo-random算法等效于Hash算法，这些Hash算法多基于XOR-Mapping机制，需要几个XOR门级电路即可实现。诸多研究表明，这种算法在处理Cache Conflict Miss时优于Bit Selection。
在已知的实现中，追求Hit Time的L1 Cache很少使用这类Hash机制，但是这些方法依然出现在一些处理器的MLC和LLC设计中，特别是在容量较大的LLC层面。在MLC层面上，多数微架构使用的Set Selection的实现依然是简单而且有效的Bit Selection方式。
Bit Selection方式所带来的最大问题是在选择Set时，经常发生碰撞。这种碰撞降低了Cache的整体利用率，这使得系统软件层面在使用物理内存时需要关注这个碰撞，也因此产生了与物理内存分配相关的一系列Index-Aware算法。
操作系统多使用分页机制管理物理内存。使用这种机制时，物理内存被分为若干个4KB大小的页面。当应用程序需要使用内存时，操作系统将从空闲内存池中选用一个未用物理页面(Available Page Frame)。选取未用物理页面的过程因操作系统而异。
有些操作系统在选用这个物理页面时，并没有采用特别的算法，对此无所作为。在很多时候，这种无为而治反而会带来某种随机性，无心插柳柳成荫。对于Cache使用而言，这种无所作为很难带来哪怕是相对的随机。
精心编制的程序与随机性本是水火难容，而且这些程序一直在努力追求着时间局部性和空间局部性，最大化地利用着Cache。这使一系列Index-Aware类的Memory分配算法得以引入。在介绍这些Memory分配算法之前，我们首先介绍采用分页机制后，一个进程如何访问Cache，其示意如下图所示。
在多数情况下，操作系统以4KB为单位将Memory分解为多个页面。如上图所示，这个4KB的页边界将Cache Line Index分解成两个部分，其中在Page Frame中的部分被称为Bin Index，在Page Off中的部分被称为Offset Index。以此进行分析，Memory分配算法也被分为两大类，一类是Bin Index Aware，另一类是Offset Index Aware Memory分配算法。
我们首先简要介绍Bin Index的优化。根据Bin Index的不同，Cache被分为Large Cache和Small Cache两类。当一个Cache的容量除以Way数大于实际使用的物理页面时，这种Cache被称为Large Cache，反之被称为Small Cache。
在许多处理器系统的实现中，L2和L3一般都属于Large Cache，L1 Cache需要视情况而定。如Sandy Bridge L1 Data Cache的大小为32KB，8-Ways结构，两者之商为4KB，不大于4KB页面，该Cache即为Small Cache。例如Opteron的L1 Data Cache为64KB，2-Ways结构，两者之商为32KB，大于4KB页面，该Cache即为Large Cache。
需要注意的是4KB只是在多数操作系统中常用的物理页面大小，有些操作系统可以使用更大的页面，如8KB，16KB等。这使得Small Cache和Big Cache的划分不仅与微架构相关，而且与操作系统的具体实现相关。一个物理页面大小的使用与许多因素相关，页面越大，碎片问题也越发严重，但是与此相关的TLB Miss Rate也越低。在上文提到的，在Superpages中存在的Allocation，Relocation，Promotion，Pollution和Fragmentation Control等若干问题，随着页面大小的增加，其解决难度也在逐步增大。
另外需要注意的是，这里的“物理页面”指实际使用的物理页面。在1GB大小的Superpage面前，所有Cache都应该属于Small Cache，但是只有极少有应用真正这样使用这个1GB页面，在多数情况下，1GB大小的Superpage仍然被分解为更小的物理页面，可能是4KB，8KB，或者是其他尺寸。
Bin-Index优化算法的实现要点是，不同的物理页面在使用Cache时，尽量均匀分配到不同的Bin Box中。如上图所示，在一个Bin中通常有若干个Set，Set中还有若干个数据单元，当所有Set的所有数据单元都被占用时，如果有新的物理页面依然要使用这个Bin Box时，将在一定程度上引发Cache Contention，即便在Cache中仍有其他未用的Block。
对于一个进程而言，产生Cache Contention原因是，一个进程使用的虚拟地址空间虽然连续，但是在进行虚实映射时，内存分配器如果没有进行Bin-Index的优化手段，将“随机”选取一个物理页面与之对应，这个“随机”不但不是“随机”的，而且有非常强的规律性，从而造成了一些原本不该出现的Cache Contention。
列举几个常用的Bin-Index的优化算法，如Page Coloring，Bin Hooping，Best Bin和Hierarchical。有些算法已经在FreeBSD和Solaris中得到了实现，在Linux系统中，目前尚未使用这些Bin-Index算法。
但是我们不能得出因为Linux系统没有使用这类算法而导致性能低下这一结论。上文所述的所有Bin-Index算法都有其优点和缺点。而且从某种意义上说，不使用Bin-Index也是一种Bin-Index算法，同时在许多微架构的Cache设计中，由于Virtual Cache和Hash算法的使用，使得Bin-Index算法并不会取得很好的效果。
Page Coloring算法最为简单，其主要原理是利用了Virtual Cache无需染色的原理，因为在多数情况下地址连续的Virtual Page很少在Cache中冲突，此时在分配物理页面时，其部分低位可以直接使用虚拟地址的低位，从而在一定程度上避免了Cache Contention。如果进一步考虑多进程情况，使用这种算法时还可以将之前的结果与进程的PID参数再次进行XOR-Mapping操作；进一步考虑多内核情况，可以将再之前的结果与内核的Logical Processor ID进行XOR-Mapping操作。
对于使用了Virtual Cache的微架构，并不意味着Bin-Index算法不再适用。因为在多数情况下，Virtual Cache仅在需要进一步降低Hit Time的L1 Cache中使用，在L2或者更高层的Cache中，很少再使用这种技术。
Bin Hooping，Best Bin和Hierarchical算法也并不复杂，这些算法都是利用Temporal Locality原则。在微架构和操作系统层面的设计与实现中，使用的多数算法都不复杂。
在一个操作系统实现中，Memory Allocator是一个非常重要的组成部件，其设计异常复杂。有一些人在努力寻求最优的，通用的分配管理原则，虽然最优和通用几乎很难划等号。
通用原则有通用原则的适用场合，专用的定制原则也有其存在的必要，没有一个绝对的准则。
通常在一个Memory Allocator的设计中需要关注自身的运行效率，如Footprint，False Sharing，Alignment和TLB的优化等一系列问题，也包含Cache-Index的优化问题。
许多操作系统实现了Cache-Index的优化，包括Bin-Index和Offset-Index。一些操作系统统筹考虑Bin和Offset的Index，并将其合并为Cache-Index，其中最著名算法的是Hoard和Slab。近些年也出现了一些较新的Cache-Index Aware算法，如CLFMalloc和CIF(Cache-Index Friendly)。
这些算法都在关注如何寻求合适的策略以避免Cache Index的冲突，尽量使物理页面映射到Cache的不同Set中。需要读者进一步考虑的是，即便为某个应用找到了这些最优的映射方式，这些方式是否能在更广阔的应用领域发挥更大的效率。所有这些最优可能都有其合适的场景，很难有放之四海而皆准的策略。
为此我们首先简要回顾Cache自身的编码方式。下文以一个2-Way Set-Associative，Cache Block长度为64B，总大小为64KB的Cache说明其内部的编码和组成方式。在采用这种方式时，该Cache的Set数目为512。
这种结构的Cache与Opteron的L1 Data Cache类似，如下图所示。由上文所述，Cache由两部分组成，一个是Tag阵列，另一个是数据阵列。在Opteron的L1 Cache中，Tag阵列由512个Set组成，每个Set的Entry数目为2，数据阵列与此一一对应。
我们首先讨论Cache的Data阵列。在现代处理器微架构中，从逻辑上看Data阵列首先被划分为多个Set，在每一个Set中含有多个Way，而且每一个Way由多个Bank组成。但是从物理实现上看，Data阵列本质上是一块SRAM，使用连续的物理地址统一编码。从Silicon Design的角度上看，Cache的Data阵列具有地址，其编码方式如下图所示。
对于64KB大小的Cache，一共需要16位地址进行编码。为简化起见，我们忽略这个地址的最后6位，仅讨论Set Number和Way Number。一个Cache的物理地址整体连续，然后被Way Number划分成为多个物理地址连续的子块。
CPU访问Cache时，首先使用Set Number访问子块，在2-Ways Set- Associative结构中，将有两个子块被同时选中，之后这些数据将同时进入一个或者Way-Select部件。在这种情况下这个Way-Select部件的数据通路为2选1结构。
在现代处理器中，为提高Cache的数据带宽，通常设置多个Way-Select部件，以组成Multi-Port Cache结构。相应的，AGU也必须具备产生多套地址的能力，分别抵达不同的Tag阵列。从而在微架构中需要设置多个AGU，并为Cache设置多个Tag阵列以支持Multi-Ports Cache结构。多端口Cache的实现代价较大，多数处理器仅在L1层面实现多端口，其他层面依然使用着Single-Port结构。
图2‑9中所示的Cache结构使用了2-Ports结构，每多使用一个Port就需要额外复制一个Tag阵列，也由此带来了不小的同步开销，而且过多的Port更易产生Bank Conflict。在现代微架构的实现中，L1 Cache层面多使用2个Port，很少更多的Port。同时为了支持Cache的流水操作，Opteron微架构设置了3个AGU部件，个数超过了2个Port所需要的。其中更深层次的原因是x86处理器EA的计算在某些情况下过于复杂。
在Cache的组成结构中，还有一个细节需要额外关注。当CPU对一个物理地址进行访问没有在Cache中命中时，通常意味着一个Cache Block的替换。Cache Block的替换算法对Cache Hit乃至整个Cache的设计至关重要。
作者：sailing
来源：处理器芯片设计https://mp.weixin.qq.com/s/EwinN9GQNrRGxxOdGYCdNQ
https://mp.weixin.qq.com/s/VS3Daol799yUQ06z0Pd1kw
推荐阅读
更多数字IC设计技术干货等请关注数字芯片实验室专栏。添加极术小姐姐（微信：aijishu20)微信可申请加入IC设计交流群。
