Algoritmo paralelo - Parallel algorithm

Em ciência da computação , um algoritmo paralelo , ao contrário de um algoritmo serial tradicional , é um algoritmo que pode fazer várias operações em um determinado momento. Tem sido uma tradição da ciência da computação descrever algoritmos seriais em modelos de máquinas abstratos , geralmente aquele conhecido como máquina de acesso aleatório . Da mesma forma, muitos pesquisadores da ciência da computação usaram a chamada máquina paralela de acesso aleatório (PRAM) como uma máquina abstrata paralela (memória compartilhada).

Muitos algoritmos paralelos são executados simultaneamente - embora, em geral, algoritmos concorrentes sejam um conceito distinto - e, portanto, esses conceitos são frequentemente confundidos, com qual aspecto de um algoritmo é paralelo e qual é concorrente não sendo claramente distinguido. Além disso, os algoritmos não paralelos e não simultâneos são frequentemente referidos como " algoritmos sequenciais ", em contraste com os algoritmos simultâneos.

Paralelizabilidade

Os algoritmos variam significativamente em quão paralelizáveis ​​são, variando de facilmente paralelizáveis ​​a completamente não paralelizáveis. Além disso, um determinado problema pode acomodar algoritmos diferentes, que podem ser mais ou menos paralelizáveis.

Alguns problemas são fáceis de dividir em partes dessa maneira - são chamados de problemas embaraçosamente paralelos . Os exemplos incluem muitos algoritmos para resolver Cubos de Rubik e encontrar valores que resultam em um determinado hash .

Alguns problemas não podem ser divididos em porções paralelas, pois requerem os resultados de uma etapa anterior para continuar efetivamente com a próxima etapa - são chamados inerentemente problema de série s. Os exemplos incluemmétodos numéricositerativos, comoo método de Newton, soluções iterativas para oproblema de três corpose a maioria dos algoritmos disponíveis para calcularpi(π). Alguns algoritmos sequenciais podem ser convertidos em algoritmos paralelos usandoparalelização automática.

Motivação

Algoritmos paralelos em dispositivos individuais tornaram-se mais comuns desde o início dos anos 2000 devido a melhorias substanciais nos sistemas de multiprocessamento e ao surgimento de processadores multi-core . Até o final de 2004, o desempenho do processador de núcleo único aumentou rapidamente por meio do escalonamento de frequência e, portanto, era mais fácil construir um computador com um único núcleo rápido do que um com muitos núcleos mais lentos com o mesmo rendimento , então os sistemas multicore eram mais limitados usar. Desde 2004, no entanto, a escala de frequência atingiu uma parede e, portanto, os sistemas multicore tornaram-se mais difundidos, tornando algoritmos paralelos de uso mais geral.

Problemas

Comunicação

O custo ou complexidade dos algoritmos seriais é estimado em termos de espaço (memória) e tempo (ciclos do processador) que eles ocupam. Algoritmos paralelos precisam otimizar mais um recurso, a comunicação entre diferentes processadores. Existem duas maneiras de os processadores paralelos se comunicarem: memória compartilhada ou passagem de mensagens.

O processamento de memória compartilhada precisa de bloqueio adicional para os dados, impõe a sobrecarga de processadores adicionais e ciclos de barramento e também serializa alguma parte do algoritmo.

O processamento de passagem de mensagens usa canais e caixas de mensagens, mas essa comunicação adiciona sobrecarga de transferência no barramento, necessidade de memória adicional para filas e caixas de mensagens e latência nas mensagens. Projetos de processadores paralelos usam barramentos especiais como barras transversais de modo que o overhead de comunicação seja pequeno, mas é o algoritmo paralelo que decide o volume do tráfego.

Se a sobrecarga de comunicação de processadores adicionais superar o benefício de adicionar outro processador, ocorrerá lentidão paralela .

Balanceamento de carga

Outro problema com algoritmos paralelos é garantir que eles tenham carga balanceada de maneira adequada , garantindo que a carga (trabalho geral) seja balanceada, ao invés de tamanho de entrada sendo balanceado. Por exemplo, verificar a primalidade de todos os números de um a cem mil é fácil de dividir entre os processadores; no entanto, se os números forem simplesmente divididos uniformemente (1–1.000, 1.001–2.000, etc.), a quantidade de trabalho será desequilibrada, pois números menores são mais fáceis de processar por este algoritmo (mais fácil de testar a primalidade), e assim, alguns processadores terão mais trabalho a fazer do que outros, que ficarão inativos até que os processadores carregados sejam concluídos.

Algoritmos Distribuídos

Um subtipo de algoritmos paralelos, algoritmos distribuídos , são algoritmos projetados para trabalhar em computação de cluster e ambientes de computação distribuída , onde questões adicionais além do escopo dos algoritmos paralelos "clássicos" precisam ser abordadas.

Veja também

Referências

links externos