较复杂的内存和缓存概念

较复杂的内存和缓存概念

在 内存缓存基础概念 中，我们讨论了一些内存和缓存的基本概念，本部分主要讨论一些复杂的内存和缓存概念。

hash组相联和skewed-associative

组相联较好的平衡了电路复杂度和缓存miss率，但是他也有一定的不足。以常见的基于内存地址的某几位的组相联为例：

  1. 假设cache line=64Byte，四路组相联，那么相当于每间隔64*4=256B的内存地址就会被映射到同一路中。如果我们有一个二维数组double a[100][8]，我们在访问第二维(a[i][0])时，这些地址实际上会被映射到同一路cache中，导致cache miss上升且cache利用率不高。
  2. 恶意程序可以通过观测不同缓存组的命中率进行攻击。比如将cache填满无用数据造成大量cache miss进而导致性能下降，推测目标进程的物理地址并注入等。

现代处理器会使用hash函数而不是内存地址的固定某几位判断属于哪个组。这样可以将内存地址与组的联系黑盒化，提升整体cache利用率。诸如Skylake的12-way，Xeon的16-way，20-wayL3cache都是通过将内存地址取hash后填入对应cache set的。

skewed-associative是另一种降低cache miss的方式。在普通组相联的情况下，假设内存地址f1,f2,f3他们经过hash后得到的结果一致，那么他们就会被映射到同一个组的cache line中。skewed-associative则将不同地址直接与cache line联系起来，比如f1可以放在set1line1-2，set2line3-4；f2可以放在set1line1,3，set2line2,4。这样打破了组相联不同组之间的屏障，降低cache miss率。arm的某些处理器可以配置sekwed-associative。

值得注意的是，这些设计都是在硬件层实现的，对于开发者来说应该是透明的。同时，实际测试经验表明传统的一些方法，如间隔插入变量手动映射地址到不同set没什么效果（因为已经被硬件做好了），但是内存地址对齐到cache line的效果还是比较明显的，尤其是在avx等向量化指令下。

VIVT，VIPT，PIVT和PIPT

cache中的cache line与内存地址通过index和tag对应起来，之前提到过，内存地址存在虚拟地址和物理地址，因此index和tag既可能是虚拟地址(Virtual)计算出的，又可能是物理地址(Physical)计算出的，组合后有VIVT,VIPT,PIVT和PIPT四种。对于CPU来说，其执行的地址是虚拟地址，也就是说VI和VT操作可以直接计算，而PI和PT操作需要通过MMU查TLB计算。

VIVT

VIVT cache的好处是快，因为不需要通过MMU转换地址，但是由于虚拟地址的特性，VIVT存在2个潜在缺点

  1. 假设有两个不同的进程A,B想要修改某个地址的值，其虚拟地址va相同而物理地址pa不同。如果进程A修改了它的va地址中的值，在B中观察到的现象就是cache中B的va的值也被改变了，因为cache中AB的va地址的index和tag是一致的。
  2. 假设有两个不同的进程A,B想要修改某个地址的值，其物理地址pa相同而虚拟地址va不同。如果进程A修改了A中va地址的值，在B中无法观察到这一更新，因为cache中AB的va和index和tag是不同的。

解决方法一般有两种，一是在切换进程时清空缓存，这样能保证cache中的数据时正确的，但是性能会受到较大损失。二是增加一个标记标记cache line归属于哪个进程，这样会增加电路设计复杂度。

VIPT

VIPT计算index时使用虚拟地址，而计算tag时采用物理地址。如果设计合理，比如计算index的内存位数都在page offset的bit中，那么VI和PI的计算结果时一致的。此时VIPT的性能比PIPT好，且避免了VIVT中的问题2。而在一般情况下，VIPT也能避免VIVT中的问题1。

PIPT

PIPT虽然慢，但是能完美解决VIVT中的问题1，2。其主要收益是切换进程不用清空缓存。

PIVT

PIVT使用较少，原因是index一般比tag先计算（先计算在哪个组，在比较组中的cache line查看命中）。在此情况下，使用PIPT和PIVT的性能非常接近，因此往往直接采用PIPT的设计。

VIVT一般被用来设计指令cache(l1i,l2i)，因为其缺点可以被避免（切换进程肯定要清空指令），而收益较大。
VIPT被大量应用，如intel和AMD的cpu的l1d，l2等都采用了VIPT。
PIPT有时候被arm采用，因为在移动端处理器上频繁flush cache可能带来较大的能耗。

值得注意的是，有些设计暴露给开发者的是VIPT，但是底层硬件实际是PIPT，如arm的某些处理器。开发者在非必要的情况下无需关注cache line的具体组成结构，因为大多数完备的硬件已经保证cache能被合理的利用。

NUMA与缓存一致性

NUMA指的是在多节点下，不同CPU核心只能直接访问部分内存地址或缓存，访问剩下的内存需要让能直接访问这些地址的CPU核心代为访问并转发，这是提升横向扩展性的代价之一。常见的例子从多路服务器到家用电脑，比如Ryzen 3100和3300x之间性能的区别。经验表明对于内存密集型任务来说，NUMA能较好地利用多个node之间的带宽，但是其延迟较大，例如Xeon E5V3直接访问内存比访问另一个CPU连接的内存要快3倍。

缓存一致性指的是多核系统不同核心之间独立的l1(l2)缓存与共享的内存(有时包括llc)中数据发生冲突的情况。这可能发生在运行在不同核心上的多个程序试图访问/修改同一个内存地址，或者一个线程被调度到其他核心上，需要访问其在之前运行的核心上已经修改的内存数据。常见的解决方案是设置一个脏位标记，并通过一种控制协议，如MSI等控制。简单来说，这些协议通过M(modified),S(Shared),I(Invalid)等状态标记数据的有效性，同时决定何时将缓存中的数据传送到另一个缓存。也有不同的状态组合，比如MI，MEI，MSEI等等，一般状态越多能更完备的表示数据的状态，其性能也应该越好。