Aula12

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Aula 12: Multiprocessadores e Clusters – Parte 1
Professor: Leandro Marzulo
Arquiteturas Avançadas de Computadores
Introdução
Objetivo: Conectar múltiplos computadores para obter melhor desempenho
Multiprocessadores
Escalabilidade, disponibilidade, eficiência energetica
Paralelismo em nível de job (ou processo)
Vazão alta para jobs independentes
Programa com Processamento Paralelo
Único programa rodando em múltiplos processadores
Precessadoes Multicore (CMP – single-Chip MultiProcessor)
Chips com múltiplos processadores (cores)
2
2
Morgan Kaufmann Publishers
5 February, 2013
Chapter 7 — Multicores, Multiprocessors, and Clusters
2
 Hardware e Software
Hardware
 Melhorias no desempenho virão de mais processadores por chip, e não de maiores frequências de clock e melhor CPI.
Processadores chamados de cores
 Espera-se que o número dobre a cada 2 anos
Processadores Multicore
Software
Programas devem ser paralelizados
3
Hardware e Software
Hardware
Serial: ex, Pentium 4
Paralelo: ex, quad-core Xeon e5345
Software
Sequencial: ex, multiplicação de matrizes
Concorrente: ex, SO (multiprogramação)
SW Sequencial/concorrente pode rodar em HW serial/paralelo
Desafio: fazer uso eficiente do HW paralelo conforme o crescimento do número de cores
4
4
Morgan Kaufmann Publishers
5 February, 2013
Chapter 7 — Multicores, Multiprocessors, and Clusters
4
Questões
Como os processadores paralelos compartilham dados?
Como processadores paralelos são coordenados?
Quantos processadores?
5
Respostas
Questão 1
Memória Compartilhada
Único Espaço de endereçamento (memória global)
Threads ou processos se comunicam através de leituras e escritas em uma região compartilhada de memória
UMA x NUMA
Processos (com SHM), Pthreads, OpenMP, TBB, Java Threads
Passagem de mensagens
Rede de interconexão
Balanço entre computação e comunicação se torna mais crítico
Maior escalabilidade (dependendo da competência dos programadores)
MPI – lamMPI, OpenMPI
Híbrido
Questão 2 - Sincronização!!!
Locks
Memórias Transacionais
Quantidade de cores
Grids > Cluster > NUMA > UMA
6
Memória Compartilhada
7
Placa mãe
Memória RAM
Core0
L1
L2
Core1
L1
L2
Core2
L1
L2
Core3
L1
L2
L3
Chip 0
Core0
L1
L2
Core1
L1
L2
Core2
L1
L2
Core3
L1
L2
L3
Chip 1
Core0
L1
L2
Core1
L1
L2
Core2
L1
L2
Core3
L1
L2
L3
Chip 2
Core0
L1
L2
Core1
L1
L2
Core2
L1
L2
Core3
L1
L2
L3
Chip 3
O que é mais barato? Compartilhar informações entre Chip0.Core0 e Chip0.Core1 ou entre Chip0.Core2 e Chip2.Core0?
Passagem de Mensagem
8
Processador 0
Processador 1
Processador 2
Processador 3
Rede de Interconexão
Híbrido
9
Placa mãe 0
Memória RAM
Core0
L1
L2
Core1
L1
L2
Core2
L1
L2
Core3
L1
L2
L3
Chip 0
Core0
L1
L2
Core1
L1
L2
Core2
L1
L2
Core3
L1
L2
L3
Chip 1
Core0
L1
L2
Core1
L1
L2
Core2
L1
L2
Core3
L1
L2
L3
Chip 2
Core0
L1
L2
Core1
L1
L2
Core2
L1
L2
Core3
L1
L2
L3
Chip 3
O que é mais barato? Compartilhar informações entre PM0.Chip0.Core0 e PM0.Chip0.Core1, PM0.Chip0.Core2 e PM0.Chip2.Core0 ou entre PM0.Chip0.Core3 e PM1.Chip0.Core0?
Placa mãe 1
Memória RAM
Core0
L1
L2
Core1
L1
L2
Core2
L1
L2
Core3
L1
L2
L3
Chip 0
Core0
L1
L2
Core1
L1
L2
Core2
L1
L2
Core3
L1
L2
L3
Chip 1
Core0
L1
L2
Core1
L1
L2
Core2
L1
L2
Core3
L1
L2
L3
Chip 2
Core0
L1
L2
Core1
L1
L2
Core2
L1
L2
Core3
L1
L2
L3
Chip 3
Rede de interconexão
Taxonomia de Flyn (1972)
10
SingleData
MultipleData
SingleInstruction
SISD
SIMD
MultipleInstruction
MISD
MIMD
Taxonomia de Flynn (1972)
11
SISD
Um computador sequencial que não explora paralelismo de instrução nem streams de dados. Uma unidade de controle única busca instruções de de uma única stream na memória. A unidade de controle gera os sinais de controle apropriados para coordenar a operação de um único elemento de processamento sobre a stream de dados.
Exemplo: Processador (mono) tradicional. 
Taxonomia de Flynn (1972)
12
SIMD
Um computador que explora múltiplas streams de dados com apenas uma stream de instruções para executar operações naturalmente paralelizáveis.
Exemplo: Processadores vetoriais (família CRAY-1) ou GPGPUs.
Taxonomia de Flynn (1972)
13
MISD
Múltiplas instruções operam em uma única stream de dados.
Exemplos:
Pipeline de máquinas (o dado vai sendo transformado);
Data-flow: Execução guiada pelo fluxo de dados;
Taxonomia de Flynn (1972)
14
MIMD
Múltiplos processadores autônomos operam simultaneamente executando diferentes instruções com diferentes dados
Exemplos:
Multiprocessadores;
Multicomputadores;
Taxonimia de Flynn (1972)
15
Correlação com:
Paralelismo
MD  Recurso
Distribuição
MI  Controle
Lei de Amdahl
A parte sequencial limita o speedup
Exemplo: Programa que contém soma de duas matrizes 1000x1000 em paralelo com 1000 processadores seguido de 1 soma que só podem ser feitas sequencialmente (tempo de uma soma = t)
Speedup perto do ideal (1000)
Lei de Amdahl
E se tivessemos 100 somas sequenciais?
Como paralelizamos a parte mais significativa, ainda temos um bom desempenho.
Lei de Amdahl
E Se tivessemos 1 milhão de processadores?
Embora o speedup da parte paralela seja de 1 milhão, a parte sequencial se torna o fator limitante no speedup geral (99010)
Speedup Superlinear
Ocorre quando o speedup é superior ao ideal.
Como isso é possível?
Exemplo: Busca sequencial em um vetor
Vetor de 10 inteiros
Queremos buscar o número 150
Tempo t para examinar um elemento
Sequencial: 
Tempo = 6t
Paralelo (em 2 cores)
Dividimos o vetor ao meio e cada core busca na sua parte
Tempo (desconsiderando a divisão do vetor e outros custos extras) = 1t
Speedup ideal = 2 (levaria a metade do tempo)
Speedup obtido = 6!!!
0
1
2
3
4
5
6
7
8
9
50
35
44
33
22
150
49
37
87
67