Lei de Amdahl

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Fórmula em arquitetura de computador

A aceleração teórica da latência (através da redução da latência, ou seja: latência como métrica é tempo decorrido entre uma entrada e saída em um sistema) da execução de um programa como uma função do número de processadores executá-lo, de acordo com a lei de Amdahl. A aceleração é limitada pela parte serial do programa. Por exemplo, se 95% do programa puder ser paralelo, a velocidade máxima teórica usando computação paralela seria 20 vezes.

Na arquitetura de computadores, a lei de Amdahl (ou argumento de Amdahl) é uma fórmula que fornece a aceleração teórica na latência da execução de uma tarefa com carga de trabalho fixa que pode ser esperada de um sistema cujos recursos são aprimorados. Ele afirma que "a melhoria geral de desempenho obtida pela otimização de uma única parte de um sistema é limitada pela fração de tempo em que a parte aprimorada é realmente usada". É nomeado após o cientista da computação Gene Amdahl, e foi apresentado na Federação Americana de Sociedades de Processamento de Informação (AFIPS) Spring Joint Computer Conference em 1967.

A lei de Amdahl é frequentemente usada em computação paralela para prever a aceleração teórica ao usar múltiplos processadores. Por exemplo, se um programa precisa de 20 horas para completar usando um único segmento, mas uma porção de uma hora do programa não pode ser paralelizada, portanto, apenas as 19 horas restantes" (p = 0,95) o tempo de execução pode ser paralelo, em seguida, independentemente de quantos fios são dedicados a uma execução paralela deste programa, o tempo de execução mínimo não pode ser inferior a uma hora. Assim, a aceleração teórica é limitada a, no máximo, 20 vezes o único desempenho de rosca, ${displaystyle left({dfrac {1}{1-p}}=20right)}$ .

Definição

A lei de Amdahl pode ser formulada da seguinte maneira:

{displaystyle S_{text{latency}}(s)={frac {1}{(1-p)+{frac {p}{s}}}}}

onde

S_latência é a aceleração teórica da execução de toda a tarefa;
S é a aceleração da parte da tarefa que beneficia dos recursos do sistema melhorados;
p é a proporção de tempo de execução que a parte que beneficia de recursos melhorados originalmente ocupados.

Além disso,

{displaystyle {begin{cases}S_{text{latency}}(s)leq {dfrac {1}{1-p}}\[8pt]lim limits _{sto infty }S_{text{latency}}(s)={dfrac {1}{1-p}}.end{cases}}}

mostra que a aceleração teórica da execução de toda a tarefa aumenta com a melhoria dos recursos do sistema e que independente da magnitude da melhoria, a aceleração teórica é sempre limitada pela parte da tarefa que não pode se beneficiar da melhora.

A lei de Amdahl se aplica apenas aos casos em que o tamanho do problema é fixo. Na prática, à medida que mais recursos de computação se tornam disponíveis, eles tendem a ser usados em problemas maiores (maiores conjuntos de dados), e o tempo gasto na parte paralelizável geralmente cresce muito mais rápido do que o trabalho inerentemente serial. Neste caso, a lei de Gustafson dá uma avaliação menos pessimista e mais realista do desempenho paralelo.

Derivação

Uma tarefa executada por um sistema cujos recursos são melhorados em comparação com um sistema similar inicial pode ser dividida em duas partes:

uma parte que não beneficia da melhoria dos recursos do sistema;
uma parte que beneficia da melhoria dos recursos do sistema.

Um exemplo é um programa de computador que processa arquivos. Uma parte desse programa pode varrer o diretório do disco e criar uma lista de arquivos internamente na memória. Depois disso, outra parte do programa passa cada arquivo para um thread separado para processamento. A parte que verifica o diretório e cria a lista de arquivos não pode ser acelerada em um computador paralelo, mas a parte que processa os arquivos pode.

O tempo de execução de toda a tarefa antes da melhoria dos recursos do sistema é denotado como $T$ . Inclui o tempo de execução da parte que não se beneficiaria da melhoria dos recursos e do tempo de execução do que beneficiaria dele. A fração do tempo de execução da tarefa que beneficiaria da melhoria dos recursos é denotada por $p$ . A parte que não lhe beneficiaria é, portanto, ${displaystyle 1-p}$ . Então:

T=(1-p)T+pT.

É a execução da parte que beneficia da melhoria dos recursos acelerados pelo fator $s$ após a melhoria dos recursos. Consequentemente, o tempo de execução da parte que não se beneficia dele permanece o mesmo, enquanto a parte que beneficia dela se torna:

{frac {p}{s}}T.

O tempo de execução teórica ${displaystyle T(s)}$ de toda a tarefa após a melhoria dos recursos é então:

{displaystyle T(s)=(1-p)T+{frac {p}{s}}T.}

A lei de Amdahl dá a aceleração teórica na latência da execução de toda a tarefa em carga de trabalho fixa $W$ , que produz

{displaystyle S_{text{latency}}(s)={frac {TW}{T(s)W}}={frac {T}{T(s)}}={frac {1}{1-p+{frac {p}{s}}}}.}

Programas paralelos

Se 30% do tempo de execução pode ser objeto de um aumento de velocidade, p será 0,3; se a melhoria tornar a parte afetada duas vezes mais rápida, s será 2. A lei de Amdahl afirma que a aceleração geral da aplicação da melhoria será:

{displaystyle S_{text{latency}}={frac {1}{1-p+{frac {p}{s}}}}={frac {1}{1-0.3+{frac {0.3}{2}}}}=1.18.}

Por exemplo, suponha que recebemos uma tarefa serial que é dividida em quatro partes consecutivas, cujas porcentagens de tempo de execução são p1 = 0,11, p2 = 0,18, p3 = 0,23, e p4 = 0,48 respectivamente. Então nos dizem que a 1ª parte não é acelerada, então s1 = 1, enquanto a 2ª parte é acelerada 5 vezes, então s2 = 5, a 3ª parte é acelerada 20 vezes, então s3 = 20, e a 4ª parte é acelerada 1,6 vezes, então s4 = 1,6. Usando a lei de Amdahl, o aumento geral de velocidade é

S_{text{latency}}={frac {1}{{frac {p1}{s1}}+{frac {p2}{s2}}+{frac {p3}{s3}}+{frac {p4}{s4}}}}={frac {1}{{frac {0.11}{1}}+{frac {0.18}{5}}+{frac {0.23}{20}}+{frac {0.48}{1.6}}}}=2.19.

Observe como o aumento de velocidade de 5 e 20 vezes na 2ª e na 3ª partes, respectivamente, não tem muito efeito na aceleração geral quando a 4ª parte (48% do tempo de execução) é acelerada apenas 1,6 vezes.

Programas seriais

Assuma que uma tarefa tem duas partes independentes, A e B. Parte B leva cerca de 25% do tempo de toda a computação. Ao trabalhar muito duro, pode-se ser capaz de fazer esta parte 5 vezes mais rápido, mas isso reduz o tempo de toda a computação apenas ligeiramente. Em contraste, pode-se precisar executar menos trabalho para fazer parte A executar duas vezes mais rápido. Isso tornará a computação muito mais rápida do que otimizando a parte B, embora parte B 's speedup é maior em termos da relação, (5 vezes versus 2 vezes).

Por exemplo, com um programa serial em duas partes A e B para as quais T_A = 3 s e T_B = 1 s,

se parte B é feito para correr 5 vezes mais rápido, que é S = 5 e p = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = T_BNão.T_A + T_B) = 0,25, então ${displaystyle S_{text{latency}}={frac {1}{1-0.25+{frac {0.25}{5}}}}=1.25;}$
se parte A é feito para correr 2 vezes mais rápido, isto é S = 2 e p = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = T_ANão.T_A + T_B) = 0,75, então ${displaystyle S_{text{latency}}={frac {1}{1-0.75+{frac {0.75}{2}}}}=1.60.}$

Portanto, fazer a parte A rodar 2 vezes mais rápido é melhor do que fazer a parte B rodar 5 vezes mais rápido. A melhoria percentual na velocidade pode ser calculada como

{displaystyle {text{percentage improvement}}=100left(1-{frac {1}{S_{text{latency}}}}right).}

Melhorar parte A por um fator de 2 aumentará a velocidade geral do programa por um fator de 1,60, o que o torna 37,5% mais rápido do que a computação original.
No entanto, melhorar a parte B por um fator de 5, que presumivelmente requer mais esforço, alcançará um fator de aceleração geral de 1,25 apenas, o que o torna 20% mais rápido.

Otimizando a parte sequencial de programas paralelos

Se a parte não paralelizável é otimizada por um fator de $O$ , então

{displaystyle T(O,s)=(1-p){frac {T}{O}}+{frac {p}{s}}T.}

Resulta da lei de Amdahl que o aumento de velocidade devido ao paralelismo é dado por

{displaystyle S_{text{latency}}(O,s)={frac {T(O)}{T(O,s)}}={frac {(1-p){frac {1}{O}}+{p}}{{frac {1-p}{O}}+{frac {p}{s}}}}.}

Quando $s=1$ nós temos ${displaystyle S_{text{latency}}(O,s)=1}$ , significando que a aceleração é medido com respeito ao tempo de execução após a parte não paralelizável é otimizada.

Quando $s=infty$ ,

{displaystyle S_{text{latency}}(O,infty)={frac {T(O)}{T(O,s)}}={frac {(1-p){frac {1}{O}}+{p}}{{frac {1-p}{O}}+{frac {p}{s}}}}=1+{frac {p}{1-p}}O.}

Se ${displaystyle 1-p=0.4}$ , ${displaystyle O=2}$ e $s=5$ Então...

{displaystyle S_{text{latency}}(O,s)={frac {T(O)}{T(O,s)}}={frac {{0.4}{frac {1}{2}}+0.6}{{frac {0.4}{2}}+{frac {0.6}{5}}}}=2.5.}

Transformando partes sequenciais de programas paralelos em paralelizáveis

Em seguida, consideramos o caso em que a parte não paralelizável é reduzida por um fator de ${displaystyle O'}$ , e a parte paralelizável é correspondentemente aumentada. Então...

{displaystyle T'(O',s)={frac {1-p}{O'}}T+left(1-{frac {1-p}{O'}}right){frac {T}{s}}.}

Resulta da lei de Amdahl que o aumento de velocidade devido ao paralelismo é dado por

{displaystyle S'_{text{latency}}(O',s)={frac {T'(O')}{T'(O',s)}}={frac {1}{{frac {1-p}{O'}}+left(1-{frac {1-p}{O'}}right){frac {1}{s}}}}.}

A derivação acima está de acordo com a análise de Jakob Jenkov do tempo de execução versus compensação de aceleração.

Relação com a lei dos rendimentos decrescentes

A lei de Amdahl é muitas vezes confundida com a lei dos rendimentos decrescentes, enquanto apenas um caso especial de aplicação da lei de Amdahl demonstra a lei dos rendimentos decrescentes. Se alguém escolher otimamente (em termos de aumento de velocidade alcançado) o que deve ser melhorado, verá melhorias monotonicamente decrescentes à medida que melhora. Se, no entanto, alguém escolher de maneira não otimizada, depois de melhorar um componente subótimo e passar para melhorar um componente mais ideal, pode-se ver um aumento no retorno. Observe que muitas vezes é racional melhorar um sistema em uma ordem que seja "não ideal" neste sentido, visto que algumas melhorias são mais difíceis ou requerem maior tempo de desenvolvimento do que outras.

A lei de Amdahl representa a lei dos rendimentos decrescentes se considerarmos que tipo de retorno obtemos adicionando mais processadores a uma máquina, se estivermos executando uma computação de tamanho fixo que usará todos os processadores disponíveis para sua capacidade. Cada novo processador adicionado ao sistema adicionará menos energia utilizável do que o anterior. Cada vez que se dobra o número de processadores, a taxa de aceleração diminui, pois a taxa de transferência total se aproxima do limite de 1/(1 − p).

Essa análise negligencia outros gargalos potenciais, como largura de banda de memória e largura de banda de E/S. Se esses recursos não forem dimensionados com o número de processadores, a simples adição de processadores fornecerá retornos ainda mais baixos.

Uma implicação da lei de Amdahl é que, para acelerar aplicativos reais que possuem partes seriais e paralelas, são necessárias técnicas de computação heterogêneas. Existem novos modelos de aceleração e consumo de energia baseados em uma representação mais geral da heterogeneidade, conhecida como heterogeneidade da forma normal, que suporta uma ampla gama de arquiteturas heterogêneas de muitos núcleos. Esses métodos de modelagem visam prever a eficiência de energia do sistema e as faixas de desempenho e facilitam a pesquisa e o desenvolvimento nos níveis de hardware e software do sistema.

Contenido relacionado

Más resultados...