体系结构学习15-cache coherence

1、Cache Coherence

现代处理器的并行代码或线程共享内存，需要保证数据一致性。

从软件、硬件两个角度考虑解决cache一致性。

现代处理器cache一般对程序员透明，ISA一般只提供cache flush命令。如果靠软件解决，对程序员负担太大。

Hardware Based：

• 所有核心共享一个L1cache，但是cache通常需要追平CPU频率，很可能无法完成所有核心的读写请求而且容量也成限制，并且核心与cache的连线会变长导致latency边长，最终使得cache成为瓶颈。
• 采用多个L1cache，保证数据一致性。（下面是Snoopy cache）
  Update Protocol：写完后把最新数据推送给所有人更新
  优点：适用数据很少更新，多用于读。
  缺点：如果只有某个核心需要某个频繁更新，那么广播给所有人十分消耗带宽
  Invalid Protocol：写后发送给所有人原数据无效并清除
  优点：适用于少部分核心需要频繁更新
  缺点：如果就两个核心打乒乓球一样相互更新数据会导致效率低下

2、Cache Coherence Methods

• Snoopy Bus：所有CPU连在同一条总线，但容易发生总线资源争夺
• Directory：数据存储空间切成小块，每一小块分配一个控制器，分布式控制大数据存储空间

3、Snoopy Cache

要求cache有双端口，接受总线和相应CPU的信息

cache block：有状态位

比如简单的两状态valid和invalid，就是VI Protocol，Write-through，No-Write-allocate，但是每次写回内存代价比较大。

采用write-back，三状态，MSI Protocol
Modify：该数据是独有的，且被修改过的 is dirty
Shared：这块没有改过的数据被多个cache读取
Invalid：指示该数据是否可用（为最新值）

解决独有数据更新浪费带宽问题，采用四状态，MESI Protocol（intel i7 加入了"forward"，cache与cache之间传输）
Exclusive：指示这块数据只有自己独有，is clean
如何确定其他人是否读取数据？
Wire-OR：shared signal
BusWr
BI：invalid ，not need data
BRI：Invalid， need data

MOESI Protocol：加入了一个owner状态，owner负责最终写回拥有的数据，不需要去内存取最新数据
cache to cache transfer

4、Coherence Miss

为了保证cache一致性，而被清除数据的cache增加了miss

• True Sharing Miss：cache block只有一个单元一定是true
• False Sharing Miss：写了2号数据，别人需要0号数据，这两个在同一个cache block，故而别人的cache数据被清除，但是两者并不是读取同一个地址（cache block太大导致无关数据被清除）。不会发生在cache block 只有1个单元。

coherence miss不受cache大小影响，但会随着CPU数量增加而增大

5、Directory Coherence

• Motivation
  Snoopy的bus往往是性能瓶颈，如果有n个CPU，就需要支持n倍带宽，并且需要每一个CPU处理其他CPU的所有信息，即处理N^2的信息。

• 解决办法：Directory Protocol：cache和Memory通信不再通过总线连接，而是通过点对点通信（目前高带宽需求的处理器都是点对点）

• NUMA（Non-Uniform Memory Access）访问不同地址空间latency不一样（近的快远的慢）
  涉及地址编号形式问题，避免出现热点，使得分配均匀

• Directory Format：Shared，Uncached，Exclusive
  对每一个CPU记录状态——Full map 或者limited Pointer

• 点对点通信潜在的问题
  （1）写请求与读请求的交叉：需要保持内存操作原子性，Atomic
  （2）避免产生死锁的情况：多个任务需要同样资源从而互相等待
  （分布式系统）

6、Snoopy VS Directory

• Snoopy ：简单，latency小；总线带宽成为瓶颈
• Directory：划分小块点对点通信，对带宽无限制；操作与设计复杂增加，Directory需要额外存储空间。