The resource demand on embedded devices is constantly growing. This is caused by the sheer explosion of software based functions in embedded systems, that are growing far faster than the resources of the single-core and multi-core embedded processors. As one of the limitation is the computing power of the processors we need to explore ways to use this resource more efficiently. We identified that during the run-time of the embedded devices the resource demand of the software functions is permanently changing dependent on the device situation. To enable an embedded device to take advantage of this dynamic resource demand, the allocation of the software functions to the processor must be handled by a scheduler that is able to evaluate the resource demand of the software functions in relation to the device situation. This marks a change in embedded devices from static defined software systems to dynamic software systems. Above that we can increase the efficiency even further by extending the approach from a single device to a distributed or networked system (many-core system). However, existing approaches to deal with dynamic resource allocation are focused on individual devices and leave the optimization potential of manycore systems untouched. Our concept will extend the existing Hierarchical Asynchronous Multi-Core Scheduler (HAMS) concept for individual devices to many-core systems. This extension introduces a dynamic situation aware scheduler for many-core systems which take the current workload of all devices and the system-situation into account. With our approach, the resource efficiency of an embedded many-core system can be increased. The following paper will explain the architecture and the expected results of our concept.

Catering to society’s demand for high performance computing, billions of transistors are now integrated on IC chips to deliver unprecedented performances. With increasing transistor density, the power consumption/density is growing exponentially. The increasing power consumption directly translates to the high chip temperature, which not only raises the packaging/cooling costs, but also degrades the performance/reliability and life span of the computing systems. Moreover, high chip temperature also greatly increases the leakage power consumption, which is becoming more and more significant with the continuous scaling of the transistor size. As the semiconductor industry continues to evolve, power and thermal challenges have become the most critical challenges in the design of new generations of computing systems. In this dissertation, we addressed the power/thermal issues from the system-level perspective. Specifically, we sought to employ real-time scheduling methods to optimize the power/thermal efficiency of the real-time computing systems, with leakage/ temperature dependency taken into consideration. In our research, we first explored the fundamental principles on how to employ dynamic voltage scaling (DVS) techniques to reduce the peak operating temperature when running a real-time application on a single core platform. We further proposed a novel real-time scheduling method, “M-Oscillations” to reduce the peak temperature when scheduling a hard real-time periodic task set. We also developed three checking methods to guarantee the feasibility of a periodic real-time schedule under peak temperature constraint. We further extended our research from single core platform to multi-core platform. We investigated the energy estimation problem on the multi-core platforms and developed a light weight and accurate method to calculate the energy consumption for a given voltage schedule on a multi-core platform. Finally, we concluded the dissertation with elaborated discussions of future extensions of our research.

Wurden früher Data-Warehouse-Systeme meist nur zur Datenanalyse für die Entscheidungsunterstützung des Managements eingesetzt, haben sie sich nunmehr zur zentralen Plattform für die integrierte Informationsversorgung eines Unternehmens entwickelt. Dies schließt vor allem auch die Einbindung des Data-Warehouses in operative Prozesse mit ein, für die zum einen sehr aktuelle Daten benötigt werden und zum anderen eine schnelle Anfrageverarbeitung gefordert wird. Daneben existieren jedoch weiterhin klassische Data-Warehouse-Anwendungen, welche hochqualitative und verfeinerte Daten benötigen. Die Anwender eines Data-Warehouse-Systems haben somit verschiedene und zum Teil konfligierende Anforderungen bezüglich der Datenaktualität, der Anfragelatenz und der Datenstabilität. In der vorliegenden Dissertation wurden Methoden und Techniken entwickelt, die diesen Konflikt adressieren und lösen. Die umfassende Zielstellung bestand darin, eine Echtzeit-Data-Warehouse-Architektur zu entwickeln, welche die Informationsversorgung in seiner ganzen Breite -- von historischen bis hin zu aktuellen Daten -- abdecken kann. Zunächst wurde ein Verfahren zur Ablaufplanung kontinuierlicher Aktualisierungsströme erarbeitet. Dieses berücksichtigt die widerstreitenden Anforderungen der Nutzer des Data-Warehouse-Systems und erzeugt bewiesenermaßen optimale Ablaufpläne. Im nächsten Schritt wurde die Ablaufplanung im Kontext mehrstufiger Datenproduktionsprozesse untersucht. Gegenstand der Analyse war insbesondere, unter welchen Bedingungen eine Ablaufplanung in Datenproduktionsprozessen gewinnbringend anwendbar ist. Zur Unterstützung der Analyse komplexer Data-Warehouse-Prozesse wurde eine Visualisierung der Entwicklung der Datenzustände, über die Produktionsprozesse hinweg, vorgeschlagen. Mit dieser steht ein Werkzeug zur Verfügung, mit dem explorativ Datenproduktionsprozesse auf ihr Optimierungspotenzial hin untersucht werden können. Das den operativen Datenänderungen unterworfene Echtzeit-Data-Warehouse-System führt in der Berichtsproduktion zu Inkonsistenzen. Daher wurde eine entkoppelte und für die Anwendung der Berichtsproduktion optimierte Datenschicht erarbeitet. Es wurde weiterhin ein Aggregationskonzept zur Beschleunigung der Anfrageverarbeitung entwickelt. Die Vollständigkeit der Berichtsanfragen wird durch spezielle Anfragetechniken garantiert. Es wurden zwei Data-Warehouse-Fallstudien großer Unternehmen vorgestellt sowie deren spezifische Herausforderungen analysiert. Die in dieser Dissertation entwickelten Konzepte wurden auf ihren Nutzen und ihre Anwendbarkeit in den Praxisszenarien hin überprüft.:1 Einleitung 1 2 Fallstudien 7 2.1 Fallstudie A: UBS AG . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 Unternehmen und Anwendungsdomäne . . . . . . . . . . . . 8 2.1.2 Systemarchitektur . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.3 Besonderheiten und Herausforderungen . . . . . . . . . . . . 13 2.2 Fallstudie B: GfK Retail and Technology . . . . . . . . . . . . . . . . 15 2.2.1 Unternehmen und Anwendungsdomäne . . . . . . . . . . . . 15 2.2.2 Systemarchitektur . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2.3 Besonderheiten und Herausforderungen . . . . . . . . . . . . 20 3 Evolution der Data-Warehouse- Systeme und Anforderungsanalyse 23 3.1 Der Data-Warehouse-Begriff und Referenzarchitektur . . . . . . . . . 23 3.1.1 Definition des klassischen Data-Warehouse-Begriffs . . . . . . 23 3.1.2 Referenzarchitektur . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Situative Datenanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2.1 Interaktion zwischen IT und Fachbereich . . . . . . . . . . . 31 3.2.2 Spreadmart-Lösungen . . . . . . . . . . . . . . . . . . . . . . 33 3.2.3 Analytische Mashups und dienstorientierte Architekturen . . 35 3.2.4 Werkzeuge und Methoden im Kostenvergleich . . . . . . . . . 40 3.3 Evolution der Data-Warehouse-Systeme . . . . . . . . . . . . . . . . 40 3.3.1 Nutzung von Data-Warehouse-Systemen . . . . . . . . . . . . 41 3.3.2 Entwicklungsprozess der Hardware- und DBMS-Architekturen 46 3.4 Architektur eines Echtzeit-Data-Warehouse . . . . . . . . . . . . . . 50 3.4.1 Der Echtzeit-Begriff im Data-Warehouse-Umfeld . . . . . . . 50 3.4.2 Architektur eines Echtzeit-Data-Warehouses . . . . . . . . . . 51 3.4.3 Systemmodell . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.5 Anforderungen an ein Echtzeit-Data-Warehouse . . . . . . . . . . . . 55 3.5.1 Maximierung der Datenaktualität . . . . . . . . . . . . . . . 55 3.5.2 Minimierung der Anfragelatenz . . . . . . . . . . . . . . . . . 56 3.5.3 Erhalt der Datenstabilität . . . . . . . . . . . . . . . . . . . . 57 4 Datenproduktionssteuerung in einstufigen Systemen 59 4.1 Qualitätskriterien und Systemmodell . . . . . . . . . . . . . . . . . . 59 4.1.1 Dienstqualitätskriterien . . . . . . . . . . . . . . . . . . . . . 60 4.1.2 Datenqualitätskriterien . . . . . . . . . . . . . . . . . . . . . 63 4.1.3 Multikriterielle Optimierung . . . . . . . . . . . . . . . . . . 64 4.1.4 Workload- und Systemmodell . . . . . . . . . . . . . . . . . . 66 4.2 Multikriterielle Ablaufplanung . . . . . . . . . . . . . . . . . . . . . 68 4.2.1 Pareto-effiziente Ablaufpläne . . . . . . . . . . . . . . . . . . 68 4.2.2 Abbildung auf das Rucksackproblem . . . . . . . . . . . . . . 71 4.2.3 Lösung mittels dynamischer Programmierung . . . . . . . . . 74 4.3 Dynamische Ablaufplanung zur Laufzeit . . . . . . . . . . . . . . . . 78 4.4 Selektionsbasierte Ausnahmebehandlung . . . . . . . . . . . . . . . . 81 4.5 Evaluierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.5.1 Experimentierumgebung . . . . . . . . . . . . . . . . . . . . . 84 4.5.2 Leistungsvergleich und Adaptivität . . . . . . . . . . . . . . . 86 4.5.3 Laufzeit- und Speicherkomplexität . . . . . . . . . . . . . . . 87 4.5.4 Änderungsstabilität . . . . . . . . . . . . . . . . . . . . . . . 89 4.6 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5 Bewertung von Ladestrategien in mehrstufigen Datenproduktionsprozessen 5.1 Ablaufplanung in mehrstufigen Datenproduktionsprozessen . . . . . 96 5.1.1 Ladestrategien und Problemstellung . . . . . . . . . . . . . . 97 5.1.2 Evaluierung und Diskussion . . . . . . . . . . . . . . . . . . . 98 5.2 Visualisierung der Datenqualität in mehrstufigen Datenproduktionsprozessen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5.2.1 Erfassung und Speicherung . . . . . . . . . . . . . . . . . . . 110 5.2.2 Visualisierung der Datenqualität . . . . . . . . . . . . . . . . 111 5.2.3 Prototypische Umsetzung . . . . . . . . . . . . . . . . . . . . 114 5.3 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 6 Konsistente Datenanalyse in operativen Datenproduktionsprozessen 119 6.1 Der Reporting-Layer als Basis einer stabilen Berichtsproduktion . . 120 6.1.1 Stabilität durch Entkopplung . . . . . . . . . . . . . . . . . . 120 6.1.2 Vorberechnung von Basisaggregaten . . . . . . . . . . . . . . 121 6.1.3 Vollständigkeitsbestimmung und Nullwertsemantik . . . . . . 125 6.1.4 Datenhaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 6.1.5 Prozess der Anfrageverarbeitung mit Vollständigkeitsbestimmung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 6.1.6 Verwandte Arbeiten und Techniken . . . . . . . . . . . . . . . 127 6.1.7 Evaluierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.2 Nullwertkomprimierung . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.2.1 Einleitendes Beispiel und Vorbetrachtungen . . . . . . . . . . 134 6.2.2 Nullwertkomprimierung . . . . . . . . . . . . . . . . . . . . . 136 6.2.3 Anfrageverarbeitung auf nullwertkomprimierten Daten . . . . 143 6.2.4 Verwandte Arbeiten und Techniken . . . . . . . . . . . . . . . 146 6.2.5 Evaluierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 6.3 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 7 Zusammenfassung und Ausblick 157 Literaturverzeichnis 161 Online-Quellenverzeichnis 169 Abbildungsverzeichnis 173

Une séparation existe de longue date entre les domaines de la compilation et de l'ordonnancement temps-réel. Si ces deux domaines ont le même objectif - la construction d'implantations correctes - la séparation se justifie historiquement par des différences significatives entre les modèles et les méthodes utilisés. Cependant, avec la complexification des applications et du materiel qui les exécute, les problèmes étudiés dans ces deux domaines se confondent désormais largement. Dans cette thèse, nous nous concentrons sur la génération automatique de code pour des systèmes de contrôle embarqué incluant des contraintes complexes (notamment temps-réel). A ces fins, nous défendons l'idée qu'il est profitable de fournir un effort commun de recherche entre ces deux communautés. En adaptant une technique de compilation au problème d'ordonnancement temps réel d'applications sur des architectures multiprocessurs, nous montrons à la fois les difficultés inhérentes à cet effort commun, mais aussi les possibles avancées qu'il porte. En effet, nous montrons que l'adaptation de techniques d'optimisation à de nouveaux objectifs, dans un contexte différent facilite le développement de systèmes de meilleure qualité. Nous proposons d'utiliser les formalismes et langages synchrones comme base formelle commune dans ce travail d'adaptation. Ceux-cis étendent naturellement les modèles classiques utilisés pour l'ordonnancement temps réel (graphes de tâches dépendentes) et la compilation (SSA et graphes de dépendence de données), et fournissent également des techniques efficaces pour la manipulation de structures de contrôle complexes. Nous avons implanté nos résultats dans le compilateur LoPhT. / There is a long standing separation between the fields of compiler construction and real-time scheduling. While both fields have the same objective - the construction of correct implementations – the separation was historically justified by significant differences in the models and methods that were used. Nevertheless, with the ongoing complexification of applications and of the hardware of the execution platforms, the objects and problems studied in these two fields are now largely overlapping. In this thesis, we focus on the automatic code generation for embedded control systems with complex constraints, including hard real-time requirements. To this purpose, we advocate the need for a reconciled research effort between the communities of compilation and real-time systems. By adapting a technique usually used in compilers (software pipelining) to the system-level problem of multiprocessor scheduling of hard real-time applications, we shed light on the difficulties of this unified research effort, but also show how it can lead to real advances. Indeed we explain how adapting techniques for the optimization of new objectives, in a different context, allows us to develop more easily systems of better quality than what was done until now. In this adaptation process, we propose to use synchronous formalisms and languages as a common formal ground. These can be naturally seen as extensions of classical models coming from both real-time scheduling (dependent task graphs) and compilation (single static assignment and data dependency graphs), but also provide powerful techniques for manipulating complex control structures. We implemented our results in the LoPhT compiler.

Typically, a real-time system consists of a controlling system (i.e., a computer) and a controlled system (i.e., the environment). Real-time systems are those systems where correctness depends on two aspects: i) the logical result of computation and, ii) the time in which results are produced. It is essential to guarantee meeting timing constraints for this kind of systems to operate correctly. Missing deadlines in many cases -- in so-called hard real-time systems -- is associated with economic loss or loss of human lives and must be avoided under all circumstances. On the other hand, there is a trend towards consolidating software functions onto fewer processors in different domains such as automotive systems and avionics with the aim of reducing costs and complexity. Hence, applications with different levels of criticality that used to run in isolation now start sharing processors. As a result, there is a need for techniques that allow designing such mixed-criticality (MC) systems -- i.e., real-time systems combining different levels of criticality -- and, at the same time, complying with certification requirements in the different domains. In this research, we study the problem of scheduling MC tasks under EDF (Earliest Deadline First) and propose new approaches to improve scheduling techniques. In particular, we consider that a mix of low-criticality (LO) and high-criticality (HI) tasks are scheduled on one processor. While LO tasks can be modeled by minimum inter-arrival time, deadline, and worst-case execution time (WCET), HI tasks are characterized by two WCET parameters: an optimistic and a conservative one. Basically, the system operates in two modes: LO and HI mode. In LO mode, HI tasks run for no longer than their optimistic execution budgets and are scheduled together with the LO tasks. The system switches to HI mode when one or more HI tasks run for more than their conservative execution budgets. In this case, LO tasks are immediately discarded so as to be able of accommodating the increase in HI execution demand. We propose an exact test for mixed-criticality EDF, which increases efficiency and reliability when compared with the existing approaches from the literature. On this basis, we further derive approximated tests with less complexity and, hence, a reduced running time that makes them more suitable for online checks.:Contents 1. Introduction 1 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2. Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3. Structure of this Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Concepts, Models and Assumptions 7 2.1. Real-Time Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1. Tasks Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2. Scheduling Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1. Feasibility versus Schedulability . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2. Schedulability Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3. Mixed-Criticality Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4. Basic Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5. The Earliest Deadline First Algorithm . . . . . . . . . . . . . . . . . . . . . . 13 2.5.1. EDF-VD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5.2. Mixed-Criticality EDF . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5.3. Demand Bound Function . . . . . . . . . . . . . . . . . . . . . . . . . 16 3. Related Work 17 3.1. Uniprocessor Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.1. Uniprocessor Scheduling Based on EDF . . . . . . . . . . . . . . . . . 18 3.2. Multiprocessor Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2.1. Multiprocessor Scheduling Based on EDF . . . . . . . . . . . . . . . . 20 4. Introducing Utilization Caps 23 4.1. Introducing Utilization Caps . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.1.1. Fixed utilization caps . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.1.2. Optimized utilization caps . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2. Findings of this Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5. Bounding Execution Demand under Mixed-Criticality EDF 29 5.1. Bounding Execution Demand . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2. Analytical Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2.1. The GREEDY Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2.2. The ECDF Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.3. Finding Valid xi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.4. Findings of this Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6. Approximating Execution Demand Bounds 41 6.1. Applying Approximation Techniques . . . . . . . . . . . . . . . . . . . . . . . 41 6.2. Devi’s Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.2.1. Per-task deadline scaling . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.2.2. Uniform deadline scaling . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.2.3. Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.3. Findings of this Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 7. Evaluation and Results 49 7.1. Mixed-Criticality EDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2. Obtaining Test Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2.1. The Case Di = Ti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2.2. The Case Di ≤ Ti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.3. Weighted schedulability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.4. Algorithms in this Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . 51 7.4.1. The EDF-VD and DEDF-VD Algorithms . . . . . . . . . . . . . . . . 51 7.4.2. The GREEDY algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 52 7.4.3. The ECDF algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 7.5. Evaluation of Utilization Caps . . . . . . . . . . . . . . . . . . . . . . . . . . 53 7.5.1. 10 tasks per task set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 7.5.2. 20 tasks per task set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 7.5.3. 50 tasks per task set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7.5.4. Comparison of runtime . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.6. Evaluation of Execution Demand Bounds . . . . . . . . . . . . . . . . . . . . 61 7.6.1. Comparison for sets of 10 tasks . . . . . . . . . . . . . . . . . . . . . . 61 7.6.2. Comparison for sets of 20 tasks . . . . . . . . . . . . . . . . . . . . . . 64 7.7. Evaluation of Approximation Techniques . . . . . . . . . . . . . . . . . . . . . 67 7.7.1. Schedulability curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.7.2. Weighted schedulability . . . . . . . . . . . . . . . . . . . . . . . . . . 69 7.7.3. Comparison of runtime . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7.8. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 8. Conclusion and Future Work 77 8.1. Outlook/Future Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Bibliography 83 A. Introduction 91 A.1. Multiple Levels of Criticality . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 A.1.1. Ordered mode switches . . . . . . . . . . . . . . . . . . . . . . . . . . 91 A.1.2. Unordered mode switches . . . . . . . . . . . . . . . . . . . . . . . . . 93 B. Evaluation and Results 95 B.1. Uniform Distribution for Task Periods . . . . . . . . . . . . . . . . . . . . . . 95

In this dissertation, we consider timeliness and energy optimization in battery-powered, mobile embedded real-time systems. We focus on real-time systems that operate in environments with dynamically uncertain properties, including context-dependent activity execution times and arbitrary activity arrival patterns. We consider an application model where activities are subject to time/utility function (or TUF) time constraints, mutual exclusion constraints on concurrent sharing of non-CPU resources, timeliness requirements including assurances on individual activity timeliness behavior, and system-level energy consumption requirements including a non-exhaustable energy budget. To account for uncertainties in activity properties in dynamic systems, we stochastically describe activity execution demands, and describe activity arrival behaviors using the unimodal arbitrary arrival model, which allows unbounded arrival frequencies. We consider the scheduling optimality criteria of: (1) probabilistically satisfying lower bounds on individual activities' maximal timeliness utilities, and (2) maximizing system-level energy efficiency, while ensuring that the system's energy consumption never exhausts the energy budget and resource mutual exclusion constraints are satisfied. For this multi-criteria scheduling problem, we present a DVS (dynamic voltage scaling)-based, real-time scheduling algorithm called the Energy-Bounded Utility Accrual Algorithm (or EBUA). Since the scheduling problem is NP-hard, EBUA heuristically (and dynamically) allocates CPU cycles to activities, computes activity schedules, and scales CPU voltage and frequency with a polynomial-time cost. If activities' cumulative execution demands exceed the available CPU time or may exhaust the system's energy budget, the algorithm defers and rejects jobs in a controlled fashion, minimizing system-level energy consumption and maximizing total accrued utility. We analytically establish several properties of EBUA. We prove that the algorithm never exhausts the specified energy budget. Further, we establish EBUA's timeliness optimality during under-loads, freedom from deadlocks, and correctness in mutually exclusive resource sharing. In particular, we prove that the algorithm's timeliness behavior subsumes the optimal timeliness behavior of deadline scheduling as a special case, and identify the conditions under which lower bounds on individual activity utilities are satisfied. In addition, we upper bound the time needed for mutually exclusively accessing shared resources under EBUA. We conduct experimental studies by simulating the algorithm on the DVS-enabled AMD k6 processor model, and by implementing it on QNX Neutrino 6.2.1 RTOS. Our experimental results validate our analytical results. Further, they confirm EBUA's superiority over other energy-efficient real-time scheduling algorithms on timeliness and energy consumption behaviors. / Ph. D.

In this dissertation, we consider scheduling distributed soft real-time tasks in unreliable (e.g., those with arbitrary node and network failures) and untrustworthy systems (e.g., those with Byzantine node behaviors). We present a distributed real-time scheduling algorithm called Gamma. Gamma considers a distributed (i.e., multi-node) task model where tasks are subject to Time/Utility Function (or TUF) end-to-end time constraints, and the scheduling optimality criterion of maximizing the total accrued utility. The algorithm makes three novel contributions. First, Gamma uses gossip for reliably propagating task scheduling parameters and for discovering task execution nodes. Second, Gamma achieves distributed real-time mutual exclusion in unreliable environments. Third, the algorithm guards against potential disruption of message propagation due to Byzantine attacks using a mechanism called Launcher-Attacker-Infective-Susceptible-Immunized-Removed-Consumer (or LAISIRC). By doing so, the algorithm schedules tasks with probabilistic termination-time satisfactions, despite system unreliability and untrustworthiness. We analytically establish several timeliness and non-timeliness properties of the algorithm including probabilistic end-to-end task termination time satisfactions, optimality of message overheads, mutual exclusion guarantees, and the mathematical model of the LAISIRC mechanism. We conducted simulation-based experimental studies and compared Gamma with its competitors. Our experimental studies reveal that Gamma's scheduling algorithm accrues greater utility and satisfies a greater number of deadlines than do competitor algorithms (e.g., HVDF) by as much as 47% and 45%, respectively. LAISIRC is more tolerant to Byzantine attacks than competitor protocols (e.g., Path Verification) by obtaining as much as 28% higher correctness ratio. Gamma's mutual exclusion algorithm accrues greater utility than do competitor algorithms (e.g., EDF-Sigma) by as much as 25%. Further, we implemented the basic Gamma algorithm in the Emulab/ChronOS 250-node testbed, and measured the algorithm's performance. Our implementation measurements validate our theoretical analysis and the algorithm's effectiveness and robustness. / Ph. D.

La conception de systèmes temps-réel embarqués se développe de plus en plus avec l’intégration croissante de fonctionnalités critiques pour les applications de surveillance, notamment dans le domaine biomédical, environnemental, domotique, etc. Le développement de ces systèmes doit relever divers défis en termes de minimisation de la consommation énergétique. Gérer de tels dispositifs embarqués, entièrement autonomes, nécessite cependant de résoudre différents problèmes liés à la quantité d’énergie disponible dans la batterie, à l’ordonnancement temps-réel des tâches qui doivent être exécutées avant leurs échéances, aux scénarios de reconfiguration, particulièrement dans le cas d’ajout de tâches, et à la contrainte de communication pour pouvoir assurer l’échange des messages entre les processeurs, de façon à assurer une autonomie durable jusqu’à la prochaine recharge et ce, tout en maintenant un niveau de qualité de service acceptable du système de traitement. Pour traiter cette problématique, nous proposons dans ces travaux une stratégie de placement et d’ordonnancement de tâches permettant d’exécuter des applications temps-réel sur une architecture contenant des cœurs hétérogènes. Dans cette thèse, nous avons choisi d’aborder cette problématique de façon incrémentale pour traiter progressivement les problèmes liés aux contraintes temps-réel, énergétique et de communications. Tout d’abord, nous nous intéressons particulièrement à l’ordonnancement des tâches sur une architecture mono-cœur. Nous proposons une stratégie d’ordonnancement basée sur le regroupement des tâches dans des packs pour pouvoir calculer facilement les nouveaux paramètres des tâches afin de réobtenir la faisabilité du système. Puis, nous l’avons étendu pour traiter le cas de l’ordonnancement sur une architecture multi-cœurs homogènes. Finalement, une extension de ce dernier sera réalisée afin d’arriver à l’objectif principal qui est l’ordonnancement des tâches pour les architectures hétérogènes. L’idée est de prendre progressivement en compte des contraintes d’exécution de plus en plus complexes. Nous formalisons tous les problèmes en utilisant la formulation ILP afin de pouvoir produire des résultats optimaux. L’idée est de pouvoir situer nos solutions proposées par rapport aux solutions optimales produites par un solveur et par rapport aux autres algorithmes de l’état de l’art. Par ailleurs, la validation par simulation des stratégies proposées montre qu’elles engendrent un gain appréciable vis-à-vis des critères considérés importants dans les systèmes embarqués, notamment le coût de la communication entre cœurs et le taux de rejet des tâches. / The design of embedded real-time systems is developing more and more with the increasing integration of critical functionalities for monitoring applications, particularly in the biomedical, environmental, home automation, etc. The developement of these systems faces various challenges particularly in terms of minimizing energy consumption. Managing such autonomous embedded devices, requires solving various problems related to the amount of energy available in the battery and the real-time scheduling of tasks that must be executed before their deadlines, to the reconfiguration scenarios, especially in the case of adding tasks, and to the communication constraint to be able to ensure messages exchange between cores, so as to ensure a lasting autonomy until the next recharge, while maintaining an acceptable level of quality of services for the processing system. To address this problem, we propose in this work a new strategy of placement and scheduling of tasks to execute real-time applications on an architecture containing heterogeneous cores. In this thesis, we have chosen to tackle this problem in an incremental manner in order to deal progressively with problems related to real-time, energy and communication constraints. First of all, we are particularly interested in the scheduling of tasks for single-core architecture. We propose a new scheduling strategy based on grouping tasks in packs to calculate the new task parameters in order to re-obtain the system feasibility. Then we have extended it to address the scheduling tasks on an homogeneous multi-core architecture. Finally, an extension of the latter will be achieved in order to realize the main objective, which is the scheduling of tasks for the heterogeneous architectures. The idea is to gradually take into account the constraints that are more and more complex. We formalize the proposed strategy as an optimization problem by using integer linear programming (ILP) and we compare the proposed solutions with the optimal results provided by the CPLEX solver. Inaddition, the validation by simulation of the proposed strategies shows that they generate a respectable gain compared with the criteria considered important in embedded systems, in particular the cost of communication between cores and the rate of new tasks rejection.

En raison de l'augmentation des coûts d'énergie et des préoccupations environnementales telles que les empreintes de carbone élevées, les systèmes de la production d'électricité centralisée se restructurent pour profiter des avantages de la production distribuée afin de répondre aux exigences énergétiques toujours croissantes. Les microgrids sont considérés comme une solution possible pour déployer une génération distribuée qui inclut des ressources énergétiques distribuées DERs (Distributed Energy Resources)(e.g, solaire, éolienne, batterie, etc). Dans cette thèse, nous traitons les défis de la gestion d'énergie dans un microgrid industriel où les charges énergétique sont constituées de processus industriels. Notre plan consiste à diviser la gestion de l'énergie du microgrid en deux parties: la production et la demande d’énergie.Du côté de la production d'énergie, les défis incluent la modélisation des générations de puissance et le lissage des fluctuations des DER. Pour modéliser les générations de puissance, nous proposons un modèle basé sur les concepts de service courbé de Network Calculus. En utilisant cet outil mathématique, nous déterminons une quantité minimale de puissance que les DERs peuvent générer; leur agrégation nous donnera une production d'énergie totale dans le microgrid. Après cela, s'il existe un déséquilibre entre la production et la demande d'énergie, nous proposons des stratégies différentes pour minimiser les coûts d'approvisionnement énergétique. Sur la base des données réelles de la consommation d'énergie d'un site industriel situé en France, des économies significatives peuvent être réalisées en adoptant ces stratégies. Dans cette thèse, nous étudions également comment atténuer les effets des fluctuations de puissance des DERs en conjonction avec des systèmes de stockage d'énergie. Pour cela, nous proposons un algorithme de lissage gaussien et nous le comparons avec des algorithmes de lissage trouvés dans l'état de l'art. Nous avons trouvé que l'algorithme proposé utilise de batterie de moins de taille à des fins de lissage par rapport à d'autres algorithmes. À cette fin, nous sommes également intéressés à étudier les effets de la gamme admissible des fluctuations sur les tailles de la batterie.Du côté de la demande, l'objectif est de réduire les coûts de l'énergie grâce aux approches de gestion de la demande DSM (Demand Side Management) telles que Demand Response (DR) et Energy Efficiency. Comme les processus industriels consomment énormément, une petite réduction de la consommation d'énergie en utilisant les approches DSM pourrait se traduire par des économies cruciales. Cette thèse se concentre sur l'approche DR qui peut profiter des prix variables de l'électricité dans le temps pour déplacer les demandes énergétiques des heures de pointe aux heures creuses. Pour atteindre cet objectif, nous comptons sur un modèle basé sur la théorie de file d'attente pour caractériser les comportements temporels (arrivée et départ des tâches) d'un système de fabrication. Après avoir défini les processus d'arrivée et de départ de tâches, une fonction d'utilisation efficace est utilisée pour prédire le comportement de la machine dans un domaine temporel et qui peut afficher son statut (allumé/éteint) à tout moment. En prenant le statut de chaque machine dans une ligne de production comme une entrée, nous proposons également un algorithme de planification DR qui adapte la consommation d'énergie d'une ligne de production aux deux contraintes de puissance disponibles et de taux de production. L'algorithme est codé à l'aide d’une machine d’état fini déterministe (Deterministic Finite State Machine) dans laquelle les transitions d'état se produisent en insérant une tâche à l'entrée du tapis roulant (on peut aussi avoir des transitions sans insertion de taches). Nous définissons des conditions pour l'existence d’un planificateur réalisable et aussi des conditions pour accepter positivement des demandes DRs / Due to increased energy costs and environmental concerns such as elevated carbon footprints, centralized power generation systems are restructuring themselves to reap benefits of distributed generation in order to meet the ever growing energy demands. Microgrids are considered as a possible solution to deploy distributed generation which includes Distributed Energy Resources (DERs) (e.g., solar, wind, battery, etc). In this thesis, we are interested in addressing energy management challenges in an industrial microgrid where energy loads consist of industrial processes. Our plan of attack is to divide the microgrid energy management into supply and demand sides.In supply side, the challenges include modeling of power generations and smoothing out fluctuations of the DERs. To model power generations, we propose amodel based on service curve concepts of Network Calculus (NC). Using this mathematical tool, we determine a minimum amount of power the DERs can generate and aggregating them will give us total power production in the microgrid. After that, if there is an imbalance between energy supply and demand, we put forward different strategies to minimize energy procurement costs. Based on real power consumption data of an industrial site located in France, significant cost savings can be made by adopting the strategies. In this thesis, we also study how to mitigate the effects of power fluctuations of DERs in conjunction with Energy Storage Systems (ESSs). For this purpose, we propose a Gaussian-based smoothing algorithm and compare it with state-of-the-art smoothing algorithms. We found out that the proposed algorithm uses less battery size for smoothing purposes when compared to other algorithms. To this end, we are also interested in investigating effects of allowable range of fluctuations on battery sizes.In demand side, the aim is to reduce energy costs through Demand Side Management (DSM) approaches such as Demand Response (DR) and Energy Efficiency (EE). As industrial processes are power-hungry consumers, a small power consumption reduction using the DSM approaches could translate into crucial savings. This thesis focuses on DR approach that can leverage time varying electricity prices to move energy demands from peak to off-peak hours. To attain this goal, we rely on a queuing theory-based model to characterize temporal behaviors (arrival and departure of jobs) of a manufacturing system. After defining job arrival and departure processes, an effective utilization function is used to predict workstation’s (or machine’s) behavior in temporal domain that can show its status (working or idle) at any time. Taking the status of every machine in a production line as an input, we also propose a DR scheduling algorithm that adapts power consumption of a production line to available power and production rate constraints. The algorithm is coded using Deterministic Finite State Machine (DFSM) in which state transitions happen by inserting a job (or not inserting) at conveyor input. We provide conditions for existence of feasible schedules and conditions to accept DR requests positively.To verify analytical computations on the queuing part, we have enhanced Objective Modular Network Testbed in C++ (OMNET++) discrete event simulator for fitting it to our needs. We modified various libraries in OMNET++ to add machine and conveyor modules. In this thesis, we also setup a testbed to experiment with a smart DR protocol called Open Automated Demand Response (OpenADR) that enables energy providers (e.g., utility grid) to ask consumers to reduce their power consumption for a given time. The objective is to explore how to implement our DR scheduling algorithm on top of OpenADR

Cette thèse se focalise sur le développement des algorithmes d’ordonnancement sous contrainte (m, k)-firm, ainsi que leurs applications pour la gestion de la qualité de service (QdS) dans les réseaux et systèmes temps réel distribués. L’objectif recherché est la garantie déterministe de la QdS tout en maintenant un fort taux d’utilisation des ressources. Les contributions sont (1) l’établissement d’une condition suffisante d’ordonnançabilité d'un ensemble de tâches sous l’algorithme « distance based priority »; (2) la définition de R-(m, k)-firm, un nouveau modèle qui relâche la contrainte (m, k)-firm et qui permet de modéliser de façon plus juste des exigences du temps réel souple; (3) le développement d’un algorithme efficace de dimensionnement de ressources sous contrainte (m, k)-firm relâchée; (4) la proposition de « Double Leaks Bucket » pour la gestion active de files d'attente permettant de maintenir une QdS en cas de surcharge des réseaux / This work focuses on the scheduling algorithms under (m,k)-firm constraint, as well as the applications for QoS (quality of service) management in the networks and distributed real-time system. The research aim is to achieve the deterministic guarantee of QoS with high resource utilization. The contributions in this thesis include (1) proposing a sufficient condition for determining the schedulability of a real-time task set under Distance Base Priority scheduling algorithm; (2) defining a novel real-time constraint which relaxes the (m,k)-firm constraint and provides a more suitable modelling of soft real-time; (3) developing an effective resource provisioning algorithm under this relaxed (m,k)-firm constraint; (4) proposing an active queue management mechanism, called Double Leaks Bucket, which can guarantee the QoS with dynamic dropping of the packets during the networks overload period