Towards energy-effcient real-time computing in embedded systems

Modern embedded real-time systems are increasingly interconnected with a multitude of sensory devices, other embedded systems, and the cloud. The adoption of high-end embedded single core processors and multiprocessors emanates from complex application processing requirements. Timeliness, safety, and deterministic systems are long-standing design and operational requirements of embedded systems. Recently, mobility, energy-efficiency, and heat dissipation are equally crucial design requirements in applications including autonomous mobile robots, wearable devices, and sensor networks. High-end embedded processors employ energy-reduction techniques like Dynamic Voltage and Frequency Scaling (DVFS) and Dynamic Power Management (DPM). An effective energy-management strategy simultaneously exploits hardware- and software-level energy-reduction techniques.Initially, this thesis addresses the issue of energy-reduction on DVFS-capable single core systems with peripheral devices. We consider a system-wide minimization problem where we concurrently consider DVFS and DPM. Given that the frequency to task assignment is an NP-hard problem, we appropriate and adapt two metaheuristics in our approach to frequency assignment; namely the differential evolution and genetic algorithms. We analyze the performance of the metaheuristics given various initial conditions and show in our simulations that our approach yields better results than two well-known heuristics.Further, even though discrete-time simulators are sufficient for analyzing real-time schedule feasibility, they fall short when evaluating energy-efficient scheduling. This is due to incorrect processor modeling (i.e. due to IP rights, complex processor designs) and the inability to capture realistic task behavior. The literature often presents case studies on real hardware to corroborate simulations. However, these approaches are often ambiguous. We propose a methodology that facilitates evaluating real-time systems on real hardware using available embedded benchmarks as system tasks at various system load points. Similar to software simulations, our methodology tackles the issue of examining the system at different utilization points. We build on previous work that estimates task WCET, generates task periods, and assigns task utilizations. The three parameters are interlocked, which limits the flexibility of changing one without affecting the others. We propose a set of efficient algorithms that pair tasks with bounded or discrete periods to meet the total system utilization with minimal relative errors.Finally, we address the issue of energy-efficient scheduling on clustered heterogeneous platforms. We focus on energy-efficient partitioning where task allocation to heterogeneous clusters directly impacts the total system energy. In this thesis, we couple the problem of energy-efficient partitioning on single-ISA heterogeneous platforms with task-aware scheduling. Tasks differ in their instruction mix, cache behavior, memory and I/O access, execution path, and active processing and SoC circuitry. This affects their power demand. We make further use of underlying frequency scaling hardware and sleep states to minimize the system energy. We propose two variants of our Task and Cluster Heterogeneity Aware Partitioning (TCHAP) algorithm targeting ARM big.LITTLE platforms. Based on our methodology for simulation on real hardware, we show that our algorithms achieve between 13% to 23% energy-reduction on average compared to a state-of-the-art schemes.Les systèmes temps-réel embarqués modernes sont de plus en plus interconnectés avec une multitude d'appareils sensoriels, d'autres systèmes embarqués et du "cloud". L'adoption de processeurs monocœurs et multicœurs haut de gamme dans les applications embarquées émane des exigences de traitement d'applications complexes. La pérennité, la sécurité et les systèmes déterministes sont des obligations de conception et de fonctionnement de longue date des systèmes embarqués. Récemment, la mobilité, l'efficacité énergétique et la dissipation de chaleur sont des exigences de conception tout aussi cruciales dans les applications comprenant les robots mobiles autonomes, les appareils portables et les réseaux sensoriels. Les processeurs embarqués haut de gamme utilisent des techniques de réduction d'énergie telles que le voltage dynamique, la mise à l'échelle de la fréquence (DVFS) et la gestion dynamique de la puissance (DPM). Une stratégie efficace de gestion de l'énergie exploite simultanément les techniques de réduction de l'énergie au niveau matériel et logiciel.Initialement, cette thèse aborde le problème de la réduction de la consommation d'énergie sur les systèmes monocœurs avec matériel DVFS et périphériques. Nous considérons un problème de minimisation à l'échelle du système où nous examinerons simultanément DVFS et DPM. Étant donné que l'affectation de fréquence à la tâche est un problème NP-difficile, nous avons adaptés deux métaheuristiques à notre approche d'affectation de fréquence: l'évolution différentielle et l'algorithme génétique. Nous analyserons les performances des métaheuristiques en fonction de diverses conditions initiales. Nous montrerons dans nos simulations que notre approche donne de meilleurs résultats que deux heuristiques bien connues.En outre, bien que les simulateurs à temps-discret sont suffisants pour analyser la faisabilité des emplois du temps en temps réel, ils sont insuffisants pour évaluer des emplois du temps qui économisent l'énergie. Cela est dû à une modélisation incorrecte de processeurs (en raison des droits de propriétés intellectuelles, conceptions de processeurs complexes) et à l'incapacité de capturer un comportement réaliste des tâches. La littérature présente souvent des études de cas de "real-hardware" pour corroborer des simulations. Cependant, ces approches sont souvent ambiguës. Nous proposons une méthodologie qui facilite le portage de simulations sur la "real-hardware" a l'aide des "benchmarks" embarqués en tant que tâches système.Comme pour les simulations logicielles, notre méthodologie aborde la question de l'examen du système à différents points d'utilisation.Nous nous appuyons sur des travaux antérieurs qui évaluent la WCET des tâches, génèrent des périodes des tâches et attribuent des utilisations des tâches. Les trois paramètres sont interconnectés, ce qui limite la possibilité de modifier l'un sans affecter les autres. Nous proposons un ensemble d'algorithmes efficaces qui associent des tâches à des périodes délimitées pour répondre à l'utilisation totale du système avec un minimum d'erreurs relatives.Enfin, nous abordons la question de l'ordonnancement optimal énergétique sur des plateformes hétérogènes groupées. Nous nous concentrons sur la répartition énergétique efficace des tâches à des groupes hétérogènes ayant un impact direct sur l'énergie totale du système. Dans cette thèse, nous associerons le problème de répartition énergétique efficace sur des plateformes hétérogènes mono-ISA à un ordonnancement conscient de la tâche. Nous utilisons davantage les fréquences de "l'hardware" et les états de veille pour minimiser l'énergie du système. Nous proposons deux variantes de notre algorithme de répartition conscient de l'hétérogénéité de tâches et de cluster ciblant les plateformes ARM big.LITTLE. Nous montrons que nos algorithmes permettent de réduire de 13% à 23% la consommation moyenne d'énergie par rapport à des systèmes à la pointe de la technologie