Processadores Para o Próximo Milênio - Parte 2

Lei de Amdhal

Apesar do quanto promissor a computação paralela possa parecer, ela não é uma solução para todo o problema de processamento. Existem tarefas que são eminentemente seqüenciais e que não tiram proveito de um computador paralelo. Voltando ao nosso exemplo da construção de uma casa, apesar dela ser executada em paralelo, existe por detrás uma seqüência que deve ser obedecida. Nessa construção, não podemos fazer o telhado antes de termos as paredes prontas e também não podemos construir as paredes antes do alicerce. Assim, é comum que as tarefas a serem executadas possuam porções paralelizáveis e porções que precisam ser executadas de forma seqüencial. Note que um computador paralelo operando de forma seqüencial é um grande desperdício, pois enquanto um processador trabalha no trecho serial, todos os demais ficam ociosos.

Abordando esse tema, Amdahl propôs uma expressão para esse problema, que ficou conhecida como Lei de Amdahl[3] e que está representada a seguir. A explicação é muito simples. Imaginemos uma tarefa que executada em uma máquina seqüencial gaste "T" segundos. Porém, quando preparada para execução em uma máquina paralela, ela tem uma porção que obrigatoriamente deve ser executada de forma serial. Digamos que "p" represente a porção serial, em conseqüência "(1-p)" representa a porção paralelizável. Quando executado em uma máquina paralela com N processadores, o tempo gasto será igual a "".

Somente o trecho paralelizável tira partido dos "N" processadores. Assim o Ganho de Processamento é dado por: ou  que é a forma consagrada da Lei de Amdahl. Deve-se notar que estamos ignorando os custos de sincronização e de troca de parâmetros entre os processadores. Vejamos em um gráfico o desempenho de alguns programas, segundo essa lei. A Figura 7 apresenta 4 casos. A curva em vermelho é a de uma tarefa 100% paralelizável, ou seja, p = 0. Nesse caso o aumento do número de processadores reflete linearmente no desempenho. A curva em verde ilustra o caso de p = 0,001 ou 0,1%, ou seja, apenas 0,1 % das tarefas não puderam ser paralelizadas. A curva em azul é para o caso onde 1% (p = 0,01) da tarefa precisa ser executada de forma serial. Nota-se uma grande queda de desempenho para grande quantidade de processadores. A última curva representa o caso de uma tarefa onde 10% (p = 0,1) precisam ser executadas de forma serial. Nota-se que há uma saturação, e que o aumento de processadores, por exemplo, de 50 para 100 processadores, pouca diferença traz para o desempenho.

Devem ser ressaltados dois pontos importantes. O primeiro é que, exceto para o caso de p = 0, todos os demais casos irão apresentar saturação em algum ponto. Se p é pequeno, a saturação só ocorre com um elevado número de processadores. O segundo ponto é que, contrastando com a Figura 7, a Lei de Amdahl não prevê queda no desempenho, no pior caso, ele fica fixo em algum valor.

Figura 7: Exemplos da Lei da Amdahl.