Computação Paralela

3 Suponha que você queira calcular a distância euclidiana entre 2 pontos p e q sendo que cada ponto tem 4 coordenadas x y z t Considere que a distância euclidiana é calculada pela raiz quadrada da soma dos quadrados das diferenças entre as coordenadas dos pontos envolvidos a 15 Construa uma versão sequencial desse algoritmo utilizando alguma das linguagens de programação CC b 20 Suponha uma versão sequencial desse algoritmo com 4 CPUs interconectados com uma topologia em anel cada ponto dessa topologia é uma CPU e consuma para cada 1 subtração e 1 ul para a subtraçãopotenciação seja feita em uma CPU e a operação de soma entre os elements resultantes da CPU 0 e 1 é realizada na CPU 2 e 3 sejam feitos respectivamente nas CPUs 1 e 2 UI cada uma destas operações por fim a soma final é realizada na CPU 1 seguida da raiz também na CPU 1 cada unidade de tempo em 1 ut genérico ele gasta e apresente o speedup da o desta solução paralela seu algoritmo sequencial apresentado calcule quanto tempo consimiu em 1 ut genérico ele gasta e apresente o speedup da 4 10 Amdahl considera em sua definição que o speedup é dado pela razão entre o tempo de execução e o throughput processador e tempo de execução com multi processadores Gustafson adota outra abordagem mostrando que speedups maiores do que os previstos por Amdahl podem ser conseguidos aumentandose o tamanho do problema Assinale a alternativa correta com relação a diferenciação das duas abordagens a Com o aumento do problema abordagem proposta por Gustafson assumese que o tempo de obtenção dos resultados é aceitável e que a questão não é diminuir este tempo mas aumentar o volume de dados processados para o mesmo tempo b A proporção de speedup que a abordagem de Gustafson propõe é exponencialmente maior em relação à abordagem de Amdahl já que aquele considera o aumento do problema c O speedup de Gustafson também chamado de Speedup escalado dá um valor de aproximadamente 10 para um parte sequencial de 5 d Na abordagem de Gustafson a parte sequencial do problema deve ser mantida constante em termos proporcionais ao tamanho do problema ou seja se um problema tem 10 de parte sequencial ele deve ter esta mesma proposição para 1 ou 100 processadores e A parte parallelizável deve ser sempre pequena para que se possa obter um Speedup linear Gustafson não se preocupa com a parte parallelizável focando apenas na parte serial Boa Prov 1 Um outro algoritmo clássico de ordenação em computação é o MergeSort Ele é apresentado a seguir de forma simples a 15 Discuta consistentemente o projeto de um algoritmo MergeSort paralelo Ele é apresentado a seguir de forma simples desenhos que facilitem sua explicação Lembrese de que essa explicação considera o processo de decomposição e granularização conforme visto em sala de aula b 20 Apresente uma versão paralela desse algoritmo podese utilizar uma notação 3 li OpenMP conforme a sua descrição anterior void mergeSortint arr int l int r if l r int m lrl2 mergeSortarr l m mergeSortarr m1 r mergearr l m r 30 27 43 3 9 38 21 82 10 30 27 43 3 1 9 82 10 30 27 43 3 9 10 82 30 27 43 3 9 82 10 38 21 43 3 9 82 10 27 38 43 3 9 82 10 30 27 43 3 1 9 82 10 1 0 2 20 Um algoritmo clássico em computação é o cálculo de um número de Fibonacci Esse algoritmo pode ser visto a seguir int fibint n if n 1 return 1 else if n 2 return 1 else return fibn 1 fibn 2 Discuta sucintamente se há ou não uma solução viável paralela para esse algoritmo apresentando seu raciocínio Resolucao da Questao 4 Analise de Algoritmos Questao 4 Enunciado resumido A questao apresenta os conceitos de Speedup segundo Amdahl e Gustafson e pede uma analise crıtica sobre essas definicoes alem de uma escolha da alternativa correta com base em uma analise teorica fundamentada Speedup de Amdahl Define que o ganho de desempenho ao usar multiplos pro cessadores e limitado pela fracao de tempo do programa que nao pode ser paralelizada A formula e SAmdahl 1 1 P P N Onde P fracao paralelizavel do programa N numero de processadores Implicacao Mesmo com N o speedup e limitado por 1 P Por exemplo se apenas 90 do programa e paralelizavel o maximo speedup possıvel e 1 01 10 independentemente de quantos processadores forem usados Speedup de Gustafson Parte do princıpio inverso em vez de manter o problema fixo aumentase o tamanho do problema a medida que se usam mais processadores A formula e SGustafson N 1 P N 1 Implicacao Para grandes valores de N se P for alto o speedup tende a crescer linearmente com N Comparacao Crıtica Amdahl foca no problema fixo o que e realista para alguns cenarios ex tempo real cargas fixas Gustafson e mais aplicavel a contextos onde o problema cresce com os recursos ex simulacoes cientıficas IA Big Data Letra correta a A letra a diz Com o aumento do numero de processadores a abordagem de Gustafson propoe o aumento do volume em relacao ao problema resultando em speedups maiores que os propostos por Amdahl 1 Esta afirmativa esta perfeitamente alinhada ao que foi exposto na teoria de Gustafson As demais alternativas apresentam erros conceituais exageros ou interpretacoes incorretas da relacao entre speedup volume de problema e numero de processadores Conclusao A abordagem de Gustafson e mais otimista e realista em muitos cenarios modernos justificando a escolha da alternativa a como correta 2 Resolução da Questão 3 Análise de Algoritmos Questão 3 Cálculo da Distância Euclidiana e Speedup a Versão sequencial do algoritmo A distância euclidiana entre dois pontos p p1 p2 p3 p4 e q q1 q2 q3 q4 é calculada por dp q q1 p1² q2 p2² q3 p3² q4 p4² Segue uma possível implementação sequencial em linguagem C double distanciadouble p double q double soma 0 for int i 0 i 4 i soma qi pi qi pi return sqrtsoma Neste código temos 4 subtrações 4 multiplicações elevações ao quadrado 3 somas internas 1 raiz quadrada b Versão paralela com 4 CPUs Assumese que Cada CPU pode realizar 1 subtração e 1 potência ao quadrado em 1 unidade de tempo por operação As somas devem ser feitas de forma sequencial A raiz quadrada pode ser feita no final considerase 1 unidade de tempo para ela também Execução paralela As 4 subtrações e potências podem ser feitas em 1 unidade de tempo paralelamente nas 4 CPUs As somas ha 4 termos A soma pode ser feita como a1 a2 a3 a4 2somasemparalelo depoismais1somafinal Total de somas 2 unidades de tempo Raiz quadrada 1 unidade de tempo Tempo total da versao paralela Tp 1 subtracaopotˆencia 2 somas 1 raiz 4 unidades Tempo da versao sequencial 4 subtracoes 4 4 potˆencias 4 3 somas 3 1 raiz 1 Total Ts 4 4 3 1 12 unidades Calculo do Speedup S Ts Tp 12 4 3 Conclusao A paralelizacao permitiu reduzir o tempo total de execucao de 12 para 4 unidades resul tando em um speedup de 3 Isso mostra que mesmo com 4 CPUs o speedup nao e 4 devido a natureza sequencial das somas e da raiz quadrada A eficiˆencia e E S p 3 4 075 Ou seja a utilizacao dos processadores foi de 75 2 Analise de Algoritmo MergeSort Paralelo Questao 2 Fibonacci e Paralelismo O algoritmo abaixo apresenta uma forma recursiva classica para o calculo do nesimo numero de Fibonacci 1 int fibint n 2 if n 1 return 1 3 else if n 2 return 1 4 else return fibn 1 fibn 2 5 Este algoritmo tem uma complexidade exponencial O2n pois a cada chamada sao feitas duas outras chamadas recursivas Isso gera uma grande quantidade de chamadas redundantes Por exemplo para calcular fib5 o fib3 sera calculado multiplas vezes Paralelizacao do Algoritmo A estrutura recursiva natural do algoritmo tornao teoricamente paralelizavel ja que as chamadas fibn 1 e fibn 2 sao independentes Um esboco usando OpenMP poderia ser 1 int fibint n 2 if n 2 return 1 3 4 int x y 5 pragma omp parallel sections 6 7 pragma omp section 8 x fibn 1 9 10 pragma omp section 11 y fibn 2 12 13 return x y 14 Discussao sobre Viabilidade Apesar de ser possıvel paralelizar esse algoritmo na pratica ele nao e eficiente para valores grandes de n pelas seguintes razoes 1 Excesso de Threads O numero de chamadas cresce exponencialmente criando muitas threads que competem por recursos o que gera overhead Chamadas Repetidas A recursao faz os mesmos calculos varias vezes A solucao ideal seria usar programacao dinˆamica com memoizacao armazenar resultados ja computados Granularidade O paralelismo fino demais pode gerar mais custo de gerenciamento de threads do que ganho em performance Conclusao Existe uma solucao paralela viavel em termos de estrutura mas ela nao e efici ente em termos praticos Uma abordagem mais eficaz seria implementar a sequˆencia de Fibonacci de forma iterativa ou usando programacao dinˆamica com paralelismo apenas nos calculos principais por exemplo soma de blocos em vetores ou com uma versao paralela topdown com memoizacao compartilhada 2 Analise de Algoritmo MergeSort Paralelo Questao 1 MergeSort Paralelo a Discussao sobre a decomposicao e granularizacao do MergeSort paralelo O algoritmo MergeSort e baseado no paradigma de Divisao e Conquista A ideia central e dividir o vetor em duas partes ordenar cada uma de forma recursiva e em seguida intercalalas merge para obter o resultado final ordenado Para paralelizar esse processo a principal estrategia e executar as chama das recursivas em paralelo de modo que cada metade do vetor seja proces sada simultaneamente Esse tipo de paralelizacao ocorre naturalmente em arquiteturas com multiplos nucleos Granularizacao referese ao tamanho das tarefas que sao paralelizadas Em granularizacao fina pequenas tarefas sao distribuıdas em paralelo o que pode levar a alto overhead Em granularizacao grossa apenas grandes tarefas sao paralelizadas o que pode subutilizar os nucleos Um equilıbrio entre essas abordagens e essencial 382743398210 382743 38 2743 27 43 398210 39 3 9 8210 82 10 1 Esse diagrama mostra claramente como o vetor original e decomposto em chamadas recursivas paralelizaveis b Versao paralela com OpenMP Abaixo esta o codigo com paralelismo utilizando diretivas OpenMP Note que limitamos a paralelizacao recursiva com base em um nıvel mınimo de granu laridade para evitar overhead desnecessario void mergesortint arr int l int r if l r int m l r l 2 pragma omp parallel sections pragma omp section mergesortarr l m pragma omp section mergesortarr m 1 r mergearr l m r Explicacao Utilizamos pragma omp parallel sections para criar secoes de execucao paralela Cada metade da divisao recursiva ocorre em paralelo A funcao merge permanece sequencial pois geralmente e rapida e linear mas tambem pode ser paralelizada em versoes mais sofisticadas Observacao E importante controlar a profundidade da recursao para lela para nao criar threads demais o que geraria sobrecarga 2