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