PPA+ +2019 01+ +parte+03

Prévia do material em texto

Programação Paralela
3ª parte
Prof. Jobson Massollar
jobson.silva@uva.br
Programação Paralela2
Modelos de Programação Paralela
➢ Um modelo de programação é uma abstração, ou seja, um modelo
mental que permite ao programador visualizar os detalhes
relacionados à execução da aplicação.
➢ Um modelo de programação facilita a definição de algoritmos e a sua
combinação em programas.
➢ Um modelo de programação paralela abstrai os detalhes relacionados
à arquitetura do computador paralelo.
➢ O consenso em torno da utilidade de um modelo de programação
específico é importante porque isso leva os fabricantes de
computadores paralelos à prover suporte para esse modelo,
facilitando a portabilidade do software para diferentes infraestruturas.
Programação Paralela3
Modelos de Programação Paralela
➢ A implementação efetiva de um modelo de programação paralela
pode tomar a forma de:
 Uma biblioteca de funções invocadas a partir de uma linguagem
sequencial;
 Uma extensão implementada em uma linguagem sequencial, ou;
 Uma nova linguagem de programação.
➢ Não existe o conceito de "melhor modelo", embora existam melhores
implementações de um modelo em detrimento de outras.
➢ Qual modelo escolher?
 Isso depende de uma combinação de escolha pessoal, tipo do
problema a ser resolvido e que modelos estão disponíveis em
determinada infraestrutura computacional.
Programação Paralela4
Modelos de Programação Paralela
➢ Existem diversos modelos de programação paralela comumente
adotados:
1. Modelos relacionados com a interação dos processos:
✓ Memória compartilhada
✓ Passagem de mensagem
2. Modelos relacionados com a decomposição do problema:
✓ Threads
✓ Paralelismo de dados
3. Modelos Híbridos
4. SPMD/MPMD
Programação Paralela5
Modelos de Programação Paralela
➢ É importante frisar que os modelos de programação não são
específicos para uma determinada arquitetura de computador.
➢ Exemplos:
1. É possível implementar um modelo de programação de memória
compartilhada em uma máquina cuja memória está fisicamente
distribuída em diferentes máquinas de uma rede
(multicomputador).
2. É possível implementar um modelo de programação de passagem
de mensagens em um computador com memória compartilhada
(multiprocessador).
Programação Paralela6
Modelo de Memória Compartilhada
➢ Um conjunto de tarefas compartilha um espaço de endereçamento
comum que pode ser lido e escrito assincronamente.
➢ O compartilhamento de dados não depende de nenhum tipo de
comunicação entre as tarefas.
➢ A comunicação entre as tarefas é realizada somente através de leitura
e escrita em áreas de memória compartilhada.
➢ O controle de acesso à memória compartilhada deve ser realizado
pelo programador.
➢ Vários mecanismos, como locks e semáforos, podem ser usados para
controlar o acesso à memória compartilhada, resolver contenções e
prevenir race conditions e deadlocks.
➢ Esse é, provavelmente, o modelo de programação paralela mais
simples.
Programação Paralela7
➢ Exemplo:
Computador
Modelo de Memória Compartilhada
Memória
Tarefa 1
Tarefa 2
Tarefa 3
Tarefa n
...
15
X
Programação Paralela8
Modelo de Memória Compartilhada
➢ Implementação do modelo:
 Em computadores com memória compartilhada
(multiprocessdores), os sistemas operacionais, compiladores e o
próprio hardware oferecem suporte para o compartilhamento da
memória.
 Em computadores com memória distribuída (multicomputadores),
a memória está fisicamente distribuída em uma rede de
computadores, mas hardware e software especiais podem torná-la
compartilhada (memória compartilhada virtual).
• Exemplo: SHMEM (https://en.wikipedia.org/wiki/SHMEM)
Programação Paralela9
Modelo de Passagem de Mensagem
➢ Cada tarefa de um conjunto de tarefas utiliza sua própria memória
local durante o processamento.
➢ O conjunto de tarefas pode estar na mesma máquina física ou
distribuído por diferentes máquinas conectadas em rede.
➢ As tarefas compartilham dados através do envio e recebimento de
mensagens.
➢ O programador define o envio e o recebimento de mensagens.
➢ A transferência de dados normalmente requer algum tipo de
colaboração (uma operação de envio de dados necessita de uma
operação e recebimento de dados).
Programação Paralela10
➢ Exemplo:
Modelo de Passagem de Mensagem
Computador A
Tarefa 1
Tarefa 3
dado
dado
Computador B
Tarefa 2
Tarefa 4
dado
dado
rede
send() recv()
send()recv()
Programação Paralela11
Modelo de Passagem de Mensagem
➢ Implementação do modelo:
 As operações de envio e recebimento de mensagens são
implementadas por bibliotecas de funções.
 Atualmente existe um padrão industrial para a troca de
mensagens denominado MPI (Message Passing Interface).
 Existem implementações do MPI para praticamente todas as
plataformas de computação paralela:
• OpenMPI
• MVAPICH
• MPICH
• IntelMPI
• HP-MPI
Programação Paralela12
Modelo de Threads
➢ Esse modelo pode ser considerado um modelo de memória
compartilhada.
➢ Pra entender o conceito de threads é preciso conhecer, também, o
conceito de processos e como eles se relacionam:
 Quando iniciamos o Microsoft Word® ou o Google Chrome estamos, do
ponto de vista do SO, iniciando um processo.
 Ao iniciar um processo, o SO aloca todos os recursos necessários para
executá-lo (memória do programa, memória de dados, pilha de execução,
descritores de arquivos, permissões, registradores, etc.).
 Além dos recursos, o processo possui uma thread principal, que
representa a linha de execução principal daquele processo.
 Entretanto, um mesmo processo pode ter várias outras threads, que
representam linhas de execução alternativas daquele processo.
 As threads possuem memória local, mas tem acesso à memória global do
processo.
Programação Paralela13
Modelo de Threads
➢ O relacionamento entre threads e processos pode se dar de duas
formas:
Um processo 
com uma 
thread 
(principal).
Um processo 
com múltiplas 
threads.
Programação Paralela14
Modelo de Threads
➢ Exemplo 1:
 Quando iniciamos o Microsoft Word® temos um processo e uma thread
principal que representa a edição do documento.
 Quando acionamos a opção de imprimir um documento, é iniciada uma
segunda thread que fica responsável pela impressão.
 Nesse momento, temos duas threads em execução: uma que trata da
edição e outra que trata da impressão do documento.
 Ao terminar a impressão, essa thread é encerrada, permanecendo em
execução somente a thread principal.
➢ Exemplo 2:
 Quando iniciamos o Google Chrome temos um processo e uma thread
principal, que cuida da interação com o usuário.
 Quando acessamos um site com várias imagens, o browser inicia várias
threads, onde cada uma fica responsável pelo download de uma imagem.
 Ao terminar os downloads, essas threads são encerradas, permanecendo
em execução somente a thread principal.
Programação Paralela15
Modelo de Threads
➢ Alguns exemplos de Sistemas Operacionais, Processos e Threads:
✓ A JVM não é um SO, mas lembre-se que a JVM é uma máquina virtual!
DOS
UNIX
(versões antigas)
JVM
Windows
Programação Paralela16
Modelo de Threads
➢ Características das threads:
✓ Processos são considerados "pesos pesados", enquanto threads
são consideradas "pesos leves".
✓ É mais rápido criar e terminar uma thread do que um processo.
✓ É mais rápido alternar entre threads de um mesmo processo do
que entre processos.
✓ Threads podem se comunicar sem a necessidade de mensagens
ou acesso ao SO, já que compartilham memória e arquivos.
✓ O programador é responsável por definir o que será executado em
cada thread e quantas threads são necessárias.
Programação Paralela17Modelo de Threads
➢ Implementação do modelo:
 As implementações de threads adotam 3 estratégias:
• Comandos específicos adotados por linguagens de programação como
Java e Python.
• Bibliotecas de funções que disponibilizam a execução paralela através
de threads.
• Diretivas de compilação, que indicam trechos de código que devem
ser executados em threads separadas.
 Para as linguagens de programação que não possuem comandos nativos
para tratamento de threads (como C/C++, por exemplo) existem
atualmente dois padrões:
• POSIX Threads (Pthreads): baseado em biblioteca e disponível
somente para C/C++.
• OpenMP: baseado em diretivas de compilação e disponível para
C/C++ e FORTRAN.
Programação Paralela18
Modelo de Paralelismo de Dados
➢ Um conjunto de tarefas que executam operações sobre o mesmo
conjunto de dados.
➢ O conjunto de dados é, tipicamente, organizado como uma estrutura
de dados (vetor, matriz, lista, árvore, etc.).
➢ Cada uma das tarefas do conjunto trabalha com uma porção distinta
da mesma estrutura de dados.
➢ Em arquiteturas de computadores com memória compartilhada
(multiprocessadores), todas as tarefas têm acesso à mesma estrutura
de dados via memória global.
➢ Em arquiteturas de computadores com memória distribuída
(multicomputadores), a estrutura de dados pode ser particionada e
distribuída pelos diversos nós da rede de computadores.
Programação Paralela19
Modelo de Paralelismo de Dados
➢ Exemplo: arquitetura com memória compartilhada
Computador
MemóriaTarefa 1
for i = 1 to 25
a[i] = a[i] * delta
...
a
Tarefa 2
for i = 26 to 50
a[i] = a[i] * delta
Tarefa k
for i = m to n
a[i] = a[i] * delta
Programação Paralela20
Modelo de Paralelismo de Dados
➢ Exemplo: arquitetura com memória distribuída
Computador A
Tarefa
for i = 1 to 25
a[i] = a[i] * delta
Memória
a
Computador B
Tarefa
for i = 26 to 50
a[i] = a[i] * delta
Memória
a
Computador k
Tarefa
for i = m to n
a[i] = a[i] * delta
Memória
a
...
rede
Programação Paralela21
Modelo de Paralelismo de Dados
➢ Implementação do modelo:
 Existem algumas soluções especialmente projetadas para o paralelismo
de dados:
• Unified Parallel C (UPC): extensão do C.
• X10: linguagem de programação projetada pela IBM.
• Chapel: linguagem de programação projetada pela Cray.
• Global Arrays: biblioteca de funções para C e FORTRAN que trabalha
com vetores distribuídos.
Programação Paralela22
Modelos Híbridos
➢ Quando combinamos dois ou mais dos modelos vistos anteriormente
temos exemplos de modelos híbridos.
➢ Exemplo 1: é possível obter o paralelismo de dados combinando os
modelos vistos anteriormente.
 Uso de threads que acessam estruturas de dados alocadas em uma
memória compartilhada.
 Uso de MPI para distribuir porções de uma estrutura de dados pelos nós
de uma arquitetura de memória distribuída.
Programação Paralela23
Modelos Híbridos
➢ Exemplo 2: atualmente um modelo híbrido bastante comum combina
MPI com threads.
 Os processos executados em cada nó da rede se comunicam através da
MPI.
 Cada processo dispara diversas threads, que podem compartilhar a
memória do nó, se necessário.
rede
Memória
CPU CPU
CPU CPU
CPU CPU
Memória
CPU CPU
CPU CPU
Memória
CPU CPU
Memória
CPU CPU
CPU CPU
OpenMPOpenMP
OpenMP OpenMP
MPI
MPIMPI
MPI
Programação Paralela24
SPMD/MPMD
➢ Quando são executadas múltiplas tarefas que se comunicam por
mensagens, é possível fazer uma subcategorização baseada na
quantidade de diferentes programas que cooperam na execução
paralela:
 SPMD (Single Program Multiple Data): Programa único com
Múltiplos dados.
 MPMD (Multiple Program Multiple Data): Múltiplos programas com
Múltiplos dados.
Atenção: não confundir SPMD/MPMD com SIMD/MIMD!
Programação Paralela25
SPMD
➢ Programa Único:
 O mesmo programa é executado em diferentes nós da arquitetura
distribuída.
 Apesar de ser o mesmo programa, cada um dos processos pode executar
porções diferentes do código dependendo do processador no qual foi
alocado.
➢ Múltiplos Dados:
 Cada um dos processos trabalha com dados distintos.
 Os dados manipulados por cada processo podem ser provenientes da
mesma estrutura de dados ou não.
➢ O SPMD com passagem de mensagens é provavelmente o modelo
mais comumente usado em multicomputadores.
Programação Paralela26
SPMD
➢ Exemplo 1: soma dos elementos de dois vetores. Cada processador se
encarrega de soma uma porção do vetor.
int main() {
int a[], b[], c[];
carregar_vetor(a, "a.txt");
carregar_vetor(b, "b.txt");
if (ID == 0) {
somar(a, b, c, 0, 1700);
receive(1, c);
receive(2, c);
salvar_vetor(c, "c.txt");
}
else if (ID == 1) {
somar(a, b, c, 1701, 3400);
send(0, c, 1701, 3400);
}
else {
somar(a, b, c, 3401, 4999);
send(0, c, 3401, 4999);
}
}
Programação Paralela27
SPMD
➢ Exemplo 1: soma dos elementos de dois vetores. Cada processador se
encarrega de soma uma porção do vetor.
int main() {
int a[], b[], c[];
carregar_vetor(a, "a.txt");
carregar_vetor(b, "b.txt");
if (ID == 0) {
somar(a, b, c, 0, 1700);
receive(1, c);
receive(2, c);
salvar_vetor(c, "c.txt");
}
else if (ID == 1) {
somar(a, b, c, 1701, 3400);
send(0, c, 1701, 3400);
}
else {
somar(a, b, c, 3401, 4999);
send(0, c, 3401, 4999);
}
}
Processador 0
Processador 1
Processador 2
Programação Paralela28
SPMD
➢ Exemplo 2: multiplicação de 4 matrizes quadradas n x n.
int main() {
int a[n][n], b[n][n], r[n][n];
if (ID == 0) {
receive(1, a);
receive(2, b);
multiplicar(a, b, r);
salvar_vetor(r, n, "r.txt");
}
else if (ID == 1) {
carregar_matriz(a, "a.txt");
carregar_matriz(b, "b.txt");
multiplicar(a, b, r);
send(0, r, n);
}
else {
carregar_matriz(a, "c.txt");
carregar_matriz(b, "d.txt");
multiplicar(a, b, r);
send(0, r, n);
}
}
Programação Paralela29
SPMD
➢ Exemplo 2: multiplicação de 4 matrizes quadradas n x n.
int main() {
int a[n][n], b[n][n], r[n][n];
if (ID == 0) {
receive(1, a);
receive(2, b);
multiplicar(a, b, r);
salvar_vetor(r, n, "r.txt");
}
else if (ID == 1) {
carregar_matriz(a, "a.txt");
carregar_matriz(b, "b.txt");
multiplicar(a, b, r);
send(0, r, n);
}
else {
carregar_matriz(a, "c.txt");
carregar_matriz(b, "d.txt");
multiplicar(a, b, r);
send(0, r, n);
}
}
Processador 0
Processador 1
Processador 2
Programação Paralela30
MPMD
➢ Múltiplos Programas:
 Diferentes programa são executados em diferentes nós da arquitetura
distribuída.
➢ Múltiplos Dados:
 Cada um dos processos trabalha com dados distintos.
 Os dados manipulados por cada processo podem ser provenientes da
mesma estrutura de dados ou não.
➢ O MPMD é bem menos comum do que o SPMD e seu uso é mais
adequado para problemas que adotam a estratégia de decomposição
funcional (será vista posteriormente).