为什么从多个线程使用相同的缓存行不会导致严重的减速？
gez*_*eza 21 c++ performance x86 multithreading
看看这个片段:
#include <atomic>
#include <thread>
typedef volatile unsigned char Type;
// typedef std::atomic_uchar Type;
void fn(Type *p) {
for (int i=0; i<500000000; i++) {
(*p)++;
}
}
int main() {
const int N = 4;
std::thread thr[N];
alignas(64) Type buffer[N*64];
for (int i=0; i<N; i++) {
thr[i] = std::thread(&fn, &buffer[i*1]);
}
for (int i=0; i<N; i++) {
thr[i].join();
}
}
这个小程序从四个不同的线程中多次增加四个相邻的字节.在此之前,我使用了以下规则:不要使用来自不同线程的相同缓存行,因为缓存线共享不好.所以我期望四线程版本(N=4)比一个线程版本(N=1)慢得多.
但是,这些是我的测量结果(在Haswell CPU上):
- N = 1:1秒
- N = 4:1.2秒
所以N=4速度并不慢.如果我使用不同的缓存行(替换*1为*64),则会N=4变得更快:1.1秒.
原子访问的相同度量(交换注释typedef),相同的缓存行:
- N = 1:3.1秒
- N = 4:48秒
所以N=4情况要慢得多(正如我预期的那样).如果使用不同的缓存行,则N=4具有类似的性能N=1:3.3秒.
我不明白这些结果背后的原因.为什么我不能严重减慢非原子的N=4情况呢？四个内核在其缓存中具有相同的内存,因此它们必须以某种方式同步它们,不是吗？它们如何几乎完全平行运行？为什么原子案会严重减速？
我想我需要了解在这种情况下如何更新内存.最初,buffer缓存中没有核心.在一次for迭代(in fn)之后,所有4个内核都buffer在其缓存行中,但每个内核写入不同的字节.这些缓存行如何同步(在非原子情况下)？缓存如何知道哪个字节是脏的？还是有其他机制来处理这种情况？为什么这个机制比原子机器便宜得多(实际上,它几乎是免费的)？
Bee*_*ope 25
您所看到的基本上是存储到转发转发的影响,允许每个核心大部分独立工作,尽管共享一个缓存行.正如我们将在下面看到的那样,真正的一个奇怪的情况是,更多的争用是不好的,直到某一点,然后更多的争论突然使事情变得非常快!
现在有了传统的争用观点,你的代码看起来像是一个高争用的东西,因此比理想慢得多.但是,只要每个内核在其写缓冲区中获得单个挂起写入,就会从写缓冲区(存储转发)中满足所有后续读取,并且稍后写入也会进入缓冲区.这将大部分工作转变为完全本地化的操作.高速缓存行仍然在核心之间反弹,但是它与核心执行路径分离,只需要实际提交商店然后1.
该std::atomic版本不能使用这个魔法可言,因为它有使用lockED的操作来维护原子性和战胜存储缓冲区,所以你看到的争夺双方的全部费用,并长期潜伏原子操作的成本2.
让我们试着收集一些证据证明这是正在发生的事情.下面的所有讨论都涉及用于强制读取和写入atomic的基准测试的非版本.volatilebuffer
让我们先检查一下装配,确保它符合我们的期望:
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) # 0.998 CPUs utilized
2,775,874,257 cycles # 2.594 GHz
2,504,256,018 instructions # 0.90 insn per cycle
501,139,187 L1-dcache-loads # 468.272 M/sec
69,351 L1-dcache-load-misses # 0.01% of all L1-dcache hits
1.072119673 seconds time elapsed
这是我们所期望的:基本上零L1D未命中(总数的0.01%,可能主要来自中断和循环外的其他代码),仅超过500,000,000次点击(我们循环的次数).另请注意,我们可以轻松计算每个循环的cyles:大约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) # 3.773 CPUs utilized
15,356,014,570 cycles # 2.594 GHz
10,012,249,418 instructions # 0.65 insn per cycle
2,003,487,964 L1-dcache-loads # 338.384 M/sec
61,450,818 L1-dcache-load-misses # 3.07% of all L1-dcache hits
1.569040529 seconds time elapsed
正如预期的那样,L1负载从5亿增加到20亿,因为有4个线程各自负载5亿个负载.L1D 未命中数也增加了约1,000倍,达到约6,000万.尽管如此,这个数字与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) # 0.989 CPUs utilized
826,349,333 cycles # 2.593 GHz
2,503,706,989 instructions # 3.03 insn per cycle
500,973,018 L1-dcache-loads # 1571.815 M/sec
63,507 L1-dcache-load-misses # 0.01% of all L1-dcache hits
0.322146774 seconds time elapsed
因此,每次迭代3约为1.65个周期,比增加相同位置快约三倍.
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) # 3.469 CPUs utilized
57,834,005,721 cycles # 2.593 GHz
10,038,366,836 instructions # 0.17 insn per cycle
2,011,160,602 L1-dcache-loads # 90.188 M/sec
237,664,926 L1-dcache-load-misses # 11.82% of all L1-dcache hits
6.428730614 seconds time elapsed
所以它比同一个位置情况慢大约4倍.现在,它不是比单线程情况慢一点,而是慢了大约20倍.这是你一直在寻找的争论!现在,L1D未命中的数量也增加了4倍,很好地解释了性能下降,并且与存储到转发无法隐藏争用的想法一致,未命中将会增加很多.
增加商店之间的距离
另一种方法是增加商店与后续负载之间的时间/指令距离.我们可以通过增加方法中的SPAN连续位置来完成此操作fn(),而不是始终使用相同的位置.例如,如果SPAN是4,则连续增加4个位置,如:
for (long i=0; i<500000000 / 4; i++) {
p[0]++;
p[1]++;
p[2]++;
p[3]++;
}
请注意,我们仍在增加5亿个位置,只是在4个字节之间扩展增量.直观地说,你会期望整体性能提高,因为你现在有SPAN长度的并行依赖性1/SPAN,所以在上面的情况下你可能会期望性能提高4倍,因为4个并行链可以以总吞吐量的大约4倍进行.
这是我们实际获得的1个线程和3个线程4的时间(以周期测量),对于SPAN1到20的值:
最初,您会发现单线程和多线程情况下性能都会大幅提升; SPAN对于两种情况,在完全平行的情况下,从1到2和3 的增加接近理论预期.
单线程案例的渐近线比单一位置写入速度快4.25倍:此时存储转发延迟不是瓶颈而且其他瓶颈已经接管(主要是最大IPC和存储端口争用).
然而,多线程的情况非常不同!一旦你达到SPAN7左右,性能会迅速恶化,比SPAN=1情况差大约2.5倍,比最佳性能差几乎10倍SPAN=5.发生的情况是,存储到加载转发停止发生,因为存储和后续加载在商店退役到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为SPAN1到20的所有值运行的bash脚本:
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亿,我想这就是你会发现的.
通过一些更聪明的递增,您甚至可以让每个线程跟踪它们递增的值来自它们的最后一个增量而不是另一个线程递增的频率(例如,通过使用该值的几个位来存储线程标识符).通过更加巧妙的测试,您几乎可以重建高速缓存线在核心之间移动的方式(例如,核心A是否更愿意切换到核心B？)以及哪些核心对最终值贡献最大,等等
这一切都留作练习:).
1最重要的是,如果英特尔有一个合并存储缓冲区,后面的存储与先前的存储完全重叠,则会杀死早期存储,每次获取该行时,它只需要向L1(最新存储)提交一个值.
2你不能在这里真正区分这两种效果,但我们稍后会通过击败存储到转发转发来实现.
3比我预期的要多一点,也许糟糕的调度会导致港口压力.如果gcc只是所有sub和jne融合,它每次迭代运行1.1个周期(仍然比我期望的1.0差).这将是我用-march=haswell而不是,-march=native但我不会回去改变所有的数字.
4结果也支持4个线程:但我只有4个核心,我在后台运行像Firefox这样的东西,所以使用1个核心可以减少测量噪音.以周期测量时间也有很大帮助.