Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments

This work presents exact, hybrid algorithms for mixed resource Allocation and Scheduling problems; in general terms, those consist into assigning over time finite capacity resources to a set of precedence connected activities. The proposed methods have broad applicability, but are mainly motivated by applications in the field of Embedded System Design. In particular, high-performance embedded computing recently witnessed the shift from single CPU platforms with application-specific accelerators to programmable Multi Processor Systems-on-Chip (MPSoCs). Those allow higher flexibility, real time performance and low energy consumption, but the programmer must be able to effectively exploit the platform parallelism. This raises interest in the development of algorithmic techniques to be embedded in CAD tools; in particular, given a specific application and platform, the objective if to perform optimal allocation of hardware resources and to compute an execution schedule. On this regard, since embedded systems tend to run the same set of applications for their entire lifetime, off-line, exact optimization approaches are particularly appealing. Quite surprisingly, the use of exact algorithms has not been well investigated so far; this is in part motivated by the complexity of integrated allocation and scheduling, setting tough challenges for ``pure'' combinatorial methods. The use of hybrid CP/OR approaches presents the opportunity to exploit mutual advantages of different methods, while compensating for their weaknesses. In this work, we consider in first instance an Allocation and Scheduling problem over the Cell BE processor by Sony, IBM and Toshiba; we propose three different solution methods, leveraging decomposition, cut generation and heuristic guided search. Next, we face Allocation and Scheduling of so-called Conditional Task Graphs, explicitly accounting for branches with outcome not known at design time; we extend the CP scheduling framework to effectively deal with the introduced stochastic elements. Finally, we address Allocation and Scheduling with uncertain, bounded execution times, via conflict based tree search; we introduce a simple and flexible time model to take into account duration variability and provide an efficient conflict detection method. The proposed approaches achieve good results on practical size problem, thus demonstrating the use of exact approaches for system design is feasible. Furthermore, the developed techniques bring significant contributions to combinatorial optimization methods.

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.

Constraint based methods for allocation and scheduling of periodic applications

This work presents exact algorithms for the Resource Allocation and Cyclic Scheduling Problems (RA&CSPs). Cyclic Scheduling Problems arise in a number of application areas, such as in hoist scheduling, mass production, compiler design (implementing scheduling loops on parallel architectures), software pipelining, and in embedded system design. The RA&CS problem concerns time and resource assignment to a set of activities, to be indefinitely repeated, subject to precedence and resource capacity constraints. In this work we present two constraint programming frameworks facing two different types of cyclic problems. In first instance, we consider the disjunctive RA&CSP, where the allocation problem considers unary resources. Instances are described through the Synchronous Data-flow (SDF) Model of Computation. The key problem of finding a maximum-throughput allocation and scheduling of Synchronous Data-Flow graphs onto a multi-core architecture is NP-hard and has been traditionally solved by means of heuristic (incomplete) algorithms. We propose an exact (complete) algorithm for the computation of a maximum-throughput mapping of applications specified as SDFG onto multi-core architectures. Results show that the approach can handle realistic instances in terms of size and complexity. Next, we tackle the Cyclic Resource-Constrained Scheduling Problem (i.e. CRCSP). We propose a Constraint Programming approach based on modular arithmetic: in particular, we introduce a modular precedence constraint and a global cumulative constraint along with their filtering algorithms. Many traditional approaches to cyclic scheduling operate by fixing the period value and then solving a linear problem in a generate-and-test fashion. Conversely, our technique is based on a non-linear model and tackles the problem as a whole: the period value is inferred from the scheduling decisions. The proposed approaches have been tested on a number of non-trivial synthetic instances and on a set of realistic industrial instances achieving good results on practical size problem.

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.

Observable stages and scheduling for alveolar remodeling following antemortem tooth loss

Zahnverlust zu Lebzeiten („antemortem tooth loss“, AMTL) kann als Folge von Zahnerkrankungen, Traumata, Zahnextraktionen oder extremer kontinuierlicher Eruption sowie als Begleiterscheinung fortgeschrittener Stadien von Skorbut oder Lepra auftreten. Nach dem Zahnverlust setzt die Wundheilung als Sekundärheilung ein, während der sich die Alveole mit Blut füllt und sich ein Koagulum bildet. Anschließend erfolgt dessen Umwandlung in Knochengewebe und schließlich verstreicht die Alveole derart, dass sie makroskopisch nicht mehr erkannt werden kann. Der Zeitrahmen der knöchernen Konsolidierung des Kieferkammes ist im Detail wenig erforscht. Aufgrund des gehäuften Auftretens von AMTL in menschlichen Populationen, ist die Erarbeitung eines Zeitfensters, mit dessen Hilfe durch makroskopische Beobachtung des Knochens die Zeitspanne seit dem Zahnverlust („time since tooth loss“, TSL) ermittelt werden kann, insbesondere im archäologischen Kontext äußerst wertvoll. Solch ein Zeitschema mit Angaben über die Variabilität der zeitlichen Abläufe bei den Heilungsvorgängen kann nicht nur in der Osteologie, sondern auch in der Forensik, der allgemeinen Zahnheilkunde und der Implantologie nutzbringend angewandt werden. rnrnNach dem Verlust eines Zahnes wird das Zahnfach in der Regel durch ein Koagulum aufgefüllt. Das sich bildende Gewebe wird rasch in noch unreifen Knochen umgewandelt, welcher den Kieferknochen und auch die angrenzenden Zähne stabilisiert. Nach seiner Ausreifung passt sich das Gewebe schließlich dem umgebenden Knochen an. Das Erscheinungsbild des Zahnfaches während dieses Vorgangs durchläuft verschiedene Stadien, welche in der vorliegenden Studie anhand von klinischen Röntgenaufnahmen rezenter Patienten sowie durch Untersuchungen an archäologischen Skelettserien identifiziert wurden. Die Heilungsvorgänge im Zahnfach können in eine prä-ossale Phase (innerhalb einer Woche nach Zahnverlust), eine Verknöcherungsphase (etwa 14 Wochen nach Zahnverlust) und eine ossifizierte bzw. komplett verheilte Phase (mindestens 29 Wochen nach Zahnverlust) eingeteilt werden. Etliche Faktoren – wie etwa die Resorption des Interdentalseptums, der Zustand des Alveolarknochens oder das Individualgeschlecht – können den normalen Heilungsprozess signifikant beschleunigen oder hemmen und so Unterschiede von bis zu 19 Wochen verursachen. Weitere Variablen wirkten sich nicht signifikant auf den zeitlichen Rahmen des Heilungsprozesse aus. Relevante Abhängigkeiten zwischen verschiedenen Variabeln wurden ungeachtet der Alveolenauffüllung ebenfalls getestet. Gruppen von unabhängigen Variabeln wurden im Hinblick auf Auffüllungsgrad und TSL in multivariablen Modellen untersucht. Mit Hilfe dieser Ergebnisse ist eine grobe Einschätzung der Zeitspanne nach einem Zahnverlust in Wochen möglich, wobei die Einbeziehung weiterer Parameter eine höhere Präzision ermöglicht. rnrnObwohl verschiedene dentale Pathologien in dieser Studie berücksichtigt wurden, sollten zukünftige Untersuchungen genauer auf deren potenzielle Einflussnahme auf den alveolaren Heilungsprozess eingehen. Der kausale Zusammenhang einiger Variablen (wie z. B. Anwesenheit von Nachbarzähnen oder zahnmedizinische Behandlungen), welche die Geschwindigkeit der Heilungsrate beeinflussen, wäre von Bedeutung für zukünftige Untersuchungen des oralen Knochengewebes. Klinische Vergleichsstudien an forensischen Serien mit bekannter TSL oder an einer sich am Anfang des Heilungsprozesses befindlichen klinischen Serie könnten eine Bekräftigung dieser Ergebnisse liefern.

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.

Optimized scheduling in real-time environments with column generation

Im Bereich sicherheitsrelevanter eingebetteter Systeme stellt sich der Designprozess von Anwendungen als sehr komplex dar. Entsprechend einer gegebenen Hardwarearchitektur lassen sich Steuergeräte aufrüsten, um alle bestehenden Prozesse und Signale pünktlich auszuführen. Die zeitlichen Anforderungen sind strikt und müssen in jeder periodischen Wiederkehr der Prozesse erfüllt sein, da die Sicherstellung der parallelen Ausführung von größter Bedeutung ist. Existierende Ansätze können schnell Designalternativen berechnen, aber sie gewährleisten nicht, dass die Kosten für die nötigen Hardwareänderungen minimal sind. Wir stellen einen Ansatz vor, der kostenminimale Lösungen für das Problem berechnet, die alle zeitlichen Bedingungen erfüllen. Unser Algorithmus verwendet Lineare Programmierung mit Spaltengenerierung, eingebettet in eine Baumstruktur, um untere und obere Schranken während des Optimierungsprozesses bereitzustellen. Die komplexen Randbedingungen zur Gewährleistung der periodischen Ausführung verlagern sich durch eine Zerlegung des Hauptproblems in unabhängige Unterprobleme, die als ganzzahlige lineare Programme formuliert sind. Sowohl die Analysen zur Prozessausführung als auch die Methoden zur Signalübertragung werden untersucht und linearisierte Darstellungen angegeben. Des Weiteren präsentieren wir eine neue Formulierung für die Ausführung mit fixierten Prioritäten, die zusätzlich Prozessantwortzeiten im schlimmsten anzunehmenden Fall berechnet, welche für Szenarien nötig sind, in denen zeitliche Bedingungen an Teilmengen von Prozessen und Signalen gegeben sind. Wir weisen die Anwendbarkeit unserer Methoden durch die Analyse von Instanzen nach, welche Prozessstrukturen aus realen Anwendungen enthalten. Unsere Ergebnisse zeigen, dass untere Schranken schnell berechnet werden können, um die Optimalität von heuristischen Lösungen zu beweisen. Wenn wir optimale Lösungen mit Antwortzeiten liefern, stellt sich unsere neue Formulierung in der Laufzeitanalyse vorteilhaft gegenüber anderen Ansätzen dar. Die besten Resultate werden mit einem hybriden Ansatz erzielt, der heuristische Startlösungen, eine Vorverarbeitung und eine heuristische mit einer kurzen nachfolgenden exakten Berechnungsphase verbindet.

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.