Ordonnancement temps réel multiprocesseur avec délais de préemption et de migration

Sujets de thèse 2013

Intitulé de la thèse
Ordonnancement temps réel multiprocesseur avec délais de préemption et de migration
Publication du sujet sur le site de l’ABG : OUI
Nature du financement : Financement institutionnel, Contrat Doctoral, Financement régional, Contrats université sur projets,)
Domaine de compétences principal (pour l’ABG) : Informatique, électronique
Domaine de compétences secondaire (pour l’ABG) : Mathématiques
Spécialité de doctorat : Informatique et Applications

Lieu de travail
LIAS/ENSMA
Laboratoire d’accueil : LIAS

Présentation de l’équipe de recherche
Le contrôle des systèmes aux fonctions critiques ou avec des garanties de service sont supportés par des ordinateurs. Le fonctionnement du système ne dépend pas uniquement de la correction des résultats des calculs mais aussi des dates auxquelles ils sont produits. Cette double exigence caractérise les systèmes temps réel. Le système informatique de commande doit être réactif vis-à-vis du procédé contrôlé ou du service à garantir. Dans de nombreuses implémentations, le logiciel de commande est décomposé en tâches s’exécutant en parallèle sur un ou plusieurs processeurs. Avant la mise en service de ce logiciel, les concepteurs doivent s’assurer que les contraintes temporelles des tâches seront respectées durant toute la vie du système. Afin de garantir les échéances temporelles des tâches, des algorithmes d’ordonnancement doivent être conçus et paramétrés en fonction des spécifications du système et de l’environnement contrôlé. Enfin, l’étape de validation du système analyse finement l’ordonnancement des tâches afin de prouver que les contraintes temporelles du système seront respectées.

Résumé de la thèse en français
Les systèmes informatiques temps réel utilisent de plus en plus des architectures multiprocesseurs afin de répondre aux besoins croissants en termes de calcul. Par nature chaque tâche informatique temps réel est récurrente et génère une infinité d’instances (d’exécutions) de la tâche. Les contraintes temporelles sont définies par des échéances strictes (deadlines) devant être respectées par chaque tâche. Les algorithmes d’ordonnancement se distinguent selon le degré de migration des tâches entre les processeurs (global, migration restreinte ou partitionné) et les schémas d’attribution des priorités aux tâches (fixes aux tâches, fixes aux instances de tâches, dynamiques). Ces algorithmes sont comparés à l’aide de différentes métriques comme le facteur d’utilisation maximum de la plateforme, le nombre de processeurs nécessaires afin d’ordonnancer un système, leurs vitesses, etc.

La majorité des résultats connus en ordonnancement en-ligne monoprocesseur et multiprocesseur suppose que les préemptions et les migrations sont effectuées à coût nul (sans délai). Or, les expérimentations menées sur plateformes réelles montrent que les préemptions et les migrations induisent des délais non négligeables liés à l’état des mémoires caches au moment de la préemption d’une tâche. De multiples approches ont été proposées dans la littérature afin de prendre en considération ces délais. Mais la majorité de ces études porte sur les systèmes monoprocesseurs. Les deux principales approches consistent à (i) prendre en compte le délai de préemption explicitement dans l’analyse d’ordonnançabilité et (ii) contrôler les points de préemption dans les programmes afin de minimiser les coûts associés tout en garantissant le respect des contraintes temporelles des tâches. Nous souhaitons étudier ce problème dans le contexte de l’ordonnancement multiprocesseur afin d’en étudier la difficulté et proposer des solutions pragmatiques intégrant si possible des facteurs pratiques d’applications temps réel. L’objectif est de trouver un compromis entre l’ordonnancement non-préemptif qui offre un déterminisme fort et des coûts de migration faible et l’ordonnancement en-ligne préemptif permettant un niveau d’utilisation des ressources de calcul plus élevé mais devant supporter les coûts des migrations et des préemptions.

Résumé de la thèse en anglais
Real-time systems are designed upon multicore processors in order to provide increasing computational power to computerized tasks. Tasks are recurrent and generate an infinite collection of jobs. Temporal constraints are defined by deadlines that must be met by jobs at run-time. Scheduling algorithms are classified according to migration and preemption degrees and the task priorities (task-fixed, job-fixed, and dynamic). These algorithms are compared through several metrics such as the maximum utilization bound of the platform, number of required processors, their speeds, etc.

Most of known results on uniprocessor and multiprocessor scheduling assume that migration and preemption are performed at no cost (i.e., without any delay). But, recent experiments upon real platforms shown that such an assumption is not realistic and that preemption and migration delays related to cache miss must be taken into account. Two main approaches have been defined to cope with this problem: (i) to extend to task model in order to explicitly take into account such delays and (ii) controlling preemption points in the code in order to minimize used data in caches. In both case, deadlines must be met at run-time. The thesis objective is to study this problem for multiprocessor platforms: computational complexity and pragmatic solutions to solve it. The objective is the find a compromise between non-preemptive scheduling and the level of required resources in order to defined feasible schedule.

Description complète du sujet de thèse
Les systèmes informatiques temps réel utilisent de plus en plus des architectures multiprocesseurs afin de répondre aux besoins croissants en termes de calcul. Par nature chaque tâche informatique temps réel est récurrente et génère une infinité d’instances (d’exécutions) de la tâche. Les contraintes temporelles sont définies par des échéances strictes (deadlines) devant être respectées par chaque tâche. Les algorithmes d’ordonnancement se distinguent selon le degré de migration des tâches entre les processeurs (global, migration restreinte ou partitionné) et les schémas d’attribution des priorités aux tâches (fixes aux tâches, fixes aux instances de tâches, dynamiques). Ces algorithmes sont comparés à l’aide de différentes métriques comme le facteur d’utilisation maximum de la plateforme, le nombre de processeurs nécessaires afin d’ordonnancer un système, leurs vitesses, etc.

La majorité des résultats connus en ordonnancement en-ligne monoprocesseur et multiprocesseur suppose que les préemptions et les migrations sont effectuées à coût nul (sans délai). Or, les expérimentations menées sur plateformes réelles montrent que les préemptions et les migrations induisent des délais non négligeables liés à l’état des mémoires caches au moment de la préemption d’une tâche. De multiples approches ont été proposées dans la littérature afin de prendre en considération ces délais. Mais la majorité de ces études porte sur les systèmes monoprocesseurs. Les deux principales approches consistent à (i) prendre en compte le délai de préemption explicitement dans l’analyse d’ordonnançabilité et (ii) contrôler les points de préemption dans les programmes afin de minimiser les coûts associés tout en garantissant le respect des contraintes temporelles des tâches. Nous souhaitons étudier ce problème dans le contexte de l’ordonnancement multiprocesseur afin d’en étudier la difficulté et proposer des solutions pragmatiques intégrant si possible des facteurs pratiques d’applications temps réel. L’objectif est de trouver un compromis entre l’ordonnancement non-préemptif qui offre un déterminisme fort et des coûts de migration faible et l’ordonnancement en-ligne préemptif permettant un niveau d’utilisation des ressources de calcul plus élevé mais devant supporter les coûts des migrations et des préemptions.

Objectifs scientifiques de la thèse
Analyse et propositions d’algorithmes d’ordonnancement multiprocesseurs.

Compétences à l’issue de la thèse
Maîtrise scientifique de l’ordonnancement des systèmes temps réel multiprocesseurs

Mots clés (séparés par des virgules)
ordonnancement temps réel, systèmes multiprocesseur, complexité des algorithmes, approximation polynomiale, optimisation combinatoire.

Expérience/profil souhaité(e)
Connaissance en:
– système temps réel (logiciel et matériel),
– algorithmiques avancées (complexité, optimisation combinatoire, approximation).

Modalité de dépôt des candidatures
Envoyer CV, avec relevé de notes M1 et M2, et lettre de motivation au directeur de thèse.

Date limite de candidature
30 avril 2013
Directeur de thèse
Pascal Richard, Professeur, Université de Poitiers
Adresse mail du directeur de thèse : pascal.richard@univ-poitiers.fr
Téléphone Directeur de thèse : 05.49.49.80.61
Cofinancement LABEX SigmaLIM demandé : NON
Thèse pour Action transverse : NON

Recherche

Menu principal

Haut de page