Prévia do material em texto
Visão geral da computação paralela Eduardo Ferreira dos Santos Ciência da Computação Universidade Presbiteriana Mackenzie 7 de agosto de 2021 1 / 60 Professor EDUARDO FERREIRA DOS SANTOS, MsC Mestre em Computação Aplicada pela Universidade de Brasília � UnB Áreas de pesquisa: Cluster & Grid; Processamento de Linguagem Natural; Recuperação da Informação; Modelagem de tópicos; Busca e recuperação textual; Classi�cação de documentos. Web Semântica; Bancos de dados NoSQL. 2 / 60 Sumário 1 Visão do curso 2 Introdução 3 Conceitos 4 Panorama da computação paralela 3 / 60 Visão do curso 1 Visão do curso 2 Introdução 3 Conceitos 4 Panorama da computação paralela 4 / 60 Visão do curso Plano de ensino Revisão do plano de ensino 5 / 60 Visão do curso Sobre as aulas A principal fonte de conhecimento está no livro. Se atente às referências; Aproveite as aulas para interagir com o professor e tirar dúvidas; Divisão das aulas: Segunda-feira Aula teórica Quinta-feira Aula prática O curso se divide entre teoria e prática; Para �nalizar o curso vai ter que programar. 6 / 60 Visão do curso Aulas práticas Nas aulas introdutórias de programação utilizaremos o webminal: https://www.webminal.org/ No máximo 2 aulas para revisar os conceitos básicos de programação em C; Ferramentas e compilação de programas. O restante das aulas será executada em nuvem pública: AWS ou Azure do Mackenzie; Aprendizagem sobre as principais bibliotecas de paralelismo: OpenMP, pthreads e MPI; Chance de abordarmos GPU a depender do andamento das aulas. 7 / 60 https://www.webminal.org/ Visão do curso Exercícios do curso Exercícios preparatórios para casa, voltados ao reforço da teoria e preparação para a prova; Laboratório (aula de Quinta): Exercícios com padrões de programação paralela; Programas utilizando as bibliotecas de paralelismo (OpenMP, pthreads e MPI); Talvez GPU. Projeto do curso: desenvolvimento, apresentação e relatório. 8 / 60 Visão do curso Conhecimentos a serem abordados no curso Entendimento profundo do projeto de computadores paralelos; Conhecimento de como programar sistemas de computação paralela; Entendimento da programação paralela baseada em padrões; Exposição a diferentes formas de algoritmos paralelos; Experiência prática usando um cluster paralelo; Experiência em modelagem de desempenho paralelo; Técnicas para análise empírica de desempenho. 9 / 60 Introdução 1 Visão do curso 2 Introdução 3 Conceitos 4 Panorama da computação paralela 10 / 60 Introdução Visão geral da computação paralela A computação paralela é uma área da Computação preocupada com [Malony, 2021]: Arquitetura, sistemas de hardware e software, linguagens, paradigmas de programação, algoritmos e modelos teóricos; Computação em paralelo. A principal razão para o paralelismo é a performance; HPC: High Performance Computing Principais tópicos relacionados: Arquiteturas paralelas; Programação paralela; Algoritmos paralelos; Modelos e ferramentas para performance paralela; Aplicações paralelas. 11 / 60 Introdução De�nições [Malony, 2021] Computador paralelo Sistema computacional que utiliza múltiplos componentes de processamento simultaneamente, trabalhando de maneira cooperativa para resolver um problema computacional. Processamento paralelo Técnicas e tecnologias que habilitam a computação paralela. O processamento paralelo é habilitado por diferentes camadas de tecnologia: hardware, rede, sistema operacional, bibliotecas paralelas, linguagens, compiladores, algoritmos, ferramentas... Também é considerada uma evolução da computação serial: A natureza funciona de forma paralela (é o que esperamos do computador); Os problemas variam de acordo com o nível/tipo de paralelismo. 12 / 60 Introdução Concorrência [Malony, 2021] Considere a execução de múltiplas tarefas no computador; As tarefas serão consideradas concorrentes uma à outra se: 1 Podem ser executadas ao mesmo tempo (execução concorrente); 2 Não existe dependência entre as tarefas. Dependência: Se uma tarefa precisa de resultados que serão fornecidos por outras para ser executada existe uma dependência; Se duas tarefas são dependentes elas não são concorrentes; Alguma forma de sincronia pode ser utilizada para reforçar (satisfazer) dependências. A concorrência é fundamental para a Ciência da Computação. 13 / 60 Introdução Concorrência e paralelismo Concorrência não é o mesmo que paralelismo; Execução paralela: Tarefas concorrentes são executadas de fato ao mesmo tempo; Múltiplos recursos de processamento (processadores) precisam estar disponíveis. Paralelismo = concorrência + hardware paralelo (ambos são obrigatórios) 1 Encontre oportunidades de execução concorrente; 2 Desenvolva a aplicação para ser executada em paralelo; 3 Execute a aplicação em hardware paralelo. Uma aplicação paralela é uma aplicação concorrente? Uma aplicação que roda somente em um processador é paralela? 14 / 60 Introdução Paralelismo Existem diferentes granularidades de paralelismo (execução paralela) em programas: Processos, threads, rotinas, declarações, instruções... Quais são os elementos de software que podem ser executados concorrentemente? O paralelismo deve ser suportado por recursos de hardware: Processadores, núcleos, ... (execução de instruções) Memória, DMA, redes, ... (ou outras operações associadas) Todos os aspectos da arquitetura de computadores oferecem oportunidades para execução em hardware paralelo. Concorrência é uma condição necessária para o paralelismo: Onde é possível encontrar concorrência? Como a concorrência é utilizada para explorar os sistemas paralelos? 15 / 60 Introdução Vantagens do processamento paralelo Tempo mais rápido para resolver um problema (tempo de resposta); Resolver problemas computacionais mais complexos (ao mesmo tempo); Outros fatores que motivam o processamento paralelo [Malony, 2021]: Uso efetivo dos recursos computacionais; E�ciência de custo; Superar restrições de memória. Máquinas seriais possuem limitações intrínsecas: velocidade do processador, memória, etc. Paralelismo é o futuro da computação; Performance ainda é a maior preocupação; Paralelismo = concorrência + hardware paralelo + performance 16 / 60 Introdução Perspectivas da computação paralela Arquitetura de computadores paralelos: Qual o hardware necessário para execução paralela? Desenho dos sistemas computacionais. Sistema operacional (paralelo): como gerenciar os aspectos do sistema em um computador paralelo? Computação paralela: Bibliotecas (baixo e alto nível); Linguagens de programação; Ambientes de desenvolvimento. Algoritmos paralelos; Avaliação de performance em paralelismo; Ferramentas de paralelismo: performance, analytics, visualização, etc. 17 / 60 Introdução Demandas de aplicações paralelas A demanda por mais ciclos de processamento é crescente e insaciável; Tendências em novos tipos de processadores; Tendências arquiteturais; Algumas outras tendências: Os microprocessadores de hoje possuem suporte a múltiplos processadores; Servidores e estações de trabalho estão disponíveis como multiprocessadores; Os microprocessadores de amanhã são os multiprocessadores de hoje; O número de processadores por núcleo continua crescendo (limites físicos); Aceleradores (GPUs, jogos). 18 / 60 Introdução Características das aplicações Desempenho do software demanda avanços no hardware; Novas aplicações têm maiores demandas de desempenho: Aumento exponencial na capacidade de desempenho do processador; Inovações na integração das arquiteturas paralelas. Faixa de requerimento de desempenho: Desempenho do sistema como um todo também tem que melhorar; Requerimentos de desempenho requerem engenharia de computação; Custos são endereçados através de avanços tecnológicos. 19 / 60 Introdução Questões (amplas) de arquiteturas paralelas Alocação de recursos: Quantos elementos de processamento? Quão poderosos são os elementos? Quanto de memória? Sincronização,comunicação e acesso a dados: Como os elementos cooperam e se comunicam? Como os dados são transmitidos entre os processadores? Quais as abstrações e primitivas para cooperação? Desempenho e estabilidade: Como tudo isso se traduz em desempenho? Como escala? 20 / 60 Conceitos 1 Visão do curso 2 Introdução 3 Conceitos 4 Panorama da computação paralela 21 / 60 Conceitos Programas de computador Listing 1: Programa de computador simples # i n c l u d e <s t d i o . h> i n t main ( i n t argc , cha r ∗∗ a rgv ) { i n t x = 1 ; 5 f o r ( i n t i =0; i <10; i++) { x = x + x ; } p r i n t f ( " % d \ n " , x ) ; r e t u r n 0 ; 10 } O que é um programa de computador? 22 / 60 Conceitos Revisão: o que é um programa? Na perspectiva do computador, o pro- grama é uma sequência de instruções [Fatahalian and Olukotun, 2020] 23 / 60 Conceitos Revisão: o que faz o processador? O processador executa programas; Executar uma instrução é mover o Program Counter � PC: Mover para a próxima instrução; Executar; Continuar a execução... 24 / 60 Conceitos Paralelismo em nível de instrução Os processadores de fato permitiam o paralelismo para que os programas executassem mais rápido, mas era, em geral, invisível ao programador [Fatahalian and Olukotun, 2020]; Paralelismo em nível de instrução (Instruction Level Paraelism) � ILP: Ideia: as instruções devem parecer estar sendo executadas em ordem; As instruções independentes podem ser executadas simultaneamente por um processador sem impactar a corretude do programa; Execução superescalar: o processador encontra instruções independentes dinamicamente a partir da sequência de entrada e executa em paralelo. 25 / 60 Conceitos Exemplo de ILP Considere o programa: a = x ∗ x + y ∗ y + z ∗ z A representação em Assembly pode ser apresentada no trecho 2. Listing 2: Exemplo de ILP // assume r0=x , r1=y , r2=z mul r0 , r0 , r0 mul r1 , r1 , r1 mul r2 , r2 , r2 5 add r0 , r0 , r1 add r3 , r0 , r2 // now r3 s t o r e s v a l u e o f program v a r i a b l e 'a ' Se o programa possui cinco instruções levará quatro ciclos de clock para executar, certo? É possível ser mais rápido? 26 / 60 Conceitos Diagrama de execução Considere ainda o programa: a = x ∗ x + y ∗ y + z ∗ z Figura 3.1: Diagrama de execução para o programa do trecho 2 27 / 60 Conceitos Execução superescalar De�nition O processador encontra automaticamente instruções independentes na pilha de execução e executa em paralelo nas múltiplas unidades de execução. No exemplo do trecho 2, as instruções das linhas 1, 2 e 3 podem ser executadas em paralelo, pois não há dependência; A instrução da linha 4 vem depois das instruções 1 e 2; A instrução da linha 5 vem depois da linha 4. // assume r0=x , r1=y , r2=z mul r0 , r0 , r0 mul r1 , r1 , r1 mul r2 , r2 , r2 5 add r0 , r0 , r1 add r3 , r0 , r2 // now r3 s t o r e s v a l u e o f program v a r i a b l e 'a ' 28 / 60 Conceitos Um exemplo mais complexo O que signi�ca para um processador superescalar respeitar a "ordem de execução"? Figura 3.2: Exemplo com grafo de dependência [Fatahalian and Olukotun, 2020] 29 / 60 Conceitos Diminuindo o retorno da execução superescalar A maior parte do ILP disponível é explorado por um processador capaz de enviar até quatro instruções por ciclo de clock; Há pouco ganho de performance ao construir um processador que pode enviar mais instruções. Figura 3.3: Capacidade de envio de instruções do processador (instruções/clock) [Fatahalian and Olukotun, 2020] 30 / 60 Panorama da computação paralela 1 Visão do curso 2 Introdução 3 Conceitos 4 Panorama da computação paralela 31 / 60 Panorama da computação paralela Contexto histórico [Fatahalian and Olukotun, 2020] Por que não computação paralela? A performance das CPUs single-thread dobra aproximadamente a cada 18 meses (Lei de Moore); Resultado: paralelizar o código não vale o esforço. Se o programador não �zer nada, o código se torna mais rápido todos os anos. 32 / 60 Panorama da computação paralela Por que processamento paralelo? Até +-15 anos atrás: obter ganhos de performance além do que as melhorias de CPU são capazes de fornecer. Figura 4.1: Breve histórico do surgimento dos supercomputadores [Fatahalian and Olukotun, 2020] 33 / 60 Panorama da computação paralela Projeto Genoma Figura 4.2: Survey de 2015 reforça a importância do paralelismo para a biologia [Ocaña and de Oliveira, 2015] Sequenciar o gene de todos os seres humanos é uma tarefa computável, mas difícil; Necessidade de tempo e recursos computacionais; O projeto genoma incentivou a área de computação paralela e consolidou uma nova área: bioinformática; Timeline do projeto genoma (clicável) 34 / 60 https://upload.wikimedia.org/wikipedia/commons/3/33/Human_Genome_Project_Timeline_%2826964377742%29.jpg Panorama da computação paralela Por que estudar computação paralela hoje? Arquitetura computacional: inovações normalmente demandam novos modelos de programação (computação quântica); Convergência tecnológica: O �super computador� está se tornando comum; Notebooks e supercomputadores são fundamentalmente similares; Tendências geram a convergência de diversas abordagens. Tendências tecnológicas tornam a computação paralela inevitável! Processadores multicore são bastante comuns; Qualquer sistema computacional moderno está operando em paralelo. Entender os princípios fundamentais e as compensações de projeto: Programação, suporte de sistemas, computação, memória... Desempenho. Paralelismo é o presente da computação (não mais o futuro). 35 / 60 Panorama da computação paralela ILP superado Figura 4.3: As frequências não escalam na mesma taxa [Fatahalian and Olukotun, 2020] 36 / 60 Panorama da computação paralela Gargalo de Von Neumann atingido O gargalo de Von Neumann tem se tornado um problema real Figura 4.4: Aumento de RAM x processamento[Fatahalian and Olukotun, 2020]37 / 60 Panorama da computação paralela Quantidade de transistors Os transistores já são quase do tamanho de uma molécula. Figura 4.5: Quantidade de transistors nos chips [Fatahalian and Olukotun, 2020] 38 / 60 Panorama da computação paralela O que tem acontecido nos últimos anos? Fabricantes de chips aumentaram o desempenho aumentando o clock da CPU; A Lei de Moore se provou consistente até certo ponto; Até que os chips �caram muito quentes! Múltiplos núcleos no processadores. 39 / 60 Panorama da computação paralela A �barreira da energia� A energia consumida por um transistor pode ser expressa da forma: Potência dinâmica ∝ carga capacitiva× voltagem2 × frequência Energia estática: o transistor consome energia mesmo quando inativo (vazamento de energia); Maior energia = maior calor (efeito Joule); Consumo de energia é uma informação crítica em processadores modernos. 40 / 60 Panorama da computação paralela Consumo de energia Figura 4.6: Alguns números sobre consumo de energia [Fatahalian and Olukotun, 2020] 41 / 60 Panorama da computação paralela Consumo de energia como função da frequência Figura 4.7: Consumo de energia para processadores i7 [Fatahalian and Olukotun, 2020] 42 / 60 Panorama da computação paralela Escalabilidade de performance em single-core A taxa de crescimento da performance para sequências de instruções single-core tem diminuído (quase zero); 1 A frequência é limitada pela quantidade de energia; 2 A escalabilidade do ILP foi superada. Os arquitetos têm construídos processadores mais velozes adicionando mais unidades de execução que rodam em paralelo; Construção de unidades especializadas para áudio, vídeo, etc. Mais núcleos com menos perda de energia. Não existe mais ganho de performance sem levar em consideração o paralelismo (sem almoço grátis para os programadores). 43 / 60 Panorama da computação paralela Mudança em 2004 The warning came �rst from a group of hobbyists that tests the speeds of computer chips. This year, the group discovered that the Intel Corporation's newestmicroproces- sor was running slower and hotter than its predecessor. What they had stumbled upon was a major threat to Intel's longstanding approach to dominating the semiconductor industry - relentlessly raising the clock speed of its chips. Then two weeks ago, Intel, the world's largest chip maker, publicly acknowledged that it had hit a �thermal wall� on its microprocessor line. As a result, the company is changing its product strategy and disbanding one of its most advanced design groups. Intel also said that it would abandon two advanced chip development projects, code- named Tejas and Jayhawk. Now, Intel is embarked on a course already adopted by some of its major rivals: obtaining more computing power by stamping multiple processors on a single chip rather than straining to increase the speed of a single processor. 1 1Disponível em https://www.nytimes.com/2004/05/17/business/ technology-intel-s-big-shift-after-hitting-technical-wall.html 44 / 60 https://www.nytimes.com/2004/05/17/business/technology-intel-s-big-shift-after-hitting-technical-wall.html https://www.nytimes.com/2004/05/17/business/technology-intel-s-big-shift-after-hitting-technical-wall.html Panorama da computação paralela Recapitulando: por que paralelismo? Até +-15 anos atrás: Obter ganhos de performance que excediam o que era possível obter com melhorias de CPU; Esperando apenas um ano o código iria rodar mais rápido na próxima geração de CPU; Em especial nos anos 2000 havia muita possibilidade de ganho com o crescimento acelerado da velocidade das CPU. Panorama atual: é a principal forma de obter melhor performance das aplicações num futuro próximo; Existem ainda limitadores em outros componentes; 45 / 60 Panorama da computação paralela Taxonomia de Flynn Taxonomia para classi�cação de sistemas paralelos; Distingue arquiteturas multiprocessador em duas dimensões independentes; Instrução e dados; Cada dimensão pode ter somente um estado: Single ou Múltiplo. SISD: Single Instruction, Single Data Máquina serial (não paralela) SIMD: Single Instruction, Multiple Data Arrays de processadores e máquinas virtuais. MISD: Multiple Instruction, Single Data (estranho) MIMD: Multiple Instruction, Multiple Data Sistemas de computação paralelo mais comum. 46 / 60 Panorama da computação paralela Tipos de arquitetura paralela Paralelismo em nível de instrução: paralelismo capturado no processamento de instruções; Processadores vetoriais: operações em múltiplos dados armazenados em registradores vetoriais; Multiprocessador de memória compartilhada (SMP): Múltiplos processadores compartilhando a memória; Multiprocessador simétrico (SMP). Multicomputador: Múltiplos computadores conectados por rede; Cluster de memória distribuída. Processadores Massivamente Paralelos (MPP) 47 / 60 Panorama da computação paralela Fases de arquiteturas de supercomputadores (paralelos) Fase 1 (1950s) Execução sequencial de instruções Fase 2 (1960s) Problema na execução sequencial Execução em Pipeline, estações de reserva; Paralelismo no Nível de Instrução (ILP). Fase 3 (1970s) Processadores vetoriais Unidades aritméticas com pipeline; Registradores, sistemas de memória com múltiplos bancos em paralelo Fase 4 (1980s) SIMD e SMPs Fase 5 (1990s) MPPs e clusters Processadores de comunicação sequencial Fase 6 (2000-2020) Muitos cores, aceleradores, escala... Fase 7 (>2020)? Computador quântico. 48 / 60 Panorama da computação paralela Paralelismo quântico Imagine que as atividades podem ser dividas em pequenos pacotes independentes; A superposição quântica permite a execução de todas as tarefas ao mesmo tempo de maneira natural2; Figura 4.8: Exemplo de paralelismo quântico 2Conheça mais sobre circuitos quânticos 49 / 60 https://samuraigab.medium.com/primeiros-conceitos-de-circuitos-qu%C3%A2nticos-por-onde-come%C3%A7ar-5fe5e84bbf9d?p=faeabdafdb01 Panorama da computação paralela Expectativas de Desempenho Se cada processador tem k MFLOPS e existem p processadores, nós esperaríamos ver k*p MFLOPS de desempenho? Correto? Se leva 100 segundos em um processador, deveria levar 10 segundos em 10 processadores? Correto? Várias causas afetam o desempenho: Cada uma precisa ser entendida separadamente; Mas elas interagem umas com as outras de modo complexo: uma solução para um problema pode criar outro; um problema pode mascarar outro. Escalonamento (sistema, tamanho do problema) pode mudar condições; É preciso entender o espaço de desempenho. 50 / 60 Panorama da computação paralela Escalabilidade Um problema pode escalonar para utilizar muitos processadores. O que isso signi�ca? Como avaliar a escalabilidade? Como avaliamos a efetividade da escalabilidade? Avaliação comparativamente: Se dobramos o número de processadores, o que esperar? A escalabilidade é linear? Utilizar uma medida de e�ciência de paralelização; A e�ciência é mantida conforme o tamanho do problema aumenta? Aplicamos métricas de desempenho. 51 / 60 Panorama da computação paralela Metodologia de benchmark do top500 Lista dos 500 computadores mais potentes do mundo; Medida para computação de alto desempenho (high-performance computing) � HPC; Rmax: maximal performance Linpack benchmark; Sistema linear denso de equações (Ax=b). Dados listados: Rpeak: máximo teórico de performance; Nmax: tamanho do problema necessário para atingir Rmax; N1/2: tamanho do problema necessário para atingir 1/2 de Rmax; Fabricante e tipo de computador; Local de instalação, localização e ano. Atualizado duas vezes ao ano nas conferências Sc e ISC. 52 / 60 Panorama da computação paralela Melhores de 2013 Figura 4.9: Lista de 10 melhores em novembro de 2013 53 / 60 Panorama da computação paralela Melhores de 2020 Figura 4.10: Lista de 10 melhores em novembro de 2020 54 / 60 Panorama da computação paralela Performance 2013 Figura 4.11: Performance dos melhores em novembro de 2013 55 / 60 Panorama da computação paralela Performance 2020 Figura 4.12: Performance dos melhores em novembro de 2020 56 / 60 Panorama da computação paralela Top 500 Acesso o endereço do top 500 (https://top500.org/) e traga algumas informações: Tipo de arquitetura; Performance em k�ops; Desde quando está no topo; Curiosidades. Tente descobrir as tendências em arquitetura de computadores; Vejamos alguns exemplos. 57 / 60 https://top500.org/ Panorama da computação paralela #1: NUDT Tiahne-2 (Milkyway-2) Figura 4.13: Primeiro colocado em 2013: Tiahne [Fatahalian and Olukotun, 2020] 58 / 60 Panorama da computação paralela Revolução da GPU Figura 4.14: https://adrenaline.com.br/noticias/v/70137/ duas-mil-nvidia-v100-de-32gb-equipam-novo-supercomputador-dragao-da-petrobras 59 / 60 https://adrenaline.com.br/noticias/v/70137/duas-mil-nvidia-v100-de-32gb-equipam-novo-supercomputador-dragao-da-petrobras https://adrenaline.com.br/noticias/v/70137/duas-mil-nvidia-v100-de-32gb-equipam-novo-supercomputador-dragao-da-petrobras Panorama da computação paralela OBRIGADO!!! PERGUNTAS??? 60 / 60 Panorama da computação paralela Fatahalian, K. and Olukotun, K. (2020). Parallel computing. Disponível em http://cs149.stanford.edu/fall20 Acessado em 04/08/2021. Malony, A. D. (2021). Parallel computing development. Disponível em https://ipcc.cs.uoregon.edu Acessado em 04/08/2021. Ocaña, K. and de Oliveira, D. (2015). Parallel computing in genomic research: advances and applications. Advances and applications in bioinformatics and chemistry: AABC, 8:23. 61 / 60 http://cs149.stanford.edu/fall20 https://ipcc.cs.uoregon.edu Visão do curso Introdução Conceitos Panorama da computação paralela