Paralelismo

O panorama geral e o vocabulário

Pense numa cozinha. Um cozinheiro que faz 100 sanduíches faz um de cada vez. Quatro cozinheiros em quatro mesas fazem juntos. O sanduíche é o trabalho, cada cozinheiro é um trabalhador (worker), e eles trabalham em paralelo porque todos cozinham no mesmo instante.

Palavras que você vai encontrar

O speed-up é "quantas vezes mais rápido". Se um trabalho leva 120 segundos sozinho e 20 segundos com ajudantes, o speed-up é 6. Boa parte desta área explica por que esse número costuma ser menor que o número de ajudantes.

Paralelismo de dados e paralelismo de tarefas

Há dois grandes jeitos de cortar um trabalho em pedaços. No álbum de figurinhas, você pode dar a cada amigo uma parte das figurinhas (mesmo serviço, figurinhas diferentes). Ou pode dar a cada amigo uma tarefa diferente: um recorta, um cola, um escreve as legendas.

Quando um laço pode ser dividido?

Um laço (loop) pode virar paralelismo de dados quando suas iterações são independentes: nenhuma lê um valor que outra escreve. Aí as voltas podem rodar em qualquer ordem, até ao mesmo tempo. O tamanho e a duração das voltas afetam só o desempenho, não a correção.

O paralelismo de tarefas tem um teto

Digamos que três tarefas independentes levam 6 s, 3 s e 3 s. Cada uma roda no seu núcleo. O tempo total é o da tarefa mais longa, 6 s, mesmo numa máquina de 16 núcleos. O speed-up é 12 / 6 = 2. Só dividir os dados dentro das tarefas usaria os outros núcleos.

As tarefas também podem depender umas das outras. A cadeia mais longa de tarefas dependentes é o caminho crítico. Nenhum número de processadores deixa o programa mais rápido que essa cadeia. Exemplo: A (4 s), B (3 s) e D (5 s) são livres, C (2 s) precisa de A e B, E (1 s) precisa de C e D. A cadeia A, C, E leva 4 + 2 + 1 = 7 s. O trabalho total é 15 s, então o melhor speed-up é 15 / 7, cerca de 2,1.

A(4) --\
         +--> C(2) --\
B(3) --/             +--> E(1)
D(5) ---------------/

cadeia mais longa: A -> C -> E = 7 s

Três armadilhas

• Pedaços desiguais. Contar primos por divisão custa mais para números grandes. Se 4 trabalhadores recebem 4 blocos iguais de números, o que pegou o bloco mais alto termina por último e os outros ficam parados.
• Pedaços pequenos demais. Criar uma tarefa para cada uma de 10 milhões de iterações minúsculas custa mais que o próprio trabalho. Agrupe as iterações em blocos. Isso é granularidade.
• Threads demais. Se 8 requisições iniciam 8 threads cada uma numa máquina de 8 núcleos, 64 threads brigam por 8 núcleos. Isso se chama oversubscription (excesso de threads). Gera trocas de contexto e briga de cache, sem velocidade extra. Use um único pool de trabalhadores do tamanho do número de núcleos.

Speed-up, eficiência e escalabilidade

Como dizer que um programa paralelo é "bom"? Medindo. Dois números fazem quase todo o trabalho.

• Speed-up: S(N) = T(1) / T(N). É o tempo com 1 trabalhador dividido pelo tempo com N trabalhadores, ambos em tempo de relógio (wall-clock). O sonho é S(N) = N, o speed-up linear.
• Eficiência: E(N) = S(N) / N. Diz quanto de cada trabalhador virou ganho. Com speed-up linear, E vale 1, ou 100%.

Exemplo: um programa leva 120 s com 1 trabalhador e 20 s com 8. O speed-up é 120 / 20 = 6. A eficiência é 6 / 8 = 75%. Um quarto da capacidade paga não virou ganho: 120 s de trabalho ocuparam 8 x 20 = 160 s de trabalhadores.

A eficiência costuma cair

Uma tabela de speed-ups engana, porque o speed-up continua subindo enquanto cada novo trabalhador ajuda menos. Olhe a eficiência:

Escalabilidade forte e fraca

Exemplo de escalabilidade fraca: 1 trabalhador resolve um problema de tamanho n em 50 s. 8 trabalhadores resolvem um problema de tamanho 8n em 62,5 s. A eficiência fraca é 50 / 62,5 = 80%. O speed-up escalado (tempo que um trabalhador levaria no problema grande, dividido pelo tempo real) é 8 x 0,8 = 6,4.

Compare com a base certa

O programa paralelo com 1 trabalhador já paga por dividir e esperar. Se você dividir por esse tempo, o programa parece melhor do que é. Este repositório usa o melhor programa sequencial como base (speed-up absoluto). Exemplo: o sequencial leva 10 s, o paralelo leva 12,5 s com 1 thread e 3,125 s com 4 threads. Contra ele mesmo, 12,5 / 3,125 = 4 parece perfeito. O speed-up real é 10 / 3,125 = 3,2.

O speed-up pode passar de N?

Às vezes sim, e se chama speed-up superlinear. Acontece quando o trabalho paralelo fica mais barato, e não só dividido. A causa mais comum é o cache: o vetor inteiro não cabe no cache de um núcleo, mas um oitavo dele cabe, então cada núcleo lê de memória rápida. Outra causa é uma busca em que um trabalhador acha a resposta cedo e para os outros.

Leis de Amdahl e de Gustafson

Você está fazendo uma pizza. A massa precisa descansar 10 minutos, e só uma pessoa pode esperar por ela. Dez cozinheiros não fazem a massa descansar mais rápido. Essa espera é a parte serial. O resto (cortar os recheios) pode ser dividido.

Lei de Amdahl

Chame de s a fatia do tempo sequencial que não pode ser paralelizada (0,1 é 10%). Só a outra parte, 1 - s, encolhe quando adicionamos N trabalhadores:

S(N) = 1 / ( s + (1 - s) / N )

N -> muito grande:   S -> 1 / s

O termo (1 - s) / N é a parte paralela depois de dividida entre N trabalhadores, como fração do tempo original. O speed-up nunca passa de 1 / s. Com s = 10%, o teto é 10, mesmo com mil processadores, porque os 10% seriais ainda rodam em um só trabalhador.

Pratique com números:

1. 80% paralelo, 4 processadores: o tempo vira 0,2 + 0,8 / 4 = 0,4, então o speed-up é 2,5.
2. Um programa de 100 s com 10 s de trabalho serial precisa terminar em 25 s. Então 10 + 90 / N é no máximo 25, logo N é no mínimo 6 (não os 4 do palpite linear).
3. Fração serial de 25%: com 8 processadores S é 2,91, com 16 é 3,37. O dobro de hardware, só cerca de 16% a mais de velocidade. Perto do limite, cada novo trabalhador devolve menos.

Lei de Gustafson

Gustafson olha a mesma história por outro lado. Quando ganhamos mais trabalhadores, em geral não rodamos o mesmo problema pequeno mais rápido: rodamos um problema maior no mesmo tempo (uma imagem mais nítida, um mapa do tempo mais detalhado). A parte paralela cresce com o problema, a parte serial quase não. O speed-up escalado é:

S(N) = s' + (1 - s') * N

s' = fração serial medida na execução PARALELA

Exemplo: uma execução em 16 processadores gasta 10% do tempo em código serial. S = 0,1 + 0,9 x 16 = 14,5.

As duas leis se contradizem?

Não. São o mesmo cálculo com a fração serial medida em bases diferentes. Amdahl mede s no tempo da execução sequencial. Gustafson mede s' no tempo da execução paralela e reconstrói o que um processador levaria. A ligação é s = s' / (s' + (1 - s') x N). Uma fração que parece grande no tempo paralelo é pequena no tempo sequencial.

Ajustando a lei a números reais

A métrica de Karp-Flatt vira Amdahl de cabeça para baixo. A partir de um speed-up medido S em N processadores, ela dá a fração serial que o explicaria: s = (1/S - 1/N) / (1 - 1/N). Exemplo: S = 4 com N = 8 dá (0,25 - 0,125) / 0,875, cerca de 14%.

Depois observe como s se comporta quando N cresce. Se fica constante, a velocidade perdida vem de código realmente serial. Se cresce (5% com 2 processadores, 8% com 4, 14% com 8), a causa é overhead: espera, briga de cache, carga desbalanceada. Encurtar o código serial não resolveria.

Fork-join e roubo de trabalho

A professora pede que você some todos os números de uma lista longa. Você corta a lista em duas e pede a um amigo que some uma metade enquanto você soma a outra. Depois você espera o amigo e soma as duas respostas. Você acabou de fazer fork-join.

• Fork: uma tarefa cria subtarefas que podem rodar em paralelo.
• Join: a tarefa espera todas elas terminarem antes de continuar.
• Todo fork tem o seu join, então o programa volta a ser sequencial em pontos claros, e o resultado é fácil de raciocinar.

O join também é uma regra de segurança. Quando ele retorna, tudo que o outro trabalhador fez já aconteceu e está visível. Se você ler a contagem parcial do amigo antes do join, pode receber um valor pela metade ou uma data race.

soma(0..800)
  fork -> soma(0..400)    soma(400..800)
            fork            fork
          200  200        200  200
          (folhas: somadas num laço simples)
  join <- soma as duas metades

O cutoff (tamanho do grão)

Continuamos dividindo até o pedaço ficar menor que um limite chamado cutoff, e então somamos com um laço simples. Cutoff pequeno demais: gasta-se mais tempo criando e escalonando tarefas do que somando. Cutoff grande demais: poucas tarefas, e alguns núcleos ficam sem nada. Um bom grão custa muito mais que o overhead de uma tarefa e ainda gera muito mais tarefas que núcleos.

Divisão estática e dinâmica

Imagine uma imagem de 8 linhas. As linhas 0 a 3 custam 2 ms cada, as linhas 4 a 7 custam 10 ms cada. Dois trabalhadores:

O jeito dinâmico custa um acesso ao contador compartilhado por pedaço, um preço pequeno pelo equilíbrio.

Roubo de trabalho (work stealing)

Os pools modernos (fork-join do Java, Rayon em Rust, Go, Cilk) usam work stealing. Cada trabalhador tem a sua lista de tarefas, uma deque. Ele trabalha pela sua ponta, da tarefa mais nova para a mais velha (LIFO). Quando a lista esvazia, ele rouba uma tarefa de outro trabalhador, pela ponta oposta, a tarefa mais antiga.

Por que a tarefa mais antiga? Numa recursão de dividir e conquistar, a tarefa mais antiga costuma ser a maior, então um roubo traz muito trabalho. A tarefa mais nova é pequena e seus dados ainda estão quentes no cache do dono. Outro ganho: com uma única fila central, todos os trabalhadores brigam pela mesma porta. Com roubo, o caminho normal é local, e os trabalhadores só conversam quando alguém fica ocioso.

Trabalho e span

• Trabalho (work) T1: o tempo com 1 processador (a soma de todas as operações).
• Span Tinf: o tempo com processadores ilimitados (o caminho crítico).
• Um escalonador guloso (greedy) garante Tp <= T1 / P + Tinf. Nenhum escalonador vence max(T1 / P, Tinf).
• Paralelismo é T1 / Tinf. Ele limita o speed-up para qualquer número de processadores.

Exemplos: T1 = 240 s e Tinf = 6 s com P = 8 dá no máximo 240 / 8 + 6 = 36 s. T1 = 1.000 s e Tinf = 10 s tem paralelismo 100, então 100 processadores bastam para chegar perto do limite e os outros 900 de uma máquina de 1.000 processadores são desperdiçados.

Reduções e ordenação paralelas

Uma redução (reduction) espreme muitos valores em um só: a soma de uma lista, o maior número, a contagem de primos. No jeito sequencial você percorre a lista com um total corrente. Em paralelo, você dá a cada trabalhador um bloco (chunk), cada um reduz o seu bloco numa variável local, e no fim os resultados parciais são combinados.

Como cada trabalhador escreve só no seu parcial, ninguém briga durante o trabalho.

Quais operadores são seguros?

Uma redução em blocos calcula (a op b) op (c op d) em vez de ((a op b) op c) op d. Os dois coincidem para qualquer entrada só se o operador for associativo: o agrupamento não importa.

Prova com a subtração em [8, 4, 2, 1]: sequencial ((8 - 4) - 2) - 1 = 1. Em dois blocos, (8 - 4) - (2 - 1) = 3. Diferente, então a subtração não pode ser reduzida em paralelo.

A redução em árvore

Com processadores ilimitados, combine os valores em pares, depois os pares de pares, e assim por diante. O número de valores cai pela metade a cada passo.

8 valores:  a b c d e f g h
passo 1:    ab  cd  ef  gh
passo 2:     abcd    efgh
passo 3:       abcdefgh

O número de passos (a profundidade) é ceil(log2 n). O total de operações continua sendo n - 1, igual ao jeito sequencial. Para 1.000 valores: 10 passos e 999 operações.

Soma de prefixos (scan)

A soma de prefixos dá, em cada posição i, a combinação dos elementos de 0 a i. O laço comum usa o resultado anterior, então parece impossível paralelizar. Com um operador associativo, resolve-se em duas passadas sobre uma árvore: o up-sweep guarda a soma de cada bloco, e o down-sweep entrega a cada posição a soma de tudo que está à esquerda. O trabalho é O(n) e a profundidade O(log n): para n = 8, 3 níveis em cada passada.

Merge sort em paralelo

O merge sort é natural para o paralelismo. O vetor é cortado no meio, e as duas metades são ordenadas sem se tocar, então podem ser duas tarefas paralelas. A dependência aparece só no merge, que precisa das duas metades prontas.

Mas se cada merge é sequencial, o caminho crítico tem um merge inteiro por nível: n + n/2 + n/4 + ..., menos que 2n. Para n = 1.024 o trabalho é cerca de 1.024 x 10 = 10.240 e o span cerca de 2.047, então o melhor speed-up fica perto de 5, não importa quantos processadores você tenha. Para ir além, o próprio merge precisa ser paralelizado.

Sample sort

Com p trabalhadores, o sample sort usa p - 1 valores chamados separadores (splitters) para dividir a entrada em p baldes, um por trabalhador. Cada um ordena o seu balde, e os baldes juntados em ordem já estão ordenados. O tempo paralelo é o do maior balde, então separadores ruins estragam tudo. A solução: tirar uma amostra aleatória dos dados, ordená-la e usar seus quantis como separadores. Assim os baldes ficam com tamanhos quase iguais.

Map-reduce e outros padrões paralelos

Um padrão é uma receita que as pessoas reaproveitam. Imagine uma escola contando votos para a melhor fruta. Vários ajudantes leem cada um algumas cédulas e anotam "banana: 1" para cada uma (isso é o map). Depois todas as anotações de "banana" vão para a mesma caixa (isso é o shuffle), e um ajudante por caixa soma (isso é o reduce).

MapReduce passo a passo

entrada map (muitas máquinas)    shuffle        reduce

livro 1 -> (o,1)(gato,1)(o,1)  -+
livro 2 -> (gato,1)(sentou,1)  -+--> o: [1,1]     -> o: 2
livro 3 -> (o,1)(tapete,1)     -+     gato: [1,1]  -> gato: 2
                                      sentou: [1]  -> sentou: 1

• Map aplica a mesma função a cada registro e emite zero ou mais pares chave-valor. Os registros não dependem uns dos outros, então rodam em qualquer ordem em tantas máquinas quantas você tiver.
• Shuffle move e agrupa os pares para que todos os valores de uma chave cheguem ao mesmo lugar. Uma função de partição (muitas vezes um hash da chave) escolhe o reducer. Costuma ser o passo que mais usa a rede.
• Reduce é chamado uma vez por chave, com todos os valores dela. Chaves diferentes podem ser reduzidas em paralelo.

O combiner

Mandar um milhão de pares (o, 1) pela rede é bobagem. Um combiner é um pequeno reduce executado dentro de cada tarefa map, antes do shuffle. Com 3 tarefas map que emitem 1.000 pares cada, com 50 palavras distintas, o combiner deixa só 50 registros por tarefa, então 150 registros vão para o shuffle em vez de 3.000. Só vale quando a operação é associativa e comutativa, como a soma. Uma média não pode ser combinada assim, a menos que você leve junto a contagem.

Falhas e chaves quentes

• Reexecução. Se um trabalhador morre no meio de uma tarefa map, o master roda a mesma tarefa em outro nó. É seguro porque a entrada não muda e a função map é pura (mesma entrada, mesma saída, sem efeitos colaterais). Chama-se tarefa idempotente. Um map que escreve num banco de dados ou lê o relógio poderia duplicar ou alterar resultados.
• Chave quente (hot key). Se uma chave concentra 55% de todos os pares, um reducer recebe essa parte e a fase termina quando ele termina. Dobrar o número de reducers só redistribui as outras chaves. Soluções: um combiner, ou dividir a chave quente em subchaves e somar em duas etapas.

Outros padrões

Exemplo de scatter-gather: uma busca envia uma consulta a 20 partições do índice e espera todas. Dezenove respondem em 20 ms e uma em 200 ms. A junção leva 5 ms. A resposta chega depois de 205 ms, porque um ajudante lento decide.

Exemplo de stencil: a[i] = (a[i-1] + a[i+1]) / 2 escrito no mesmo vetor quebra quando as threads dividem a faixa de índices, porque uma célula pode já ter o valor novo quando o vizinho a lê. O double buffering faz o resultado independer da ordem.

Determinismo e reprodutibilidade

Se você pedir "2 + 2" a uma calculadora dez vezes, sempre vem 4. Um programa paralelo determinístico é assim: a saída depende só da entrada. O escalonador pode intercalar as threads de um jeito diferente a cada execução, mas todos os caminhos levam à mesma resposta. É isso que permite testar a versão paralela comparando com a sequencial.

Data race e condição de corrida

Uma data race acontece quando duas threads tocam o mesmo endereço de memória, pelo menos uma escreve, e nada ordena os acessos (nem lock, nem operação atômica, nem join). O valor final depende da sorte. Em C e C++ o comportamento passa a ser indefinido. Rust seguro rejeita esse código na compilação.

Uma condição de corrida (race condition) é mais ampla: um resultado que depende de como as threads se intercalam. Você pode ter uma race condition sem data race. Veja este código de verificar-e-agir, em que cada método trava a conta por dentro:

// duas threads rodam isto ao mesmo tempo, saldo começa em 100
if acct.Balance() >= 100 { // trava, lê, destrava
	acct.Withdraw(100) // trava, subtrai, destrava
}

As duas threads veem 100, as duas sacam, e o saldo termina em -100. A decisão tomada na verificação já não era verdadeira quando a ação rodou. A solução é fazer a verificação e a ação um único passo atômico (uma só seção crítica, ou um método que verifica e saca).

Por que somas paralelas são exatamente iguais, ou não

Contar primos com contadores locais e somá-los depois do join dá exatamente a resposta sequencial com qualquer número de threads. A soma de inteiros é associativa e comutativa, então o agrupamento não importa. Comparar por igualdade exata é válido.

Números decimais (ponto flutuante, como double) são diferentes. Cada soma arredonda o resultado para o valor mais próximo que o computador consegue guardar, então (a + b) + c pode diferir de a + (b + c). Pegue [1e16, -1e16, 1.0], onde os vizinhos de 1e16 estão a 2 de distância. Da esquerda para a direita: (1e16 - 1e16) + 1 = 1. Dividindo em [1e16] e [-1e16, 1.0]: o segundo parcial é -1e16 + 1, que arredonda de volta para -1e16, e o total é 0. Outra resposta, e bem diferente.

Números aleatórios e ordem da saída

• Números aleatórios. Numa simulação Monte Carlo com tarefas distribuídas dinamicamente, amarre a aleatoriedade ao índice da tarefa, não à thread. Cada tarefa cria o seu gerador com uma semente calculada a partir da semente base e do seu índice, de preferência com um gerador feito para fluxos independentes.
• Ordem da saída. Os trabalhadores terminam numa ordem imprevisível. Faça cada resultado carregar a sua posição lógica: escreva o resultado i na posição i, ou devolva parciais com o índice e combine-os em ordem de índice depois do join. A ordem de execução fica livre, e a ordem da saída fica fixa.

O tempo não é determinístico

Mesmo quando o resultado é idêntico, o tempo varia: 410 ms numa execução, 470 ms na seguinte. O escalonador, a carga da máquina, o estado do cache e a frequência da CPU mudam. Um benchmark reprodutível usa a mesma entrada e a mesma máquina, deixa o aquecimento (warm-up) de fora, repete a execução várias vezes, informa a dispersão junto com o valor central e registra a máquina, as versões e o comando exato.

Falso compartilhamento e efeitos de cache

A memória é lenta, então cada núcleo guarda uma pequena cópia rápida do que usa, chamada cache. Mas o cache não guarda variáveis soltas. Ele guarda blocos chamados linhas de cache, em geral de 64 bytes. Toque num byte e o bloco inteiro de 64 bytes entra.

Falso compartilhamento (false sharing)

Quando um núcleo escreve numa linha, as cópias dessa linha nos outros núcleos são invalidadas (jogadas fora) para todos ficarem coerentes. Se variáveis de threads diferentes estão na mesma linha, os núcleos ficam roubando a linha um do outro, embora não compartilhem nenhum dado de verdade. Isso é o falso compartilhamento.

uma linha de cache de 64 bytes (8 contadores de 8 bytes)
[c0][c1][c2][c3][c4][c5][c6][c7]
  ^   ^   ^   ^   ^   ^   ^   ^
  8 threads em 8 núcleos, cada uma soma no seu ci
  -> a linha fica pulando entre os núcleos

Contando quem atrapalha quem: o deslocamento em bytes dividido por 64 dá a linha. 16 contadores de 8 bytes começando no limite de uma linha: os contadores 0 a 7 estão na linha 0 e 8 a 15 na linha 1. A thread 3 briga com as outras 7 threads do seu grupo, e os dois grupos não se atrapalham.

Como perceber

A assinatura: nenhum lock, todos os núcleos a 100%, tempo paralelo igual ou pior que o sequencial (por exemplo 2,0 s com 1 thread e 3,1 s com 4), e uma melhora drástica (para 0,52 s) quando você só afasta os contadores 64 bytes. Os núcleos estão ocupados, mas esperando a linha voltar.

Como consertar

• Acumule numa variável local dentro do laço quente e entregue o total uma vez, depois do laço. A linha que o trabalhador modifica passa a ser só dele, e a junção acontece uma vez por trabalhador.
• Preencha ou alinhe cada contador na sua própria linha, por exemplo com alignas(64) em C++. O preço é memória: 8 bytes viram 64, então um vetor de 8 dessas structs cresce de 64 para 512 bytes.

Localidade espacial

Como uma falha (miss) carrega uma linha inteira, usar dados vizinhos é barato. Uma matriz de 1024 x 1024 inteiros de 4 bytes guardada por linhas: uma falha traz 16 inteiros, então percorrer linha por linha falha 1 vez em 16, cerca de 65.536 falhas no total (1.048.576 / 16). Percorrer por colunas salta 4.096 bytes a cada passo. Se o cache não comporta as 1.024 linhas de uma coluna, todo acesso falha: 16 vezes mais.

Limitado por CPU contra limitado por memória

Um laço que conta primos quase não usa memória, e cada núcleo traz seu próprio poder de cálculo, então escala quase linearmente (7,6 vezes com 8 threads). Um laço que soma um vetor de 16 GiB depende da vazão dos canais de memória, um recurso compartilhado por todos os núcleos. Quando ela satura, mais threads só dividem a mesma banda: 2,9 vezes com 4 threads e nenhum ganho com 8.

SIMD e vetorização

O paralelismo também vive dentro de um núcleo. Imagine um carimbo que imprime 8 pontos de uma vez em vez de 1. Isso é SIMD, de Single Instruction, Multiple Data (uma instrução, vários dados). Um registrador vetorial guarda vários números do mesmo tipo, e uma instrução soma, multiplica ou compara todos juntos.

Ele independe de threads, e os dois podem ser combinados. Na taxonomia de Flynn:

Faixas (lanes)

O número de elementos por instrução (as lanes) é a largura do registrador dividida pela largura do elemento. Um registrador de 256 bits e floats de 32 bits dão 256 / 32 = 8 lanes. Esse também é o teto do ganho do corpo do laço. Na prática você ganha menos por causa do laço de resto, do acesso à memória e da frequência menor em algumas CPUs.

Quando n não é múltiplo da largura, o compilador faz dois laços: o laço vetorial roda floor(n / 8) vezes e o laço de resto cuida dos últimos n mod 8 elementos um a um. Para 1.003 floats: 125 iterações vetoriais (1.000 elementos) e 3 escalares. Em vetores curtos o resto pode esconder o ganho do SIMD.

Auto-vetorização

O compilador pode fazer isso sozinho. Ele analisa um laço escalar e, se consegue provar que o resultado não muda, emite instruções vetoriais. Você ajuda mantendo o laço simples: iterações independentes, sem chamadas de função opacas, sem dúvida sobre sobreposição de vetores.

O que bloqueia a vetorização

• Dependência carregada pelo laço (loop-carried). Em a[i] = a[i-1] + b[i] cada elemento precisa do que acabou de ser escrito (uma soma de prefixos), então 8 elementos não podem ser calculados juntos. Já a[i] = a[i+1] + b[i] é válido: o valor lido é sempre o original.
• Aliasing de ponteiros. Com float *dst, const float *src, o compilador precisa admitir que os dois podem se sobrepor, o que criaria uma dependência. Ele adiciona uma checagem em tempo de execução, ou você tira a dúvida com o qualificador restrict em C. As fatias &mut e & do Rust já garantem que não há sobreposição.
• Desvios por elemento. Um vetor tem um único fluxo de controle, então if (a[i] > 0) b[i] = a[i] * 2 vira dado: a comparação monta uma máscara, o trabalho é feito em todas as lanes, e a máscara decide o que é gravado (if-conversion). O custo é fazer trabalho que será descartado, então o ganho cai quando o desvio é caro e raramente tomado.

// vetoriza: as iterações são independentes
for (int i = 0; i < n; i++) c[i] = a[i] + b[i];

// não vetoriza: cada passo precisa do resultado anterior
for (int i = 1; i < n; i++) a[i] = a[i - 1] + b[i];

Fundamentos de computação em GPU

Uma CPU é como 8 professores muito inteligentes: cada um resolve rápido problemas difíceis e diferentes. Uma GPU (unidade de processamento gráfico) é como um estádio cheio de milhares de alunos, cada um simples, todos mandados fazer o mesmo cálculo pequeno ao mesmo tempo em números diferentes.

O kernel

Na CPU você escreve for (i = 0; i < n; i++) out[i] = f(in[i]). Na GPU você escreve só o corpo, como uma função chamada kernel, e a dispara sobre um espaço de índices de n posições. Cada thread recebe o seu índice de thread, que faz o papel de i, e cuida de um elemento. Isso só é correto quando as iterações são independentes, a mesma condição do paralelismo de dados na CPU.

Por que desvios e ponteiros encadeados doem

Uma GPU agrupa threads que executam a mesma instrução juntas, como as lanes de um vetor. Se um desvio manda metade do grupo para um lado e metade para o outro, o hardware percorre os dois caminhos um depois do outro, e a vazão cai. Os núcleos simples também não têm a predição de desvios nem os caches grandes com que uma CPU absorve código irregular.

Vale a viagem?

A GPU tem a sua própria memória. Os dados precisam ser copiados para lá e de volta, e iniciar um kernel tem um custo fixo. Então o tempo na GPU tem três partes: cálculo, transferência, lançamento.

Exemplo: a CPU custa 40 ns por elemento. A GPU calcula em 4 ns por elemento, copiar custa 6 ns por elemento, e o lançamento custa 30 ms fixos. O ganho por elemento é 40 - (4 + 6) = 30 ns. O ponto de equilíbrio é 30 ms / 30 ns = 1.000.000 de elementos. Abaixo disso a CPU vence. Se a cópia custasse mais que a economia no cálculo, a GPU nunca compensaria.

Amdahl ainda vale para qualquer acelerador. Um programa leva 100 s: 80 s num kernel e 20 s que precisam ficar na CPU. O kernel fica 20 vezes mais rápido (4 s), e as transferências somam 6 s. Novo tempo: 20 + 4 + 6 = 30 s, speed-up 3,33. Sem as transferências seria 24 s e 4,17. O limite com um kernel infinitamente rápido é 100 / 20 = 5. A transferência é um novo termo serial que não existia na versão sequencial.

Memória compartilhada e distribuída

Dois jeitos de organizar ajudantes. Numa sala de aula com um quadro grande, todos leem e escrevem no mesmo quadro. Isso é memória compartilhada. Num grupo de amigos em casas diferentes, cada um tem um caderno, e eles se ligam para trocar informações. Isso é memória distribuída.

Threads compartilham, processos em outros nós enviam

As threads de um processo compartilham o heap e as variáveis globais; cada uma tem só a sua pilha e os seus registradores. A comunicação é direta, e escritas concorrentes exigem sincronização. Na memória distribuída cada processo vê só a sua memória. Quem tem o dado o envia e quem precisa dele o recebe. Você decide o quê, para quem e quando, e paga o custo de copiá-lo pela rede.

Exemplo: somar 1.000.000 de inteiros de 8 bytes com 4 trabalhadores. Com threads, cada uma recebe um ponteiro e um tamanho: nenhum byte é copiado. Com troca de mensagens, um master envia um quarto a cada trabalhador: 4 mensagens de 2.000.000 de bytes cada, 8.000.000 de bytes na ida, mais 4 respostas de 8 bytes, 32 bytes na volta, em 8 mensagens.

UMA e NUMA

A memória compartilhada tem duas formas. Em UMA (acesso uniforme à memória) toda CPU leva o mesmo tempo para alcançar qualquer endereço. Em NUMA (não uniforme) cada nó tem CPUs e um banco de memória próximos. O acesso local é rápido, e ler uma página que mora em outro nó é mais lento. O programa continua correto, mas o desempenho depende de manter os dados perto de quem os usa.

Por que máquinas distribuídas chegam a mais processadores

Na memória compartilhada, cada nova CPU disputa o mesmo barramento, a mesma banda de memória e o mesmo tráfego de coerência de cache. Na memória distribuída cada nó é um computador completo, então não há um único ponto de contenção. O preço: toda cooperação custa mensagens, então o algoritmo precisa se comunicar pouco.

Memória compartilhada distribuída (DSM)

Uma DSM baseada em páginas cria a ilusão de memória compartilhada sobre mensagens. Tocar numa página ausente gera uma falta (page fault), e o tratador busca a página em outro nó. A unidade é a página inteira, então duas variáveis x e y sem relação na mesma página, escritas pelos nós A e B, fazem a página ficar pulando pela rede. É falso compartilhamento de novo, em escala maior, chamado thrashing.

Programas híbridos

Muitos programas misturam os dois: processos com troca de mensagens entre nós (por exemplo MPI) e threads dentro de cada nó. Cada camada traz seus próprios bugs. Uma data race só pode acontecer onde a memória é comum, ou seja, entre threads do mesmo processo. Um deadlock não precisa de memória comum: dois processos que fazem, cada um, um receive bloqueante do outro antes de enviar vão esperar para sempre.

Juntando tudo

Este repositório mediu essas ideias no mini-projeto scaling-by-cores: ele conta primos e renderiza uma imagem de Mandelbrot em Rust, Go e C++ com 1, 2, 4 e 8 trabalhadores, com divisão estática e dinâmica. As 72 execuções imprimiram exatamente os mesmos resultados dos programas sequenciais (uma redução determinística e um escritor por pixel).

Mesmo código, só a divisão mudou, e o speed-up dobrou. A divisão estática deu as linhas caras do meio a poucos trabalhadores e os outros esperaram. A lei de Amdahl leu essa espera como código serial: uma fração serial ajustada perto de 30%, num programa que quase não tem nenhuma. Com a divisão dinâmica ela caiu abaixo de 7%. A lição: antes de culpar Amdahl, confira se todo trabalhador está ocupado até o fim.

Uma lista de checagem para um programa paralelo lento

Qual ferramenta para qual problema