January
24th,
2019
缓存设计回顾
写缓存
- 直写（write-through）：直接将高速缓存块写回低一层中，每次都会引起总线流量，低效。
- 写回（write-back）：直到替换算法要驱逐缓存块时，才将它写回低一层中，需要额外的修改位（dirty bit）表示高速缓存块是否被修改过。
处理写不命中
- 写分配（write-allocate）：加载低一层块到高速缓存中并更新，与写回搭配。
- 非写分配（not-write-allocate）：直接写到低一层中，与直写搭配。
缓存一致性问题
来源
在共享内存多处理器中，每个处理器缓存中的内存备份不一致。
不能用锁解决？锁只能用于共享变量的互斥，而缓存一致性的问题在于对内存的备份不一致。
简单例子：单核处理器
I/O操作+DMA
例如，处理器写共享缓冲区，网卡异步地从共享缓冲区中读数据，如果缓冲区没有刷新，网卡会得到错误数据。
解决
CPU使用非缓存（uncached）写法，操作系统标记含有共享缓冲区的内存为非缓存的；和CPU的load/store比，DMA的使用频率很低，因此这种软件解决方法开销不大。
定义
对内存X读的结果必须是上一次写完后的结果。在多处理模型中：
- 读写符合单处理器顺序（即程序顺序）
- 多处理器中，其他处理器的写操作必须更新后才能读
- 多处理器中，任意两个处理器的写操作在其他处理器看来是有顺序的。
硬件解决方案
- 监听snooping
- 目录directory
监听式缓存
共享缓存（作为对比）
- 解决缓存一致性问题
- 可拓展问题，多个处理器有竞争关系
- 失去局部性、快速的特点
监听式缓存
缓存监听器监听内存操作，并传播到其他缓存的缓存监听器
简单的直写式（write-through）
一旦发生写操作，该处理器的缓存控制器传播无效信号，其他处理器的缓存控制器接收信号，接下来的读操作会触发缓存丢失，从而直接到内存中读。
状态图
- 状态：Invalid，Valid
- 操作：PrRd，PrWr（当前处理器操作），BusRd，BusWr（总线操作）
写回式（write-back）
MSI状态图
- 状态：Invalid，Modified（缓存行只对当前有效，可写），Shared（缓存行对所有都有效，可读不可写）
- 操作：PrRd，PrWr，BusRd（复制缓存行但不修改），BusRdX（复制缓存行并修改），flush（将dirty line写回内存）
- Modified缓存行可以被直接修改
- 处理器只能修改Modified缓存行，即对其他状态的缓存行需要一种方式使得当前缓存行成为Modified状态
多层缓存结构
- 缓存的包含性
- L2包含L1，只需对L2监听
代码编写
False-sharing：处理器对不同地址进行写操作，然而不同地址却映射到同一个缓存行。
// bad
int myPerThreadCounter[NUM_THREADS];
// better
struct PerThreadState{
int myPerThreadCounter;
char padding[CACHE_LINE_SIZE-sizeof(int)];
}
PerThreadState myPerThreadCounter[NUM_THREADS];