Constrangedoramente paralelo - Embarrassingly parallel
Na computação paralela , uma carga de trabalho ou problema constrangedoramente paralelo (também chamado de constrangedoramente paralelizável , perfeitamente paralelo , encantadoramente paralelo ou agradavelmente paralelo ) é aquele em que pouco ou nenhum esforço é necessário para separar o problema em várias tarefas paralelas. Geralmente, esse é o caso em que há pouca ou nenhuma dependência ou necessidade de comunicação entre essas tarefas paralelas ou de resultados entre elas.
Portanto, eles são diferentes dos problemas de computação distribuída que precisam de comunicação entre tarefas, especialmente comunicação de resultados intermediários. Eles são fáceis de executar em farms de servidores que não possuem a infraestrutura especial usada em um verdadeiro cluster de supercomputador . Eles são, portanto, adequados para grandes plataformas distribuídas baseadas na Internet, como o BOINC , e não sofrem de lentidão paralela . O oposto de problemas embaraçosamente paralelos são problemas inerentemente seriais , que não podem ser paralelizados de forma alguma.
Um exemplo comum de um problema embaraçosamente paralelo é a renderização de vídeo 3D gerenciada por uma unidade de processamento gráfico , onde cada quadro (método de encaminhamento) ou pixel ( método de traçado de raio ) pode ser manipulado sem interdependência. Algumas formas de quebra de senha são outra tarefa embaraçosamente paralela que é facilmente distribuída em unidades de processamento central , núcleos de CPU ou clusters.
Etimologia
"Embaraçosamente" é usado aqui no mesmo sentido que na frase "um embaraço de riquezas ", significando uma superabundância - aqui se referindo a problemas de paralelização que são "embaraçosamente fáceis". O termo também pode implicar constrangimento por parte dos desenvolvedores ou compiladores: "Como tantos problemas importantes permanecem sem solução principalmente devido à sua complexidade computacional intrínseca, seria embaraçoso não desenvolver implementações paralelas de métodos de continuação de homotopia polinomial ." O termo foi encontrado pela primeira vez na literatura em um livro de 1986 sobre multiprocessadores do criador do MATLAB , Cleve Moler , que afirma ter inventado o termo.
Um termo alternativo, agradavelmente paralelo , ganhou algum uso, talvez para evitar as conotações negativas de constrangimento em favor de uma reflexão positiva sobre a paralelizabilidade dos problemas: "Claro, não há nada embaraçoso nesses programas."
Exemplos
Alguns exemplos de problemas embaraçosamente paralelos incluem:
- Análise de Monte Carlo
- Consultas de banco de dados relacional distribuído usando processamento de conjunto distribuído .
- Integração numérica
- Servir arquivos estáticos em um servidor da web para vários usuários ao mesmo tempo.
- O conjunto de Mandelbrot , ruído Perlin e imagens semelhantes, onde cada ponto é calculado de forma independente.
- Renderização de computação gráfica . Na animação por computador , cada quadro ou pixel pode ser renderizado de forma independente (veja renderização paralela ).
- Pesquisas de força bruta em criptografia . Exemplos notáveis do mundo real incluem Distributed.net e sistemas de prova de trabalho usados em criptomoeda .
- O BLAST pesquisa em bioinformática para consultas múltiplas (mas não para grandes consultas individuais).
- Sistemas de reconhecimento facial em grande escala que comparam milhares de rostos adquiridos arbitrariamente (por exemplo, um vídeo de segurança ou vigilância via televisão de circuito fechado ) com um número igualmente grande de rostos armazenados anteriormente (por exemplo, uma galeria de rogues ou lista de observação semelhante ).
- Simulações de computador comparando muitos cenários independentes.
- Algoritmos genéticos .
- Cálculos de conjunto de previsão numérica do tempo .
- Simulação e reconstrução de eventos em física de partículas .
- O algoritmo dos quadrados de marcha .
- Passo de peneiramento da peneira quadrática e da peneira de campo numérico .
- Etapa de crescimento da árvore da técnica de aprendizado de máquina florestal aleatório .
- Transformada discreta de Fourier, onde cada harmônico é calculado de forma independente.
- Redes neurais convolucionais em execução em GPUs .
- Pesquisa de grade de hiperparâmetros em aprendizado de máquina.
- Pesquisa paralela em programação de restrição
Implementações
- Em R (linguagem de programação) - o pacote Simple Network of Workstations (SNOW) implementa um mecanismo simples para usar um conjunto de estações de trabalho ou um cluster Beowulf para cálculos constrangedoramente paralelos.
Veja também
- A lei de Amdahl define o valor P , que seria quase ou exatamente igual a 1 para problemas constrangedoramente paralelos.
- Mapa (padrão paralelo)
- Multiprocessamento
- Maciçamente paralelo
- Computação paralela
- Programação orientada a processos
- Arquitetura sem compartilhamento (SN)
- Multiprocessamento simétrico (SMP)
- Máquina de Conexão
- Autômato celular
- Framework CUDA
- Processador manycore
- Processador vetorial
Referências
-
^
Herlihy, Maurice; Shavit, Nir (2012). The Art of Multiprocessor Programming, Revised Reprint (edição revisada). Elsevier. p. 14. ISBN 9780123977953. Retirado em 28 de fevereiro de 2016 .
Alguns problemas computacionais são “embaraçosamente paralelos”: eles podem ser facilmente divididos em componentes que podem ser executados simultaneamente.
- ^ Seção 1.4.4 de: Foster, Ian (1995). Projetando e criando programas paralelos . Addison – Wesley. ISBN 9780201575941. Arquivado do original em 01/03/2011.
- ^ Alan Chalmers; Erik Reinhard; Tim Davis (21 de março de 2011). Renderização paralela prática . CRC Press. ISBN 978-1-4398-6380-0.
- ^ Matloff, Norman (2011). The Art of R Programming: A Tour of Statistical Software Design , p.347. Sem amido. ISBN 9781593274108 .
- ^ Leykin, Anton; Verschelde, Jan; Zhuang, Yan (2006). Algoritmos de homotopia paralela para resolver sistemas polinomiais . Tramitação do ICMS . Notas de aula em Ciência da Computação. 4151 . pp. 225–234. doi : 10.1007 / 11832225_22 . ISBN 978-3-540-38084-9.
- ^ Moler, Cleve (1986). Heath, Michael T. (ed.). Computação matricial em multiprocessadores de memória distribuída . Multiprocessadores Hypercube . Society for Industrial and Applied Mathematics, Filadélfia. ISBN 978-0898712094.
- ^ The Intel hypercube parte 2 publicado no blog Cleve's Corner no site The MathWorks
- ^ Kepner, Jeremy (2009). MATLAB paralelo para computadores multicore e multinó , p.12. SIAM. ISBN 9780898716733 .
- ^ Erricos John Kontoghiorghes (21 de dezembro de 2005). Handbook of Parallel Computing and Statistics . CRC Press. ISBN 978-1-4200-2868-3.
- ^ Yuefan Deng (2013). Computação paralela aplicada . World Scientific. ISBN 978-981-4307-60-4.
- ^ Josefsson, Simon; Percival, Colin (agosto de 2016). "A função de derivação de chave baseada em senha scrypt" . tools.ietf.org . Retirado 2016-12-12 .
- ^ Fórum SeqAnswers
- ^ Como tornamos nosso reconhecedor de rosto 25 vezes mais rápido (postagem do blog do desenvolvedor)
- ^ Shigeyoshi Tsutsui; Pierre Collet (5 de dezembro de 2013). Computação Evolutiva Massivamente Paralela em GPGPUs . Springer Science & Business Media. ISBN 978-3-642-37959-8.
- ^ Youssef Hamadi; Lakhdar Sais (5 de abril de 2018). Handbook of Parallel Constraint Reasoning . Springer. ISBN 978-3-319-63516-3.
- ^ Pacote Rede Simples de Estações de Trabalho (SNOW)
links externos
- Computações embaraçosamente paralelas , projetando um cluster de computação no estilo Beowulf
- " Star-P: Computação Paralela de Alta Produtividade "