Nel corso degli anni la simulazione ha progressivamente assunto un ruolo di primo piano come strumento di supporto alla progettazione, alla verifica e alla valutazione di prestazioni di sistemi. I sistemi attualmente considerati d'interesse sono spesso caratterizzati da un’estrema complessità: sono dinamici, formati da entità eterogenee e spesso massivamente popolati. Soprattutto in passato, la loro analisi basata sulle tecniche di simulazione è stata vincolata dalle ridotte capacità di calcolo. L’approccio caratterizzato da un’eccessiva semplificazione del modello concettuale ha spesso portato a risultati incompleti o errati. La progettazione e la valutazione delle performance di sistemi complessi, in particolare se di supporto a strutture di vitale importanza, non possono prescindere dagli strumenti di simulazione a disposizione. L’analisi di modelli complessi suggerisce naturalmente un approccio basato su simulazione parallela o distribuita. Questo approccio, anche se molto promettente, non è sempre prestazionalmente proficuo. I modelli intrinsecamente caratterizzati da un’elevata dinamicità spesso introducono tali overhead di comunicazione da vanificare i vantaggi offerta dalla parallelizzazione del carico. Per ovviare a questi problemi si sono cercate varie soluzioni, usualmente basate su meccanismi di filtraggio delle interazioni (Data Distribution Management, DDM). Lo standard IEEE 1516 (High Level Architecture) rappresenta l’attuale punto di riferimento per l’implementazione di simulazioni distribuite. Purtroppo la sua analisi ha evidenziato lacune significative sia nell'architettura che nelle implementazioni attualmente disponibili sul mercato. Ad esempio, l’assenza di un paradigma basato sulla migrazione delle entità simulate rende difficile l’elaborazione di sistemi dinamici (es. reti wireless Ad-Hoc, reti di sensori ecc.) salvo che non si faccia uso di ulteriori componenti software esterne al middleware.
L'assenza di implementazioni dello standard Open Source (o con codice facilmente utilizzabile a fini di ricerca) e la ricerca di migliori prestazioni ha portato al design e all’implementazione di ARTÌS (Advanced RTI System), un middleware adattivo fortemente basato sul riutilizzo delle componenti. Il middleware è espressamente orientato alla simulazione parallela e distribuita, pur essendo utilizzabile anche per l'implementazione di simulazioni monolitiche.
L'approccio parallelo e distribuito potenzialmente offre numerosi vantaggi, soprattutto in contesti come:
Nel seguito di questo documento verranno introdotti i concetti principali che caratterizzano il runtime ARTÌS e la sua struttura logica generale. Verranno passati in rassegna i moduli principali che compongono il middleware, le Application Programming Interfaces (API) attualmente disponibili e alcuni esempi di utilizzo.
Il runtime ARTÌS nasce con il preciso obiettivo di supportare efficientemente simulazioni di scenari complessi seguendo un approccio ambito parallelo e distribuito. La struttura logica altamente modulare è stata riflessa in un’implementazione basata su componenti che sono facilmente estendibili. Tipicamente il punto critico dei sistemi distribuiti è rappresentato dall’overhead introdotto dalla latenza nelle comunicazioni di rete, questa è estremamente variabile a seconda della tipologia di rete utilizzata (la latenza di una comunicazione attraverso un bus è ordini di grandezza inferiore rispetto alla comunicazione degli stessi dati su Internet). Ottenere prestazioni di un certo interesse significa quindi distribuire la computazione e minimizzare il costo di comunicazione, traendo vantaggio da eventuale memoria condivisa su piattaforme multiprocessore e da protocolli ottimizzati a seconda dell’architettura di rete utilizzata. Nella nostra visione queste funzionalità dovrebbero essere rese disponibili in maniera quanto più trasparente possibile all’utente finale, possibilmente in modo del tutto adattivo, senza penalizzare le prestazioni. Una delle caratteristiche cruciali tipiche di qualsiasi runtime dedicato alla simulazione è la gestione del tempo: nel corso degli anni sono state sviluppate varie tecniche di gestione della sincronizzazione in ambiente parallelo e distribuito. A seconda del modello simulato è possibile trarre vantaggi da algoritmi di sincronizzazione diversi. Al momento ARTÌS mette a disposizione il supporto per simulazioni ad approccio pessimistico (Chandy-Misra-Bryant, Timestepped) e il supporto per la sincronizzazione ottimistica (Time-Warp). A differenza di quanto avviene nello standard IEEE 1516, ARTÌS intende offrire supporto nativo a varie tecniche di migrazione delle componenti, la possibilità di integrare questa metodologia modificando direttamente gli algoritmi di sincronizzazione permette una migliore gestione degli overhead. Spesso i runtime risultano opachi all’utente durante l’esecuzione, è impossibile accedere alle informazioni dettagliate di funzionamento, tra l’altro questa caratteristica rende difficoltosa un’eventuale ottimizzazione del modello simulato. Per ovviare a questo inconveniente è stato previsto un meccanismo di real-time introspection attraverso il quale gran parte delle informazioni interne al runtime sono rese disponibili all’utente finale tramite un meccanismo di publishing/subscribe, inoltre questo sistema permette la riconfigurazione durante l’esecuzione dei parametri di funzionamento del middleware.
È evidente come la comunicazione rivesta un ruolo essenziale nella ricerca delle prestazioni per le simulazioni parallele e distribuite. Partendo da questo concetto è altrettanto evidente come nell’implementazione di un middleware sia necessario ottimizzare il sistema di comunicazione, per adattarlo alle varie architetture a seconda delle loro peculiarità. L’approccio classico alla simulazione distribuita prevede un insieme di Logical Process (LP) che interagiscono tra di loro attraverso semplici primitive di comunicazione. Nell’implementazione ARTÌS ogni LP risulta basato su un’architettura multithread: ogni thread è dedicato alla gestione della comunicazione su un singolo canale di input/output al fine di svincolare la componente simulativa vera e propria del processo logico dalle problematiche di comunicazione. Uno degli obiettivi del nostro progetto è la creazione di un middleware in grado di ottenere buone prestazioni su architetture miste (formate da sistemi multiprocessore e monoprocessori collegati in rete), abbiamo quindi lavorato in modo da rendere il meccanismo di comunicazione adattivo rispetto all’ambiente di esecuzione. Allo stato attuale di sviluppo ARTÌS comunica attraverso Shared Memory, dove possibile, e TCP/IP negli altri casi. Dall’architettura logica (Fig 2.1) si può notare come siano previste anche soluzioni basate su Reliable UDP e ottimizzazioni su multicast dove disponibile: inoltre la modularità è garantita in questo caso dalla natura multi-threaded dell’architettura, che permette appunto l’estensione a nuovi protocolli tramite l’aggiunta di ulteriori thread per la comunicazione.
Le componenti relative ai Services implementano parzialmente i servizi tipicamente offerti da un RTI Kernel, fornendo i servizi di Time, Federation, Declaration ecc. Management tipici di ogni middleware per la simulazione. Per quanto tali componenti costituiscano il vero cuore del runtime, l’utente finale può rimanere all’oscuro dei dettagli implementativi, accedendo alle funzionalità grazie a funzioni di libreria, che offrono all’utente l’interfaccia attraverso la quale accedere ai servizi di sincronizzazione e comunicazione.
Le API messe a disposizione dal middleware sono multiple, una versione base rappresentata dalle Unibo API disponibili in binding C/C++. A queste API iniziali è previsto si aggiunga un livello di compatibilit`a High Level Architecture IEEE 1516 e alcune versioni semplificate e specializzate per obiettivi particolari (es. Internet Gaming API).
Real-Time Introspection, Logging, Performance, Migration e Utility intendono rappresentare una serie di moduli di servizio a supporto del runtime, integrati nel middleware e con obiettivi diversificati. Proprio per la loro peculiarità, tali moduli sono abilitati opzionalmente in modo da non interferire con le prestazioni del middleware in un contesto normale. Si tratta di funzionalità avanzate, utili in fase di debug o durante la fase di progettazione del modello, che è quindi opportuno poter disabilitare.
L’implementazione attuale offre un sottoinsieme limitato delle funzionalità preventivate per la versione completa del runtime. Questo sottoinsieme è comunque sufficiente per l’implementazioni di modelli basati su diversi approcci. La natura prettamente in sviluppo del lavoro non permette di assicurare il mantenimento della compatibilità tra le varie versioni del runtime che si succederanno nel tempo. Il riscontro degli utenti ricopre comunque una notevole importanza: ARTÌS uno strumento che ha l’obiettivo di facilitare l’implementazione di simulazioni. Per la sua natura, non è previsto che il runtime sia utilizzabile senza una prepazione basilare su temi come i sistemi distribuiti [6], la simulazione e la sincronizzazione. Allo stesso tempo riteniamo comunque indispensabile che tutta una serie di ottimizzazioni siano automatiche e demandate al runtime, senza alcun intervento da parte dell’utilizzatore. La trasparenza dei meccanismi di comunicazione, unita all’adattività del sistema apportano flessibilità e facilitano molte fasi del lavoro, ma il punto focale delle simulazioni rimane la descrizione del modello, la sua correttezza ed implementazione. Senza un’adeguata descrizione del contesto da ricreare sarà impossibile ottenere risultati fedeli, indipendentemente dal runtime utilizzato.
L’architettura dell’implementazione risulta parzialmente centralizzata per la presenza di un SImulation MAnager che ricopre vari compiti tra i quali la coordinazione degli LP, l’inizializzazione e terminazione della simulazione, la gestione di barriere di sincronizzazione durante l’esecuzione. Il SIMA è a conoscenza del numero totale di LP, e della natura dei canali di comunicazione che li collegano. Esso rileva la disposizione topologica degli host (secondo la nostra terminologia PEU, Physical Execution Unit) ed indica ad ognuno di essi come instaurare il dialogo con gli altri. In pratica, è necessario eseguire prima della simulazione vera e propria una fase di inizializzazione dei canali di trasmissione, cos`ı da predisporre ogni LP alla comunicazione con gli altri nel modo più efficiente possibile.
Il codice del SIMA dovrà avere una struttura di questo tipo:
SIMA Initialize(porta, lps,channels.txt); ... SIMA Finalize( );
Il file di configurazione indica al runtime quali siano i valori di lookahead su ogni singolo canale, oppure specifica un valore globale e comune a tutti gli LP. Esso dovrebbe essere composto in due parti: la prima per definire i canali di comunicazione ed i loro nomi, la seconda per specificare un valore di lookahead. Quest’ultimo potrà essere di tipo globale, cioè comune a tutti gli LP, oppure distinto per ognuno di essi (solo nel caso Chandy-Misra-Bryant) , come nell’esempio seguente:
# DEFINIZIONE DEI CANALI: :MILANO 0 :BOLOGNA 1 :ROMA 2 #DEFINIZIONE DEI LOOKAHEAD GLOBAL LA=0 # Look−Ahead Globale Disabilitato MILANO: BOLOGNA 5 ROMA 7 ROMA: MILANO 7 BOLOGNA 3 BOLOGNA: MILANO 5 ROMA 3
Nella prima parte vengono associati ID numerici alle etichette che identificano gli LP, quindi si procede con la specifica del lookahead per ognuno di essi, se il modello lo prevede, oppure con l’inserimento di un valore positivo nel campo GLOBAL_LA. Esso segnala che il lookahead sarà lo stesso per tutti gli LP e lo quantifica (nell’esempio non viene usato lookahead globale). Nel file di configurazione le linee che iniziano con il simbolo # sono considerate come commenti.
Attualmente sono implementati due diversi meccanismi di sincronizzazione en- trambi basati su approccio pessimistico:
Le procedure di sincronizzazione e gestione dei messaggi sono dichiarate nelle librerie TS.h e CMB.h, all’interno della cartella INCLUDE. Esse mettono a disposizione dell’utente le funzioni descritte nel paragrafo seguente.
Tutte le funzioni elencate restituiscono un valore negativo in caso di errore. In particolare, per le chiamate relative all’invio di messaggi (CMB Send, Broadcast, SendToOthers), devono essere rispettati i vincoli temporali imposti dal valore del lookahead al momento dell’invocazione per ognuno dei destinatari. Nessuna delle funzioni adibite all’invio di messaggi è bloccante. Per evitare di ottenere risultati solo apparentemente corretti, è consigliabile verificare il valore di ritorno di tali funzioni, in caso esso risulti negativo, per avere una descrizione dell’errore è possibile controllare la stringa cmb error[MAX ERROR STRING], previa dichiarazione extern della stessa. Oltre ai vincoli temporali, possono infatti incorrere altre problematiche comuni negli ambienti distribuiti (overflow, time-out di rete, ecc).
Le funzioni di libreria offerte dalla libreria TimeStepped sono del tutto analoghe a quelle appena descritte, con l’omissione delle due funzioni per la gestione del lookahead, in quanto esso viene specificato staticamente all’interno dei file di configurazione del modello. L’invocazione della funzione TimeAdvance conclude lo step passando al successivo.
Uno degli esempi più diffusi nella simulazione è quello del traffico aereo. La semplicità del modello concettuale, ed il ridotto numero di relazioni causali lo rende particolarmente adatto per illustrare il funzionamento di una simulazione. Ovviamente sono tralasciati molti aspetti fondamentali del contesto reale (es. altitudine degli aeroplani), ma secondari considerando la natura e gli scopi prettamente didattici. All’interno della cartella EXAMPLES/AIRPORTS si trova il codice relativo al modello, implementato con l’algoritmo TimeStepped. In pratica è suddiviso in 3 sezioni: le variabili di stato del simulatore, i gestori degli eventi e la funzione main, che inizializza le variabili e “spedisce” i primi aeroplani, quindi entra in un ciclo while che riceve i messaggi successivi ed invoca per ognuno di essi un handler appropriato, fino al raggiungimento del limite temporale impostato per la conclusione. Il flusso di aerei tra i diversi aeroporti è implementato tramite un semplice scambio di messaggi.
typedef struct sub msg header {
char event type[4]; //Arrival, Landing or Departure
char from[10]; //Airport from which the message arrives
char id[12]; //Name of the fly
} SubMsgHeader;
La variabile event type può rappresentare 3 diversi stati: Partenza, Arrivo ed Atterraggio. Il ciclo di vita di un aeroplano inizia nel suo aeroporto d’origine, dove al tempo 0 viene schedulata la prima partenza verso un aeroporto scelto a caso tra i due disponibili. Da questo momento, esso continuerà ad arrivare, attendere che si liberi la pista di atterraggio, atterrare scaricare i passeggeri e ripartire, fino al timestamp definito come termine della simulazione. La modellazione del modello `e estremamente lineare, in quanto si possono facilmente individuare gli handler necessari e la politica con la quale la simulazione procede. Il ciclo while all’interno della funzione main chiarifica ulteriormente questa semplice struttura:
/*Simulation main loop, receives messages and calls procedure associated with it*/
while (!end reached) {
size = TS Receive(&from, &Ts, (void *)msg, 1024);
if (size > 0) {//A message has been received, process it calling appropriate handler
submsg = (SubMsgHeader *)msg;
if (strcmp (submsg−>event type, "ARR")==0)
arrival event handler (clock, submsg−>from, submsg−>id); 10
if (strcmp (submsg−>event type, "LAN")==0)
landed event handler (clock, submsg−>from, submsg−>id);
if (strcmp (submsg−>event type, "DEP")==0)
departure event handler (clock, submsg−>id);
}
else {//no new messages, and end clock reached
if (clock == end clock) {
printf ("[%s]: condiz. arresto raggiunta...); 20
end˙reached = 1;
TS˙Finalize();
}
else//no new messages, and end clock still not reached
clock = TS˙TimeAdvance();
}
}
Si distinguono facilmente due casi, dipendentemente dall’arrivo di nuovi messaggi. Tale controllo viene eseguito sulla dimensione ritornata dalla funzione TS_Receive(): nel caso esso sia maggiore di zero, si può procedere all’elaborazione dell’evento passandolo all’handler. In caso contrario, se la simulazione è terminata (end clock = 1) viene invocata la TS Finalize(), se non è così dobbiamo attendere l’arrivo di un nuovo messaggio e far avanzare il tempo. La directory di questo esempio comprende uno script (run) che lancia prima il SIMA ed in seguito tre istanze di airports ts, deviando l’output di ogni singolo LP sui file x.out-ts e x.err-ts. All’interno di essi compare una riga per ogni evento, con l’indicazione del tempo simulato pi`u altre informazioni utili per ricostruire l’andamento della simulazione; si nota come la scelta delle destinazioni sia casuale, e come la definizione dei tempi di atterraggio/carico/partenza influisca sul numero totale di voli effettuati in un intervallo predefinito (2000). Lo script va eseguito passando come primo argomento l’eseguibile che si intende utilizzare.
All’interno della directory EXAMPLES/AIRPORTS si trova un esempio del tutto analogo al precedente, solo implementato utilizzando l’algoritmo Chandy/Misra/Bryant. A fronte di un’apparente analogia con il modello Time-Stepped, questo scenario simulato sfrutta un differente algoritmo di sincronizzazione. Descrivere nei dettagli questo modello sarebbe ridondante, è stato incluso a scopo didattico per permettere di studiare le analogie/differenze tra i due algoritmi. Principalmente, nel ciclo main() non compare la funzione per l’avanzamento del tempo, ed all’interno del file channels.txt sono da definire i lookahead per ognuno dei canali. Nel caso della simulazione del traffico aereo, il lookahead di un canale corrisponde alla durata minima del viaggio tra i due rispettivi aeroporti.
Allo scopo di includere un esempio più concreto, pur rimanendo in un ambito didattico, è stato incluso un modello di reti Wireless estremamente semplificato, che rappresenta lo scambio di messaggi PING tra un numero arbitrario di Host simulati (Simulted Mobile Hosts, SMH) in movimento. Ognuno di essi ha un determinato raggio di copertura, e si sposta all’interno di uno spazio bidimensionale toroidale. Il modello sfrutta le primitive fornite da ARTÌS (Time-Stepped) per far comunicare tra loro gli host simulati su LP distinti, e come negli esempi precedenti il ruolo del SImulation MAnager è quello di coordinarli in fase di inizializzazione. È importante notare come ogni LP gestisca solamente una parte degli host simulati. Ad ogni step della simulazione, ogni host esegue un PING verso tutti gli altri host che si trovano in sua prossimit`a (all’interno del suo raggio di copertura). Successivamente l’host simulato con probabilità del 50% si muove su una direzione casuale. Analizzando il traffico uscente dagli LP si può notare come ad ogni step vengano inviati i messaggi di PING dei vari host simulati (SMH) e gli aggiornamenti relativi alla loro posizione, necessari per mantenere aggiornato lo stato globale del sistema.