thumb|300px|Grandes supercomputadores como o Blue Gene/P da IBM são projetados para explorar intensivamente o paralelismo.
Computação paralela é um tipo de computação em que muitos cálculos ou processos são realizados simultaneamente. Problemas de grande porte muitas vezes podem ser divididos em partes menores, que podem então ser solucionadas ao mesmo tempo. Existem várias formas de computação paralela: Paralelismo em nível de bit, Paralelismo em nível de instrução, Paralelismo de dados e Paralelismo de tarefas. O paralelismo há muito é empregado em computação de alto desempenho, mas ganhou interesse mais amplo devido às limitações físicas que impedem o escalonamento de frequência.S.V. Adve et al. (November 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda" (PDF). Parallel@Illinois, University of Illinois at Urbana-Champaign. "The main techniques for these performance benefits—increased clock frequency and smarter but increasingly complex architectures—are now hitting the so-called power wall. The computer industry has accepted that future performance increases must largely come from increasing the number of processors (or cores) on a die, rather than making a single core go faster." Como o consumo de energia (e consequentemente a geração de calor) pelos computadores se tornou uma preocupação nos últimos anos,Asanovic et al. Old [conventional wisdom]: Power is free, but transistors are expensive. New [conventional wisdom] is [that] power is expensive, but transistors are "free". a computação paralela tornou-se o paradigma dominante em arquitetura de computadores, principalmente na forma de processadores multinúcleo.Asanovic, Krste et al. (December 18, 2006). "The Landscape of Parallel Computing Research: A View from Berkeley" (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. "Old [conventional wisdom]: Increasing clock frequency is the primary method of improving processor performance. New [conventional wisdom]: Increasing parallelism is the primary method of improving processor performance… Even representatives from Intel, a company generally associated with the 'higher clock-speed is better' position, warned that traditional approaches to maximizing performance through maximizing clock speed have been pushed to their limits."
thumb|Paralelismo vs concorrência Em ciência da computação, paralelismo e concorrência são duas coisas diferentes: um programa paralelo utiliza múltiplos núcleos de CPU, cada núcleo executando uma tarefa de forma independente. Por outro lado, concorrência possibilita que um programa lide com várias tarefas mesmo em um único núcleo de CPU; o núcleo alterna entre tarefas (isto é, threads) sem necessariamente concluir cada uma. Um programa pode apresentar características de paralelismo, de concorrência, ambos ou nenhum dos dois.
Computadores paralelos podem ser classificados conforme o nível em que o hardware suporta paralelismo: computadores multinúcleo e multiprocessadores simétricos possuem vários elementos de processamento numa única máquina, enquanto clusters, MPPs e grids usam múltiplos computadores para trabalhar na mesma tarefa. Arquiteturas especializadas são às vezes usadas juntamente com processadores tradicionais para acelerar tarefas específicas.
Em alguns casos o paralelismo é transparente ao programador, como no paralelismo em nível de bit ou em nível de instrução, mas algoritmos paralelos explícitos, especialmente os que usam concorrência, são mais difíceis de escrever do que algoritmos sequenciais, pois a concorrência introduz várias novas classes de potenciais bugs, sendo as condições de corrida as mais comuns. Comunicação e sincronização entre subtarefas são frequentemente alguns dos maiores obstáculos para obter desempenho ótimo.
Um limite teórico para o aceleração de um programa pela paralelização é dado pela Lei de Amdahl, que afirma que ela é limitada pela fração de tempo que pode ser paralelizada.
Antecedentes Tradicionalmente, software de computador era escrito para computação serial. Para resolver um problema, constrói-se um algoritmo e o implementa como um fluxo serial de instruções. Essas instruções são executadas em uma unidade central de processamento de um único computador. Apenas uma instrução é executada por vez — após sua conclusão, a próxima é executada.
Por outro lado, a computação paralela usa múltiplos elementos de processamento simultaneamente para resolver um problema. Isso é feito dividindo o problema em partes independentes, de modo que cada elemento execute sua parte do algoritmo ao mesmo tempo que os demais. Os elementos podem incluir um único computador com vários processadores, vários computadores em rede, hardware especializado ou qualquer combinação. Historicamente, a computação paralela era usada em aplicações científicas e simulações, particularmente nas ciências naturais e de engenharia, como meteorologia. Isso levou ao desenvolvimento de hardware e software paralelos, bem como à computação de alto desempenho.
O escalonamento de frequência foi o principal fator de melhoria em desempenho de computador de meados dos anos 1980 até 2004. O tempo de execução de um programa é o número de instruções multiplicado pelo tempo médio por instrução. Aumentar a frequência do relógio reduz esse tempo médio, diminuindo o tempo total de programas CPU-bound. Contudo, o consumo de energia ‹P› de um chip é dado por ‹P› = ‹C› × ‹V›² × ‹F›, onde ‹C› é a capacitância comutada (proporcional ao número de transistores ativos), ‹V› é a tensão e ‹F› é a frequência do relógio. Aumentos em ‹F› elevam o consumo. Esse problema levou ao cancelamento dos processadores Tejas and Jayhawk da Intel em 8 de maio de 2004, marcando o fim do escalonamento de frequência como paradigma dominante.
Para mitigar consumo e calor, fabricantes de CPU começaram a produzir processadores energeticamente eficientes com múltiplos núcleos. Cada núcleo é independente e acessa a mesma memória concorrentemente. Processadores multinúcleo trouxeram a computação paralela a computadores de mesa. Em 2012, processadores quad-core tornaram-se padrão em desktops, enquanto servidores já possuíam 10+ núcleos. Até 2023, alguns chegavam a mais de cem núcleos, inclusive com núcleos de desempenho e eficiência (como ARM big.LITTLE). Pela Lei de Moore, prevê-se que o número de núcleos dobrará a cada 18–24 meses.
Um sistema operacional pode distribuir tarefas em múltiplos núcleos. Contudo, para que software serial aproveite totalmente o multicore, o programador deve reestruturar e paralelizar o código. O ganho de desempenho não virá mais do aumento de frequência, mas da paralelização do software.
Leis relevantes right|thumbnail|300px|Uma representação gráfica da Lei de Amdahl. A lei demonstra o ganho teórico máximo de um sistema e o conceito de retornos decrescentes. Se exatamente 50% do trabalho pode ser paralelizado, o melhor ganho possível é 2×. Se 95% pode, o melhor ganho é 20×. Segundo a lei, mesmo com processadores infinitos, o ganho é limitado pela parte não paralelizável. thumb|300px|Suponha uma tarefa com duas partes independentes, A e B. B leva 25% do tempo total. Tornar B 5× mais rápida reduz pouco o tempo total, enquanto tornar A 2× mais rápida melhora mais, apesar do ganho de B ser maior (5× vs 2×).
Artigo principal: Lei de Amdahl
Ideally, o Speedup da paralelização seria linear — dobrar o número de elementos de processamento reduziria o tempo pela metade; dobrar novamente, reduziria pela metade de novo. Porém, raros algoritmos alcançam esse ganho ótimo. A maioria tem aceleração quase linear para poucos elementos, mas estagna com muitos.
O ganho potencial máximo de um sistema é calculado pela Lei de Amdahl. A Lei de Amdahl indica que o melhor desempenho é alcançado equilibrando aprimoramentos em componentes paralelizáveis e não paralelizáveis, e mostra retornos decrescentes ao adicionar processadores.
A Lei de Amdahl tem limitações: assume carga fixa, ignora sobrecargas de comunicação e sincronização, foca no aspecto computacional e negligencia fatores extrínsecos como persistência de dados, E/S e acesso à memória.
As leis de Gustafson e Lei de Escalabilidade Universal oferecem avaliações mais realistas do desempenho paralelo. thumb|right|300px|Representação da lei de Gustafson
Dependências Compreender dependências de dados é fundamental para algoritmos paralelos. Nenhum programa pode rodar mais rápido que o maior caminho crítico (a longa cadeia de cálculos dependentes), pois cálculos dependentes devem seguir ordem. Mas a maioria dos algoritmos não é apenas uma longa cadeia; há oportunidades de paralelismo.
Sejam Pi e Pj segmentos de programa. As condições de Bernstein definem quando são independentes e podem rodar em paralelo:
Violação de fluxo ocorre na primeira, antidependência na segunda, e dependência de saída na terceira.
Exemplos:
: 1: function Dep(a, b) : 2: c := a * b : 3: d := 3 * c : 4: end function
Aqui, instrução 3 depende de 2 (fluxo), não podendo rodar antes ou em paralelo.
: 1: function NoDep(a, b) : 2: c := a * b : 3: d := 3 * b : 4: e := a + b : 5: end function
Sem dependências, todas podem rodar em paralelo.
Bernstein não permite memória compartilhada; para isso, é preciso impor ordenação entre acessos, como semáforos ou barreiras.
Condições de corrida, exclusão mútua, sincronização e desaceleração paralela Subtarefas são chamadas threads. Algumas arquiteturas usam fibers ou processes, mas "threads" é o termo genérico. Threads frequentemente precisam de acesso sincronizado a um recurso, como ao atualizar uma variável compartilhada. Sem sincronização, instruções podem ser entrelaçadas de modo incorreto, criando condição de corrida. Exemplo:
Thread AThread B1A: Ler V1B: Ler V2A: +1 a V2B: +1 a V3A: Gravar V3B: Gravar V
Se 1B ocorre entre 1A e 3A, dados incorretos resultam. Usa-se lock para exclusão mútua:
Thread AThread B1A: Bloquear V1B: Bloquear V2A: Ler V2B: Ler V3A: +1 a V3B: +1 a V4A: Gravar V4B: Gravar V5A: Desbloquear V5B: Desbloquear V
Locks garantem correção, mas podem retardar e afetar confiabilidade.
Bloquear múltiplas variáveis com locks não atômicos pode causar deadlock. Locks atômicos bloqueiam múltiplas variáveis de uma vez, evitando deadlocks.
Muitos programas exigem que threads sincronizem em barreiras, implementadas com locks ou semáforos. Algoritmos lock-free e wait-free evitam locks, mas são difíceis e exigem estruturas de dados especiais.
Nem toda paralelização resulta em aceleração: threads podem gastar mais tempo comunicando ou esperando recursos. Quando sobrecarga de comunicação domina, mais threads podem aumentar o tempo — chamado parallel slowdown. Pode ser mitigado por análise e redesenho de software.
Paralelismo de grão fino, grosso e embarassingly parallel Aplicações são classificadas segundo a frequência de comunicação entre subtarefas. Se precisam se comunicar muitas vezes por segundo, têm paralelismo de grão fino; poucas vezes, grão grosso; raramente, Embarrassingly parallel, as mais fáceis de paralelizar.
Taxonomia de Flynn
Michael J. Flynn criou um dos primeiros sistemas de classificação para computadores e programas, conhecido como Taxonomia de Flynn. Ele classificou conforme o número de fluxos de instruções e dados:
SISD (Single Instruction, Single Data): programa totalmente sequencial. SIMD (Single Instruction, Multiple Data): mesma operação em múltiplos dados, comum em processamento de sinais. MISD (Multiple Instruction, Single Data): raro; arquiteturas como systolic array foram propostas mas pouco usadas. MIMD (Multiple Instruction, Multiple Data): mais comum em programas paralelos.
Segundo David A. Patterson e John L. Hennessy, "Algumas máquinas são híbridas destas categorias, mas este modelo clássico sobrevive por ser simples, fácil de entender e oferecer uma boa aproximação. É também — talvez por sua compreensão clara — o esquema mais amplamente usado."Patterson and Hennessy, p. 748.
Desvantagens