Learning for scheduling a portfolio of constraint solvers

Nel lavoro di tesi qui presentato si indaga l'applicazione di tecniche di apprendimento mirate ad una più efficiente esecuzione di un portfolio di risolutore di vincoli (constraint solver). Un constraint solver è un programma che dato in input un problema di vincoli, elabora una soluzione mediante l'utilizzo di svariate tecniche. I problemi di vincoli sono altamente presenti nella vita reale. Esempi come l'organizzazione dei viaggi dei treni oppure la programmazione degli equipaggi di una compagnia aerea, sono tutti problemi di vincoli. Un problema di vincoli è formalizzato da un problema di soddisfacimento di vincoli(CSP). Un CSP è descritto da un insieme di variabili che possono assumere valori appartenenti ad uno specico dominio ed un insieme di vincoli che mettono in relazione variabili e valori assumibili da esse. Una tecnica per ottimizzare la risoluzione di tali problemi è quella suggerita da un approccio a portfolio. Tale tecnica, usata anche in am- biti come quelli economici, prevede la combinazione di più solver i quali assieme possono generare risultati migliori di un approccio a singolo solver. In questo lavoro ci preoccupiamo di creare una nuova tecnica che combina un portfolio di constraint solver con tecniche di machine learning. Il machine learning è un campo di intelligenza articiale che si pone l'obiettivo di immettere nelle macchine una sorta di `intelligenza'. Un esempio applicativo potrebbe essere quello di valutare i casi passati di un problema ed usarli in futuro per fare scelte. Tale processo è riscontrato anche a livello cognitivo umano. Nello specico, vogliamo ragionare in termini di classicazione. Una classicazione corrisponde ad assegnare ad un insieme di caratteristiche in input, un valore discreto in output, come vero o falso se una mail è classicata come spam o meno. La fase di apprendimento sarà svolta utilizzando una parte di CPHydra, un portfolio di constraint solver sviluppato presso la University College of Cork (UCC). Di tale algoritmo a portfolio verranno utilizzate solamente le caratteristiche usate per descrivere determinati aspetti di un CSP rispetto ad un altro; queste caratteristiche vengono altresì dette features. Creeremo quindi una serie di classicatori basati sullo specifico comportamento dei solver. La combinazione di tali classicatori con l'approccio a portfolio sara nalizzata allo scopo di valutare che le feature di CPHydra siano buone e che i classicatori basati su tali feature siano affidabili. Per giusticare il primo risultato, eettueremo un confronto con uno dei migliori portfolio allo stato dell'arte, SATzilla. Una volta stabilita la bontà delle features utilizzate per le classicazioni, andremo a risolvere i problemi simulando uno scheduler. Tali simulazioni testeranno diverse regole costruite con classicatori precedentemente introdotti. Prima agiremo su uno scenario ad un processore e successivamente ci espanderemo ad uno scenario multi processore. In questi esperimenti andremo a vericare che, le prestazioni ottenute tramite l'applicazione delle regole create appositamente sui classicatori, abbiano risultati migliori rispetto ad un'esecuzione limitata all'utilizzo del migliore solver del portfolio. I lavoro di tesi è stato svolto in collaborazione con il centro di ricerca 4C presso University College Cork. Su questo lavoro è stato elaborato e sottomesso un articolo scientico alla International Joint Conference of Articial Intelligence (IJCAI) 2011. Al momento della consegna della tesi non siamo ancora stati informati dell'accettazione di tale articolo. Comunque, le risposte dei revisori hanno indicato che tale metodo presentato risulta interessante.

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.

Scheduling application-aware in piattaforme di stream processing distribuito per scenari smart city

In piattaforme di Stream Processing è spesso necessario eseguire elaborazioni differenziate degli stream di input. Questa tesi ha l'obiettivo di realizzare uno scheduler in grado di attribuire priorità di esecuzione differenti agli operatori deputati all'elaborazione degli stream.

Performance evaluation of improved output scheduling in 3lihon nodes

Le reti ottiche, grazie alla loro elevata capacità, hanno acquisito sempre maggiore importanza negli ultimi anni, sia per via del crescente volume di dati scambiati, legato soprattutto alla larga diffusione di Internet, sia per la necessità di comunicazioni in tempo reale. Dati i (relativamente) lunghi tempi di adattamento, questa tecnologia nativamente non è quella ottimale per il trasporto di un traffico a burst, tipico delle telecomunicazioni odierne. Le reti ibride cercano, quindi, di coniugare al meglio le potenzialità della commutazione ottica di circuito e della commutazione ottica a pacchetto. In questo lavoro, in particolare, ci si è concentrati su un'architettura di rete ibrida denominata 3LIHON (3-Level Integrated Hybrid Optical Network). Essa prevede tre distinti livelli di qualità di servizio (QoS) per soddisfare differenti necessità: - Guaranteed Service Type (GST): simile ad un servizio a commutazione di circuito, non ammette perdita di dati. - Statistically Multiplexed Real Time (SM/RT): simile ad un servizio a commutazione di pacchetto, garantisce ritardo nullo o molto basso all'interno della rete, permette un piccolo tasso di perdita di dati e ammette la contesa della banda. - Statistically Multiplexed Best Effort (SM/BE): simile ad un servizio a commutazione di pacchetto, non garantisce alcun ritardo tra i nodi ed ammette un basso tasso di perdita dei dati. In un nodo 3LIHON, il traffico SM/BE impossibile da servire, a causa ad es. dell'interruzione da parte di pacchetti aventi un livello di QoS più prioritario, viene irrimediabilmente perso. Questo implica anche lo spreco del tempo e delle risorse impiegati per trasmettere un pacchetto SM/BE fino alla sua interruzione. Nel presente lavoro si è cercato di limitare, per quanto possibile, questo comportamento sconveniente, adottando e comparando tre strategie, che hanno portato alla modifica del nodo 3LIHON standard ed alla nascita di tre sue varianti.

OpenMP task scheduling strategies to mitigate hardware variability in tightly-coupled shared memory clusters

In questa tesi sono stati apportati due importanti contributi nel campo degli acceleratori embedded many-core. Abbiamo implementato un runtime OpenMP ottimizzato per la gestione del tasking model per sistemi a processori strettamente accoppiati in cluster e poi interconnessi attraverso una network on chip. Ci siamo focalizzati sulla loro scalabilità e sul supporto di task di granularità fine, come è tipico nelle applicazioni embedded. Il secondo contributo di questa tesi è stata proporre una estensione del runtime di OpenMP che cerca di prevedere la manifestazione di errori dati da fenomeni di variability tramite una schedulazione efficiente del carico di lavoro.

Valutazione delle funzioni obiettivo nell'operating theatre scheduling

il ruolo della tesi è stato di valorizzare attraverso la valutazione di un peso l'urgenza e la necessità di cure dei pazienti processati da un modello di ottimizzazione. Essa si inserisce all'interno di un progetto di creazione di tale modello per la schedulazione di interventi in un reparto chirurgico di un generico ospedale.si è fatto uso del software ibm opl optimization suite.

Impact of irrigation in the Po valley (Italy) on meteorological parameters through numerical simulation

Recent studies found that soil-atmosphere coupling features, through soil moisture, have been crucial to simulate well heat waves amplitude, duration and intensity. Moreover, it was found that soil moisture depletion both in Winter and Spring anticipates strong heat waves during the Summer. Irrigation in geophysical studies can be intended as an anthropogenic forcing to the soil-moisture, besides changes in land proprieties. In this study, the irrigation was add to a LAM hydrostatic model (BOLAM) and coupled with the soil. The response of the model to irrigation perturbation is analyzed during a dry Summer season. To identify a dry Summer, with overall positive temperature anomalies, an extensive climatological characterization of 2015 was done. The method included a statistical validation on the reference period distribution used to calculate the anomalies. Drought conditions were observed during Summer 2015 and previous seasons, both on the analyzed region and the Alps. Moreover July was characterized as an extreme event for the referred distribution. The numerical simulation consisted on the summer season of 2015 and two run: a control run (CTR), with the soil coupling and a perturbed run (IPR). The perturbation consists on a mask of land use created from the Cropland FAO dataset, where an irrigation water flux of 3 mm/day was applied from 6 A.M. to 9 A.M. every day. The results show that differences between CTR and IPR has a strong daily cycle. The main modifications are on the air masses proprieties, not on to the dynamics. However, changes in the circulation at the boundaries of the Po Valley are observed, and a diagnostic spatial correlation of variable differences shows that soil moisture perturbation explains well the variation observed in the 2 meters height temperature and in the latent heat fluxes.On the other hand, does not explain the spatial shift up and downslope observed during different periods of the day. Given the results, irrigation process affects the atmospheric proprieties on a larger scale than the irrigation, therefore it is important in daily forecast, particularly during hot and dry periods.

Scheduling di applicazioni periodiche con durata variabile

In questa tesi presentiamo una strategia, e la relativa implementazione, per il problema dell’allocazione e schedulazione, su risorse unarie, di applicazioni multi-task periodiche, composte da attività che interagiscono fra loro e la cui durata è incerta. Lo scopo che ci si propone di raggiungere, è l’implementazione di una strategia di allocazione schedulazione che garantisca robustezza ed efficienza, in quei contesti in cui la conoscenza a priori è limitata e in cui le applicazioni si ripetono indefinitamente nel tempo. Per raggiungere questo scopo, sarà usato un approccio ibrido fra statico e dinamico. Staticamente è generata una soluzione del problema, sfruttando la programmazione a vincoli, in cui le durate delle attività sono arbitrariamente fissate. Questa soluzione, non rappresenta la soluzione del nostro problema, ma è utilizzata per generare un ordinamento delle attività, che compongono le applicazioni periodiche. Dinamicamente, sfruttando l’ordinamento ottenuto, è effettuata l’allocazione e la schedulazione effettiva delle applicazioni periodiche, considerando durate variabili per le attività. L’efficienza ottenuta applicando il nostro approccio è valutata effettuando test su una vasta gamma di istanze, sia industriali, sia sintetiche appositamente generate. I risultati sono confrontati con quelli ottenuti, per le stesse istanze, applicando un approccio puramente statico. Come si vedrà, in alcuni casi, è possibile anche quadruplicale la velocità di completamento delle applicazioni trattate.

Distributed allocation and scheduling of applications on HPC platforms

High Performance Computing e una tecnologia usata dai cluster computazionali per creare sistemi di elaborazione che sono in grado di fornire servizi molto piu potenti rispetto ai computer tradizionali. Di conseguenza la tecnologia HPC e diventata un fattore determinante nella competizione industriale e nella ricerca. I sistemi HPC continuano a crescere in termini di nodi e core. Le previsioni indicano che il numero dei nodi arrivera a un milione a breve. Questo tipo di architettura presenta anche dei costi molto alti in termini del consumo delle risorse, che diventano insostenibili per il mercato industriale. Un scheduler centralizzato non e in grado di gestire un numero di risorse cosi alto, mantenendo un tempo di risposta ragionevole. In questa tesi viene presentato un modello di scheduling distribuito che si basa sulla programmazione a vincoli e che modella il problema dello scheduling grazie a una serie di vincoli temporali e vincoli sulle risorse che devono essere soddisfatti. Lo scheduler cerca di ottimizzare le performance delle risorse e tende ad avvicinarsi a un profilo di consumo desiderato, considerato ottimale. Vengono analizzati vari modelli diversi e ognuno di questi viene testato in vari ambienti.