Introdução ao Processamento de Alto Desempenho - ERAD...

IntroduçãoProgramação Paralela

Introdução ao Processamento de AltoDesempenhoERAD Nordeste

Prof. Dr. Esbel Tomás Valero Orellana

Núcleo de Biologia Computacional e Gestão de Informações BiotecnológicasDepartamento de Ciências Exatas e Tecnológicas

Universidade Estadual de Santa Cruzevalero@nbcgib.uesc.br

21 de Setembro de 2011

1 / 46

IntroduçãoProgramação Paralela

Apresentação

O PROFESSOR

1995 - Formado em Enganharia Nuclear pelo ISCTN (Havana, Cuba)

2000 - Mestrado em Modelagem Computacional pelo IP da UERJ (NovaFriburgo, RJ, Brasil)

2008 - Doutorado em Modelagem Computacional pelo LNCC (Petrópolis, RJ,Brasil)

2002 - Implantação do O Laboratório de Bioinformática - LABBI na UESC

2007 - Direção do Núcleo de Biologia Computacional e Gestão de InformaçõesBiotecnológicas - NBCGIB na UESC http://nbcgib.uesc.br

2008 - Criaç o da Rede Colaborativa de Computação de Alto Desempenho eAplicações da Bahia (Rede CoCADA-Ba) http://nbcgib.uesc.br/cocada

2009 - Implantação do Centro de Armazenamento de dados e ComputaçãoAvançada da UESC - CACAU http://nbcgib.uesc.br/cacau

2 / 46

IntroduçãoProgramação Paralela

Apresentação

O EVENTO

A Escola Regional de Alto Desempenho (ERAD) - Região Nordeste é um eventoorganizado pela Rede CoCADA, a qual é composta por instituições de ensino e depesquisa dos estados da Bahia, Alagoas e Sergipe, bem como por pesquisadores daUniversidade Autônoma de Barcelona.O público-alvo do evento é composto por alunos de cursos de graduação epós-graduação, professores, pesquisadores e profissionais com interesse na área deProcessamento de Alto Desempenho (PAD) e seus temas relacionados.Objetivos

Promover a área de PAD no estado e na região;

Qualificar o público-alvo nos temas pertinentes a essa área;

Estabelecer um espaço de referência para o intercâmbio de experiências deensino, pesquisa e extensão em PAD na região.

3 / 46

IntroduçãoProgramação Paralela

Apresentação

O MINI-CURSO A

O Mini-curso A: Introdução a Processamento de Alto desempenho pretende fazerum revisão de alguns tópicos gerais PAD. Serão abordadas as principais tecnologiasdisponíveis e as técnicas de programação paralela mais utilizadas. Programaçãoutilizando multithreads, troca de mensagens e a arquitetura CUDA são apresentadasde forma resumida.O Minicurso se propões servir como base para estudos futuros, mais avançados,sobre os temas abordados. Pelas limitações de tempo e espaço está fora do escopooferecer uma referência detalhada em programação paralela.

4 / 46

IntroduçãoProgramação Paralela

Apresentação

OS PARTICIPANTES

A plateia está formada por ...

quantos alunos de graduação?

de quais cursos?

quantos alunos de pós-graduação?

quantos professores, pesquisadores e profissionais com interesse na área dePAD?

5 / 46

IntroduçãoProgramação Paralela

Apresentação

OS PARTICIPANTES

A plateia está formada por ...

quantos alunos de graduação?

de quais cursos?

quantos alunos de pós-graduação?

quantos professores, pesquisadores e profissionais com interesse na área dePAD?

5 / 46

IntroduçãoProgramação Paralela

Apresentação

OS PARTICIPANTES

A plateia está formada por ...

quantos alunos de graduação?

de quais cursos?

quantos alunos de pós-graduação?

quantos professores, pesquisadores e profissionais com interesse na área dePAD?

5 / 46

IntroduçãoProgramação Paralela

Apresentação

OS PARTICIPANTES

A plateia está formada por ...

quantos alunos de graduação?

de quais cursos?

quantos alunos de pós-graduação?

quantos professores, pesquisadores e profissionais com interesse na área dePAD?

5 / 46

IntroduçãoProgramação Paralela

Tópicos

Introdução

Considerações sobre PADArquiteturas Modernas com Múltiplos ProcessadoresVisão Geral sobre Programação ParalelaEstudo de caso: Multiplicação de MatizesConsiderações Finais

6 / 46

IntroduçãoProgramação Paralela

Tópicos

IntroduçãoConsiderações sobre PAD

Arquiteturas Modernas com Múltiplos ProcessadoresVisão Geral sobre Programação ParalelaEstudo de caso: Multiplicação de MatizesConsiderações Finais

6 / 46

IntroduçãoProgramação Paralela

Tópicos

IntroduçãoConsiderações sobre PADArquiteturas Modernas com Múltiplos Processadores

Visão Geral sobre Programação ParalelaEstudo de caso: Multiplicação de MatizesConsiderações Finais

6 / 46

IntroduçãoProgramação Paralela

Tópicos

IntroduçãoConsiderações sobre PADArquiteturas Modernas com Múltiplos ProcessadoresVisão Geral sobre Programação Paralela

Estudo de caso: Multiplicação de MatizesConsiderações Finais

6 / 46

IntroduçãoProgramação Paralela

Tópicos

IntroduçãoConsiderações sobre PADArquiteturas Modernas com Múltiplos ProcessadoresVisão Geral sobre Programação ParalelaEstudo de caso: Multiplicação de Matizes

Considerações Finais

6 / 46

IntroduçãoProgramação Paralela

Tópicos

IntroduçãoConsiderações sobre PADArquiteturas Modernas com Múltiplos ProcessadoresVisão Geral sobre Programação ParalelaEstudo de caso: Multiplicação de MatizesConsiderações Finais

6 / 46

IntroduçãoProgramação Paralela

A evolução

7 / 46

IntroduçãoProgramação Paralela

Uma linha do tempo

Em 1993 começa a ser desenvolvido o primeiro cluster tipoBeowulf

8 / 46

IntroduçãoProgramação Paralela

Uma linha do tempo

Em 1993 começa a ser desenvolvido o primeiro cluster tipoBeowulf

8 / 46

IntroduçãoProgramação Paralela

Uma linha do tempo

O conceito de cluster Beowulf evoluiu ...

9 / 46

IntroduçãoProgramação Paralela

Uma linha do tempo

O conceito de cluster Beowulf evoluiu ...

9 / 46

IntroduçãoProgramação Paralela

Uma linha do tempo

... e ficou sofisticado

10 / 46

IntroduçãoProgramação Paralela

Uma linha do tempo

... e ficou sofisticado

10 / 46

IntroduçãoProgramação Paralela

Uma linha do tempo

Entretanto, por volta de 2003 novidades tecnológicaschegaram para modificar a forma como se pensava PAD atéaquele momento

11 / 46

IntroduçãoProgramação Paralela

Uma linha do tempo

Entretanto, por volta de 2003 novidades tecnológicaschegaram para modificar a forma como se pensava PAD atéaquele momento

11 / 46

IntroduçãoProgramação Paralela

Uma linha do tempo

Hoje, quase dez anos depois, nos encontramos com umsenário totalmente novo no qual um simples laptop podepossuir um desempenho da ordem dos teraflops;

12 / 46

IntroduçãoProgramação Paralela

Uma linha do tempo

Os modernos clusters passaram a utilizar máquinasmultiprocessadas e, em alguns casos, equipadas compoderosas GPUs;As novas arquiteturas híbridas, interligadas por redes cadavez mais rápidas, incrementaram a capacidadecomputacional disponível.

13 / 46

IntroduçãoProgramação Paralela

Serial vs Paralelo

Algoritmo serial ou sequencial: executado em um únicoprocessador,

Algoritmo paralelo: executado em dois ou mais processa-dores,

Para cada algoritmo paralelo existe um algoritmo serial querealiza a mesma tarefa,

Antes de criar um algoritmo paralelo sempre crie uma ver-são serial para o mesmo problema.

Algoritmo serial:ponto de partida,garante a compreensão do problema,auxilia na validação do programa paralelo.

14 / 46

IntroduçãoProgramação Paralela

Objetivo de um programa paralelo

Objetivo de um algoritmo paralelo: obter um desempe-

nho superior com relação a versão sequencial;

Desempenho = tempo de execução,

Tempo total de execução = tempo de computação +

tempo ocioso + tempo de comunicação,

15 / 46

IntroduçãoProgramação Paralela

Tempo de execução

Tempo de computação: tempo das operações de E/S e

cálculos do programa,

Tempo ocioso ou tempo de sincronização: Dedicado a sin-

cronizar um algoritmo ou a esperar pelos processos mais

lentos,

Tempo de comunicação = latência + tempo de transmis-

são,

latência: tempo de preparação da mensagem (pacotes),

tempo de transmissão: velocidade real de transmissão

(largura de banda).

16 / 46

IntroduçãoProgramação Paralela

Fatores

Para obtermos algoritmos paralelos eficientes devemos con-

siderar:

Balanceamento de carga: dividir equitativamente o trabalho

entre os processadores,

Minimizar as necessidades de comunicação,

Minimizar o tempo ocioso,

Sobrepor as operações de comunicação e de computação.

Minimizar (concentrar) as operações E/S.

17 / 46

IntroduçãoProgramação Paralela

Projeto de programas paralelos

Existem basicamente dois enfoques para projetar progra-

mas paralelos:

1 Paralelismo de dados: neste enfoque particionamos os

dados, e associamos um subconjunto de dados a cada pro-

cesso, cada processo executa os mesmos comandos sobre

seu subconjunto de dados.

2 Paralelismo de controle: dividimos o problema em tare-

fas (etapas) independentes, associamos cada tarefa a um

processo, cada processo executa comandos diferentes.

18 / 46

IntroduçãoProgramação Paralela

Projeto de programas paralelos

Características do paralelismo de dados:

1 pode ser implementado mais facilmente que o paralelismo

de controle,

2 não é prejudicado pela dependência entre as operações,

3 programas deste tipo são facilmente escaláveis (podem ser

utilizados para resolver problemas cada vez maiores, ape-

nas colocando mais processos),

4 pouca comunicação entre processos.

19 / 46

IntroduçãoProgramação Paralela

Projeto de programas paralelos

Características do paralelismo de controle:

1 deve considerar a dependência entre as operações,

2 difícil de ser implementado,

3 dificuldades de escalabilidade,

4 grandes necessidades de comunicação.

A maioria dos programas paralelos envolvem os dois

enfoques (dados e controle),

O paralelismo de dados é muito mais comum.

20 / 46

IntroduçãoProgramação Paralela

Projeto de programas paralelos

Características do paralelismo de controle:

1 deve considerar a dependência entre as operações,

2 difícil de ser implementado,

3 dificuldades de escalabilidade,

4 grandes necessidades de comunicação.

A maioria dos programas paralelos envolvem os dois

enfoques (dados e controle),

O paralelismo de dados é muito mais comum.

20 / 46

IntroduçãoProgramação Paralela

Projeto de programas paralelos

Como construir um programa paralelo:

1 Estudar, implementar e validar uma solução serial para o

problema;

2 Dividir os dados do problema entre os processos (PD);

3 Verificar se a solução paralela pode ser alcançada apenas

executando o algoritmo serial em cada conjunto de dados

(PD);

4 Se o paralelismo de dados não for suficiente, identificar as

necessidades de comunicação entre os processos;

5 Introduzir o paralelismo de controle (PC).

21 / 46

IntroduçãoProgramação Paralela

Projeto de programas paralelos

Como construir um programa paralelo:

1 Estudar, implementar e validar uma solução serial para o

problema;

2 Dividir os dados do problema entre os processos (PD);

3 Verificar se a solução paralela pode ser alcançada apenas

executando o algoritmo serial em cada conjunto de dados

(PD);

4 Se o paralelismo de dados não for suficiente, identificar as

necessidades de comunicação entre os processos;

5 Introduzir o paralelismo de controle (PC).

21 / 46

IntroduçãoProgramação Paralela

Projeto de programas paralelos

Como construir um programa paralelo:

1 Estudar, implementar e validar uma solução serial para o

problema;

2 Dividir os dados do problema entre os processos (PD);

3 Verificar se a solução paralela pode ser alcançada apenas

executando o algoritmo serial em cada conjunto de dados

(PD);

4 Se o paralelismo de dados não for suficiente, identificar as

necessidades de comunicação entre os processos;

5 Introduzir o paralelismo de controle (PC).

21 / 46

IntroduçãoProgramação Paralela

Projeto de programas paralelos

Como construir um programa paralelo:

1 Estudar, implementar e validar uma solução serial para o

problema;

2 Dividir os dados do problema entre os processos (PD);

3 Verificar se a solução paralela pode ser alcançada apenas

executando o algoritmo serial em cada conjunto de dados

(PD);

4 Se o paralelismo de dados não for suficiente, identificar as

necessidades de comunicação entre os processos;

5 Introduzir o paralelismo de controle (PC).

21 / 46

IntroduçãoProgramação Paralela

Projeto de programas paralelos

Como construir um programa paralelo:

1 Estudar, implementar e validar uma solução serial para o

problema;

2 Dividir os dados do problema entre os processos (PD);

3 Verificar se a solução paralela pode ser alcançada apenas

executando o algoritmo serial em cada conjunto de dados

(PD);

4 Se o paralelismo de dados não for suficiente, identificar as

necessidades de comunicação entre os processos;

5 Introduzir o paralelismo de controle (PC).

21 / 46

IntroduçãoProgramação Paralela

Análise de Desempenho

p = número de processos (processadores) ou threads.

n = tamanho do problema.

Para avaliar o desempenho de programas seriais se utiliza

notação assintótica (O, Ω),

Análises assintóticas não são apropriadas para

caracterizar o desempenho de programas paralelos.

22 / 46

IntroduçãoProgramação Paralela

Métricas

Tempo de execução,

Granularidade,

Fator de balanço de carga,

Speedup,

Eficiência.

23 / 46

IntroduçãoProgramação Paralela

Tempo de execução

Tempo de execução de um programa serial: T (n), apenas

depende do tamanho do problema;

Tempo de execução de um programa paralelo: T (n, p), de-

pende do tamanho do problema e do número de processa-

dores utilizados na execução;

T (n, p)→ tempo total de execução, tempo transcorrido desde

que o primeiro processador começa a execução, até que o

último processador completa a execução da última instru-

ção.

24 / 46

IntroduçãoProgramação Paralela

Tempo de execução

Na maioria dos programas T (n, p) é simplesmente o tempo

de execução do processo responsável pelas operações de

E/S do programa (processo master),

Consideramos que cada processo é executado em um pro-

cessador físico diferente (não existem processos concor-

rentes),

Geralmente para avaliarmos o desempenho de um programa

paralelo comparamos ele com o programa serial que re-

solve o mesmo problema.

25 / 46

IntroduçãoProgramação Paralela

Speedup

Speedup: é a razão do tempo de execução do algoritmo

serial T (n) com o tempo de execução do algoritmo paralelo

T (n, p),

S(n, p) =T (n)

T (n, p)

T (n)→ tempo de execução do algoritmo serial mais rápido

executado em um processador da máquina paralela,

T (n, p) → tempo de execução do algoritmo paralelo em p

processadores da máquina paralela.

26 / 46

IntroduçãoProgramação Paralela

Speedup

O algoritmo paralelo pode ser diferente do algoritmo serial

mais rápido,

O speedup fornece um indicador para o aumento da velo-

cidade por utilizarmos uma maquina paralela.

De forma geral: 0 < S(n, p) ≤ p,

Se S(n, p) = p teremos speedup linear,

Speedup linear é uma rara ocorrência pois a maioria das

soluções paralelas introduzem alguma sobrecarga produto

da distribuição de carga e a comunicação entre processos.

27 / 46

IntroduçãoProgramação Paralela

Speedup

Se a sobrecarga da paralelização for muito alta, teremos

que T (n) < T (n, p) e S(n, p) < 1 esta situação indesejável

é chamada de slowdown.

Resumo de speedups:

S(n, p) < 1, slowdown, situação indesejável;

1 < S(n, p) < p, sublinear, comportamento geral;

S(n, p) = p, linear, ideal não existe sobrecarga;

S(n, p) > p, supralinear, situação possível;

28 / 46

IntroduçãoProgramação Paralela

Eficiência

Eficiência: é a medida de utilização dos processos em umprograma paralelo em relação ao programa serial.

E(n, p) =S(n, p)

p=

T (n)

pT (n, p)

E(n, p) < 1p , slowdown;

1p < E(n, p) < 1, sublinear;

E(n, p) = 1, linear;

E(n, p) > 1, supralinear.

29 / 46

IntroduçãoProgramação Paralela

Eficiência

Eficiência: é a medida de utilização dos processos em umprograma paralelo em relação ao programa serial.

E(n, p) =S(n, p)

p=

T (n)

pT (n, p)

E(n, p) < 1p , slowdown;

1p < E(n, p) < 1, sublinear;

E(n, p) = 1, linear;

E(n, p) > 1, supralinear.

29 / 46

IntroduçãoProgramação Paralela

Tomadas de tempo

Para avaliar o desempenho de programas paralelos deve-mos realizar tomadas de tempo,

Para obtermos tomadas de tempo confiáveis considere asseguintes etapas:

1 Garantir na medida do possível exclusividade na utilizaçãodo processador,

2 Sincronizar os processo no inicio do código,3 Fazer uma tomada de tempo (start),4 Sincronizar os processo no final do código,5 fazer uma tomada de tempo (finish),6 Calcular o tempo transcorrido (finish-start).

30 / 46

IntroduçãoProgramação Paralela

Lei de Ahmdal

A lei de Amdahl, foi formulada por Gene Amdahl em 1967;

Estabelece um limite superior para o speedup de um algo-

ritmo paralelo;

De forma geral um problema é composto por:

Um conjunto de operações de cálculo,

Um conjunto de operações de E/S.

Um algoritmo serial leva um tempo Ts para resolver o pro-

blema.

31 / 46

IntroduçãoProgramação Paralela

Instruções paralelas

O programa tem uma fração r = (1 − f ) de instruções que

são “perfeitamente paralelizáveis”;

Operações de cálculo;

Independentemente do número de processos envolvidos

(p), a fração r do programa apresenta speedup linear;

O tempo de execução quando paralelizada com p proces-

sos é: rTs/p.

32 / 46

IntroduçãoProgramação Paralela

Instruções seriais

Entretanto, temos uma fração f que é inerentemente serial;

Operações de E/S;

Independentemente do número de processos (p) utiliza-

dos;

O tempo de execução destas instruções é sempre fTs.

33 / 46

IntroduçãoProgramação Paralela

Instruções seriais + paralelas

34 / 46

IntroduçãoProgramação Paralela

Speedup

Calculamos o speedup deste programa:

S(n, p) =Ts

fTs + (1− f )Ts/p

S(n, p) =1

f + (1− f )/p

Derivamos S(n, p) com relação a p, obteremos uma deri-

vada sempre positiva indicando S(n, p) é uma função sem-

pre crescente.dS(p)

dp=

r

[(1− r)p + r ]2≥ 0

35 / 46

IntroduçãoProgramação Paralela

Speedup

Calculamos o speedup deste programa:

S(n, p) =Ts

fTs + (1− f )Ts/p

S(n, p) =1

f + (1− f )/p

Derivamos S(n, p) com relação a p, obteremos uma deri-

vada sempre positiva indicando S(n, p) é uma função sem-

pre crescente.dS(p)

dp=

r

[(1− r)p + r ]2≥ 0

35 / 46

IntroduçãoProgramação Paralela

Speedup

Calculamos o limite de S(n, p) quando p →∞

limp→∞

S(n, p) = limp→∞

1(1− r) + r/p

=1

(1− r)

A função 1/(1− r) é um limite superior para o speedup de

um programa paralelo.

Lei de Amhdal: o speedup que podemos obter ao parale-

lizar um programa é limitado por 1/(1− r).

36 / 46

IntroduçãoProgramação Paralela

Exemplos

Cálculo de speedup máximo segunda a lei de Ahmdal

1 r = 0.50, MS = 1/(1− r) = 2, para p > 2, E(n, p) ↓.

2 r = 0.75, MS = 1/(1− r) = 4, para p > 4, E(n, p) ↓.

3 r = 0.99, MS = 1/(1− r) = 100, para p > 100, E(n, p) ↓.

4 Se executarmos o caso 3 com p = 1000 teremos uma

eficiência E(n, p) = 0.1.

37 / 46

IntroduçãoProgramação Paralela

Exemplos

Cálculo de speedup máximo segunda a lei de Ahmdal

1 r = 0.50, MS = 1/(1− r) = 2, para p > 2, E(n, p) ↓.

2 r = 0.75, MS = 1/(1− r) = 4, para p > 4, E(n, p) ↓.

3 r = 0.99, MS = 1/(1− r) = 100, para p > 100, E(n, p) ↓.

4 Se executarmos o caso 3 com p = 1000 teremos uma

eficiência E(n, p) = 0.1.

37 / 46

IntroduçãoProgramação Paralela

Exemplos

Cálculo de speedup máximo segunda a lei de Ahmdal

1 r = 0.50, MS = 1/(1− r) = 2, para p > 2, E(n, p) ↓.

2 r = 0.75, MS = 1/(1− r) = 4, para p > 4, E(n, p) ↓.

3 r = 0.99, MS = 1/(1− r) = 100, para p > 100, E(n, p) ↓.

4 Se executarmos o caso 3 com p = 1000 teremos uma

eficiência E(n, p) = 0.1.

37 / 46

IntroduçãoProgramação Paralela

Exemplos

Cálculo de speedup máximo segunda a lei de Ahmdal

1 r = 0.50, MS = 1/(1− r) = 2, para p > 2, E(n, p) ↓.

2 r = 0.75, MS = 1/(1− r) = 4, para p > 4, E(n, p) ↓.

3 r = 0.99, MS = 1/(1− r) = 100, para p > 100, E(n, p) ↓.

4 Se executarmos o caso 3 com p = 1000 teremos uma

eficiência E(n, p) = 0.1.

37 / 46

IntroduçãoProgramação Paralela

Exemplos

Speedup máximo segunda a lei de Ahmdal

38 / 46

IntroduçãoProgramação Paralela

Exemplos

O pintor de estacas1 Preparo da tinta = 30s2 Pintura das estacas = 300s3 Tempo para a tinta secar = 30s

Pintores Tempo Speedup

1 30 + 300 + 30 = 360 1.02 30 + 150 + 30 = 210 1.7

10 30 + 30 + 30 = 90 4.0100 30 + 3 + 30 = 63 5.7∞ 30 + 0 + 30 = 60 6.0

39 / 46

IntroduçãoProgramação Paralela

Exemplos

O pintor de estacas1 Preparo da tinta = 30s2 Pintura das estacas = 300s3 Tempo para a tinta secar = 30s

Pintores Tempo Speedup

1 30 + 300 + 30 = 360 1.02 30 + 150 + 30 = 210 1.7

10 30 + 30 + 30 = 90 4.0100 30 + 3 + 30 = 63 5.7∞ 30 + 0 + 30 = 60 6.0

39 / 46

IntroduçãoProgramação Paralela

Exemplos

A lei de Ahmdal desencoraja a utilização de paralelismo

massivo;

Não devemos utilizar centos ou mieis de processadores

para resolver um único problema;

Esta conclusão é correta? O que fazer?

A formulação de Ahmdal é matematicamente correta;

Entretanto, devemos discutir suas hipóteses.

40 / 46

IntroduçãoProgramação Paralela

Exemplos

A lei de Ahmdal desencoraja a utilização de paralelismo

massivo;

Não devemos utilizar centos ou mieis de processadores

para resolver um único problema;

Esta conclusão é correta? O que fazer?

A formulação de Ahmdal é matematicamente correta;

Entretanto, devemos discutir suas hipóteses.

40 / 46

IntroduçãoProgramação Paralela

Lei de Ahmdal - Hipóteses

Em todo programa existe um conjunto de (1− r) instruções

que não são paralelizáveis;

É excessivamente otimista supor que as restantes r ins-

truções são perfeitamente paralelizáveis, sempre teremos

alguma sobrecarga produto da paralelização;

A principal deficiência da lei de Amdhal é que não consi-

dera o tamanho do problema n na formulação.

41 / 46

IntroduçãoProgramação Paralela

Lei de Ahmdal - Hipóteses

Em todo programa existe um conjunto de (1− r) instruções

que não são paralelizáveis;

É excessivamente otimista supor que as restantes r ins-

truções são perfeitamente paralelizáveis, sempre teremos

alguma sobrecarga produto da paralelização;

A principal deficiência da lei de Amdhal é que não consi-

dera o tamanho do problema n na formulação.

41 / 46

IntroduçãoProgramação Paralela

Lei de Ahmdal - Hipóteses

Em todo programa existe um conjunto de (1− r) instruções

que não são paralelizáveis;

É excessivamente otimista supor que as restantes r ins-

truções são perfeitamente paralelizáveis, sempre teremos

alguma sobrecarga produto da paralelização;

A principal deficiência da lei de Amdhal é que não consi-

dera o tamanho do problema n na formulação.

41 / 46

IntroduçãoProgramação Paralela

Lei de Gustavfson

Em um problema qualquer ao aumentarmos o tamanho do

problema n, a fração de instruções seriais (1− r) fica con-

sideravelmente menor;

Exemplos

Escalabilidade: um programa é escalável se podemos man-

ter constante a eficiência E(n, p), incrementando o tama-

nho do problema n ao mesmo tempo que incrementamos o

número de processos p.

42 / 46

IntroduçãoProgramação Paralela

Lei de Gustavfson

Em um problema qualquer ao aumentarmos o tamanho do

problema n, a fração de instruções seriais (1− r) fica con-

sideravelmente menor;

Exemplos

Escalabilidade: um programa é escalável se podemos man-

ter constante a eficiência E(n, p), incrementando o tama-

nho do problema n ao mesmo tempo que incrementamos o

número de processos p.

42 / 46

IntroduçãoProgramação Paralela

Lei de Gustavfson

Conceitos de trabalho (W ) e sobrecarga (T0);

O trabalho de um programa serial é justamente seu tempode execução

W (n) = T (n);

O trabalho de um programa paralelo é a soma do trabalhofeito por cada processo

W (n, p) = pT (n, p);

A sobrecarga do programa paralelo, é a diferença entre otrabalho feito pelo programa paralelo e o programa serialcorrespondente

T0(n, p) = W (n, p)−W (n) = pT (n, p)− T (n).

43 / 46

IntroduçãoProgramação Paralela

Lei de Gustavfson

Conceitos de trabalho (W ) e sobrecarga (T0);

O trabalho de um programa serial é justamente seu tempode execução

W (n) = T (n);

O trabalho de um programa paralelo é a soma do trabalhofeito por cada processo

W (n, p) = pT (n, p);

A sobrecarga do programa paralelo, é a diferença entre otrabalho feito pelo programa paralelo e o programa serialcorrespondente

T0(n, p) = W (n, p)−W (n) = pT (n, p)− T (n).

43 / 46

IntroduçãoProgramação Paralela

Lei de Gustavfson

Conceitos de trabalho (W ) e sobrecarga (T0);

O trabalho de um programa serial é justamente seu tempode execução

W (n) = T (n);

O trabalho de um programa paralelo é a soma do trabalhofeito por cada processo

W (n, p) = pT (n, p);

A sobrecarga do programa paralelo, é a diferença entre otrabalho feito pelo programa paralelo e o programa serialcorrespondente

T0(n, p) = W (n, p)−W (n) = pT (n, p)− T (n).

43 / 46

IntroduçãoProgramação Paralela

Lei de Gustavfson

Conceitos de trabalho (W ) e sobrecarga (T0);

O trabalho de um programa serial é justamente seu tempode execução

W (n) = T (n);

O trabalho de um programa paralelo é a soma do trabalhofeito por cada processo

W (n, p) = pT (n, p);

A sobrecarga do programa paralelo, é a diferença entre otrabalho feito pelo programa paralelo e o programa serialcorrespondente

T0(n, p) = W (n, p)−W (n) = pT (n, p)− T (n).

43 / 46

IntroduçãoProgramação Paralela

Lei de Gustavfson

A eficiência foi definida na forma

E(n, p) =T (n)

pT (n, p),

Escrevemos a eficiência em função da sobrecarga,

Substituímos o denominador pela definição de sobrecarga

e obtemos

E(n, p) =1

T0(n, p)

T (n)+ 1

.

44 / 46

IntroduçãoProgramação Paralela

Lei de Gustavfson

Ao aumentar o número de processos incrementarmos p au-

menta a sobrecarga T0(n, p);

Se incrementamos n (aumenta T (n)) de forma que a fração

T0(n, p)/T (n) permanece constante;

Podemos então manter a eficiência constante e aumentar

o número de processos,

Este procedimento diminui o peso das operações seriais no

problema.

45 / 46

IntroduçãoProgramação Paralela

Lei de Gustavfson

Fontes de sobrecarga em programas paralelos:

Comunicação entre processos,

Inatividade de processos,

Cálculos adicionais (provocados pela paralelização).

Durante as décadas de 70 e 80, a lei de Amdahl foi ampla-

mente aceita nos círculos científicos.

Nos últimos anos o conceito de escalabilidade (Lei de Gufs-

tavson) tem aberto novos horizontes ao uso de paralelismo

massivo.

46 / 46