Computação paralela
A computação paralela é uma técnica que permite a execução simultânea de múltiplos cálculos ou processos. Essa abordagem é especialmente útil para resolver problemas complexos, pois permite dividi-los em partes menores que podem ser processadas ao mesmo tempo. Existem diversas formas de computação paralela, como paralelismo em nível de bit, de instrução, de dados e de tarefas. Embora historicamente utilizada em computação de alto desempenho, a computação paralela ganhou destaque devido às limitações físicas no aumento da frequência dos processadores e à crescente preocupação com o consumo de energia. Atualmente, tornou-se o paradigma dominante na arquitetura de computadores, especialmente com o advento dos processadores multinúcleo.
Pontos-chave
- Computação paralela executa múltiplos cálculos simultaneamente, dividindo grandes problemas em partes menores.
- Existem diferentes tipos de paralelismo: em nível de bit, instrução, dados e tarefas.
- A computação paralela é crucial devido às limitações de escalonamento de frequência e ao consumo de energia.
- Processadores multinúcleo são a forma mais comum de computação paralela hoje.
- A Lei de Amdahl define o ganho máximo de desempenho em sistemas paralelos.
Tradicionalmente, o software era executado sequencialmente, uma instrução por vez. A computação paralela inverte isso, utilizando múltiplos elementos de processamento para resolver um problema simultaneamente, dividindo-o em partes independentes. Essa abordagem, que começou em aplicações científicas e simulações, levou ao desenvolvimento de hardware e software paralelos e à computação de alto desempenho.
Leis de Desempenho Paralelo
Idealmente, o paralelismo dobraria a velocidade com o dobro de processadores. No entanto, a Lei de Amdahl descreve o ganho máximo de desempenho, considerando que nem todas as partes de um programa podem ser paralelizadas. Ela destaca a importância de equilibrar aprimoramentos nas partes paralelizáveis e não paralelizáveis, mostrando que adicionar mais processadores pode ter retornos decrescentes e ignora sobrecargas de comunicação e sincronização.
Dependências e Paralelismo
Para que um algoritmo paralelo funcione, é crucial entender as dependências de dados entre as partes do programa. Cálculos dependentes devem seguir uma ordem específica, formando um 'caminho crítico'. As Condições de Bernstein definem quando segmentos de programa são independentes e podem ser executados em paralelo, evitando problemas como violação de fluxo, antidependência e dependência de saída.
Sincronização e Desaceleração
Threads (subtarefas) em computação paralela frequentemente precisam acessar recursos compartilhados de forma sincronizada. A falta de sincronização pode levar a 'condições de corrida'. Mecanismos como 'locks' garantem acesso exclusivo (exclusão mútua), mas podem causar lentidão e 'deadlocks' (bloqueio mútuo). Algoritmos 'lock-free' e 'wait-free' evitam locks, mas são complexos. A sincronização em 'barreiras' é comum.
Tipos de Paralelismo (Grão)
Aplicações paralelas são classificadas pelo grau de comunicação entre suas subtarefas: 'Grão Fino' (comunicação frequente), 'Grão Grosso' (comunicação menos frequente) e 'Embarrassingly Parallel' (comunicação rara, mais fácil de paralelizar).
Taxonomia de Flynn
Michael J. Flynn propôs um sistema clássico para classificar computadores e programas com base no número de fluxos de instruções e dados. Este modelo, embora simples, é amplamente utilizado por sua clareza e por oferecer uma boa aproximação das arquiteturas paralelas.
A computação paralela pode incorrer em custos significativos de sobrecarga, especialmente na fusão de dados de múltiplos processos. A comunicação e a sincronização entre tarefas podem ser ordens de magnitude mais caras do que o processamento em thread única, exigindo uma avaliação cuidadosa do ganho de desempenho global.
A granularidade refere-se à frequência de comunicação entre as subtarefas em um sistema paralelo. Existem diferentes níveis de paralelismo explorados no hardware e software.
Paralelismo em Nível de Bit
Nas décadas de 1970 a 1980, o aumento da velocidade era obtido expandindo o tamanho da palavra de máquina (a quantidade de dados processada por ciclo). Processadores de 8, 16, 32 e, mais tarde, 64 bits reduziram o número de instruções necessárias para operar com dados maiores.
Paralelismo em Nível de Instrução
Um programa é uma sequência de instruções. O paralelismo em nível de instrução permite que processadores reordenem e executem múltiplas instruções simultaneamente, sem alterar o resultado do programa. Processadores modernos usam 'pipelines' (sequências de estágios) e múltiplas unidades de execução para alcançar um desempenho superior a uma instrução por ciclo (IPC > 1), sendo chamados 'superscalares'.
Paralelismo de Tarefas
Neste tipo, diferentes cálculos são executados simultaneamente, cada um em seus próprios dados. Isso contrasta com o paralelismo de dados, onde o mesmo cálculo é aplicado a múltiplos conjuntos de dados. O paralelismo de tarefas envolve decompor um problema em subtarefas independentes e alocá-las a diferentes processadores.
Paralelismo em Nível de Superpalavra
Esta técnica de vetorização automática explora o paralelismo em código 'inline' (direto no código) através de técnicas como desenrolar laços e vetorização de blocos básicos, sendo útil em manipulações como cores ou coordenadas.
A arquitetura de hardware é fundamental para a computação paralela, envolvendo como a memória é acessada e como os diferentes componentes se comunicam.
Memória e Comunicação
A memória pode ser compartilhada (um único espaço de endereçamento) ou distribuída (lógica e fisicamente separada). Arquiteturas como NUMA (Non-Uniform Memory Access) são comuns em sistemas distribuídos, onde o acesso à memória local é mais rápido. Supercomputadores utilizam interconexões de alta velocidade e sistemas de memória compartilhada distribuída.
Classes de Computadores Paralelos
Computadores paralelos são classificados pela proximidade dos nós de processamento. Processadores multinúcleo (vários núcleos no mesmo chip) diferem de sistemas SMP (Symmetric Multiprocessing), que possuem múltiplos processadores compartilhando memória via barramento. Tecnologias como multithreading permitem que um único núcleo execute múltiplos fluxos de instruções simultaneamente.
O desenvolvimento de software para computação paralela envolve linguagens de programação, bibliotecas e técnicas para gerenciar a execução em múltiplos processadores.
Linguagens de Programação Paralela
Existem linguagens, bibliotecas e APIs específicas para programação paralela, categorizadas pelo modelo de memória (compartilhada, distribuída ou mista). POSIX Threads e OpenMP são comuns para memória compartilhada, enquanto MPI domina a passagem de mensagens. Conceitos como 'futuros' e padrões como OpenHMPP facilitam a programação e otimização.
Paralelização Automática
A capacidade de um compilador de automaticamente paralelizar um programa é um objetivo de longa data na computação paralela. No entanto, os resultados práticos dessa abordagem ainda são limitados, principalmente a algoritmos científicos e numéricos específicos.
Checkpointing de Aplicação
Em sistemas com muitos processadores, a probabilidade de falha aumenta. O 'checkpointing' permite salvar o estado de uma aplicação em intervalos regulares, possibilitando a retomada da execução a partir do último ponto salvo em caso de falha, o que é crucial para a confiabilidade.
A capacidade de processamento aumentada pela computação paralela permite resolver problemas antes intratáveis em áreas como bioinformática e economia, incluindo análise de sequências e dobramento de proteínas.
A computação paralela pode ser usada para aumentar a tolerância a falhas através de sistemas 'lockstep', onde operações são executadas em paralelo para redundância. Se os resultados divergem, erros podem ser detectados e corrigidos, protegendo contra falhas transitórias.
As raízes da computação paralela remontam a ideias do século XIX com Charles Babbage. Na década de 1950, designs para paralelismo começaram a surgir, como o Gamma 60. Décadas seguintes viram o desenvolvimento de sistemas multiprocessadores, a Lei de Amdahl e arquiteturas como SMP e C.mmp.
Nos anos 1970, a teoria 'Society of Mind' de Marvin Minsky propôs que o cérebro funciona como um sistema massivamente paralelo, composto por muitos 'agentes' simples que, juntos, criam a inteligência.
