Análise de Desempenho n n Analíticos – –Determinísticos n n Melhor e pior casos – –Probabilisticos n n Valores prováveis n n Simulação n n Análise exaustiva

  • Published on
    17-Apr-2015

  • View
    108

  • Download
    0

Embed Size (px)

Transcript

  • Slide 1
  • Anlise de Desempenho n n Analticos Determinsticos n n Melhor e pior casos Probabilisticos n n Valores provveis n n Simulao n n Anlise exaustiva n n Implementao real Medidas obtidas do sistema real Benchmarks Prottipos
  • Slide 2
  • Redes de Petri Espao dos Formalismos Nveis de Abstrao Interpretaes Autnomo Estocstico Detreminstico Intervalo Predicados Limites Sinais Externos TemporizadoDados Interpretados Obj.RdP Pr/T, CPN P,T CE, EN
  • Slide 3
  • Redes Temporizadas Extenses Temporizadas Token-Timed PN Transition-Timed PN Place-Timed PN Stochastic PN Time PN Timed PN
  • Slide 4
  • Redes Temporizadas Extenses Temporizadas Token-Timed PN Transition-Timed PN Place-Timed PN Stochastic PN Time PN Timed PN
  • Slide 5
  • Redes Temporizadas Ramchandani, 1973 - Transition Timed Net Ramchandani, 1973 - Transition Timed Net Merlin, 1976 - Transition Time Net Merlin, 1976 - Transition Time Net Sifakis, 1977 - Place Timed Net Sifakis, 1977 - Place Timed Net
  • Slide 6
  • Redes Temporizadas Estocsticas Natkin -1980 Molloy - 1981 Marsan et al. - 1984 uma rede temporizada onde o delay associado transio uma varivel aleatria de distribuio exponencial
  • Slide 7
  • Redes Temporizadas n Redes de Petri com Lugares Temporizados (PTPN) (Sifakis77) n Definio: PTPN=(P,T,F,K,W,M 0,, ), onde P o conjunto de lugares, T o conjunto de transies, F (P T) (T P) uma relao que representa os arcos W Valorao (peso dos arcos) - W: F N M 0 - Marcao inicial - M 0 :P N ={ 1, 2,, i,} nmeros reais denominada base de tempo. ={ 1, 2,, i,} nmeros reais denominada base de tempo. :P um mapeamato que (p) = j :P um mapeamato que (p) = j
  • Slide 8
  • Redes Temporizadas - PTPN - 2 t0 p0 t1 n Regra de Disparo (p0) = 3 (p0) = 3 p1 2
  • Slide 9
  • Redes Temporizadas - PTPN - 2 t0 p0 t1 n Regra de Disparo Instante=0 p1 2 (p0) = 3 (p0) = 3
  • Slide 10
  • Redes Temporizadas - PTPN - 2 t0 p0 t1 n Regra de Disparo Instante=1 p1 2 (p0) = 3 (p0) = 3
  • Slide 11
  • Redes Temporizadas - PTPN - 2 t0 p0 t1 n Regra de Disparo Instante=2 p1 2 (p0) = 3 (p0) = 3
  • Slide 12
  • Redes Temporizadas - PTPN - 2 t0 p0 t1 n Regra de Disparo Instante=3 p1 2 (p0) = 3 (p0) = 3
  • Slide 13
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Conceitos Bsicos: Durao (disparo em trs fases) n Marcas so consumidas dos lugares de entrada n H uma durao n Marcas so geradas no lugares de sada Disparo atmico n As marca permanecem nos lugares de entrada pelo perodo igual ao delay associada transio. Aps o delay as marcas so consumidas e geradas nos lugares de sada imediatamente.
  • Slide 14
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Conceitos Bsicos: Durao (disparo em trs fases) n Pode ser representada por uma rede com disparo atmico n Modelo mais compacto n O estado uma informao mais complexa do que o modelo no-temporizado Disparo atmico n Pode representar o modelo com durao n O conjunto de marcaes alcanveis um sub-conjunto das marcaes do modelo no- temporizado.
  • Slide 15
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Conceitos Bsicos: Regras de Seleo: n Pr-seleo: (durao e delay) Prioridade Probabilidade n Race (corrida): (delay) Transies habilitadas com menor delay so disparadas
  • Slide 16
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Conceitos Bsicos: Quando uma das transies conflitantes desabilitada pelo disparo da outra, o que acontece com o timer da que ficou desabilitada quando a mesma tornar-se habilitada outra vez?
  • Slide 17
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Como fica a memorizao do tempo de habilitao anterior? n Continue O timer associado transio mantem o valor atual e quando a transio se tornar novamente habilitada o valor do timer iniciar daquele valor. n n Restart Quando a transio for novamente habilitada o timer ser re-iniciado. ta tb p0 p1 p2 da db
  • Slide 18
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Conceitos Bsicos: O que acontece com o timer das transies habilitadas aps o disparo de uma transio? n Todas as transies. No somente as transies conflitantes. Algumas polticas de memria podem ser construdas
  • Slide 19
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Conceitos Bsicos: Resampling n Aps cada disparo os timers de TODAS as transies so re-iniciado (restart) n No h memria n Aps descartar todos os timers, os valores iniciais so associados a todas as transies que se tornarem habilitadas na nova marcao.
  • Slide 20
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Conceitos Bsicos: Enabling Memory n Aps cada disparo os timers das transies que ficaram desabilitadas so re-iniciados (restart) n As transies que permaneceram habilitadas com o disparo matem seus valores presentes(continue)
  • Slide 21
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Conceitos Bsicos: Age Memory n Aps cada disparo os timersde todas as transies so mantidos em seus valores presentes (continue)
  • Slide 22
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Conceitos Bsicos: Grau de Habilitao (Enabling Degree) n o nmero de vezes que uma determinada transio pode ser disparada, numa determinada marcao, antes de se torna desabilitada. n Quando o grau de habilitao maior que um, ateno especial semntica de temporizao deve ser considerada. ta p0 p1 d
  • Slide 23
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Conceitos Bsicos: Semntica de Temporizao n Single-server firing semantics n Infinite-server firing semantics n Multiple-server firing semantics K o mximo grau de paralelismo. Quando k, Multiple-server firing semantics igual a infinite-server firing semantics.
  • Slide 24
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Conceitos Bsicos: Single-server firing semantics ta p0 p1 d=3 t=3 t=6 t=9t
  • Slide 25
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Conceitos Bsicos: Infinite-server firing semantics ta p0 p1 d=3 t=3t
  • Slide 26
  • Redes de Petri Temporizadas - Tempo Associado s Transies - n Conceitos Bsicos: Multiple-server firing semantics k=2 ta p0 p1 d=3 tt=3 t=6
  • Slide 27
  • Redes Temporizadas com Transies Temporizadas n Time Petri Nets (Merlin76) n Definio: TPN=(P,T,F, W,M 0,I), onde P o conjunto de lugares, T o conjunto de transies, F (P T) (T P) uma relao que representa os arcos W Valorao (peso dos arcos) - W: F W Valorao (peso dos arcos) - W: F M 0 - Marcao inicial - M 0 :P M 0 - Marcao inicial - M 0 :P I : T ( + {0}) ( + {0}), onde I(t i )=(d i min, d i max ), d i max d i min TC: T uma funo parcial que associa as transies um timer clock
  • Slide 28
  • Redes Temporizadas com Transies Temporizadas Semntica de Disparo de Transio n Uma transio t j disparvel se estiver habilitada Regras de habilitao M[t j >, M(pi) pi, t j ) M[t j >, M(pi) pi, t j ) pi P pi P durante o intervalo I(t j )=(d j min, d j max ), Ou seja, t j s ser disparvel se tc(t j ) d j min n e ter que disparar at tc(t j ) d j max (strong semantics) ou ou n e poder disparar at tc(t j ) d j max (weak semantics) n Resampling n Regras de disparo Se M[t j >M Se M[t j >M M(pi)=M0(pi) - I(pi, t j )+O(pi, t j ) M(pi)=M0(pi) - I(pi, t j )+O(pi, t j ) pi P pi P
  • Slide 29
  • Redes Temporizadas com Transies Temporizadas p0 t0 p1 t1 p2 [3,5] [1,3] M0 tc(t0)=1 tc(t1)= indefinido
  • Slide 30
  • Redes Temporizadas com Transies Temporizadas p0 t0 p1 t1 p2 [3,5] [1,3] M0 tc(t0)=2 tc(t1)= indefinido
  • Slide 31
  • Redes Temporizadas com Transies Temporizadas p0 t0 p1 t1 p2 [3,5] [1,3] M0 tc(t0)=3 tc(t1)= indefinido t0 pode disparar
  • Slide 32
  • Redes Temporizadas com Transies Temporizadas p0 t0 p1 t1 p2 [3,5] [1,3] M0 tc(t0)=4 tc(t1)= indefinido
  • Slide 33
  • Redes Temporizadas com Transies Temporizadas p0 t0 p1 t1 p2 [3,5] [2,4] M0 tc(t0)= indefinido tc(t1)=1 M1 t0
  • Slide 34
  • Redes Temporizadas com Transies Temporizadas p0 t0 p1 t1 p2 [3,5] [2,4] M0 tc(t0)= indefinido tc(t1)=2 M1 t0 t1 pode disparar M2 t1
  • Slide 35
  • Redes Temporizadas com Transies Temporizadas p0 t0 p1 t1 p2 [3,5] [2,4] M0 tc(t0)= indefinido tc(t1)= indefinido M1 t0 M2 t1
  • Slide 36
  • Redes Temporizadas com Transies Temporizadas p0 t0 p1 t1 t2 p2p3 [2,3] [2,4] M0 tc(t0)= 1 tc(t1)= indefinido tc(t2)= indefinido
  • Slide 37
  • Redes Temporizadas com Transies Temporizadas p0 t0 p1 t1 t2 p2p3 [2,3] [2,4] M0 tc(t0)= indefinido tc(t1)= 1 tc(t2)= 1 M1 t0
  • Slide 38
  • Redes Temporizadas com Transies Temporizadas p0 t0 p1 t1 t2 p2p3 [2,3] [2,4] M0 tc(t0)= indefinido tc(t1)= 2 tc(t2)= 2 M1 t0
  • Slide 39
  • Redes Temporizadas com Transies Temporizadas p0 t0 p1 t1 t2 p2p3 [2,3] [2,4] M0 tc(t0)= indefinido tc(t1)= indefinido tc(t2)= indefinido M1 t0 M2 t1 t1 tem que disparar (strong semantics) t1 pode disparar at este momento (weak semantics)