Lei de Amdahl

A lei de Amdahl nomeia o teto que o trabalho serial restante impõe à aceleração paralela. Se uma fração P de um programa pode rodar de forma concorrente e o restante precisa ficar sequencial, acrescentar processadores nunca multiplica o tempo de execução por N. A aceleração teórica é um sobre um menos P mais P sobre N: o resto serial permanece no denominador por maior que N se torne. Esta calculadora da lei de Amdahl aceita a fração paralelizável e a contagem de processadores e então devolve o fator de aceleração, a fração serial, a eficiência paralela e o limite assintótico serial um sobre um menos P sempre que reste trabalho serial. A aritmética é uma identidade de forma fechada, plenamente determinística, sem simulação e sem modelo de linguagem. Serve para dimensionar um cluster, rebater uma afirmação ingênua de N vezes ou conferir uma curva de aceleração de livro antes de comprar hardware.

O que a lei de Amdahl mede e como se obtém o fator de aceleração

A lei de Amdahl é a observação de Gene Amdahl de 1967: o trabalho serial que sobra limita o quanto um programa inteiro pode ficar mais rápido, por mais processadores que se apliquem à parte paralela. Escreva P para a fração do tempo de relógio de um único processador que pode rodar de forma concorrente, e N para a contagem de processadores. A fração sequencial é um menos P.

Depois de dividir o trabalho paralelo em N partes, o tempo relativo passa a ser um menos P mais P sobre N, de modo que a aceleração teórica S de N é o recíproco dessa soma: um dividido por um menos P mais P sobre N. Quando P vale um, cada ciclo se paraleliza e a aceleração é igual a N. Quando P vale zero, a tarefa é puramente serial e a aceleração permanece um para qualquer N.

Entre esses extremos, a aceleração cresce com N mas achata em direção ao limite serial um sobre um menos P. Esse teto é o ponto da lei: um programa que é só cinco por cento serial nunca ultrapassa uma aceleração de vinte vezes, mesmo em um milhão de núcleos, porque os cinco por cento seriais continuam depois que o oceano paralelo foi fatiado até o infinito. A eficiência paralela é a aceleração dividida por N; ela cai conforme N cresce, salvo se P for exatamente um.

Esta calculadora avalia essas identidades de forma direta. Não é um profiler, nem um simulador de eventos discretos, nem o modelo de aceleração escalada de Gustafson, que formula outra pergunta ao fazer o problema crescer com a máquina. Se você conhece P por medição ou por uma estimativa de envelope que separa laços quentes e preparação, a fórmula de Amdahl dá a aceleração teórica que se deve esperar antes que efeitos de cache, contenção de locks ou tráfego NUMA piorem a curva real.

Onde uma calculadora da lei de Amdahl rende o investimento

Use a ferramenta do navegador quando estiver dimensionando um cluster, revisando uma afirmação de desempenho de que a aceleração acompanhará a contagem de núcleos, ou mostrando em aula por que noventa e cinco por cento paralelo ainda estanca em vinte vezes. Aumente N até a aceleração se aproximar do limite serial e pare de comprar núcleos que você não consegue colher.

Contraste o resultado com a lei de Gustafson se a carga crescer com a máquina; Amdahl mantém o tamanho do problema fixo, que é o limite conservador para lotes, compiladores e kernels científicos que não aumentam por mágica quando se acrescentam soquetes. Os resultados são plenamente determinísticos: os mesmos P e N sempre produzem o mesmo vetor de aceleração, de modo que você pode fixar exemplos em testes e materiais de aula. Não há modelo de linguagem, nem serviço externo de profiling, nem aleatoriedade.