Sistemas Distribuídos Introdução a Sistemas Distribuídos 11/3/[email protected] São Paulo, 2011 Universidade Paulista (UNIP) Programaçã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 [email protected] 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 [email protected]

mailto:[email protected]

http://www3.unip.br/


trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os




http://4.bp.blogspot.com/_hrCh9RbFTaA/TNCcxr3CkVI/AAAAAAAAADk/r-GXtRdjotM/s1600/Pipelining.jpg


trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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);




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os



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.





trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os



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.





trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os



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.





trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os



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.





trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os



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.





trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os



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.





trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os



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.





trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os



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.





trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os



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.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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).




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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).).




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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).




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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;



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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;



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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;



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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;



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os





trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os





trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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.




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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 .




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


Fator de aceleração (speed-up)Fator de aceleração (speed-up)



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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




trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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()(



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os





trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


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



trodu

ção

a S

iste

mas

Dis

tribu

ídos

Intro

duçã

o a

Sis

tem

as D

istri

buíd

os


São Paulo, 2011São Paulo, 2011

Universidade Paulista (UNIP)Universidade Paulista (UNIP)

Programação ParalelaProgramação Paralela

Prof. Msc. Vladimir CameloProf. Msc. Vladimir [email protected]

mailto:[email protected]


Documents

Sistemas Distribuídos Introdução a Sistemas Distribuídos 11/3/[email protected] São Paulo, 2011 Universidade Paulista (UNIP) Programação