你所看到的基本上是存储缓冲区与
存储器到加载器转发相结合的效果,使每个内核在共享高速缓存线路的情况下可以独立工作。正如我们将在下面看到的那样,这确实是一个奇怪的情况,在某种程度上更多的争用是不好的,然后
更多的争用突然使事情变得非常快!
现在,根据争用的传统观点,你的代码似乎会有很高的争用,因此比理想状态下要慢得多。然而,当每个内核在其写入缓冲区中获得单个待处理写入时,所有后续读取都可以从写入缓冲区中满足(存储器转发),稍后的写入也只是进入缓冲区,即使内核已经失去了高速缓存线路的所有权。这使大部分工作成为完全的本地操作。高速缓存线路仍然在内核之间反弹,但它已经与内核执行路径解耦,并且只需要偶尔实际提交存储器。
std::atomic
版本根本无法使用这种魔法,因为它必须使用
lock
操作来维护原子性并打败存储缓冲区,因此你会看到争用的全部代价
和长延迟原子操作的代价。
让我们试着收集一些证据来证明这是正在发生的事情。以下所有讨论都涉及不使用
atomic
的基准测试版本,该版本使用
volatile
强制从
buffer
读取和写入。
让我们先检查汇编代码,确保它符合我们的预期:
0000000000400c00 <fn(unsigned char volatile*)>:
400c00: ba 00 65 cd 1d mov edx,0x1dcd6500
400c05: 0f 1f 00 nop DWORD PTR [rax]
400c08: 0f b6 07 movzx eax,BYTE PTR [rdi]
400c0b: 83 c0 01 add eax,0x1
400c0e: 83 ea 01 sub edx,0x1
400c11: 88 07 mov BYTE PTR [rdi],al
400c13: 75 f3 jne 400c08 <fn(unsigned char volatile*)+0x8>
400c15: f3 c3 repz ret
这很简单:一个包含五个指令的循环,其中包括一个字节加载、加载字节的增量、一个字节存储以及循环增量和有条件跳回顶部。在这里,gcc错过了一个优化机会,通过分离
sub
和
jne
来阻止宏融合,但总体而言还是可以的,而且存储转发延迟在任何情况下都会限制循环。
接下来,让我们看一下L1D缺失的数量。每当一个核心需要写入被夺走的行时,它将遭受L1D缺失,我们可以使用
perf
进行测量。首先,考虑单线程(
N=1
)的情况:
$ perf stat -e task-clock,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses ./cache-line-increment
Performance counter stats for './cache-line-increment':
1070.188749 task-clock (msec)
2,775,874,257 cycles
2,504,256,018 instructions
501,139,187 L1-dcache-loads
69,351 L1-dcache-load-misses
1.072119673 seconds time elapsed
这篇文章主要讲述的是我们对于期望结果的预测:基本上没有 L1D 缺失(总共 0.01%,可能大部分来自中断和循环外的其他代码),以及略多于 5 亿次命中(几乎完全匹配循环迭代次数)。注意,我们可以轻松计算每次迭代的周期数:大约是 5.5 的五次方。这主要反映了存储到加载转发的成本,再加上一个用于增量的周期,由于同一位置被重复更新而形成了一个传递依赖链(并且 volatile 意味着它不能提升到寄存器中)。
现在让我们看看当 N=4 时的情况:
$ perf stat -e task-clock,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses ./cache-line-increment
Performance counter stats for './cache-line-increment':
5920.758885 task-clock (msec)
15,356,014,570 cycles
10,012,249,418 instructions
2,003,487,964 L1-dcache-loads
61,450,818 L1-dcache-load-misses
1.569040529 seconds time elapsed
作为预期,由于有4个线程每个线程都做500百万次加载,L1负载从5亿跳到了20亿。 L1D缺失的数量也增加了约1000倍,达到约6000万。尽管如此,与20亿次加载(和20亿次存储-未显示,但我们知道它们存在)相比,这个数字并不多。这是每个缺失的约33次加载和33次存储。这也意味着每个缺失之间有250个周期。
这并不真正符合缓存行在核心之间错误地弹跳的模型,其中一旦一个核心获得该行,另一个核心就要求它。我们知道,在共享L2的核心之间,线路在大约20-50个周期内反弹,因此每250个周期有一个缺失的比率似乎太低了。
两个假设
上述行为引发了几个想法:
也许这个芯片中使用的MESI协议变种是“智能”的,并且识别出在多个核心中有一行是热点,但每次核心获取锁并且该行花费更多时间在L1和L2之间移动而不是实际满足某些核心的负载和存储时,某些智能组件在一致性协议中决定强制执行某种最小“所有权时间”:在一个核心获取该行后,即使另一个核心要求(其他核心只需等待),它也将保留N个周期。这将有助于平衡缓存行乒乓的开销与实际工作量,代价是牺牲了其他核心的“公平性”和响应能力,就像不公平锁和公平锁之间的权衡,以及抵消
此处描述的效果,在这里,一致性协议越快速和公平,某些(通常是合成的)循环表现得越差。我从未听说过这样的事情(并且前面的链接显示至少在Sandy-Bridge时代,事情正在朝着相反的方向发展),但这当然是可能的!
所述的存储缓冲区效应确实发生了,因此大多数操作几乎可以在本地完成。
让我们尝试通过一些修改来区分两种情况。
显而易见的方法是改变
fn()
工作函数,使线程仍然争夺同一缓存行,但无法触发存储转发。我们读取位置
x
,然后写入位置
x+1
怎么样?我们给每个线程两个连续的位置(即,
thr [i] = std :: thread(&fn,&buffer [i * 2])
),这样每个线程操作两个私有字节。修改后的
fn()
如下:
for (int i=0; i<500000000; i++)
unsigned char temp = p[0];
p[1] = temp + 1;
}
核心循环与早期版本基本相同:
400d78: 0f b6 07 movzx eax,BYTE PTR [rdi]
400d7b: 83 c0 01 add eax,0x1
400d7e: 83 ea 01 sub edx,0x1
400d81: 88 47 01 mov BYTE PTR [rdi+0x1],al
400d84: 75 f2 jne 400d78
唯一变化的是我们现在写入
[rdi+0x1]
而不是
[rdi]
。
正如我上面提到的,原始(相同位置)循环即使在最佳单线程情况下也运行得非常慢,每次迭代大约需要5.5个周期,因为循环传递的
load->add->store->load...
依赖关系。这段新代码打破了这个链条!加载不再依赖存储,因此我们可以几乎并行执行所有操作,我预计这个循环每次迭代将运行约1.25个周期(5条指令/CPU宽度为4)。
以下是单线程情况:
$ perf stat -e task-clock,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses ./cache-line-increment
Performance counter stats for './cache-line-increment':
318.722631 task-clock (msec)
826,349,333 cycles
2,503,706,989 instructions
500,973,018 L1-dcache-loads
63,507 L1-dcache-load-misses
0.322146774 seconds time elapsed
关于每次迭代1.65个周期3左右,相比于在同一位置递增,速度约为三倍。
那么4个线程呢?
$ perf stat -e task-clock,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses ./cache-line-increment
Performance counter stats for './cache-line-increment':
22299.699256 task-clock (msec)
57,834,005,721 cycles
10,038,366,836 instructions
2,011,160,602 L1-dcache-loads
237,664,926 L1-dcache-load-misses
6.428730614 seconds time elapsed
所以它比相同位置情况
慢了大约4倍。现在,与单线程情况相比,它慢了约
20倍。这就是你一直在寻找的争用!现在还要注意,L1D缺失的数量也增加了4倍,很好地解释了性能下降,并且与当存储器到加载器无法隐藏争用时,缺失会大量增加的想法一致。
增加存储之间的距离
另一种方法是增加存储和随后加载之间的时间/指令距离。我们可以通过在fn()
方法中递增SPAN
个位置,而不总是相同的位置来实现这一点。例如,如果SPAN
为4,则连续递增4个位置,如下所示:
for (long i=0; i<500000000 / 4; i++) {
p[0]++;
p[1]++;
p[2]++;
p[3]++;
}
请注意,我们仍然在总共增加5亿个位置,只是将增量分散在4个字节中。 直观地说,您会期望整体性能提高,因为现在您具有长度为1 / SPAN的
并行依赖,因此在上面的情况下,您可能会期望性能提高4倍,因为4个并行链可以以大约4倍的总吞吐量进行处理。以下是我们实际获得的时间(以周期为单位)的结果,其中1线程和3线程
4,
SPAN值从1到20:
![Time vs Increment Distable](https://istack.dev59.com/OvQo0.webp)
最初,您可以在单线程和多线程情况下看到性能显著提高;从一个SPAN
到两个和三个的增加接近于理论上完美并行情况下的预期,对于这两种情况。
单线程情况下,速度达到了大约比单位置写入快4.25倍的渐近值:此时存储转发延迟不是瓶颈,而其他瓶颈已经占据主导地位(主要是最大IPC和存储端口争用)。
然而,多线程情况非常不同!一旦您达到约7的SPAN
,性能迅速变差,水平稳定在比SPAN=1
情况差2.5倍左右,并且与SPAN=5
的最佳性能相比几乎差10倍。发生的情况是存储到加载转发停止,因为存储和随后的加载在时间/周期上相距足够远,以至于存储已退役到L1,因此加载实际上必须获取该行并参与MESI。
还绘制了L1D缺失,如上所述,这表明核心之间的“高速缓存行传输”。单线程情况下基本上为零,并且与性能不相关。然而,多线程情况的性能几乎完全跟踪缓存未命中。在SPAN
值在2到6范围内,仍在工作的存储转发比例较少。显然,核心能够在每个高速缓存行传输之间“缓冲”更多的存储,因为核心循环更快。
另一种思考方式是,在争用情况下,每单位时间 L1D 未命中基本上是恒定的(这是有道理的,因为它们基本上与 L1->L2->L1 的延迟以及某些一致性协议开销相关),因此您可以在缓存线传输之间完成更多工作,从而更好地利用资源。
这是多跨度情况下的代码:
void fn(Type *p) {
for (long i=0; i<500000000 / SPAN; i++) {
for (int j = 0; j < SPAN; j++) {
p[j]++;
}
}
}
运行 perf
的bash脚本,对所有 SPAN
值从1到20进行测试:
PERF_ARGS=${1:--x, -r10}
for span in {1..20}; do
g++ -std=c++11 -g -O2 -march=native -DSPAN=$span cache-line-increment.cpp -lpthread -o cache-line-increment
perf stat ${PERF_ARGS} -e cycles,L1-dcache-loads,L1-dcache-load-misses,machine_clears.count,machine_clears.memory_ordering ./cache-line-increment
done
最后,将结果“转置”为适当的CSV格式:
FILE=result1.csv; for metric in cycles L1-dcache-loads L1-dcache-load-misses; do { echo $metric; grep $metric $FILE | cut -f1 -d,; } > ${metric}.tmp; done && paste -d, *.tmp
最终测试
有一个最终测试可以证明每个核心有效地完成了大部分私有工作:使用线程在相同位置上工作的基准版本(这不会改变性能特征),检查最终计数器值的总和(您需要 int
计数器而不是 char
)。如果一切都是原子的,您将得到 20 亿的总和,而在非原子情况下,总和接近该值的程度是衡量核心传递行的频率的粗略指标。如果核心几乎完全独立工作,则该值将接近 5 亿而不是 20 亿,我想这就是您会发现的(一个与 5 亿相当接近的值)。
通过更聪明的增量操作,您甚至可以让每个线程跟踪它们增加的值来自其上次增加而不是另一个线程的增加(例如,通过使用一些值的位来存储线程标识符)。通过更聪明的测试,您甚至可以实际重建缓存行在核心之间移动的方式(是否有模式,例如核心 A 更喜欢移交给核心 B?)以及哪些核心对最终值做出了最大贡献等。
所有这些都留作练习 :)
1 此外,如果英特尔拥有一个合并存储缓冲区,在此缓冲区中,后面的存储完全覆盖了早期的存储,则每次获取该行时,它只需要提交一个值到L1(最新的存储)。
2 在这里,您无法真正分离这两个效果,但我们稍后将通过打败存储到加载转发来解决这个问题。
3 比我预期的要多一点,可能是糟糕的调度导致端口压力。如果gcc
只需将所有sub
和jne
融合在一起,它以每次迭代1.1个周期运行(仍然比我期望的1.0差)。如果我使用-march = haswell
而不是-march = native
,它会这样做,但我不打算回去更改所有数字。
4 结果在4个线程下也成立:但我只有4个核心,并且我在后台运行像Firefox之类的东西,因此使用1个较少的核心使测量数据变得不那么嘈杂。用周期测量时间也很有帮助。
5 在此CPU架构上,存储转发,在加载到达之前存储数据已准备好似乎在4个和5个周期之间交替出现,平均为4.5个周期。