Un framework per simulazione massiva distribuita basata su Agenti

Un framework per simulazione
massiva distribuita basata
su Agenti D-MASON:
Architettura
Carmine Spagnuolo
1
Simulazione
Multi-Agente
• Una simulazione multi-agente è
un sistema in cui entità (agenti)
intelligenti interagiscono per
soddisfare un certo insieme di
obiettivi allo scopo di portare a
termine un certo insieme di
compiti.
• La simulazione consente di
confrontare il comportamento di
un sistema biologico tramite il
comportamento di un sistema
artificiale.
2
Esempio di
Simulazione:
Modello di Reynolds
• Agenti autonomi riproducono il
movimento di uno stormo di uccelli.
i.
• Ogni volatile è un agente definito da
tre regole:
i.
ii.
cerca di dirigersi verso lo stormo.
cerca di evitare le zone troppo
affollate.
iii. si muove nella stessa direzione
dello stormo.
• Eseguendo la simulazione si nota che
gli agenti tendono a unirsi in gruppi.
ii.
iii.
3
Simulazione Multi-Agente
Agenti
Definizione della struttura degli agenti
e dei rapporti reciproci che si possono
instaurare
Modello ad agenti
Creazione di modelli che
rappresentano la realtà
mediante gli agenti.
Simulazione ad agenti
Implementazione software dei modelli
ad agenti ed analisi dei risultati
emergenti.
4
Ambiti di utilizzo
Scienze Sociali (Modello di
segregazione di Schelling)
Economia (Andamento della Borsa)
Biologia (Propagazione dell’antrace
nel corpo umano)
Fisica (Fisica delle Particelle)
Intelligenza Artificiale (Videogiochi,
robots, ecc…)
5
Simulazione Multi-Agente distribuita
La simulazione
parallela/distribuita consente a
un programma di simulazione di
essere eseguito da più computer
interconnessi.
Vantaggi
1. Riduzione del tempo di esecuzione.
2. Fault tolerance.
6
MASON – Toolkit
di simulazione
multi-agente
• Libreria scritta in Java per la
modellazione di sistemi basati su
agenti.
• L’architettura di MASON si divide
in due parti:
- simulation model, che può essere
eseguito da linea di comando
- visualization toolkit, per analizzare e
manipolare il modello.
7
Obiettivi del lavoro
• Parallelizzare MASON per migliorarlo
 Permettere la simulazione di un numero
maggiore di agenti.
 Eseguire la stessa simulazione in un tempo
inferiore.
 Ottenere tutto ciò modificando il meno possibile
il codice delle simulazioni in MASON.
•
Recuperare potenza di calcolo non utilizzata tramite
l’utilizzo di macchine eterogenee.
8
Perché si è scelto MASON ?
• E’ uno fra i più efficienti (in termini di velocità e di
flessibilità) [Matthew Berryman-Review of Software
Platforms for Agent Based Models-2008].
• E’ open-source.
• La sua struttura a moduli permette un facile reengineering in chiave distribuita.
• Un significativo numero di simulazioni già presenti da
poter studiare.
9
Problematiche
Distribuzione del carico di lavoro
Sincronizzazione
Riproducibilità
della simulazione
10
Distribuzione del carico di lavoro
• La distribuzione del carico di lavoro è ottenuta tramite il
partizionamento del campo in celle:
o AOI (area of interest) – raggio di interesse dell’agente.
o Ogni entità del sistema distribuito esegue una o più celle.
D-MASON una dimensione
D-MASON due dimensioni
MASON
Suddivisione
11
Partizionamento
del Campo
• Si utilizzano concetti
descritti in “Distributed
Load Balancing for
Parallel Agent-based
Simulations [2011]”
• L’agente α è interessato
a tutti gli agenti nel suo
raggio di interesse.
• Per ogni passo i di
simulazione gli agenti
interagiscono con lo
stato del campo al passo
i-1.
12
Partizionamento
del Campo
•
In D-MASON ogni
agente si sposta da una
cella all’altra e le
interazioni avvengono in
un sistema distribuito.
•
Il sistema provvederà
all’aggiornamento del
campo consentendo agli
agenti di interagire in
modo corretto.
13
Sincronizzazione e Comunicazione
• Self-synchronization: il passo i della cella c utilizza gli stati dei
passi i-1 delle celle del vicinato.
• La sincronizzazione permette di mantenere coerente la
simulazione.
• La comunicazione è distribuita e utilizza il paradigma
Publish/Subscribe (nel caso di D-MASON è utilizzato Java
Message Service)
14
Architettura
D-MASON
• D-MASON si colloca nel
secondo layer di MASON.
• D-MASON dipende da MASON
ma non è vero il contrario.
• Le scelte architetturali effettuate
seguono la necessità di
mantenere lo sviluppo di
applicazioni D-MASON
evoluzione naturale di quelle in
MASON.
15
Architettura
D-MASON
• In Util sono presenti tutti gli
oggetti necessari ai vari layer.
• In Field sono presenti le versioni
distribuite dei campi di
simulazione di MASON.
• In Engine è presente il modello di
simulazione e la definizione di
agente.
MASON
• Per ogni elemento di MASON è
fornita la controparte “distribuita”
in D-MASON.
dmason.Util
dmason.Field
dmason.Engine
16
Un framework per simulazione
massiva distribuita basata
su Agenti D-MASON:
Applicazioni
Dario Mazzeo
17
Struttura di un’applicazione D-MASON
Campo
distribuito della
simulazione
Agenti simulati
Generatore di
Numeri PseudoCasuali
Simulato da
Simulatore
Worker
18
Agente
Ri-localizzazione
posizione e
recupero del
vicinato
Stato della simulazione
Visualizzazione
Simulazione di
una singola
porzione del
campo
Visualizzazione di
una singola
porzione del
campo
Differenze MASON / D-MASON
Il programmatore deve avere coscienza
dell’ambiente distribuito solo per alcuni aspetti
implementativi delle classi della simulazione
19
Differenze MASON / D-MASON
MASON
D-MASON
•
• Ogni agente è un Remote Agent,
un’astrazione di un agente che
vive e interagisce in un ambiente
distribuito.
•
Ogni agente è di tipo Steppable
permette di definire il
comportamento dell’agente nel
metodo step().
Un passo di simulazione eseguito
dall’oggetto Schedule richiama
ripetutamente il metodo step() di
ogni agente.
– Memorizza i dati necessari alla
migrazione da un nodo all’altro.
– Può essere schedulato solo per un
passo, nel successivo bisogna
considerare a quale cella appartiene.
• DistributedSchedule è l’oggetto
delegato all’esecuzione della
simulazione distribuita : passo di
simulazione – sincronizzazione &
aggiornamento.
20
Differenze MASON / D-MASON
MASON
D-MASON
• L’oggetto che rappresenta lo stato
della simulazione è SimState:
sono memorizzati i campi di
simulazione contenitori di agenti o
di informazioni.
.
•
Lo stato della simulazione,
l’oggetto DistributedState,
aggiunge le informazioni per un
ambiente distribuito: utilizza
campi di simulazione distribuiti,
identifica le celle e gestisce la loro
sincronizzazione, inizializzando i
campi con i particolari
RemoteAgents.
21
Esecuzione MASON / D-MASON
Modello di Studio
Cella 0-0 Di D-MASON
MASON
22
System Management D-MASON
Client
Console di gestione
23
System Management D-MASON
24
Testing D-MASON
• Motivazioni
– Capacità di eseguire simulazioni impraticabili con
MASON eseguito su una singola macchina.
– Capacità di sfruttare hardware eterogeneo.
– Scalabilità del sistema in termini del numero di
agenti e grandezza del campo.
25
Testing – Scalabilità di D-MASON
• Il test confronta le prestazioni di MASON e di D-MASON.
– I tempi di esecuzione al variare del numero di agenti e macchine del sistema
distribuito.
7 HOST : Intel i7-2600 4x3,4GHz con HT 8GB RAM JVM 32 bit
Avg simulation step timing (s)
14
12
10
8
6
Mason
4
DMason 2x2, (1,1,1,1)
DMason 3x3, (2,2,2,2,1)
2
DMason 4x4, (3,3,3,3,2,2)
0
DMason 5x5, (4,4,4,4,3,3,3)
0
2000000
4000000
6000000
8000000
Agents
10000000
12000000
14000000
26
Testing D-MASON
Il sistema eterogeneo utilizzato è composto dalle macchine:
Macchina 1
Pentium 4 - 3,4 GHz - 2GB di RAM - Win XP 32bit
Macchina 2
2 x Xeon - 2,67 GHz - 3GB di RAM - Win7 32 bit
Macchina 3
2 x AMD Opteron 252 – 1.9 GHz - 4GB di RAM - Win 7 64bit
Macchina 4
i5 2 x 2,53GHz con HT - 4GB di RAM - Win7 64bit
Macchina 5
i7-2600 4 x 3,4GHz con HT - 8GB di RAM - Win7 64bit
- Si confrontano i tempi di esecuzione di una particolare simulazione al
variare del carico di lavoro di ogni macchina del sistema.
- Il numero di agenti simulati è di 3 e 5 milioni.
27
Testing – Sistema Eterogeneo
3,000,000 Agents
5,000,000 Agents
Avg simulation step timing (s)
20
19,65
15
12,70
11,87
10,75
9,88
10
11,48
9,16
9,15
7,43
7,24
6,25
5,61
5,65
5,52
5
0
(0,0,0,0,25)
(1,1,1,1,21)
(1,2,2,2,18)
(1,2,2,3,17)
(1,2,2,4,16)
Configurations (P4, Xeon, Opt, I5,I7)
(1,3,3,6,12)
(5,5,5,5,5)
28
Punti di forza
• D-MASON ottimizza l’uso di sistemi multi-core, permettendo
di incrementare il numero di agenti simulabili rispetto a
MASON.
• D-MASON richiede mirate modifiche a simulazioni
preesistenti in MASON.
• D-MASON permette di sfruttare l’eterogeneità di un sistema
non composto solo da macchine ad alte prestazioni (come nei
laboratori di ricerca)
29
Sviluppi futuri
• Visualizzazione grafica centralizzata
• Load Balancing
• Overlay P2P
30
31
Grazie per l’attenzione.
32