4

Estava procurando problemas chamados de "embaraçosamente paralelos", que são problemas que não existem dependências entre tarefas, podendo as mesmas serem divididas paralelamente.

Poderia me dar alguma sugestão de algum algoritmo?

2 Respostas 2

6

Renderização de imagens

Um algoritmo desse gênero é a renderização de cenas tridimensionais, em que cada pixel é renderizado por completo sem depender em nada da renderização dos outros pixels.

É por isso que as GPUs atuais ampliam cada vez mais o número de processadores chamados de shaders, que são responsáveis por calcular a cor final de cada pixel, de forma independente um dos outros.

Uma menção importante nesse conjunto é o ruído de Perlin (Perlin noise em inglês), que é usado para gerar ruído pseudo-aleatório.

Simulações físicas com partículas

Outro exemplo são simulações físicas, em que cada partícula tem suas características alteradas levando em conta o estado anterior da simulação. Ou seja, em cada passo, as partículas não interagem entre si, mas sim com as partículas do estágio anterior.

Também por isso, muitos jogos usam a GPU para fazer simulações físicas com um número muito maior de partículas, obviamente a GPU tem que oferecer suporte para isso.

Problemas que não paralelizam por completo

Problemas da categoria "Dividir para conquistar", não são tão paralelizáveis para árvores pequenas. Mas a medida que o conjunto de informações cresce, a solução vai se tornando cada vez mais paralelizável.

Exemplos:

  • somar todos os números de uma lista gigante... é possível subdividir o problema, dividindo a lista gigante em listas menores e delegar a solução parcial para processadores distintos.

  • buscar todas as alternativas em um jogo de xadrez (terá de definir a profundidade máxima da busca, pois é impossível calcular todas... o número de alternativas é absurdamente grande)

4

Alguns problemas clássicos de algoritmos relativamente simples e bons de paralelizar são:

Cálculo de Pi usando o Método de Monte Carlo

Considere a seguinte imagem com um quadrado e um círculo cujo diâmetro tem a mesma medida do lado do quadrado.

Alvo

Agora imagine que o círculo é um alvo. Você jogará dardos aleatoriamente dentro do quadrado.

Agora considere a fórmula abaixo:

Fórmula Pi

Isso significa que se você pegar a quantidade de dardos que acertaram dentro do círculo, dividir pela quantidade que acertou fora do círculo e multiplicar por quatro, obterá um valor de Pi aproximado.

A teoria diz que a aproximação melhora de acordo com o número de dardos lançados. Logo, um programa em paralelo pode "jogar dardos" aleatoriamente no quadrado e contabilizar a quantidade de dardos dentro e fora do círculo. Ao final, basta somar os resultados e aplicar na fórmula.

Aproximação de integral pela regra trapezoidal

Você quer o valor aproximado da integral de uma função f(x) no intervalor de a a b.

Uma forma bem simples (e imprecisa) de resolver isso é calcular a integral de uma função linear que passa pelos pontos f(a) e f(b).

Veja o exemplo:

função e aproximação

Em azul você tem a função real e em vermelho a função linear usada para calcular a aproximação.

Bem, uma função linear vai resultar numa aproximação ruim. Porém, aumentarmos a quantidade de pontos da função de aproximação, o resultado será mais preciso, certo? Quanto mais pontos calcularmos, melhor.

Aproximação melhor

Então, podemos usar um programa paralelo e dividir o intervalo [a, b] pelo número de threads ou processos e cada um calcular a integral parcial daquele trecho.

No final, basta somar os resultados.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .