Brevet FR2910654A1 — publié le 20080627

Procédés et dispositif d'estimation du temps d'exécution d'une application embarquée en présence de mémoire cache La présente invention concerne les procédés d'estimation et de démonstration du temps d'exécution d'une application temps réel. Elle s'applique à des dispositifs comprenant notamment une mémoire cache. Le procédé selon l'invention propose une méthode de majoration du temps d'exécution, au plus proche, de chacun des scénarios possibles de l'application. Ces scénarios sont déterminés par un ensemble dénombrable de services élémentaires de base, leur agencement dans le scénario étant déterministe. Le procédé selon l'invention s'inscrit dans le domaine des applications critiques embarquées, notamment dans l'aéronautique où la prédiction et la garantie de bon fonctionnement sont primordiales. Dans l'aéronautique, en particulier, dans le domaine des applications embarquées en avionique, il est important de répondre à des exigences de temps de calculs sévères, ces exigences pouvant être critiques pour la sécurité des aéronefs. Les temps de réponses et d'exécution des applications dimensionnent les architectures comprenant des boucles, des asservissements et des rafraîchissements. La nécessité de réduire les temps d'exécution des applications, a conduit au choix et à l'utilisation de composants de plus en plus performant. Notamment, la mémoire cache est un composant permettant de réduire les temps d'exécution des applications en informatique et en électronique. On entend par mémoire cache, une mémoire généralement proche d'un processeur capable de stocker une partie des informations les plus demandées par ledit processeur. Elle est associée à une mémoire vive et lui permet d'alléger la quantité d'information à stocker. Les temps d'exécutions sont de ce fait, généralement, plus rapide. On appelle cette mémoire également mémoire tampon ou mémoire intermédiaire ou encore antémémoire. 2910654 2 Par ailleurs, dans le secteur aéronautique, il est important de prédire et d'anticiper les mécanismes possibles d'une application et des interactions éventuelles avec d'autres applications. II est nécessaire de prévoir l'ensemble des scénarios d'une application et d'en maîtriser les 5 temps d'exécution critiques. Cette prédiction est, généralement, réalisée de manière déterministe en ce qui concerne les applications les plus critiques. Le but étant, par exemple, de borner dans le temps l'ensemble des comportements éventuellement critiques d'une application. Des tests sont donc nécessaires 1 o pendant les étapes d'optimisation des logiciels embarqués. Les comportements aux limites de chaque application ou logiciel font l'objet d'analyses et de tests poussés selon leur criticité. Un des aspects critiques dans l'avionique embarquée, généralement, est le temps d'exécution des applications qu'il faut maîtriser. 15 Les mémoires cache ont, pendant longtemps, été non-employées dans l'avionique embarquée dès lors que de fortes contraintes de temps d'exécution des applications étaient à considérer. II est difficile de prédire précisément ces temps d'exécution, ceux-ci étant dépendants de l'état de la 20 mémoire cache et de la variabilité des temps d'accès à la mémoire. Dans les cas où une mémoire cache était employée, son contenu était généralement figé de manière à supprimer cette variabilité liée au contenu du cache. Les temps d'accès à la mémoire cache ainsi que les changements d'état de la mémoire cache par chargement des données et du code avant 25 l'exécution d'une tâche sont aléatoires, ou du moins difficile à prévoir. Ce caractère aléatoire ne permet pas de connaître finement les temps nécessaires à l'exécution d'une tâche. Généralement, dans le but de prédire les temps d'exécution d'une 30 application, celle-ci est décomposée selon l'architecture en cycles élémentaires exécutés séquentiellement. Un cycle élémentaire est, notamment, exécuté dans un intervalle de temps déterminé au préalable et suffisant. Cet intervalle comprend une marge de temps en théorie non-utilisée par les instructions comprises dans le cycle élémentaire. Cette marge 2910654 3 est calculée par rapport au scénario correspondant au pire cas, c'est à dire à l'exécution la plus longue du cycle élémentaire. Cette découpe permet de définir un temps partagé de l'utilisation des ressources entre différentes applications, éventuellement exécutées en 5 parallèle. Ces cycles élémentaires comprennent eux-mêmes des services élémentaires, généralement connus. Ces services élémentaires sont constitués d'une suite d'instructions déterminées et peuvent être bornés dans le temps. 10 Dans le cas où une mémoire cache est utilisée, celle-ci comprend à chaque instant d'une part des données nécessaires à l'exécution d'un service et d'autre part du code, c'est à dire une suite d'instructions. Le contenu de la mémoire cache évolue en fonction des services qui sont exécutés dans l'application. 15 Les services élémentaires auxquels fait appel une application, lors de son exécution, peuvent s'exécuter avec le code ou/et les données pré-chargés nécessaires à l'exécution du service. Il est possible que le cache contienne d'autres données et/ou un code ne correspondant pas au service appelé. Dans ce dernier cas, il est nécessaire de charger la mémoire cache 20 du code et des données nécessaires à l'exécution dudit service. Eventuellement, il peut être nécessaire de vider la mémoire cache des données ou/et du code déjà présents dans la mémoire cache si celle-ci est pleine. Lors de l'enchaînement d'exécutions de services élémentaires 25 constituants l'exécution complète d'un cycle élémentaire d'une application, une variabilité du temps d'exécution est liée au contenu de la mémoire cache et aux temps d'accès à la mémoire. Cette variabilité est le plus souvent non négligeable et ne permet pas de connaître finement la durée de l'exécution de l'enchaînement de services élémentaires différents. 30 Ainsi, les estimations des temps d'exécution d'application comprenant une mémoire cache sont aujourd'hui trop largement majorées, donc pas assez prédictives. 2910654 4 Par ailleurs, des facteurs extérieurs à l'application peuvent avoir une influence sur les conditions d'exécution et donc sur la durée d'exécution d'un enchaînement de services élémentaires. Notamment les configurations de processeur ou du système d'exploitation conduisent à considérer 5 différents scénarios d'enchaînements de services élémentaires dans un cycle élémentaire. La variabilité associée à l'exécution d'un cycle élémentaire est difficilement prévisible compte tenu des différents scénarios. Le procédé selon l'invention propose une méthode prédictive 10 d'estimation du temps d'exécution d'une application lorsqu'une mémoire cache est utilisée. Pour cela, un profil d'usage de la mémoire cache est défini. Ce profil étant établi des bornes dans le temps peuvent être définie pour connaître au plus proche les temps d'exécution des services élémentaires et leur variabilité. Dans un deuxième temps, des bornes dans le 15 temps sont calculées, ainsi que la variabilité pour prédire au plus proche la durée d'exécution des cycles élémentaires et ceci en considérant l'ensemble des scénarios possibles. Le Procédé de prédiction du temps d'exécution d'une application à 20 partir d'un profil d'usage d'une mémoire cache s'applique à un système comprenant une mémoire cache, ladite application comprenant au moins un cycle élémentaire (CE), chaque cycle élémentaire s'exécutant selon un scénario (n) déterminé, ledit scénario étant compris dans un ensemble de scénarios déterminés en fonction de l'application et de son environnement, 25 chaque scénario comprenant un ensemble de services élémentaires (Si) connus et exécutés dans un ordre déterminé. Avantageusement, le profil d'usage est déterminé, pour chaque service du scénario, par au moins un temps d'estimation (Bmax-si), ledit temps d'estimation étant un majorant du temps d'exécution de l'ensemble des 30 exécutions d'un service élémentaire (Si) dans un scénario donné (n), et déterminé en fonction : • d'un taux moyen de conflit de cache (%conflit) correspondant pour un ensemble de services, au nombre moyen de recharges nécessaires de la mémoire cache avant l'exécution d'un service 35 sur le nombre total d'exécutions des services dans chaque 2910654 5 scénario, la recharge de la mémoire cache correspondant au vidage de la mémoire et au chargement du code et des données en mémoire nécessaire à l'exécution du service ; • et de deux états de la mémoire cache auquel sont associés des temps d'exécution moyens pour chaque service dont : • le premier état, appelé MAX, représente la mémoire cache lorsqu'elle contient du code et des données ne correspondant pas au code et aux données nécessaires à l'exécution du prochain service, dont le temps d'exécution moyen pour le ieme service (Tmax(i)) est déterminé ; • le deuxième état, appelé OPTIM-max, représente l'état de la mémoire cache lorsqu'elle contient des données ne correspondant pas aux données nécessaires à l'exécution du prochain service et comprenant le code nécessaire à l'exécution du prochain service, dont le temps d'exécution moyen pour le ieme service (Toptimax(i)) est déterminé, ledit temps majorant (Bmax_si) étant défini par la somme : o du temps moyen d'exécution du service lorsque la mémoire cache est en condition MAX (Tmax(i)), pondéré par le nombre statistique moyen d'appel du service en condition MAX (Nimax), avec Nimax = MAX(1, Ni . %conf,;,) , Ni.%conflit étant le nombre d'appel du service (Ni) dans un scénario multiplié par le taux de conflit du cache (%conflit) ; o et du temps moyen d'exécution de ce même service lorsque la mémoire cache est en condition OPTIM-max (Toptimax(i)), pondéré par le nombre statistique d'appel du service lorsque la condition n'est pas en condition MAX dans le scénario (Ni-Nimax). 30 Avantageusement, le profil d'usage de la mémoire cache comprend un temps d'estimation (Burin-si) minorant le temps d'exécution de l'ensemble des exécutions d'un service élémentaire (Si) dans un scénario donné (n), et déterminé en fonction : • du taux moyen de conflit (%conflit) ; 5 10 15 20 25 2910654 6 • et de deux états de la mémoire cache auquel sont associés des temps d'exécution moyens pour chaque service dont : • le premier état, appelé CLASS, représente la mémoire cache vide ou disposant d'un espace disponible suffisant pour accueillir le code et les données du service à exécuter, dont le temps d'exécution moyen pour le ieme service (Tclass(i)) est déterminé ; • le deuxième état, appelé OPTIM-min, représente l'état de la mémoire cache lorsqu'elle contient des données correspondantes aux données nécessaires à l'exécution du prochain service et comprenant le code nécessaire à l'exécution du prochain service, dont le temps d'exécution moyen pour le ieme service (Toptimin(i>) est déterminé, ledit temps minorant (Burin-si) étant défini par la somme : 15 o du temps moyen d'exécution du service lorsque la mémoire cache est en condition CLASS (Tciass(i)), pondéré par le nombre statistique moyen d'appel du service en condition CLASS (Niclass), avec Nicias,. = M4X (1, Ni • %conJ,;,) , Ni.%conflit étant le nombre d'appel du service (Ni) dans un scénario 20 multiplié par le taux de conflit du cache (%conflit) ; o et du temps moyen d'exécution de ce même service lorsque la mémoire cache est en condition OPTIM-min (Toptimin(i)), pondéré par le nombre statistique d'appel du service lorsque la condition n'est pas en condition CLASS dans le 25 scénario, c'est à dire Ni-Niciass• Avantageusement, une étape supplémentaire consiste à estimer un temps majorant et un temps minorant le temps d'exécution d'un scénario (n) d'une application, par une première borne (Bmax(n)) et une deuxième 30 borne (Bmin(n)), définie respectivement : • d'une part, comme la somme des temps d'estimation majorant chaque service compris dans le scénario ; • et d'autre part, comme la somme des temps d'estimation minorant chaque service compris dans le scénario ; 5 10 35 2910654 7 Avantageusement, une étape supplémentaire consiste, pour un ensemble de scénario : • d'une part, à calculer l'ensemble des bornes (Bmin, Bmax) de chaque scénario ; 5 • d'autre part, à mesurer le temps moyen d'exécution de chaque scénario (n) de l'ensemble (Tmoy(n)) à l'aide de moyens d'analyse, • et enfin, à ajuster le taux moyen de conflit de la mémoire cache (%conflit) de façon à ce que pour l'ensemble des scénarios la 10 mesure du temps moyen d'exécution de chaque scénario soit compris dans les bornes calculées (Emin, Bmax) du scénario. Avantageusement, la valeur du taux moyen de conflit de la mémoire cache est ajustée de manière à ce que le temps moyen d'exécution 15 d'au moins un des scénarios corresponde au temps majorant (Bmax) de ce même scénario. Avantageusement, le calcul de la variabilité du temps d'exécution d'un scénario comprend : 20 • Une première étape de calcul de la variabilité du temps d'exécution de chaque service (Si) du scénario, effectuée pour chacun des états de la mémoire cache, CLASS, MAX, OPTIM-max et OPTIM-min, noté respectivement VAolass-i, VArnax-i, VAoptimax-i, VAoptimin-i, celle-ci étant le résultat de la différence entre le temps d'exécution 25 le plus long et le temps d'exécution le plus court du service ; • Une deuxième étape de calcul de la moyenne du temps d'exécution de chaque service pour chacun des états de la mémoire cache, CLASS, MAX, OPTIM-max et OPTIM-min, respectivement noté Tciass(i), Tmax(i), Toptimax(i), Toptimin(i); 30 • Une troisième étape de pondération du temps d'exécution mesuré de chaque service par le taux de variabilité analysé pour ledit service dans chaque état de la mémoire cache ; • Une quatrième étape, conformément au profil d'usage déterminé, de calcul de la somme des pondérations des variabilités de chaque 2910654 8 service d'un scénario, de manière à obtenir la variabilité minimale (TvA-min) suivante : Nimax ~Tclass(i) VAclass(i) + (Ni ù Nimax) E7optimin(i) . VAoptimin(i) ainsi que la variabilité maximale (TvA-max) suivante : 5 Ni max Tmax(i) VAmax(i) + (Ni ù Ni max I Tooti max(i) . VAopti max(i) • Une cinquième étape déterminant la variabilité du scénario comme la variabilité maximale calculée à la quatrième étape. Avantageusement, le procédé de calcul d'un temps majorant un 10 cycle élémentaire d'une application temps réelle donnée, le cycle élémentaire s'effectuant selon une succession d'au moins un service élémentaire dont l'ordre et la répétition déterminent autant de scénarios possibles, est caractérisé en ce que la majoration du temps d'exécution du cycle élémentaire est déterminée par la plus grande somme du majorant du 15 scénario et de sa variabilité, chaque somme (Tmaxi) étant effectuée pour l'ensemble des scénarios d'un cycle élémentaire. Avantageusement, la valeur du taux moyen de conflit de la mémoire cache est ajustée de manière à ce que le temps moyen d'exécution 20 d'au moins un des scénarios corresponde à la somme (Tmaxi) du majorant du scénario et de sa variabilité. Avantageusement, le procédé de calcul d'un temps majorant d'une suite d'instructions constituant une tache d'une application asynchrone 25 est caractérisé en ce que la suite d'instruction définie un cycle élémentaire unique. Avantageusement, l'exécution d'une application temps réel est décomposée en une suite d'exécution de cycles élémentaires, dont la 30 mémoire cache se vide entre chaque exécution, lesdits cycles élémentaires comprenant chacun un nombre dénombrable de scénarios possibles, lesdits scénarios comprenant un nombre déterminé de services de base dont le nombre, la répétition et l'agencement sont déterminés, les scénarios étant dénombrés par des conditions d'exécution, relatif à des composants 35 externes. 2910654 9 Avantageusement, le dispositif électronique embarqué dans un cockpit comprend une mémoire cache, un processeur et un écran de visualisation. II est caractérisé en ce que le temps d'exécution d'une 5 application est majoré au moyen du procédé défini précédemment. D'autres caractéristiques et avantages de l'invention apparaîtront à l'aide de la description qui suit faîte en regard des dessins annexés qui représentent : 10 • la figure 1 : la structure d'une application en cycles élémentaires et en services élémentaires ; • la figure 2 : l'accès à la mémoire cache avant l'exécution d'un service élémentaire • la figure 3 : la détermination du %conflit par encadrement. 15 Le procédé selon l'invention définit un profil d'usage de la mémoire cache et un taux de conflit de cette même mémoire afin de borner au plus proche les temps d'exécutions d'une application. Tout d'abord, pour cela il est nécessaire de décomposer 20 l'exécution d'une application quelle qu'elle soit dans une forme canonique. Dans l'électronique embarquée, des cycles élémentaires comprenant des exécutions de code sont généralement définis. L'application exécute un certain nombre de tâches dans ces cycles dont le but du procédé selon l'invention est de maîtriser au préalable le temps d'exécution. 25 Dans une architecture synchrone, ces cycles élémentaires sont généralement de durée fixe et sont répétés dans le temps à intervalles réguliers. Dans une application asynchrone, ces cycles élémentaires peuvent être de durée différente et exécutée non cycliquement. Le procédé selon l'invention s'applique sans restriction à des applications asynchrones. 30 La figure 1 représente une application synchrone s'exécutant en trois cycles successifs 1, 2, 3 différents et de durée égale. La représentation du cycle élémentaire 2 est décomposée en un certain nombre déterminé de services élémentaires 4, 5, 6 différents qui peuvent être appelés plusieurs fois dans un même cycle élémentaire. L'ordre et la répétition de ces services 35 représentent un scénario possible de l'exécution du cycle élémentaire. Avant 2910654 10 l'exécution de chaque service, la mémoire cache comporte des lignes de code et des données. Le code et les données étant ordonnées, ils constituent un état du cache 11 ou 12. Afin d'exécuter le prochain service, la mémoire cache charge le code et les données nécessaires à l'exécution du 5 prochain service. Selon si le code et/ou les données sont pré-chargées dans la mémoire cache, on définit plusieurs états probables de la mémoire cache avant l'exécution d'un service, ces états définissent des profils de la mémoire. Quatre conditions définissent un profil probable de l'état de la 10 mémoire cache avant l'exécution du service. Elles sont décrites selon les conditions suivantes : • la condition CLASS définit la mémoire cache comme totalement vide, ou disposant d'un espace disponible suffisant pour accueillir tout le code et les données du service à exécuter ; 15 • la condition MAX définit la mémoire comme entièrement pleine, des données et du code sont chargés dans la mémoire mais ne correspondent pas au code et aux données nécessaires à l'exécution du service ; • la condition OPTIM-max définit la mémoire cache comme chargée 20 avec le code nécessaire à l'exécution du service mais ne comprenant pas les données nécessaires à l'exécution du service ; • la condition OPTIM-min définit la mémoire cache comme chargée des données et du code nécessaires à l'exécution du service. 25 La figure 2 représente deux services élémentaires 4, 5 qui sont exécutés successivement. La mémoire cache 13 contient des données et du code évoluant constamment avec les exécutions des instructions de l'application. L'état de la mémoire cache, avant l'exécution des services 11 et 12, dépendent des données et du code chargés dans la mémoire cache. 30 Chacun des états de la mémoire cache sera donc modélisé par un état décrit dans le profil d'usage de la mémoire cache. Par ailleurs, les différents profils de la mémoire cache ne tiennent pas compte des temps d'accès 14, 15 de l'application à la mémoire. Ces 35 temps sont variables et sont modélisés dans le procédé selon l'invention. 2910654 11 La condition MAX définit le pire cas , c'est à dire le temps le plus long nécessaire à l'exécution du service en question. Par ailleurs la condition OPTIM-min définit le meilleur cas , c'est à dire le temps le plus 5 court nécessaire à l'exécution du service. Une première étape consiste à calculer les temps d'exécutions moyens de chacun des services d'un scénario dans chacune des conditions précitées. Pour cela, des moyens de tests et d'analyses sont nécessaires et 10 sont utilisés. Aujourd'hui de nombreuse plate-formes temps réel permettent de telles mesures et ne présentent pas de difficultés particulières. Pour un service élémentaire déterminé et connu, on connaît par construction le code et les données nécessaires à son exécution. Par exemple, dans la condition OPTIM-min, ces informations sont présentent 15 dans la mémoire cache avant l'exécution d'un service. On calcule le temps d'exécution par analyse de la différence constatée, entre le lancement de l'exécution et une valeur témoin par exemple renvoyant un signal de fin d'exécution. Dans ces conditions, selon cet exemple, le temps d'exécution du service est déduit dans la condition OPTIM-min. On procède de même pour 20 les autres conditions définies ci-dessus correspondant aux différents profils définis de la mémoire cache. On note, ainsi, les temps moyens d'exécution du service Si Tclass(Si), Tmax(Si), Toptimax(Si) et Toptimin(Si), respectivement aux conditions 25 CLASS, MAX, OPTIM-max et OPTIM-min. Pour chacun des services compris dans un scénario, on détermine ces quatre temps moyens d'exécution du service dans les différentes conditions. Par ailleurs, on définit la variabilité du temps d'exécution d'un 30 service correspondant à la différence entre le temps d'exécution le plus long et le temps d'exécution le plus court. On ajoute par ailleurs à cette variabilité les différentes causes de variabilité additionnelles, issues de l'analyse : û variabilité de parcours local du code du service, 2910654 12 variabilité introduite par des causes non-déterministes externes au code, mais dont l'impact peut être borné. On note respectivement, pour un service Si, les variabilités 5 calculées suivantes : VAciass(Si), VAmax(Si), VAoptimax(Si), VAoptimin(Si) D'autre part, le procédé selon l'invention introduit une valeur, ajustable, représentant le taux de conflit moyen de la mémoire cache, noté %conflit. Il y a conflit de la mémoire cache lorsque celle-ci doit être vidée avant io l'exécution d'un service élémentaire. Le code et/ou les données, correspondant au prochain service, doivent, nécessairement, être chargés dans la mémoire cache. Dans le procédé de majoration du temps d'exécution d'une application, %conflit est estimé pour l'ensemble des services quel que soit 15 l'état de la mémoire cache. C'est une valeur estimée de manière empirique. Le procédé propose de déterminer %conflit en plusieurs étapes. • Dans un premier temps, une valeur approximative est déterminée afin de situer la marge d'erreur sur le profil d'usage que l'on souhaite vérifier. • Dans un deuxième temps, %conflit est ajusté en fonction des résultats obtenus de l'estimation du temps d'exécution d'une série de scénarios déterminés. • Dans une troisième étape itérative, la deuxième étape est réitérée par ajustement de %conflit afin d'obtenir les bornes des temps d'exécutions les plus proches des valeurs mesurées. Le modèle du profil d'usage de la mémoire cache à vérifier, proposé selon le procédé, est le suivant : 30 Pour chaque service, noté Si, et pour chaque scénario, noté n, un temps majorant, noté Bmax-si(n), est défini, ledit majorant correspondant au temps maximum de toutes les exécutions du service Si dans ledit scénario. Pour cela, on définit : • le nombre d'appels du service dans un scénario, noté Ni, et ; 20 25 2910654 13 • le nombre statistique moyen d'appels du service en condition MAX dans le scénario, noté Nimax. Les deux valeurs Ni et Nimax dépendent donc d'un scénario donné, le nombre d'appels d'un service donné pouvant varier d'un scénario à un 5 autre. Pour un scénario n déterminé on a donc les deux valeurs Ni(n) et Nimax(n), qu'on écrira par la suite Ni et Nimax par simplification. Ce dernier est défini par la relation suivante : Nimax = MAX(l, Ni • %can1,i,) , MAX() étant la fonction qui établit le maximum de 1 o deux variables. Le temps majorant des exécutions d'un service dans un scénario est défini par une proportion du nombre Nimax d'exécutions en condition MAX et les autres exécutions en conditions OPTIM-max. On obtient l'expression littérale d'un temps majorant du temps d'exécution d'un service suivante : 15 BmaxùSi (n) = (Nimax) . Tmax(i) + (Ni ù Nimax) Toplimax(i) D'une manière analogue, pour chaque service Si et pour chaque scénario n, un temps minorant, noté Bmin-si(n), est défini, ledit minorant correspondant au temps minimum de toutes les exécutions du service Si 20 dans ledit scénario. On définit également le nombre statistique moyen d'appels du service en condition CLASS dans le scénario, noté Niciass• Ce dernier est défini par la relation suivante : Ni~,ass = MAX(1, Ni . %conflü) , Niciass étant dans ce cas de réalisation identique à Nimax. 25 On obtient donc l'expression littérale suivante, d'un temps minorant du temps d'exécution d'un service : Borin-Si (n) = (Nimax) . Tcia,s(i) + (Ni - Nimax ) Toptim;n(i) , avec Nimax = Niciass Dans un autre cas de réalisation le nombre statistique moyen 30 d'appels du service en condition CLASS dans un scénario pourrait dépendre d'un taux de conflit de cache spécifique. Ce cas de réalisation n'est pas détaillé dans ce brevet mais résulte du même procédé que celui de l'invention. 2910654 14 Il est possible de déterminer, en sommant les majorants de chaque service Si dans un scénario n, leur répétition dans le scénario étant prise en compte, le majorant du temps d'exécution de chaque scénario. Le majorant du scénario est déterminé à la variabilité près des temps d'accès à 5 la mémoire. Ainsi, pour un scénario déterminé, noté n, l'expression littérale d'un temps majorant le temps d'exécution d'un scénario, noté Bmax(n), peut s'exprimer de la manière suivante : Bmax ( n ) = Eservice(i) Bmax-si , la somme se faisant sur les services différents d'un scénario n déterminé. o Dans l'exemple de la figure 1, le scénario 2 comprend les services 4, 5 et 6. Leur répétition dans le scénario étant prise en compte dans chacun des majorants Bmax-4, Bmax-5, Bmax-6, on a : Bmax (2) Bmax-4 + Bmax-5 + Bmax-6 15 De la même manière, on détermine l'expression littérale d'un temps minorant le temps d'exécution d'un scénario n, noté Bmin(n). Il s'exprime de la manière suivante : Bmm (n) = 1 Service(i) Bmin-Si Dans l'exemple de la figure 1, on a : Bmin (2) =Bmin-4 + Bminù5 + Bmin-6 20 Le procédé selon l'invention permet, ensuite, de relever les mesures des bornes Bmax et Bmin de chacun des scénarios possibles de chaque cycle élémentaire. Une mesure du temps d'exécution de chacun des scénarios est 25 alors effectuée à l'aide des moyens d'analyse. II peut s'agir de moyens identiques, dans ce cas de réalisation, que des moyens de calculs du temps d'exécution des services ou éventuellement d'autres moyens de calculs. On note Tmoy(n), le temps mesuré du scénario n. Le temps mesuré est, ensuite, comparé aux bornes de ce même scénariocalculées 30 précédemment. Cette comparaison est effectuée pour chacun des scénarios. La figure 3 représente 5 temps d'exécution 40, correspondant à 5 scénarios différents d'un même cycle élémentaire. Les bornes 37 et 38 sont représentées sur chaque mesure 32, 33, 34, 35, 36. Chaque scénario représenté sur une échelle de mesures 30 permettant de comparer les 2910654 15 bornes de temps minorant et majorant les temps d'exécution pour un %conflit donné. Le %conflit peut correspondre à 30%, par exemple. Les cinq mesures 40, des temps d'exécution des scénarios, correspondent à Tmoy(l), 5 Tmoy(2), Tmoy(3), Tmoy(4) et Tmoy(5), telles que Tmoy(1) est la mesure réalisée sur le scénario numéro 1, et pareillement pour les scénarios 2, 3, 4, 5. Chaque scénario correspondant à un axe différent. Tmoy(l) est situé sur l'axe 32 qui est compris entre les bornes Bmin(1) et Bmax(l). De la même manière, Tmoy(2), Tmoy(3), et Tmoy(5) sont compris, respectivement, entre Bmin(2) et 10 Bmax(2), Bmin(3) et Bmax(3) et Bmin(5) et Bmax(5). Pour ces valeurs, le choix de %conflit paraît correspondre à une valeur conforme au taux moyen de conflit de la mémoire cache. En revanche, concernant la mesure du temps moyen d'exécution du scénario numéro 4 dont les valeurs des bornes sont positionnées sur l'axe 15 35, Tmoy(4) n'est pas compris entre les bornes Bmin(4) et Bmax(4). La valeur de %conflit ne correspond pas à un cas représentatif du taux moyen de conflit de la mémoire cache dans ce scénario. Le procédé selon l'invention propose, dans une autre étape, de corriger les estimations en changeants la valeur de %conflit. En effet, la 20 mesure de Tmoy(4) étant plus grande que Bmax(4), compte tenu du profil d'usage de la mémoire cache, du fait que Tmax(i) > Toptimax(i) et des deux expressions littrales suivantes : • BmaxùS i =(N max). 7 max(l) + +(N -N i max ).T opu maxi) ^ Ni =mA (l, Nl.%conflit), max 25 la valeur de %conflit a été sous-estimé. Il est alors intéressant de calculer, à nouveau, dans un premier temps, la valeur de Nimax et dans un second temps les bornes de temps majorant et minorant du temps d'exécution de chaque scénario avec une 30 nouvelle valeur de %conflit, par exemple 35%. Dans cette étape du procédé, il n'est pas nécessaire, de calculer à nouveau les durées Tmoy pour chaque scénario, mais uniquement de recalculer les bornes en prenant en compte les nouvelles valeurs de %conflit. Cette nouvelle valeur permet de comparer les durées Tmoy avec 35 chacune des bornes des scénarios calculées précédemment. 2910654 16 Si tous les temps moyens d'exécutions sont compris entre chaque borne de chaque scénario, alors un premier profil d'usage est déterminé. II est alors possible de l'optimiser. 5 La valeur la plus proche de %conflit correspondant au profil le plus optimum étant obtenu pour une valeur de Tmoy(i) égal à l'un des temps majorants du temps d'exécution du scénario numéro i, tel que tous les autres temps moyens d'exécution mesurés Tmoy(p#i) des scénarios p soient compris entre les bornes Bmin(p) et Bmax(p)• i0 Dans un autre cas de réalisation, on ajustera la valeur de %conflit de telle manière à obtenir une marge entre le temps d'exécution Tmoy(i) et le temps majorant d'un scénario quelque soit le scénario considéré. 15 La valeur de %conflit étant ajustée après un certains nombre d'itérations nécessaires, le profil d'usage de la mémoire cache est validé pour toutes les autres mesures de temps d'exécution des services Si. Cette dernière étape permet de choisir la valeur de %conflit la plus 20 adaptée au profil d'usage que l'on souhaite déterminer. Après validation du taux de conflit de la mémoire cache, le procédé selon l'invention propose de calculer la variabilité d'un scénario à partir du profil d'usage. 25 Cette variabilité permet de calculer le majorant global de chaque scénario obtenu par la somme des bornes des temps majorants le scénario et des temps correspondant à la variabilité relative du scénario. La variabilité d'un scénario est calculée à partir de chacune des variabilités de chaque service compris dans le scénario en prenant en 30 compte leur répétition dans ledit scénario. On additionne les temps d'exécution de chaque service élémentaire pondéré par la variabilité de chaque service élémentaire conformément au profil d'usage de la mémoire cache. 2910654 17 Pour établir la borne de temps majorant la variabilité d'un service, on considère les données définies précédemment : Ni, Nimax, Niciass, avec dans ce cas de réalisation Nimax = Niciass• 5 On note TvA-max(n) le temps correspondant à la variabilité maximum du scénario n, on a l'expression littérale suivante avec les notations définies précédemment : TvA-max(n) = Nimax E (Tmax(,)) VAmax (Si) + (Ni ù Nlmax) E (Tipti max(,)) . VAop,,max (Si) ; De même, on note TvA-min(n) le temps correspondant à la variabilité minimum du scénario n, on a l'expression littérale suivante : TVA-min(n) = Nlmax (Tclass(,)) VAclasr (Si) + (Ni ù Nlmax) • E (Toi. min(,)) . VAopt,min (Si) ; Le temps correspondant au majorant global de l'exécution d'un scénario, comptetenu de sa variabilité, est donc la somme : - du temps majorant la variabilité du scénario et ; du temps majorant l'exécution du scénario. 20 Ce temps majorant est noté TMAx, et l'expression littérale du majorant globale est la suivante pour le scénario noté n : TMAXI (n) = Bmax(n) + TvA-max(n) ; 25 L'ensemble des scénarios correspond à l'ensemble des exécutions possibles d'un cycle élémentaire relatives aux différentes conditions extérieures à l'application, le nombre de scénarios est donc fini et dénombré. Le procédé selon l'invention permet d'extraire le temps majorant le scénario le plus long d'un cycle élémentaire CE, celui-ci est noté TMAx(CE). 30 L'expression littérale du temps majorant le temps d'exécution d'un cycle élémentaire d'une application est la suivante : TMAx(CE) = MAX(TMAXI(n)), pour tout scénario n possible du cycle élémentaire CE. 10 15 35 2910654 18 Pour une application comprenant un certain nombre de cycles élémentaires, il suffit d'additionner les temps TMAx(CE) de chaque cycle élémentaire pour trouver un majorant du temps d'exécution de l'application. Ce temps majorant le temps d'exécution est noté WCET, dont 5 l'acronyme anglo-saxon est Worst Case Execution Time , signifiant pire cas du temps d'exécution. Le WCET s'écrit littéralement : WCET = 1TMf (CEi) ; Dans une application asynchrone, le cycle élémentaire CE est 10 considéré comme la durée de la tache de l'application asynchrone, la tache étant une suite d'instructions. Le procédé selon l'invention s'applique de la même manière en décomposant la tache asynchrone en services élémentaires s'exécutant selon un ordre déterminé, l'ordre et la répétition des services formant un scénario donné. 15 REVENDICATIONS 1. Procédé de prédiction du temps d'exécution d'une application à partir d'un profil d'usage d'une mémoire cache s'appliquant à un système comprenant une mémoire cache, ladite application comprenant au moins un cycle élémentaire (CE), chaque cycle élémentaire s'exécutant selon un scénario (n) déterminé, ledit scénario étant compris dans un ensemble de scénarios déterminés ~o en fonction de l'application et de son environnement, chaque scénario comprenant un ensemble de services élémentaires (Si) connus et exécutés dans un ordre déterminé, caractérisé en ce que ledit profil est déterminé, pour chaque service du scénario, par au moins un temps d'estimation (Bmax-si), ledit temps d'estimation 15 étant un majorant du temps d'exécution de l'ensemble des exécutions d'un service élémentaire (Si) dans un scénario donné (n), et déterminé en fonction : • d'un taux moyen de conflit de cache (%conflit) correspondant pour un ensemble de services, au nombre moyen de recharges 20 nécessaires de la mémoire cache avant l'exécution d'un service sur le nombre total d'exécutions des services dans chaque scénario, la recharge de la mémoire cache correspondant au vidage de la mémoire et au chargement du code et des données en mémoire nécessaire à l'exécution du service ; 25 • et de deux états de la mémoire cache auquel sont associés des temps d'exécution moyens pour chaque service dont : • le premier état, appelé MAX, représente la mémoire cache lorsqu'elle contient du code et des données ne correspondant pas au code et aux données nécessaires à 30 l'exécution du prochain service, dont le temps d'exécution moyen pour le ieme service (Tmax(i)) est déterminé ; • le deuxième état, appelé OPTIM-max, représente l'état de la mémoire cache lorsqu'elle contient des données ne correspondant pas aux données nécessaires à l'exécution 35 du prochain service et comprenant le code nécessaire à 2910654 20 l'exécution du prochain service, dont le temps d'exécution moyen pour le ieme service (Toptimax(i)) est déterminé, ledit temps majorant (Bmax-si) étant défini par la somme : o du temps moyen d'exécution du service lorsque la mémoire 5 cache est en condition MAX, pondéré par le nombre statistique moyen d'appel du service en condition MAX (Nimax), avec Ni. =MAX(1,Ni•%.flit), Ni•%conflit étant le nombre d'appel du service (Ni) dans un scénario multiplié par le taux de conflit du cache (%conflit) ; o et du temps moyen d'exécution de ce même service lorsque la mémoire cache est en condition OPTIM-max, pondéré par le nombre statistique d'appel du service lorsque la condition n'est pas en condition MAX dans le scénario (Ni- Nimax) 2. Procédé de prédiction du temps d'exécution d'une application à partir d'un profil d'usage d'une mémoire cache selon la revendication 1, caractérisé en ce que le profil d'usage de la mémoire cache comprend un temps d'estimation (Emin-si) minorant le temps d'exécution de l'ensemble des exécutions d'un service élémentaire (Si) dans un scénario donné (n), et déterminé en fonction : • du taux moyen de conflit (%conflit) ; • et de deux états de la mémoire cache auquel sont associés des temps d'exécution moyens pour chaque service dont : • le premier état, appelé CLASS, représente la mémoire cache vide ou disposant d'un espace disponible suffisant pour accueillir le code et les données du service à exécuter, dont le temps d'exécution moyen pour le ieme service (Tciass(i)) est déterminé ; • le deuxième état, appelé OPTIM-min, représente l'état de la mémoire cache lorsqu'elle contient des données correspondantes aux données nécessaires à l'exécution du prochain service et comprenant le code nécessaire à 30 2910654 21 l'exécution du prochain service, dont le temps d'exécution moyen pour le ieme service (Toptimin(i)) est déterminé, ledit temps minorant (Bmin-si) étant défini par la somme : o du temps moyen d'exécution du service lorsque la mémoire 5 cache est en condition CLASS, pondéré par le nombre statistique moyen d'appel du service en condition CLASS (Niclass), avec Nic,ass = MAX(1, Ni • %co,n,t), Ni.%conflit étant le nombre d'appel du service (Ni) dans un scénario multiplié par le taux de conflit du cache (%conflit) ; 10 o et du temps moyen d'exécution de ce même service lorsque la mémoire cache est en condition OPTIM-min, pondéré par le nombre statistique d'appel du service lorsque la condition n'est pas en condition CLASS dans le scénario, c'est à dire Ni-Nidass• 15 3. Procédé de prédiction du temps d'exécution d'une application à partir d'un profil d'usage d'une mémoire cache selon l'une quelconque des revendications 1 ou 2 caractérisé en ce qu'une étape supplémentaire consiste à estimer un temps majorant et un 20 temps minorant le temps d'exécution d'un scénario (n) d'une application, par une première borne (Bmax(n)) et une deuxième borne (Bmin(n)), définies respectivement : • d'une part, comme la somme des temps d'estimation majorant chaque service compris dans le scénario ; 25 • et d'autre part, comme la somme des temps d'estimation minorant chaque service compris dans le scénario ; 4. Procédé de prédiction du temps d'exécution d'une application à partir d'un profil d'usage d'une mémoire cache selon la revendication 3 caractérisé en ce qu'une étape supplémentaire consiste, pour un ensemble de scénario : • d'une part, à calculer l'ensemble des bornes (Bmin, Bmax) de chaque scénario ; 2910654 22 • d'autre part, à mesurer le temps moyen d'exécution de chaque scénario (n) de l'ensemble (Tmoy(n)) à l'aide de moyens d'analyse, • et enfin, à ajuster le taux moyen de conflit de la mémoire cache 5 (%conflit) de façon à ce que pour l'ensemble des scénarios la mesure du temps moyen d'exécution de chaque scénario soit compris dans les bornes calculées (Bmin, Bmax) du scénario. 5. Procédé de prédiction du temps d'exécution d'une application à 10 partir d'un profil d'usage d'une mémoire cache selon la revendication 4, caractérisé en ce que la valeur du taux moyen de conflit de la mémoire cache est ajustée de manière à ce que le temps moyen d'exécution d'au moins un des scénarios corresponde au temps majorant (Bmax) de ce même scénario. 15 6. Procédé de prédiction du temps d'exécution d'une application à partir d'un profil d'usage d'une mémoire cache selon l'une quelconque des revendications 1, 2, 3 ou 4, caractérisé en ce que le calcul de la variabilité du temps d'exécution d'un scénario 20 comprend : • Une première étape de calcul de la variabilité du temps d'exécution de chaque service (Si) du scénario, effectuée pour chacun des états de la mémoire cache, CLASS, MAX, OPTIM-max et OPTIM-min, noté respectivement VAclass-i, VAmax-i, 25 VAoptimax-i, VAoptimin-i, celle-ci étant le résultat de la différence entre le temps d'exécution le plus long et le temps d'exécution le plus court du service ; • Une deuxième étape de calcul de la moyenne du temps d'exécution de chaque service pour chacun des états de la 30 mémoire cache, CLASS, MAX, OPTIM-max et OPTIM-min, respectivement noté Tciass(i), Tmax(i), Toptimax(i), Toptiman(i); • Une troisième étape de pondération du temps d'exécution mesuré de chaque service par le taux de variabilité analysé pour ledit service dans chaque état de la mémoire cache ; 2910654 23 • Une quatrième étape, conformément au profil d'usage déterminé, de calcul de la somme des pondérations des variabilités de chaque service d'un scénario, de manière à obtenir la variabilité minimale (TVA_min) suivante : 5 Nimax ' ETcrass(i) ' VAcrass(i) + (Ni ù Nimax) ' ETopa min( i) . Mopti min( i) ainsi que la variabilité maximale (TvA_max) suivante : Nimax ETmax(i) VAmax(i) + (Ni ù Nimax) E Topiimax(i) ' VAoptimax(i) • Une cinquième étape déterminant la variabilité du scénario comme la variabilité maximale calculée à la quatrième étape. 10 7. Procédé de prédiction du temps d'exécution d'une application à partir d'un profil d'usage d'une mémoire cache selon l'une quelconque des revendications précédentes, caractérisé en ce que le cycle élémentaire s'effectuant selon une succession d'au moins 15 un service élémentaire dont l'ordre et la répétition déterminent autant de scénarios possibles, la majoration du temps d'exécution du cycle élémentaire est déterminée par la plus grande somme du majorant du scénario et de sa variabilité, chaque somme (Tmaxi) étant effectuée pour l'ensemble des scénarios d'un cycle 20 élémentaire. 8. Procédé de prédiction du temps d'exécution d'une application à partir d'un profil d'usage d'une mémoire cache selon la revendication 7, caractérisé en ce que la valeur du taux moyen de 25 conflit de la mémoire cache est ajustée de manière à ce que le temps moyen d'exécution d'au moins un des scénarios corresponde à la somme (Tmaxi) du majorant du scénario et de sa variabilité. 30 9. Procédé de prédiction du temps d'exécution d'une application à partir d'un profil d'usage d'une mémoire cache selon la revendication 7, caractérisé en ce que la suite d'instructions constituant une tache d'une application asynchrone définie un cycle élémentaire unique. 2910654 24 10. Procédé de prédiction du temps d'exécution d'une application à partir d'un profil d'usage d'une mémoire cache selon la revendication 7 caractérisé en ce que l'exécution d'une application temps réel est décomposée en une suite d'exécution de cycles 5 élémentaires, dont la mémoire cache se vide entre chaque exécution, lesdits cycles élémentaires comprenant chacun un nombre dénombrable de scénarios possibles, lesdits scénarios comprenant un nombre déterminé de services de base dont le nombre, la répétition et l'agencement sont déterminés, les ~o scénarios étant dénombrés par des conditions d'exécution, relatif à des composants externes. 11. Dispositif électronique embarqué dans un cockpit comprenant une mémoire cache, un processeur et un écran de visualisation, 15 caractérisé en ce que le temps d'exécution d'une application est majoré au moyen du procédé selon la revendication 10.