Arquiteturas Paralelas - PDF
Download "Arquiteturas Paralelas"
Márcio Sequeira Brandt
1 I Escola Regional de Alto Desempenho de SP São Paulo - SP 30 e 31 de Julho de 2010 Arquiteturas Paralelas Prof. Dr. Edson T. Midorikawa Departamento de Engenharia de Computação e Sistemas Digitais Escola Politécnica da USP ERAD-SP
2 Apresentação Prof. Edson Midorikawa Formação Graduação em Engenharia Elétrica EPUSP (1986) Mestrado em Engenharia Elétrica EPUSP (1992) Doutorado em Engenharia Elétrica EPUSP (1997) Atividades Professor doutor da Escola Politécnica da USP Membro do LAHPC (Laboratório de Arquitetura e Computação de Alto Desempenho) Áreas de Interesse Arquiteturas paralelas (multicore, hierarquia de memória) Máquinas virtuais (escalonamento de recursos, gerencia de memória, interação MMV-SO) Computação avançada (cluster, grid, cloud computing) ERAD-SP
3 Sumário Introdução Motivação Classificação de Máquinas Paralelas Paralelismo em Arquitetura de Computadores Pipelining Superescalaridade Multithreading Arquiteturas Multicore Arquiteturas Avançadas Multicores Avançados Multiprocessadores GPGPU Clusters ERAD-SP
4 1. Introdução ERAD-SP
5 Motivação Por que estudar Arquitetura de Computadores? Disciplina obrigatória nos cursos de Engenharia de Computação, Ciência da Computação, Sistemas de Informação, etc. Melhor entendimento do funcionamento (e aproveitamento) das máquinas modernas. Cria novas oportunidades de pesquisa em computação avançada. ERAD-SP
6 Motivação Por que pesquisar Arquiteturas Paralelas? Explora alternativas de projeto de novos sistemas para aumento de desempenho e de recursos de microeletrônica. Área de pesquisa com uma comunidade brasileira ativa e atuante em várias áreas (SBAC-PAD) Áreas de atuação: Desenvolvimento de novos modelos de computação Desenvolvimento de novas arquiteturas de sistemas computacionais (processadores multi-core, multiprocessadores, sistemas de cluster, grid e cloud computing) Viabiliza novas aplicações computacionais (modelos matemáticos) Previsão de tempo e de clima Drug design, genômica, proteômica Simulação (car crash, plataforma petrolífera,...) ERAD-SP
7 Motivação Evolução em várias categorias de computadores ENIAC supercomputador NORC CDC-6600 Cray-1 Cray-2 Cray-3 Cray T3E Cray-4? mainframe UNIVAC /360 /370 /390 z/900 PDP-8 PDP-11 VAX minicomputador x RS/6000 Xeon servidor/workstation PPro microcomputador PII PIIIP4 desktop PC Altair Pentium value PC Celeron ERAD-SP
8 Motivação Evolução do desempenho de processadores SPE Cint92 L eveling off P4/3200 * *** 5000 * Pres Pres cott cott (1M (2M ) ) * * * ** 2000 P4/1500 P4/2000 P4/2400 P4/3060 * Northwood B P4/2800 * * P4/2200 P4/1700 PI I I / ** * * PI I I /1000 PI I /400PI I I /500 PI I /300 PI I / * ~ 100*/10 years Pe ntium/200* Pentium Pro/ Pe ntium/133pe * * * * * 100 Pentium/100 Pentium/120 ntium/166 Pe ntium/66 * 50 * 486-D X 4/ /50 * 486/33* 486-DX2/66 * DX2/50 * 486/25 * 10 * 386/33 386/20 * 5 * 386/25 386/16 * 80286/12 2 * 80286/10 1 * 8088/8 0.5 * 0.2 * 8088/ Year ERAD-SP
9 Motivação Fatores para melhora de desempenho f c (MHz) * * 8088 * 286 * Pentium 4 * * * * * * ~100*/10years * * * Pentium III * * * * Pentium II * * ** * * Pentium Pentium Pro * * * 486-DX4 * ~10*/10years 486-DX2 * * * * * * * * * * Aumento da Frequencia do relógio Leveling off * * * Year Year of first volume shipment ERAD-SP
10 Motivação Fatores para melhora de desempenho (2) Lei de Moore ERAD-SP
11 Motivação Fatores para melhora de desempenho (3) Como manter a tendencia de aumento de desempenho dos processadores? O que fazer se não é possível manter continuamente o aumento do clock? Como utilizar eficientemente os transistores disponíveis em um chip? ERAD-SP
12 Motivação Resposta PARALELISMO ERAD-SP
13 Classificação de Máquinas Paralelas Classificação de Flynn Classificação de arquiteturas paralelas genérica de acordo com as características do fluxo de instruções e o fluxo de dados (único ou múltiplo) Michael J. Flynn ERAD-SP
14 Classificação de Máquinas Paralelas SISD Single Instruction, Single Data Um único fluxo de instruções Um único fluxo de dados Contém as arquiteturas tradicionais não paralelas Máquinas de Von Neumann instrução dado UC = unidade de controle UP = unidade de processsamento MEM = memória ERAD-SP
15 Classificação de Máquinas Paralelas SIMD Single Instruction, Multiple Data Um único fluxo de instrução Múltiplos fluxos de dados Execução síncrona da instrução para todos os dados Exemplos: Processadores vetoriais (Cray 1) GPU instrução dados ERAD-SP
16 Classificação de Máquinas Paralelas MISD Multiple Instruction, Single Data Múltiplos fluxos de instrução Um único fluxo de dados Execução de várias instruções em um único dado. UP2 UP Não há exemplos. UCn instruções UPn dado ERAD-SP
17 Classificação de Máquinas Paralelas MIMD Multiple Instruction, Multiple Data Múltiplos fluxos de instruções Múltiplos fluxos de dados Permite a execução de instruções diferentes para cada um dos dados Exemplos: Arquiteturas paralelas atuais Top500.org instruções dados ERAD-SP
18 Máquinas Paralelas Top500.org Lista com os 500 computadores mais rápidos Atualizada duas vezes ao ano (junho e novembro) ERAD-SP
19 ERAD-SP
20 2. Paralelismo em Arquitetura de Computadores ERAD-SP
21 Fontes de Paralelismo Há várias fontes de execução paralela em um computador moderno: Aplicações diferentes; Instâncias de execução da mesma aplicação; Multiprogramação Multitarefa Fluxo de instruções (threads) de uma aplicação; Instruções de um programa (ILP) Processadores multicore ERAD-SP
22 Fontes de Paralelismo Paralelismo no Nível de Instrução (ILP) Permite executar várias instruções em cada ciclo de relógio. Modificações na microarquitetura do processador para possibilitar a execução paralela de instruções. Alternativas: Paralelismo temporal: encadeamento no fluxo de execução das instruções (pipeline); Paralelismo na emissão de instruções: submissão de várias instruções para execução pelo fluxo de dados (VLIW e superescalaridade); Paralelismo de dados: permite executar várias instâncias da mesma instrução para um conjunto de dados (processamento SIMD ou vetorial). ERAD-SP
23 Fontes de Paralelismo Paradigmas de processamento ILP Paralelismo Temporal Paralelismo de Emissão de Instruções Paralelismo de Dados Resolução estática de dependências Resolução dinâmica de dependências Processadores com Pipeline Processadores VLIW Processadores Superscalares extensão SIMD ERAD-SP
24 Evolução do Paralelismo Extensão do paralelismo da execução Processamento Sequencial ILP Paralelismo temporal + paralelismo de envio de instruções + paralelismo de dados Processadores von Neumann tradicionais Processadores Pipelined Processadores Superscalares Processadores Superscalares com extensão SIMD ~ 1985/88 ~ 1990/93 ~ 1994/00 t Nível de redundância de hardware ERAD-SP
25 Pipelining Execução de uma instrução é dividida em etapas: Memória Registradores Memória IF ID EXE MEM WB IF = busca da instrução na memória (inclui atualização do PC) ID = decodificação da instrução + busca de valores em registradores EXE = execução da instrução (ULA ou cálculo de endereços) MEM = acesso à memória ou instrução de desvio WB = escrita resultados nos registradores de saída Uma instrução leva 5 períodos de clock para concluir. ERAD-SP
26 Pipelining Fluxo de dados do processador MIPS didático (COD/4e, Patterson & Hennessy) ERAD-SP
27 Pipelining Inicia a execução de uma instrução por ciclo de clock fluxo de instruções IF ID I1 I2 I1 EXE MEM WB I3 I4 I5 I6 I2 I3 I4 I5 I1 I2 I3 I4 I1 I2 I3 I1 I2 ciclo A cada ciclo de clock, termina-se a execução de uma instrução. ERAD-SP
28 Superescalaridade Em um processador superescalar, várias instruções são submetidas para execução simultaneamente. Memoria Busca instruções Registradores Memoria instruções de instr. ID EXE MEM WB Várias instruções do programa são analisadas para execução paralela. PROBLEMA: dependência de dados entre instruções. ERAD-SP
29 Superescalaridade Dependência de dados Time (cycles) lw $t0, 40($s0) IM lw RF $s DM $t0 RF add $t1, $t0, $s1 sub $t0, $s2, $s3 IM add sub RF $t0 $s1 $s2 $s3 RF $t0 $s1 $s2 $s3 + - DM $t1 $t0 RF and $t2, $s4, $t0 or $t3, $s5, $s6 Stall and IM or IM and or RF $s4 $t0 $s5 $s6 & DM $t2 $t3 RF sw $s7, 80($t3) IM sw RF $t $s7 DM RF ERAD-SP
30 Superescalaridade Para resolver o problema da dependência de dados, um processador superescalar permite a execução fora de ordem das instruções (OOO out of order execution) Time (cycles) lw $t0, 40($s0) or $t3, $s5, $s6 IM lw or RF $s0 40 $s5 $s6 + DM $t0 $t3 RF RAW sw $s7, 80($t3) two cycle latency between load and RAW use of $t0 add $t1, $t0, $s1 WAR sub $t0, $s2, $s3 IM $t3 sw $s RF DM $t0 add $s1 + IM RF $s2 sub $s3 - RF DM $t1 $t0 RF RAW and $t2, $s4, $t0 IM and RF $s4 $t0 & DM $t2 RF ERAD-SP
31 Multithreading Algumas definições: Processo: programa rodando em um computador. Vários processos estão em execução simultaneamente, como p. ex.: browser Web, editor de texto, anti-virus. Thread: parte de um processo. Cada processo pode ter vários threads, como p. ex.: um editor de texto pode ter vários threads para digitação, verificação ortográfica e impressão. Em um processador convencional: Apenas um thread é executado por vez. Quando ocorre uma parada (stall) na execução de um thread (p.ex. acesso à memória), realiza-se uma troca de contexto para outro thread. ERAD-SP
32 Multithreading Em um processador com multithreading, vários threads podem estar ativos ao mesmo tempo: Possui mais de um conjunto de registradores de estado Quando ocorre stall em um thread, outro é colocado em execução imediatamente (não há necessidade de operações de salvamente e carga de estado) Se um thread não usar uma unidade funcional (p.ex. somador, ULA, FPU), outro pode usá-lo Não modifica o paralelismo de instruções de um único thread, mas aumenta o desempenho geral do sistema. ERAD-SP
33 Multithreading A presença de vários conjuntos de registradores de estado é normalmente interpretado pelos sistemas operacionais como se houvesse vários processadores (virtuais), onde os processos podem ser escalonados. Permite um melhor compartilhamento dos recursos do processador Unidades funcionais Memórias cache ERAD-SP
34 Multithreading Simultaneous Multithreading (SMT) Permite executar instruções de threads de vários programas (processos) simultaneamente sem a necessidade de troca de contexto sem multithreading blocked multithreading Interleaved multithreading SMT ciclos cache miss Vantagens Permite a execução simultânea de mais instruções por ciclo Desempenho total se tiver apenas um thread ativo ERAD-SP
35 Multithreading Superescalar (4-way) Superescalar com SMT (4-way/2 threads) Thread Thread 1 Thread 2 ERAD-SP
36 Multithreading Simultaneous Multithreading A Intel implementa a técnica SMT em seus processadores com o nome comercial Hyperthreading (HT) permitindo a execução simultânea de 2 threads por core. Sun UltraSparc T2 (8 threads por core) IBM Power 7 (4 threads por core) ERAD-SP
37 Arquiteturas Multicore ERAD-SP
38 Processadores Multicore Etapa atual no desenvolvimento de novas arquiteturas de processadores. Permite a execução simultânea de múltiplos threads e/ou aplicações. Inclui vários núcleos de processadores na pastilha. ERAD-SP
39 Exemplos de Multicore Intel Core i7 e AMD Phenom X6 ERAD-SP
40 Exemplos de Multicore Intel Xeon 5600 (hexacore) ERAD-SP
41 Exemplos de Multicore Intel Xeon 7500 (8-core) ERAD-SP
42 Exemplos de Multicore AMD Opteron 6000 (12-core) ERAD-SP
43 Intel Processadores Multicore Tilera Tile64 UltraSparc T2 ERAD-SP
44 Paralelismo no Nível de Threads Granularidade do paralelismo TLP (paralelismo no nível de threads) Múltiplos threads ILP (paralelismo no nível de instruções) Thread (fluxo de instruções) ERAD-SP
45 Paralelismo no Nível de Threads Execução paralela de threads De onde vem os vários threads? de aplicações diferentes da mesma aplicação Multiprogramação Multitarefa, Multithreading ERAD-SP
46 Paralelismo no Nível de Threads Implementação de paralelismo no nível de threads em microprocessadores SMP: Symmetric Multiprocessing (CMP: Chip Multiprocessing) Implementação de dois ou mais cores colocados na mesma pastilha SMT: Simultaneous Multithreading (HT: Hyperthreading (Intel)) Implementação de um core multithreaded Core L2/L3 Core pastilha (chip) Core SMT L2/L3 L3/Memória ERAD-SP 2010 L3/Memória 46
47 Paralelismo no Nível de Threads Simultaneous Multithreading Superescalar (4-way) Superescalar com SMT (4-way/2 threads) Thread Thread 1 Thread 2 ERAD-SP
48 Paralelismo no Nível de Threads Simultaneous Multiprocessing Nehalem-EX ERAD-SP
49 Simultaneous Multiprocessing A presença de vários núcleos de processador (core) em um computador pode ser realizada em dois níveis distintos: Multiprocessador: vários chips processadores. Multicore: um único chip processador com vários cores. chip único ERAD-SP
50 Multicore Vários processadores single core agrupados em um único chip (CMP = chip multiprocessor). Replicação real dos recursos de um processador dentro do chip (ao contrário do multithreading) Compatibilidade de código com os multiprocessadores (modelo de memória compartilhada) Incorpora uma hierarquia complexa de memórias cache interna Caches L1 e L2 privados (particulares a cada core) Cache L3 único e compartilhado entre os cores ERAD-SP
51 Multicore Organização interna de um Multicore Principais componentes: Núcleos de processador (cores) Memórias cache Rede de interconexão interna Interface com barramento de E/S externo Controlador de interrupções Timers etc Fonte: ARM, The ARM Cortex-A9 Processors White Paper, ERAD-SP
52 Hierarquia de caches Multicore ERAD-SP
53 Interconexão Interna Multicore Implementação das interconexões Árbitro/Implementações de cache multi-porta Crossbar Anel Aspectos quantitativos, tais como número de fontes e destinos ou requisitos de banda, afetam qual alternativa de implementação é mais benéfica. Número pequeno de fontes e destinos p.ex. Conexão dos dual-cores aos cache L2 compartilhado UltraSPARC T1 (2005) UltraSPARC T2 (2007) Número grande de fontes e destinos Cell BE (2006) XRI (2005) ERAD-SP
54 Multicore Aplicação de multicores vs. SMP e processadores superescalares Instrução Bloco básico Loop Tarefa Processo Fonte: Olukotun et al. Chip Multiprocessor Architecture, ERAD-SP
55 Multicore Breve Histórico Prescott (core original) Smithfield (dois cores Prescott modificados colocados no mesmo die) 2/2004 5/ nm 112 mm mtrs L2: 1 MB Pentium 4 A/E/F series Pentium 4 5xx series 90 nm 2 x 103 mm 2 2 x 115 mtrs L2: 2 MB Pentium D 8xx Pentium EE 840 Pentium D/EE ERAD-SP
56 Multicore Breve Histórico Conroe (die) Kentsfield (dois Conroes no mesmo empacotamento) 7/ nm 143 mm 2 167/291 mtrs 11/ nm 2 x 143 mm 2 2 x 167/291 mtrs Core 2 Duo E 6x00 series Core 2 Extreme QX6x00 series Core2 Extrem X6x00 series ERAD-SP
57 Desafio dos Multicores Os processadores multicore... possuem uma grande capacidade computacional ( lembre-se que um octocore permite executar ao menos 8 threads simultaneamente ); Implementam várias otimizações para execução paralela (caches integrados, alta banda de comunicação, etc); mas Os programas existentes não foram escritos para usar tais recursos. ERAD-SP
58 Desafio dos Multicores É muito importante que a aplicação seja capaz de aproveitar completamente os recursos dos processadores multicore. Conceitos de programação paralela e multithreaded. ERAD-SP
59 ERAD-SP 2010 Fonte: Multi-core Programming, Intel Press,
60 3. Arquiteturas Avançadas ERAD-SP
61 Multicores Avançados IBM Power 7 Lançado em ,2 bilhões de transistores Módulos de até 4 soquetes 4, 6 ou 8 cores por chip 4 threads SMT por core 12 unidades funcionais por core ERAD-SP
62 Multicores Avançados Sun UltraSparc T3 a ser lançado em bilhão de transistores 16 cores 8 threads SMT por core 128 threads por chip SMP com 4 processadores ERAD-SP
63 Manycore Pastilhas de processadores multicore com cores heterogêneos Aplicações Processamento especializado Co-processamento Exemplos: Cell (Sony, Toshiba, IBM) Intel Sandy Bridge AMD Fision ERAD-SP
64 Manycore Cell 1 PPE (PowerPC) 8 SPE PS3 (Cell BE) Roadrunner (PowerXCell 8i) Top 500 #3 ERAD-SP
65 Manycore Cell Fonte: Gshwind M., Chip Multiprocessing and the Cell BE, ACM Computing Frontiers, 2006, ERAD-SP
66 Manycore Cell Circuito de um único SPE Fonte: Gshwind M., Chip Multiprocessing and the Cell BE, ACM Computing Frontiers, 2006, ERAD-SP
67 Manycore CPU + GPU (ex. Intel Sandy Bridge, AMD Fusion) ERAD-SP
68 GPGPU GPGPU = General Purpose computation on Graphics Processing Unit Utilização de GPUs (unidades de processamento gráfico) para execução de computação normalmente realizada em CPUs. Exemplos: NVIDIA ATI ERAD-SP
69 GPGPU GPU Unidade de processamento especializado para acelerar o processamento gráfico 2D e 3D. ERAD-SP
70 GPGPU GPU Arquitetura baseada em SP (streaming processor) e SFU (Special Function Units) ERAD-SP
71 GPGPU CPU vs. GPU Comparação relativa a utilização de área de silício alocada por funcionalidade nas CPUs e GPUs. Fonte: Nvidia, Compute Unified Device Architecture Programming Guide ERAD-SP
72 GPGPU Princípios básicos Multicore streaming multiprocessor (Nvidia) superscalar shader processor (AMD) wide SIMD processor, CPU core (Intel). Processamento vetorial Modelo SIMD Paralelismo de dados Hardware Multithreading Sincronização de barreira ERAD-SP
73 Paralelismo de dados GPGPU Mesma instrução para todos os dados ERAD-SP
74 GPGPU Fonte: Nvidia, Compute Unified Device Architecture Programming Guide ERAD-SP
75 GPGPU Mais informações: gpgpu.org developer.amd.com (ATI) Minicurso 2 (avançado): Programação Paralela: CUDA Raphael Y. de Camargo (UFABC) ERAD-SP 2010 (Material disponível no CD) ERAD-SP
76 Multiprocessadores Um multiprocessador contém vários (chips de) processadores Memória compartilhada entre os processadores Comunicação pela memória Modelo UMA (uniform memory access) Baixa escalabilidade (até poucas dezenas de processadores) Fácil programação (OpenMP, CPar,...) ERAD-SP
77 Arquitetura básica Multiprocessadores ERAD-SP
78 Multiprocessadores Cada processador pode ser um multicore com suporte a multithreading Vários níveis de paralelismo Outras questões importantes Coerência de caches Multiprocessadores NUMA Programação paralela ERAD-SP
79 Coerência de caches Multiprocessadores Várias soluções na literatura. ERAD-SP
80 Multiprocessadores Multiprocessadores NUMA NUMA = Non-Uniform Memory Acess Grupos de processadores com sua respectiva memória Tempos de acesso à memória diferentes Mantém modelo de memória compartilhada (mas precisa cuidados para obter desempenho) ERAD-SP
81 Multiprocessadores Programação Paralela Método de desenvolvimento de programas que explora a disponibilidade de vários processadores/cores para uma única aplicação. Modelos de programação Memória compartilhada (OpenMP, CPar) Memória distribuída (MPI) Mais informações: Minicurso 3 (básico): Programação Paralela: multicores e clusters Profa. Dra. Liria Matsumoto Sato (Poli-USP) (amanhã 31/07 às 14h00) ERAD-SP
82 Clusters Arquitetura de sistema paralelo multiprocessador organizado como um conjunto de processadores interligados através de uma rede de interconexão rápida Interconexão rápida (Myrinet, Infiniband, Gigabit Ethernet) Rede interna de administração (Ethernet) cluster ERAD-SP
83 Clusters Conhecido inicialmente como NOW (Network of Workstations) ou COW (cluster of workstations) Cada nó tem sua própria memória local (não compartilhada) Comunicação por troca de mensagens Difícil programação Modelo de programação diferente Conceito cliente-servidor MPI ERAD-SP
84 Máquinas comerciais Clusters ERAD-SP
85 4. Considerações Finais ERAD-SP
86 Alguns pensamentos: Arquiteturas Paralelas Hoje, a maioria de sistemas computacionais apresenta uma arquitetura paralela. Contudo nossos cursos não apresentam este conteúdo de forma detalhada. É uma grande oportunidade para todos melhorar sua formação com um estudo detalhado deste tópico. ERAD-SP
87 Pensamento final: Arquiteturas Paralelas Precisamos difundir a necessidade em compreender o funcionamento das arquiteturas paralelas e do aprendizado das técnicas de programação paralela e distribuída para usufruirmos dos benefícios destas máquinas. ERAD-SP
88 Bibliografia Algumas referências bibliográficas interessantes para consulta sobre Arquiteturas Paralelas: Akter, S.; Roberts, J. Multi-core Programming. Intel Press, Culler, D.; Singh, J. Parallel Computer Architecture: A Hardware/ Software Approach. Morgan Kaufmann, De Rose, C.; Navaux, P. Arquiteturas Paralelas. Editora Sagra-Luzzatto, (Série Livros Didáticos - Número 15) Grama, A.; Gupta, A.; Karypis, G. and Kumar, V. Introduction to Parallel Computing. 2 nd ed., Addison-Wesley, Hennessy, J.L.; Patterson, D.A. Computer Architecture: A Quantitative Approach. 4 th ed., Morgan Kaufmann, Olukotun, K.; Hammond, L. and Laudon, J. Chip Multiprocessor Architecture: Techniques to Improve Throughput and Latency. Morgan & Claypool, Zomaya, A.Y.H. (ed.) Parallel & Distributed Computing Handbook. McGraw-Hill, ERAD-SP