ICode9

精准搜索请尝试: 精确搜索
首页?>?其他分享> 文章详细

c – 为什么从多个线程使用相同的缓存行不会导致严重的减速?

2019-09-30 10:06:33??阅读:10??来源: 互联网

标签:c?performance?x86?multithreading


看看这个片段:

#include 
#include 

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 = 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的情况?四个内核在其缓存中具有相同的内存,因此它们必须以某种方式同步它们,不是吗?它们如何几乎完全平行运行?为什么原子案会严重减速?

我想我需要了解在这种情况下如何更新内存.最初,没有核心在缓存中有缓冲区.在迭代之后(在fn中),所有4个内核在其缓存行中都有缓冲区,但每个内核写入不同的字节.这些缓存行如何同步(在非原子情况下)?缓存如何知道哪个字节是脏的?还是有其他机制来处理这种情况?为什么这个机制比原子机器便宜得多(实际上,它几乎是免费的)?

解决方法:

您所看到的基本上是store-to-load forwarding的影响,允许每个核心大部分独立工作,尽管共享一个缓存行.正如我们将在下面看到的那样,真正的一个奇怪的情况是,更多的争用是不好的,直到某一点,然后更多的争论突然使事情变得非常快!

现在有了传统的争用观点,你的代码看起来像是一个高争用的东西,因此比理想慢得多.但是,当每个内核在其写缓冲区中获得单个挂起写入时,会发生以下所有后续读取都可以从写入缓冲区(存储转发)中得到满足,稍后写入也会进入缓冲区.这将大部分工作转变为完全本地化的操作.高速缓存行仍在核心之间反弹,但它与核心执行路径分离,只需要实际提交存储然后1.

std :: atomic版本根本不能使用这种魔法,因为它必须使用锁定操作来维持原子性并打败存储缓冲区,因此您既可以看到争用的全部成本,也可以看到长延迟原子操作的成本2.

让我们试着收集一些证据证明这是正在发生的事情.下面的所有讨论都涉及使用volatile来强制从缓冲区读取和写入的基准测试的非原子版本.

让我们先检查一下装配,确保它符合我们的期望:

0000000000400c00 :
  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 
  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->存储 – >加载…依赖.这个新代码打破了这个链条!负载不再依赖于存储,因此我们几乎可以并行执行所有操作,并且我希望这个循环每次迭代运行大约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

因此,每次迭代约为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)         #    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倍,很好地解释了性能下降,并且与存储到负载转发无法隐藏争用的想法一致,未命中将增加很多.

增加商店之间的距离

另一种方法是增加商店与后续负载之间的时间/指令距离.我们可以通过在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的SPAN并行依赖,所以在上面的情况下你可能会期望性能提高4倍,因为4个并行链可以进行大约4倍的处理.总吞吐量.

这是我们实际获得的1个线程和3个线程4的时间(以周期测量),SPAN值从1到20:

Time vs Increment Distable

最初,您会发现单线程和多线程情况下性能都会大幅提升;从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]++;
        }
    }
}

bash脚本为所有SPAN值从1到20运行perf:

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个核心可以减少噪声.以周期测量时间也有很大帮助.



标签:c,performance,x86,multithreading

专注分享技术,共同学习,共同进步。侵权联系[admin#icode9.com]

Copyright (C)ICode9.com, All Rights Reserved.

ICode9版权所有