Complexidade em paralelo
Trabalho e profundidade, o teto de Amdahl, e por que dez núcleos não dividem o tempo por dez.
Com mais de um núcleo, um número só não descreve o custo. São dois, e a distância entre eles é o quanto o problema aceita ser dividido.
| Medida | Símbolo | O que é |
|---|---|---|
| trabalho | T₁ | o total de operações — o custo com um processador |
| profundidade | T∞ | a cadeia mais longa de dependências — o custo com infinitos processadores |
O tempo com p processadores fica entre os dois, e nunca abaixo da profundidade: T_p ≥ max(T₁/p, T∞). O paralelismo do algoritmo é T₁/T∞ — quantos processadores adiantam antes de sobrar.
Somar um milhão de números#
| Forma | Trabalho T₁ | Profundidade T∞ | Paralelismo |
|---|---|---|---|
| laço sequencial | O(n) | O(n) | 1 — não divide |
| soma em árvore | O(n) | O(log n) | n / log n |
O mesmo trabalho, profundidades diferentes. O laço obriga cada soma a esperar a anterior; a árvore soma pares independentes e depois pares de pares. É por isso que >> distill é sequencial por definição e uma redução por partes não é.
O teto de Amdahl#
Se uma fração s do programa é inerentemente sequencial, o ganho máximo é 1 / s, não importa quantos núcleos existam:
| Parte sequencial | Ganho máximo | Com 10 núcleos |
|---|---|---|
| 0% | ∞ | 10,0x |
| 5% | 20x | 6,9x |
| 10% | 10x | 5,3x |
| 25% | 4x | 3,1x |
| 50% | 2x | 1,8x |
Dez por cento de código sequencial já corta o ganho de dez núcleos quase pela metade. Ler o arquivo, montar a lista e imprimir o resultado contam nesses dez por cento.
O que se mede de verdade#
Oito blocos de CPU numa máquina de 10 núcleos, comparando a série com processos de verdade:
adopt Arcane.Concurrent as P
adopt Arcane.Time as T
action pesado(semente):
total := 0
cycle i from 1 to 400000:
total += (i * semente) % 7
yield total
lotes := [1, 2, 3, 4, 5, 6, 7, 8]
inicio := T.monotonic()
serie := [pesado(s) cycle s in lotes]
ms_serie := (T.monotonic() - inicio) * 1000
inicio := T.monotonic()
processos := P.map_processos(pesado, lotes)
ms_proc := (T.monotonic() - inicio) * 1000
out $"serie: {round(ms_serie, 0)} ms"
out $"processos: {round(ms_proc, 0)} ms ({round(ms_serie / ms_proc, 2)}x)"
out $"igual: {serie is processos}"serie: 4069 ms
processos: 864 ms (4.71x)
igual: yes4,71x com 8 tarefas em 10 núcleos — e não 8x. O que falta foi para a partida dos processos, a cópia dos dados e a coleta dos resultados. É a diferença entre o modelo e a máquina, e ela é sempre nessa direção.
Threads não dividem trabalho de CPU#
O mesmo teste com thread em vez de processos dá 0,97x — ligeiramente pior que a série. O GIL do Python deixa uma thread por vez executar bytecode: para CPU, thread não é paralelismo.
| Ferramenta | Serve para | Ganho em CPU |
|---|---|---|
thread: / parallel: | rede, disco, banco, espera | nenhum — o GIL serializa |
async / await | entrada e saída sobreposta | nenhum em CPU, muito em I/O |
P.map_processos | trabalho de CPU | medido: 4,71x em 10 núcleos |
P.pool_processos() | CPU, muitas vezes seguidas | evita os ~100 ms de partida por chamada |
Complexidade de comunicação#
Num processo separado, o dado precisa atravessar. Isso é custo que a versão sequencial não tem, e ele entra na conta:
- O que atravessa é copiado. Mandar um record de trinta campos junto de cada lote copia trinta campos por lote.
- Por isso o pacote vai uma vez por processo, no início, e o que cada lote leva é um índice.
- Lote grande demais desequilibra: um processo termina e fica ocioso enquanto o outro ainda trabalha.
- Lote pequeno demais paga comunicação mais vezes do que trabalha.
A regra prática: divida em algumas vezes mais lotes do que núcleos — o suficiente para equilibrar, longe o bastante de comunicar a cada item.