c++ - 为什么从多个线程使用相同的缓存行不会导致严重的速度下降？

Question

看一下这段代码:

#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迭代之后(在 fn中)，所有4个内核在其缓存行中都具有 buffer，但是每个内核写入一个不同的字节。这些高速缓存行如何同步(在非原子情况下)？缓存如何知道哪个字节是脏的？还是有其他机制可以处理这种情况？为什么这种机制比原子一便宜很多(实际上，它几乎是免费的)？

Answer 1

您所看到的基本上是存储缓冲区与store-to-load forwarding组合所产生的效果，尽管共享了缓存行，但每个核心仍可以独立工作。正如我们将在下面看到的，这确实是奇怪的情况，其中更多的争用是不好的，直到某个点，然后更多的争用突然使事情变得非常快!
现在，使用传统的争用 View ，您的代码似乎将具有很高的争用性，因此比理想情况要慢得多。但是，发生的情况是，每个内核在其写缓冲区中获得单个挂起的写操作后，就可以从写缓冲区中满足所有以后的读操作(存储转发)，并且即使在写操作完成之后，以后的写操作也才进入缓冲区。核心已失去对缓存行的所有权。这将大部分工作变成了完全本地化的操作。高速缓存行仍在内核之间跳动，但已与内核执行路径脱钩，仅需要不时地实际提交存储。std::atomic版本根本无法使用此魔术，因为它必须使用lock ed操作来维护原子性并破坏存储缓冲区，因此您可以看到争用的全部成本和长等待时间原子操作的成本2。
让我们尝试实际收集一些证据，证明这是正在发生的事情。下面的所有讨论都针对基准测试的非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)         #    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(几乎完全匹配循环迭代的次数)。还要注意，我们可以轻松计算每次迭代的周期:大约5.55。这主要反射(reflect)了存储到装载转发的成本，外加一个周期的增量，这是一个携带的依赖链，因为同一位置被重复更新(并且 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失误的数量也增加了约1000倍，达到约6000万。不过，与20亿个负载(和20亿个商店-未显示，但我们知道它们在那里)相比，这个数字并不多。大约有33个加载项，每个未命中的存储约为33个。这也意味着每个未命中之间有250个循环。
这确实不适合高速缓存行的模型在内核之间不规则地跳动，在这种情况下，只要有内核获得该行，另一个内核就会要求它。我们知道，在共享L2的内核之间，线路会在大约20-50个周期内反弹，因此，每250个周期一次未命中的比率似乎很低。
两个假设
对于上述行为，有两个想法浮现在脑海:

也许此芯片中使用的MESI协议(protocol)变体是“智能的”，并认识到多个内核中的一条线路很热，但是每次内核获得锁定时，仅需做少量工作，而线路在此之间花费了更多时间L1和L2比实际满足某些核心的负载和存储要大。鉴于此，一致性协议(protocol)中的某个智能组件决定为每条线路强制执行某种最小的“所有权时间”:一个核心获得该线路后，它将保持N个周期，即使另一个核心(其他核心只需要等待)。
这将有助于平衡高速缓存行乒乓球与实际工作之间的开销，但要以“公平”和其他核心的响应为代价，就像在不公平和公平锁之间进行权衡，并抵消described here的影响一样，一致性协议(protocol)越快越公平，某些(通常是合成的)循环执行的效果就越差。
现在，我从未听说过这样的事情(并且上一链接显示，至少在桑迪·布里奇时代，事情正朝相反的方向发展)，但这肯定是有可能的!

所描述的存储缓冲区效应实际上正在发生，因此大多数操作几乎都可以在本地完成。

一些测试
让我们尝试通过一些修改来区分两种情况。
读写不同的字节
一种明显的方法是更改​​ fn()工作函数，以便线程仍在同一高速缓存行上竞争，但是无法进行存储转发。
我们只是从 x位置读取然后写入 x + 1怎么样？我们将为每个线程提供两个连续的位置(即 thr[i] = std::thread(&fn, &buffer[i*2]))，以便每个线程都对两个私有(private)字节进行操作。修改后的 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]。
现在，如上所述，即使是在最佳情况下的单线程情况下，由于循环承载的 load->add->store->load...依赖性，原始(相同位置)循环实际上也相当缓慢地运行，每次迭代大约需要5.5个周期。这段新代码打破了这一链条!负载不再取决于存储，因此我们几乎可以并行执行所有操作，我希望此循环每次迭代大约运行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个周期，比增加同一位置要快大约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倍，很好地解释了性能下降，并且与以下想法一致:当存储到负载转发无法隐藏竞争时，丢失的数量会大大增加。
加大商店之间的距离
另一种方法是增加存储与后续负载之间的时间/指令距离。我们可以通过在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，以及从1到20的SPAN值，这是我们实际获得的时间(以周期为单位):

最初，您发现单线程和多线程情况下的性能都大大提高；从SPAN的1增加到2和3，这与两种情况下完全并行的情况下的理论值接近。
单线程的情况比单位置写入的渐近速度快约4.25倍:在这一点上，存储转发延迟不是瓶颈，而其他瓶颈也已被接管(最大IPC和存储端口争用)。
但是，多线程的情况却大不相同!一旦您达到约7的SPAN，性能就会迅速变差，变平，约为SPAN=1情况的2.5倍，比SPAN=5的最佳性能差近10倍。发生的事情是，存储到负载的转发停止发生，因为存储和后续负载在时间/周期上相距足够远，以致于该存储已退休到L1，因此负载实际上必须获得线路并参与MESI。
还绘制了L1D未命中，如上所述，L1D未命中指示核之间的“高速缓存线转移”。单线程情况基本上为零，并且它们与性能无关。但是，多线程情况的性能几乎可以准确地跟踪高速缓存未命中的情况。如果SPAN值在2到6的范围内(存储转发仍在起作用)，则按比例减少了未命中的次数。显然，由于核心循环更快，因此核心能够在每个高速缓存行传输之间“缓冲”更多的存储。
另一种思考的方式是，在有争议的情况下，L1D丢失在单位时间内基本上是恒定的(这是有道理的，因为它们基本上与L1-> L2-> L1延迟相关联，并加上一些一致性协议(protocol)开销)，因此在两次高速缓存行传输之间可以做的工作越多，效果越好。
这是跨跨案例的代码:

void fn(Type *p) {
    for (long i=0; i<500000000 / SPAN; i++) {
        for (int j = 0; j < SPAN; j++) {
            p[j]++;
        }
    }
}

bash脚本，用于从1到20的所有perf值运行SPAN:

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亿美元的总和，而在非原子的情况下，总数与该值的接近程度可以粗略地衡量核心绕线通过的频率。如果核心几乎完全在私下工作，则值(value)将接近5亿，而不是20亿，我想这就是您会发现的(值(value)接近5亿)。
有了一些更聪明的增量，您甚至可以让每个线程跟踪它们递增的值多久一次来自其上一个增量，而不是另一个线程增量(例如，通过使用该值的一些位来存放线程标识符)。通过更加巧妙的测试，您几乎可以重建高速缓存线在内核之间移动的方式(是否存在某种模式，例如，内核A是否愿意移交给内核B？)，以及哪些内核对最终值的贡献最大，等等。
剩下的都是练习:)。

1最重要的是，如果Intel有一个合并的存储缓冲区，与早期存储区完全重叠的后来存储区将杀死早期存储区，则它每次上线时只需向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个周期。