simulazione - Dipartimento di Ingegneria Informatica e delle

SIMULAZIONE
Ing. Alessandro Leonardi
Dipartimento di Ingegneria Informatica e delle
Telecomunicazioni
Università degli Studi di Catania
Outline
„
„
„
„
„
„
„
„
„
„
analisi e simulazione
pianificazione di una simulazione
tipi di simulatori
esempio di una coda a singolo servente
generatori pseudo
- casuali
transitorio e regime
precisione dei risultati
correlazione dei campioni
alcuni simulatori
NS
- 2
DIIT - A. Leonardi
2
Analisi e simulazione a confronto
„
Analisi
… si
„
„
basa sul modello analitico
es. teoria delle code
Simulazione
… consiste
nell’emulazione al calcolatore del
comportamento del sistema, mediante un modello di
simulazione
… il comportamento del sistema è specificato dallo stato
in cui il sistema si trova
DIIT - A. Leonardi
3
Analisi e simulazione a confronto
„
In entrambi i casi:
… BUON
MODELLO
… buon compromesso tra accuratezza della
descrizione ed efficienza/fattibilità
DIIT - A. Leonardi
4
Vantaggi - Svantaggi
„
Approccio analitico
… grande
sforzo di astrazione, risultati non
sempre in forma chiusa
… molto efficiente per la valutazione degli indici
prestazionali
„
Approccio simulativo
… sforzo
minore nella costruzione del modello
… lunghi periodi per l’elaborazione
DIIT - A. Leonardi
5
Simulazione
„
esistono sistemi non descrivibili con
modelli di sistemi a coda:
… sistemi
wireless
… routing dinamico
… controllo di congestione
… protocolli di ritrasmissione complessi
DIIT - A. Leonardi
6
Pianificazione e realizzazione di una
simulazione
„
„
„
„
„
„
„
Formulazione del problema
Raccolta ed analisi dei dati
Formulazione del modello matematico
Impostazione e scrittura del programma
Verifica del modello
Pianificazione degli esperimenti
Analisi dei risultati
DIIT - A. Leonardi
7
1
Formulazione del problema
2
Raccolta ed analisi dei dati
3
Formulazione del modello
4
5
6
Valutazione
del
Modello
Scrittura del programma
Verifica
del
Modello
7
Pianificazione degli esperimenti
8
Analisi dei risultati
DIIT - A. Leonardi
8
Formulazione del problema (1)
„
determinare gli obiettivi dello studio simulativo
… analizzare
le prestazioni
… determinare relazione ingressi- u
scite
… ottimizzare i parametri di controllo
… confrontare sistemi diversi
„
„
specificare gli indici di prestazione di interesse
individuare i parametri di ingresso
DIIT - A. Leonardi
9
Raccolta ed analisi dei dati di ingresso (2)
raccogliere dati sperimentali sulle
distribuzioni delle grandezze aleatorie che
intervengono
„ oppure… ipotizzare le caratteristiche dei
dati in ingresso
„
DIIT - A. Leonardi
10
Formulazione del modello matematico
e valutazione (3) (4)
semplificare il sistema reale in modo da
rappresentarlo sul calcolatore
„ identificare le relazioni funzionali tra le
componenti del sistema dinamico
„
DIIT - A. Leonardi
11
Scrittura del programma (5)
„
si sceglie lo strumento di programmazione
più adatto e si sviluppa il simulatore
DIIT - A. Leonardi
12
Verifica del modello (6)
si confrontano le uscite del modello con
quelle del sistema reale
„ si può simulare qualche caso semplice per
il quale esiste una soluzione analitica
„
DIIT - A. Leonardi
13
Pianificazione degli esperimenti (7)
„
analisi delle prestazioni del sistema
…
„
determinazione delle relazioni tra i parametri di ingresso
e le prestazioni di uscita
…
„
stimare i parametri che caratterizzano la funzione
ottimizzazione dei parametri di controllo del sistema
…
„
precisione dei risultati
max o min della funzione che lega parametri da ottimizzare alle
grandezze su cui si può agire
paragone tra le prestazioni di sistemi diversi
…
simulare i due sistemi e stimarne le prestazioni medie
DIIT - A. Leonardi
14
Analisi dei risultati (8)
„
raccolta od interpretazione dei risultati
delle simulazioni
… seconda
serie di simulazioni…
DIIT - A. Leonardi
15
Tipi di simulazioni 1/2
„
deterministiche
… le
simulazioni sono completamente definite
dal modello e la sua evoluzione dipende
fondamentalmente dagli ingressi
„
„
es: descrizione del moto di oggetti
casuali
…i
modelli includono variabili o processi aleatori
„
es: determinare probabilità di rifiuto di un sistema
DIIT - A. Leonardi
16
Tipi di simulazioni 2/2
„
simulazioni statiche
… non
„
„
esiste la variabile tempo
simulazioni Monte
- Carlo
simulazioni dinamiche
… il
tempo è la variabile principale
… il modello evolve temporalmente
„
problemi del transitorio
DIIT - A. Leonardi
17
Tipologie di simulatori
sincroni e asincroni
„ orientati agli eventi (o a eventi discreti) e
orientati ai processi
„
DIIT - A. Leonardi
18
Simulatori sincroni 1/2
„
Il tempo di simulazione viene diviso in tanti
intervalli di uguale ampiezza
… definizione
del passo di discretizzazione
dell’asse dei tempi
… perdita di precisione
… perdita di efficienza nel caso di eventi che si
verificano su scale temporali molto diverse
DIIT - A. Leonardi
19
Simulatori sincroni 2/2
A
B
DIIT - A. Leonardi
20
Simulatori asincroni
„
il tempo di simulazione viene aggiornato in
modo irregolare in base al cambiamento di
stato del sistema
DIIT - A. Leonardi
21
Simulatori orientati agli eventi
„
i cambiamenti di stato del sistema (eventi)
non avvengono in modo continuo ma in
istanti temporali discreti
… es:
sistemi di servizio, gli eventi
corrispondono ad arrivo o partenza
„
ad ogni evento il simulatore modifica le
variabili che descrivono il comportamento
del sistema
DIIT - A. Leonardi
22
Simulatori orientati ai processi
„
il sistema viene descritto in termini di
processi che sono eseguiti in parallelo e
che interagiscono tra di loro scambiandosi
informazioni
DIIT - A. Leonardi
23
Simulazioni ad eventi discreti 1/2
„
occorre:
… definire
i tipi di eventi che possono verificarsi
… definire per ogni evento le modifiche da apportare allo
stato del sistema
… una struttura dati che raccolga le informazioni relative
agli eventi che si devono verificare Æ calendario
… definire uno stato iniziale
… scorrere il calendario degli eventi
… effettuare misure sulle variabili di uscita
DIIT - A. Leonardi
24
Simulazioni ad eventi discreti 2/2
„
calendario degli eventi
… si
realizza con una lista linkata, ordinata
secondo il campo che contiene il tempo di
schedulazione
… durante la simulazione si scorre il calendario
degli eventi e si eseguono le modifiche alle
variabili di stato corrispondenti a quell’evento
DIIT - A. Leonardi
25
Esempio: coda a singolo servente
µ
λ
tempo medio di interarrivo 1/λ
„ tempo medio di servizio 1/µ
„
DIIT - A. Leonardi
26
Esempio: coda a singolo servente
„
Variabili del sistema
… variabili
di ingresso: processo degli arrivi e dei tempi
di servizio.
„
Es. M/M/1 processo arrivi di Poisson a tasso λ e tempi di
servizio distribuiti esponenzialmente con tasso µ
… variabili
„
di stato: numero clienti in coda N
Obiettivi
… numero
medio di clienti in coda E[N]
… tempo medio di attesa in coda E[W]
DIIT - A. Leonardi
27
Esempio: coda a singolo servente
„
Simulazione: ricostruire l’evoluzione nel
tempo del comportamento del sistema.
… sequenza
degli istanti di arrivo A[k] dei clienti
… tempi di servizio S[k]
„
scandendo i vettori si può costruire la
funzione N[t] (numero di clienti presenti nel
sistema al tempo t)
DIIT - A. Leonardi
28
Esempio: coda a singolo servente
N(t)
S[1]
A[1]
S[2]
A[3]
S[3]
A[4]
A[2]
DIIT - A. Leonardi
29
Esempio: coda a singolo servente
E[N]=(integrale N[t])/(tempo totale
simulazione)
„ E[W]=(integrale N[t])/(numero totale
partenze)
„
DIIT - A. Leonardi
30
Esempio: coda a singolo servente
(approccio analitico)
„
concetti base di teoria delle code
ρ) con ρ=λ/µ
… E[W]=1/(µ- λ)
… E[N]=ρ/(1
-
„
confronto:
… N[t]
può essere ricostruita qualunque sia la sequenza
di ingresso
… la teoria ci permette di osservare caratteristiche
fondamentali del sistema
DIIT - A. Leonardi
31
Esempio: coda a singolo servente
calendario degli eventi
„
Calendario degli eventi, deve contenere:
… tempo
di schedulazione
… identificativo del tipo di evento
… altri campi, es: ID del cliente a cui l’evento si riferisce
„
Eventi possibili:
… arrivo
di un nuovo cliente
… partenza di un cliente
DIIT - A. Leonardi
32
Esempio: coda a singolo servente
calendario degli eventi
„
inizializzazione
t=0
… N=0
… si inserisce nel calendario degli eventi un arrivo per ogni istante
A[k]
…
„
t=A[1] (primo arrivo)
N++
… viene inserito un evento di tipo partenza nel calendario degli
eventi all’istante A[1]+S[1]
…
„
„
occorre un inserimento in liste ordinate di tipo efficiente
la simulazione procede analizzando il prossimo evento…
DIIT - A. Leonardi
33
Esempio: coda a singolo servente
calendario degli eventi
t=0
N=0
A[1]
arrivo
t=A[1]
N=1
A[2]
arrivo
cliente 1
cliente 2
A[2]
A[3]
arrivo
arrivo
cliente 2
cliente 3
A[3]
A[1]+S[1]
arrivo
partenza
cliente 3
cliente 1
DIIT - A. Leonardi
34
Generazione di sequenze pseudo-casuali 1/5
la simulazione coinvolge variabili di
ingresso di tipo casuale
„ ripetibilità degli esperimenti anche su
piattaforme di calcolo differenti
„
… generazione
algoritmica (deterministica)
… appare ‘casuale’ a chi la usa
„
generatori pseudo-casuali
DIIT - A. Leonardi
35
Generazione di sequenze pseudo-casuali 2/5
„
formule ricorsive
… Es.
Generatori congruenziali moltiplicativi
xn +1 = xn ⋅ a mod m
x0
seme iniziale della sequenza
i numeri possibili sono: 1, 2, …, m-2, m-1
Es: a=5, m=7, x0=1
si genera la sequenza 1, 5, 4, 6, 2, 3, 1
DIIT - A. Leonardi
36
Generazione di sequenze pseudo-casuali 3/5
„
l’algoritmo è deterministico, e da quando
viene generato il seme iniziale, la
sequenza si ripete identica.
… la
periodicità massima è m-1
m è il periodo della sequenza
„ per ottenere un distribuzione tra 0 e 1 si
divide per m-1
„
DIIT - A. Leonardi
37
Generazione di sequenze pseudo-casuali 4/5
„
Generazione di più sequenze indipendenti
… Es:
M/M/1 occorre una sequenza per i tempi
di interarrivo e una sequenza per i tempi di
servizio indipendenti
utilizzare due moltiplicatori differenti
„ utilizzare due semi iniziali differenti
„ utilizzare una sola sequenza e partizionarla in più
sottosequenze
„
DIIT - A. Leonardi
38
Generazione di sequenze pseudo-casuali 5/5
„
la problematica della generazione di
numeri casuali si divide in due parti:
… generazione
di numeri uniformemente
distribuiti tra 0 e 1
… generazione di sequenze casuali di numeri
distribuiti in modo arbitrario
DIIT - A. Leonardi
39
Esempio 1
„
Generazione di una variabile casuale con
distribuzione uniforme in [a,b]
F(x)
1
a
x−a
F ( x) =
b−a
b
x−a
y=
b−a
x
x = (b − a ) y + a
(*)
generando y uniforme in [0,1] e calcolando la (*) si ottiene una istanza
della v.a. uniforme in [a,b]
40
DIIT - A. Leonardi
Esempio 2
„
generazione di una variabile gaussiana
… la
funzione distribuzione non è invertibile in
modo esplicito
… sommando ∞ v.a. distribuite unif.Ægaussiana
… per N≥12 v.a.uniformiÆgaussiana
for i=1:12
x=rnd();
y+=x;
end
DIIT - A. Leonardi
41
Transitorio e regime
„
durante una simulazione si possono
osservare due fasi
… fase
iniziale, durante la quale il sistema
risente delle condizioni iniziali Æ transitorio
… fase in cui il sistema si stabilizza Æ regime
„
di solito interessa calcolare gli indici di
prestazione a regime
DIIT - A. Leonardi
42
Transitorio e regime
la durata del transitorio dipende dalle
condizioni iniziali
„ problemi:
„
… difficoltà
nell’individuare un ‘buon’ stato
iniziale
… difficoltà nel distinguere il funzionamento di
regime da quello transitorio
DIIT - A. Leonardi
43
Transitorio e regime
„
metodi euristici per stimare la lunghezza
del transitorio
… metodo
del troncamento
… metodo della cancellazione dei dati iniziali
„
sono basati sull’idea che la variabilità delle
misure nei periodi di transitorio è più
elevata che a regime
DIIT - A. Leonardi
44
Transitorio e regime
„
metodo del troncamento
… siano
dati n campioni {x1 ,x2 ,…,xn}
… per ogni l=1,2, …, n si confronta xl+1 con il
massimo e minimo dei campioni del
sottoinsieme {xl+1 ,xl+2 ,…,xn}
… il più piccolo l per cui xl+1 non è né il minimo
né il massimo di {xl+1 ,xl+2 ,…,xn} è la
lunghezza del transitorio
DIIT - A. Leonardi
45
Transitorio e regime
xl
l*
transitorio
regime
DIIT - A. Leonardi
46
Transitorio e regime
„
metodo della cancellazione dei dati iniziali
… siano
dati n campioni {x1 ,x2 ,…,xn}
… sia x la media degli n campioni
… al crescere di l=1,2, …, n si calcola la media xl dei
campioni {xl+1 ,xl+2 ,…,xn}
xl − x
… si calcola
Rl =
x
… il
valore di l in corrispondenza del ginocchio di Rl
identifica la lunghezza del transitorio
DIIT - A. Leonardi
47
Transitorio e regime
xl
x
l*
transitorio
regime
DIIT - A. Leonardi
48
Analisi e convalida dei risultati
„
Costruito il modello e il software, occorre:
… decidere
cosa misurare
… essendo le variabili di uscita aleatorie,
decidere con quali parametri caratterizzare
tali variabili (media, varianza)
… valutare l’accuratezza (precisione) della stima
DIIT - A. Leonardi
49
Analisi e convalida dei risultati
„
Supponiamo di voler misurare un indice di
prestazione x.
…x
è v.a. con media µ e varianza σ2
Obiettivo simulazione Æ stimare µ
„ consideriamo n esperimenti, s.i. e
ricaviamo n osservazioni:
„
… x1, x2,
…, xn
1 n
„ calcoliamo la media aritmetica: x = ∑ xi
n i =1
DIIT - A. Leonardi
50
Analisi e convalida dei risultati
„
„
L’intervallo di confidenza ci dice con quale
probabilità µ cade in un intervallo attorno a x
anche la media è una v.a. con:
E[x ] = µ
„
σ 2 (x) =
σ2
n
notiamo che all’aumentare di n (numero
esperimenti) la varianza decresce, ovvero x
diventa molto vicino a µ
DIIT - A. Leonardi
51
Analisi e convalida dei risultati
„
consideriamo ora la nuova v.a.
x−µ
z=
σ/ n
„
„
„
ha una distribuzione gaussiana con media 0 e
varianza 1 (distribuzione normale)
la distribuzione si trova tabulata
sia uα un valore tale che
… P{-
uα≤z≤ uα }=1
- α
DIIT - A. Leonardi
52
Analisi e convalida dei risultati
„
quindi:
…
„
ovvero:
…
„
„
x−µ
P{−uα ≤
≤ uα } = 1 − α
σ/ n
P{x − uα
σ
n
≤ µ ≤ x + uα
σ
n
} = 1−α
la costante (1-α) è di solito espressa in
percentuale e si chiama livello di confidenza
l’intervallo x ± uα σ si chiama intervallo di
n
confidenza
DIIT - A. Leonardi
53
Analisi e convalida dei risultati
„
di solito, si adotta un livello di confidenza pari al
95%
… α=0.05
… uα=1.96
„
„
ciò significa che µ cade nell’intervallo suddetto
con una probabilità del 95%
siccome σ2 non è nota, viene sostituita da:
…
1 n
2
s =
(
x
−
x
)
∑ i
n − 1 i =1
2
(scarto quadratico medio)
DIIT - A. Leonardi
54
Analisi e convalida dei risultati
„
invece di z, consideriamo t:
…
x−µ
t=
s/ n
„
t è distribuita come t-student con n-1 gradi di libertà
il nuovo intervallo di confidenza risulta:
„
…
„
δ = tα
s
n
per n grande (n>30) la possiamo approssimare alla
distribuzione normale
DIIT - A. Leonardi
55
Analisi e convalida dei risultati
„ tα prende
il nome di percentile
… tabella
„
δ
<ε
ciclo while finchè la condizione
x
non è verificata
…ε
è la precisione (es: 10-3)
x −δ x
x +δ
DIIT - A. Leonardi
56
Analisi e convalida dei risultati
„
Esempio:
…9
esperimenti di simulazione indipendenti
„
x1, x2, …, x9
1 9
… x = ∑ xi = 65
9 i =1
1 9
… s=
( xi − 65) 2 = 445
∑
9 − 1 i =1
DIIT - A. Leonardi
57
Analisi e convalida dei risultati
„
calcoliamo gli intervalli di confidenza con livello
di confidenza 0.9 (1-α=0.9)
s
s
…
P{x − tα
≤ E[ x] ≤ x + tα
} = 0.9
9
9
nel nostro caso l’intervallo di confidenza risulta pari
a (78.08
- 51.92)
δ
… controllo
<ε
x
…
„
„
verificatoÆ stop
non verificatoÆaltre simulazioni
DIIT - A. Leonardi
58
Correlazione dei campioni
nella realtà i campioni ottenuti durante
l’esperimento di simulazione sono correlati
„ es: sistema a coda FIFO
„
… il
ritardo del k-esimo cliente è correlato con il
ritardo osservato dal cliente (k+1)-esimo
„
si potrebbe ricorrere a stimatori
dell’autocorrelazione
… complessità
eccessiva
DIIT - A. Leonardi
59
Correlazione dei campioni
„
metodi euristici
… prove
ripetute
… metodo batch means
… metodo rigenerativo
DIIT - A. Leonardi
60
Correlazione dei campioni
„
metodo delle prove ripetute
…i
campioni scorrelati sono ottenuti come valori
osservati al termine di brevi simulazioni
indipendenti, ottenuti con semi diversi del
generatore di numeri casuali
DIIT - A. Leonardi
61
Correlazione dei campioni
„
metodo batch means
… si
effettua una simulazione lunga e si divide in
intervalli più brevi (batch)
… ogni intervallo contiene un numero n di osservazioni
maggiore di quello osservato nel transitorio iniziale
… il vantaggio è che si elimina un solo transitorio iniziale
… non è necessario generare semi diversi
DIIT - A. Leonardi
62
Correlazione dei campioni
„
metodo rigenerativo
…
…
…
…
…
si identificano alcuni stati del sistema per i quali il
comportamento futuro non dipende dalla storia passata
gli istanti di tempo in cui il sistema entra in questi stati sono detti
di rigenerazione (il sistema si rigenera perché perde la
correlazione con la storia passata)
i campioni ricavati durante questi intervalli sono scorrelati
insieme secondario: è costituito dalla medie dei campioni primari
negli intervalli di rigenerazione
è difficile trovare i punti di rigenerazione
DIIT - A. Leonardi
63
Linguaggi per simulazione di sistemi ad eventi
discreti
„
„
„
„
tutti i moderni linguaggi di simulazione usano per
l’avanzamento del tempo l’approccio dell’evento
successivo.
dopo aver fatto tutte le operazioni relative all’evento
verificatosi all’istante attuale, incrementano il tempo al
valore in cui si verificherà l’evento successivo.
la simulazione salta i periodi di inattività.
sistema di sincronizzazione
…
tutte le strutture dati utilizzate per manipolare la lista degli eventi
DIIT - A. Leonardi
64
Linguaggi per simulazione di sistemi ad
eventi discreti
„
Alcuni dei linguaggi più diffusi:
…
SIMSCRIPT
„
„
…
GPSS
„
„
…
linguaggio basato sui diagrammi a blocchi
facile da usare
SIMULA
„
„
…
estensione del FORTRAN
è fornito di funzioni che gestiscono gli eventi
estensione dell’ALGOL
consente di realizzare complesse strutture di dati dinamiche
NS-2
„
„
„
utilizzato da tutta la comunità scientifica
C++ / Tcl
codice sorgente free
DIIT - A. Leonardi
65