Valutazione delle prestazioni di processori a basso consumo energetico in applicazioni parallele

In questo lavoro di tesi sono state impiegate le librerie grafiche OpenGL ES 2 per eseguire calcoli paralleli sulla GPU del Raspberry Pi. Sono stati affrontati e discussi concetti riguanrdati il calcolo parallelo, stream processing, GPGPU e le metriche di valutazione di algoritmi paralleli. Sono inoltre descritte le potenzialita e le limitazioni derivanti dall'impiego di OpenGL per implementare algoritmi paralleli. In particolare si e fatto riferimento all'algoritmo Seam Carving per il restringimento di immagini, realizzando e valutando una implementazione parallela di questo sul Raspberry Pi.

Una libreria OpenGL per la selezione e editing di mesh poligonali

Nel mondo Open Source, la libreria grafica OpenGL è oggi ampiamente utilizzata in svariati settori come l'animazione 2D/3D, la modellazione CAD o nello sviluppo di videogiochi. A causa dei suoi innumerevoli usi e dell'astrazione che OpenGL permette di ottenere su diversi ambienti grafici, lo sviluppatore - che la utilizza - è vincolato a cercare librerie di supporto al fine di sfruttarne al meglio le potenzialità. Questa tesi si configura su questi presupposti, presentando una libreria di selezione e editing di mesh 3D basata su OpenGL. La libreria, chiamata libEditMesh, sfrutta il meccanismo geometrico del RayPicking permettendo all'utilizzatore di identificare col mouse punti, facce e lati di solidi in scena. La tesi si articola sostanzialmente in due parti: nella prima vengono proposte alcune soluzioni ad-hoc sviluppate su applicazioni già esistenti nel panorama openSource, e non; nella seconda vengono esposti gli algoritmi e funzioni implementate in libEditMesh.

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.

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.

Algoritmi esatti per il Job Shop Scheduling: approcci Mathematical Programming

In questa tesi ci occuperemo di fornire un modello MIP di base e di alcune sue varianti, realizzate allo scopo di comprenderne il comportamento ed eventualmente migliorarne l’efficienza. Le diverse varianti sono state costruite agendo in particolar modo sulla definizione di alcuni vincoli, oppure sui bound delle variabili, oppure ancora nell’obbligare il risolutore a focalizzarsi su determinate decisioni o specifiche variabili. Sono stati testati alcuni dei problemi tipici presenti in letteratura e i diversi risultati sono stati opportunamente valutati e confrontati. Tra i riferimenti per tale confronto sono stati considerati anche i risultati ottenibili tramite un modello Constraint Programming, che notoriamente produce risultati apprezzabili in ambito di schedulazione. Un ulteriore scopo della tesi è, infatti, comparare i due approcci Mathematical Programming e Constraint Programming, identificandone quindi i pregi e gli svantaggi e provandone la trasferibilità al modello raffrontato.

Implementazione di algoritmi di stima della distanza con segnali a bassa frequenza

L’obiettivo di questo lavoro di tesi è stato quello di definire degli algoritmi in grado di comprendere le prestazioni raggiungibili dalla tecnica NFER alternativa in termini di ranging e accuratezza e, di conseguenza, dedurre se il sistema sia utilizzabile o meno.