Skip to Main content Skip to Navigation
Theses

Ordonnancement temps-réel conscient des caches dans des architectures multi-cœurs : algorithmes et réalisation

Viet Anh Nguyen 1
1 PACAP - Pushing Architecture and Compilation for Application Performance
Inria Rennes – Bretagne Atlantique , IRISA-D3 - ARCHITECTURE
Résumé : Les temps avancent et les applications temps-réel deviennent de plus en plus gourmandes en ressources. Les plateformes multi-cœurs sont apparues dans le but de satisfaire les demandes des applications en ressources, tout en réduisant la taille, le poids, et la consommation énergétique. Le challenge le plus pertinent, lors du déploiement d’un système temps-réel sur une plateforme multi-cœur, est de garantir les contraintes temporelles des applications temps réel strict s’exécutant sur de telles plateformes. La difficulté de ce challenge provient d’une interdépendance entre les analyses de prédictabilité temporelle. Cette interdépendance peut être figurativement liée au problème philosophique de l’œuf et de la poule, et expliqué comme suit. L’un des pré-requis des algorithmes d’ordonnancement est le Pire Temps d’Exécution (PTE) des tâches pour déterminer leur placement et leur ordre d’exécution. Mais ce PTE est lui aussi influencé par les décisions de l’ordonnanceur qui va déterminer quelles sont les tâches co-localisées ou concurrentes propageant des effets sur les caches locaux et les ressources physiquement partagées et donc le PTE. La plupart des méthodes d’analyse pour les architectures multi-cœurs supputent un seul PTE par tâche, lequel est valide pour toutes conditions d’exécutions confondues. Cette hypothèse est beaucoup trop pessimiste pour entrevoir un gain de performance sur des architectures dotées de caches locaux. Pour de telles architectures, le PTE d’une tâche est dépendant du contenu du cache au début de l’exécution de la dite tâche, qui est lui-même dépendant de la tâche exécutée avant et ainsi de suite. Dans cette thèse, nous proposons de prendre en compte des PTEs incluant les effets des caches privés sur le contexte d’éxecution de chaque tâche. Nous proposons dans cette thèse deux techniques d’ordonnancement ciblant des archi- tectures multi-cœurs équipées de caches locaux. Ces deux techniques ordonnancent une application parallèle modélisée par un graphe de tâches, et génèrent un planning statique partitionné et non-préemptif. Nous proposons une méthode optimale à base de Programma- tion Linéaire en Nombre Entier (PLNE), ainsi qu’une méthode de résolution par heuristique basée sur de l’ordonnancement par liste. Les résultats expérimentaux montrent que la prise en compte des effets des caches privés sur les PTE des tâches réduit significativement la longueur des ordonnancements générés, ce comparé à leur homologue ignorant les caches locaux. Afin de parfaire les résultats ainsi obtenus, nous avons réalisé l’implémentation de nos ordonnancements dirigés par le temps et conscients du cache pour un déploiement sur une machine Kalray MPPA-256, une plateforme multi-cœur en grappes (clusters). En premier lieu, nous avons identifé les challenges réels survenant lors de ce type d’implémentation, tel que la pollution des caches, la contention induite par le partage du bus, les délais de lancement d’une tâche introduits par la présence de l’ordonnanceur, et l’absence de cohérence des caches de données. En second lieu, nous proposons des stratégies adaptées et incluant, dans la formulation PLNE, les contraintes matérielles ; ainsi qu’une méthode permettant de générer le code final de l’application. Enfin, l’évaluation expérimentale valide la correction fonctionnelle et temporelle de notre implémentation pendant laquelle nous avons pu observé le facteur le plus impactant la longeur de l’ordonnancement: la contention.
Complete list of metadatas

Cited literature [142 references]  Display  Hide  Download

https://hal.inria.fr/tel-01933422
Contributor : Isabelle Puaut <>
Submitted on : Friday, November 23, 2018 - 4:50:43 PM
Last modification on : Wednesday, June 24, 2020 - 4:19:47 PM

File

ThesisNguyen.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01933422, version 1

Citation

Viet Anh Nguyen. Ordonnancement temps-réel conscient des caches dans des architectures multi-cœurs : algorithmes et réalisation. Architectures Matérielles [cs.AR]. Université de Rennes 1 [UR1], 2018. Français. ⟨tel-01933422⟩

Share

Metrics

Record views

451

Files downloads

258