Programação Paralela e Distribuída Métricas de Desempenhofds/aulas/PPD/1314/Slides/metricas.pdf · Ricardo Rocha DCC-FCUP Programação Paralela e Distribuída 2010/11 Métricas

Ricardo Rocha DCC-FCUP

Programação Paralela e Distribuída 2010/11 Métricas de Desempenho

1

Programação Paralela e Distribuída

Métricas de Desempenho



2

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



3

Limites ao Desempenho !   Limites Arquitecturais

!   Latência e Largura de Banda !   Coerência dos Dados !   Capacidade de Memória

!   Limites Algorítmicos !   Falta de Paralelismo (código sequencial/concorrência) !   Frequência de Comunicação !   Frequência de Sincronização !   Escalonamento Deficiente (granularidade das tarefas/balanceamento de carga)



4

Métricas de Desempenho !   Existem 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.



5

Métricas de Desempenho para Processadores !   Algumas 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).



6

Métricas de Desempenho para Aplicações Paralelas !   Existem várias medidas que permitem medir/avaliar o desempenho duma aplicação

paralela. As mais conhecidas são: !   Speedup !   Eficiência !   Redundância !   Utilização !   Qualidade

!   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 Amdahl !   Lei de Gustafson-Barsis !   Métrica de Karp-Flatt !   Métrica de Isoeficiência



7

Speedup !   O 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 processador T(p) é o tempo de execução com p processadores

)()1()(pT

TpS =

1 CPU 2 CPUs 4 CPUs 8 CPUs 16 CPUs

T(p) 1000 520 280 160 100

S(p) 1 1,92 3,57 6,25 10,00



8

Eficiência !   A 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

×==


S(p) 1 1,92 3,57 6,25 10,00

E(p) 1 0,96 0,89 0,78 0,63



9

Redundância !   A 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 processador O(p) é o número total de operações realizadas com p processadores

)1()()(

OpOpR =


O(p) 10000 10250 11000 12250 15000

R(p) 1 1,03 1,10 1,23 1,50



10

Utilização !   A 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 ×=


R(p) 1 1,03 1,10 1,23 1,50

E(p) 1 0,96 0,89 0,78 0,63

U(p) 1 0,99 0,98 0,96 0,95



11

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


S(p) 1 1,92 3,57 6,25 10,00

E(p) 1 0,96 0,89 0,78 0,63

R(p) 1 1,03 1,10 1,23 1,50

Q(p) 1 1,79 2,89 3,96 4,20

)()()()(

pRpEpSpQ ×

=



12

Lei de Amdahl !   A 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 ser definido do seguinte modo:

)()()(

)()()()1()(

comCpparCseqC

parCseqCpT

TpS++

+==



13

Lei de Amdahl !   Como 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 )()(

)(



14

Lei de Amdahl !   Simplificando:

pff

pS

pf

fpS

pf

seqCseqC

fseqC

pS

−+

≤⇒−

+

≤⇒

⎟⎟⎠

⎞⎜⎜⎝

⎛−×

+

≤

11)(

11

1

1

)(

11)()(

)(

)(



15

Lei de Amdahl !   Seja 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 p processadores 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)(



16

Lei de Amdahl !   Suponha 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



17

Limitações da Lei de Amdahl !   A 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 realistas para determinados problemas.

!   Suponha que desenvolveu uma aplicação paralela, com complexidade O(n2), 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 devido a comunicação/sincronização (n=10.000):

⎡ ⎤nlog100

2nn+000.18

⎡ ⎤ 10log000.10 np +×



18

Limitações da Lei de Amdahl !   Qual é 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

npnpnn

nnpS



19

Limitações da Lei de Amdahl


Lei de Amdahl

n = 10.000 1 1,95 3,70 6,72 11,36

n = 20.000 1 1,98 3,89 7,51 14,02

n = 30.000 1 1,99 3,94 7,71 14,82

Speedup

n = 10.000 1 1,61 2,11 2,22 2,57

n = 20.000 1 1,87 3,21 4,71 6,64

n = 30.000 1 1,93 3,55 5,89 9,29



20

Lei de Gustafson-Barsis !   Consideremos 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 (1-f) é a fracção de tempo gasto na computação paralela:

pparCseqC

parCseqCpS )()(

)()()(+

+≤

( )

pC(par)C(seq)

pC(par)

f

pparCseqC

seqCf+

=−+

= 1 e )()(

)(



21

Lei de Gustafson-Barsis !   Logo:

!   Simplificando:

⎟⎟⎠

⎞⎜⎜⎝

⎛+×−×=

⎟⎟⎠

⎞⎜⎜⎝

⎛+×=

pparCseqCfpparC

pparCseqCfseqC

)()()1()(

)()()(

( )( )

( ) ( )pfppSfpfpSpparCseqC

pparCseqCfpf

pS

−×+≤⇒−×+≤⇒

+

⎟⎟⎠

⎞⎜⎜⎝

⎛+×−×+

≤

1)( 1)(

)()(

)()(1)(



22

Lei de Gustafson-Barsis !   Seja 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)(



23

Lei de Gustafson-Barsis !   Considere 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 supercomputador com 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



24

Limitações da Lei de Gustafson-Barsis !   Ao 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 p processadores.

!   Isto 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.



25

Métrica de Karp-Flatt !   Consideremos 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 =



26

Métrica de Karp-Flatt !   Logo:

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

!   Por outro lado:

)1()1()()1()(TeparC

TeseqC×−=

×=

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

pTpSTpT

TpS

×=⇒

=

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

+×=



27

Métrica de Karp-Flatt !   Simplificando:

p

ppSepp

epS

pe

pe

pSpee

pS

ppSepSe

ppTpSepTpSepT

11

1)(

1

111)(

1

1)(

1 )1()(

1

)()1()(1

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

−

−=⇒+⎟⎟

⎠

⎞⎜⎜⎝

⎛−×=⇒

−+=⇒−

+=⇒

×−+×=⇒

××−+××=



28

Métrica de Karp-Flatt !   Seja 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

−

−=



29

Métrica de Karp-Flatt !   Por 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

−

−=



30

Métrica de Karp-Flatt !   Como 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 aumenta

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



31

Métrica de Karp-Flatt !   Por 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 5.

!   Por outro lado, se tivermos 6 processadores para resolver o mesmo problema, 4 processadores podem executar 3 tarefas mas 2 deles terão necessariamente de executar 4. Isto faz com que o tempo de execução em paralelo seja igualmente uma razão de 5 e não uma razão de 6.



32

Métrica de Karp-Flatt !   Considere 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.

2 CPUs 3 CPUs 4 CPUs 5 CPUs 6 CPUs 7 CPUs 8 CPUs

S(p) 1,82 2,50 3,08 3,57 4,00 4,38 4,71

e 0,099 0,100 0,100 0,100 0,100 0,100 0,100



33

Métrica de Karp-Flatt !   Considere 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.

2 CPUs 3 CPUs 4 CPUs 5 CPUs 6 CPUs 7 CPUs 8 CPUs

S(p) 1,87 2,61 3,23 3,73 4,14 4,46 4,71

e 0,070 0,075 0,079 0,085 0,090 0,095 0,100



34

Eficiência e Escalabilidade !   Dos 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.



35

Eficiência e Escalabilidade !   Uma 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 dimensão do problema aumentam proporcionalmente.

!   A escalabilidade duma aplicação reflecte a sua capacidade de utilizar mais recursos computacionais de forma efectiva.


Eficiência

n = 10.000 1 0,81 0,53 0,28 0,16

n = 20.000 1 0,94 0,80 0,59 0,42

n = 30.000 1 0,96 0,89 0,74 0,58



36

Métrica de Isoeficiência !   A 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

×+×−++

+×=

×++×

+×=

++

+=



37

Métrica de Isoeficiência !   Seja 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

+=

++

=++

+=

++

+×=



38

Métrica de Isoeficiência !   Entã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

pTpEpET

pEpE

TpT

TpTpE

×−

=⇒−

=⇒

+=

)()1( e )(1

)(0 pTcTc

pEpE

×≥=−



39

Métrica de Isoeficiência !   Seja 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

comCpseqCppTpEpEc

pTcT

×+×−=−

=

×≥



40

Métrica de Isoeficiência !   Suponha 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 ≥

( ))()( pfMnM ≥

( )ppfM

pnM )()(≥



41

Métrica de Isoeficiência

Mem

ória por processador

Eficiência não pode ser mantida e deve decrescer

Eficiência pode ser mantida

Número de processadores

limite de memória

ppc log××

pc×

c

pc log×



42

Métrica de Isoeficiência !   Considere 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

××=××

=××

⇒=

××≥

×××≥



43

Speedup Superlinear !   O 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(



44

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

resolver o mesmo problema em 1 segundo?”

Speedup Superlinear

Documents

Programação Paralela e Distribuída Métricas de Desempenhofds/aulas/PPD/1314/Slides/metricas.pdf · Ricardo Rocha DCC-FCUP Programação Paralela e Distribuída 2010/11 Métricas