Ordonnancement temps réel de plates-formes hétérogènes multiprocesseurs

Contexte

De nombreuses applications soumises à des contraintes temporelles nécessitent une importante puissance de calcul. Depuis près de 20 ans, l’unique moyen d’augmenter les capacités de traitement est d’utiliser plusieurs cœurs. Les problèmes d’ordonnancement multiprocesseurs sont bien plus compliqués que leurs équivalents en monopresseur. Le cas où les cœurs sont identiques a été largement étudié et plusieurs ordonnanceurs optimaux sont connus [4].

Cependant, en pratique, les systèmes embarqués multiprocesseurs sur puce (Multiprocessor Systems on Chips - MPSoCs) dans les systèmes temps réel sont dotés d’un nombre croissant d’unités de calcul spécialisées (CPUs, GPUs, NPUs, etc.). Cette hétérogénéité permet une meilleure utilisation des ressources (unités de traitement, consommation électrique, etc.), mais ces systèmes restent plus difficiles à rendre prédictibles. Les systèmes temps réel critiques doivent être prouvés fonctionnellement et temporellement corrects. La validation des contraintes temporelles dans de tels systèmes hétérogènes reste encore limitée.

Les caractéristiques temporelles de ces applications nécessitent un traitement spécifique de la part du système d’exploitation via son ordonnanceur de tâches. L’algorithme d’ordonnancement doit permettre une utilisation efficace des ressources (e.g., processeurs multi-cœurs, mémoire) tout en assurant que les contraintes temporelles seront respectées durant l’exécution.

L’objectif de la thèse est d’étudier l’ordonnancement de tâches temps réel à exécuter sur une plate-forme composée de plusieurs processeurs hétérogènes.

Description du sujet

But

L’objectif de la thèse est de proposer un ou plusieurs algorithmes d’ordonnancement temps réel pour les systèmes multiprocesseurs hétérogènes. Les tâches temps réel sont activées périodiquement, avec un intervalle spécifié entre deux activations successives, et doivent terminer leur exécution avant leurs échéances temporelles.

Pour les plates-formes multiprocesseurs, il est bien connu que la migration et les priorités dynamiques des tâches sont nécessaires pour définir un ordonnanceur optimal, c’est-à-dire un algorithme capable d’ordonnancer les tâches en respectant les échéances, si un tel ordonnancement existe.

Tout ordonnanceur réalise deux étapes fondamentales :

• Allouer les tâches aux processeurs
• Séquencer les tâches sur chaque processeur en respectant les échéances temporelles et en évitant qu’une tâche ne s’exécute simultanément sur deux processeurs (parallélisme intra-tâche).

Selon le modèle de tâche, les algorithmes optimaux peuvent réaliser l’allocation et le séquencement séparément ou bien simultanément. La frontière entre ces deux étapes reste floue lorsqu’il s’agit de concevoir des algorithmes optimaux ou des heuristiques efficaces. L’étude de ces dépendances dans les algorithmes existants de la littérature sera le point de départ de la thèse, afin de classifier les approches existantes et de mettre en évidence les problèmes ouverts.

Validation

Les solutions développées devront être validées formellement et comparées à l’état de l’art. Les simulations évalueront les performances des ordonnanceurs en fonction de la charge de travail supportée, ainsi que du nombre de préemptions et de migrations générées. Ces deux derniers paramètres impactent fortement la mise en pratique des solutions.

Le candidat devra être à l’aise dans le développement en langage Python. De façon complémentaire, les algorithmes pourront être évalués sur une plate-forme multiprocesseur de test existant dans notre laboratoire.
 

Références

[1] Sanjoy K. Baruah. Feasibility analysis of preemptive real-time systems upon heterogeneous multiprocessor platforms. In Real-Time Systems Symposium, pages 37–46. IEEE, 2004.

[2] Antoine Bertout, Joël Goossens, Emmanuel Grolleau, Roy Jamil, et Xavier Poczekajlo. Workload assignment for global real-time scheduling on unrelated clustered platforms. Real-Time Systems, pages 1–32, 2021.

[3] Antoine Bertout, Joël Goossens, Emmanuel Grolleau, et Xavier Poczekajlo. Template schedule construction for global real-time scheduling on unrelated multiprocessor platforms. In 2020 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 216–221. IEEE, 2020.

[4] Robert I. Davis et Alan Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Computing Surveys, 43(4), octobre 2011.

[5] Ernesto Massa, George Lima, Bjorn Andersson, et Vinicius Petrucci. Heterogeneous quasi-partitioned scheduling. In 2021 IEEE Real-Time Systems Symposium (RTSS), pages 266–278, 2021.

Le Laboratoire d'Informatique et d'Automatique pour les Systèmes (LIAS) est un laboratoire de recherche affilié à l’Université de Poitiers et à l’ISAE-ENSMA. Nos travaux de recherche, ancrés dans les fondements théoriques des mathématiques, de la théorie du signal, de l'informatique théorique et du génie électrique, sont à la frontière des Sciences et Technologies de l'Information et de la Communication (STIC) et des Sciences pour l'Ingénieur (SPI).

Voici la correction typographique de votre texte :

Le candidat devra être titulaire d’un master en informatique ou d’un titre d’ingénieur équivalent, avec des connaissances sur les systèmes informatiques, en mathématiques et en développement logiciel. La maîtrise de l’anglais, à l’écrit et à l’oral, est requise, et une bonne maîtrise du français sera appréciée.