Qual é a diferença entre atômico e crítico no OpenMP?

111

Qual é a diferença entre atômico e crítico no OpenMP?

eu posso fazer isso

#pragma omp atomic
g_qCount++;

mas não é o mesmo que

#pragma omp critical
g_qCount++;

?

codereviewanskquestions
fonte

Respostas:

173

O efeito em g_qCount é o mesmo, mas o que é feito é diferente.

Uma seção crítica do OpenMP é completamente geral - ela pode envolver qualquer bloco arbitrário de código. Você paga por essa generalidade, no entanto, incorrendo em sobrecarga significativa sempre que um encadeamento entra e sai da seção crítica (além do custo inerente de serialização).

(Além disso, no OpenMP todas as seções críticas não nomeadas são consideradas idênticas (se preferir, há apenas um bloqueio para todas as seções críticas não nomeadas), de modo que se um thread estiver em uma seção crítica [sem nome] como acima, nenhum thread pode entrar em qualquer seção crítica [sem nome]. Como você pode imaginar, você pode contornar isso usando seções críticas nomeadas).

Uma operação atômica tem uma sobrecarga muito menor. Quando disponível, ele se beneficia do hardware que fornece (digamos) uma operação de incremento atômico; nesse caso, não há necessidade de bloqueio / desbloqueio ao entrar / sair da linha de código, ele apenas faz o incremento atômico que o hardware informa que não pode ser interferido.

As vantagens são que a sobrecarga é muito menor e um thread em uma operação atômica não bloqueia nenhuma operação atômica (diferente) prestes a acontecer. A desvantagem é o conjunto restrito de operações que o atômico suporta.

Claro, em qualquer caso, você incorre no custo de serialização.

Jonathan Dursi
fonte
5
"você pode perder a portabilidade" - não tenho certeza se isso é verdade. O padrão (versão 2.0) especifica quais operações atômicas são permitidas (basicamente coisas como ++e *=) e que, se não forem suportadas no hardware, podem ser substituídas por criticalseções.
Dan R
@DanRoche: Sim, você está certo. Acho que essa afirmação nunca foi correta, vou corrigi-la agora.
Jonathan Dursi
Há alguns dias segui um tutorial do OpenMP e, pelo que entendi, há uma diferença nos dois códigos diferentes. Ou seja, o resultado pode ser diferente porque a seção crítica garante que a instrução seja executada por uma thread por vez, porém é possível que a instrução: g_qCount = g_qCount + 1; para o thread 1 simplesmente armazena o resultado g_qCount apenas no writebuffer e não na memória RAM, e quando o thread 2 busca o valor g_qCount, ele simplesmente lê aquele na RAM, não no writebuffer. A instrução atômica garante que a instrução liberou os dados para a memória
Giox79
31

No OpenMP, todas as seções críticas sem nome são mutuamente exclusivas.

A diferença mais importante entre crítico e atômico é que o atômico pode proteger apenas uma única atribuição e você pode usá-lo com operadores específicos.

Michael
fonte
13
Seria melhor que fosse um comentário (ou uma edição) da resposta anterior.
kynan
20

Seção Crítica:

  • Garante a serialização de blocos de código.
  • Pode ser estendido para serializar grupos de blocos com o uso adequado da tag "name".

  • Mais devagar!

Operação atômica:

  • É muito mais rápido!

  • Garante apenas a serialização de uma determinada operação.

efarsarakis
fonte
9
Mas esta resposta é muito legível e seria um ótimo resumo da primeira resposta
Michał Miszczyszyn
7

O caminho mais rápido não é crítico nem atômico. Aproximadamente, a adição com seção crítica é 200 vezes mais cara do que a adição simples, a adição atômica é 25 vezes mais cara do que a adição simples.

A opção mais rápida (nem sempre aplicável) é dar a cada thread seu próprio contador e fazer a operação de redução quando você precisar da soma total.

Andrii
fonte
2
Não concordo com todos os números que você menciona em sua explicação. Assumindo x86_64, a operação atômica terá uma sobrecarga de alguns ciclos (sincronizando uma linha de cache) ao custo de aproximadamente um ciclo. Se você tivesse um custo de '' compartilhamento verdadeiro '' de outra forma, a sobrecarga seria nula. Uma seção crítica incorre no custo de uma fechadura. Dependendo se o bloqueio já foi executado ou não, a sobrecarga é de aproximadamente 2 instruções atômicas OU duas execuções do agendador e o tempo de suspensão - que normalmente será significativamente mais do que 200x.
Klaas van Gend
6

As limitações de atomicsão importantes. Eles devem ser detalhados nas especificações do OpenMP . O MSDN oferece uma rápida folha de referências, pois eu não ficaria surpreso se isso não mudasse. (Visual Studio 2012 tem uma implementação OpenMP de março de 2002). Para citar o MSDN:

A declaração de expressão deve ter uma das seguintes formas:

xbinop =expr

x++

++x

x--

--x

Nas expressões anteriores: xé uma lvalueexpressão com tipo escalar. expré uma expressão com tipo escalar e não faz referência ao objeto designado por x. binop não é um operador sobrecarregado e é um de +, *, -, /, &, ^, |, <<, ou >>.

Eu recomendo usar atomicquando puder e nomear seções críticas de outra forma. Nomear é importante; você evitará dores de cabeça de depuração dessa maneira.

darda
fonte
1
Isso não é tudo, temos outras diretivas atômicas avançadas como: #pragma omp aromic update (ou leia, atualize, escreva, capture) para que possamos ter alguma outra declaração benéfica
pooria
1

Já são ótimas explicações aqui. No entanto, podemos mergulhar um pouco mais fundo. Para entender a diferença central entre os conceitos de seção atômica e crítica no OpenMP, temos que entender o conceito de bloqueio primeiro. Vamos revisar porque precisamos usar bloqueios .

Um programa paralelo está sendo executado por vários threads. Resultados determinísticos acontecerão se e somente se realizarmos a sincronização entre esses threads. Obviamente, a sincronização entre threads nem sempre é necessária. Estamos nos referindo aos casos em que a sincronização é necessária.

Para sincronizar as threads em um programa multi-thread, usaremos lock . Quando o acesso deve ser restrito por apenas um segmento de cada vez, os bloqueios entram em ação. A implementação do conceito de bloqueio pode variar de processador para processador. Vamos descobrir como um bloqueio simples pode funcionar de um ponto de vista algorítmico.

1. Define a variable called lock.
2. For each thread:
   2.1. Read the lock.
   2.2. If lock == 0, lock = 1 and goto 3    // Try to grab the lock
       Else goto 2.1    // Wait until the lock is released
3. Do something...
4. lock = 0    // Release the lock

O algoritmo fornecido pode ser implementado na linguagem de hardware da seguinte maneira. Estaremos assumindo um único processador e analisaremos o comportamento dos bloqueios nele. Para esta prática, vamos supor um dos seguintes processadores: MIPS , Alpha , ARM ou Power .

try:    LW R1, lock
        BNEZ R1, try
        ADDI R1, R1, #1
        SW R1, lock

Este programa parece estar OK, mas não é. O código acima sofre do problema anterior; sincronização . Vamos encontrar o problema. Suponha que o valor inicial de bloqueio seja zero. Se duas threads executam este código, uma pode alcançar o SW R1, travar antes que a outra leia a variável de travamento . Assim, ambos pensam que a fechadura está livre. Para resolver esse problema, há outra instrução fornecida em vez de simples LW e SW . É chamada de instrução Read-Modify-Write . É uma instrução complexa (consistindo em subinstruções) que garante que o procedimento de aquisição de bloqueio seja feito por apenas um únicofio de cada vez. A diferença de Read-Modify-Write em comparação com as instruções simples de Read e Write é que ele usa uma maneira diferente de Carregar e Armazenar . Ele usa LL (Load Linked) para carregar a variável de bloqueio e SC (Store Conditional) para gravar na variável de bloqueio. Um Link Register adicional é usado para garantir que o procedimento de aquisição de bloqueio seja feito por uma única thread. O algoritmo é fornecido abaixo.

1. Define a variable called lock.
2. For each thread:
   2.1. Read the lock and put the address of lock variable inside the Link Register.
   2.2. If (lock == 0) and (&lock == Link Register), lock = 1 and reset the Link Register then goto 3    // Try to grab the lock
       Else goto 2.1    // Wait until the lock is released
3. Do something...
4. lock = 0    // Release the lock

Quando o registro do link é redefinido, se outro encadeamento assumiu que o bloqueio está livre, ele não será capaz de gravar o valor incrementado no bloqueio novamente. Assim, a simultaneidade de acesso à variável de bloqueio é adquirida.

A principal diferença entre crítico e atômico vem da ideia de que:

Por que usar bloqueios (uma nova variável) enquanto podemos usar a variável real (na qual estamos executando uma operação), como uma variável de bloqueio?

Usar uma nova variável para bloqueios levará a uma seção crítica , enquanto usar a variável real como um bloqueio levará ao conceito atômico . A seção crítica é útil quando estamos realizando muitos cálculos (mais de uma linha) na variável real. Isso porque, se o resultado desses cálculos não for escrito na variável real, todo o procedimento deve ser repetido para calcular os resultados. Isso pode levar a um desempenho ruim em comparação com esperar que o bloqueio seja liberado antes de entrar em uma região altamente computacional. Assim, é recomendado usar a diretiva atômica sempre que quiser realizar um único cálculo (x ++, x--, ++ x, --x, etc.) e usardiretiva crítica quando uma região computacionalmente mais complexa está sendo feita pela seção intensiva.

hexfeu
fonte
-5

atomic é relativamente eficiente em termos de desempenho quando você precisa habilitar a exclusão mútua para apenas uma única instrução semelhante não é verdade sobre omp critical.

Mahesh
fonte
13
Isso nada mais é do que uma reformulação mal formulada da resposta aceita sem explicação.
Alto desempenho Mark
-5

atômica é uma seção crítica de instrução única, ou seja, você bloqueia a execução de uma instrução

seção crítica é um bloqueio em um bloco de código

Um bom compilador irá traduzir seu segundo código da mesma forma que faz o primeiro

Wissam Y. Khalil
fonte
Isso é simplesmente errado. Por favor, não fale sobre coisas que você não entende.
jcsahnwaldt Reinstaurar Monica