Search

This paper introduces and assesses novel strategies to schedule firm real-time jobs on an overloaded server. The jobs are released periodically and have the same relative deadline. Job execution times obey an arbitrary probability distribution and can take unbounded values (no WCET). We introduce three control parameters to decide when to start or interrupt a job. We couple this dynamic scheduling with several admission policies and investigate several optimization criteria, the most prominent being the Deadline Miss Ratio (DMR). Then we derive a Markov model and use its stationary distribution to determine the best value of each control parameter. Finally we conduct an extensive simulation campaign with 14 different probability distributions; the results nicely demonstrate how the new control parameters help improve system performance compared with traditional approaches. In particular, we show that (i) the best admission policy is to admit all jobs; (ii) the key control parameter is to upper bound the start time of each job; (iii) the best scheduling strategy decreases the DMR by up to 0.35 over traditional competitors., Ce travail présente et évalue de nouvelles stratégies d’ordonnancement pour exécuter des tâches périodiques en temps réel sur une plate-forme surchargée. Les tâches arrivent périodiquement et ont le même délai relatif pour leur exécution. Les temps d’exécution des tâches obéissent à une distribution de probabilité arbitraire et peuvent prendre des valeurs illimitées (pas de WCET). Certaines tâches peuvent être interrompues à leur admission dans le système ou bien en cours d’exécution. Nous introduisons trois paramètres de contrôle pour décider quand démarrer ou interrompre une tâche. Nous associons cet ordonnancement dynamique à plusieurs politiques d’admission et étudions plusieurs critères d’optimisation, le plus important étant le Deadline Miss Ratio (DMR). Ensuite, nous dérivons un modèle deMarkov et utilisons sa distribution stationnaire pour déterminer la meilleure valeur de chaque paramètre de contrôle. Enfin, nous conduisons de vastes simulations avec 14 distributions de probabilité différentes ; les résultats démontrentbien comment les nouveaux paramètres de contrôle contribuent à améliorer les performances du système par rapport aux approches traditionnelles. En particulier, nous montrons que (i) la meilleure politique d’admission est d’admettre toutes les tâches; (ii) le paramètre de contrôle clé est de limiter le temps de début de chaque tâche après son admission; (iii) la meilleure stratégie de planification diminue le DMR jusqu’à 0,35 par rapport aux concurrents traditionnels.

International audience; This paper discusses evaluation criteria and scheduling strategies for the analysis of overloaded real-time systems. This work builds upon techniques from queueing theory and proposes a new approach for real-time systems.

In this thesis, we design scheduling heuristics for independent tasks under budget and time constraints, in order to satisfy the requirement on performance or on energy consumption. The first three chapters of this thesis have performance as objective, while the fourth chapter focuses on energy-efficiency. The first three chapters have a common framework: We have a bag of tasks whose execution times follow some probability distributions. We can decide at any instant to interrupt the execution of a long running task and to launch a new one instead. The main questions are how many (or which) processors to enroll, and whether and when to interrupt tasks if they have been executing for a long time. In previous work, the problem has been dealt with on a homogeneous platform and with the same release time and deadline for all tasks. Our work extends the state-of-the-art in three directions: In the first work, we consider an heterogeneous platform. In the second work, we assume that the distribution of task execution times is unknown. In the third work, tasks are released periodically and have their own deadline. The fourth work considers a real-time framework. We have periodic tasks and an heterogeneous platform. We consider transient fault. Tasks are replicated to guarantee a pre-defined reliability threshold. We aim at find a heuristic which minimizes the expected energy consumption, while matching the deadline and reliability constraints of all tasks. This alls for a difficult trade-off between reliability and energy consumption.; De nos jours, l'informatique est un outil essentiel dans divers domaines de la recherche scientifique et dans notre vie quotidienne. Beaucoup des travaux informatiques, ou tâches, ont des échéances. D'autre part, le budget dont nous disposons est généralement limité. Afin de répondre aux exigences en termes de performances sous contraintes de budget et d'échéance, nous devons concevoir des heuristiques de planification pour améliorer les performances. En même temps, nous accordons de plus en plus d'attention à la protection de l'environnement. L'efficacité énergétique devient l'un des objectifs critiques dans une variété de problèmes. Ainsi, dans cette thèse, nous présentons des heuristiques d'ordonnancement pour des tâches indépendantes sous contraintes budgétaires et temporelles, qui cherchent à optimiser la performance ou la consommation d'énergie. Les trois premières parties de cette thèse ont la performance comme objectif, et nous traitons l'efficacité énergétique dans le quatrième. Les trois premiers travaux ont des conditions similaires : Nous avons un sac de tâches pour lesquelles les temps d'exécution suivent la même distribution. On peut décider à tout instant d'interrompre l'exécution d'une tâche et d'en lancer une nouvelle. Les principales questions sont de savoir combien (ou quels) processeurs utiliser, et si et quand interrompre les longues tâches. Dans un travail antérieur, les auteurs ont considéré une plateforme homogène et une échéance commune pour toutes les tâches. Nos travaux prolongent les travaux précédents dans trois directions : Premièrement, nous considérons une plateforme hétérogène. Deuxièmement, nous supposons que la distribution des temps d'exécution des tâches est inconnue. Troisièmement, les tâches arrivent périodiquement et ont leur propre échéance. Le quatrième travail se place dans un cadre temps-réel. Nous avons des tâches périodiques et une plateforme hétérogène. Nous considérons des pannes transitoires, et les tâches sont répliquées pour assurer un seuil de fiabilité prescrit. Nous n'avons plus de budget limité. En revanche, nous devons trouver une heuristique qui minimise la consommation d'énergie, tout en respectant les contraintes d'échéance et de fiabilité de toutes les tâches.

Low energy consumption and high reliability are widely identified as increasingly relevant issues in real-time systems on heterogeneous platforms. In this paper, we propose a multi-criteria optimization strategy to minimize the expected energy consumption while enforcing the reliability threshold and meeting all task deadlines. The tasks arrive periodically. Each instance of a task is replicated to ensure a prescribed reliability threshold. The platform is composed of processors with different (and possibly unrelated) characteristics, including speed profile, energy cost and failure rate. We provide several mapping and scheduling heuristics to solve this challenging optimization problem. Specifically, a novel approach is designed to control (i) how many replicas to use for each task, (ii) on which processor to map each replica and (iii) when to schedule each replica for eachtask instance on its assigned processor. Different mappings achieve different levels of reliability and consume different amounts of energy. Scheduling matters because once a task replica is successful, the other replicas of that task instance are canceled, which calls for minimizing the amount of temporal overlap between any replica pair. The experiments are conducted for a comprehensive set of execution scenarios, with a wide range of processor speed profiles and failure rates. The comparison results reveal that our strategies perform better than the random baseline, with a gain in energy consumption of more than 40% for nearly all cases. The absolute performance of the heuristics is assessed by a comparison with a lower-bound; the best heuristics achieve an excellent performance. It saves only 2% less energy than the lower-bound.; La faible consommation d’énergie et la haute fiabilité sont identifiées comme des problèmes de plus en plus pertinents dans les systèmes en temps réel sur des plateformes hétérogènes. Dans ce rapport, nous proposons une stratégie d’optimisation multi-critère pour minimiser l’espérance de laconsommation d’énergie tout en respectant le seuil de fiabilité et toutes les échéances des tâches. Les tâches arrivent périodiquement. Chaque instance d’une tâche est répliquée pour garantir un seuil de fiabilité prescrit. La plateforme est composée de processeurs avec des caractéristiques différentes (et éventuellement sans corrélation), y compris la vitesse, le coût énergétique et le taux de panne. Nous fournissons plusieurs heuristiques de placement et d’ordonnancement pour ce problème d’optimisation difficile. Plus précisément, une nouvelle solution est conçue pour contrôler (i) le nombre de répliques à utiliser pour chaque tâche, (ii) sur quel processeur doit-on placer chaque réplique et (iii) comment ordonnancer chaque réplique de chaque instance de tâche sur le processeur qui lui est affecté. Différents placements atteignent différents niveaux de fiabilité et consomment différentes quantités d’énergie. L’ordonnancement est important car une fois qu’une réplique de tâche réussit, les autres répliques de cette instance sont annulées, ce qui demande de minimiser le recouvrement en temps entre toute paire de répliques. Les expériences sont exécutées pour un grand ensemble de scénarios, avec une large gamme de vitesses et de taux d’échec pour les processeurs. Les résultats montrent que nos stratégies fonctionnent mieux que la référence de base aléatoire, avec un gain de 40 % en consommation d’énergie, dans presque tous les cas. La performance absolue de l’heuristique est évaluée en la comparant avec une borne inférieure. La meilleure heuristique atteint une excellente performance, avec une valeur moyenne supérieure de seulement 2% à la borne inférieure.

This work introduces scheduling strategies to maximize the expected numberof independent tasks that can be executed on a cloud platform within a given budgetand under a deadline constraint. Task execution times are not known before execution;instead, the only information available to the scheduler is that they obey some (unknown)probability distribution. The scheduler needs to acquire some information before decidingfor a cutting threshold: instead of allowing all tasks to run until completion, one maywant to interrupt long-running tasks at some point. In addition, the cutting thresholdmay be reevaluated as new information is acquired when the execution progresses further.This works presents several strategies to determine a good cutting threshold, and to decidewhen to re-evaluate it. In particular, we use the Kaplan-Meier estimator to account fortasks that are still running when making a decision. The efficiency of our strategies isassessed through an extensive set of simulations with various budget and deadline values,and ranging over 14 probability distributions.; Ce travail présente des stratégies d’ordonnancement permettant de maximiser le nombre attendu de tâches indépendantes pouvant être exécutées sur une plateforme de type cloud avec un budget donné et une contrainte de date limite. Le temps d’exécution des tâches est inconnu, on sait seulement qu’ils obéissent à une distribution de probabilité (inconnue). L’ordonnanceur peut décider à tout moment d’interrompre l’exécution d’une tâche (longue) en cours d’exécution et d’en lancer une nouvelle, mais le budget déjà utilisé pour la tâche interrompue est perdu. Le seuil d’interruption d’une tâche peut être recalculé au fur et à mesure que l’exécution progresse globalement. Ce travail présente plusieurs stratégies pour déterminer un bon seuil d’interruption, et pour décider quand le ré-évaluer. Nous utilisons l’estimateur de Kaplan-Meier pour prendre en compte les tâches en cours d’exécution au moment où la décision est prise. L’efficacité de nos stratégies est évaluée via un vaste ensemble de simulations, avec diverses valeurs de budget et de date limite, et portant sur 14 distributions de probabilité

Low energy consumption and high reliability are widely identified as increasingly relevant issues in real-time systems on heterogeneous platforms. In this paper, we propose a multi-criteria optimization strategy to minimize the expected energy consumption while enforcing the reliability threshold and meeting all task deadlines. The tasksare replicated to ensure a prescribed reliability threshold. The platforms are composed of processors with different (and possibly unrelated) characteristics, including speed profile, energy cost and failure rate. We provide several mapping and scheduling heuristics towards this challenging optimization problem. Specifically, a novel approach is designed to control (i) how many replicas to use for each task, (ii) on which processor to map each replica and(iii) when to schedule each replica on its assigned processor. Different mappings achieve different levels of reliability and consume different amounts of energy. Scheduling matters because once a task replica is successful, the other replicas of that task are cancelled, which calls for minimizing the amount of temporal overlap between any replica pair. The experiments are conducted for a comprehensive set of execution scenarios, with a wide range ofprocessor speed profiles and failure rates. The comparison results reveal that our strategies perform better than the random baseline, with a gain of 40% in energy consumption, for nearly all cases. The absolute performance of the heuristics is assessed by a comparison with a lower bound; the best heuristics achieve an excellent performance, with an average value only 4% higher than the lower bound.; La faible consommation d’énergie et la haute fiabilité sont identifiées comme des problèmes de plus en plus pertinents dans les systèmes en temps réel sur des plateformes hétérogènes. Dans cet article, nous proposons une stratégie d’optimisation multicritères pour minimiser la consommation d’énergie attendue tout en respectant le seuil de fiabilité et en respectant toutes les échéances des tâches. Les tâches sont répliquées pour garantir un seuil de fiabilité prescrit. Les plateformes sont composées de processeurs avec des caractéristiques différentes (et éventuellement sans corrélation), y compris la vitesse, le coût énergétique et le taux d’échec. Nous fournissons plusieurs heuristiques de mapping et de planification pour ce problème d’optimisation difficile. Plus précisément, une nouvelle architecture est conçue pour contrôler (i) le nombre de répliques à utiliser pour chaque tâche, (ii) sur quel processeur doit-on mapper chaque réplique et (iii) comment planifier chaque réplique sur le processeur qui lui est affecté. Différents mappings atteignent différents niveaux de fiabilité et consomment différentes quantités d’énergie. La planification est importante car une fois qu’une réplique de tâche réussit, les autres répliques de cette tâche sont annulées, ce qui nécessite de minimiser le chevauchement en temps entre toute paire de répliques. Les expériences sont exécutées pour un grand ensemble de scénarios, avec une large gamme de vitesse et de taux d’échec pour les processeurs. Les résultats révèlent que nos stratégies fonctionnent mieux que la référence aléatoire, avec un gain de 40 % en consommation d’énergie, dans presque tous les cas. La performance absolue de l’heuristique est évaluée en comparant avec une borne inférieure. La meilleure heuristique atteint une excellenteperformance, avec une valeur moyenne de seulement 4 % supérieure à la borne inférieure.

This work introduces scheduling strategies to maximize the expected number of independent tasks that can be executed on a cloud platform within a given budget and under a deadline constraint. The cloud platform is composed of several types of virtual machines (VMs), where each type has a unit execution cost that depends upon its characteristics. The amount of budget spent during the execution of a task on a given VM is the product of its execution length by the unit execution cost of that VM. The execution length of tasks follow an exponential, uniform or lognormal probability distribution whose mean and standard deviation both depend upon the VM type. Finally, there is a global available budget and a deadline constraint, and the goal is to successfully execute as many tasks as possible before the deadline is reached or the budget is exhausted (whichever comes first). On each VM, the scheduler can decide at any instant to interrupt the execution of a (long) running task and to launch a new one, but the budget already spent for the interrupted task is lost. The main questions are which VMs to enroll, and whether and when to interrupt tasks that have been executing for some time. We assess the complexityof the problem by showing its NP-completeness and providing a 2-approximation for the asymptotic case where budget and deadline both tends to infinity. We introduce several heuristics and compare their performance by running an extensive set of simulations.

Hofmeister series ranks the ability of salt ions in influencing a variety of properties and processes in aqueous solutions. In this review, we reexamine how these ions and some other small molecules affect water structure and thermodynamic properties, such as surface tension and protein backbone solvation. We illustrate the difficulties in interpreting the thermodynamic information based on structural and dynamic arguments. As an alternative, we show that the solvation properties of ions and proteins/small molecules can be used to explain the salt effects on the thermodynamic properties of the solutions. Our analysis shows that the often neglected cation-anion cooperativity plays a very important role in these effects. We also argue that the change of hydrogen donor/acceptor equilibrium by added cosolutes/cosolvents can be used to explain their effects on protein secondary structure denaturation/protection: those increase hydrogen donor concentrations such as urea and salts with strongly solvated cations/weakly hydrated anions tend to dissolve protein backbone acting as secondary structure denaturants, whereas those lack of hydrogen donors but rich in acceptors have the opposite effect.