22
1 Ricardo Rocha DCC-FCUP Programação Paralela e Distribuída 2007/08 Métricas de Desempenho 1 Programação Paralela e Distribuída Métricas de Desempenho Ricardo Rocha DCC-FCUP Programação Paralela e Distribuída 2007/08 Métricas de Desempenho 2 Desempenho Desempenho Dois dos principais objectivos do desenho de aplicações paralelas são: Desempenho: a capacidade de reduzir o tempo de resolução do problema à medida que os recursos computacionais aumentam. Escalabilidade: a capacidade de aumentar o desempenho à medida que a complexidade do problema aumenta. Os factores que condicionam o desempenho e a escalabilidade de uma aplicação são: Limites Arquitecturais Limites Algorítmicos

Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

Embed Size (px)

Citation preview

Page 1: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

1

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

1

ProgramaçãoParalela e Distribuída

Métricas de Desempenho

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

2

DesempenhoDesempenhoDois dos principais objectivos do desenho de aplicações paralelas são:

Desempenho: a capacidade de reduzir o tempo de resolução do problema à medida que os recursos computacionais aumentam.Escalabilidade: a capacidade de aumentar o desempenho à medida que a complexidade do problema aumenta.

Os factores que condicionam o desempenho e a escalabilidade de uma aplicação são:Limites ArquitecturaisLimites Algorítmicos

Page 2: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

2

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

3

Limites ao DesempenhoLimites ao DesempenhoLimites Arquitecturais

Latência e Largura de BandaCoerência dos DadosCapacidade de Memória

Limites AlgorítmicosFalta de Paralelismo (código sequencial/concorrência)Frequência de ComunicaçãoFrequência de SincronizaçãoEscalonamento Deficiente (granularidade das tarefas/balanceamento de carga)

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

4

Métricas de DesempenhoMétricas de DesempenhoExistem 2 classes distintas de métricas de desempenho:

Métricas de Desempenho para Processadores: métricas que permitem avaliar a performance de um processador tendo por base a velocidade/número de operações que este consegue realizar num determinado espaço temporal.Métricas de Desempenho para Aplicações Paralelas: métricas que permitem avaliar a performance de uma aplicação paralela tendo por base a comparação entre a execução com múltiplos processadores e a execução com um só processador.

No nosso caso, estamos obviamente mais interessados nas métricas que permitem avaliar o desempenho das aplicações paralelas.

Page 3: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

3

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

5

Métricas de Desempenho para ProcessadoresMétricas de Desempenho para ProcessadoresAlgumas das métricas mais conhecidas para medir o desempenho da arquitectura de um processador/computador são:

MIPS: acrónimo para Millions of Instructions Per Second.FLOPS: acrónimo para FLoating point Operations Per Second.SPECint: conjunto de programas de teste (benchmarks) da SPEC (Standard Performance Evaluation Corporation) que avaliam o desempenho do processador em aritmética de inteiros (1992).SPECfp: conjunto de programas de teste da SPEC que avaliam o desempenho do processador em operações de vírgula flutuante (2000).Whetstone: programa de teste sintético que avalia o desempenho do processador em operações de vírgula flutuante (1972).Dhrystone: programa de teste sintético que avalia o desempenho do processador em aritmética de inteiros (1984).

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

6

Métricas de Desempenho para Aplicações ParalelasMétricas de Desempenho para Aplicações ParalelasExistem várias medidas que permitem medir/avaliar o desempenho duma aplicação paralela. As mais conhecidas são:

SpeedupEficiênciaRedundânciaUtilizaçãoQualidade

Existem igualmente várias leis/métricas que permitem balizar o comportamento duma aplicação paralela face ao seu potencial desempenho. As mais conhecidas são:

Lei de AmdahlLei de Gustafson-BarsisMétrica de Karp-FlattMétrica de Isoeficiência

Page 4: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

4

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

7

SpeedupSpeedupO speedup é uma medida do grau de desempenho. O speedup mede o rácio entre o tempo de execução sequencial e o tempo de execução em paralelo.

T(1) é o tempo de execução com um processadorT(p) é o tempo de execução com p processadores

)()1()(

pTTpS =

10,006,253,571,921S(p)

1001602805201000T(p)

16 CPUs8 CPUs4 CPUs2 CPUs1 CPU

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

8

EficiênciaEficiênciaA eficiência é uma medida do grau de aproveitamento dos recursos computacionais. A eficiência mede o rácio entre o grau de desempenho e os recursos computacionais disponíveis.

S(p) é o speedup para p processadores

)()1()()(pTp

TppSpE

×==

0,630,780,890,961E(p)

10,006,253,571,921S(p)

16 CPUs8 CPUs4 CPUs2 CPUs1 CPU

Page 5: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

5

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

9

RedundânciaRedundânciaA redundância é uma medida do grau de aumento da computação. A redundância mede o rácio entre o número de operações realizadas pela execução paralela e pela execução sequencial.

O(1) é o número total de operações realizadas com 1 processadorO(p) é o número total de operações realizadas com p processadores

)1()()(

OpOpR =

1,501,231,101,031R(p)

1500012250110001025010000O(p)

16 CPUs8 CPUs4 CPUs2 CPUs1 CPU

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

10

UtilizaçãoUtilizaçãoA utilização é uma medida do grau de aproveitamento da capacidade computacional. A utilização mede o rácio entre a capacidade computacional utilizada durante a computação e a capacidade disponível.

)()()( pEpRpU ×=

1,501,231,101,031R(p)

0,950,960,980,991U(p)

0,630,780,890,961E(p)

16 CPUs8 CPUs4 CPUs2 CPUs1 CPU

Page 6: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

6

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

11

QualidadeQualidadeA qualidade é uma medida do grau de importância de utilizar programação paralela.

0,630,780,890,961E(p)

1,501,231,101,031R(p)

10,006,253,571,921S(p)

4,203,962,891,791Q(p)

16 CPUs8 CPUs4 CPUs2 CPUs1 CPU

)()()()(

pRpEpSpQ ×

=

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

12

Lei de Lei de AmdahlAmdahlA computação realizada por uma aplicação paralela pode ser divididas em 3 classes:

C(seq): computações que só podem ser realizadas sequencialmente.C(par): computações que podem ser realizadas em paralelo.C(com): computações de comunicação/sincronização/iniciação.

Usando estas 3 classes, o speedup de uma aplicação pode definido do seguinte modo:

)()()(

)()()()1()(

comCpparCseqC

parCseqCpT

TpS++

+==

Page 7: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

7

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

13

Lei de Lei de AmdahlAmdahlComo C(com) ≥ 0 então:

Se f for a fracção da computação que só pode ser realizada sequencialmente então:

pparCseqC

parCseqCpS )()(

)()()(+

+≤

pf

seqCseqC

fseqC

pSparCseqC

seqCf

⎟⎟⎠

⎞⎜⎜⎝

⎛−×

+

≤+

=11)(

)(

)(

)( e )()(

)(

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

14

Lei de Lei de AmdahlAmdahlSimplificando:

pff

pS

pf

fpS

pf

seqCseqC

fseqC

pS

−+

≤⇒−

+

≤⇒

⎟⎟⎠

⎞⎜⎜⎝

⎛−×

+

11)(

11

1

1

)(

11)()(

)(

)(

Page 8: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

8

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

15

Lei de Lei de AmdahlAmdahlSeja 0 ≤ f ≤ 1 a fracção da computação que só pode ser realizada sequencialmente. A lei de Amdahl diz-nos que o speedup máximo que uma aplicação paralela com pprocessadores pode obter é:

A lei de Amdahl dá-nos uma medida do speedup máximo que podemos obter ao resolver um determinado problema com p processadores.A lei de Amdahl também pode ser utilizada para determinar o limite máximo de speedup que uma determinada aplicação poderá alcançar independentemente do número de processadores a utilizar.

pff

pS−

+≤ 1

1)(

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

16

Lei de Lei de AmdahlAmdahlSuponha que pretende determinar se é vantajoso desenvolver uma versão paralela de uma determinada aplicação sequencial. Por experimentação, verificou-se que 90% do tempo de execução é passado em procedimentos que se julga ser possível paralelizar. Qual é o speedup máximo que se pode alcançar com uma versão paralela do problema executando em 8 processadores?

E o limite máximo de speedup que se pode alcançar?

71,4

81,011,0

1)( ≈−

+≤pS

101,011,0

1lim =−

+∞→

pp

Page 9: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

9

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

17

Limitações da Lei de Limitações da Lei de AmdahlAmdahlA lei de Amdahl ignora o custo das operações de comunicação/sincronização associadas à introdução de paralelismo numa aplicação. Por esse motivo, a lei de Amdahl pode resultar em predições pouco realísticas para determinados problemas. Suponha que desenvolveu uma aplicação paralela cujo padrão de execução é o seguinte, em que n é o tamanho do problema:

Tempo de execução da parte sequencial (input e output de dados):

Tempo de execução da parte paralelizável:

Total de pontos de comunicação/sincronização por processador:

Tempo de execução por comunicação/sincronização:

⎡ ⎤nlog100

2n

n+000.18

⎡ ⎤ 10log000.10 np +×

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

18

Limitações da Lei de Limitações da Lei de AmdahlAmdahlQual é o speedup máximo que se pode obter?

Utilizando a lei de Amdahl:

Utilizando a medida de speedup:

100000.18

100000.18

)( e

100000.18

000.182

2

2

×++

++≤

++

+=

pnn

nnpS

nn

nf

⎡ ⎤ ⎡ ⎤ ⎟⎠⎞

⎜⎝⎛ +××+

×++

++=

10log000.10log

100000.18

100000.18

)( 2

2

npnp

nn

nnpS

Page 10: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

10

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

19

Limitações da Lei de Limitações da Lei de AmdahlAmdahl

Speedup

Lei deAmdahl

14,827,713,941,991n = 30.000

14,027,513,891,981n = 20.000

2,572,222,111,611n = 10.000

6,644,713,211,871n = 20.000

11,366,723,701,951n = 10.000

9,295,893,551,931n = 30.000

16 CPUs8 CPUs4 CPUs2 CPUs1 CPU

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

20

Lei de Lei de GustafsonGustafson--BarsisBarsisConsideremos novamente a medida de speedup definida anteriormente:

Se f for a fracção da computação paralela realizada a executar computações sequenciais então:

pparCseqC

parCseqCpS )()(

)()()(+

+≤

( )

pC(par)C(seq)

pC(par)

f

pparCseqC

seqCf+

=−+

= 1 e )()(

)(

Page 11: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

11

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

21

Lei de Lei de GustafsonGustafson--BarsisBarsisLogo:

Simplificando:

⎟⎟⎠

⎞⎜⎜⎝

⎛+×−×=

⎟⎟⎠

⎞⎜⎜⎝

⎛+×=

pparCseqCfpparC

pparCseqCfseqC

)()()1()(

)()()(

( )( )

( ) ( )pfppSfpfpSpparCseqC

pparCseqCfpf

pS

−×+≤⇒−×+≤⇒

+

⎟⎟⎠

⎞⎜⎜⎝

⎛+×−×+

1)( 1)(

)()(

)()(1)(

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

22

Lei de Lei de GustafsonGustafson--BarsisBarsisSeja 0 ≤ f ≤ 1 a fracção da computação paralela realizada a executar computações sequenciais. A lei de Gustafson-Barsis diz-nos que o speedup máximo que uma aplicação paralela com p processadores pode obter é:

Enquanto a lei de Amdahl parte do tempo de execução sequencial para estimar o speedup máximo passível de ser conseguido em múltiplos processadores, a lei de Gustafson-Barsis faz precisamente o contrário, ou seja, parte do tempo de execução em paralelo para estimar o speedup máximo comparado com a execução sequencial.

( )pfppS −×+≤ 1)(

Page 12: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

12

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

23

Lei de Lei de GustafsonGustafson--BarsisBarsisConsidere que uma determinada aplicação executa em 220 segundos em 64 processadores. Qual é o speedup máximo da aplicação sabendo que por experimentação verificou-se que 5% do tempo de execução é passado em computações sequenciais.

Suponha que uma determinada companhia pretende comprar um supercomputadorcom 16.384 processadores de modo a obter um speedup de 15.000 num problema de fundamental importância. Qual é a fracção máxima da execução paralela que pode ser passada em computações sequenciais de modo a se atingir o speedup pretendido?

85,6015,364)641()05,0(64)( =−=−×+≤pS

084,0384.1383.16

)384.161(384.16000.15

≤≤×

−×+≤

ff

f

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

24

Limitações da Lei de Limitações da Lei de GustafsonGustafson--BarsisBarsisAo usar o tempo de execução em paralelo como o ponto de partida, em lugar do tempo de execução sequencial, a lei de Gustafson-Barsis assume que a execução com um só processador é no pior dos casos p vezes mais lenta que a execução com pprocessadores.Isso pode não ser verdade se a memória disponível para a execução com um só processador for insuficiente face à computação realizada pelos p processadores. Por este motivo, o speedup estimado pela lei de Gustafson-Barsis é habitualmente designado por scaled speedup.

Page 13: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

13

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

25

Métrica de Métrica de KarpKarp--FlattFlattConsideremos novamente a definição do tempo de execução sequencial e do tempo de execução em paralelo:

Seja e a fracção sequencial determinada experimentalmente duma computação paralela:

)()()()(

)()()1(

comCpparCseqCpT

parCseqCT

++=

+=

)1()(

TseqCe =

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

26

Métrica de Métrica de KarpKarp--FlattFlattLogo:

Se considerarmos que C(com) é desprezável então:

Por outro lado:

)1()1()()1()(

TeparCTeseqC×−=

×=

)()()1( )()1()(

pTpSTpT

TpS

×=⇒

=

pTeTepT )1()1()1()( ×−

+×=

Page 14: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

14

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

27

Métrica de Métrica de KarpKarp--FlattFlattSimplificando:

p

ppSepp

epS

pe

pe

pSpee

pS

ppSepSe

ppTpSepTpSepT

11

1)(

1

111)(

1

1)(

1 )1()(

1

)()1()(1

)()()1()()()(

−=⇒+⎟⎟

⎞⎜⎜⎝

⎛−×=⇒

−+=⇒−

+=⇒

×−+×=⇒

××−+××=

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

28

Métrica de Métrica de KarpKarp--FlattFlattSeja S(p) o speedup duma aplicação paralela com p > 1 processadores. A métrica de Karp-Flatt diz-nos que a fracção sequencial determinada experimentalmente é:

A métrica de Karp-Flatt é interessante porque ao desprezar o custo das operações de comunicação/sincronização/iniciação associadas à introdução de paralelismo numa aplicação, permite-nos determinar à posteriori qual a importância da componente C(com) no eventual decréscimo de eficiência da aplicação.

p

ppSe 11

1)(

1

−=

Page 15: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

15

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

29

Métrica de Métrica de KarpKarp--FlattFlattPor definição, a fracção sequencial determinada experimentalmente é um valor constante que não depende do número de processadores.

Por outro lado, a métrica de Karp-Flatt é uma função do número de processadores.

)1()(

TseqCe =

p

ppSe 11

1)(

1

−=

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

30

Métrica de Métrica de KarpKarp--FlattFlattComo a eficiência duma aplicação é uma função decrescente do número de processadores, a métrica de Karp-Flatt permite-nos determinar qual a importância da componente C(com) nesse decréscimo.

Se os valores de e forem constantes à medida que o número de processadores aumentaisso significa que a componente C(com) é também constante. Logo, o decréscimo da eficiência é devido à existência de pouco paralelismo no problema.Se os valores de e aumentarem à medida que o número de processadores aumenta isso significa que o decréscimo é devido à componente C(com), ou seja, à existência de custos excessivos associados à computação em paralelo (custos de comunicação, sincronização e/ou iniciação da computação).

Page 16: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

16

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

31

Métrica de Métrica de KarpKarp--FlattFlattPor exemplo, a métrica de Karp-Flatt permite-nos detectar fontes de ineficiência não consideradas pelo modelo que assume que p processadores executam a parte que pode ser paralelizável p vezes mais rápido do que a execução com um só processador.

Se tivermos 5 processadores para resolver um problema decomposto em 20 tarefas indivisíveis, todos os processadores podem executar 4 tarefas. Se todas as tarefas demorarem o mesmo tempo a executar então o tempo de execução em paralelo será uma razão de 4.Por outro lado, se tivermos 6 processadores para resolver o mesmo problema, 4 processadores podem executar 3 tarefas mas dois deles terão necessariamente de executar 4. Isto faz com que o tempo de execução em paralelo seja igualmente uma razão de 4 e não uma razão de 20/6.

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

32

Métrica de Métrica de KarpKarp--FlattFlattConsidere os seguintes speedups obtidos por uma determinada aplicação paralela:

Qual é a principal razão para a aplicação obter apenas um speedup de 4,71 com 8 processadores?

Como e não aumenta com o número de processadores, isso significa que a principal razão para o baixo speedup é a falta de paralelismo existente no problema.

0,1000,1000,1000,1000,1000,1000,099e

4,714,384,003,573,082,501,82S(p)

6 CPUs 7 CPUs 8 CPUs5 CPUs4 CPUs3 CPUs2 CPUs

Page 17: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

17

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

33

Métrica de Métrica de KarpKarp--FlattFlattConsidere os seguintes speedups obtidos por uma determinada aplicação paralela:

Qual é a principal razão para a aplicação obter apenas um speedup de 4,71 com 8 processadores?

Como e aumenta ligeiramente com o número de processadores, isso significa que a principal razão para o baixo speedup são os custos associados à computação em paralelo.

4,714,464,143,733,232,611,87S(p)

0,1000,0950,0900,0850,0790,0750,070e

6 CPUs 7 CPUs 8 CPUs5 CPUs4 CPUs3 CPUs2 CPUs

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

34

Eficiência e Eficiência e EscalabilidadeEscalabilidadeDos resultados anteriores podemos concluir que a eficiência duma aplicação é:

Uma função decrescente do número de processadores.Tipicamente uma função crescente do tamanho do problema.

Page 18: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

18

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

35

Eficiência e Eficiência e EscalabilidadeEscalabilidadeUma aplicação é dita de escalável quando demonstra a capacidade de manter a mesma eficiência à medida que o número de processadores e a complexidade do problema aumentam proporcionalmente.A escalabilidade duma aplicação reflecte a sua capacidade de utilizar mais recursos computacionais de forma efectiva.

Eficiência

0,160,280,530,811n = 10.000

0,420,590,800,941n = 20.000

0,580,740,890,961n = 30.000

16 CPUs8 CPUs4 CPUs2 CPUs1 CPU

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

36

Métrica de Métrica de IsoeficiênciaIsoeficiênciaA eficiência duma aplicação é tipicamente uma função crescente do tamanho do problema porque a complexidade de comunicação é habitualmente inferior à complexidade da computação, ou seja, a forma de manter o mesmo nível de eficiência quando aumentamos o número de processadores é aumentar o tamanho do problema. A métrica de isoeficiência formaliza esta ideia.Consideremos novamente a medida de speedup definida anteriormente:

( )

( ))()()1()()(

)()(

)()()()()(

)()()(

)()()(

comCpseqCpparCseqCparCseqCp

comCpparCseqCpparCseqCp

comCpparCseqC

parCseqCpS

×+×−+++×

=

×++×+×

=++

+=

Page 19: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

19

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

37

Métrica de Métrica de IsoeficiênciaIsoeficiênciaSeja T0(p) o tempo de execução dispendido pelos p processadores do algoritmo paralelo a realizar computações não realizadas pelo algoritmo sequencial:

Simplificando:

)()()1()(0 comCpseqCppT ×+×−=

( )

)1()(1

1

)()()(1

1)()()(

)()()(

)()()()()()(

000

0

TpT

parCseqCpTpTparCseqC

parCseqCpE

pTparCseqCparCseqCppS

+=

++

=++

+=

+++×

=

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

38

Métrica de Métrica de IsoeficiênciaIsoeficiênciaEntão:

Se pretendermos manter o mesmo nível de eficiência quando aumentamos o número de processadores então:

)()(1

)()1( )(

)(1)1()(

)1()(1

1)(

00

0

pTpE

pETpE

pET

pTT

pTpE

×−

=⇒−

=⇒

+=

)()1( e )(1

)(0 pTcTc

pEpE

×≥=−

Page 20: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

20

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

39

Métrica de Métrica de IsoeficiênciaIsoeficiênciaSeja E(p) a eficiência duma aplicação paralela com p processadores. A métrica de isoeficiência diz-nos que para se manter o mesmo nível de eficiência quando aumentamos o número de processadores então o tamanho do problema deve ser aumentado de forma a que a seguinte desigualdade seja satisfeita:

A aplicação da métrica de isoeficiência pode depender da quantidade de memória disponível, pois o tamanho máximo do problema que pode ser resolvido é limitado por essa quantidade.

)()()1()( e )(1

)( que em

)()1(

0

0

comCpseqCppTpE

pEc

pTcT

×+×−=−

=

×≥

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

40

Métrica de Métrica de IsoeficiênciaIsoeficiênciaSuponha que a métrica de isoeficiência para um problema de tamanho n nos é dada por uma função do número de processadores p:

Se M(n) designar a quantidade de memória necessária para resolver o problema de tamanho n então:

Ou seja, para se manter o mesmo nível de eficiência, a quantidade de memória necessária por processador é:

)( pfn ≥

( ))( pfMn ≥

( )p

pfM )(

Page 21: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

21

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

41

Métrica de Métrica de IsoeficiênciaIsoeficiência

Eficiência não pode sermantida e deve decrescer

Mem

ória por processador

Número de processadores

Eficiência podeser mantida

limite de memória

ppc log××

pc×

c

pc log×

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

42

Métrica de Métrica de IsoeficiênciaIsoeficiênciaConsidere que a versão sequencial de uma determinada aplicação tem complexidade O(n3) e que o tempo de execução dispendido por cada um dos p processadores da versão paralela em operações de comunicação/sincronização é O(n2 log p). Se a quantidade de memória necessária para representar um problema de tamanho n for n2, qual é a escalabilidade da aplicação em termos de memória?

Logo, a escalabilidade da aplicação é baixa.

ppcp

ppcp

ppcMnnM

ppcnpnpcn

22222

2

23

loglog)log( )(

loglog

××=××

=××

⇒=

××≥×××≥

Page 22: Programação Paralela e Distribuída Métricas de Desempenhoricroc/aulas/0708/ppd/apontamentos/... · Métricas de Desempenho para Aplicações Paralelas: métricas que permitem

22

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

43

SpeedupSpeedup SuperlinearSuperlinearO speedup diz-se superlinear quando o rácio entre o tempo de execução sequencial e o tempo de execução em paralelo com p processadores é maior do que p.

Alguns dos factores que podem fazer com que o speedup seja superlinear são:Custos de comunicação/sincronização/iniciação praticamente inexistentes.Tolerância à latência da comunicação.Aumento da capacidade de memória (o problema passa a caber todo em memória).Subdivisão do problema (tarefas menores geram menos cache misses).Aleatoriedade da computação em problemas de optimização ou com múltiplas soluções.

ppT

T≥

)()1(

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2007/08 Métricas de Desempenho

44

“Se um único computador (processador) consegue resolver um problemaem N segundos, podem N computadores (processadores)

resolver o mesmo problema em 1 segundo?”

SpeedupSpeedup SuperlinearSuperlinear