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.

Informationsstrukturen der protokollbasierten Medizin

Die protokollbasierte Medizin stellt einen interdisziplinären Brennpunkt der Informatik dar. Als besonderer Ausschnitt der medizinischen Teilgebiete erlaubt sie die relativ formale Spezifikation von Prozessen in den drei Bereichen der Prävention, Diagnose und Therapie.Letzterer wurde immer besonders fokussiert und gilt seit jeher im Rahmen klinischer Studien als Projektionsfläche für informationstechnologische Konzepte. Die Euphorie der frühen Jahre ernüchtert sich jedoch bei jeder Bilanz. Nur sehr wenige der unzählbaren Projekte haben ihre Routine in der alltäglichen Praxis gefunden. Die meisten Vorhaben sind an der Illusion der vollständigen Berechenbarkeit medizinischer Arbeitsabläufe gescheitert. Die traditionelle Sichtweise der klinischen Praxis beruht auf einer blockorientierten Vorstellung des Therapieausführungsprozesses. Sie entsteht durch seine Zerlegung in einzelne Therapiezweige, welche aus vordefinierten Blöcken zusammengesetzt sind. Diese können sequentiell oder parallel ausgeführt werden und sind selbst zusammengesetzt aus jeweils einer Menge von Elementen,welche die Aktivitäten der untersten Ebene darstellen. Das blockorientierte Aufbaumodell wird ergänzt durch ein regelorientiertes Ablaufmodell. Ein komplexes Regelwerk bestimmt Bedingungen für die zeitlichen und logischen Abhängigkeiten der Blöcke, deren Anordnung durch den Ausführungsprozeß gebildet wird. Die Modellierung der Therapieausführung steht zunächst vor der grundsätzlichen Frage, inwieweit die traditionelle Sichtweise für eine interne Repräsentation geeignet ist. Das übergeordnete Ziel besteht in der Integration der unterschiedlichen Ebenen der Therapiespezifikation. Dazu gehört nicht nur die strukturelle Komponente, sondern vorallem die Ablaufkomponente. Ein geeignetes Regelmodell ist erforderlich, welches den spezifischen Bedürfnissen der Therapieüberwachung gerecht wird. Die zentrale Aufgabe besteht darin, diese unterschiedlichen Ebenen zusammenzuführen. Eine sinnvolle Alternative zur traditionellen Sichtweise liefert das zustandsorientierte Modell des Therapieausführungsprozesses. Das zustandsorientierte Modell beruht auf der Sichtweise, daß der gesamte Therapieausführungsprozeß letztendlich eine lineare Folge von Zuständen beschreibt, wobei jeder Zustandsübergang durch ein Ereignis eingeleitet wird, an bestimmte Bedingungen geknüpft ist und bestimmte Aktionen auslösen kann. Die Parallelität des blockorientierten Modells tritt in den Hintergrund, denn die Menge der durchzuführenden Maßnahmen sind lediglich Eigenschaften der Zustände und keine strukturellen Elemente der Ablaufspezifikation. Zu jedem Zeitpunkt ist genau ein Zustand aktiv, und er repräsentiert eine von endlich vielen klinischen Situationen, mit all ihren spezifischen Aktivitäten und Ausführungsregeln. Die Vorteile des zustandsorientierten Modells liegen in der Integration. Die Grundstruktur verbindet die statische Darstellung der möglichen Phasenanordnungen mit der dynamischen Ausführung aktiver Regeln. Die ursprünglichen Inhalte des blockorientierten Modells werden als gewöhnliche Eigenschaften der Zustände reproduziert und stellen damit nur einen Spezialfall der zustandsbezogenen Sicht dar.Weitere Möglichkeiten für die Anreicherung der Zustände mit zusätzlichen Details sind denkbar wie sinnvoll. Die Grundstruktur bleibt bei jeder Erweiterung jedoch die gleiche. Es ergibt sich ein wiederverwendbares Grundgerüst,ein gemeinsamer Nenner für die Erfüllung der Überwachungsaufgabe.

Studio e sviluppo di un'applicazione mobile per iOS nell'ambito della BI: un task manager per SAP Business Planning and Consolidation

La tesi riguarda lo sviluppo di un'applicazione che estende la possibilità di effettuare i caricamenti dei package di SAP BPC ai dispositivi mobile, fino ad ora questo era possibile solo attraverso l'interfaccia di Microsoft Excel.

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.

Ricostruzione delle sorgenti corticali da segnali EEG in task di discriminazione visiva: Effetto di training multisensoriale

I neuroni in alcune regioni del nostro cervello mostrano una risposta a stimoli multisensoriali (ad es. audio-visivi) temporalmente e spazialmente coincidenti maggiore della risposta agli stessi stimoli presi singolarmente (integrazione multisensoriale). Questa abilità può essere sfruttata per compensare deficit unisensoriali, attraverso training multisensoriali che promuovano il rafforzamento sinaptico all’interno di circuiti comprendenti le regioni multisensoriali stimolate. Obiettivo della presente tesi è stato quello di studiare quali strutture e circuiti possono essere stimolate e rinforzate da un training multisensoriale audio-visivo. A tale scopo, sono stati analizzati segnali elettroencefalografici (EEG) registrati durante due diversi task di discriminazione visiva (discriminazione della direzione di movimento e discriminazione di orientazione di una griglia) eseguiti prima e dopo un training audio-visivo con stimoli temporalmente e spazialmente coincidenti, per i soggetti sperimentali, o spazialmente disparati, per i soggetti di controllo. Dai segnali EEG di ogni soggetto è stato ricavato il potenziale evento correlato (ERP) sullo scalpo, di cui si è analizzata la componente N100 (picco in 140÷180 ms post stimolo) verificandone variazioni pre/post training mediante test statistici. Inoltre, è stata ricostruita l’attivazione delle sorgenti corticali in 6239 voxel (suddivisi tra le 84 ROI coincidenti con le Aree di Brodmann) con l’ausilio del software sLORETA. Differenti attivazioni delle ROI pre/post training in 140÷180 ms sono state evidenziate mediante test statistici. I risultati suggeriscono che il training multisensoriale abbia rinforzato i collegamenti sinaptici tra il Collicolo Superiore e il Lobulo Parietale Inferiore (nell’area Area di Brodmann 7), una regione con funzioni visuo-motorie e di attenzione spaziale.

Impaired performance on the rapid visual information processing task (RVIP) could be an endophenotype of schizophrenia

The aim of the present study was to investigate whether healthy first-degree relatives of schizophrenia patients show reduced sensitivity performance, higher intra-individual variability (IIV) in reaction time (RT), and a steeper decline in sensitivity over time in a sustained attention task. Healthy first-degree relatives of schizophrenia patients (n=23) and healthy control subjects (n=46) without a family history of schizophrenia performed a demanding version of the Rapid Visual Information Processing task (RVIP). RTs, hits, false alarms, and the sensitivity index A' were assessed. The relatives were significantly less sensitive, tended to have higher IIV in RT, but sustained the impaired level of sensitivity over time. Impaired performance on the RVIP is a possible endophenotype for schizophrenia. Higher IIV in RT, apparently caused by impaired context representations, might result in fluctuations in control and lead to more frequent attentional lapses.

Determination of Language Dominance: Wada Test and fMRI Compared Using a Novel Sentence Task

This study aimed to develop a new linguistic based functional magnetic resonance imaging (fMRI)-sentence decision task that reliably detects hemispheric language dominance.