View
215
Download
0
Category
Preview:
Citation preview
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 1
São Paulo, 2011São Paulo, 2011
Universidade Paulista (UNIP)Universidade Paulista (UNIP)
Programação ParalelaProgramação Paralela
Prof. Msc. Vladimir CameloProf. Msc. Vladimir Camelovladimir.professor@gmail.com
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 2
O que é pipeline?O que é pipeline?
Técnica inicialmente utilizada em processadores com arquitetura Técnica inicialmente utilizada em processadores com arquitetura
RISC (Reduced Instruction Set Computer);RISC (Reduced Instruction Set Computer);
É um recurso de hardware utilizado para dividir o processador em É um recurso de hardware utilizado para dividir o processador em
vários estágios no processo de execução, de forma simultânea, vários estágios no processo de execução, de forma simultânea,
dividindo o trabalho de processar as instruções.dividindo o trabalho de processar as instruções.
É como uma linha de produção com vários operários, em que É como uma linha de produção com vários operários, em que
cada um monta uma peça, até que seja entregue um produto cada um monta uma peça, até que seja entregue um produto
completo ao final do processo de produção.completo ao final do processo de produção.
Algumas definiçõesAlgumas definições
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 3
O que é pipeline?O que é pipeline?
A vantagem desta técnica, é que o primeiro estágio não
precisa ficar esperando a instrução passar por todos os
demais para carregar a próxima, e sim carregar uma nova
instrução assim que se livra da primeira, ou seja, depois do
primeiro pulso de clock.
Algumas definiçõesAlgumas definições
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 4
Algumas definiçõesAlgumas definições
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 5
Crescimento nos últimos anos na demanda por computação de alto Crescimento nos últimos anos na demanda por computação de alto
desempenho em áreas diversas, tais como:desempenho em áreas diversas, tais como:
Biomecânica;Biomecânica;
Meteorologia; eMeteorologia; e
Engenharia.Engenharia.
IntroduçãoIntrodução
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 6
Existem limites físicos para o aumento da velocidade de um único Existem limites físicos para o aumento da velocidade de um único
processador, como por exemplo:processador, como por exemplo:
Alto custo associado ao desenvolvimento de novas tecnologias de Alto custo associado ao desenvolvimento de novas tecnologias de
processamento para aumentar a velocidade (memória, processamento para aumentar a velocidade (memória,
processador, barramento, outros);processador, barramento, outros);
IntroduçãoIntrodução
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 7
Início Fim
Programação não paralela
T1 T2 T3 T4 T5 T6 T7 T8 T9
Visão geral da programação paralelaVisão geral da programação paralela
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 8
Início Fim
Tarefa 2
Tarefa 1
Tarefa 3
Tarefa 4
Tarefa 5
Programação paralela
Visão geral da programação paralelaVisão geral da programação paralela
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 9
Estas novas arquiteturas integram vários processadores (dezenas a Estas novas arquiteturas integram vários processadores (dezenas a
milhares), razoavelmente rápidos, para compor uma máquina de alto milhares), razoavelmente rápidos, para compor uma máquina de alto
desempenho.desempenho.
Estas máquinas podem ser classificadas em três tipos:Estas máquinas podem ser classificadas em três tipos:
Multiprocessadores vetoriais:Multiprocessadores vetoriais:
possuem um pequeno número de processadores vetoriais de possuem um pequeno número de processadores vetoriais de
alta performance.alta performance.
IntroduçãoIntrodução
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 10
Estas máquinas podem ser classificadas em três tipos:Estas máquinas podem ser classificadas em três tipos:
Sistemas MPP (Massively Parallel Processors):Sistemas MPP (Massively Parallel Processors):
possuem de centenas a milhares de processadores, com possuem de centenas a milhares de processadores, com
memória distribuída ou compartilhada.memória distribuída ou compartilhada.
Rede de estações de trabalho:Rede de estações de trabalho:
máquinas interligadas por redes que podem trabalhar como máquinas interligadas por redes que podem trabalhar como
uma única máquina virtual paralela. uma única máquina virtual paralela.
IntroduçãoIntrodução
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 11
Reduzir tempo total de processamento (wall clock time);Reduzir tempo total de processamento (wall clock time);
Reduzir o custo de processamento:Reduzir o custo de processamento:
execução em paralelo utilizando um grande número de estações execução em paralelo utilizando um grande número de estações
de trabalho pode ser menor (custo) que utilizar um de trabalho pode ser menor (custo) que utilizar um
supercomputador;supercomputador;
Recursos Recursos locaislocais versus versus não locaisnão locais::
Pode-se utilizar arquiteturas e equipamentos de tipos diversos e Pode-se utilizar arquiteturas e equipamentos de tipos diversos e
agregar sempre mais poder de processamento sempre que agregar sempre mais poder de processamento sempre que
necessário;necessário;
ObjetivosObjetivos
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 12
Alguns termos utilizados em processamento paralelo (Elias, 1995):Alguns termos utilizados em processamento paralelo (Elias, 1995):
Tarefas (ou processos): Tarefas (ou processos): programas executados programas executados
concorrentemente, disparados por um programa mestre. São as concorrentemente, disparados por um programa mestre. São as
principais unidades do processamento paralelo em um ambiente principais unidades do processamento paralelo em um ambiente
de computação distribuída; comunicam-se por meio de troca de de computação distribuída; comunicam-se por meio de troca de
mensagens.mensagens.
[Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory [Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop. Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop.
TerminologiaTerminologia
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 13
Alguns termos utilizados em processamento paralelo (Elias, 1995):Alguns termos utilizados em processamento paralelo (Elias, 1995):
Execução seqüencial: Execução seqüencial: execução de um programa em um único execução de um programa em um único
processador, com as instruções sendo processadas uma de cada processador, com as instruções sendo processadas uma de cada
vez.vez.
TerminologiaTerminologia
[Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory [Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop. Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop.
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 14
Alguns termos utilizados em processamento paralelo (Elias, 1995):Alguns termos utilizados em processamento paralelo (Elias, 1995):
Paralelização de código: Paralelização de código: consiste na transformação de um consiste na transformação de um
programa seqüencial em paralelo, com a identificação de porções programa seqüencial em paralelo, com a identificação de porções
de código que podem ser executadas independentemente. Exige de código que podem ser executadas independentemente. Exige
mudanças no código do programa e, caso necessário, no mudanças no código do programa e, caso necessário, no
algoritmo utilizado no programa seqüencial.algoritmo utilizado no programa seqüencial.
TerminologiaTerminologia
[Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory [Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop. Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop.
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 15
Alguns termos utilizados em processamento paralelo (Elias, 1995):Alguns termos utilizados em processamento paralelo (Elias, 1995):
Aceleração (speed-up): Aceleração (speed-up): consiste na comparação entre o tempo consiste na comparação entre o tempo
de execução do programa em um único processador e o tempo de de execução do programa em um único processador e o tempo de
execução utilizando vários processadores. execução utilizando vários processadores.
TerminologiaTerminologia
[Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory [Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop. Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop.
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 16
Alguns termos utilizados em processamento paralelo (Elias, 1995):Alguns termos utilizados em processamento paralelo (Elias, 1995):
Sincronização: Sincronização: coordenação entre processos para a troca de coordenação entre processos para a troca de
informações.informações.
É um fator de decréscimo da eficiência do programa, uma vez É um fator de decréscimo da eficiência do programa, uma vez
que alguns processadores podem ficar inativos, esperando que alguns processadores podem ficar inativos, esperando
pelo término de outros processos.pelo término de outros processos.
[Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory [Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop. Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop.
TerminologiaTerminologia
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 17
Alguns termos utilizados em processamento paralelo (Elias, 1995):Alguns termos utilizados em processamento paralelo (Elias, 1995):
Granularidade: Granularidade: quantidade de processamento realizado por cada quantidade de processamento realizado por cada
processo, em relação à quantidade de comunicação entre processo, em relação à quantidade de comunicação entre
processos.processos.
Muito granular: Muito granular: processos executam poucas instruções e se processos executam poucas instruções e se
comunicar muito.comunicar muito.
Pouco granular: Pouco granular: processos executam muitas instruções, com processos executam muitas instruções, com
pouca troca de informação.pouca troca de informação.
TerminologiaTerminologia
[Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory [Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop. Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop.
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 18
Alguns termos utilizados em processamento paralelo (Elias, 1995):Alguns termos utilizados em processamento paralelo (Elias, 1995):
Um programa com granularidade alta necessita de maior Um programa com granularidade alta necessita de maior
sincronização que um programa com menor granularidade, o que sincronização que um programa com menor granularidade, o que
afeta o tempo de execução do programa.afeta o tempo de execução do programa.
TerminologiaTerminologia
[Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory [Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop. Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop.
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 19
Alguns termos utilizados em processamento paralelo (Elias, 1995):Alguns termos utilizados em processamento paralelo (Elias, 1995):
Escalabilidade: Escalabilidade: um sistema computacional paralelo é dito um sistema computacional paralelo é dito
escalável se a aceleração atingida cresce proporcionalmente ao escalável se a aceleração atingida cresce proporcionalmente ao
número de processadores utilizados.número de processadores utilizados.
TerminologiaTerminologia
[Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory [Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop. Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop.
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 20
Alguns termos utilizados em processamento paralelo (Elias, 1995):Alguns termos utilizados em processamento paralelo (Elias, 1995):
Balanceamento de carga: Balanceamento de carga: consiste na distribuição equilibrada de consiste na distribuição equilibrada de
tarefas entre os processadores, de forma a garantir uma execução tarefas entre os processadores, de forma a garantir uma execução
eficiente do programa paralelo.eficiente do programa paralelo.
TerminologiaTerminologia
[Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory [Elias,95] Elias, D., "Introduction to Parallel Programming Concepts", Workshop on Parallel Programming on the IBM SP, Cornell Theory Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop. Center, 1995. Disponível através da WWW no endereço http://www.tc.cornell.edu/Edu/Workshop.
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 21
Alguns termos utilizados em processamento paralelo (Elias, 1995):Alguns termos utilizados em processamento paralelo (Elias, 1995):
SPMD (Single Program - Multiple Data): SPMD (Single Program - Multiple Data): modelo de modelo de
programação onde todos os processadores executam o mesmo programação onde todos os processadores executam o mesmo
programa sobre diferentes conjuntos de dados. programa sobre diferentes conjuntos de dados.
TerminologiaTerminologia
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 22
Organização de computadores paralelosOrganização de computadores paralelos Existem várias maneiras de se organizar computadores paralelos. Existem várias maneiras de se organizar computadores paralelos.
Classificação de computadores paralelos segundo Ben-Dyke (1993) :Classificação de computadores paralelos segundo Ben-Dyke (1993) :
Hierárquica: Hierárquica: iniciando em um nível mais abstrato, a classificação iniciando em um nível mais abstrato, a classificação
deve ser refinada em subníveis à medida que se diferencie de deve ser refinada em subníveis à medida que se diferencie de
maneira mais detalhada cada arquitetura; maneira mais detalhada cada arquitetura;
Universal: Universal: um computador único, deve ter uma classificação um computador único, deve ter uma classificação
única; única;
BEN-DYKE, A. D., “Architectural taxonomy, A brief review”, University of Birmingham, 1993
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 23
Organização de computadores paralelosOrganização de computadores paralelos Classificação de computadores paralelos segundo Ben-Dyke (1993) :Classificação de computadores paralelos segundo Ben-Dyke (1993) :
Extensível: Extensível: futuras máquinas que surjam, devem ser incluídas futuras máquinas que surjam, devem ser incluídas
sem que sejam necessárias modificações na classificação; sem que sejam necessárias modificações na classificação;
Concisa: Concisa: os nomes que representam cada uma das classes os nomes que representam cada uma das classes
devem ser pequenos para que a classificação seja de uso prático; devem ser pequenos para que a classificação seja de uso prático;
Abrangente: Abrangente: a classificação deve incluir todos os tipos de a classificação deve incluir todos os tipos de
arquiteturas existentesarquiteturas existentes
BEN-DYKE, A. D., “Architectural taxonomy, A brief review”, University of Birmingham, 1993
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 24
Há três modelos básicos de programação multiprocessadaHá três modelos básicos de programação multiprocessada
Tolerância a falhas:Tolerância a falhas:
utilizada em servidores de banco de dados e servidores utilizada em servidores de banco de dados e servidores webweb..
Replicação de dados.Replicação de dados.
Delegação de servidores no caso de paradas.Delegação de servidores no caso de paradas.
O que é programação paralelaO que é programação paralela
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 25
Há três modelos básicos de programação multiprocessadaHá três modelos básicos de programação multiprocessada
Balanceamento de carga:Balanceamento de carga:
Usado principalmente em servidores Usado principalmente em servidores webweb..
Divisão de carga entre o servidor principal com outros Divisão de carga entre o servidor principal com outros
computadores.computadores.
O que é programação paralelaO que é programação paralela
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 26
Os programas que rodam nos 2 primeiros casos não são feitos Os programas que rodam nos 2 primeiros casos não são feitos
especialmente para rodarem em vários computadores ao mesmo especialmente para rodarem em vários computadores ao mesmo
tempo.tempo.
Programação paralela:Programação paralela:
Modelo em que o mesmo programa é carregado e roda Modelo em que o mesmo programa é carregado e roda
simultaneamente em vários computadores.simultaneamente em vários computadores.
O programa construído para rodar especificamente em vários O programa construído para rodar especificamente em vários
computadores e utiliza funções de comunicação entre os computadores e utiliza funções de comunicação entre os
computadores (MPI).computadores (MPI).
O que é programação paralelaO que é programação paralela
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 27
Os programas que rodam nos 2 primeiros casos não são feitos Os programas que rodam nos 2 primeiros casos não são feitos
especialmente para rodarem em vários computadores ao mesmo especialmente para rodarem em vários computadores ao mesmo
tempo.tempo.
Vantagens de algoritmos paralelos: Vantagens de algoritmos paralelos: menor tempo de execução.menor tempo de execução.
O computador possui um número de identificação (O computador possui um número de identificação (idid).).
O que é programação paralelaO que é programação paralela
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 28
Aumento de desempenho:Aumento de desempenho:
Capacidade de memória maiorCapacidade de memória maior
Desempenho:Desempenho:
Aumento do tamanho da palavra e da precisão utilizada Aumento do tamanho da palavra e da precisão utilizada
decorrente da quantidade de processadores que podem ser decorrente da quantidade de processadores que podem ser
utilizadosutilizados
Por que utilizar programação paralelaPor que utilizar programação paralela
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 29
Aumento de desempenho:Aumento de desempenho:
Velocidade:Velocidade:
Mais transistores em menor espaçoMais transistores em menor espaço
Mais vias de comunicaçãoMais vias de comunicação
Limites para esse aumentoLimites para esse aumento
Velocidade de transmissão faz com que módulos tenham que ser Velocidade de transmissão faz com que módulos tenham que ser
colocados relativamente perto um dos outros para não perder colocados relativamente perto um dos outros para não perder
sincronizaçãosincronização
Por que utilizar programação paralelaPor que utilizar programação paralela
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 30
Limites para redução de componentes e aumento de capacidade de Limites para redução de componentes e aumento de capacidade de
um computador;um computador;
Investimento financeiro em supercomputadores;Investimento financeiro em supercomputadores;
Problemas grandes pode ser subdividido e executados em paralelo Problemas grandes pode ser subdividido e executados em paralelo
por mais de um computador;por mais de um computador;
Disponibilidade de processadores (relativamente mais barato).Disponibilidade de processadores (relativamente mais barato).
Por que utilizar programação paralelaPor que utilizar programação paralela
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 31
Aspectos favoráveis a adoção da programação paralelaAspectos favoráveis a adoção da programação paralela
Barreiras ao crescimento da freqüência (clock) dos processadores;Barreiras ao crescimento da freqüência (clock) dos processadores;
Consumo de energia e a conseqüente dissipação térmica;Consumo de energia e a conseqüente dissipação térmica;
Dimensão do processador e seus componentes acessórios;Dimensão do processador e seus componentes acessórios;
Largura de banda no acesso a memória;Largura de banda no acesso a memória;
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 32
Aspectos favoráveis a adoção da programação paralelaAspectos favoráveis a adoção da programação paralela
Paralelismo intrínseco do mundo real;Paralelismo intrínseco do mundo real;
A relação custo-benefício dos processadores de última geração;A relação custo-benefício dos processadores de última geração;
Aplicações extremamente complexas;Aplicações extremamente complexas;
Suporte a tolerância de falhas;Suporte a tolerância de falhas;
Crescimento modular;Crescimento modular;
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 33
Aspectos desfavoráveis a adoção da programação paralelaAspectos desfavoráveis a adoção da programação paralela
Disponibilidade de software aplicativo;Disponibilidade de software aplicativo;
Mercado de equipamentos paralelos ainda é pequeno;Mercado de equipamentos paralelos ainda é pequeno;
Elevado custo de conversão;Elevado custo de conversão;
Ausência de padrões;Ausência de padrões;
Validação (testar exatidão de um software paralelo);Validação (testar exatidão de um software paralelo);
Instabilidade no fornecimento;Instabilidade no fornecimento;
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 34
Aspectos desfavoráveis a adoção da programação paralelaAspectos desfavoráveis a adoção da programação paralela
Padronização;Padronização;
Relação entre a teoria e tecnologia;Relação entre a teoria e tecnologia;
Instabilidade dos fornecedores;Instabilidade dos fornecedores;
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 35
Previsão do tempo;Previsão do tempo;
Modelo de movimentação de corpos celestes;Modelo de movimentação de corpos celestes;
Acelerador de partículas.Acelerador de partículas.
Ex. de aplicações que utilizam programação paralelaEx. de aplicações que utilizam programação paralela
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 36
Os tipos de paralelismos que podem ser aplicados são:Os tipos de paralelismos que podem ser aplicados são:
Paralelismo de dados;Paralelismo de dados;
Paralelismo funcional;Paralelismo funcional;
Paralelismo temporalParalelismo temporal
Tipos de paralelismoTipos de paralelismo
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 37
O volume de dados é dividido em sub-volumes e cada porção é O volume de dados é dividido em sub-volumes e cada porção é
enviada para uma unidade de processamento.enviada para uma unidade de processamento.
A maior limitação é a quantidade de processadores que podem ser A maior limitação é a quantidade de processadores que podem ser
incorporados em uma dada arquitetura bem como a velocidade de incorporados em uma dada arquitetura bem como a velocidade de
comunicação entre os processadores. comunicação entre os processadores.
Cada tarefa executa uma mesma série de cálculos sobre diferentes Cada tarefa executa uma mesma série de cálculos sobre diferentes
dados;dados;
Paralelismo de dadosParalelismo de dados
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 38
Localidade dos dados é parte essencial de um algoritmo paralelo;Localidade dos dados é parte essencial de um algoritmo paralelo;
Exemplos:Exemplos:
Cálculo da média de temperatura em um determinado estado;Cálculo da média de temperatura em um determinado estado;
Procura de pessoas com mais de 65 anos em uma população;Procura de pessoas com mais de 65 anos em uma população;
Jogo de xadrez.Jogo de xadrez.
Paralelismo de dadosParalelismo de dados
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 39
o algoritmo de renderização é dividido em vários passos ou funções.o algoritmo de renderização é dividido em vários passos ou funções.
A cada função corresponderá um processo distinto o qual será A cada função corresponderá um processo distinto o qual será
executado em uma unidade de processamento específica executado em uma unidade de processamento específica
(Correspondência bi-unívoca entre funções e unidades de (Correspondência bi-unívoca entre funções e unidades de
processamento).processamento).
Uma vez terminado o processamento de uma unidade, o resultado é Uma vez terminado o processamento de uma unidade, o resultado é
enviado para a próxima função no enviado para a próxima função no pipelinepipeline..
Paralelismo funcionalParalelismo funcional
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 40
Cada tarefa executa cálculos diferentes para resolver um problemaCada tarefa executa cálculos diferentes para resolver um problema
Tarefas podem ser executadas sobre mesmos dados ou dados Tarefas podem ser executadas sobre mesmos dados ou dados
diferentesdiferentes
Exemplo:Exemplo:
Modelagem de um ecossistema, onde cada programa calcula a Modelagem de um ecossistema, onde cada programa calcula a
população de um determinado grupo que depende dos vizinhospopulação de um determinado grupo que depende dos vizinhos
Paralelismo funcionalParalelismo funcional
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 41
Ocorre no Pipeline, onde a tarefa é subdividida numa seqüência de Ocorre no Pipeline, onde a tarefa é subdividida numa seqüência de
subtarefas cada uma executada por um estágio de hardware subtarefas cada uma executada por um estágio de hardware
específico, que trabalha concorrentemente com os outros estágios do específico, que trabalha concorrentemente com os outros estágios do
pipeline, criando um paralelismo temporal na execução das pipeline, criando um paralelismo temporal na execução das
subtarefas.subtarefas.
E1 E2 En
Relógio
Paralelismo temporalParalelismo temporal
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 42
Paralelismo temporalParalelismo temporal
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 43
Definição:Definição:
É um programa em execução em uma máquina;É um programa em execução em uma máquina;
Cada processo é identificado pelo seu PID (Process Identifier);Cada processo é identificado pelo seu PID (Process Identifier);
ProcessosProcessos
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 44
Execução dos Processos:Execução dos Processos:
Um processador pode executar somente um processo a cada Um processador pode executar somente um processo a cada
instante;instante;
Em um Sistema Operacional multitarefa, processos se alternam Em um Sistema Operacional multitarefa, processos se alternam
no uso do processador – cada processo é executado durante um no uso do processador – cada processo é executado durante um
quantum de tempo;quantum de tempo;
Se houver N processadores, N processos podem ser executados Se houver N processadores, N processos podem ser executados
simultaneamente.simultaneamente.
ProcessosProcessos
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 45
Um computador convencional consiste de um processador Um computador convencional consiste de um processador
executando um programa armazenado na memória;executando um programa armazenado na memória;
Cada lugar da memória possui um endereço que inicia em 0 e vai até Cada lugar da memória possui um endereço que inicia em 0 e vai até
22n n - 1, onde n é o número de bits do endereço.- 1, onde n é o número de bits do endereço.
Memória principalMemória principal
ProcessadorProcessador
Instruções para o processadorInstruções para o processadorDados para ou do processadorDados para ou do processador
Modelo de acesso a memóriaModelo de acesso a memória
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 46
A mesma memória é acessada pelos múltiplos processadores;A mesma memória é acessada pelos múltiplos processadores;
Sincronização entre tarefas é feita por escrita/leitura na/da memória Sincronização entre tarefas é feita por escrita/leitura na/da memória
compartilhada e usuário é responsável por sua especificação;compartilhada e usuário é responsável por sua especificação;
Uma posição de memória não pode ser modificado por uma tarefa Uma posição de memória não pode ser modificado por uma tarefa
enquanto outra o estiver acessando;enquanto outra o estiver acessando;
Comunicação entre tarefas é rápida;Comunicação entre tarefas é rápida;
Escalabilidade limitada pelo número de caminhos entre memória e Escalabilidade limitada pelo número de caminhos entre memória e
processadores .processadores .
Memória compartilhadaMemória compartilhada
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 47
Memória compartilhadaMemória compartilhada
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 48
SMP (Symetric MultiProcessors) utiliza esse modelo;SMP (Symetric MultiProcessors) utiliza esse modelo;
Programação:Programação:
Linguagens de programação paralela:Linguagens de programação paralela:
Construções e instruções paralelas permitem declarações de Construções e instruções paralelas permitem declarações de
variáveis compartilhadas e seções paralelas de código;variáveis compartilhadas e seções paralelas de código;
Compilador responsável pela geração do código final Compilador responsável pela geração do código final
executável.executável.
Memória compartilhadaMemória compartilhada
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 49
SMP (Symetric MultiProcessors) utiliza esse modelo;SMP (Symetric MultiProcessors) utiliza esse modelo;
Programação:Programação:
Threads:Threads:
Seqüências de código escritas em alto nível para Seqüências de código escritas em alto nível para
processadores individuais que podem acessar localidades processadores individuais que podem acessar localidades
compartilhadas .compartilhadas .
Memória compartilhadaMemória compartilhada
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 50
Fator de aceleração (speed-up)Fator de aceleração (speed-up)
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 51
O Speedup é a relação entre o tempo gasto para executar uma O Speedup é a relação entre o tempo gasto para executar uma
tarefa utilizando um único processador se comparado ao tempo tarefa utilizando um único processador se comparado ao tempo
gasto com N processadores, ou seja, Speedup é a mndida do ganho gasto com N processadores, ou seja, Speedup é a mndida do ganho
em tempo de execução da tarefa.em tempo de execução da tarefa.
S = speedupS = speedup
T(N) = tempo gasto para N processadoresT(N) = tempo gasto para N processadores
Fator de aceleração (speed-up)Fator de aceleração (speed-up)
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 52
Fator de aceleração (speed-up)Fator de aceleração (speed-up) Equação conhecida com Lei de AmdahlEquação conhecida com Lei de Amdahl
fnn
ntffttnS
ss
s
)1(1/)1()(
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 53
Fator de aceleração (speed-up)Fator de aceleração (speed-up)
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 54
Eficiência fornece a fração de tempo que os processadores estão Eficiência fornece a fração de tempo que os processadores estão sendo utilizados para processamentosendo utilizados para processamento
%100)(
nnSE
nttEp
s
resprocessado de númeroparalela execução de temposerial execução de tempo
EficiênciaEficiência
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 55
Custo de um processamento é definido como:Custo de um processamento é definido como:
O custo de uma execução seqüencial é simplesmente o tempo de O custo de uma execução seqüencial é simplesmente o tempo de
execução execução ttss
O custoO custo de uma execução paralela é:de uma execução paralela é:
utilizados resprocessado de totalnúmeroexecução de tempoCusto
Etn
nStnt ss
p )(
CustoCusto
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 56
O custo é considerado ótimo para um determinado algoritmo paralelo O custo é considerado ótimo para um determinado algoritmo paralelo
quando o custo da execução paralela é proporcional ao custo da quando o custo da execução paralela é proporcional ao custo da
execução seqüencial;execução seqüencial;
CustoCusto
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 57
Necessária para coordenar troca de informações (mensagens) entre Necessária para coordenar troca de informações (mensagens) entre
tarefas;tarefas;
Pode consumir tempo de processamento, pois um processador pode Pode consumir tempo de processamento, pois um processador pode
ter que ficar esperando o término de tarefas em outros ter que ficar esperando o término de tarefas em outros
processadores;processadores;
Fator de redução da aceleração (speed-up), porque o tempo utilizado Fator de redução da aceleração (speed-up), porque o tempo utilizado
para esperar uma outra tarefa poderia ser utilizado para para esperar uma outra tarefa poderia ser utilizado para
processamento.processamento.
SincronizaçãoSincronização
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 58
Tempo utilizado para coordenar as tarefas paralelas, por exemplo:Tempo utilizado para coordenar as tarefas paralelas, por exemplo:
Tempo para iniciar uma tarefa:Tempo para iniciar uma tarefa:
identificação da tarefa;identificação da tarefa;
procura de um processador para executá-la;procura de um processador para executá-la;
carregamento da tarefa no processador;carregamento da tarefa no processador;
carregamento de dados necessários à execução da tarefa;carregamento de dados necessários à execução da tarefa;
inicialização da tarefa.inicialização da tarefa.
Tempo para terminar uma tarefa;Tempo para terminar uma tarefa;
Sincronização;Sincronização;
Overhead de paralelismoOverhead de paralelismo
Sistemas DistribuídosSistemas DistribuídosIn
trodu
ção
a S
iste
mas
Dis
tribu
ídos
Intro
duçã
o a
Sis
tem
as D
istri
buíd
os
27/04/23 vladimir.professor@gmail.com 59
São Paulo, 2011São Paulo, 2011
Universidade Paulista (UNIP)Universidade Paulista (UNIP)
Programação ParalelaProgramação Paralela
Prof. Msc. Vladimir CameloProf. Msc. Vladimir Camelovladimir.professor@gmail.com
Recommended