Por que as comparações são tão caras em uma GPU?

10

Enquanto tentava melhorar o desempenho da minha classe de detecção de colisões, descobri que ~ 80% do tempo gasto na gpu passava em condições if / else apenas tentando descobrir os limites dos buckets pelos quais deveria passar.

Mais precisamente:

  1. cada thread obtém um ID, por esse ID ele busca seu triângulo na memória (3 inteiros cada) e pelos 3 busca seus vértices (3 flutua cada).

  2. Em seguida, transforma os vértices em pontos inteiros da grade (atualmente 8x8x8) e os transforma nos limites do triângulo nessa grade

  3. Para transformar os 3 pontos em limites, ele encontra o mínimo / máximo de cada dimensão entre cada um dos pontos

Como a linguagem de programação que estou usando está com falta de um minmax intrínseco, eu mesmo criei uma, assim:

procedure MinMax(a, b, c):
   local min, max

   if a > b:
      max = a
      min = b
   else:
      max = b
      min = a
   if c > max:
      max = c
   else:
      if c < min:
         min = c

   return (min, max)

Portanto, em média, deve haver comparações de 2,5 * 3 * 3 = 22,5, o que acaba consumindo muito mais tempo do que os testes reais de interseção da borda do triângulo (cerca de 100 * 11-50 instruções).

De fato, descobri que pré-calcular os buckets necessários na CPU (thread único, sem vetorização), empilhá-los em uma exibição de GPU junto com a definição do bucket e fazer com que a GPU faça ~ 4 leituras extras por thread foi 6 vezes mais rápida do que tentar para descobrir os limites no local. (observe que eles são recalculados antes de cada execução, pois estou lidando com malhas dinâmicas)

Então, por que a comparação é tão terrivelmente lenta em uma gpu?

user29075
fonte
2
Sua pergunta é sobre o desempenho no nível de instrução de um trecho de código específico em um tipo específico de hardware. Isso me parece muito mais uma questão de programação do que uma questão de ciência da computação.
David Richerby
7
Meu palpite é que não são as comparações caras, mas os ramos. Se o compilador não usar predicação (ou a GPU não fornecer isso), serão usadas ramificações que causam bifurcação de "thread" (porque as GPUs são orientadas para SIMD). Converter a condição em uma máscara e usá-la para sintetizar movimentos / trocas condicionais pode ser uma alternativa razoável.
Paul A. Clayton
11
@DavidRicherby Não tenho certeza se é tão específico assim. Esta pergunta não se aplica a nenhuma arquitetura SIMD?
kasperd
11
@ DavidRicherby: a razão pela qual ensinamos o arco de comp nos departamentos de CS é porque o arco de comp tem impacto nos algoritmos que você escolhe. As arquiteturas SIMD podem produzir alta taxa de transferência somente se você descobrir como escrever o programa sem ramificações aninhadas.
Wandering Logic
2
Como a resposta da Wandering Logic afirma de uma maneira menos óbvia, as GPUs funcionam assumindo que muitos "threads" estão na mesma instrução simultaneamente. Portanto, as GPUs, grosso modo, assumem todas as ramificações, e não apenas as verdadeiras. É por isso que as GPUs exploram o fato de que os vizinhos geralmente têm as mesmas ramificações; e o desempenho é terrível quando isso não é verdade.
27715 Rob

Respostas:

10

GPUs são arquiteturas SIMD. Nas arquiteturas SIMD, todas as instruções precisam ser executadas para cada elemento que você processa. (Há uma exceção a essa regra, mas ela raramente ajuda).

Portanto, em sua MinMaxrotina, não apenas todas as chamadas precisam buscar as três instruções de ramificação (mesmo que em média sejam avaliadas apenas 2,5), mas todas as instruções de atribuição também executam um ciclo (mesmo que, na verdade, não sejam "executadas" )

Esse problema às vezes é chamado de divergência de thread . Se sua máquina tiver algo como 32 faixas de execução SIMD, ainda terá apenas uma única unidade de busca. (Aqui, o termo "encadeamento" significa basicamente "faixa de execução do SIMD".) Portanto, internamente, cada faixa de execução do SIMD possui um bit "Estou ativado / desativado", e as ramificações na verdade apenas manipulam esse bit. (A exceção é que, no ponto em que todas as faixas do SIMD ficam desabilitadas, a unidade de busca geralmente passa diretamente para a cláusula "else".)

Portanto, no seu código, todas as faixas de execução do SIMD estão executando:

compare (a > b)
assign (max = a if a>b)
assign (min = b if a>b)
assign (max = b if not(a>b))
assign (min = a if not(a>b))
compare (c > max)
assign (max = c if c>max)
compare (c < min if not(c>max))
assign (min = c if not(c>max) and c<min)

Pode ser que em algumas GPUs essa conversão de condicionais em predicação seja mais lenta se a GPU estiver fazendo isso sozinha. Conforme apontado por @ PaulA.Clayton, se sua linguagem e arquitetura de programação tiver uma operação de movimentação condicional predicada (especialmente uma das formas if (c) x = y else x = z), você poderá fazer melhor. (Mas provavelmente não muito melhor).

Além disso, colocar o c < mincondicional dentro elsede c > maxé desnecessário. Certamente não está poupando nada e (já que a GPU precisa convertê-la automaticamente em predicação) pode realmente ser prejudicial ao aninhar-se em dois condicionais diferentes.

Lógica Errante
fonte
2
(Desculpe se alguma parte deste está claro, eu estou tentando obter uma resposta antes de os teóricos fechar a questão de fora do tópico.)
Wandering Logic
Para obter mais informações básicas: http.developer.nvidia.com/GPUGems2/gpugems2_chapter34.html E para soluções alternativas mais recentes: eecis.udel.edu/~cavazos/cisc879/papers/a3-han.pdf
Fizz
É um tópico no sentido de que alguns algoritmos não podem ser acelerados pelo paralelismo SIMD. (ou seja: Trabalho, Span, etc para um tratamento mais teórico do porquê)
Rob
11
Aqui está outra palestra sobre os conceitos básicos de divergência people.maths.ox.ac.uk/gilesm/cuda/lecs/lec3-2x2.pdf Observe a partir deles que o problema (na Nvidia de qualquer maneira) é apenas por distorção. O código executado em diferentes warps pode divergir alegremente. E outro artigo propondo um método para evitá-lo: hal.inria.fr/file/index/docid/649650/filename/sbiswi.pdf
Fizz
Em uma tática um pouco diferente, mas de acordo com os comentários que escrevi sob a pergunta eprint.iacr.org/2012/137.pdf, vale a pena ler: uma desaceleração de 10x em comparação com o desempenho previsto pode ser "normal" para uma GPU, a menos que você desça à sua montagem (geralmente com ferramentas oficialmente não suportadas). É possível que os compiladores de segmentação por GPU tenham melhorado, mas eu não prendi a respiração.
Fizz