AnaliseEComplexidadeDeAlgoritmosAula10e17Mar2015

Análise e Complexidade de Algoritmos
Professor Ricardo Mesquita
AULA-01 10/03/2015

Conceitos Fundamentais
Desempenho Computacional
Intuitivamente, esperamos que uma máquina (ou processo) de alto desempenho tenha suas tarefas rapidamente executadas. Temos:
Desempenho =

1 tempo de execução

A PERCEPÇÃO PODE SER SUBJETIVA.

A noção de desempenho relativo de duas máquinas (ou dois programas).
Sejam M1 e M2 duas máquinas. desempenho de M1 desempenho de M2
= Speedup

=

tempo de execução M2 tempo de execução M1

de M1 sobre M2.

O DESEMPENHO RELATIVO É UMA GRANDEZA ADIMENSIONAL

Diz-se: M1 oferece X vezes o desempenho M2. ou M1 é X vezes mais rápida ( se x > 1)
Ex: M1 é 1,5 vezes mais rápida que M2 x= 1,5 em percentual use 100 * (x-1)%
M1 é 50% mais rápida que M2
OBS: y% mais rápida = 1 +

y vezes mais rápida.
100

Tempo de Execução na CPU tCPU = no de instruções X no de ciclos de CPU por instrução X x duração de cada ciclo ou tCPU = instruções x CPI / taxa de clock (CPI= cicleo per instruction)

Lei de Amdahl
Se f representa a fração do tempo de execução de um programa devido a computações não-paralelizáveis.
Temos:
S=

1 f + (1-f) p <= min (p. 1) f S= speedup
P= processadores

Ex: Um processador é usado para aplicações nas quais 30% do tempo é gasto em adição de ponto flutuante, 25% em multiplicações e 10% em divisões de pontos flutuantes. Para um novo modelo de processador, a equipe apresentou três aperfeiçoamentos possíveis, cada um custando quase o mesmo em espaços de projeto e manutenção. Qual dos seguintes aperfeiçoamentos deve ser escolhido?
a) Somador 2 vezes mais rápido
b) Multiplicador 3 vezes mais rápido
c) Divisor 10 vezes mais rápido.
RESOLUÇÃO:
a) Somador 2 vezes mais rápido
30% = 0,3 = fração das adições
0,7 = fração das demais operações
S=

1
0,7 + 0,3
2

=

1
=
1
0,7 + 0,15
0,85

b) Multiplicador 3 vezes mais rápido
25% = 0,25 => fração de multiplicação
0,75 demais operações
S=

1
= 1,20 melhora 20%
0,75+ 0,25
3

c) Divisor 10 vezes mais rápido.