Algoritmos Paralelos
1
Demanda por velocidade computacional



Demanda contínua por maior rapidez
computacional das máquinas que as
atualmente disponíveis.
As áreas que exigem maior rapidez
computacional incluem modelagem numérica
e simulação de problemas de engenharia.
Computação dever ser completada em um
tempo “razoável”.
2
Problemas desafiadores



Um problema desafiador é aquele que não
pode ser resolvido em um tempo razoável
com os computadores atuais.
Claro, um tempo de execução de 5 anos
nunca é razoável.
Exemplos



Modelar grandes estruturas de DNA
Previsão de tempo
Modelar movimentos de corpos astronômicos.
3
Previsão do Tempo
Atmosfera é modelada dividindo-se em células 3-d.
 Cálculos em cada célula é repetida várias vezes
para modelar a passagem do tempo.
 Exemplo
A atmosfera inteira é dividida em partes de
1 km x 1km x 1 km para uma altura de 10 km (10
células) - cerca de 5 x 108 células.
Suponha que cada cálculo requer 200 flops. Em um
passo são necessários 1011 flops.

4
Movimento de Corpos Celestes




Cada corpo é atraído por outro pela força
gravitacional.
O movimento de cada corpo é previsto
através do cálculo da força total em cada
corpo.
Com N corpos, N-1 forças calculadas em
cada corpo, ou aprox. N2 cálculos.
Após determinar uma posição dos corpos,
repetir os cálculos.
5
Supercomputador



BlueGene
Está localizado na cidade de Livermore(USA) e tem
a incrível velocidade de processamento de
aproximadamente 280,6 Teraflops.
são 131.072 processadores, 24 Terabytes de
memória. Ele foi desenvolvido para simular toda e
qualquer modificação terrestre: oceanos, atmosfera,
tudo em conjunto conseguindo prever terremotos
com até 180 dias de antecedência
6
Computação Paralela



Uma das estratégias que podem ser
adotadas para se aumentar o desempenho
de uma aplicação computacional, é utilizar
vários processos operando sobre um mesmo
problema.
Neste caso, o problema é dividido em partes
e cada processador "cuida" de uma (ou mais)
dessas partes
A programação dessa forma é dita
programação paralela.
7
Computação Paralela


Usar mais de um computador, ou um
computador com mais de um processador,
para resolver um problema.
Motivos:



Computação mais rápida - idéia simples - n
computadores operando simultaneamente produz
o resultado n vezes mais rápido –
Não é sempre n vezes mais rápido.
Problemas: Tolerância a falhas, mais memória
disponível, ...
8
Tipos de Computadores Paralelos

Programação paralela requer uma plataforma
de computação, o qual pode ser:



Ou um computador com múltiplos processadores
Ou múltiplos processadores interconectados
Vamos analisar os detalhes das
organizações possíveis de computadores
paralelos.
9
Classificação de Flynn

Em 1966, M. J. Flynn propôs uma
classificação dos sistemas computacionais
baseados na relação entre o fluxo de
instruções e o fluxo de dados.
10
Classificação de Flynn
11
Classificação de Flynn: SISD

SISD - Single Instruction Stream - Single
Data Stream


Em um computador monoprocessado, um
programa é representado por uma sequência
única de instruções.
A cada instante de tempo, uma única instrução
opera sobre um único conjunto de dados
12
Classificação de Flynn: SIMD

SIMD - Single Instruction Stream - Multiple
Data Stream


Cada processador executa a mesma instrução,
ao mesmo tempo, sobre um conjunto distinto de
dados.
Há aplicações que requerem este modelo de
operação, como por exemplo, simuladores de
sistemas moleculares e processamento de
imagens.
13
Modelo SIMD
14
Classificação de Flynn: MISD

MISD - Multiple Instruction Stream - Single
Data Stream

Não existe, na prática, um computador com esta
classificação. Alguns autores incluem neste grupo
arquiteturas pipeline.
15
Classificação de Flynn: MIMD

MIMD - Multiple Instruction Stream - Multiple
Data Stream


Engloba os modelos de memória compartilhada e
passagem de mensagens, onde ocorrem a
presença de vários processadores.
Composto pelos multiprocessadores e
multicomputadores
16
O Modelo MIMD
17
Extensão à classificação de Flynn

Em 1988, E. E. Johnson propôs uma
extensão à classificação de Flynn, na qual as
máquinas MIMD seriam baseadas na
estrutura de memória (global ou distribuída) e
no mecanismo usado para
comunicação/sincronização (variáveis
compartilhadas ou passagem de
mensagem).
18
Extensão à classificação de Flynn
19
Extensão à classificação de Flynn

GMSV - Global Memory - Shared Variables


Engloba as máquinas que contém vários
processadores e que compartilham a mesma
memória.
GMMP - Global Memory – Message Passing

Não existe, na prática, um computador com esta
classificação.
20
Extensão à classificação de Flynn

DMSV - Distributed Memory - Shared
Variables


Engloba múltiplos computadores interconectados
e que compartilham a memória distribuída.
DMMP - Distributed Memory - Message
Passing


Engloba múltiplos computadores interconectados
e que se comunicam via passagem (troca) de
mensagens.
Supercomputadores
21
Computador Paralelo


Podemos entender um computador paralelo
como sendo uma máquina contendo vários
processadores, bem como um conjunto de
máquinas interconectadas.
Teoricamente, teríamos que N computadores
equivaleriam a N vezes o poder
computacional de uma única máquina.
22
Computador Paralelo

Na prática, obviamente, nem todos os
problemas podem ser resolvidos pela divisão
perfeita em partes totalmente independentes.


Além disso, temos outros fatores físicos, como
latência e largura de banda das redes de
interconexão entre as máquinas, por exemplo.
Contudo, um considerável aumento de
desempenho pode ser alcançado.
23
Computador Paralelo


O uso de múltiplos computadores/processadores
permite que se possa obter uma solução mais
precisa de um problema em um tempo aceitável.
Além disso, um fator associado com o uso de
múltiplos computadores é que podemos ter uma
quantidade total de memória muito superior a de um
único computador, possibilitando a resolução
também de problemas que necessitem de grande
volume de dados.
24
Tipos de Computadores Paralelos

Há dois tipos principais:


Multiprocessador de Memória Compartilhada
Multicomputador de Memória Distribuída
25
Sistema com Múltiplos Processadores e
Memória Compartilhada


Computador convencional = um processador
executando um programa em uma memória
principal
Neste modelo é utilizado o conceito de
memória virtual, ou seja, são associados dois
endereços para cada local da memória:


um endereço virtual, gerado pelo processador
um endereço real, usado para o acesso à posição
de memória
26
Sistema com Múltiplos Processadores e
Memória Compartilhada



Com base em uma tabela armazenada no
hardware se faz a tradução automática entre
um endereço virtual e um real.
Uma maneira de se estender este modelo
com um único processador é ter vários
processadores conectados a uma memória
principal.
Neste modelo é utilizado um único espaço de
endereçamento, podendo-se usar também
uma extensão do modelo de memória virtual.
27
Sistema com Múltiplos Processadores e
Memória Compartilhada
28
Visão simplificada de um multiprocessador
de memória compartilhada

Exemplos


Dual Pentium
Sparcs Sun
29
Sistema com Múltiplos Processadores e
Memória Compartilhada



Cada processador acessa qualquer
localização de memória.
Há um único espaço de endereço, cada local
de memória é dado por um único endereço
em um só intervalo de endereços.
Geralmente, sua programação é mais
conveniente embora o acesso a dados
compartilhados deva ser controlado pelo
programador (usando seções críticas etc.)
30
Sistema com Múltiplos Processadores e
Memória Compartilhada

O desenvolvimento de programas para
execução neste modelo de memória
compartilhada pode ser feito:

Usando Threads (Java, ..) na qual o programador
decompõe o programa em seqüências paralelas
individuais, cada uma sendo uma thread, e sendo
capaz de acessar variáveis declaradas fora das
threads.
31
Sistema com Múltiplos Processadores e
Memória Compartilhada

O desenvolvimento de programas para
execução neste modelo de memória
compartilhada pode ser feito (cont.):

Usando uma linguagem de programação
sequencial com diretivas de compilação para
declarar variáveis compartilhadas e especificar
paralelismo.

Ex. OpenMP – Padrão da indústria
32
Sistema com Múltiplos Processadores e
Memória Compartilhada

O desenvolvimento de programas para
execução neste modelo de memória
compartilhada pode ser feito (cont.):

Linguagem de programação seqüencial c/
biblioteca user-level para declarar e acessar
variáveis compartilhadas.
33
Memória Compartilhada Distribuída


Cada processador tem acesso à memória como um
todo, usando um espaço de endereçamento único.
Para o acesso a um endereço de memória não-local
ao processador, é necessário uma troca de
mensagem para passar dados do processador para
o local da memória ou vice-versa.


Esta troca é transparente e automatizada de forma a
esconder o fato da distribuição
Desvantagem:

Acesso remoto pode representar um atraso maior do que
um acesso à memória local
34
Múltiplos Computadores com Passagem
de Mensagem
• Computador completo conectado por uma rede de
interconexão:
35
Múltiplos Computadores com Passagem
de Mensagem



Memória Compartilhada = sistema
especialmente projetado
Alternativa: uso de um conjunto de
computadores interconectados via rede
Cada computador consiste de um
processador e uma memória local não
acessível pelos demais processadores.

A memória é distribuída entre os computadores e
cada um tem seu próprio espaço de
endereçamento
36
Múltiplos Computadores com Passagem
de Mensagem



Mensagens são enviadas de um processador
para outro via a rede de interconexão.
Tais mensagens podem incluir dados
necessários para que um processador faça
seu trabalho.
O conteúdo dessas mensagens depende do
processo que está sendo executado.
37
Múltiplos Computadores com Passagem
de Mensagem

Programar para este modelo implica na
divisão do problema em partes que deverão
executar simultaneamente.


Podem ser usadas linguagens seqüenciais
estendidas ou linguagens paralelas
Porém, mais comum é o uso de bibliotecas com
rotinas para passagem de mensagens que podem
ser associadas a linguagens de programação
convencionais
38
Múltiplos Computadores com Passagem
de Mensagem

Portanto, um problema é dividido em
processos, os quais são alocados nos
computadores que compõem o ambiente de
passagem de mensagem.


Processo trocam mensagens entre si, sendo esta
a única forma de comunicação entre os mesmos,
distribuindo dados e resultados
Este modelo é mais facilmente escalável que
o modelo de memória compartilhada.
39
Múltiplos Computadores com Passagem
de Mensagem


Desvantagens:

Menos atrativa que memória compartilhada

Programador tem que explicitamente prover as chamadas
às rotinas de passagem de mensagem

Bastante susceptível a erros de programação

Dados não podem ser compartilhados, apenas copiados
Vantagens:

Não requer mecanismos avançados para acesso
concorrente a dados compartilhados

Escalabilidade mais facilmente implementada
40
Aspectos Arquiteturais em Ambientes de
Passagem de Mensagem

Redes Estáticas

Presença de links físicos fixos entre os computadores
41
Aspectos Arquiteturais em Ambientes de
Passagem de Mensagem

Redes Estáticas

Links podem ser bidirecionais ou apresentarem
dois links unidirecionais separados (um em cada
direção)

Características chaves:

Largura de banda (bits/segundo)

Latência (tempo para transferir uma mensagem pela
rede)

Custo
42
Aspectos Arquiteturais em Ambientes de
Passagem de Mensagem

Redes Estáticas


A quantidade de links entre dois nós é um fator
importante no atraso de uma mensagem
Diâmetro representa o número mínimo de links
entre os dois nós mais distantes da rede.

É usado para se determinar o maior atraso que
pode ocorrer
43