计算机体系结构


Memory Consistency and Cache Coherence

Memory Consistency and Cache Coherence

Memory Consistency and Cache Coherence 定义

1. Memory Consistency（内存一致性）

2. Cache Coherence（缓存一致性）

3. 主要区别

特性 Memory Consistency（内存一致性） Cache Coherence（缓存一致性）
关注点 内存操作的全局顺序和可见性 多个缓存副本之间的数据一致性
范围 涉及所有内存操作（读/写）的顺序 仅涉及缓存和内存之间的数据一致性
问题背景 多个处理器对共享内存的访问顺序是否一致 多个处理器的缓存中数据是否一致
解决方案 内存一致性模型（如顺序一致性、弱一致性） 缓存一致性协议（如MESI、写失效、写更新）

4. 总结

Memory Consistency and Cache Coherence

TSO（Total Store Ordering）内存模型

  1. TSO（Total Store Ordering）是一个被广泛使用的内存模型
  2. 并在x86架构中使用，RISC-V也提供了TSO扩展，即RVTSO，人们普遍认为x86内存模型等同于TSO，然而Intel和AMD从来没有保证这一点
  3. x86选择放弃SC（顺序一致性sequential consistency），以更好地支持基于FIFO的write buffer，用于加速性能
  4. TSO和SC最关键的区别就是store可能被放入write buffer中且允许load的bypass
    1. 对于单核视角来说，和SC没有区别，执行顺序和程序顺序一致
    2. 对于多核来说，需要额外的手段来保证memory consistency
  5. 由于TSO只允许store-load的重排，因此需要使用FENCE的场合不多，FENCE的实现方式也不是很重要。一种简单的实现是，当FENCE被执行时，清空write buffer，并在FENCE提交之前不再执行后面的load指令。
Memory Consistency and Cache Coherence

x86的多核宽松内存一致性模型

  1. 被修饰的汇编指令成为“原子的”
    1. 本身是原子指令，比如“XCHG”和“XADD”汇编指令
    2. 本身不是原子指令，但是被LOCK指令前缀修饰后成为原子指令，比如LOCK CMPXCHG
    3. 被修饰的汇编指令A在执行期间，会在内存总线上声言一个#LOCK信号，该信号导致内存被锁住，此时内存不能再被其他汇编指令存取，直到A执行完成。经过分析可知，A的执行效果与“暂停执行其他所有汇编指令直到A执行完成等价，因此此时A是原子的
  2. fence
    1. sfence: 在sfence指令前的写操作当必须在sfence指令后的写操作前完成
    2. lfence：在lfence指令前的读操作当必须在lfence指令后的读操作前完成
    3. mfence：在mfence指令前的读写操作当必须在mfence指令后的读写操作前完成

  3. C++11中支持的内存模型

    1. Acquire-Release能保证不同线程之间的Synchronizes-With关系，同时也约束到同一个线程中前后语句的执行顺序。
    2. Release-Consume只约束有明确的carry-a-dependency关系的语句的执行顺序，同一个线程中的其他语句的执行先后顺序并不受这个内存模型的影响
enum memory_order {
    memory_order_relaxed, // Relaxed
    memory_order_consume, // Release-Consume
    memory_order_acquire, // Acquire-Release 用来修饰一个读操作，表示在本线程中，所有后续的关于此变量的内存操作都必须在本条原子操作完成后执行
    memory_order_release, // Acquire-Release 用来修饰一个写操作，表示在本线程中，所有之前的针对该变量的内存操作完成后才能执行本条原子操作
    memory_order_acq_rel, // Acquire-Release 同时包含memory_order_acquire和memory_order_release标志
    memory_order_seq_cst  // 顺序一致性模型
};

 

einsum

两个基本概念

自由索引（Free indices）和求和索引（Summation indices）：

三条基本规则

特殊规则

特殊规则有两条：

a = torch.randn(2,3,5,7,9)
# i = 7, j = 9
b = torch.einsum('...ij->...ji', [a])

二次变换（bilinear transformation）

np_a = a.numpy()
np_b = b.numpy()
np_c = c.numpy()
np_out = np.empty((2, 5), dtype=np.float32)

np_out = torch.einsum('ik,jkl,il->ij', [a, b, c]).numpy()
# ik broadcast成ikl
# il broadcast成 ikl
# 'ik,jkl,il->ij'可以理解成'ikl,jkl,ikl->ij'

for i in range(0, 2):
    for j in range(0, 5):
        # 求和索引内循环  这里是 k 和 l
        sum_result = 0
        for k in range(0, 3):
            for l in range(0, 7):
                sum_result += np_a[i, k] * np_b[j, k, l] * np_c[i, l]
        np_out[i, j] = sum_result

总结

a = torch.rand(2,3)
b = torch.rand(3,4)
c = torch.einsum("ik,kj->ij", [a, b])
# 等价操作 torch.mm(a, b)

equation 中的字符也可以理解为索引，就是输出张量的某个位置的值，是怎么从输入张量中得到的，比如上面矩阵乘法的输出 c 的某个点 c[i, j] 的值是通过 a[i, k] 和 b[k, j] 沿着 k 这个维度做内积得到的。

 

 

RAM

DRAM

  1. 电容
  2. 带宽不是很高
  3. 需要刷新，会有颠簸

SRAM

  1. 面积和功耗不能和工艺平行
  2. 类型
    1. Cpu register Flip Flops 每个bit都有一读一写
    2. L1/L2 SRAM  6个晶体管，一般最多每个bank一读一写
    3. L3/L4  eDRAM/GCRAM   4晶体管/电容   读写速度明显降低，也会有使用上的问题

NoC

OpenSMART

https://github.com/hyoukjun/OpenSMART/tree/master

connect

https://users.ece.cmu.edu/~mpapamic/connect/

https://github.com/crossroadsfpga/connect/tree/main

Flexnoc

is a commercial NoC generator by Arteris which generates a customized
topology for each SoC,

Cache写机制 Write-through与Write-back

Cache写机制分为write through和write back两种。

Write-through: Write is done synchronously both to the cache and to the backing store.
Write-back (or Write-behind) : Writing is done only to the cache. A modified cache block is written back to the store, just before it is replaced.
Write-through（直写模式）在数据更新时，同时写入缓存Cache和后端存储。此模式的优点是操作简单；缺点是因为数据修改需要同时写入存储，数据写入速度较慢。

Write-back（回写模式）在数据更新时只写入缓存Cache。只在数据被替换出缓存时，被修改的缓存数据才会被写到后端存储。此模式的优点是数据写入速度快，因为不需要写存储；缺点是一旦更新后的数据未被写入存储时出现系统掉电的情况，数据将无法找回。

Write-misses写缺失的处理方式

对于写操作，存在写入缓存缺失数据的情况，这时有两种处理方式：

Write allocate (aka Fetch on write) – Datum at the missed-write location is loaded to cache, followed by a write-hit operation. In this approach, write misses are similar to read-misses.
No-write allocate (aka Write-no-allocate, Write around) – Datum at the missed-write location is not loaded to cache, and is written directly to the backing store. In this approach, actually only system reads are being cached.
Write allocate方式将写入位置读入缓存，然后采用write-hit（缓存命中写入）操作。写缺失操作与读缺失操作类似。

No-write allocate方式并不将写入位置读入缓存，而是直接将数据写入存储。这种方式下，只有读操作会被缓存。

无论是Write-through还是Write-back都可以使用写缺失的两种方式之一。只是通常Write-back采用Write allocate方式，而Write-through采用No-write allocate方式；因为多次写入同一缓存时，Write allocate配合Write-back可以提升性能；而对于Write-through则没有帮助。

处理流程图

Write-through模式处理流程：A Write-Through cache with No-Write Allocation

image.png

Write-back模式处理流程：A Write-Back cache with Write Allocation

image.png