MPI: Arquiteturas Paralelas e Distribuídas

Prévia do material em texto

Arquitetura Paralelas
e
Distribuídas
Professor: Leonardo Lima
Email: leonardo.lima1@anhanguera.com
REVISÃO
Introdução
• O MPI é um padrão para desenvolvimento de aplicações
distribuídas
• Disponível na forma de bibliotecas para linguagens C, C++, Fortran
e pode ser estendida em Java e C#.NET
• SPMD – Single Program Multiple Data – todos os processos
executam o MESMO programa
• Síntese de diversos sistemas anteriores
3
Arquiteturas Paralelas e Distribuídas
Objetivos
• Eficiência na comunicação
• Ambientes para desenvolvimento e execução para computadores,
clusters e redes heterogêneas paralelas
• Fácil aprendizado para atuais programadores de aplicações
distribuídas (interface parecida com a do PVM)
4
Arquiteturas Paralelas e Distribuídas
Características
• Supõe que a subcamada de comunicação é confiável
• Garante ordem de entrega das mensagens
• Trabalha com o conceito de COMUNICADORES, que definem o
universo de processos envolvidos em uma operação de
comunicação
• Cada processo ganha uma identificação numérica (rank)
5
Arquiteturas Paralelas e Distribuídas
Comandos de inicialização e finalização
• MPI_Init: Inicializa o ambiente de execução
• MPI_Comm_rank: Determina o rank (identificação) do processo no
comunicador
• MPI_Comm_size: Determina o número de processos no
comunicador
• MPI_Finalize: Termina o ambiente de execução
6
Arquiteturas Paralelas e Distribuídas
MPI_Send
int MPI_Send(void* message, int count, MPI_Datatype datatype, int dest, int tag, 
MPI_Comm comm)
• message: Endereço inicial da informação a ser enviada
• count: Número de elementos do tipo especificado a enviar
• datatype: MPI_CHAR, MPI_INT, MPI_FLOAT, MPI_BYTE, MPI_LONG,
MPI_UNSIGNED_CHAR, etc
• dest: rank do processo destino
• tag: Identificador do tipo da mensagem
• comm: Especifica o contexto da comunicação e os processos participantes do
grupo. O padrão é MPI_COMM_WORLD
7
Arquiteturas Paralelas e Distribuídas
MPI_Recv
int MPI_Recv(void* message, int count, MPI_Datatype datatype, int source, int
tag, MPI_Comm comm , MPI_Status* status)
• message: Endereço inicial do buffer de recepção
• count: Número máximo de elementos a serem recebidos
• datatype: MPI_CHAR, MPI_INT, MPI_FLOAT, MPI_BYTE, MPI_LONG,
MPI_UNSIGNED_CHAR, etc.
• source: rank do processo origem ( * = MPI_ANY_SOURCE)
• tag: identificador do tipo da mensagem a receber (* = MPI_ANY_TAG)
• comm: comunicador
• status: Estrutura com três capôs: MPI_SOURCE_TAG, MPI_TAG, MPI_ERROR
8
Arquiteturas Paralelas e Distribuídas
MPI_Irecv
• Menos utilizada
• Parâmetros iguais ao bloqueante, acrescido de uma estrutura
(request) que armazena informações que possibilitam o bloqueio
posterior do processo usando a função MPI_Wait(&request,
&status)
9
Arquiteturas Paralelas e Distribuídas
Comunicação Coletiva
• mais restritivas que as comunicações ponto a ponto:
– quantidade de dados enviados deve casar exatamente com a
quantidade de dados especificada pelo receptor
– Apenas a versão bloqueante das funções está disponível
– O argumento tag não existe
• Todos os processos participantes da comunicação coletiva chamam
a mesma função com argumentos compatíveis
10
Arquiteturas Paralelas e Distribuídas
Algumas Funções para Comunicação Coletiva
• MPI_Barrier: Bloqueia o processo até que todos os processos
associados ao comunicador chamem essa função
11
Arquiteturas Paralelas e Distribuídas
Algumas Funções para Comunicação Coletiva
• MPI_Bcast: Faz a difusão de uma mensagem do processo raiz para
todos os processos associados ao comunicador
12
Arquiteturas Paralelas e Distribuídas
Algumas Funções para Comunicação Coletiva
• MPI_Reduce: Combina todos os elementos presentes no buffer de cada
processo do grupo usando a operação definida como parâmetro e coloca o valor
resultante no buffer do processo especificado. O exemplo abaixo soma todas as
variáveis “x” armazenando o total na variável “tot” do processo 2.
13
Arquiteturas Paralelas e Distribuídas
Exceto para todos os outros !!!
14
Arquiteturas Paralelas e Distribuídas
MPI é a pior maneira de Programar ???
15
Arquiteturas Paralelas e Distribuídas
Conclusão
• Proporciona aumentos reais de desempenho
• Proposto para inclusão na norma MPI
• Atualmente disponível em LibNBC
- Implementação portátil usando MPI 1
16
Arquiteturas Paralelas e Distribuídas
Conclusão
• Aplica-se otimizações de tempo de execução agressivos
- Mapas de operações de alto nível, mais específicas, para operação MPI
ativa
- Nunca serializes tipos primitivos ou estruturas (tipos de dados ou
construções derivadas quando necessário).
• Desempenho micro referência (NetPipe):
- Insignificante mais cabe (em relação ao C - A memória compartilhada o
TCP pode ser mais lento no C).
17
Arquiteturas Paralelas e Distribuídas
Conclusão
Ainda não esta Morto !!!
TRABALHO P2 – EM GRUPO – ENTREGA 25/05
VALENDO PONTO !!!!
DESENVOLVAM UM EXEMPLO USANDO ALGUMA BIBLIOTECA
COM OS RECURSOS DO MPI, NO VISUAL STUDIO (.NET) OU
EM ECLIPSE/NETBEANS (JAVA)
MPI FOR JAVA
HTTP://WWW.NEW-NPAC.ORG/USERS/FOX/DOCUMENTS/MPIFORJAVAMARCH00/CPEMPI.PDF
HTTPS://BLOGS.CISCO.COM/PERFORMANCE/JAVA-BINDINGS-FOR-OPEN-MPI
MICROSOFT MPI
HTTPS://MSDN.MICROSOFT.COM/EN-US/LIBRARY/BB524831(V=VS.85).ASPX
HTTP://RESEARCH.IHOST.COM/PPOPP08/PRESENTATIONS/GREGOR-MPI-NET.PDF
HTTPS://WWW.CODEPROJECT.COM/ARTICLES/25252/IMPLEMENTING-PARALLEL-PROGRAMMING-USING-MPI-AND-C
Arquiteturas Paralelas e Distribuídas
http://www.new-npac.org/users/fox/documents/mpiforjavamarch00/cpempi.pdf
https://blogs.cisco.com/performance/java-bindings-for-open-mpi
https://msdn.microsoft.com/en-us/library/bb524831(v=vs.85).aspx
http://research.ihost.com/ppopp08/presentations/gregor-mpi-net.pdf
https://www.codeproject.com/Articles/25252/Implementing-parallel-programming-using-MPI-and-C
AULA DE HOJE
Arquiteturas Paralelas e Distribuídas
Arquiteturas Paralelas e Distribuídas
Arquiteturas Paralelas e Distribuídas
Arquiteturas Paralelas e Distribuídas
NA TECNOLOGIA DA INFORMAÇÃO
Arquiteturas Paralelas e Distribuídas
NA TECNOLOGIA DA INFORMAÇÃO
Arquiteturas Paralelas e Distribuídas
25
Arquiteturas Paralelas e Distribuídas
PIPELINE - Introdução
• Pipeline é uma técnica de implementação de processadores que permite a
sobreposição temporal das diversas fases de execução das instruções.
• Aumenta o número de instruções executadas simultaneamente e a taxa de
instruções iniciadas e terminadas por unidade de tempo
• O pipeline não reduz o tempo gasto para completar uma instrução
individualmente.
26
Arquiteturas Paralelas e Distribuídas
PIPELINE – Exemplo
• Vamos supor uma lavanderia, em que cada etapa possa ser realizada em 15
minutos:
1. Colocar a roupa na maquina de lavar
2. Depois de lavada, colocá-la na máquina de secar roupa
3. Depois de seca, passar a ferro
4. Depois de passada, arrumá-la no armário
27
Arquiteturas Paralelas e Distribuídas
PIPELINE – Exemplo Sem Pipeline
28
Arquiteturas Paralelas e Distribuídas
PIPELINE – Exemplo Com Pipeline
29
Arquiteturas Paralelas e Distribuídas
PIPELINE – Exemplo
• Supondo-se que cada uma destas etapas leve 15 minutos para ser realizada, a
lavagem de um cesto de roupas continuará levando 1 horas para ser realizada.
• Entretanto, podemos iniciar a lavagem de um cesto de roupas a cada 15 minutos,
até que tenhamos 4 cestos sendo lavados simultaneamente, um em cada etapa
do “pipeline”.
30
Arquiteturas Paralelas e Distribuídas
PIPELINE 
• Não melhora a latência de cada tarefa individualmente.
• Melhora o throughput (taxa de transferência) de todo o trabalho.
• Várias tarefas executam simultaneamente usando recursos diferentes.
• Speedup (aceleração) potencial = número de estágios do pipeline.
31
Arquiteturas Paralelas e Distribuídas
Exemplo de Pipeline de Instruções
Divisão da execução da instrução em 5 estágios:
• Busca da instrução na memória (B)
• Leitura dos registradores e decodificação da instrução (D)
• Execução da instrução(E)
• Acesso a um operando na memória (M)
• Escrita de um resultado em um registrador (W)
32
Arquiteturas Paralelas e Distribuídas
Exemplo de Instruções
33
Arquiteturas Paralelas e Distribuídas
Exemplo de Instruções com Pipeline
34
Arquiteturas Paralelas e Distribuídas
Sem Pipeline
35
Arquiteturas Paralelas e Distribuídas
Com Pipeline
36
Arquiteturas Paralelas e Distribuídas
Características dos Pipelines de Instruções
• O tempo do ciclo do relógio do processador deve ser igual ou maior que o tempo
de execução do estágio mais lento do pipeline.
• Deve-se procurar dividir a execução da instrução em estágios com o mesmo
tempo.
• O pipeline deve ser mantido sempre “cheio” para que o desempenho máximo
seja alcançado.
• De um modo geral, com o uso do pipeline, cada instrução ainda leva o mesmo
tempo para ser executada.
• Algumas instruções contudo podem ter o seu tempo de execução aumentado,
pois atravessam estágios em que não realizam nenhuma operação útil.
37
Arquiteturas Paralelas e Distribuídas
Características dos Pipelines de Instruções
• O tempo gasto no processamento de M instruções em um pipeline com K
estágios e ciclo de máquina igual a t é dado por:
T = [K + (M – 1)] * t
• Se M >> K (caso comum), T é aproximadamente M * t
38
Arquiteturas Paralelas e Distribuídas
Características dos Pipelines de Instruções
• Se um programa tem 10.001 instruções. Quanto tempo leva para ser executado
em um processador com pipeline de 5 estágios e relógio de 100ns?
T = [K + (M – 1)] * t
T = (5 + (10.000)) * 100x10-9 = ~1ms (com pipeline)
T = M * t
T = 500ns * 10.000 = ~5ms (sem pipeline)
39
Arquiteturas Paralelas e Distribuídas
Problemas no uso de Pipelines
• Estágios pode ter tempos de execução diferentes:
– Solução 1: Implementar esses estágios como um pipeline onde cada sub-
estágio possui tempo de execução semelhante aos demais estágios do
pipeline principal.
– Solução 2: Replicar esse estágio, colocando replicas em paralelo no
estágio principal. O número de replicas é dado pela razão entre o tempo do
estágio mais lento e os demais.
40
Arquiteturas Paralelas e Distribuídas
Problemas no uso de Pipelines
• O sistema de memória é incapaz de manter o fluxo de instruções no pipeline
– O uso de memória cache com alta taxa de acertos e tempo de acesso
compatível com o tempo de ciclo do pipeline.
• Dependências ou conflitos (“Hazards”) (“Perigos”)
– Conflitos estruturais (
Pode haver acessos simultâneos à memória feitos por 2 ou mais
estágios.
– Dependência de dados
As instruções dependem de resultados de instruções anteriores,
ainda não completadas.
– Dependência de controle
A próxima instrução não está no endereço subsequente ao da
instrução anterior
• Tratamento de execuções
41
Arquiteturas Paralelas e Distribuídas
Conflitos Estruturais no uso de Pipelines
• Acesso concorrente à memória
– Uso de memórias multiportas ou com múltiplos bancos com acessos
independentes
• Leitura de instrução de leitura / escrita de dados simultâneos à memória
– Uso de arquitetura “Harvard” com cache de dados e instruções separados
• Acesso simultâneo ao banco de registradores
– Uso de banco de registradores com múltiplas portas.
• Uso simultâneo de uma mesma unidade funcional
– Replicação da unidade funcional ou implementação “pipelined” dessa
unidade.
42
Arquiteturas Paralelas e Distribuídas
Conflitos Estruturais no uso de Pipelines
• Problema: acesso simultâneo à memória por 2 ou mais estágios
• Soluções
– Caches separados de dados e instruções
– Memória com múltiplos bancos com acessos independentes.
43
Arquiteturas Paralelas e Distribuídas
Conflitos Por Dados no uso de Pipelines
• Problema: uma instrução faz uso de um operando que vai ser produzido por uma
outra instrução que ainda está no pipeline.
• A execução da instrução seguinte depende de operando calculado pela instrução
anterior
• Tipos de dependência de dados:
– Dependência verdadeira
– Dependência falsa
 Antidependência
 Dependência de saída
44
Arquiteturas Paralelas e Distribuídas
Dependência de dados no uso de Pipelines
• Dependência verdadeira (direta):
– O pipeline precisa ser parado durante certo número de ciclos (interlock)
– Colocação de instruções de “nop” ou escalonamento adequado das
instruções pelo compilador
– O adiamento dos dados pode resolver em alguns casos
• Dependência falsa
– Não é um problema em pipelines onde a ordem de execução das
instruções é mantida
Arquiteturas Paralelas e Distribuídas
MUITO OBRIGADO !!!
EXERCÍCIOS
Arquiteturas Paralelas e Distribuídas
47
Arquiteturas Paralelas e Distribuídas
Exercícios - Pipelines
1) “Um hazard de pipeline ocorre quando o pipeline, ou alguma parte dele, precisa
parar porque as condições não permitem a execução contínua. A parada
do pipeline é conhecida como bolha de pipeline.” Existem três tipos de hazards;
assinale-os.
A - Recurso; dados; controle.
B - Recurso; endereço; dados.
C - Desvio; Recurso; endereço.
D - Endereço; instrução; recurso.
48
Arquiteturas Paralelas e Distribuídas
Exercícios - Pipelines
2) Numa discussão técnica sobre a utilidade e funcionalidade do pipeline foram
citadas as seguintes afirmativas:
( ) o número de estágios do pipeline é determinado pelo clock do processador.
( ) o pipeline reduz para um único ciclo, a execução das instruções de três ciclos.
( ) embora o pipeline melhore o tempo de latência ele diminui o throughput
global.
Considerando as afirmações acima, dê valores de Verdadeiro (V) ou falso (F) e
assinale a alternativa que apresenta a sequência correta de cima para baixo.
A - V V F
B - V V F
C - V F V
D - F F V
E - F F F
49
Arquiteturas Paralelas e Distribuídas
Exercícios - Pipelines
3) Com base na organização e arquitetura de computadores, analise as afirmativas
abaixo e assinale a alternativa CORRETA.
I. O conceito de pipeline consiste em dividir a execução da instrução em várias
partes, sendo cada uma delas manipulada por unidades dedicadas do hardware que
trabalham em paralelo.
II. Os compiladores são programas que recebem como entrada arquivos-texto
contendo módulos escritos em linguagem de alto nível e geram como saída
arquivos-objeto correspondentes a cada módulo.
III. O clock é um circuito oscilador que tem a função de sincronizar e determinar a
medida de velocidade de transferência de dados no computador.
A - Apenas a afirmativa I está correta.
B - Apenas as afirmativas I e II estão corretas.
C - Apenas as afirmativas II e III estão corretas.
D - Todas as afirmativas estão corretas.
50
Arquiteturas Paralelas e Distribuídas
Exercícios - Pipelines
4) Diversas arquiteturas modernas de computadores, como as do tipo IBM-PC,
apresentam processadores que implementam o conceito de pipeline. Esse conceito
está relacionado com:
A - a apresentação de informações visuais com maior realismo.
B - a percepção, por parte do usuário, de memória da máquina acima da memória
realmente existente.
C - a segurança no acesso a informações em disco
D - o número de portas de Entrada e Saída destinadas à comunicação com
equipamentos periféricos.
E - o paralelismo na execução de instruções de máquina
51
Arquiteturas Paralelas e Distribuídas
Exercícios - Pipelines
5) No que se refere às tecnologias e aos processos envolvidos na construção de
computadores, julgue o próximo item.
O conflito estrutural ocorre quando o hardware não suporta a combinação de
instruções que o pipeline tenta executar no mesmo ciclo de clock.
( ) CERTO ( ) ERRADO
PÓS – AULA
PROCUREM SOBRE ARQUITETURAS:
- RISC
- CISC
RESPONDAM A PERGUNTA:
UM COMPUTADOR BASEADO EM UMA UNIDADE CENTRAL DE
PROCESSAMENTO DO TIPO RISC FAZ USO DO PIPELINE
Arquiteturas Paralelas e Distribuídas
53
Arquiteturas Paralelas e Distribuídas
Arquitetura RISC e CISC
O projeto do Conjunto de Instruções inicia com a escolha de uma
entre duas abordagens, a abordagem RISC e a CISC.
O termo RISC é a abreviação de Reduced Instruction Set Computer,
ou Computador de Conjuntode Instruções Reduzido e CISC vem de Complex
Instruction Set Computer, ou Computador de Conjunto de Instruções
Complexo.
Um computador RISC parte do pressuposto de que um conjunto
simples de instruções vai resultar numa Unidade de Controle simples, barata
e rápida.
Já os computadores CISC visam criar arquiteturas complexas o
bastante a ponto de facilitar a construção dos compiladores, assim,
programas complexos são compilados em programas de máquina mais
curtos. Com programas mais curtos, os computadores CISC precisariam
acessar menos a memória para buscar instruções e seriammais rápidos.
https://www.youtube.com/watch?v=m1uKe6GdjOE
https://www.youtube.com/watch?v=m1uKe6GdjOE
54
Arquiteturas Paralelas e Distribuídas
Arquitetura RISC e CISC
A Tabela abaixo resume as principais características dos computadores RISC em
comparação com os CISC. Os processadores RISC geralmente adotam arquiteturas
mais simples e que acessam menos a memória, em favor do acesso aos
registradores. A arquitetura Registrador-Registrador é mais adotada, enquanto que
os computadores CISC utilizam arquiteturas Registrador-Memória.
55
Arquiteturas Paralelas e Distribuídas
Arquitetura RISC e CISC
Como as arquiteturas RISC visam Unidades de Controle mais
simples, rápidas e baratas, elas geralmente optam por instruções
mais simples possível, com pouca variedade e com poucos
endereços.
A pouca variedade dos tipos de instrução e dos modos de
endereçamento, além de demandar uma Unidade de Controle mais
simples, também traz outro importante benefício, que é
a previsibilidade.
Como as intrusões variam pouco de uma para outra, é mais
fácil para a Unidade de Controle prever quantos ciclos serão
necessários para executa-las.
Esta previsibilidade traz benefícios diretos para o ganho de
desempenho com o Pipeline. Ao saber quantos ciclos serão
necessários para executar um estágio de uma instrução, a Unidade
de Controle saberá exatamente quando será possível iniciar o
estágio de uma próxima instrução.
56
Arquiteturas Paralelas e Distribuídas
Arquitetura RISC e CISC
Já as arquiteturas CISC investem em Unidades de Controle
poderosas e capazes de executar tarefas complexas como a
Execução Fora de Ordem e a Execução Superescalar.
Na execução Fora de Ordem, a Unidade de Controle analisa
uma sequência de instruções ao mesmo tempo. Muitas vezes há
dependências entre uma instrução e a seguinte, impossibilitando
que elas sejam executadas em Pipeline.
Assim, a Unidade de Controle busca outras instruções para
serem executadas que não são as próximas da sequência e que não
sejam dependentes das instruções atualmente executadas.
Isso faz com que um programa não seja executado na
mesma ordem em que foi compilado.
A Execução Superescalar é a organização do processador em
diversas unidades de execução, como Unidades de Pontos
Flutuante e Unidades de Inteiros.
57
Arquiteturas Paralelas e Distribuídas
Arquitetura RISC e CISC
Essas unidades trabalham simultaneamente.
Enquanto uma instrução é executada por uma das
unidades de inteiros, outra pode ser executada por uma
das unidades de Pontos Flutuantes. Com a execução
Fora de Ordem junto com a Superescalar, instruções que
não estão na sequência definida podem ser executadas
para evitar que as unidades de execução fiquem
ociosas.
É importante ressaltar que a execução fora de ordem 
não afeta o resultado da aplicação pois foram 
projetadas para respeitar as dependências entre os 
resultados das operações.
58
Arquiteturas Paralelas e Distribuídas
Arquitetura RISC e CISC
Estas características de complexidade tornam os
estágios de Pipeline dos processadores CISC mais longos, em
torno de 20 a 30 estágios. Isto porque estas abordagens de
aceleração de execução devem ser adicionadas no processo de
execução. Já os processadores RISC trabalham com estágios
mais curtos, em torno de 4 a 10 estágios.
Os processadores CISC também utilizam mais memória
principal e Cache, enquanto que os processadores RISC
utilizam mais registradores. Isso porque os processadores CISC
trabalham com um maior volume de instruções e dados
simultaneamente. Esses dados não poderiam ser armazenados
em registradores, devido à sua elevada quantidade e são,
geralmente, armazenados em memória Cache. Enquanto que
os processadores RISC trabalham com menos instruções e
dados por vez, o que possibilita a utilização predominante de
registradores.
59
Arquiteturas Paralelas e Distribuídas
Arquitetura RISC e CISC – Qual a melhor Abordagem
Sempre que este assunto é apresentado aos alunos,
surge a pergunta crucial sobre qual é a melhor abordagem, a
RISC ou a CISC? Esta é uma pergunta difícil e sem resposta
definitiva. A melhor resposta que acho é de que depende do
uso que se quer fazer do processador.
Processadores RISC geralmente resultam em projetos
menores, mais baratos e que consumem menos energia. Isso
torna-os muito interessante para dispositivos móveis e
computadores portáteis mais simples. Já os processadores
CISC trabalham com clock muito elevado, são mais caros e
mais poderosos no que diz respeito a desempenho.
Entretanto, eles são maiores e consomem mais energia, o que
os torna mais indicados para computadores de mesa e
notebooks mais poderosos, além de servidores e
computadores profissionais.
60
Arquiteturas Paralelas e Distribuídas
Arquitetura RISC e CISC – Qual a melhor Abordagem
Os processadores CISC iniciaram com processadores
mais simples e depois foram incorporando mais
funcionalidades. Os fabricantes, como a Intel e a AMD,
precisavam sempre criar novos projetos mas mantendo a
compatibilidade com as gerações anteriores. Ou seja, o
Conjunto de Instruções executado pelo 486 precisa também
ser executado pelo Pentium para os programas continuassem
compatíveis. O Pentium IV precisou se manter compatível ao
Pentium e o Duo Core é compatível com o Pentium IV. Isso
tornou o projeto dos processadores da Intel e AMD muito
complexos, mas não pouco eficientes. Os computadores
líderes mundiais em competições de desempenho
computacional utilizam processadores CISC.
61
Arquiteturas Paralelas e Distribuídas
Arquitetura RISC e CISC – Qual a melhor Abordagem
Já o foco dos processadores RISC está na simplicidade e 
previsibilidade. Além do benefício da previsibilidade do tempo 
de execução ao Pipeline, ele também é muito interessante 
para aplicações industriais. Algumas dessas aplicações são 
chamadas de Aplicações de Tempo Real. Essas aplicações 
possuem como seu requisito principal o tempo para realizar as 
tarefas. Assim, o Sistema Operacional precisa saber com 
quantos milissegundos um programa será executado. Isso só é 
possível com processadores RISC, com poucos estágios de 
Pipeline, poucos tipos de instrução, execução em ordem etc. 
Mesmo que os processadores RISC sejam mais lentos do que 
os CISC, eles são mais utilizados nessas aplicações críticas e de 
tempo real, como aplicações industriais, de automação e 
robótica.