Análise de Desempenho

Analíticos
– Determinísticos
 Melhor e pior casos
– Probabilisticos
 Valores prováveis

Simulação


Análise exaustiva
Implementação real
– Medidas obtidas do sistema real
– Benchmarks
– Protótipos
Redes de Petri
Níveis
de
Abstração
Obj.RdP
Espaço dos
Formalismos
Pr/T, CPN
P,T
Sinais Externos
Limites
Predicados
Intervalo
Detreminístico
Estocástico
Autônomo
CE, EN
Temporizado Dados Interpretados
Interpretações
Redes Temporizadas
Extensões
Temporizadas
Token-Timed
PN
Stochastic
PN
……
Transition-Timed
PN
Time
PN
Place-Timed
PN
Timed
PN
Redes Temporizadas
Extensões
Temporizadas
Token-Timed
PN
Stochastic
PN
……
Transition-Timed
PN
Time
PN
Place-Timed
PN
Timed
PN
Redes Temporizadas



Ramchandani, 1973 - Transition Timed Net
Merlin, 1976 - Transition Time Net
Sifakis, 1977 - Place Timed Net
Redes Temporizadas
Estocásticas
 Natkin
-1980
 Molloy - 1981
 Marsan et al. - 1984
É uma rede temporizada onde o delay
associado à transição é uma variável aleatória
de distribuição exponencial
Redes Temporizadas

Redes de Petri com Lugares Temporizados (PTPN)
(Sifakis77)
Definição: PTPN=(P,T,F,K,W,M0,,), onde
P é o conjunto de lugares,
T o conjunto de transições,
F  (P  T)  (T  P) uma relação que representa os arcos
W – Valoração (peso dos arcos) - W: F  N
M0- Marcação inicial - M0:P  N
={1, 2,…, i,…} números reais denominada base de tempo.
:P   um mapeamato que (p) = j

Redes Temporizadas
- PTPN 
Regra de Disparo
p1
2
2
t0
(p0) = 3
p0
t1
Redes Temporizadas
- PTPN 
Regra de Disparo
p1
2
2
t0
(p0) = 3
p0
t1
Instante=0
Redes Temporizadas
- PTPN 
Regra de Disparo
p1
2
2
t0
(p0) = 3
p0
t1
Instante=1
Redes Temporizadas
- PTPN 
Regra de Disparo
p1
2
2
t0
(p0) = 3
p0
t1
Instante=2
Redes Temporizadas
- PTPN 
Regra de Disparo
p1
2
2
t0
(p0) = 3
p0
t1
Instante=3
Redes de Petri Temporizadas
- Tempo Associado às Transições -

Conceitos Básicos:
– Duração (disparo em três fases)



Marcas são consumidas dos lugares de entrada
Há uma duração
Marcas são geradas no lugares de saída
– Disparo atômico

As marca permanecem nos lugares de entrada
pelo período igual ao delay associada à
transição. Após o delay as marcas são
consumidas e geradas nos lugares de saída
imediatamente.
Redes de Petri Temporizadas
- Tempo Associado às Transições -

Conceitos Básicos:
– Duração (disparo em três fases)



Pode ser representada por uma rede com
disparo atômico
Modelo mais compacto
O estado é uma informação mais complexa do
que o modelo não-temporizado
– Disparo atômico


Pode representar o modelo com duração
O conjunto de marcações alcançáveis é um
sub-conjunto das marcações do modelo nãotemporizado.
Redes de Petri Temporizadas
- Tempo Associado às Transições -

Conceitos Básicos:
– Regras de Seleção:

Pré-seleção: (duração e delay)
– Prioridade
– Probabilidade

Race (corrida): (delay)
– Transições habilitadas com menor delay são
disparadas
Redes de Petri Temporizadas
- Tempo Associado às Transições -
 Conceitos
Básicos:
– Quando uma das transições
conflitantes é desabilitada pelo
disparo da outra, o que acontece com
o timer da que ficou desabilitada
quando a mesma tornar-se habilitada
outra vez?
Redes de Petri Temporizadas
- Tempo Associado às Transições -


Como fica a memorização
do tempo de habilitação
anterior?
Continue
da
– O timer associado à
transição mantem o valor
atual e quando a transição
se tornar novamente
habilitada o valor do timer
iniciará daquele valor.

p0
Restart
– Quando a transição for
novamente habilitada o timer
ta
db
p1
p2
tb
Redes de Petri Temporizadas
- Tempo Associado às Transições -
 Conceitos
Básicos:
– O que acontece com o timer das
transições habilitadas após o disparo
de uma transição?

Todas as transições. Não somente as
transições conflitantes.
•Algumas políticas de memória podem ser construídas
Redes de Petri Temporizadas
- Tempo Associado às Transições -
 Conceitos
Básicos:
– Resampling
 Após cada disparo os timers de TODAS
as transições são re-iniciado (restart)
 Não há memória
 Após descartar todos os timers, os
valores iniciais são associados a todas as
transições que se tornarem habilitadas
na nova marcação.
Redes de Petri Temporizadas
- Tempo Associado às Transições -
 Conceitos
Básicos:
– Enabling Memory
 Após cada disparo os timers
das
transições que ficaram desabilitadas são
re-iniciados (restart)
 As transições que permaneceram
habilitadas com o disparo matêem seus
valores presentes(continue)
Redes de Petri Temporizadas
- Tempo Associado às Transições -
 Conceitos
Básicos:
– Age Memory
 Após cada disparo os timers
de
todas as transições são mantidos em
seus valores presentes (continue)
Redes de Petri Temporizadas
- Tempo Associado às Transições -
 Conceitos Básicos:
– Grau de Habilitação
(Enabling Degree)


É o número de vezes que
uma determinada transição
pode ser disparada, numa
determinada marcação,
antes de se torna
desabilitada.
Quando o grau de
habilitação é maior que
um, atenção especial à
semântica de temporização
deve ser considerada.
p1
p0
ta
d
p1
Redes de Petri Temporizadas
- Tempo Associado às Transições -
 Conceitos Básicos:
– Semântica de Temporização

Single-server firing semantics

Infinite-server firing semantics

Multiple-server firing semantics
– K é o máximo grau de paralelismo. Quando
k , Multiple-server firing semantics é
igual a infinite-server firing semantics.
Redes de Petri Temporizadas
- Tempo Associado às Transições -

Conceitos Básicos:
– Single-server firing
semantics
p0
ta
p1
d=3
t=3
t=6
t=9
t
Redes de Petri Temporizadas
- Tempo Associado às Transições -

Conceitos Básicos:
– Infinite-server firing
semantics
p0
ta
p1
d=3
t=3
t
Redes de Petri Temporizadas
- Tempo Associado às Transições -

Conceitos Básicos:
– Multiple-server firing
semantics k=2
p0
ta
p1
d=3
t=3
t=6
t
Redes Temporizadas
com Transições Temporizadas

Time Petri Nets (Merlin76)
Definição: TPN=(P,T,F, W,M0,I), onde
P é o conjunto de lugares,
T o conjunto de transições,
F  (P  T)  (T  P) uma relação que representa os arcos
W – Valoração (peso dos arcos) - W: F  
M0- Marcação inicial - M0:P  
I : T  (+  {0})  (+  {0}), onde I(ti)=(dimin, dimax),
dimax dimin
TC: T   é uma função parcial que associa as transições um

timer clock
Redes Temporizadas
com Transições Temporizadas
Semântica de Disparo de Transição
 Uma transição tj é disparável se estiver habilitada
– Regras de habilitação
M[tj > ,
M(pi) >=I(pi, tj)
 pi P
durante o intervalo I(tj)=(djmin, djmax),
Ou seja, tj só será disparável se tc(tj)  djmin
 e terá que disparar até tc(tj)  djmax (strong semantics)
ou
 e poderá disparar até tc(tj)  djmax (weak semantics)


Resampling
Regras de disparo
Se M[tj >M’
Redes Temporizadas
com Transições Temporizadas
p0
t0
[3,5]
M0
p1
t1
[1,3]
p2
tc(t0)=1
tc(t1)= indefinido
Redes Temporizadas
com Transições Temporizadas
p0
t0
[3,5]
M0
p1
t1
[1,3]
p2
tc(t0)=2
tc(t1)= indefinido
Redes Temporizadas
com Transições Temporizadas
p0
t0
[3,5]
p1
t1
[1,3]
M0
t0 pode disparar
p2
tc(t0)=3
tc(t1)= indefinido
Redes Temporizadas
com Transições Temporizadas
p0
t0
[3,5]
M0
p1
t1
[1,3]
p2
tc(t0)=4
tc(t1)= indefinido
Redes Temporizadas
com Transições Temporizadas
p0
t0
[3,5]
M0
t0
M1
p1
t1
[2,4]
p2
tc(t0)= indefinido
tc(t1)=1
Redes Temporizadas
com Transições Temporizadas
p0
t0
p1
[3,5]
M0
t0
M1
t1
t1
[2,4]
M2
t1 pode disparar
p2
tc(t0)= indefinido
tc(t1)=2
Redes Temporizadas
com Transições Temporizadas
p0
t0
p1
[3,5]
M0
t0
M1
t1
M2
t1
[2,4]
p2
tc(t0)= indefinido
tc(t1)= indefinido
Redes Temporizadas
com Transições Temporizadas
M0
p0
t0
[2,3]
p1
[2,3]
t1
[2,4]
t2
p2
p3
tc(t0)= 1
tc(t1)= indefinido
tc(t2)= indefinido
Redes Temporizadas
com Transições Temporizadas
M0
p0
t0
t0
[2,3]
M1
p1
[2,3]
t1
[2,4]
t2
p2
p3
tc(t0)= indefinido
tc(t1)= 1
tc(t2)= 1
Redes Temporizadas
com Transições Temporizadas
M0
p0
t0
t0
[2,3]
M1
p1
[2,3]
t1
[2,4]
t2
p2
p3
tc(t0)= indefinido
tc(t1)= 2
tc(t2)= 2
Redes Temporizadas
com Transições Temporizadas
M0
p0
t0
t0
[2,3]
M1
p1
[2,3]
t1
p2
tc(t0)= indefinido
tc(t1)= indefinido
tc(t2)= indefinido
t1
[2,4]
t2
M2
p3
t1 tem que disparar (strong semantics)
t1 pode disparar até este momento (weak semantics)