原子操作成本

Question

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

缓存有什么影响？

我对现代流行的CPU感兴趣:x86,x86_64,PowerPC,SPARC,Itanium.

Answer 1

我查了过去几天的实际数据,一无所获.但是,我做了一些研究,将原子操作的成本与缓存未命中的成本进行了比较.

在x86 LOCK前缀,或CAS的成本,PentiumPro(如文档中所述)之前,是一个内存访问(如高速缓存未命中),+其它处理器停止存储器操作,+与其他处理器尝试锁定任何争总线.但是,由于PentiumPro,对于Writeback(即可缓存)内存(应用程序处理的所有内存,除非您直接与硬件通信),而不是阻止所有内存操作,只有相关的缓存行被阻止(基于上面发布的链接).

实际上,CAS案例可能会更复杂,如本页所述,没有时间限制,但值得信赖的工程师进行深刻的描述.

去之前太多的细节,我会说是被锁定的操作成本的一种高速缓存未命中+可能的竞争与同一缓存行的其它处理器,而CAS +前面的负载(这几乎总是需要除了在互斥,在那里你总是CAS 0和1)可能花费两次缓存未命中.

他解释说,单个位置上的加载+ CAS实际上可能花费两次缓存未命中,例如Load-Linked/Store-Conditional(参见后者).他的解释依赖于MESI缓存一致性协议的知识.它使用4个状态作为高速缓存行:M(odified),E(xclusive),S(hared),I(nvalid)(因此它被称为MESI),在需要时在下面解释.解释的场景如下:

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

在所有情况下,已经修改数据的其他处理器可以阻止高速缓存行请求.

Answer 2

我通过以下设置进行了一些分析:测试机器(AMD Athlon64 x2 3800+)启动,切换到长模式(中断禁用),感兴趣的指令在循环中执行,100次迭代展开和1,000次循环.循环体对齐到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#。它将禁止总线上的其他CPU/设备使用它。

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/读-修改-写=原子本身/指令确保处理器在执行锁定指令之前先执行所有指令。/关于尚未刷新的写入/它强制在执行下一条指令之前将处理器内的所有已发布写入刷新到外部存储器。

/about SMP/ 信号量处于 S 状态的高速缓存中...发出 0 字节日期的读取和无效事务（这是相邻 CPU 中高速缓存行的共享副本的终止/）