Analisi di grafi su architetture a memoria distribuita

Questo lavoro di tesi tratta il tema delle reti complesse, mostrando i principali modelli di rete complessa quali: il modello Random, il modello Small-World ed il modello Scale-free; si introdurranno alcune metriche usate per descrivere le reti complesse quali la Degree centrality, la Closeness centrality e la Betweenness centrality; si descriveranno i problemi da tenere in considerazione durante la definizione e l’implementazione di algoritmi su grafi; i modelli di calcolo su cui progettare gli algoritmi per risolvere i problemi su grafi; un’analisi prestazionale degli algoritmi proposti per calcolare i valori di Beweenness centrality su grafi di medio-grandi dimensioni. Parte di questo lavoro di tesi è consistito nello sviluppo di LANA, LArge-scale Network Analyzer, un software che permette il calcolo e l’analisi di varie metriche di centralità su grafo.

Large-scale Network Analysis on Distributed Architectures

Questa dissertazione esamina le sfide e i limiti che gli algoritmi di analisi di grafi incontrano in architetture distribuite costituite da personal computer. In particolare, analizza il comportamento dell'algoritmo del PageRank così come implementato in una popolare libreria C++ di analisi di grafi distribuiti, la Parallel Boost Graph Library (Parallel BGL). I risultati qui presentati mostrano che il modello di programmazione parallela Bulk Synchronous Parallel è inadatto all'implementazione efficiente del PageRank su cluster costituiti da personal computer. L'implementazione analizzata ha infatti evidenziato una scalabilità negativa, il tempo di esecuzione dell'algoritmo aumenta linearmente in funzione del numero di processori. Questi risultati sono stati ottenuti lanciando l'algoritmo del PageRank della Parallel BGL su un cluster di 43 PC dual-core con 2GB di RAM l'uno, usando diversi grafi scelti in modo da facilitare l'identificazione delle variabili che influenzano la scalabilità. Grafi rappresentanti modelli diversi hanno dato risultati differenti, mostrando che c'è una relazione tra il coefficiente di clustering e l'inclinazione della retta che rappresenta il tempo in funzione del numero di processori. Ad esempio, i grafi Erdős–Rényi, aventi un basso coefficiente di clustering, hanno rappresentato il caso peggiore nei test del PageRank, mentre i grafi Small-World, aventi un alto coefficiente di clustering, hanno rappresentato il caso migliore. Anche le dimensioni del grafo hanno mostrato un'influenza sul tempo di esecuzione particolarmente interessante. Infatti, si è mostrato che la relazione tra il numero di nodi e il numero di archi determina il tempo totale.

Progettazione ed implementazione di strumenti per la valutazione di reti complesse con proprietà scale-free

Il cervello è una rete di cellule nervose connesse da assoni e le cellule stesse sono reti di molecole connesse da reazioni biochimiche. Anche le società sono reti di persone collegate da rapporti di amicizia, parentela e legami professionali. Su più larga scala, catene alimentari ed ecosistemi possono essere rappresentati come reti di specie viventi. E le reti pervadono la tecnologia: Internet, reti elettriche e sistemi di trasporto non sono che pochi degli esempi possibili. Anche il linguaggio che si sta usando in questo momento per veicolare questi ragionamenti a chi legge è una rete, fatta di parole connesse da relazioni sintattiche. A dispetto dell'importanza e della pervasività delle reti, gli scienziati hanno sempre avuto poca comprensione delle loro strutture e proprietà. In che modo le interazioni di alcuni nodi non funzionanti in una complessa rete genetica possono generare il cancro? Come può avvenire così rapidamente la diffusione in taluni sistemi sociali e di comunicazioni, portando ad epidemie di malattie e a virus informatici? Come possono alcune reti continuare a funzionare anche dopo che la maggioranza dei loro nodi ha, invece, smesso di farlo? [...] Le reti reali sono realmente casuali?

Una semantica distribuita per il Multi-CCS utilizzando reti di Petri

Questa tesi descrive e approfondisce l'algebra di processo Multi-CCS, le fornisce una semantica basata sulle reti di Petri non limitate - a correzione e miglioramento della precedente - e una dimostrazione dettagliata della sua correttezza, ovvero della bisimilitudine tra la marcatura ottenuta dalla uova semantica e da un generico processo Multi-CCS e lo stesso processo nella semantica di default definita sugli LTS

Rassegna di strutture dati e algoritmi per l'indicizzazione di basi di dati.

La frenetica evoluzione sociale e culturale, data dal crescente e continuo bisogno di conoscenza dell’uomo, ha portato oggi a navigare in un oceano sconfinato di dati e informazioni. Esse assumono una propria peculiare importanza, un valore sia dal punto di vista del singolo individuo, sia all’interno di un contesto sociale e di un settore di riferimento specifico e concreto. La conseguente mutazione dell’interazione e della comunicazione a livello economico della società, ha portato a parlare oggi di economia dell’informazione. In un contesto in cui l’informazione rappresenta la risorsa principale per l’attività di crescita e sviluppo economico, è fondamentale possedere la più adeguata strategia organizzativa per la gestione dei dati grezzi. Questo per permetterne un’efficiente memorizzazione, recupero e manipolazione in grado di aumentare il valore dell’organizzazione che ne fa uso. Un’informazione incompleta o non accurata può portare a valutazioni errate o non ottimali. Ecco quindi la necessità di gestire i dati secondo specifici criteri al fine di creare un proprio vantaggio competitivo. La presente rassegna ha lo scopo di analizzare le tecniche di ottimizzazione di accesso alle basi di dati. La loro efficiente implementazione è di fondamentale importanza per il supporto e il corretto funzionamento delle applicazioni che ne fanno uso: devono garantire un comportamento performante in termini di velocità, precisione e accuratezza delle informazioni elaborate. L’attenzione si focalizzerà sulle strutture d’indicizzazione di tipo gerarchico: gli alberi di ricerca. Verranno descritti sia gli alberi su dati ad una dimensione, sia quelli utilizzati nel contesto di ricerche multi dimensionali (come, ad esempio, punti in uno spazio). L’ingente sforzo per implementare strutture di questo tipo ha portato gli sviluppatori a sfruttare i principi di ereditarietà e astrazione della programmazione ad oggetti al fine di ideare un albero generalizzato che inglobasse in sé tutte le principali caratteristiche e funzioni di una struttura di indicizzazione gerarchica, così da aumentarne la riusabilità per i più particolari utilizzi. Da qui la presentazione della struttura GiST: Generalized Search Tree. Concluderà una valutazione dei metodi d’accesso esposti nella dissertazione con un riepilogo dei principali dati relativi ai costi computazionali, vantaggi e svantaggi.

Impatto della propagazione elettromagnetica sulle prestazioni delle reti M3N

Con il termine Smart Grid si intende una rete urbana capillare che trasporta energia, informazione e controllo, composta da dispositivi e sistemi altamente distribuiti e cooperanti. Essa deve essere in grado di orchestrare in modo intelligente le azioni di tutti gli utenti e dispositivi connessi al fine di distribuire energia in modo sicuro, efficiente e sostenibile. Questo connubio fra ICT ed Energia viene comunemente identificato anche con il termine Smart Metering, o Internet of Energy. La crescente domanda di energia e l’assoluta necessità di ridurre gli impatti ambientali (pacchetto clima energia 20-20-20 [9]), ha creato una convergenza di interessi scientifici, industriali e politici sul tema di come le tecnologie ICT possano abilitare un processo di trasformazione strutturale di ogni fase del ciclo energetico: dalla generazione fino all’accumulo, al trasporto, alla distribuzione, alla vendita e, non ultimo, il consumo intelligente di energia. Tutti i dispositivi connessi, diventeranno parte attiva di un ciclo di controllo esteso alle grandi centrali di generazione così come ai comportamenti dei singoli utenti, agli elettrodomestici di casa, alle auto elettriche e ai sistemi di micro-generazione diffusa. La Smart Grid dovrà quindi appoggiarsi su una rete capillare di comunicazione che fornisca non solo la connettività fra i dispositivi, ma anche l’abilitazione di nuovi servizi energetici a valore aggiunto. In questo scenario, la strategia di comunicazione sviluppata per lo Smart Metering dell’energia elettrica, può essere estesa anche a tutte le applicazioni di telerilevamento e gestione, come nuovi contatori dell’acqua e del gas intelligenti, gestione dei rifiuti, monitoraggio dell’inquinamento dell’aria, monitoraggio del rumore acustico stradale, controllo continuo del sistema di illuminazione pubblico, sistemi di gestione dei parcheggi cittadini, monitoraggio del servizio di noleggio delle biciclette, ecc. Tutto ciò si prevede possa contribuire alla progettazione di un unico sistema connesso, dove differenti dispositivi eterogenei saranno collegati per mettere a disposizione un’adeguata struttura a basso costo e bassa potenza, chiamata Metropolitan Mesh Machine Network (M3N) o ancora meglio Smart City. Le Smart Cities dovranno a loro volta diventare reti attive, in grado di reagire agli eventi esterni e perseguire obiettivi di efficienza in modo autonomo e in tempo reale. Anche per esse è richiesta l’introduzione di smart meter, connessi ad una rete di comunicazione broadband e in grado di gestire un flusso di monitoraggio e controllo bi-direzionale esteso a tutti gli apparati connessi alla rete elettrica (ma anche del gas, acqua, ecc). La M3N, è un’estensione delle wireless mesh network (WMN). Esse rappresentano una tecnologia fortemente attesa che giocherà un ruolo molto importante nelle futura generazione di reti wireless. Una WMN è una rete di telecomunicazione basata su nodi radio in cui ci sono minimo due percorsi che mettono in comunicazione due nodi. E’ un tipo di rete robusta e che offre ridondanza. Quando un nodo non è più attivo, tutti i rimanenti possono ancora comunicare tra di loro, direttamente o passando da uno o più nodi intermedi. Le WMN rappresentano una tipologia di rete fondamentale nel continuo sviluppo delle reti radio che denota la divergenza dalle tradizionali reti wireless basate su un sistema centralizzato come le reti cellulari e le WLAN (Wireless Local Area Network). Analogamente a quanto successo per le reti di telecomunicazione fisse, in cui si è passati, dalla fine degli anni ’60 ai primi anni ’70, ad introdurre schemi di rete distribuite che si sono evolute e man mano preso campo come Internet, le M3N promettono di essere il futuro delle reti wireless “smart”. Il primo vantaggio che una WMN presenta è inerente alla tolleranza alla caduta di nodi della rete stessa. Diversamente da quanto accade per una rete cellulare, in cui la caduta di una Base Station significa la perdita di servizio per una vasta area geografica, le WMN sono provviste di un’alta tolleranza alle cadute, anche quando i nodi a cadere sono più di uno. L'obbiettivo di questa tesi è quello di valutare le prestazioni, in termini di connettività e throughput, di una M3N al variare di alcuni parametri, quali l’architettura di rete, le tecnologie utilizzabili (quindi al variare della potenza, frequenza, Building Penetration Loss…ecc) e per diverse condizioni di connettività (cioè per diversi casi di propagazione e densità abitativa). Attraverso l’uso di Matlab, è stato quindi progettato e sviluppato un simulatore, che riproduce le caratteristiche di una generica M3N e funge da strumento di valutazione delle performance della stessa. Il lavoro è stato svolto presso i laboratori del DEIS di Villa Grifone in collaborazione con la FUB (Fondazione Ugo Bordoni).

Sviluppo di algoritmi per l'automazione di misure industriali

Oggi, grazie al continuo progredire della tecnologia, in tutti i sistemi di produzione industriali si trova almeno un macchinario che permette di automatizzare determinate operazioni. Alcuni di questi macchinari hanno un sistema di visione industriale (machine vision), che permette loro di osservare ed analizzare ciò che li circonda, dotato di algoritmi in grado di operare alcune scelte in maniera automatica. D’altra parte, il continuo progresso tecnologico che caratterizza la realizzazione di sensori di visione, ottiche e, nell’insieme, di telecamere, consente una sempre più precisa e accurata acquisizione della scena inquadrata. Oggi, esigenze di mercato fanno si che sia diventato necessario che macchinari dotati dei moderni sistemi di visione permettano di fare misure morfometriche e dimensionali non a contatto. Ma le difficoltà annesse alla progettazione ed alla realizzazione su larga scala di sistemi di visione industriali che facciano misure dimensioni non a contatto, con sensori 2D, fanno sì che in tutto il mondo il numero di aziende che producono questo tipo di macchinari sia estremamente esiguo. A fronte di capacità di calcolo avanzate, questi macchinari necessitano dell’intervento di un operatore per selezionare quali parti dell’immagine acquisita siano d’interesse e, spesso, anche di indicare cosa misurare in esse. Questa tesi è stata sviluppata in sinergia con una di queste aziende, che produce alcuni macchinari per le misure automatiche di pezzi meccanici. Attualmente, nell’immagine del pezzo meccanico vengono manualmente indicate le forme su cui effettuare misure. Lo scopo di questo lavoro è quello di studiare e prototipare un algoritmo che fosse in grado di rilevare e interpretare forme geometriche note, analizzando l’immagine acquisita dalla scansione di un pezzo meccanico. Le difficoltà affrontate sono tipiche dei problemi del “mondo reale” e riguardano tutti i passaggi tipici dell’elaborazione di immagini, dalla “pulitura” dell’immagine acquisita, alla sua binarizzazione fino, ovviamente, alla parte di analisi del contorno ed identificazione di forme caratteristiche. Per raggiungere l’obiettivo, sono state utilizzate tecniche di elaborazione d’immagine che hanno permesso di interpretare nell'immagine scansionata dalla macchina tutte le forme note che ci siamo preposti di interpretare. L’algoritmo si è dimostrato molto robusto nell'interpretazione dei diametri e degli spallamenti trovando, infatti, in tutti i benchmark utilizzati tutte le forme di questo tipo, mentre è meno robusto nella determinazione di lati obliqui e archi di circonferenza a causa del loro campionamento non lineare.