1 Algoritmos Paralelos. 2 Demanda por velocidade computacional Demanda contínua por maior rapidez...

1

Algoritmos Paralelos

2

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

3

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.

4

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.

5

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.

6

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

7

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.

8

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

9

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.

10

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.

11

Classificação de Flynn

12

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

13

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.

14

Modelo SIMD

15

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.

16

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

17

O Modelo MIMD

18

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

19

Extensão à classificação de Flynn

20

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.

21

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

22

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.

23

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.

24

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.

25

Tipos de Computadores Paralelos Há dois tipos principais:

Multiprocessador de Memória Compartilhada Multicomputador de Memória Distribuída

26

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

27

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.

28

Sistema com Múltiplos Processadores e Memória Compartilhada

29

Visão simplificada de um multiprocessador de memória compartilhada

Exemplos Dual Pentium Sparcs Sun

30

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

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

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

33

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.

34

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

35

Múltiplos Computadores com Passagem de Mensagem

• Computador completo conectado por uma rede de interconexão:

36

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

37

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.

38

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

39

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.

40

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

41

Aspectos Arquiteturais em Ambientes de Passagem de Mensagem Redes Estáticas

Presença de links físicos fixos entre os computadores

42

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

43

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