原子操作成本

Question

原子操作(比较并交换或原子加/减)的成本是多少？它消耗了多少周期？它会暂停SMP或NUMA上的其他处理器，还是会阻止内存访问？它会刷新乱序CPU中的重新排序缓冲区吗？

对缓存有什么影响？

我对现代流行的CPU很感兴趣: x86、x86_64、PowerPC、SPARC、安腾。

Answer 1

我已经查找了过去几天的实际数据，但什么也没有找到。但是，我做了一些研究，将原子操作的成本与缓存未命中的成本进行了比较。

x86锁前缀(包括用于原子CAS的lock cmpxchg )在PentiumPro之前(如文档中所述)的成本是内存访问(如缓存未命中)，+停止其他处理器的内存操作，+与试图锁定总线的其他处理器的任何争用。然而，由于PentiumPro对于正常的回写可缓存内存(应用程序处理的所有内存，除非您直接与硬件对话)，而不是阻塞所有内存操作，只有相关的缓存线被阻塞(基于@osgx's answer中的链接)。

即，核心延迟对该行的MESI共享和RFO请求的应答，直到实际locked操作的存储部分之后。这被称为“高速缓存锁”，并且只影响那一条高速缓存线。其他内核可以加载/存储，甚至可以同时CASing其他线路。

实际上，中科院的案例可以更复杂，正如this page上解释的那样，没有时间，但由值得信赖的工程师进行了有洞察力的描述。(至少对于在实际CAS之前执行纯加载的正常用例是这样的。)

在进入更多细节之前，我要说的是，LOCKed操作耗费一次缓存未命中加上与同一缓存行上其他处理器的可能争用，而CAS +前面的加载(除了互斥，在互斥上几乎总是需要的，在互斥上总是CAS0和1)可能会耗费两次缓存未命中。

他解释说，单个位置上的load + CAS实际上会消耗两个缓存未命中，比如Load-Linked/Store-Conditional (参见后者)。他的解释依赖于MESI cache coherence protocol的知识。它对缓存线使用4种状态: M(odified)，E(xclusive)，S(hared)，i(无效)(因此称为MESI)，在下面需要的地方进行了解释。以下是对场景的解释：

• 加载导致缓存未命中-相关的缓存行是在共享状态下从内存中加载的(即，其他处理器仍被允许将该缓存行保留在内存中；在此状态下不允许更改)。如果该位置在内存中，则跳过此缓存未命中。可能的成本:1高速缓存未命中。(如果高速缓存行处于共享、独占或修改状态，即数据在此CPU的L1高速缓存中，则跳过)。
• 程序计算要存储的新值，
• ，并运行原子CAS指令。
  • 它必须避免并发修改，因此它必须从其他CPU的缓存中删除缓存行的副本，以将缓存行移动到独占状态。可能的成本:1缓存未命中。如果它已经是独占的，即处于独占或已修改状态，则不需要此操作。在这两种状态下，没有其他CPU持有缓存行，但在独占状态下，它还没有被修改。
  • 在这次通信之后，变量在我们的CPU的本地缓存中被修改，此时它对所有其他CPU都是全局可见的(因为它们的缓存与我们的一致)。根据通常的algorithms.
  • Other处理器尝试读取或修改该变量将首先必须以共享或独占模式获得该缓存行，并且为了这样做将联系该处理器并接收该缓存行的更新版本，它最终将被写入主存储器。相反，LOCKed操作只能消耗缓存未命中的成本(因为将在独占state).

中直接请求缓存行

在所有情况下，缓存行请求都可以被已经修改数据的其他处理器停止。

Answer 2

我使用以下设置进行了一些分析:启动测试机器(AMD Athlon64 x2 3800+)，切换到长模式(禁用中断)，在循环中执行感兴趣的指令，展开100次迭代和1000个循环周期。循环体与16个字节对齐。在循环之前和之后使用rdtsc指令测量时间。此外，执行一个没有任何指令的虚拟循环(每次循环迭代测量2个周期，其余循环测量14个周期)，并从指令剖析时间的结果中减去结果。

测量了以下说明：

• "lock cmpxchg [rsp - 8], rdx“(同时具有比较匹配和不匹配)、
• "lock xadd [rsp - 8], rdx"，
• "lock bts qword ptr [rsp - 8], 1"

在所有情况下，测量的时间约为310个周期，误差约为+/- 8个周期

这是在同一(缓存)内存上重复执行的值。有了额外的缓存未命中，时间就会大大增加。此外，这是在两个核心中只有一个处于活动状态的情况下完成的，因此缓存是独占的，不需要缓存同步。

为了评估缓存未命中时锁定指令的成本，我在锁定指令之前添加了wbinvld指令，并将wbinvld加上add [rsp - 8], rax放入比较循环中。在这两种情况下，每个指令对的成本约为80,000个周期！在锁定bts的情况下，每条指令的时间差约为180个周期。

请注意，这是倒数吞吐量，但由于锁定操作是序列化操作，因此延迟可能没有区别。

结论:锁定操作很繁重，但缓存未命中可能要严重得多。另外:锁定操作不会导致缓存未命中。只有当缓存行不是独占时，它才会导致缓存同步流量。

为了引导这台机器，我使用了ReactOS项目中的x64版本的FreeLdr。下面是asm的源代码：

#define LOOP_COUNT 1000
#define UNROLLED_COUNT 100

PUBLIC ProfileDummy
ProfileDummy:

    cli

    // Get current TSC value into r8
    rdtsc
    mov r8, rdx
    shl r8, 32
    or r8, rax

    mov rcx, LOOP_COUNT
    jmp looper1

.align 16
looper1:

REPEAT UNROLLED_COUNT
    // nothing, or add something to compare against
ENDR

    dec rcx
    jnz looper1

    // Put new TSC minus old TSC into rax
    rdtsc
    shl rdx, 32
    or rax, rdx
    sub rax, r8

    ret

PUBLIC ProfileFunction
ProfileFunction:

    cli

    rdtsc
    mov r8, rdx
    shl r8, 32
    or r8, rax
    mov rcx, LOOP_COUNT

    jmp looper2

.align 16
looper2:

REPEAT UNROLLED_COUNT
    // Put here the code you want to profile
    // make sure it doesn't mess up non-volatiles or r8
    lock bts qword ptr [rsp - 8], 1
ENDR

    dec rcx
    jnz looper2

    rdtsc
    shl rdx, 32
    or rax, rdx
    sub rax, r8

    ret

Answer 3

在基于总线的SMP上，原子前缀LOCK确实断言(接通)总线线信号LOCK#。它将禁止总线上的其他cpus/设备使用它。

Ppro & P2图书http://books.google.com/books?id=3gDmyIYvFH4C&pg=PA245&dq=lock+instruction+pentium&lr=&ei=_E61S5ehLI78zQSzrqwI&cd=1#v=onepage&q=lock%20instruction%20pentium&f=false第244-246页

锁定指令正在序列化、同步操作.../about无序/锁定RMW/read-modify-write =原子本身/指令可确保处理器在执行锁定指令之前执行锁定指令之前的所有指令。/about尚未刷新写入/它强制在执行下一条指令之前将处理器内的所有已发送写入刷新到外部存储器。

/about SMP/信号量在缓存中处于S状态...针对0字节的数据发出读取和无效事务(这是相邻CPU中的高速缓存线的共享副本的终止/)