custo de operação atômica

93

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.

osgx
fonte
@Jason S, Any. A diferença entre cas e atômico inc / dec é insignificante.
osgx
2
As operações atômicas em um x86 tornam-se mais lentas à medida que mais contenção é colocada no endereço de memória. Eu acredito que em geral eles estão em torno de uma ordem de magnitude mais lenta do que a operação não bloqueada, mas claramente isso irá variar dependendo da operação, contenção e barreiras de memória usadas.
Stephen Nutt,
hmmm. as gravações parecem ser atômicas em x86. 'Compreendendo o kernel do Linux' -> spin_unlock
osgx
Uma gravação de 32 bits é atômica em Java, ou seja, é portavelmente atômica (mas não tem semântica de barreira de memória, então isso geralmente não é suficiente para ponteiros). Adicionar 1 normalmente não é atômico, a menos que você adicione o prefixo LOCK. Sobre o kernel Linux, não há necessidade de olhar para spin_unlock. Veja, nas versões atuais, arch / x86 / include / asm / atomic_32.h (costumava ser include / asm-i386 / atomic.h).
Blaisorblade
@Blaisorblade, JAva não está aqui. Qual é o custo das operações LOCKed?
osgx

Respostas:

61

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.

Blaisorblade
fonte
por que mudar de estado em outros cpus custa como 1 perda de cache?
osgx
1
Porque é uma comunicação fora da CPU e, portanto, mais lenta do que acessar o cache. Enquanto uma falha de cache tem que passar de outras CPUs de qualquer maneira. Na verdade, pode ser que falar com outra CPU seja mais rápido do que falar com memória, se uma interconexão direta for usada, como o AMD Hypertransport (desde muito tempo atrás), ou Intel QuickPath Interconnect da Intel, nos mais recentes processadores Xeon baseado em Nehalem. Caso contrário, a comunicação com outras CPUs ocorre no mesmo FSB da memória. Pesquise HyperTransport e Front Side Bus na Wikipedia para obter mais informações.
Blaisorblade
Uau, nunca pensei que o dele fosse tão caro - uma falha de cache pode ter alguns milhares de ciclos.
Lothar
2
Mesmo? A figura que estou acostumada é: cem ciclos para perdas de cache e milhares de ciclos para alternâncias de contexto / privilégio (incluindo syscalls).
Blaisorblade
1
A perda de cache não ocorre em alguns milhares de ciclos! É cerca de 100 ns, o que normalmente é de 300-350 ciclos de CPU ...
usuário997112
37

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
Timo
fonte
Obrigado! Você pode publicar seu código de teste ou testar o Core2 / Core i3 / i5 / i7 você mesmo? Todos os núcleos foram inicializados em sua configuração de teste?
osgx
Eu adicionei o código-fonte. Apenas um núcleo foi inicializado. Adoraria ver resultados de outras máquinas.
Timo
CLFLUSH deve ser uma maneira muito mais leve de liberar uma linha de cache do que WBINVD de todo o cache. WBINVD irá liberar caches de instrução também, levando a perdas de cache extras.
Peter Cordes
Talvez seja interessante testar o caso da linha do cache estar quente no estado Compartilhado. Você pode fazer isso acontecer fazendo com que outro tópico o leia com uma carga pura.
Peter Cordes
3

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 /)

osgx
fonte
1
O SMP baseado em barramento não é usado desde a arquitetura P6 / Pentium Pro em 1995 ( fonte ). O Now LOCKnão faz um bloqueio de barramento todas as vezes, a menos que os dados estejam desalinhados na linha do cache ou haja uma contenção do cache. Verifique rigtorp.se/split-locks para números atualizados.
Arnaud Bouchez de