Existem problemas / algoritmos famosos na computação científica que não podem ser acelerados pela paralelização

27

Existem problemas / algoritmos famosos na computação científica que não podem ser acelerados pela paralelização? Parece-me ao ler livros sobre CUDA que a maioria das coisas pode ser.

RNs_Ghost
fonte
A pesquisa binária não pode ser acelerada (significativamente, ou seja, por um fator), mesmo quando se considera a hierarquia de memória.
3
@Anycorn Não, o Gram-Schmidt clássico à esquerda e o Gram-Schmidt modificado à direita funcionam bem em paralelo. Existem muitos outros algoritmos QR paralelos, incluindo o TSQR recentemente popularizado.
22412 Jed Brown
@ Rafael: Eu acho que é possível acelerar a pesquisa binária pelo fator log (n), n = # processadores. Em vez de dividir o intervalo de pesquisa em partes e verificar onde continuar, divida o intervalo em n partes. Talvez haja maneiras mais eficientes, eu não sei.
miracle173

Respostas:

32

O problema central é o comprimento do caminho crítico em relação à quantidade total de computação T . Se C é proporcional a T , o paralelismo oferece, na melhor das hipóteses, uma aceleração constante. Se C é assintoticamente menor que T , há espaço para mais paralelismo à medida que o tamanho do problema aumenta. Para algoritmos nos quais T é polinomial no tamanho de entrada N , o melhor caso é C log T porque muito poucas quantidades úteis podem ser calculadas em menos que o tempo logarítmico.CTCTCTTNClogT

Exemplos

  • para uma resolução tridiagonal usando o algoritmo padrão. Toda operação depende da conclusão da operação anterior, portanto não há oportunidade para paralelismo. Problemas tridiagonais podem ser resolvidos em tempo logarítmico em um computador paralelo usando uma solução direta de dissecação aninhada, decomposição de domínio multinível ou multigrid com funções básicas construídas usando extensão harmônica (esses três algoritmos são distintos em múltiplas dimensões, mas podem coincidir exatamente em 1D).C=T
  • Um denso triangular inferior resolver com uma matriz tem T = N = O ( m 2 ) , mas o caminho crítico só é C = m = m×mT=N=O(m2) , então algum paralelismo pode ser benéfico.C=m=T
  • Multigrade e FMM ambos têm , com um caminho crítico de comprimento C = log T .T=NC=logT
  • Propagação da onda explícita para um tempo sobre uma malha regular do domínio ( 0 , 1 ) d requer k = τ / Δ t ~ τ N 1 / d passos de tempo (por estabilidade), por conseguinte, o caminho crítico é, pelo menos, C = k . A quantidade total de trabalho é T = k N = τ N ( d + 1 ) / d . O número máximo útil de processadores é P = Tτ(0,1)dk=τ/ΔtτN1/dC=kT=kN=τN(d+1)/d , o fator restante N 1 / d não pode ser recuperado pelo aumento do paralelismo.P=T/C=NN1/d

Complexidade formal

A classe de complexidade NC caracteriza os problemas que podem ser resolvidos eficientemente em paralelo (isto é, em tempo polilogarítmico). Não se sabe se , mas a hipótese é amplamente falsa. Se esse for realmente o caso, o P-complete caracteriza os problemas que são "inerentemente sequenciais" e não podem ser acelerados significativamente pelo paralelismo.NC=P

Jed Brown
fonte
13

Para dar um aspecto teórica para este, NC é definida como a classe de complexidade que é solúvel em de tempo em um sistema com S ( n k ) processadores paralelos. Ainda não se sabe se P = N C (embora a maioria das pessoas suspeite que não esteja) onde P é o conjunto de problemas solucionáveis ​​no tempo polinomial. Os problemas "mais difíceis" a serem paralelizados são conhecidos como problemas completos de P no sentido de que todo problema em P pode ser reduzido a um problema completo de P viaO(logcn)O(nk)P=NCPPPPReduções de N C. Se você mostrar que um únicoproblema com P completo está em N C , você prova que P = N C (embora isso provavelmente seja falso como mencionado acima).NCPNCP=NC

Portanto, qualquer problema que seja completo seria intuitivamente difícil de paralelizar (embora ainda sejam possíveis grandes acelerações). Um problema completo de P para o qual não temos acelerações de fator constante muito boas é a Programação Linear (veja este comentário na troca OR).PP

Optar
fonte
9

Comece grocking Lei de Amdahl . Basicamente, qualquer coisa com um grande número de etapas seriais se beneficiará de forma insignificante do paralelismo. Alguns exemplos incluem análise, regex e a maior compactação de alta taxa.

Além disso, o principal problema geralmente é um gargalo na largura de banda da memória. Em particular na maioria das GPUs, seus flops teóricos superam amplamente a quantidade de números de ponto flutuante que você pode obter nas ALU, pois algoritmos com baixa intensidade aritmética (flops / cache-miss) gastam a maior parte do tempo esperando na RAM.

Por fim, sempre que um pedaço de código exigir ramificação, é improvável que ele tenha um bom desempenho, pois a ALU geralmente supera a lógica.

Em conclusão, um exemplo realmente simples de algo que seria difícil obter um ganho de velocidade de uma GPU é simplesmente contar o número de zeros em uma matriz de números inteiros, pois você pode precisar ramificar frequentemente, no máximo, executar uma operação (incremento por um) caso encontre um zero e faça pelo menos uma busca de memória por operação.

Um exemplo livre do problema de ramificação é calcular um vetor que é a soma cumulativa de outro vetor. ([1,2,1] -> [1,3,4])

Não sei se isso conta como "famoso", mas certamente há um grande número de problemas com os quais a computação paralela não o ajudará.

meawoppl
fonte
3
O "exemplo gratuito de ramificação" que você forneceu é o prefixo-sum, que na verdade possui um bom algoritmo paralelo: http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html O cálculo do número de zeros deve ser eficiente por razões semelhantes. Não há maneira de contornar intensidade aritmética, embora ...
Max Hutchinson
Legal. Eu estou corrigido naquele.
01
8

O método (famoso) de marcha rápida para resolver a equação de Eikonal não pode ser acelerado pela paralelização. Existem outros métodos (por exemplo, métodos de varredura rápida) para resolver a equação Eikonal que são mais passíveis de paralelização, mas mesmo aqui o potencial para aceleração (paralela) é limitado.

O problema com a equação de Eikonal é que o fluxo de informações depende da própria solução. Em termos gerais, a informação flui ao longo das características (isto é, raios de luz na óptica), mas as características dependem da própria solução. E o fluxo de informações para a equação Eikonal discretizada é ainda pior, exigindo aproximações adicionais (como implicitamente presentes em métodos de varredura rápida) se qualquer aceleração paralela for desejada.

Para ver as dificuldades da paralelização, imagine um belo labirinto como em alguns exemplos na página de Sethian . O número de células no caminho mais curto através do labirinto (provavelmente) é um limite inferior para o número mínimo de etapas / iterações de qualquer algoritmo (paralelo) que resolve o problema correspondente.

(Eu escrevo "(provavelmente) é", porque limites mais baixos são notoriamente difíceis de provar e geralmente exigem algumas suposições razoáveis ​​sobre as operações usadas por um algoritmo).

Thomas Klimpel
fonte
Belo exemplo, mas não acredito que seu limite inferior seja reivindicado. Em particular, métodos multigrid podem ser usados ​​para resolver a equação eikonal. Assim como o multigrid para Helmholtz de alta frequência, os desafios estão principalmente no design de espaços grosseiros adequados. No caso de um labirinto, uma estratégia de agregação de gráfico deve ser eficaz, com a representação grosseira determinada pela solução de problemas locais (portanto independentes) para segmentos do labirinto.
precisa
Em geral, quando os métodos multigrid se dão bem, isso significa que a granularidade do problema é menor que a descritização, e uma "quantidade de resposta correta" desproporcional vem da etapa de solução do curso. Apenas uma observação, mas o limite inferior desse tipo de coisa é complicado!
27412
@JedBrown De uma perspectiva prática, o multigrid para Helmholtz de alta frequência é bastante desafiador, ao contrário do que seu comentário parece sugerir. E usar multigrid para a equação eikonal é "incomum", para dizer o mínimo. Mas vejo sua objeção "teórica" ​​contra o limite inferior sugerido: as compensações de tempo de vários pontos dentro do labirinto podem ser calculadas antes que o tempo para atingir esses pontos seja conhecido e adicionadas paralelamente depois que as informações ausentes estiverem disponíveis. Mas, na prática, os solucionadores eikonais paralelos de propósito geral são felizes se realmente chegarem perto do limite.
Thomas Klimpel
Eu não quis dizer que era fácil, os espaços grossos dos raios de onda são realmente muito técnicos. Mas acho que concordamos que já existe oportunidade de paralelismo em regiões abertas, enquanto em estreitos "labirintos" (que expõem muito pouco paralelismo com métodos padrão), o problema de aumento de escala é mais tratável.
precisa
O @JedBrown Slide 39 do www2.ts.ctw.utwente.nl/venner/PRESENTATIONS/MSc_Verburg.pdf (de 2010) diz coisas como "Estenda o solucionador de 2D para 3D" e "Adapte o método a problemas com números de onda altamente variáveis". Portanto, o multigrid de raios-onda pode ser promissor, mas "ainda não maduro" parece ser mais apropriado do que "muito técnico" para descrever seus problemas atuais. E não é realmente um solucionador de Helmholtz de alta frequência (porque é um solucionador de "onda completa"). Existem outros solucionadores de Helmholtz multigrid "suficientemente maduros" (solucionadores de "onda completa"), mas mesmo esses ainda são "pesquisas ativas".
Thomas Klimpel
1

Outra classe de problemas difíceis de paralelizar na prática são os problemas sensíveis a erros de arredondamento, em que a estabilidade numérica é alcançada pela serialização.

Considere, por exemplo, o processo de Gram-Schmidt e sua modificação serial. O algoritmo funciona com vetores, portanto, você pode usar operações com vetores paralelos, mas isso não é escalável. Se o número de vetores for grande e o tamanho do vetor for pequeno, o uso de Gram-Schmidt clássico paralelo e a re-regionalização pode ser estável e mais rápido que o Gram-Schmidt modificado único, embora isso envolva fazer várias vezes mais trabalho.

Jakub Klinkovský
fonte