Processamento Paralelo Arquitetura de Sistemas Paralelos e

Processamento Paralelo
Arquitetura de Sistemas
Paralelos e Distribuídos
Prof. João Paulo A. Almeida
([email protected])
2013/01
Informações gerais
•  Página web:
http://nemo.inf.ufes.br/jpalmeida/ensino/
2013-01-ppd
•  Carga horária semestral total: 60 horas
•  Horário:
–  terças 15:00-17:00
–  sextas 16:00-18:00
•  Local: CT-9 sala 202
Avaliação
•  Duas provas parciais e trabalhos
•  A média parcial (MP) é calculada por:
MP = 0,6*P + 0,4*T
onde:
P é a média aritmética das provas parciais e
T é a média aritmética das notas dos trabalhos.
•  A média final (MF) será:
MF = MP, se MP ≥ 7,0 (e houver presença)
MF = (PF + MP)/2, se MP < 7,0
(PF é a nota da prova final)
•  Se MF ≥ 5,0 -> Aprovado
•  Se MF < 5,0 -> Reprovado
Material didático
•  COULOURIS, George F.; DOLLIMORE, Jean;
KINDBERG, Tim. Sistemas distribuídos:
conceitos e projeto. 4. ed. Porto Alegre:
Bookman, 2007.
•  Distributed Systems: Concepts and Design,
4. ed. Addison Wesley, 2005.
–  Existe uma 5ª edição em inglês
•  Pelo menos os capítulos:
–  1, 2, 4, 5, 9, 19, 20
Material didático
•  Capítulo 3, seções 3.1 e 3.2 de "Introduction to Parallel
Computing" (2nd Edition) de Ananth Grama, George
Karypis, Vipin Kumar, Anshul Gupta, Addison Wesley,
2003.
•  Artigos e tutoriais online:
–  P.A. Bernstein. Middleware. Communications of the ACM,
Vol. 39, No. 2, February 1996, 86-98.
–  P. Eugster, P. Felber, R. Gerraoui, A.M. Kermarrec, The
Many Faces of Publish/Subscribe, ACM Computing Surveys,
Vol. 35, No. 2, June 2003, pp. 114–131.
–  Tutorial Java RMI:
•  http://java.sun.com/docs/books/tutorial/rmi/index.html
–  Tutorial JMS:
•  http://java.sun.com/j2ee/1.4/docs/tutorial/doc/JMS.html#wp84181
Níveis de paralelismo
1.  Paralelismo no nível de instrução
2.  Várias linhas de execução em um mesmo
processador
3.  Várias linhas de execução em diferentes
processadores (SMP, dual, quad core)
4.  Computadores paralelos
•  interconectados com redes dedicadas de alta
velocidade
5.  Cluster de computadores
6.  Computadores na Internet
Autonomia
•  Redes compartilhadas, comunicação peer-topeer, máquinas heterogêneas, problemas de
segurança, …
Paralelismo no nível de instrução
•  Velocidade (throughput) versus custo
•  Metodologias básicas para melhorar a
velocidade (fixando circuito e ISA):
–  Simplificar organização da máquina de modo a
reduzir o período do clock;
–  Reduzir número de ciclos de clock necessários
para executar uma instrução;
–  Sobrepor a execução das instruções (pipelines!!!)
•  Uma CPU, fazendo uso mais adequado do
hardware
Paralelismo no nível de instrução
•  Exemplo da lavanderia
•  Patrícia, Fernanda, Pedro, João
têm cada um saco de roupas para lavar, secar e
dobrar
•  O ciclo de lavagem leva 30 minutos
•  O de secagem leva 30 minutos
•  O tempo para dobrar é de 30 minutos
•  O funcionário leva 30 minutos
para colocar as roupas no armário
A
Lavanderia sequencial
6 PM
A
7
8
9
10
11
12
1
2 AM
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
Tempo
B
C
D
• De maneira sequencial, eles levam 8 horas para 4 cargas
• Quanto tempo levaria se eles utilizassem a técnica de
pipeline?
Lavanderia paralela (pipeline)
6 PM
T
a
s
k
O
r
d
e
r
7
8
9
30 30 30 30 30 30 30
10
11
12
1
Tempo
A
B
C
D
• Lavanderia Pipelined leva 3.5 horas para 4
cargas!
2 AM
Paralelismo no nível de instrução
•  5 estágios básicos
–  Carrega (fetch)
instrução (F)
–  decodifica instrução
instruction / lê
registradores (R)
–  executa (X)
–  acessa memória (M)
–  armazena resultados
nos registradores (W)
I-Fetch
Decode
Execute
Memory
Write
Result
Paralelismo no nível de instrução
Instrução
F
R
X
M
W
F
R
X
M
W
F
R
X
M
W
F
R
X
M
W
F
R
X
M
F
R
X
Paralelismo no nível de instrução
•  Pipelining é um mecanismo que permite a
sobreposição temporal das diversas fases da
execução de instruções
•  Aumenta o throughput das instruções (mais
instruções são executadas por unidade de
tempo). Porém, pipeline não ajuda na latência
da execução de uma única instrução
Paralelismo no nível de instrução
•  Assume independência entre fases da execução
da instrução
•  Não é sempre o caso (ex., saltos condicionais)
levam a ociosidade
•  Afeta a eficiência
•  Um assuntos para arquitetura de
computadores...
Níveis de paralelismo
1.  Paralelismo no nível de instrução
2.  Várias linhas de execução em um mesmo
processador
3.  Várias linhas de execução em diferentes
processadores (SMP, dual, quad core)
4.  Computadores paralelos
•  interconectados com redes dedicadas de alta
velocidade
5.  Cluster de computadores
6.  Computadores na Internet
Autonomia
•  Redes compartilhadas, comunicação peer-topeer, máquinas heterogêneas, problemas de
segurança, …
Várias linhas de execução: um processador
•  Paralelismo
“simulado”
–  processos
–  threads
•  “Logicamente” há
várias linhas de
execução
•  “Fisicamente” não há
•  Um assunto de
sistemas
operacionais...
•  ... mas uso de multithreading / processos
é muito importante
na programação de
sistemas distribuídos
Fonte: Douglas Schmidt http://www.cs.wustl.edu/~schmidt/PDF/mt-unix4.pdf
Níveis de paralelismo
1.  Paralelismo no nível de instrução
2.  Várias linhas de execução em um mesmo
processador (single core)
3.  Várias linhas de execução em diferentes
processadores/cores (SMP, dual, quad core)
4.  Computadores paralelos
•  interconectados com redes dedicadas de alta
velocidade
5.  Cluster de computadores
6.  Computadores na Internet
Autonomia
•  Redes compartilhadas, comunicação peer-topeer, máquinas heterogêneas, problemas de
segurança, …
Vários processadores, memória compartilhada
Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed.,
by B. Wilkinson & M. Allen,
Vários processadores, memória compartilhada
Symmetric Multiprocessing / SMP:
Processadores idênticos / multi core
Memória compartilhada
Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed.,
by B. Wilkinson & M. Allen,
Quad Pentium
multi-core: vários processadores, mesmo chip
Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed.,
by B. Wilkinson & M. Allen,
Processador de 3 cores Xenon no Xbox 360
Multi-computadores / Computadores paralelos
Memória Local
Processador de 1+1+6 cores Cell no PS3
http://beautifulpixels.blogspot.com/2008/08/multi-platform-multi-core-architecture.html
Memória Compartilhada Distribuída
NUMA (Non-Uniform Memory Access)
Acesso à memória local é mais rápido que acesso à memória remota
Taxonomia de Flynn
Single
Instruction
Multiple
Instruction
Single
Data
SISD
(PCs /
Mainframes)
MISD
(redundância, ex:
avião)
Multiple
Data
SIMD
(vector / array)
MIMD
(maioria dos
supercomputad
ores atuais)
Arquiteturas são frequentemente híbridas
CUDA
•  NVIDIA fala:
– 240 stream
processors
•  Mais claro:
–  30 cores
–  8 SIMD/core
Fonte (texto): http://s09.idav.ucdavis.edu/talks/02_kayvonf_gpuArchTalk09.pdf
Cyclops64 (Blue Gene/C)
Arquitetura celular
Objetivo: 1.1 Pflops
Cyclops64 (Blue Gene/C)
•  Cada chip contém 80 processadores de 64-bits /
500 MHz, cada processador suporta 2 linhas de
execução (threads).
•  80 gigaflops por chip (desempenho teórico de
pico)
Cyclops64 (Blue Gene/C)
x4
Cyclops64 (Blue Gene/C)
x4
x48
Cyclops64 (Blue Gene/C)
x4
x48
x72
Para quem perdeu as contas...
• 
• 
• 
• 
2 x 80 x 4 x 48 x 72
2.211.840 linhas de execução
1.1 Pflops
13.8 TB RAM
Blade server farms
http://en.wikipedia.org/wiki/Image:IBM_bladecenter_%28front%29.jpg
Dificuldades
•  HVAC - heating, ventilating, and air conditioning
•  Refrigeração
–  desempenho por watt dissipado
•  Refrigeração a líquido
•  (Interessante: localização de grandes
datacenters em locais frios, longe do equador)
Dificuldades
•  Falhas
•  Com muitos elementos não há como não haver
falhas
•  Faça um cálculo de probabilidade:
–  1024 máquinas, com taxa λ de falha...
–  Qual a taxa de falha da máquina como um todo,
se a máquina tivesse que funcionar a todo
momento?
Computação de alto desempenho na Internet
•  Formação de clusters virtuais (grid) (na
Internet)
•  BOINC
•  SETI@home, FOLDING@home, Einstein@home
•  500 Tflop/s (média), Jan. 2007
•  925 Tflops/s (média), Fev. 2008
•  1.287 Pflops, Dez. 2008
–  Com 565000 computadores
•  5.1 PFLOPS as of April 21, 2010
•  9.2 petaFLOPS as of March 2013
–  596224 active computers
•  Universidade da Califórnia, Berkeley
•  http://en.wikipedia.org/wiki/BOINC
Botnets
Date created
Name
Estimated no. of bots
Spam capacity
Aliases
2009 (May)
BredoLab
30,000,000
3.6 billion/day
Oficla
2008 (around)
Mariposa
12,000,000
0?
?
?
Conficker
Zeus
10,500,000+
3,600,000 (US Only)
10 billion/day
DownUp,
DownAndUp,
DownAdUp, Kido
-1n/a
Zbot, PRG,
Wsnpoem,
Gorhax, Kneber
2007 (Around)
Cutwail
1,500,000
74 billion/day
Pandex, Mutant
(related to:
Wigon, Pushdo)
?
Grum
560,000
39.9 billion/day
Tedroo
?
Mega-D
509,000
10 billion/day
Ozdok
?
Kraken
495,000
9 billion/day
Kracken
http://en.wikipedia.org/wiki/Botnet
Diferentes modelos de interação em
software
•  Middleware
•  RPC – Remote Procedure Call
•  Orientado a objetos distribuídos
–  Distributed Objects
–  Remote Method Invocation
•  Orientado a passagem de mensagem
•  Orientado a eventos (publish/subscribe)
•  Orientado a streams (fluxo de dados)
–  Multimedia streams: áudio e vídeo
•  Orientado a serviços