Un algoritmo genetico parallelo per la k-colorabilità

Implementazione mediante librerie MPI di un algoritmo genetico parallelo per risolvere il problema sulla k-colorabilità. La tesi descrive la versione sequenziale dell'algoritmo genetico di riferimento e l'implementazione della sua versione parallela. Vi è una fase di analisi dei risultati ottenuti dai test effettuati su una macchina ad architettura parallela.

Analisi spaziale della longevità in Emilia-Romagna

Negli ultimi anni la longevità è divenuto un argomento di notevole interesse in diversi settori scientifici. Le ricerche volte ad indagare i meccanismi che regolano i fattori della longevità si sono moltiplicate nell’ultimo periodo interessando, in maniera diversa, alcune regioni del territorio italiano. Lo studio presentato nella tesi ha l’obiettivo di identificare eventuali aggregazioni territoriali caratterizzate da una significativa propensione alla longevità nella regione Emilia-Romagna mediante l’impiego di metodologie di clustering spaziale, alcune delle quali di recente implementazione. La popolazione in esame è costituita dagli individui residenti in Emilia- Romagna nel quinquennio 2000-2004 suddivisa in classi di età, sesso e comune. L’analisi è di tipo puramente spaziale, in cui l’unità geografica elementare è identificata dal comune, ed è stata condotta separatamente per i due sessi. L’identificazione delle aree regionali ad elevata longevità è avvenuta utilizzando quattro metodologie di clustering spaziale, basate sulla teoria della massima verosimiglianza, che si differenziano tra loro per la modalità di ricerca dei potenziali clusters. La differenza consiste nella capacità di identificare aggregazioni territoriali di forma regolare (spatial scan statistic, Kulldorff e Nagarwalla,1995; Kulldorff,1997, 1999) o dall’andamento geometrico “libero” (flexible scan statistic, Tango e Takahashi,2005; algoritmo genetico, Duczmal et al.,2007; greedy growth search, Yiannakoulias et al.,2007). Le caratteristiche di ciascuna metodologia consentono, in tal modo, di “catturare” le possibili conformazioni geografiche delle aggregazioni presenti sul territorio e la teoria statistica di base, comune ad esse, consente di effettuare agevolmente un confronto tra i risultati ottenuti. La persistenza di un’area caratterizzata da un’elevata propensione alla longevità consente, infatti, di ritenere il cluster identificato di notevole interesse per approfondimenti successivi. Il criterio utilizzato per la valutazione della persistenza di un cluster è stato derivato dalla teoria dei grafi, con particolare riferimento ai multigrafi. L’idea è confrontare, a parità di parametri di ricerca, i grafi associati alle aggregazioni spaziali identificate con le diverse metodologie attraverso una valutazione delle occorrenze dei collegamenti esistenti tra le coppie di vertici. Alcune valutazioni di carattere demografico ed un esame della letteratura esistente sugli studi di longevità, hanno indotto alla definizione di una classe (aperta) di età per rappresentare il fenomeno nella nostra ricerca: sono stati considerati gli individui con età superiore o uguale a 95 anni (indicata con 95+). La misura di sintesi utilizzata per descrivere il fenomeno è un indicatore specifico di longevità, mutuato dalla demografia, indicato con Centenarian Rate (CR) (Robine e Caselli, 2005). Esso è definito dal rapporto tra la popolazione 95+ e la popolazione residente, nello stesso comune, al censimento del 1961. L’idea alla base del CR è confrontare gli individui longevi di un istante temporale con quelli presenti, nella stessa area, circa 40 anni prima dell’osservazione, ipotizzando che l’effetto migratorio di una popolazione possa ritenersi trascurabile oltre i 60 anni di età. La propensione alla longevità coinvolge in maniera diversa le aree del territorio dell’Emilia-Romagna. Le province della regione caratterizzate da una maggiore longevità sono Bologna, Ravenna e parte di Forlì-Cesena mentre la provincia di Ferrara si distingue per un livello ridotto del fenomeno. La distinzione per sesso non appare netta: gli uomini con età 95+, numericamente inferiori alle donne, risiedono principalmente nei comuni delle province di Bologna e Ravenna, con qualche estensione nel territorio forlivese, analogamente a quanto accade per la popolazione femminile che mostra, tuttavia, una maggiore prevalenza nei territori di Bologna e Forlì-Cesena, includendo alcune aree del riminese. Le province occidentali della regione, invece, non risultano interessate significativamente da questo fenomeno. Le metodologie di cluster detection utilizzate nello studio hanno prodotto risultati pressoché simili seppur con criteri di ricerca differenti. La spatial scan statistic si conferma una metodologia efficace e veloce ma il vincolo geometrico regolare imposto al cluster condiziona il suo utilizzo, rivelando una scarsa adattabilità nell’identificazione di aggregazioni irregolari. La metodologia FSC ha evidenziato buone capacità di ricerca e velocità di esecuzione, completata da una descrizione chiara e dettagliata dei risultati e dalla possibilità di poter visualizzare graficamente i clusters finali, anche se con un livello minimo di dettaglio. Il limite principale della metodologia è la dimensione ridotta del cluster finale: l’eccessivo impegno computazionale richiesto dalla procedura induce a fissare il limite massimo al di sotto delle 30 aree, rendendola così utilizzabile solo nelle indagini in cui si ipotizza un’estensione limitata del fenomeno sul territorio. L’algoritmo genetico GA si rivela efficace nell’identificazione di clusters di qualsiasi forma ed estensione, seppur con una velocità di esecuzione inferiore rispetto alle procedure finora descritte. Senza un’adeguata selezione dei parametri di ricerca,la procedura può individuare clusters molto irregolari ed estesi, consigliando l’uso di penalizzazione non nulla in fase di ricerca. La scelta dei parametri di ricerca non è comunque agevole ed immediata e, spesso, è lasciata all’esperienza del ricercatore. Questo modo di procedere, in aggiunta alla mancanza di informazioni a priori sul fenomeno, aumenta il grado di soggettività introdotto nella selezione dei parametri influenzando i risultati finali. Infine, la metodologia GGS richiede un carico computazionale nettamente superiore rispetto a quello necessario per le altre metodologie utilizzate e l’introduzione di due parametri di controllo favorisce una maggiore arbitrarietà nella selezione dei valori di ricerca adeguati; inoltre, la recente implementazione della procedura e la mancanza di studi su dati reali inducono ad effettuare un numero maggiore di prove durante la fase di ricerca dei clusters.

Algoritmo di scelta della posizione degli scaricatori di tensione per la protezione delle reti di distribuzione elettrica dalle fulminazioni indirette

Le reti di distribuzione sono normalmente esposte ai fulmini, i quali producono sovratensioni sia da eventi diretti che indiretti. Le sovratensioni indotte, prodotte da fulminazioni indirette, sono le più frequenti nelle reti di media tensione, e sono una delle maggiori cause di guasto e di malfunzionamento dei dispositivi della rete. E’ per ciò essenziale realizzare un’accurata valutazione delle prestazioni dei mezzi di protezione delle reti di distribuzione dai fulmini al fine di migliorare la continuità e la qualità del servizio. L’obiettivo della tesi è sviluppare una procedura basata sull'algoritmo genetico in grado di determinare il numero di scaricatori ed i punti ottimali di installazione, tenendo conto della particolare configurazione della rete oggetto di studio, in modo da garantire la protezione della rete e in particolare dei componenti più vulnerabili. La procedura deve essere generica, ovvero deve risolvere il problema per una qualsiasi topologia di rete di media tensione.

L'algoritmo bionomico per il Traveling Salesman Problem

In questa tesi viene presentato un nuovo metaeuristico per la risoluzione del Traveling Salesman Problem (TSP) simmetrico. Tale metodo, detto algoritmo bionomico, è una variante dell'algoritmo genetico che usa un metodo innovativo di generazione del parents set. Nella tesi vengono proposti diversi metodi di crossover specifici per il TSP ma che possono essere facilmente estesi per altri problemi di ottimizzazione combinatoria. Tali metodi sono stati sperimentati su un insieme di problemi test, i risultati computazionali mostrano l'efficienza dei metodi proposti. In particolare uno dei metodi domina gli altri sia per la miglior qualità delle soluzioni prodotte che per il minor tempo di calcolo impiegato.

Solució paral·lelitzada d'interpolació kriging amb ajust automatitzat del variograma

El principal objectiu d'aquest treball és proporcionar una metodologia per a reduir el temps de càlcul del mètode d'interpolació kriging sense pèrdua de la qualitat del model resultat. La solució adoptada ha estat la paral·lelització de l'algorisme mitjançant MPI sobre llenguatge C. Prèviament ha estat necessari automatitzar l'ajust del variograma que millor s'adapta a la distribució espacial de la variable d'estudi. Els resultats experimentals demostren la validesa de la solució implementada, en reduir de forma significativa els temps d'execució final de tot el procés.

Ottimizzazione di strutture reticolari mediante algoritmi genetici

La tesi tratta dell'ottimizzazione di alcune tipologie di strutture reticolari. Per sviluppare i problemi analizzati ci si è avvalsi del software Grasshopper, conducendo poi l'ottimizzazione mediante un algoritmo genetico.

Sviluppo di metodologie di simulazione avanzate per la progettazione fluidodinamica di condotti di motori endotermici alternativi

L’attuale panorama motoristico, fortemente guidato dalle normative, prevede l’implementazione di diverse tecnologie che hanno lo scopo di migliorare l’efficienza del motore e ridurre le emissioni di inquinanti e per le quali risulta necessario una corretta progettazione dei condotti di aspirazione. Lo sviluppo ottimale dei condotti risulta un compromesso tra obiettivi contrastanti e in termini matematici si tratta di un’ottimizzazione multiobiettivo. Le simulazioni CFD e gli algoritmi genetici sono stati applicati con successo allo studio di questi problemi, ma la combinazione di questi elementi risulta notevolmente dispendiosa in termini di tempo, in quanto sarebbero necessarie un alto numero di simulazioni. Per ridurre i tempi di calcolo, un set di simulazioni CFD pu`o essere pi`u convenientemente utilizzato per istruire una rete neurale, che una volta opportunamente istruita pu`o essere usata per prevedere gli output delle simulazioni in funzione dei parametri di progetto durante l’ottimizzazione con l’algoritmo genetico, operando quella che viene chiamata una ottimizzazione virtuale. In questa tesi, viene mostrata una metodologia numerica per l’ottimizzazione multi-obiettivo dei condotti di aspirazione, basata su un modello CAD a geometria variabile, le simulazioni fluidodinamiche tridimensionali e una rete neurale combinata con un algoritmo genetico.

Analisi delle prestazioni di un sistema di accumulo termico

Analisi termofluidodinamica di un accumulatore di calore che utilizza materiali a cambiamento di fase (PCM). I campi di velocità, di temperatura e di titolo, in regime termico non stazionario, relativi al singolo canale, vengono calcolati con un programma basato sul metodo dei volumi finiti, scritto in ambiente di lavoro Matlab. Vengono proposte diverse ottimizzazioni delle performance di accumulo termico, basate su un algoritmo genetico. Le ottimizzazioni sono fatte sia con differenti tipi di parametri di valutazione, sia con differenti gradi del polinomio che descrive la parete del canale; per ogni ottimizzazione l’algoritmo genetico è stato, quindi, utilizzato per determinare i parametri geometrici del canale ottimali. A partire dai risultati ottenuti dalle ottimizzazioni, vengono poi analizzate le prestazioni di canali della stessa geometria, ai quali viene aggiunta un’intelaiatura metallica. Vengono, infine, mostrati i risultati delle simulazioni numeriche fatte.

Paralelización del algoritmo Rho de Pollard utilizando el protocolo de paso por mensajes MPI

El agoritmo Rho de Pollard es uno de los mejores conocidos para resolver el problema del logaritmo discreto. Se trata de una implementación de una paralelización utilizando MPI sobre un clúster. El lector encontrará en este proyecto el algoritmo de paralelización utilizado, así como, un conjunto de pruebas y resultados de la ejecución debidamente analizados.

Implementazione dell'algoritmo filtered back-projection (FBP) per architetture low-power di tipo systems-on-chip

Il presente lavoro di tesi, svolto presso i laboratori dell'X-ray Imaging Group del Dipartimento di Fisica e Astronomia dell'Università di Bologna e all'interno del progetto della V Commissione Scientifica Nazionale dell'INFN, COSA (Computing on SoC Architectures), ha come obiettivo il porting e l’analisi di un codice di ricostruzione tomografica su architetture GPU installate su System-On-Chip low-power, al fine di sviluppare un metodo portatile, economico e relativamente veloce. Dall'analisi computazionale sono state sviluppate tre diverse versioni del porting in CUDA C: nella prima ci si è limitati a trasporre la parte più onerosa del calcolo sulla scheda grafica, nella seconda si sfrutta la velocità del calcolo matriciale propria del coprocessore (facendo coincidere ogni pixel con una singola unità di calcolo parallelo), mentre la terza è un miglioramento della precedente versione ottimizzata ulteriormente. La terza versione è quella definitiva scelta perché è la più performante sia dal punto di vista del tempo di ricostruzione della singola slice sia a livello di risparmio energetico. Il porting sviluppato è stato confrontato con altre due parallelizzazioni in OpenMP ed MPI. Si è studiato quindi, sia su cluster HPC, sia su cluster SoC low-power (utilizzando in particolare la scheda quad-core Tegra K1), l’efficienza di ogni paradigma in funzione della velocità di calcolo e dell’energia impiegata. La soluzione da noi proposta prevede la combinazione del porting in OpenMP e di quello in CUDA C. Tre core CPU vengono riservati per l'esecuzione del codice in OpenMP, il quarto per gestire la GPU usando il porting in CUDA C. Questa doppia parallelizzazione ha la massima efficienza in funzione della potenza e dell’energia, mentre il cluster HPC ha la massima efficienza in velocità di calcolo. Il metodo proposto quindi permetterebbe di sfruttare quasi completamente le potenzialità della CPU e GPU con un costo molto contenuto. Una possibile ottimizzazione futura potrebbe prevedere la ricostruzione di due slice contemporaneamente sulla GPU, raddoppiando circa la velocità totale e sfruttando al meglio l’hardware. Questo studio ha dato risultati molto soddisfacenti, infatti, è possibile con solo tre schede TK1 eguagliare e forse a superare, in seguito, la potenza di calcolo di un server tradizionale con il vantaggio aggiunto di avere un sistema portatile, a basso consumo e costo. Questa ricerca si va a porre nell’ambito del computing come uno tra i primi studi effettivi su architetture SoC low-power e sul loro impiego in ambito scientifico, con risultati molto promettenti.

Sviluppo e analisi di un algoritmo parallelo di riconoscimento di oggetti in immagini

Implementazione sequenziale e parallela dell'algoritmo Evolution Constructed feature per il riconoscimento di oggetti in immagini. Analisi dei risultati ottenuti dall'algoritmo tramite la precision e la recall. Confronto dei tempi di esecuzione delle due versioni dell'algoritmo al fine di valutare gli effettivi guadagni ottenuti tramite la parallelizzazione.

Alocação de canais em sistemas de comunicação celular empregando algoritmo genético distribuído

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Planejamento de reativos em sistemas de energia elétrica através de um algoritmo de Branch-and-Bound não linear

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

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 e sviluppo di una versione distribuita di un algoritmo di subspace clustering

Il task del data mining si pone come obiettivo l'estrazione automatica di schemi significativi da grandi quantità di dati. Un esempio di schemi che possono essere cercati sono raggruppamenti significativi dei dati, si parla in questo caso di clustering. Gli algoritmi di clustering tradizionali mostrano grossi limiti in caso di dataset ad alta dimensionalità, composti cioè da oggetti descritti da un numero consistente di attributi. Di fronte a queste tipologie di dataset è necessario quindi adottare una diversa metodologia di analisi: il subspace clustering. Il subspace clustering consiste nella visita del reticolo di tutti i possibili sottospazi alla ricerca di gruppi signicativi (cluster). Una ricerca di questo tipo è un'operazione particolarmente costosa dal punto di vista computazionale. Diverse ottimizzazioni sono state proposte al fine di rendere gli algoritmi di subspace clustering più efficienti. In questo lavoro di tesi si è affrontato il problema da un punto di vista diverso: l'utilizzo della parallelizzazione al fine di ridurre il costo computazionale di un algoritmo di subspace clustering.