Upload
others
View
2
Download
0
Embed Size (px)
Citation preview
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 [email protected]
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