Simulação de Eventos Discretos
Aplicação à simulação de Circuitos Lógicos
AED - 2003
Esquema de um Simulador de
Eventos Discretos
Inicializa
TEMPO
t
ESTADO
x
x’
Actualiza Estado
x’ = f (x, e1 )
x’
Gerador de
Eventos
Temporais
LISTA de
EVENTOS
e1
et11
e2
t2
...
t’
Actualiza Tempo
t’ = t1
t’
Elimina eventos
(ek , tk)
Acrescenta eventos
(ek , t’)
e re-ordena lista
2
Passos de Simulação
1.
Retirar o primeiro elemento, (e1, t1), da LISTA DE EVENTOS;
2.
Actualizar o tempo de simulação (TEMPO), avançando-o para o instante do novo
evento, t1;
3.
Actualizar o ESTADO de acordo com as regras de transição, representadas pela
função de transição de estado, x’=f(x, e1);
4.
Eliminar da LISTA DE EVENTOS todas as entradas correspondentes a eventos
incompatíveis com o novo estado x’;
5.
Adicionar à LISTA DE EVENTOS todos os eventos que ainda não estejam
agendados, despoletados pelo evento processado;
6.
Reordenar a LISTA DE EVENTOS por ordem crescente de tempo.
3
Componentes de um Simulador
•
ESTADO: memória onde todas as variáveis de estado são guardadas;
•
TEMPO: variável que armazena o tempo de simulação;
•
LISTA DE EVENTOS: lista onde todos os eventos agendados são guardados, com
indicação dos instantes de tempo em que ocorrem;
•
Função de Inicialização: função que inicializa todas as estruturas de dados no início
de uma simulação;
•
Função de Actualização de Estado: função que actualiza o estado baseado no
próximo evento a ocorrer;
•
Funções de Geração de Eventos Temporais: conjunto de funções que geram eventos
relacionados explicitamente com o tempo, por exemplo, eventos periódicos;
•
Função Principal: responsável pela coordenação de todas as componentes do
simulador. Começa por invocar a função de inicialização, após o que, repetidamente,
invoca as funções de actualização do tempo e do estado e actualiza a lista ordenada
de eventos. É também responsável pela terminação da simulação, baseada na
observância de critérios especificados pelo utilizador, bem como pela apresentação
dos resultados da simulação.
4
Exemplo de Circuito Lógico
z_1
G3
xin1
G1
y3
pzt
1
4
G4
u
G2
q
zout
3
v
2
•Portas lógicas: G1 (and), G2 (nand), G3 (not), G4 (or)
•Atrasos das portas: G1 = 4; G2 = 2; G3 = 1; G4 = 3;
•Entradas do circuito: xin1, y3, u, v
•Saídas do circuito: z_1, zout
•Nós do circuito: xin1, y3, u, v, pzt, q, z_1, zout
5
Modelo de Atraso
•
Modelo de Atraso Fixo: cada porta tem um atraso fixo de entrada para a
saída, definido na descrição da porta.
•
O modelo de atraso assume inércia nos sinais e transições. Isto significa
que a saída de uma porta lógica só muda como consequência de uma
alteração nas entradas se as entradas mantiverem constantes a condição
para o novo valor da saída até ao instante efectivo da alteração da saída.
6
G3
xin1
pzt
G1
z_1
1
y3
4
G4
3
u
G2
v
Simulação
zout
q
2
Sinais de entrada:
Tempo
Valor
Nó
0
0
Xin1
0
0
y3
0
1
U
0
1
V
14
0
U
20
X
U
30
1
Xin1
30
1
Y3
30
1
U
40
0
Xin1
42
1
xin1
7
G3
xin1
pzt
G1
z_1
ESTADO
1
xin1
y3
4
G4
u
v
pzt
q
z_1
zout
zout
3
u
G2
v
y3
q
2
Inicialização:
Tempo
Valor
Nó
0
0
Xin1
0
0
y3
0
1
U
0
1
V
14
0
U
20
X
U
30
1
Xin1
30
1
Y3
30
1
U
40
0
Xin1
42
1
xin1
TEMPO
0
ESTADO
X
LISTA de EVENTOS
X X X X X X X
Gerador de
Eventos
Temporais
xin1, 0
0
y3,0
0
u,1
0
v, 1
0
Acrescenta eventos
(ek , t’)
e re-ordena lista
8
G3
xin1
G1
pzt
z_1
ESTADO
1
xin1
y3
4
G4
u
v
pzt
q
z_1
zout
zout
3
u
G2
v
y3
q
2
t=0:
xi1,0
0
TEMPO
0
ESTADO
0
Actualiza Tempo
t’ = 0
LISTA de EVENTOS
X X X X X X X
Actualiza Estado
x’ = f (x, e1 )
•Retira o evento (xi1,0 , 0) da lista de eventos
•Actualiza o TEMPO
•Actualiza o ESTADO
• xin1 afecta a porta G1 gerando o evento (pzt,0 , 4)
y3,0
0
u,1
0
v, 1
0
pzt, 0
4
Acrescenta eventos
(ek , t’)
e re-ordena lista
9
G3
xin1
pzt
G1
z_1
1
ESTADO
y3
4
G4
G2
t=0:
xin1
y3
u
v
pzt
q
z_1
zout
3
u
v
zout
q
2
y3,0
TEMPO
0
0
ESTADO
0
0 X X X X X X
LISTA de EVENTOS
t=0:
0
u,1
u,1
0
TEMPO
v, 1
0
0
pzt, 0
4
ESTADO
0
0 1 X X X X X
LISTA de EVENTOS
t=0:
0
v,1
v, 1
0
TEMPO
pzt, 0
4
0
ESTADO
0
0 1 1 X X X X
LISTA de EVENTOS
q, 0
2
pzt, 0
4
10
G3
xin1
pzt
G1
z_1
1
ESTADO
y3
4
G4
G2
t=2:
y3
u
v
pzt
q
z_1
zout
q
2
2
q,0
TEMPO
2
xin1
3
u
v
zout
ESTADO
0
0 1 1 X 0 X X
LISTA de EVENTOS
pzt, 0
4
t=4:
pzt, 0
TEMPO
4
4
ESTADO
0
0 1 1 0 0 X X
LISTA de EVENTOS
z_1, 1
5
zout, 0
7
t=5:
z_1, 1
TEMPO
5
5
ESTADO
0
0 1 1 0 0 1 X
LISTA de EVENTOS
zout, 0
7
11
G3
xin1
G1
pzt
z_1
ESTADO
1
xin1
y3
4
G4
u
v
pzt
q
z_1
zout
zout
3
u
G2
v
t=7:
y3
q
2
zout, 0
TEMPO
t=14:
7
ESTADO
7
0
0 1 1 0 0 1 0
LISTA de EVENTOS
u, 0
14
Acrescenta eventos
(ek , t’)
e re-ordena lista
TEMPO
t=19:
ESTADO
14
0
0 0 1 0 0 1 0
LISTA de EVENTOS
16
q, 1
t=16:
q, 1
TEMPO
16
Gerador de
Eventos
Temporais
14
u, 0
16
ESTADO
0
TEMPO
19
ESTADO
19
0
0 0 1 0 1 1 1
LISTA de EVENTOS
u, X
20
Acrescenta eventos
(ek , t’)
e re-ordena lista
0 0 1 0 1 1 0
LISTA de EVENTOS
Z_out, 1
Z_out, 1
19
Gerador de
Eventos
Temporais
12
G3
xin1
pzt
G1
z_1
ESTADO
1
xin1
y3
4
G4
G2
t=20:
t=25:
zout, X
TEMPO
20
25
ESTADO
0
q
z_1
zout
25
t=30:
22
q, X
q, X
TEMPO
Gerador de
Eventos
Temporais
ESTADO
0
0 X 1 0 X 1 1
LISTA de EVENTOS
zout, X
0
y3, 1
30
25
0 X 1 0 X 1 X
TEMPO
30
ESTADO
1
1 X 1 0 X 1 X
LISTA de EVENTOS
xin1, 1
30
u, 1
30
y3, 1
30
pzt, 1
34
u, 1
30
t=30:
22
ESTADO
LISTA de EVENTOS
0 X 1 0 1 1 1
LISTA de EVENTOS
22
pzt
zout
q
TEMPO
t=22:
v
2
u, X
20
u
3
u
v
y3
xin1, 1
TEMPO
30
30
ESTADO
1
0 X 1 0 X 1 X
LISTA de EVENTOS
t=30:
u, 1
TEMPO
30
30
ESTADO
1
1 1 1 0 X 1 X
LISTA de EVENTOS
y3, 1
30
q, 0
32
u, 1
30
pzt, 1
34
13
G3
xin1
pzt
G1
z_1
ESTADO
1
xin1
y3
4
G4
G2
t=32:
v
pzt
q
z_1
TEMPO
zout
zout
t=35:
q
35
32
LISTA de EVENTOS
34
zout, 0
35
pzt, 1
TEMPO
34
zout, 1
TEMPO
1 1 1 1 0 0 1
37
37
ESTADO
1
1 1 1 1 0 0 1
LISTA de EVENTOS
34
ESTADO
1
1
t=37:
37
t=34:
ESTADO
zout, 1
1 1 1 0 0 1 X
pzt, 1
35
LISTA de EVENTOS
ESTADO
1
z_1, 0
TEMPO
2
q, 0
32
u
3
u
v
y3
1 1 1 1 0 1 X
LISTA de EVENTOS
z_1, 0
35
zout, 1
37
Elimina eventos
(ek , tk)
Inércia na transição: os sinais
na entrada de G4 não se
mantiveram constantes antes
da transição em t=35, pelo que
esta deixa de ter efeito,
retirando-se o evento (zout, 1)
da lista de eventos
xin1, 0
40
Gerador de
Eventos
Temporais
14
G3
xin1
G1
pzt
z_1
ESTADO
1
xin1
y3
4
G4
u
v
pzt
q
z_1
zout
zout
3
u
G2
v
y3
q
2
t=40:
xin1, 0
TEMPO
40
40
ESTADO
0
1 1 1 1 0 0 1
LISTA de EVENTOS
Gerador de
Eventos
Temporais
xin1, 1
42
pzt, 0
44
t=42:
xin1, 1
TEMPO
42
42
ESTADO
1
1 1 1 1 0 0 1
LISTA de EVENTOS
Elimina eventos
(ek , tk)
Inércia na transição: o sinal
xin1 não se manteve constante
na entrada de G1 antes da
transição pzt=0 em t=44, pelo
que esta deixa de ter efeito,
retirando-se o evento (pzt, 0) da
lista de eventos
15
16