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?
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.
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 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)
Alguns problemas clássicos de algoritmos relativamente simples e bons de paralelizar são:
Considere a seguinte imagem com um quadrado e um círculo cujo diâmetro tem a mesma medida do lado do quadrado.
Agora imagine que o círculo é um alvo. Você jogará dardos aleatoriamente dentro do quadrado.
Agora considere a fórmula abaixo:
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.
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:
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.
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.