Por que a eficiência do trabalho é desejada na programação da GPU?

Eu li o seguinte artigo sobre como fazer uma verificação paralela no CUDA:

https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch39.html

No artigo, há uma ênfase em tornar a verificação "eficiente". Em outras palavras, um algoritmo de GPU não deve executar mais adições que um algoritmo de CPU, O (n). Os autores apresentam dois algoritmos, um "ingênuo" que faz adições ao O (nlogn) e outro que eles consideram "eficiente no trabalho". No entanto, o algoritmo de trabalho eficiente faz o dobro de iterações de loop.

Pelo meu entendimento, as GPUs são simplesmente processadores SIMD gigantes e devem operar em travamento. Executar o dobro de loops no algoritmo "trabalho eficiente" parece implicar que muitos threads ficarão ociosos e diminuirão o desempenho a longo prazo. o que estou perdendo?

Antes de tudo, re: "GPUs são simplesmente processadores SIMD gigantes e devem operar em travamento", é um pouco mais complicado que isso. o GPU inteira não é executada no passo de bloqueio. Os threads de shader são organizados em grupos de 32 chamados "warps" (na NVIDIA; na AMD são grupos de 64 chamados "frontes de onda", mas com o mesmo conceito). Dentro de um warp, todos os threads são executados no lockstep como uma matriz SIMD. No entanto, diferentes warps não estão juntos entre si. Além disso, alguns warps podem estar em execução ativa enquanto outros podem ser suspensos, como os threads da CPU. Os warps podem ser suspensos porque estão aguardando algo (como transações de memória retornar ou barreiras para limpar) ou porque não há '

Agora, de volta à sua pergunta. Eu posso ver duas maneiras pelas quais o algoritmo "trabalho eficiente" desse artigo parece ser mais eficiente que o algoritmo "ingênuo".

1. A versão com eficiência de trabalho requer metade do número de threads para começar. No algoritmo ingênuo, eles têm um segmento por elemento da matriz; mas na versão com eficiência de trabalho, cada thread opera em dois elementos adjacentes da matriz e, portanto, eles precisam apenas da metade do número de threads que os elementos da matriz. Menos encadeamentos significam menos distorções e, portanto, uma fração maior das distorções pode estar em execução ativa.

2. Embora a versão com eficiência de trabalho exija mais etapas, isso é compensado pelo fato de o número de encadeamentos ativos diminuir mais rapidamente e o número total de encadeamentos ativos em todas as iterações ser consideravelmente menor. Se um warp não tiver threads ativos durante uma iteração, ele simplesmente pulará para a barreira a seguir e será suspenso, permitindo que outros warps sejam executados. Portanto, ter menos distorções ativas geralmente pode render em tempo de execução. (Implícito nisso é que o código da GPU precisa ser projetado de forma que os threads ativos sejam agrupados no menor número possível de warps - você não deseja que eles sejam dispersos esparsamente, pois mesmo um thread ativo forçará todo o warp para permanecer ativo.)

   Considere o número de threads ativos no algoritmo ingênuo. Observando a Figura 2 no artigo, é possível ver que todos os encadeamentos estão ativos, exceto os primeiros 2 ^k na k- ésima iteração. Assim, com N threads, o número de threads ativos é de N - 2 ^k . Por exemplo, com N = 1024, o número de encadeamentos ativos por iteração é:

   1023, 1022, 1020, 1016, 1008, 992, 960, 896, 768, 512
   

   Se eu converter isso para o número de warps ativos (dividindo por 32 e arredondando para cima), obterá:

   32, 32, 32, 32, 32, 31, 30, 28, 24, 16
   

   por uma soma de 289. Por outro lado, o algoritmo eficiente em termos de trabalho começa com metade do número de threads e reduz pela metade o número de ativos em cada iteração até chegar a 1, depois começa a dobrar até voltar a metade do tamanho da matriz novamente:

    512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
   

   Convertendo isso em warps ativos:

   16, 8, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 8, 16
   

   A soma é 71, o que representa apenas um quarto do total. Assim, você pode ver que, ao longo de toda a operação, o número de warps ativos é muito menor com o algoritmo de trabalho eficiente. (De fato, para uma longa execução no meio, existem apenas alguns warps ativos, o que significa que a maior parte do chip não está ocupada. Se houver tarefas adicionais de computação em execução, por exemplo, de outros fluxos CUDA, elas poderão se expandir para preencher essa lacuna. espaço desocupado.)

Tudo isso dito, é lamentável que o artigo da GPU Gems não explique claramente nada disso, ao invés disso, concentre-se na análise de grande número de adições que, embora não seja totalmente irrelevante, perde muitos detalhes sobre o porquê desse algoritmo. Mais rápido.