Lei de Amdahl e Paralelização de Algoritmos - Avaliação com Questões Resolvidas

Avaliação Integrada Questão 01 O conceito de aceleração é usado como uma medida para indicar até que ponto um programa sequencial pode ser paralelizado A aceleração pode ser considerada como uma espécie de grau de paralelismo inerente a um programa A esse respeito Amdahl criou uma lei conhecida como Lei de Amdahl que afirma que a aceleração potencial do programa é definida pela fração de código P que pode ser paralelizada Aceleração 11P Se nenhuma parte do código puder ser paralelizada P 0 e o aumento de velocidade é 1 ou seja é um programa inerentemente sequencial Se todo o código for paralelizado P 1 o aumento de velocidade é infinito Mas praticamente o código em nenhum programa pode ser 100 paralelo e portanto a velocidade nunca pode ser infinita Se 50 do código puder ser paralelizado o aumento de velocidade é 2 significando que o código será executado duas vezes mais rápido Se introduzirmos o número de processadores em execução a relação pode ser modelada por Aceleração 1PNS Onde P fração paralela N número de processadores e S fração serial Em um determinado algoritmo foi detectado que ele poderia ser paralelizado em 70 do seu código Mais tarde esse algoritmo foi implementado em um computador de 10 processadores Qual foi o valor da aceleração Questão 02 O fator de aceleração depende da fração a ser paralelizada e do número de processadores Para um algoritmo com 50 de paralelização temos a seguinte tabela de aceleração levando em conta o número de processadores Processadores Aceleração 1 1 2 133 4 16 8 177 16 188 Veja na tabela acima que simplesmente dobrar o número de processadores não garante uma boa aceleração no final Explique porque isso ocorre e qual a estratégia para mitigar o problema Questão 1 𝐴𝑐𝑒𝑙𝑒𝑟𝑎çã𝑜 1 𝑃 𝑁 𝑆 1 07 10 03 1 00703 1 037 2 7027 Questão 2 Inicialmente devemos considerar o tempo necessário para paralelizar ou seja o tempo de execução necessário para criar threads e dividir o trabalho Além disso o fator que tem maior impacto nisto é o acesso a regiões críticas tais como acesso a um mesmo recurso como memória ou ES Para mitigar isto devese buscar estratégias para evitar regiões críticas Uma das estratégias é que em alguns problemas basta criar várias cópias de um mesmo recurso de forma que cada execução paralela consiga acessar a sua cópia do recurso sem ser necessário a criação de regiões críticas Questão 1 Aceleração 1 P N S 1 07 10 03 1 00703 1 037 27027 Questão 2 Inicialmente devemos considerar o tempo necessário para paralelizar ou seja o tempo de execução necessário para criar threads e dividir o trabalho Além disso o fator que tem maior impacto nisto é o acesso a regiões críticas tais como acesso a um mesmo recurso como memória ou ES Para mitigar isto devese buscar estratégias para evitar regiões críticas Uma das estratégias é que em alguns problemas basta criar várias cópias de um mesmo recurso de forma que cada execução paralela consiga acessar a sua cópia do recurso sem ser necessário a criação de regiões críticas