Gestión de la carga dinámica de tareas de tiempo real con criterios de ahorro energético y su aplicación en el desarrollo de un middleware de control

Abstract

[EN] The development of embedded systems in industrial sectors such as railway, aerospace and automotive are based on Critical Real-Time Embedded Systems (CRTES). These systems face new challenges and demand related to increase of dependability, intelligence, connectivity, cost-size-volume reduction and energy efficiency. In this last topic is where this thesis expects to have a higher contribution. The global energy consumption can be combined with others criteria such as schedulability, communication delays and control application correctness, which contribute to determine the dynamic code movement and on-line load balancing in a system. The main goal of this thesis is the development of mechanisms for the management and optimization of energy consumption. These mechanisms are presented in the context of a distributed real-time control system and from the perspective of control kernel middleware. Let's consider a dynamic environment where an embedded and networked system operates with the support of task migration and processor frequency scaling. Assuming that the system knows where and when it must allocate tasks, we must perform feasibility analyses when each task arrives and departs on the affected embedded units. This guarantees that the temporal requirements of the system will be accomplished during the task allocation phase or delegation of tasks. Additionally, a new processor speed (frequency scaling) should be also computed to enable the system to adapt itself to the new computational workload and reduce energy consumption. And in this last is where the proposed algorithms in this work have their higher relevance. Although some authors have carried out these two phases (feasibility analysis and frequency scaling computation) separately, these analyses are strongly related and in some cases can be performed together. In this thesis, we present novel algorithm that perform feasibility analyses and compute new processor static frequencies based on dynamic voltage and frequency scaling techniques (DVFS). The frequency obtained as result of applying the algorithm proposed is the minimum processor frequency that minimizes CPU energy consumption while guaranteeing the fulfilment of real-time system constraints. The algorithm uses fixed priority scheduling schemes with deadlines less than, or equal to, the period of the tasks. Other propose of this algorithm is the use on-line during the task allocation and processor speed assignment phases. In this work, the computation of the minimum static processor frequency is accompanied with the proposed the additional approaches for the dynamic optimization of the energy consumption. Dynamic algorithms are based on the reclamation of additional slack resulting from the early completions of tasks. These are then used to further reduce the processor frequency and save more energy. These algorithms are applied at run-time. The computation of these additional dynamic processor frequencies uses as reference the previous calculation of the minimum static processor frequency. Through extensive simulations, we evaluate the performance of this algorithm against other existing feasibility tests that have been adapted to compute the minimum processor frequency. This minimum frequency is computed in terms of energy consumption, acceptability ratio, and real computing costs. In addition, predictability in the execution and behaviour of the algorithms in relation to the continuing arrival of tasks is analysed.

[ES] El desarrollo de sistemas de cómputo en sectores industriales tales como el ferroviario, aeroespacial y automóvil está basado en Sistemas Empotrados Críticos de Tiempo Real (CRTES). Estos sistemas se enfrentan a nuevas demandas y exigencias relacionadas con el incremento de la fiabilidad, mayor inteligencia, conectividad, reducción del volumen, mejoras del rendimiento y eficiencia en el consumo energético. Y es en ese último aspecto donde esta tesis doctoral espera hacer su principal aportación. El criterio de consumo energético, combinado con otros criterios tales como planificabilidad, retardos de comunicación y estabilidad en aplicaciones de control, contribuyen a la determinación del movimiento de código y al balance de cargas en sistemas distribuidos. El objetivo principal de esta tesis es el desarrollo de mecanismos de gestión y optimización del consumo energético. Estos mecanismos se presentan como posibles funcionalidades en el marco del diseño de middlewares basados en el concepto de núcleo de control. El desarrollo de esta tesis considera un entorno dinámico donde sistemas CRTES, basados en soportes middleware y conectados a una red de comunicaciones, permiten llevar a cabo migraciones de tareas y modificaciones de la frecuencia del procesador en tiempo de ejecución. Suponiendo que el sistema distribuido conoce dónde y cuándo asignar las tareas entre las unidades de cómputo, es necesario realizar un análisis de factibilidad de la planificación en cada llegada y partida de tareas sobre los sistemas empotrados afectados. De esta forma, se garantiza que los requisitos temporales del sistema serán cumplidos durante la fase de re-asignación o distribución de tareas. Esto también implica que una nueva velocidad de procesador (escalamiento de frecuencia) deberá ser calculada para permitir una optimización energética y la adaptación del sistema a las nuevas condiciones de carga computacional. Y es en este punto en el que los algoritmos propuestos en esta tesis tiene su importancia. Aunque algunos autores han llevado a cabo estas dos fases (análisis de planificabilidad y cálculo del escalado de frecuencia) separadamente, estos análisis están fuertemente relacionados y en algunos casos pueden ser ejecutados de forma conjunta. En este trabajo de tesis se propone un algoritmo nuevo para el análisis de factibilidad de planificación y el cálculo de frecuencias estáticas de procesador basado en técnicas de escalamiento de frecuencia y voltaje dinámico (también conocido como DVFS). La frecuencia obtenida por este algoritmo es la frecuencia mínima que garantiza que si se usa de forma invariable en el procesador, se ahorrará la mayor energía posible y además se cumplirán todos los plazos de ejecución de las tareas del sistema. Este algoritmo utiliza un esquema de planificación por prioridades fijas con plazos de ejecución menor y/o igual que el periodo de las tareas. Uno de los propósitos de este algoritmo es su uso durante la ejecución del sistema, que permita gestionar adaptaciones de carga computacional y energética del procesador. El algoritmo para el cálculo de frecuencias estáticas de procesador, es complementado en esta tesis con la propuesta de métodos nuevos de optimización dinámica, que ajustan el consumo energético basado en las condiciones de carga de computo reales en cada instante. Estos métodos propuestos se utilizan en tiempo de ejecución de las tareas del sistema y se basan en la asignación de frecuencias dinámicas al procesador. Estas nuevas frecuencias utilizan como referencia el cálculo previo de la frecuencia estática. Los cambios de frecuencia dinámicos se suceden como respuesta a instantes ociosos de procesador debidos principalmente a terminaciones anticipadas de tareas. Para la evaluación de esta tesis se proponen un conjunto de simulaciones y experimentos que permiten comparar y valorar las contribuciones de esta tesis con respecto a otros al

[CA] El desenvolupament de sistemes de còmput en sectors industrials com són el ferroviari, aeroespacial i automòbil està basat en Sistemes Embeguts Crítics de Temps Real (també coneguts per les sigles en anglès CRTES). Aquests sistemes s'enfronten a noves demandes i exigències relacionades amb l'increment de la fiabilitat, major intel·ligència, connectivitat, reducció del volum, millores de rendiment i eficiència en el consum energètic. És en aquest últim aspecte on aquesta tesi doctoral espera fer la seva principal aportació. El criteri de consum energètic, combinat amb altres criteris com ara planificabilitat, retards de comunicació i estabilitat en aplicacions de control, contribueixen a la determinació del moviment de codi i al balanç de càrregues en sistemes distribuïts. L'objectiu principal d'aquesta tesi és el desenvolupament de mecanismes de gestió i optimització del consum energètic. Aquests mecanismes es presenten com a possibles funcionalitats en el marc del disseny de middlewares basats en el concepte de nucli de control. El desenvolupament d'aquesta tesi considera un entorn dinàmic on sistemes CRTES basats en suport middleware i connectats a una xarxa de comunicacions, permeten dur a terme migracions de tasques i modificacions de la freqüència del processador en temps d'execució. Suposant que el sistema distribuït coneix on i quan assignar les tasques entre les unitats de còmput, cal fer un anàlisi de factibilitat de la planificació en cada arribada i sortida de tasques sobre els sistemes embeguts afectats. D'aquesta manera, es pot garantir que els requisits temporals del sistema seran complerts durant la fase de re-assignació o distribució de tasques. Això també implica que una velocitat de processador nova (escalament de freqüència) ha de ser calculada per permetre una optimització energètica i l'adaptació del sistema a les noves condicions de càrrega computacional. I és en aquest punt en el que els algoritmes proposats en aquesta tesi tenen la seva importància. Encara que alguns autors han dut a terme aquestes dues fases (l'anàlisi de planificabilitat i el càlcul de l'escalat de freqüència) separadament, aquestes anàlisis estan fortament relacionats i en alguns casos poden ser executats de forma conjunta. En aquest treball de tesi es proposa un algoritme nou per a l'anàlisi de factibilitat de planificació i el càlcul de freqüències estàtiques de processador basat en tècniques d'escalament de freqüència i voltatge dinàmic (també conegut com DVFS). La freqüència obtinguda per aquest algoritme és la freqüència mínima que garanteix que si es fa servir de forma invariable en el processador, s'estalviarà la major energia possible i a més a més es compliran tots els terminis d'execució de les tasques del sistema. Aquest algoritme utilitza un esquema de planificació per prioritats fixes amb terminis d'execució menors i/o iguals que el període de les tasques. Un dels propòsits d'aquest algoritme és el seu ús durant l'execució del sistema, que ha de permetre gestionar adaptacions de càrrega computacional i energètica del processador. L'algoritme de càlcul de freqüències estàtiques de processador, és complementat en aquesta tesi amb la proposta de mètodes nous d'optimització dinàmica, que ajusten el consum energètic basat en les condicions de càrregues de còmputs reals en cada instant. Aquests mètodes proposats s'utilitzen en temps d'execució de les tasques del sistema i es basen en l'assignació de freqüències dinàmiques al processador. Aquestes noves freqüències utilitzen com a referència el càlcul previ de la freqüència estàtica. Els canvis de freqüència dinàmics se succeeixen com a resposta a instants ociosos de processador deguts principalment a terminacions anticipades de tasques. Per a l'avaluació d'aquesta tesi es proposen un conjunt de simulacions i experiments que permeten comparar i valorar les contribucions