Programação Paralela Simone de Lima Martins Março-Julho/2001 Universidade Federal do Mato Grosso do Sul

Programação Paralela

Simone de Lima MartinsMarço-Julho/2001

Universidade Federal do Mato Grosso do Sul

Programação Paralela

• Conceitos gerais• Programação por passagem de mensagens• Computação embaraçosamente paralela• Estratégia de divisão e conquista• Computação pipelined• Computação com sincronização• Programação com memória compartilhada• Algoritmos e aplicações

Visão Geral

• Processamento paralelo consiste na utilização de múltiplos processadores para executar partes diferentes de um mesmo programa simultaneamente

• Principal objetivo é reduzir o tempo total de processamento (wall-clock time)

• Número de trabalhadores versus aceleração obtida

Objetivos

• Reduzir tempo total de processamento (wall clock time)• Custo

– execução em paralelo utilizando um grande número de estações de trabalho pode ser menor que utilizar um super computador

• Recursos locais versus não locais• Restrições de memória

Porque utilizar programação paralela ?

• Aumento de desempenho de um único processador– capacidade de memória– desempenho

• aumento do tamanho da palavra e da precisão utilizada– velocidade

• tecnologia de substratos mais finos, mais transistores em menor espaço, maiores e mais rápidas 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


• 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

• Limites na minituarização dos componentes• Limites econômicos

– aumento da velocidade dos processadores faz com que outros componentes tenham que ser modificados para trabalhar com maior velocidade aumento de custo

– aumento da densidade de transistores• aumenta a complexidade do processo de preparação do substrato para a

implementação da matriz de transistores e as ligações que os conectam e necessita-se desenvolver novos isoladores e dissipadores de calor


• Problemas denominados grandes desafios demoram muito para serem resolvidos

• Exemplos:– Previsão do tempo– Modelo de movimentação de corpos celestes

• Processadores bastante rápidos disponíveis e baratos• Utilização de um maior número de processadores

relativamente baratos em paralelo

Taxonomia de Arquiteturas (Flynn 1966)

Single InstructionSingle Data

SISD

Single InstructionMultiple Data

SIMD

Multiple InstructionSingle Data

MISD

Multiple InstructionMultiple Data

MIMD

Fluxo de dados

Fluxo de instruções

Único Múltiplo

Único

Múltiplo

Single Instruction, Single Data (SISD)B(I)=A(I)*4 LOAD A(I)

MULT 4STORE B(I)

LOAD A(1)

MULT 4

STORE A(1)

Processador P

Processador P

Processador P

TEMPO:

t1

t2

t3

Single Instruction, Single Data (SISD)

• Serial– Instruções são executadas uma após outra

• Determinismo– Pode-se saber o que está ocorrendo exatamente em cada instante de tempo

e reproduzir o processo passo a passo mais tarde

• Exemplos:– Computadores pessoais, estações de trabalho com uma única CPU,

minicomputadores e mainframes

Multiple Instruction, Single Data (MISD)

• Existem poucas máquinas que se encaixam nessa definição

• Exemplos de máquinas de propósito especial:– Múltiplos filtros de freqüência operando sobre um único fluxo de sinal– Múltiplos algoritmos de criptografia para decodificar uma mensagem

Single Instruction, Multiple Data (SIMD)B(I)=A(I)*4 LOAD A(I)

MULT 4STORE B(I)

TEMPO:

t1

t2

t3

LOAD A(1)

MULT 4

STORE A(1)

P1

P1

P1

LOAD A(2)

MULT 4

STORE A(2)

P2

P2

P2

LOAD A(3)

MULT 4

STORE A(3)

P3

P3

P3

. . .

. . .

. . .

Single Instruction, Multiple Data (SIMD)• Síncrono

– Todas as unidades devem receber a mesma instrução no mesmo instante de tempo de modo que todas possam executá-la de forma simultânea

• Determinismo– Em cada instante de tempo só existe uma instrução sendo executada por

várias unidades, então se o programa é executado com os mesmo dados de entrada, utilizando o mesmo número de unidades de execução, o resultado será o mesmo

• Apropriado para aplicações que utilizam paralelismo orientado a instrução

Single Instruction, Multiple Data (SIMD)• Exemplos:

– Cambridge Parallel Processing Gamma II Plus• 1024 processadores em um array 32x32, ou 4096 em 64x64• processador de controle armazena instruções e dados são

armazenados na memória de cada processador– Quadrics Apemille

• Máximo de 128 nós• Comunicação controlada por Controlador de memória e Controlador

de comunicação do backplane– Hoje em dia existem poucos supercomputadores SIMD vetorizados

pipelined

Multiple Instruction, Multiple Data (MIMD)

TEMPO:

InicializaDispara tarefa A

Dispara tarefa B

Espera por processador

Dispara tarefa C

Espera por processador

Dispara tarefa D

Espera fim de todas as tarefas

Junta resultadosFim

P1

Programa principal

P2 P3

Tarefa B

Fim

Tarefa A

Fim

Tarefa D

Fim

Tarefa C

Fim

Múltiple Instruction, Multiple Data (MIMD)

• Síncrono ou assíncrono• Determinismo ou não determinismo

– Sistemas MIMD pode ter comportamento determinístico tomando cuidado com alguns fatores, como a ordem de recepção das mensagens

• Adequado para paralelismo orientado a bloco, loop ou subrotinas– Requerimentos de comunicação menos restritos que paralelismo orientado

a instrução

Múltiple Instruction, Multiple Data (MIMD)

• Exemplos:– Assíncronos:

• IBM SP ou clusters utilizando PVM, MPI– utilizado para aplicações com menor comunicação e acoplamento entre tarefas

• Múltiplas unidades vetoriais trabalhando em um problema (Fujitsu VPP5000)

• Hipercubos (nCube2S) e meshes (Intel Paragon)– Síncronos

• IBM RS/6000 (4 instruções por ciclo) • Processadores capazes de executar instruções em modo pipelined

requerem compiladores capazes de ordenar instruções para resolver dependência de dados

Terminologia• Tarefa

– Uma seção logicamente discreta de um trabalho computacional– Exemplos:

• Calcular a transformada de Fourier• Calcular a média de 1000 valores

• Tarefas paralelas– Tarefas cujo processamento é independente um dos outros

• Execução serial– Execução de um programa de forma seqüencial, uma instrução de cada

vez

• SPMD (Single Program, Multiple Data)

Problema paralelizável

• Um problema que pode ser dividido em tarefas paralelas– Exemplos:

• Calcular a energia potencial de cada uma das diferentes conformações de uma molécula e determinar aquela de menor energia potencial Paralelizável

• Calcular a série de Fibonacci pela fórmula: Não paralelizável

)()1()2( kFkFkF

Tipos de paralelismo

• Paralelismo de dados– Cada tarefa executa uma mesma série de cálculos sobre diferentes dados– Localidade dos dados é parte essencial do algoritmo – Exemplos:

• cálculo da média de temperatura em um estado, procura de pessoas com mais de 65 anos em uma população

• Jogo de xadrez:

m1 m2 m3 ... mnLista de possíveis movimentos

p5

m1 m2

m5

m4m6

m7

p2 p3

m3

m8

p4

p1

tempo

Tipos de paralelismo

• Paralelismo funcional– 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

p4p2 p3p1

tempoPl

anta

s

Her

bívo

ros

Car

nívo

ros

Dec

ompo

sito

res para p1de p4

Modelos de acesso à memória

• Um computador convencional consiste de um processador executando um programa armazenado na memória:

• 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

Memória principal

Processador

Instruções para o processadorDados para ou do processador

Memória compartilhada

• 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• Um lugar da 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

Interconexão

P P P...

...

M M M

Memória compartilhada

• 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

– Threads• Seqüências de código escritas em alto nível para processadores

individuais que podem acessar localidades compartilhadas

Memória distribuída

• Memória fisicamente distribuída entre os processadores e cada memória local só pode ser acessada pelo seu processador• Sincronização requer comunicação entre processadores através de troca de mensagens• Problema na decomposição de domínio de dados• Tarefas se comunicam através de troca de mensagens

Interconexão

...P

M

P

M

Memória distribuída

• Programação:– Bibliotecas com rotinas para passagem de mensagens que são ligadas a

programas seqüenciais convencionais são bastante utilizadas– Problema dividido em um número de tarefas– Tarefas se comunicam entre si pela troca de mensagens, único modo de

distribuir dados e resultados entre elas

Memória compartilhada distribuída

• Cada processador tem acesso à toda memória utilizando um único espaço de endereçamento de memória• Para um processador acessar um lugar da memória que não está localizado na sua memória local, deve haver uma troca mensagens para que

os dados sejam passados da memória para o processador ou dele para a memória de uma forma automática que esconde o fato da memória ser fisicamente distribuída

• Máquinas ccNUMA (Cache Coherent Non-Uniform Memory Access)

Interconexão

...P

M

P

M

Fator de aceleração (speedup)

• Para uma máquina paralela com n processadores, speedup ideal seria n (speedup linear)

• S(n) > n, chamado de superlinear speedup– algoritmo seqüencial sub-ótimo– característica particular da arquitetura da máquina paralela

• memória extra, por exemplo

p

s

ttnS

paralela execução de temposerial execução de tempo)(

Speedup

Processo 1

Processo 2

Processo 3

Processo 4

Tempo

Espera para enviar mensagem Mensagem

Computando

Inclinação indica tempopara enviar mensagem

Speedup máximost

Seção serial Seções paralelizáveis

sft stf )1(

pt ntf s)1(

Um processador

Múltiplosprocessadores

n processadores

Speedup

• O fator de speedup é dado por:

• Equação conhecida com Lei de Amdahl

fnn

ntffttnS

ss

s

)1(1/)1()(

Lei de Amdhal

• Mesmo com número infinito de processadores o speedup é limitado a 1/f

• 5% de fração serial speedup máximo de 20, independente do número de processadores

4 8 12 16 20

4

8

12

16

20f=0%

f=5%f=10%f=20%

Número de processadores

Fato

r de

spee

dup,

S(n

)

0.2 0.4 0.6 0.8 1.0

4

8

12

16

20

Fator serial, f

Fato

r de

spee

dup,

S(n

)

n=256

n=16

Eficiência

• Eficiência fornece a fração de tempo que os processadores estão sendo utilizados para processamento

%100)(

nnSE

nttEp

s

resprocessado de númeroparalela execução de temposerial execução de tempo

Custo

• Custo de um processamento é definido como:

• O custo de uma execução seqüencial é simplesmente o tempo de execução ts

• O custo de uma execução paralela e´:

• Custo é considerado ótimo para um determinado algoritmo paralelo quando o custo da execução paralela é proporcional ao custo da execução seqüencial

utilizados resprocessado de totalnúmeroexecução de tempoCusto

Etn

nStnt ss

p )(

Sincronização

• Necessária para coordenar troca de informações entre tarefas– Ex: Somente após todas as tarefas terem calculado a energia potencial de

cada conformação de molécula, pode-se encontrar a molécula que possui a energia mínima

• 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 (speedup), porque o tempo utilizado para esperar uma outra tarefa poderia ser utilizado para processamento

Overhead de paralelismo

• Tempo utilizado para coordenar as tarefas paralelas• 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

Granulosidade• Uma medida da razão entre a quantidade de computação realizada em uma

tarefa paralela e a quantidade de comunicação necessária

tempo

FIM

Execução serial

INÍCIO Tarefas paralelasgeradas

Segundo pontode sincronização

granulosidade fina

INÍCIO

FIM

granulosidade grossa

Granulosidade

• Nível de granulosidade varia de fina (muito pouco processamento por comunicação de byte) a grossa (muita comunicação por comunicação de byte)

• Quanto mais fina a granulosidade, menor a aceleração devido à quantidade de sincronização exigida

Granulosidade fina

Granulosidade grossa

Nível de instrução

Rotinas longas

Loop com poucasiteraões

Escalabilidade

• Escalabilidade de hardware ou de arquitetura– Aumento do tamanho do sistema aumenta o desempenho

• capacidade de interconexão memória-processador e processador-processador

• Escalabilidade do algoritmo– Algoritmo pode acomodar um aumento do tamanho do problema a ser

tratado com um aumento baixo e limitado dos passos de computação• tamanho do problema:

– número de elementos de dados sendo processados– duplicação de dados de entrada não leva necessariamente à duplicação do número de

passos de computação» Ex: duplicar matrizes, duplica número de passos para adição de matrizes mas

quadruplica número de passos para multiplicação– complexidade do melhor algoritmo seqüencial (O(n), O(log n))

Convertendo programas seriais em paralelos

• Conversão manual versus automática– Conversão automática

• Compiladores tentam fazer alguma paralelização automática de loops DO• Para obter bons speedups deve-se ter a ajuda de especialistas além do

nível de automatização– Conversão manual

• Programador gasta tempo paralelizando• Dicas para extrair paralelismo de códigos seriais

– re-arranjar índices de loop para evitar interdependência de loops– chamadas a rotinas já paralelizadas e indicações (constructs) para pré-processadores ou

geradores de código indicando tentativa de paralelismo que deve ser executada em parte do código serial

– checar código gerado com constructs – reestruturação do algoritmo (tirar cálculo de um loop, por exemplo)


• Dependências gerais– Existe dependência entre instruções quando a ordem de execução delas

afeta o resultado do programa– Dependência de dados resulta do uso múltiplo do mesmo local da

memória– Exemplo:

• Programa com 3 instruções: a=b+1;c=4-a;b=2a-c;• 3 dependências de dados• 3 instruções dependentes de execução


• Dependências gerais– Dependência de comunicação

– Problemas de execução devido à dependência entre tarefas paralelas

send(B)

blocking_recv(C)

A

send(C)

blocking_recv(A)

B

send(A)

blocking_recv(B)

C


• Dependências em loops– Dependência independente no loop: local da memória é usado por instruções sucessivas em

uma iteração, mas não por iterações diferentes pode ser paralelizado porque iterações do loop podem ser executadas de forma independente e assíncrona

• Ex:DO 500 J=2,9 C[J]=A[J]+B[J] C[J]=C[J]*2.0500 CONTINUE

– Dependência carregada no loop: local da memória é utilizado por instruções, com pelo menos uma escrita, durante diferentes iterações do loop não pode ser paralelizado

• Ex:DO 500 J=2,9A[J]=A[J-1]*2.0500 CONTINUE


• Dependências em loops– Dependência carregada no loop: local da memória é utilizado por

instruções, com pelo menos uma escrita, durante diferentes iterações do loop não pode ser paralelizado

DO 500 J = 2,9A(J) = A(J-1) * 2.0

500 CONTINUE

A(2)=A(1)*2.0A(3)=A(2)*2.0

Proc. 1J=2,3

A(4)=A(3)*2.0A(5)=A(4)*2.0A(6)=A(5)*2.0

Proc. 2J=4,6

A(7)=A(6)*2.0A(8)=A(7)*2.0A(9)=A(8)*2.0

Proc. 3J=7,9

A(2)=A(1)*2.0A(3)=A(2)*2.0A(4)=A(3)*2.0A(5)=A(4)*2.0

A(7)=A(6)*2.0

A(6)=A(5)*2.0

A(8)=A(7)*2.0A(9)=A(8)*2.0

Custo de desenvolvimento de um programa paralelo

• Tempo do programador– análise do código para paralelizá-lo– re-escrita do código

• Depuração complicada• Perda de portabilidade do código• Tempo gasto em todas as CPUs é contabilizado pelo

centro de computação• Replicação de código e dados requer mais memória• Utilização de recursos por outros usuários

Documents

Programação Paralela Simone de Lima Martins Março-Julho/2001 Universidade Federal do Mato Grosso do Sul