A lei de Amhdal explicada – O motivo pelo qual Xbox série X e PS5 são mais parecidas do que se pensa.

A lei de Amdahl aplicada às actuais consolas permite perceber o motivo pelo qual elas são bastante semelhantes.

A questão dos GPUs das novas consolas está a surpreender muita gente. Como é possível que um GPU com mais 1.84 Tflops. a potência de uma PS4, seja tão rápido ou até mais lento como um de 10.28 Tflops»

Vamos imaginar uma fábrica… onde temos esteiras onde a matéria prima entra numa sequência automatizada de produção.

Ora com uma esteira que recebe o material a uma determinada cadência, um determinado volume de produção que entre na esteira (100 unidades, por exemplo) demora T segundos a ser produzido!

Poderemos então pensar… ora se eu pegar e colocar outras esteiras lado a lado com a que tenho, o tempo que demoro a calcular este mesmo volume vai ser divido pelo número de esteiras.

Ou seja, se eu colocar P esteiras, o que vou ter é esse tempo dividido por esse número, ou seja T/P.

Num exemplo, se T = 60 minutos, e se o número de esteiras P = 4, então, para o mesmo volume de produção, irei precisar de apenas 15 minutos. 60m/4=15m.

Mas se isto é assim numa fábrica, porque motivo não é assim num GPU, quando temos igualmente unidades de produção, os CU, e aumentamos a quantidade deles?

Existem 2 obstáculos a isso:

• O não paralelismo
• A sobrecarga

Ora o grande interesse do paralelismo é podermos dividir o trabalho por várias unidades de produção. O objetivo aqui passa por duas partes. O reduzir o tempo que demora a tarefa a ser feita,  e o poder efetuar mais tarefas no mesmo tempo.

Ora o Ganho é o Tempo que temos com o aumento das unidades paralelas, o P. Vamos chamar a isso o TP. Ou seja,:

Ganho =  T/TP

No exemplo de cima, o Ganho era então 60m/15 m = 4 vezes! Ou seja, a nível de tempo para produzir a mesma coisa, tínhamos um ganho de 4 vezes, pois produzíamos em 1/4 do tempo a mesma coisa.

E repare-se: Que o Ganho não é nada mais, nada menos, do que o número de unidades de produção paralelas ou seja o P.

Ganho = P = 4

Ora o que podemos igualmente ter é casos onde o Ganho é Sublinear, ou seja o Ganho é menor que P. E casos onde onde o ganho é Superlinear, ou seja o Ganho é maior que P.

Por exemplo, se P=4, mas o Ganho = 5, temos um aumento superlinear, mas se P=4 e o Ganho = 3 temos um aumento Sublinear.

Vamos agora abortar um outro conceito relevante, o rendimento:

O Rendimento é o trabalho sobre o tempo usado com o uso das unidades paralelas, que em cima chamamos de TP.

Rendimento = Trabalho/TP

Assim, imaginemos que produzíamos 100 caixas, que seria o nosso trabalho.

Com uma única unidade de produção, o rendimento seria 100/60 m = 1,66

Mas com as 4, a nossa produção faz-se em 15m, logo o rendimento será 100/15 = 6.666

Basicamente, no caso de uma fábrica, o Rendimento seria P vezes superior, ou seja, é igual ao número de unidades de produção.

E isto leva-nos a um novo conceito, o de Eficiencia.

A Eficiência ou uso efetivo das unidades de produção paralelas traduz-se na seguinte formula:

Eficiência = Ganho/P

Ora no caso anterior, como o Ganho era de 4 vezes e as unidades paralelas eram 4 (P=4), temos uma Eficiência de 4/4=1 ou seja, de 100%.

E com este conceito percebido, vamos calcar novamente naquilo que já abordei aqui mais de 100 vezes, a Lei de Amdahl, aplicada aos processadores paralelos!

A Lei de Amdahl

Antes do mais, devo referir que já estudei isto há muitos anos, e não tendo a necessidade de ter estas coisas na ponta da língua, pode-se tornar difícil explicar este conceito. Diga-se mesmo que estou a relembrar muita coisa pelo que espero que consiga passar a mensagem.

Mas a realidade é que o paralelismo na computação não é idêntico ao paralelismo numa fábrica como no exemplo de cima. E daí que Gene Amdahl tenha tido a necessidade de criar uma Lei que explica o rendimento de um sistema informático com o aumento das unidades de computação paralelas.

E que melhor exemplo de grandes quantidades de unidades de processamento paralelas do que um GPU?

O grande problema da computação, e que cria a diferença para o exemplo de cima fornecido numa fábrica, é que a computação é inerentemente sequencial. Mesmo quando temos computação paralela, há sempre processamento sequencial. E ao contrário do que acontece numa fábrica onde eu posso fabricar um produto em várias linhas sem problemas, na computação existe algo chamado as dependências, ou seja, resultados que podem estar a ser calculados na linha de produção A, mas que são depois necessários na linha de produção M para esta poder prosseguir.

E estas dependências são o que impede que a computação paralela seja equivalente à produção paralela.

A acrescentar a isto, há muito código que, pura e simplesmente, não pode, ou pelo menos não deve sob pena de as dependências criarem gargalos a todo o sistema, ser paralelizado, havendo a necessidade de ser processado sequencialmente.

E isto cria uma realidade na computação paralela que é diferente da realidade da produção paralela, um aumento da perda de eficiencia, com o aumento do número de unidades de processamento paralelas.

Assim a formula do Ganho assume uma outra forma, e passa a ser:

Ganho = 1/Percentagem de código que necessita de ser sequencial.

Assim, se precisarmos de 50% de código sequencial, o ganho será 1/0.5, ou 2x
Se o código que precisa de ser sequencial for de 10%, o Ganho será 1/0.1 ou 10x

O que, mantendo-se a formula da eficiência, permite perceber que a mesma só será 100% quando a percentagem de código sequencial for basicamente nula.

Esta situação leva-nos a tabelas deste tipo:

O gráfico basicamente representa o seguinte:

O Ganho (Speedup) pode ser representado por várias linhas, dependendo da capacidade de paralelização do código. A azul temo código que é em 50% sequencial, e 50% paralelizável, e onde o ganho máximo que podemos obter é, como já tínhamos visto na conta de cima, 2, e a verde um código basicamente bem executado e preparado para paralelismo, onde apenas 5% do código é sequencial, e onde o ganho pode ir até 20 vezes sobre a existência de um único processador.

No entanto, com o aumento do número de processadores, as dependências aumentam exponencialmente, e consequentemente, a partir de um determinado número de processadores, os ganhos tornam-se nulos.

Eis um exemplo de uma dependência, em código:

sum = a+1; /* << */
first_term = sum*scale1; /* << */
sum = sum+b;
second_term = sum*scale2;

Basicamente, a variável sum depende do valor que possuía anteriormente

Podemos ver no gráfico de cima que com 95% de paralelismo isso ocorre com algo acima dos 4096 processadores. Tendo cada CU 64 unidades de processamento, isso implica que o limite acima do qual não justifica ir é 64 CU. Exatamente o limite que sabemos existia no CGN, e acima do qual a AMD nunca foi.

Mas o que podemos ver aqui é que a diferença no ganho entre 52 CU ou 3328 Processadores e 36 CU ou 2304 processadores é super reduzida.

Outra coisa que o que estamos a ver nos mostra é que a velocidade é importante. O ganho que estamos a observar no gráfico é em número de vezes o ganho de um único processador. Se um único processador é 22% mais rápido do que outro, o ganho obtido com as consequentes perdas é, comparativamente superior.

Por outras palavras, e algo que já sabemos, um processador que obtenha a sua performance por velocidade é mais eficiente que um que obtenha a mesma performance por paralelismo.

Como vemos no gráfico de Amdahl, a velocidade não é tomada em conta, mas sendo a Eficiência =  Ganho / P, e o Ganho com 2304 processadores muito próximo do Ganho com 3328 processadores, o valor da Eficiência do processador com menos unidades paralelas é mais alto.

Ora o que sabemos é que a Sony mexeu ainda mais na sua eficiência. Os Cache Scrubbers, os motores de Coerência, e mesmo o seu Geometry Engine estão alterados para melhorarem a eficiência ao reduzir a quantidade de processamento que é feito pelo sistema na sua gestão interna. E consequentemente, se a Eficiência ainda sobe mais, sendo P um valor fixo, o Ganho aumenta.

E isso permite que a PS5 possa estar ao mesmo nível da Xbox, apesar da diferença teórica de 18% dada pelos Tflops.

Mas várias perguntas podem ser colocadas:

1 – O paralelismo máximo é 95%?

Apesar de não poder dar essa certeza, é quase uma certeza que ele não deverá ser muito superior a isso.

Situações como a computação que seja limitada pela memória, ou pelo sistema de I/O, ou mesmo maus balanceamentos de cargas de processamento que criem sobrecargas ou overheads no sistema, obrigam forçosamente a serialização, mesmo que o código fosse totalmente paralelizável. Daí que apesar de não poder afirmar com toda a certeza que 95% seja a paralelização máxima, os 100% nos sistemas catuais são apenas teoria, e os 95% são uma boa aproximação da realidade em código bem realizado.

2 – Mas então porque apostar em mais CU e não em mais velocidade?

Na realidade, desde que o código seja bem feito, ambas as situações são meras alternativas. A questão passa depois pela maior dificuldade em paralelizar o código para mais CUs evitando as dependências ao máximo. Mas acreditando-se que isso se supera ambas as alternativas são viáveis e conduzem a resultados semelhantes.

A opção da Sony não seria a melhor se não fosse pelas melhorias adicionais na eficiência interna do sistema, que permitem fechar os pouco porcento de performance extra que a Xbox possui, tornando as consolas em tudo semelhantes, apesar de chegarem lá de formas diferentes. Eventualmente código mais otimizado para um tipo de processamento ou para outro, poderá fazer a balança pender para um lado ou para o outro mas, à partida, sempre com algum equilíbrio pois no global os sistemas acabam por ser muito semelhantes a nível de performance.

3 – Mas há quem diga que a lei de Amdahl está ultrapassada! Ela continua válida?

Na realidade a Lei de Amdahl é um modelo muito simplista que ignora imensos fatores, servindo apenas como modelo de aproximação, mas não como algo preciso.

Basicamente o modelo foi criado para responder a uma questão relacionada com o paralelismo: Se tenho um trabalho a fazer, quão mais rápido o posso fazer com paralelismo?

Mas por exemplo, se eu tenho um tempo de duas horas para processar algo, e arranjo um sistema mais rápido ele no mesmo tempo pode processar algo ainda mais complexo.

Sem darem significado aos termos, chama-se ao primeiro caso uma medida de escalamento forte, e ao segundo uma medida de escalamento fraca. E este segundo caso responde a uma outra pergunta: Que quantidade de trabalho posso processar num tempo fixo.

Ora apesar de para os videojogos basicamente e historicamente apenas sempre nos interessou o escalamento forte pois o jogo é o mesmo em todos os sistemas, cada vez mais vemos o escalamento fraco a ser usado, com a performance adicional a ser usada para efeitos adicionais ou resolução.

Daí que surgiu uma perspetiva diferente. Uma que inverte o problema que Amdahl colocou, e que em vez de calcular o quanto mais rápido é um sistema com P processadores do que com um processador com uma fração F de código paralelizável, podemos ver quanto mais lento é um processador face a P processadores num problema que é P vezes maior.

 

E teremos esta formula:

	S(P)	=	T __	≤	(1-F)+FP ____	=	1+F(P-1)
			TP		(1-F)+F

Esta é o lei de Gustafson’s, e nela a parte serializada não aumenta com o problema e pode ser ignorada.

Como vimos num cálculo anterior, se a percentagem de paralelização fosse de 90%, o ganho máximo do sistema seria de 10x, mesmo que subíssemos os processadores para além do necessário. Mas se a percentagem serializada não escalar com o tamanho do problema, 100 processadores poderiam aumentar o problema a resolver em 1000 vezes e escalar o mesmo num fator de 900.

Esta situação demonstrou uma fraqueza na lei de Amdahl, que na realidade não é uma fraqueza. Basicamente o que acontece é que esta inversão do problema mostra que os ganhos não são exatamente aquilo que a lei de Amhdal refere. E que os ganhos podem ser maiores do que os ali indicados. No entanto não altera a realidade global da lei, pelo que a mesma continua válida na teoria que representa e no limite imposto pelos processadores paralelos.

Outra situação onde a lei falha é que não toma em conta a paralelização dentro da paralelização. Todos sabemos que a AMD passou a usar Double CUs. Basicamente uma Navi RDNA 1 possui agora 40 CUs, mas numa estrutura de 20 Double CUs. Quer isto dizer que onde antes tínhamos um limite de 64 CUs, esse limite passa agora a ser de 64 Double CUs, ou seja 128 CUs.

Esta situação contorna o limite da lei de Amdhal, sem no entanto a quebrar. Continua a haver um limite de 4096 processadores com 95% de paralelização de código, mas cada um desses processadores são agora constituídos por dois processadores.

Numa outra falha da lei, ela parte do principio que todos os processadores em jogo são iguais, o que não necessita de ser verdade (por exemplo a PS3). Mas mais uma vez apesar de todos estes pontos serem referidos como algo que a lei não toma em conta, para o caso em causa a mesma continua válida.

É contudo uma lei que, dados os avanços na computação, deverá deixar de ser usada em breve pois não toma em conta muitas das novidades tecnológicas que apareceram e que permitem superar os seus limites. No entanto, para o caso em questão, e apesar de já estarmos a lidar com Dual Cus, a validade da mesma ainda pode ser tomada em conta para perceção da semelhança dos sistemas.