Upload
buiminh
View
217
Download
0
Embed Size (px)
Citation preview
29/3/16
1
Processamento Paralelo Arquitetura de Sistemas Paralelos e Distribuídos
Prof. João Paulo A. Almeida ([email protected])
2016/01
Informações gerais • Página web:
http://nemo.inf.ufes.br/jpalmeida/ensino • Carga horária semestral total: 60 horas • Horário:
– terças 13:00-15:00 – sextas 16:00-18:00
• Local, atenção: – CT-9 sala 207 (terças) – CT-9 sala 204 (sextas)
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
• 5ª Edição, capítulo 6
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
• Redes compartilhadas, comunicação peer-to-peer, máquinas heterogêneas, problemas de segurança, …
Autonomia
29/3/16
2
Paralelismo no nível de instrução • Metodologias básicas para melhorar a
“velocidade” de uma CPU: – 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
• Velocidade (throughput, número de instruções por unidade de tempo) versus custo
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
30
B
C D
A Tempo 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
6 PM 7 8 9 10 11 12 1 2 AM
• De maneira sequencial, eles levam 8 horas para 4 cargas • Quanto tempo levaria se eles utilizassem a técnica de pipeline?
Lavanderia paralela (pipeline)
• Lavanderia Pipelined leva 3.5 horas para 4 cargas!
T a s k O r d e r
12 2 AM 6 PM 7 8 9 10 11 1
Tempo
B C D
A 30 30 30 30 30 30 30
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
F
Inst
ruçã
o
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
29/3/16
3
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
• Redes compartilhadas, comunicação peer-to-peer, máquinas heterogêneas, problemas de segurança, …
Autonomia
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 multi-threading / 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
• Redes compartilhadas, comunicação peer-to-peer, máquinas heterogêneas, problemas de segurança, …
Autonomia
Vários processadores, memória compartilhada
Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,
29/3/16
4
Vários processadores, memória compartilhada
Parallel Programming Techniques & Applications Using Networked Workstations & Parallel Computers 2nd ed., by B. Wilkinson & M. Allen,
Symmetric Multiprocessing / SMP: Processadores idênticos / multi core Memória compartilhada
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
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
• Redes compartilhadas, comunicação peer-to-peer, máquinas heterogêneas, problemas de segurança, …
Autonomia
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
29/3/16
5
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
supercomputadores 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)
29/3/16
6
Cyclops64 (Blue Gene/C)
x4
Cyclops64 (Blue Gene/C)
x48
x4
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)
29/3/16
7
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 (grids) (na Internet) • BOINC
– Várias aplicações: SETI@home, FOLDING@home, Einstein@home
• 500 Tflops (média), Jan. 2007 • 1,287 Pflops, Dez. 2008 • 5,1 Pflops as of April 21, 2010 • 9,2 Pflops as of March 2013 • 10,915 petaFLOPS as of 1 January 2016
– 383,337 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 10,500,000+ 10 billion/day DownUp, DownAndUp, DownAdUp, Kido
? Zeus 3,600,000 (US Only) -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
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
• Redes compartilhadas, comunicação peer-to-peer, máquinas heterogêneas, problemas de segurança, …
Autonomia
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