custo de operação atômica

Qual é o custo da operação atômica (qualquer um de comparar e trocar ou adicionar / decrementar atômico)? Quantos ciclos ele consome? Ele pausará outros processadores no SMP ou NUMA ou bloqueará os acessos à memória? Ele irá liberar o buffer de reordenamento na CPU fora de ordem?

Quais efeitos estarão no cache?

Estou interessado em CPUs modernas e populares: x86, x86_64, PowerPC, SPARC, Itanium.

Procurei dados reais nos últimos dias e não encontrei nada. No entanto, fiz algumas pesquisas que comparam o custo das operações atômicas com os custos dos erros de cache.

O custo do prefixo x86 LOCK, (incluindo lock cmpxchgpara CAS atômico), antes do PentiumPro (conforme descrito no documento), é um acesso à memória (como uma falha de cache), + interromper as operações de memória por outros processadores, + qualquer contenção com outros processadores tentando BLOQUEAR o ônibus. No entanto, desde o PentiumPro, para memória armazenável de Writeback normal (toda a memória com a qual um aplicativo lida, a menos que você converse diretamente com o hardware), em vez de bloquear todas as operações de memória, apenas a linha de cache relevante é bloqueada (com base no link na resposta de @osgx ) .

ou seja, o núcleo atrasa o atendimento das solicitações de compartilhamento MESI e RFO para a linha até depois da parte de armazenamento da lockoperação real ed. Isso é chamado de "bloqueio de cache" e afeta apenas aquela linha de cache. Outros núcleos podem carregar / armazenar ou até mesmo fazer o CASing de outras linhas ao mesmo tempo.

Na verdade, o caso do CAS pode ser mais complicado, conforme explicado nesta página , sem intervalos, mas com uma descrição criteriosa feita por um engenheiro confiável. (Pelo menos para o caso de uso normal em que você faz um carregamento puro antes do CAS real.)

Antes de entrar em muitos detalhes, direi que uma operação LOCKed custa um cache miss + a possível contenção com outro processador no mesmo cache, enquanto CAS + a carga anterior (que quase sempre é necessária, exceto em mutexes, onde você sempre CAS 0 e 1) podem custar dois erros de cache.

Ele explica que uma carga + CAS em um único local pode, na verdade, custar duas perdas de cache, como Load-Linked / Store-Conditional (veja a última opção aqui). Sua explicação se baseia no conhecimento do protocolo de coerência do cache MESI . Ele usa 4 estados para um cacheline: M (odificado), E (xclusivo), S (hared), I (nválido) (e portanto é chamado de MESI), explicado abaixo quando necessário. O cenário, explicado, é o seguinte:

• o LOAD causa uma perda de cache - o cacheline relevante é carregado da memória no estado Compartilhado (ou seja, outros processadores ainda podem manter esse cache na memória; nenhuma alteração é permitida neste estado). Se o local estiver na memória, essa perda de cache será ignorada. Custo possível: 1 falha de cache. (ignorado se o cacheline estiver no estado Compartilhado, Exclusivo ou Modificado, ou seja, os dados estão no cache L1 desta CPU).
• o programa calcula os novos valores para armazenar,
• e executa uma instrução CAS atômica.
  • Ele deve evitar modificações simultâneas, portanto, deve remover cópias do cacheline do cache de outras CPUs, para mover o cacheline para o estado Exclusivo. Custo possível: 1 falha de cache. Isso não é necessário se já for propriedade exclusiva, ou seja, no estado Exclusivo ou Modificado. Em ambos os estados, nenhuma outra CPU mantém o cacheline, mas no estado Exclusivo ele não foi modificado (ainda).
  • Após esta comunicação, a variável é modificada no cache local do nosso processador, ficando então globalmente visível para todos os outros processadores (pois seus caches são coerentes com os nossos). Eventualmente, será gravado na memória principal de acordo com algoritmos usuais.
  • Outros processadores que tentarem ler ou modificar essa variável terão primeiro de obter esse cacheline no modo Compartilhado ou Exclusivo e, para isso, entrarão em contato com esse processador e receberão a versão atualizada do cacheline. Uma operação LOCKed, em vez disso, pode custar apenas uma perda de cache (porque o cacheline será solicitado diretamente no estado Exclusivo).

Em todos os casos, uma solicitação de cacheline pode ser interrompida por outros processadores já modificando os dados.

Fiz alguns perfis com a seguinte configuração: A máquina de teste (AMD Athlon64 x2 3800+) foi inicializada, alternada para o modo longo (interrupções desabilitadas) e a instrução de interesse foi executada em um loop, 100 iterações desenroladas e 1.000 ciclos de loop. O corpo do loop foi alinhado a 16 bytes. O tempo foi medido com uma instrução rdtsc antes e depois do loop. Além disso, um loop fictício sem nenhuma instrução foi executado (que mediu 2 ciclos por iteração do loop e 14 ciclos para o resto) e o resultado foi subtraído do resultado do tempo de criação de perfil da instrução.

As seguintes instruções foram medidas:

• " lock cmpxchg [rsp - 8], rdx" (com correspondência de comparação e incompatibilidade),
• " lock xadd [rsp - 8], rdx",
• " lock bts qword ptr [rsp - 8], 1"

Em todos os casos, o tempo medido foi de cerca de 310 ciclos, o erro foi de cerca de +/- 8 ciclos

Este é o valor para execução repetida na mesma memória (em cache). Com uma falha de cache adicional, os tempos são consideravelmente maiores. Além disso, isso foi feito com apenas um dos 2 núcleos ativos, portanto, o cache era de propriedade exclusiva e nenhuma sincronização de cache era necessária.

Para avaliar o custo de uma instrução bloqueada em uma falha de cache, adicionei uma wbinvldinstrução antes da instrução bloqueada e coloquei wbinvldmais um add [rsp - 8], raxno loop de comparação. Em ambos os casos, o custo foi de cerca de 80.000 ciclos por par de instruções! No caso de lock bts, a diferença de tempo era de cerca de 180 ciclos por instrução.

Observe que essa é a taxa de transferência recíproca, mas como as operações bloqueadas são operações de serialização, provavelmente não há diferença na latência.

Conclusão: uma operação bloqueada é pesada, mas uma falha de cache pode ser muito mais pesada. Além disso: uma operação bloqueada não causa perda de cache. Ele só pode causar tráfego de sincronização de cache, quando um cacheline não é de propriedade exclusiva.

Para inicializar a máquina, usei uma versão x64 do FreeLdr do projeto ReactOS. Aqui está o código-fonte do 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

No SMP baseado em barramento, o prefixo atômico LOCKafirma (liga) um sinal de fio de barramento LOCK#. Isso proibirá outros cpus / dispositivos no barramento para usá-lo.

Livro Ppro e 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 pages 244-false

As instruções bloqueadas são serializando, sincronizando operações .... / about RMW fora de ordem / bloqueado / read-modify-write = atomic próprio / instrução garante que o processador executará todas as instruções antes da instrução bloqueada antes de executá-la. / sobre as gravações ainda não liberadas / força todas as gravações postadas no processador a serem liberadas para a memória externa antes de executar a próxima instrução.

/ sobre SMP / semáforo está em cache no estado S ... emitindo uma transação de leitura e invalidação para 0 bytes de data (isto é um kill / de cópias compartilhadas da linha de cache em CPUs adjacentes /)