logo EDITE Sujets de doctorat

Etude probabiliste des contraintes de bout en bout dans les systèmes temps réel

Résumé rédigé par
Directeur de thèse:
Doctorant: Cristian MAXIM
Unité de recherche INRIA 0 Institut National de Recherches en Informatique et en Automatique

Projet

Les systèmes temps réel nécessitent la vérification des contraintes temporelles de ces systèmes. Cette vérification, faite tout au long du cycle de développement, doit prendre en compte des architectures de plus en plus complexes. Ces architectures rendent certaines techniques déterministe trop pessimistes, voire impossibles, à cause des scénarios pire cas sur lesquels elles s'appuient. Une alternative à ces problèmes est l’approche probabiliste [1,2]. L’approche probabiliste est, en général, plus adaptée pour la prise en compte des aléas et elle permet un dimensionnement plus fin des systèmes. Contraintes de bout en bout. Dans le contexte de systèmes embarqués temps réel de grande taille, les différentes activités du système (tâches, transmission de messages) s’exécutent sur un ensemble de ressources hétérogènes (microprocesseurs de technologies variées, différents réseaux de communication interconnectés par des passerelles, etc). Pour vérifier les contraintes de temps, il faut être en mesure de modéliser et d’analyser formellement les performances de la plateforme d’exécution et le comportement temporel des activités qui s’y exécutent. Le besoin va souvent au-delà de l’analyse d’une seule ressource considérée de façon isolée car certaines activités impliquent plusieurs ressources : on parle de contraintes de bout en bout (ex : contrainte de temps entre la détection d’une alarme par un capteur et l’application d’une consigne en réponse sur un calculateur distant). Formalismes pour l’analyse déterministe. Pour répondre à ce besoin, un certain nombre de formalismes ont été proposés au cours des 15 dernières années : approche holistique (York)[4], approche Symta/S (Braunschweig)[5], modèle event-stream (Ulm)[6], modèle trajectoriel (INRIA/LRI), Real-Time Calculus (ETZ)[7], contraintes de latence (INRIA)[8], etc. Ces modèles offrent des compromis précision des résultats/complexité des analyses différents, et sont bien adaptés pour des vérifications déterministes (ex : bornes sur les temps de réponse). Cependant, à notre connaissance, un seul premier résultat prend en compte des analyses probabilistes [3]. Ce résultat étend le Real-Time Calculus et il hérite de son pessimisme. Prise en compte des dépendances entre activités. Malgré l’existence de certains mécanismes de confinement, des dépendances à l’exécution entre activités existent le plus souvent : dépendance par l’accès à des bus de communication partagés, des accès à la mémoire ou à des I/O, accès aux caches, des préemptions, etc. Ces dépendances sont aujourd’hui particulièrement délicates dans un contexte multicore. Le besoin existe également pour décrire des situations de défaillances en chaîne. Il est dans une certaine mesure possible d’intégrer des dépendances dans des analyses probabilistes mais, à notre connaissance, aucun formalisme ne permet de les décrire de façon adapté à notre domaine applicatif, et les limites de ce qu’il est possible d’évaluer efficacement de façon analytique sont mal appréhendées.

Objectifs • Définition d’un formalisme de modélisation permettant de décrire des activités s’exécutant sur une ressource et des dépendances entre ces activités, dans l’optique d’analyses probabilistes (et de la simulation). Développement des analyses probabilistes adaptées dans le contexte de l’ordonnancement de calculateurs. Etude des différentes façons pratique de fixer les paramètres des modèles et des limites en termes de validation (ex : impossibilité d’estimer efficacement des événements en dessous d’un seuil de probabilité). Application sur une étude de cas. • Extension du modèle à des analyses probabilistes de bout en bout (plusieurs ressources). Identification des nouvelles dépendances entre activités/ressources. Validation sur une étude de cas. • En partant de l’identification d’un ensemble événements redoutés (ex : contraintes de performances non respectées, désynchronisation de flux, etc), en déduire à l’aide du modèle les causes les plus probables pour identifier les leviers permettant des gains significatifs. Organisation des travaux de recherche La première année sera dédiée d’abord à l’établissement d’un état de l’art ainsi qu’à la proposition d’un formalisme permettant de prendre en compte les analyses probabilistes. La première année va permettre également à l’étudiant de se familiariser avec les applications utilisées par l’entreprise et une liste d’études possibles de cas sera établie. La deuxième année sera consacrée à l’extension des résultats vers le cas de plusieurs ressources. Ce sera aussi le moment de consolider les résultats obtenus pendant la première année en travaillant sur une ou deux publications. En fin de la deuxième année le dernier objectif sera attaqué en s’appuyant sur des analyses statistiques afin d’identifier les leviers permettant d’utiliser justement la richesse d’un modèle probabiliste.

Bibliographie [1] J.L Dıaz, D.F. Garcia, K. Kim, C.G. Lee, L.L. Bello, Lopez J.M., and O. Mirabella. Stochastic analysis of periodic real-time systems. In the 23rd IEEE Real-Time Systems Symposium (RTSS02), 2002 [2] L. Cucu-Grosjean, L. Santinelli, M. Houston, C. Lo, T. Vardanega, L. Kosmidis, J. Abella, E. Mezzeti, E. Quinones and F. Cazorla, Measurement-Based Probabilistic Timing Analysis for Multi-path Programs, In the 24th Euromicro Conference on Real-Time Systems (ECRTS12), 2012 [3] L. Santinelli and L. Cucu-Grosjean, "Towards Probabilistic Real-Time Calculus", ACM SIGBED Review 8(1), March 2011 [4] K. Tindell and J. Clark, Holistic schedulability analysis for distributed hard real-time systems, Microprocessing and Microprogramming, 40(2-3), 1994 [5] http://www.symtavision.com/symtas.html [6] K. Albers, F. Bodmann and F. Slomka, Advanced Hierarchical Event-Stream Model. ECRTS'08: 20th Euromicro Conference on Real-Time Systems, 2008 [7] A. Simalatsar, Y. Ramadian, K. Lampka, S. Perathoner, R. Passerone, and L. Thiele, Enabling parametric feasibility analysis in real-time calculus driven performance evaluation. In the 14th international conference on Compilers, architectures and synthesis for embedded systems (CASES '11), 2011 [8] L. Cucu, N. Pernet and Y. Sorel, Periodic real-time scheduling: from deadline-based model to latency-based model, Annals of Operations Research, 159(1): 41-51, March 2008