3,473 leituras

Um mergulho profundo na lei de Amdahl e na lei de Gustafson

por Durganshu Mishra14m2023/11/11

Muito longo; Para ler

A Lei de Gustafson é adequada quando um algoritmo pode ajustar dinamicamente a quantidade de computação para corresponder à paralelização disponível. Em contraste, a Lei de Amdahl é mais adequada quando a carga de computação é fixa e não pode ser alterada significativamente pela paralelização. Testes fracos e de escala devem ser realizados dependendo da natureza do problema.

featured image - Um mergulho profundo na lei de Amdahl e na lei de Gustafson

Imagine o seguinte: você está com pressa para preparar um banquete delicioso, mas está limitado pelo tamanho da sua cozinha e pelo número de mãos no convés. No mundo da computação paralela, a Lei de Amdahl e a Lei de Gustafson são as receitas confiáveis que você precisa para otimizar sua obra-prima culinária. Eles são como os ingredientes secretos que temperaram o desempenho dos computadores durante décadas, permitindo-nos deleitar-nos com velocidades de processamento cada vez mais rápidas. Esses dois princípios podem ser o yin e o yang da computação paralela e têm guiado os magos experientes em tecnologia em sua busca para conquistar o reino dos processadores multi-core e da computação de alto desempenho. Mas quais são as leis de Amdahl e de Gustafson, e como elas fazem sua mágica separadamente ou em conjunto? Estando cientes da importância da programação paralela , hoje mergulharemos nos meandros dessas leis e descobriremos como elas podem ser utilizadas como ferramentas poderosas nas mãos de programadores experientes.

Índice

Lei de Amdahl: Antecedentes
– Aceleração Máxima
- Ressalvas
Lei de Gustafson: Antecedentes
– Aceleração em escala
- Ressalvas
Dimensionamento forte versus dimensionamento fraco
– Testes de escala
- Escala forte
– Escala fraca
Conclusões

Lei de Amdahl: Antecedentes

Em 1967, na Spring Joint Computer Conference, o Dr. Gene Amdahl, fazendo algumas magias computacionais sérias na IBM, se reuniu com três outras pessoas que entendem de tecnologia, incluindo o cérebro Daniel Slotnick, o gênio por trás do funcionamento interno do Illiac-IV. O que eles estavam fazendo, você pergunta? Bem, eles estavam discutindo o futuro da arquitetura de computadores. Durante esta conferência, o Dr. Gene Amdahl expôs suas idéias sobre os obstáculos enfrentados pela “abordagem multiprocessador” ao lidar com problemas do mundo real e todas as suas peculiaridades complicadas. E adivinhe, ele elogiou a “abordagem de processador único” para questões dessa natureza!

Enquanto estava na IBM, Amdahl percebeu que uma parte substancial do trabalho computacional era ocupada pelo que ele apropriadamente chamou de “ manutenção do gerenciamento de dados ”. Ele argumentou firmemente que essa fração específica permaneceu notavelmente consistente por cerca de uma década, absorvendo consistentemente 40% das instruções executadas em execuções de produção.

O que se enquadra neste trabalho de “administração doméstica”? Abrange uma ampla gama de tarefas computacionais que, embora essenciais, não contribuem diretamente para a missão central da computação. Dependendo do algoritmo e da aplicação específicos, isso pode envolver E/S de dados, pré-processamento, gerenciamento de memória, manipulação de arquivos e muito mais. Esta consistência sugere que, para muitas aplicações, uma parte substancial do tempo de processamento é gasta nestas tarefas. Um certo nível de manutenção do gerenciamento de dados é quase inevitável e difícil de minimizar significativamente. Amdahl observa que essa sobrecarga parece sequencial, o que significa que ocorre passo a passo e não é adequada para técnicas de processamento paralelo.

“Uma conclusão bastante óbvia que pode ser tirada neste ponto é que o esforço despendido para alcançar altas taxas de processamento paralelo é desperdiçado, a menos que seja acompanhado por conquistas em taxas de processamento sequencial de quase a mesma magnitude.” - Dr.

Em seu artigo original [1], Amdahl acrescenta que o domínio das tarefas de “gestão doméstica” é apenas a ponta do iceberg em relação aos desafios enfrentados pela abordagem “multiprocessador”. Com sua impressionante experiência como físico teórico treinado e com doutorado, Amdahl possuía uma compreensão íntima dos desafios físicos do mundo real que os computadores foram projetados para enfrentar. Ele destaca muitas complicações, como limites irregulares, interiores não uniformes e dependências espaciais e temporais de estados variáveis, todas elas apresentando obstáculos formidáveis para o paradigma do “multiprocessador”.

Por exemplo, considere calcular a distribuição de calor em uma grade cartesiana 2D. Em qualquer ponto, a temperatura (T) depende das temperaturas dos pontos vizinhos. Ao empregar um modelo de computação paralela, é essencial comunicar esses valores com pontos adjacentes, que podem ser armazenados em processadores separados. Essas questões continuam a ser difundidas nos cenários contemporâneos.

Felizmente, a engenhosidade coletiva de especialistas em computação produziu numerosos métodos numéricos e técnicas de programação adaptadas para enfrentar de frente esses intrincados desafios.

Lei de Amdahl: Aceleração Máxima

Em seu trabalho original, a formulação de Amdahl não se aprofundou em equações matemáticas; foi somente em análises subsequentes que a aceleração máxima foi quantificada.

A Lei de Amdahl baseia-se na suposição de que uma fração f do tempo de execução de um programa serial é idealmente paralelizável sem qualquer sobrecarga de comunicação ou sincronização. A parcela complementar, representada como s = 1 − f, é inteiramente sequencial.

Assim, se T é o tempo de execução do programa sequencial, o tempo de execução em p núcleos, T(p), é dado por:

Speedup , sendo a razão entre o tempo de execução sequencial e o tempo de execução paralela, fornece:

Assim, o limite superior da aceleração pode ser definido como:

Ressalvas

Apesar de sua simplicidade, a lei de Amdahl tem suas limitações. O modelo ignora gargalos críticos de hardware, como largura de banda de memória, latência e restrições de E/S. Ele também não considera as desvantagens de desempenho da criação de threads, sincronização, sobrecarga de comunicação e outros fatores do mundo real. Lamentavelmente, estes factores não contabilizados têm geralmente um impacto negativo no desempenho real.

A figura a seguir ilustra o impacto da paralelização na aceleração, conforme determinado pela lei de Amdahl. É claro que, mesmo com uma fração paralela substancial de 95% e uma vasta gama de processadores, a aceleração máxima alcançável é de cerca de 20 vezes. Aumentar a porcentagem de paralelização para 99% e empregar um número infinito de processadores pode gerar uma aceleração de 100x mais impressionante, o que é promissor.

No entanto, é crucial reconhecer que ter tantos processadores é uma raridade . Muitas vezes trabalhamos com um número muito mais modesto, como 64 ou até menos.

Quando aplicamos a lei de Amdahl a um programa que utiliza 64 processadores (com f sendo 95%), a aceleração máxima gira em torno de 15,42x. É certo que este número não é muito promissor!

Este insight é um tanto obscurecido pelo limite empregado nesta expressão:

Limite

Esse limite tende a ocultar o fato de que os números de aceleração são notavelmente mais baixos quando consideramos os números práticos e reais de processadores.

No entanto, a desvantagem mais significativa da lei de Amdahl reside na sua suposição de que o tamanho do problema permanece constante ao utilizar mais núcleos para executar uma aplicação.

Essencialmente, presume-se que a fração paralelizável permanece inalterada, independentemente do número de núcleos empregados. Esta limitação foi completamente abordada e ampliada por John L. Gustafson , que propôs uma perspectiva modificada agora conhecida como lei de Gustafson . No entanto, apesar destas questões e advertências reconhecidas, é essencial reconhecer que a lei de Amdahl tem os seus próprios méritos, oferecendo informações valiosas sobre as complexidades da paralelização. A lei de Amdahl encontra aplicação na forma de testes de escala fortes , um tópico que exploraremos mais tarde.

Lei de Gustafson: Antecedentes

Enquanto trabalhava nos sistemas de computação massivamente paralelos nos Laboratórios Nacionais Sandia, o Dr. John L. Gustafson e sua equipe obtiveram fatores de aceleração impressionantes para três aplicações diferentes em um hipercubo de 1024 processadores. A fração do código serial correspondeu a 0,4–0,8%.

“…alcançamos os fatores de aceleração em um hipercubo de processador 1024 que acreditamos serem sem precedentes: 1021 para análise de tensão de feixe usando gradientes conjugados, 1020 para simulação de onda de superfície confusa usando diferenças finitas explícitas e 1016 para fluxo de fluido instável usando correção de fluxo transporte." - Dr.

Vimos claramente na última seção que, de acordo com a lei de Amdahl, a aceleração máxima alcançável para um grande número de processadores é 1/s. Então, como essa aceleração desconcertante de 1021x pode ser alcançada?

Gustafson [2] destacou que a expressão matemática tem uma suposição sutil, implicando que a variável f não está relacionada a p . No entanto, este cenário raramente é a realidade que encontramos. Em cenários do mundo real, normalmente não pegamos um problema de tamanho fixo e o executamos em diferentes números de processadores, exceto talvez no ambiente controlado da pesquisa acadêmica. Em vez disso, em aplicações práticas, o tamanho do problema tende a aumentar em conjunto com o número de processadores.

Quando processadores mais potentes ficam disponíveis, os usuários se adaptam, expandindo a complexidade do problema para aproveitar ao máximo os recursos aprimorados. Eles podem ajustar aspectos como resolução da grade, número de intervalos de tempo, complexidade do operador de diferença e outros parâmetros para garantir que o programa possa ser executado no período de tempo desejado.

De acordo com Gustafson, muitas vezes é mais realista assumir que, na prática, o tempo de execução permanece relativamente constante, em vez do tamanho do problema.

Gustafson percebeu que a fração paralela ou vetorial de um programa cresce proporcionalmente ao tamanho do problema. Elementos como inicialização vetorial, carregamento de programas, gargalos seriais e operações de E/S, que contribuem coletivamente para o componente s do tempo de execução do programa, normalmente permanecem relativamente constantes e não apresentam crescimento significativo com o tamanho do problema.

Gustafson levou o argumento mais longe, enfatizando que em cenários onde duplicamos os graus de liberdade numa simulação física, uma duplicação correspondente da contagem de processadores é muitas vezes essencial. Como estimativa preliminar, o volume de trabalho que pode ser efetivamente distribuído em paralelo tende a crescer linearmente com o número de processadores.

Em seu exame aprofundado das três aplicações mencionadas, Gustafson e seus colegas descobriram que o componente paralelo exibia fatores de escala de aproximadamente 1.023,9969, 1.023,9965 e 1.023,9965.

Lei de Gustafson: aceleração escalonada

A suposição de Gustafson reside em considerar o tempo de execução normalizado em p núcleos, que soma (1 − f) + f , resultando em um valor geral de 1. Por esta lógica, se (1 − f) + f significa o tempo de execução em p núcleos , então o tempo de execução em um único núcleo pode ser expresso como (1 − f) + p*f . Consequentemente, a aceleração, que Gustafson chamou de “ aceleração escalonada ”, pode ser calculada da seguinte forma:

Quando aplicamos a lei de Gustafson a um programa que utiliza 64 processadores (com f sendo 95%), o aumento de velocidade previsto é de 60,85x (em comparação com 15,42x com a lei de Amdahl). Agora estamos conversando😉

As figuras a seguir destacam as diferenças entre as duas leis.

Ressalvas

As perspectivas de Amdahl e Gustafson oferecem visões distintas sobre paralelização, cada uma com suas próprias suposições.

A lei de Amdahl assume que a quantidade de trabalho que pode ser paralelizado é constante e independente do número de processadores, o que a torna muito pessimista. A perspectiva de Gustafson, que assume que a quantidade de trabalho que pode ser paralelizado cresce linearmente com o número de núcleos, é sem dúvida prática para muitos cenários. No entanto, às vezes pode ser excessivamente otimista.

Os aplicativos do mundo real frequentemente encontram restrições que podem limitar essa escalabilidade linear. Por exemplo, à medida que o número de núcleos aumenta, podem ocorrer retornos decrescentes devido a complexidades no processamento paralelo, dependências de dados e sobrecarga de comunicação. Além disso, as limitações de hardware praticamente restringem o número de núcleos que podem ser efetivamente integrados em um único chip. A lei de Gustafson nem sempre pode dar conta destes intrincados desafios do mundo real, tornando necessário considerar as advertências que afectam a sua aplicabilidade.

A eficácia da lei de Gustafson também pode depender da natureza da própria aplicação. Embora alguns aplicativos se prestem naturalmente à escalabilidade linear com uma contagem crescente de núcleos, outros podem estagnar muito mais cedo devido a restrições inerentes ou à natureza do problema. As complexidades de programação e o potencial para rendimentos decrescentes devem ser considerados ao considerar a viabilidade da escalabilidade linear em aplicações práticas.

Em essência, embora ofereça uma visão mais otimista da paralelização, a lei de Gustafson precisa ser aplicada com um profundo entendimento da aplicação, das restrições de hardware e dos meandros da programação paralela para se alinhar às complexidades do mundo real da computação moderna.

Dimensionamento forte versus dimensionamento fraco

Basicamente, escalabilidade refere-se à capacidade de um sistema ou aplicativo de gerenciar com eficiência o aumento das cargas de trabalho à medida que seu tamanho aumenta.

Na computação, seja hardware ou software, escalabilidade denota a capacidade de aumentar o poder computacional aumentando os recursos disponíveis.

No contexto dos clusters de computação de alto desempenho (HPC), alcançar a escalabilidade é fundamental; significa a capacidade de expandir perfeitamente a capacidade geral do sistema integrando componentes de hardware adicionais. Em relação ao software, escalabilidade é muitas vezes sinônimo de eficiência de paralelização , representando a relação entre a aceleração real realizada e a aceleração ideal alcançável ao empregar um número específico de processadores. Essa métrica oferece insights sobre a eficácia com que o software pode aproveitar o processamento paralelo para melhorar o desempenho.

Testes de escalonamento

No processo típico de desenvolvimento de aplicativos grandes, muitas vezes é impraticável começar os testes com o tamanho total do problema e a contagem máxima de processadores desde o início. Esta abordagem implica tempos de espera prolongados e uma utilização excessiva de recursos. Portanto, uma estratégia mais pragmática envolve inicialmente a redução destes factores, o que acelera a fase de testes e permite uma estimativa mais precisa dos recursos necessários para a eventual execução em grande escala, auxiliando no planeamento de recursos.

O teste de escalabilidade serve como um meio para avaliar quão bem um aplicativo pode se adaptar a diferentes tamanhos de problemas e contagens variadas de processadores, garantindo desempenho ideal.

É importante observar que os testes de escalabilidade não examinam a funcionalidade geral ou a correção do aplicativo; seu foco principal está no desempenho e na eficiência à medida que os recursos computacionais são ajustados.

Dois testes de escala padrão, forte e fraco , são amplamente empregados na computação paralela.

Escala forte

O escalonamento forte envolve aumentar o número de processadores enquanto mantém o tamanho do problema constante. Essa abordagem reduz a carga de trabalho por processador, o que é particularmente valioso para aplicativos de longa duração com uso intensivo de CPU. O objetivo principal do dimensionamento forte é identificar uma configuração que ofereça tempos de execução razoáveis e, ao mesmo tempo, mantenha os custos dos recursos dentro de uma faixa gerenciável.

O escalonamento forte está ancorado na lei de Amdahl, com o tamanho do problema permanecendo fixo enquanto o número de elementos de processamento é aumentado. Esta metodologia é frequentemente justificada para programas com cargas de trabalho substanciais vinculadas à CPU.

O objetivo final do dimensionamento forte é localizar o “ponto ideal” ideal que permite que os cálculos sejam concluídos dentro de um prazo razoável, ao mesmo tempo que minimiza o desperdício de ciclos de processamento devido à sobrecarga paralela.

No dimensionamento forte, considera-se que um programa é dimensionado linearmente se a aceleração, em termos de unidades de trabalho concluídas por unidade de tempo, estiver alinhada com o número de elementos de processamento empregados (N). Da mesma forma, a aceleração pode ser sublinear ou até superlinear, dependendo de como ela é dimensionada com o número de processadores.

Por fim, tentei realizar testes de dimensionamento forte em um dos meus códigos. Fluidchen-EM é um solucionador de dinâmica de fluidos computacional capaz de resolver muitos problemas de dinâmica de fluidos. Os resultados a seguir correspondem à simulação da cavidade acionada pela tampa . A velocidade no timestamp final (após a convergência) é visualizada e o tempo de execução é calculado. Fluidchen-EM usa MPI para distribuir o domínio computacional em processadores iproc*jproc .

Nota : Os resultados foram executados no meu computador pessoal e todos os núcleos correspondem a apenas um processador. Os resultados podem variar se a simulação for executada em uma máquina maior e melhor!

O domínio computacional é dividido em um total de pontos da grade imax*jmax .
iproc: Número de processadores na direção x
jproc: Número de processadores na direção y

Conforme mostrado na figura, o tempo de execução diminui drasticamente à medida que o número de processadores dobra de 1 para 2. No entanto, a aceleração não é tão dramática para a próxima duplicação de processadores de 2 para 4, e até começa a saturar para novos aumentos. no número de processadores. Porém, os resultados foram compilados em um processador com oito núcleos, portanto esses resultados podem mudar se a execução for feita em uma máquina maior e mais potente.

Escala fraca

No escalonamento fraco, o número de processadores e o tamanho do problema aumentam, mantendo uma carga de trabalho constante por processador. A escalabilidade fraca está alinhada com a lei de Gustafson, onde a aceleração escalonada é calculada com base na carga de trabalho de um tamanho de problema escalonado, em oposição à lei de Amdahl, que se concentra em um tamanho de problema fixo.

O tamanho do problema alocado para cada elemento de processamento permanece constante, permitindo que elementos adicionais resolvam coletivamente um problema geral maior, que pode exceder a capacidade de memória de um único nó.

O escalonamento fraco justifica aplicativos com requisitos substanciais de memória ou recursos (limitados à memória) que necessitam de mais memória do que um único nó pode fornecer. Esses aplicativos geralmente apresentam escalonamento eficiente, pois suas estratégias de acesso à memória priorizam nós próximos, tornando-os adequados para contagens de núcleos mais altas.

No caso de escalonamento fraco, a escalabilidade linear é alcançada quando o tempo de execução permanece constante à medida que a carga de trabalho aumenta em proporção direta ao número de processadores.

A maioria dos programas que adotam este modo exibem uma escala favorável para contagens de núcleos mais altas, particularmente aqueles que empregam padrões de comunicação do vizinho mais próximo, uma vez que a sua sobrecarga de comunicação permanece relativamente consistente, independentemente do número de processos utilizados. As exceções a esta tendência incluem algoritmos fortemente dependentes de padrões de comunicação globais.

Por fim, realizei os testes de escalonamento fraco usando Fluidchen-EM . Os resultados a seguir correspondem à simulação da convecção de Rayleigh-Bénard . Novamente, a velocidade no carimbo de data/hora final (após a convergência) é visualizada e o tempo de execução é calculado. Fluidchen-EM usa MPI para distribuir o domínio computacional em processadores iproc*jproc .

Nota: Os resultados foram executados no meu computador pessoal e todos os núcleos correspondem a apenas um processador. Os resultados podem variar se a simulação for executada em uma máquina maior e melhor!

O domínio computacional é dividido em um total de pontos da grade imax*jmax .
iproc: Número de processadores na direção x
jproc: Número de processadores na direção y
imax: Número de pontos da grade ao longo do comprimento do canal
jmax: Número de pontos da grade ao longo da altura do canal
xlength: comprimento do canal
ylength: altura do canal

Conforme ilustrado na figura acima, o tempo de execução apresenta um aumento com o crescimento do tamanho do problema e do número de processadores. Esse comportamento pode ser atribuído a vários fatores. Com todos os núcleos residindo em um único processador, à medida que o tamanho do problema aumenta e mais processadores são envolvidos, uma parte do tempo de processamento é consumida na configuração da comunicação MPI (Message Passing Interface). Além disso, o tamanho maior do problema exige maior troca de dados entre os núcleos, amplificando a latência de comunicação devido à largura de banda finita da rede de comunicação.

Assim, os resultados desses testes fornecem insights cruciais sobre a paralelização do problema.

Conclusão

A seleção entre a Lei de Gustafson e a Lei de Amdahl na paralelização de algoritmos depende da adaptabilidade da carga de trabalho computacional. A Lei de Gustafson é adequada quando um algoritmo pode ajustar dinamicamente a quantidade de computação para corresponder à paralelização disponível. Em contraste, a Lei de Amdahl é mais adequada quando a carga de computação é fixa e não pode ser alterada significativamente pela paralelização. Em cenários do mundo real, a adaptação de um algoritmo para paralelização geralmente envolve algum grau de modificação computacional, e ambas as leis servem como referências valiosas, oferecendo limites superiores e inferiores para a aceleração prevista. A escolha entre eles depende da extensão das alterações computacionais introduzidas durante a paralelização, permitindo uma avaliação abrangente dos potenciais ganhos de aceleração.