CPU Cache与False Sharing

Orlion

发布于 2024-09-02 16:25:28

970

发布于 2024-09-02 16:25:28

文章被收录于专栏：我的独立博客

一、CPU 缓存架构

现代多核CPU会在每个核心上加上一个较小的SRAM高速缓存存储器称为：L1高速缓存，其中L1缓存由分为dcache数据缓存，icache指令缓存。在L1缓存的下级加一个较大的L2高速缓存，然后会再L2之下加一个多核共享的L3高速缓存。它们之间的逻辑结构大概是这样的：

相较于访问CPU高速缓存来说访问主存简直太慢了，Jeff Dean曾给出过这样一组数字：

L1缓存访问时间 0.5ns
分支预测错误 5ns
L2缓存访问时间 7ns
主存访问 100ns

https://colin-scott.github.io/personal_website/research/interactive_latency.html 给出了不同年份这些指标的数字，

1.1 通用的高速缓存存储器结构

告诉缓存被划分为S = 2 ^ s个高速缓存组(cache set),每个组含有E个高速缓存行(cache line)，每个行又由B = 2 ^ b个字节的数据块(block)和有一个标识该行是否有效(即是否已过期或者已修改)的有效位(valid bit),以及t个标记位(tag bit)组成。物理结构大概是下图这样：

高速缓存的大小指的是所有数据块的大小的和，即：B * E * S。

假设当前CPU地址总线有m位，从而主存有M=2^m个地址，所以每个内存地址会有m位。当CPU需要从主存加载地址为A的内存块上的字节时，会先从CPU高速缓存中获取，这时候问题来了，应该到高速缓存的什么位置去拿呢？实际上会将m位地址A划分为以下几段：

这里的m、t、b、s都是二进制数，不要想成十进制数哦

从而有m = t + b + s CPU会根据A地址中间的s位定位主存地址A映射到了哪个组中，然后根据开头的t位与组内的E个行的标记位挨个比对以确认地址A映射到了哪一行(这里有文章说是并行查询)，这时会检查该行的有效位标识该行是否有效，如果有效的话最后根据后b位就直接定位主存地址A映射到了数据块中的哪个字节上了。如果通过以上的步骤没有找到对应的高速缓存地址的话，高速缓存会向主存请求包含A地址的数据块的一个拷贝，CPU必须等待，当被请求的块到达高速缓存中时高速缓存会将这个块放到对应的位置上，然后从数据块中抽取出A地址上的字节返回给CPU。注意：高速缓存从主存中一次请求的是一个数据块而非具体地址上的一个字节，这非常关键！

CSAPP书中提到了为什么选择中间位作为组索引位，其大概意思是选择中间位能够使连续内存映射到不同的组上，提高高速缓存利用率并且减小冲突覆盖的问题，但是个人感觉其解释是按照特定平台来描述的，并没有普适所有平台，这里就不以我昏昏使你昭昭了，待后续查阅更加合理的解释再说。

根据E的不同我们将高速缓存划分为以下三类：

直接映射高速缓存
组相连高速缓存
全相连高速缓存

1.2 直接映射高速缓存

每组只有一行即E=1的高速缓存称为直接映射高速缓存。这种缓存一旦定位到了组后就无需查询对应行了。

1.2.1 直接映射高速缓存的冲突不命中

假设当前计算机b=16即数据块为16个字节，高速缓存中有两个组，s=5即内存地址的第5位决定内存地址映射到哪个组上，有下面的一段golang代码

func foo(x [8]int32, y [8]int32) int32 {
	var sum int32 = 0
	for i := 0; i < 8; i++ {
		sum += x[i] * y[i]
	}

	return sum
}

上面的程序中x与y占用了8 * 4 = 2 ^ 5 = 32个字节，假设x被加载到地址为0-31的内存之中，y被加载到32-63之中，sum存在于寄存器中，不占用内存地址。如下图所示

运行时，第一次循环中，CPU需要先加载x[0]，由于高速缓存中一开始并没有，所以会从主存中加载x[0]-x[3]共16个字节（数据块的大小）的数据到高速缓存的组0中再返回给CPU，接下来同样的道理会将y[0]-y[3]加载到高速缓存的组0中。这时候由于每组只有一个行就导致了上一步加载进来的x[0]-x[3]被覆盖了，下一次循环中要加载x[1]时，x[1]就不在高速缓存中了，所以又必须去内存中加载一次，结果从内存中加载会的数据又把第二次加载进来的y[0]-y[3]给覆盖了，之后的每次循环都存在这个问题，导致每次都回冲突不命中。这种高速缓存反复地加载和驱逐相同的高速缓存块的组的情况称为抖动(thrash)。

为了解决这个问题我们可以将x和y两个数组的长度定为12，即：

func foo(x [12]int32, y [12]int32) int32

这样的话再看下分布情况：

这样的话由于y[0]-y[3]与x[0]-x[3]不在一个组上就不会出现抖动问题了。

1.3 组相联高速缓存

组相联高速缓存每组中有多个行。

1.4 全相联高速缓存

全相联高速缓存只有一个组。

1.5 写的问题

如果CPU要写一个已经缓存了的字时，有两种方法将该数据写到下层缓存中： 1. 直写，最简单的一种方法，直接将数据写入到下层缓存。但是这种方案每次写都回引起总线流量 2. 写回，为每个行单独维护一个修改位dirty bit，标识这个缓存块被修改过，只有当替换算法要驱逐更新过的块时才将它写入到下一层缓存中。

写不命中通常有两种方法： 1. 写分配，加载低一层的缓存到高速缓存中，然后更新这个数据块。缺点是每次不命中都会导致一个块从低一层传送到高速缓存。 2. 非写分配，避开高速缓存，直接把这个数据写入到低一层中。

直写通常是非写分配的，写会通常是写分配的。

二、伪共享False Sharing

通过上文了解CPU的缓存结构后我们做一个实验来引出伪共享的问题，实验前我们先看下实验机器的一些信息。Mac上通过sysctl -a查看机器信息，这里我过滤了下只拿出来与此实验相关的一些机器指标:

hw.cachelinesize: 64 // Cacheline 64字节
hw.l1icachesize: 32768
hw.l1dcachesize: 32768 // L1数据缓存32K
hw.l2cachesize: 262144 // L2缓存256K
hw.l3cachesize: 6291456 // L3缓存6M
machdep.cpu.core_count: 4 // 4核
machdep.cpu.thread_count: 8

现在我们定义一个程序，有2个线程，两个变量a和b，线程1循环n次执行a++操作，线程2执行n次b++操作，我们用Go来描述：

type SimpleStruct struct {
	n int32
}

type PaddedStruct struct {
	n int32
	_ CacheLinePad
}

type CacheLinePad struct {
	_ [CacheLinePadSize]byte
}

const CacheLinePadSize = 64

const Num = 10000000

func BenchmarkSimple(b *testing.B) {
	structA := SimpleStruct{}
	structB := SimpleStruct{}
	wg := sync.WaitGroup{}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		wg.Add(2)
		go func() { // 为方便下文描述这个线程称为structA线程
			var j int32
			for j = 0; j < Num; j++ {
				structA.n += j
			}
			wg.Done()
		}()
		go func() { // 为方便下文描述这个线程称为structB线程
			var j int32
			for j = 0; j < Num; j++ {
				structB.n += j
			}
			wg.Done()
		}()
		wg.Wait()
	}
}

func BenchmarkSimplePad(b *testing.B) {
	structB := SimpleStruct{}
	structA := PaddedStruct{}
	wg := sync.WaitGroup{}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		wg.Add(2)
		go func() {
			var j int32
			for j = 0; j < Num; j++ {
				structA.n += j
			}
			wg.Done()
		}()
		go func() {
			var j int32
			for j = 0; j < Num; j++ {
				structB.n += j
			}
			wg.Done()
		}()
		wg.Wait()
	}
}

运行benchmark go test -bench=. 得到以下结果

可以看到我们只在结构体中加入了一个64字节的元素性能就得到了极大的提高，这是为什么呢？

我们看下Simple这个函数的代码，假设structA线程运行在core1上，structB线程运行在core2s上，假设structA线程先执行，它会将structA这个变量与structB一起加载到core1的L1的同一cacheline中，structB线程也会将structA这个变量与structB一起加载到core2的L1的同一cacheline，structA线程修改了structA的值，它会将这个事件同步到core2上，导致core2上cacheline失效，这时就需要从低一层存储中加载最新数据，然后structB又修改了structB，又导致了cacheline失效，循环往复导致了运行效率极低。

而SimplePad这个函数中structA中加入了cachelinesize个字节，使得structA和structB处于不同的cacheline上，也就避免了上面的问题。

2.1 题外话

关于多核间同步缓存我没有查到特别好的文章，所以我就不妄加解释了，如果你想深入研究的话可以搜索这个关键词：MESI协议
上面的实验代码来自于【译】CPU 高速缓存原理和应用。最初在我在做这个实验时，写的实验代码是这样的： var a int32 var pad [64]byte{} var b int32 ...

运行benchmark后发现运行时间并没有缩短，后来获取了a、pad、b的地址后才发现go将pad这个变量分配到了堆上，a和b两个变量在内存上还是紧挨着的，你做实验的话可以吸收这个经验：如果加上pad后发现运行时间没有缩短的话确认下a和b是不是真的被分隔到了两个cacheline上。