Brevet FR3067482A1 — publié le 20181214

INRIA191.FRD Dispositif de caractérisation et/ou de modélisation de temps d'exécution pire-cas L'invention concerne le domaine de la conception des systèmes embarqués et la simulation de leur fonctionnement. Plus particulièrement, l'invention trouve son application dans la conception des systèmes embarqués critiques. Les systèmes embarqués critiques présentent la particularité d'être conçus de manière à ne connaître aucune faille et/ou pour présenter une très haute tolérance en cas d'apparition d'une faille. Par exemple, les ressources de ces systèmes sont doublées, triplées, voire décuplées, de manière à assurer une redondance en cas de panne d'un des éléments, ainsi que pour s'assurer que tous les calculs que ces systèmes sont chargés de réaliser sont terminés dans les temps souhaités. Historiquement, la progression technologique a été suffisante pour combler la complexification croissante de ces systèmes. En d'autres termes, l'accroissement de puissance disponible pour les processeurs des systèmes embarqués rendait la conception simple : il suffisait de surdimensionner le pilote avec un coefficient important pour garantir l'intégrité de tous les systèmes embarqués, qu'il s'agisse d'avionique, d'aérospatiale, d'automobile ou de ferroviaire. Dans les années récentes, deux effets combinés ont changé ce paradigme. D'une part, bien que les puissances des pilotes continuent de s'accroître de manière régulière, cette croissance s'est ralentie et tend à se ralentir encore plus au fur et à mesure que la finesse de gravure augmente. Cela est accru par le fait que la consommation électrique et la chaleur dégagée sont des critères qui sont devenus cruciaux, alors que cela n'était pas le cas pour les anciens pilotes. D'autre part, de grands progrès ont été réalisés en termes de modélisation physique et d'application pratique des systèmes embarqués, et les applications de ceux-ci exigent une puissance de calcul qui s'est grandement accrue, et qui tend à s'accroître plus vite que l'accroissement de la puissance des processeurs. 2 Il existe donc un besoin de produire un dispositif qui permet de mieux dimensionner les besoins en puissance de calcul des systèmes embarqués. Dans la demande de brevet français FR 15 51828, la Demanderesse a proposé un 5 dispositif de simulation et un procédé qui permettent d'évaluer de manière précise un temps d'exécution « pire cas » avec un degré de certitude choisi. Cela constitue une avance considérable dans le domaine, mais nécessite un jeu de données d'entrée qui caractérise suffisamment le processeur et le programme pour lequel le temps 10 d'exécution pire cas est recherché. Pour produire ces temps d'exécution, il est donc nécessaire d'exécuter le programme sur le processeur un nombre de fois extrêmement important, pouvant aller au-delà de 100 000 d'occurrences. Le jeu de données d'entrée pour ces exécutions fait partie de domaine de définition de programme sur le processeur respectif Ce domaine de définition étant souvent trop large pour être complètement visité 15 on peut faire appel à des méthodes en utilisant des procédés aléatoires (par exemple Monte-Carlo) pour choisir un jeu de données de ce même domaine. Chaque jeu de données d'entrée étend caractéristiques d'un processeur et d'un programme donné, il est donc nécessaire de relancer la production du jeu de données d'entrée à chaque fois qu'un nouveau programme est considéré. 20 L'invention vient améliorer la situation. À cet effet, l'invention propose un dispositif informatique de caractérisation de temps d'exécution par un processeur, comprenant une mémoire agencée pour recevoir des données de programme banc, des jeux de données de configuration de caractérisation et des jeux de données de cas d'exécution, et un 25 constructeur agencé, pour chaque jeu de données de cas d'exécution, pour déterminer un jeu de données de configuration pire-cas du processeur et un jeu de valeurs d'initialisation à partir d'un jeu de données de cas d'exécution, et déterminer un temps d'exécution de référence en exécutant le programme banc selon le jeu de données de cas d'exécution par le processeur configure avec le jeu de données de configuration avec le jeu de valeurs 30 d'initialisation, l'ensemble des temps d'exécution de référence formant un jeu de temps d'exécution de référence. 3 Le constructeur est en outre agencé, pour chaque jeu de données de configuration de caractérisation, pour déterminer un jeu de temps d'exécution de caractérisation, chaque jeu de temps d'exécution de caractérisation comprenant un nombre de temps d'exécution de caractérisation égal au nombre d'éléments du jeu de temps d'exécution de référence et 5 chaque temps d'exécution de caractérisation étant déterminé en exécutant le programme banc par le processeur configuré avec un jeu de données de configuration de caractérisation et avec un jeu de valeurs d' initialisation représentatif du programme banc et du processeur, et pour déterminer un jeu de coefficients de caractérisation en appliquant un algorithme de détermination du maximum de vraisemblance entre le jeu de temps 10 d'exécution de référence et les jeux de temps d'exécution de caractérisation. Le dispositif est enfin agencé pour retourner le jeu de données de configuration de caractérisation et le jeu de coefficients de caractérisation. 15 Selon diverses variantes, le dispositif peut présenter une ou plusieurs des caractéristiques suivantes : - le constructeur est agencé pour calculer les coefficients de caractérisation en déterminant, pour chaque jeu de temps d'exécution de caractérisation, une pluralité de vecteurs d'estimation dans lequel, pour chaque indice, la valeur est nulle ou vaut un si le 20 temps d'exécution de caractérisation d'indice est le plus proche du temps d'exécution de référence pour cet indice parmi tous les temps d'exécution de caractérisation pour cet indice, ainsi qu'une variance pour chaque jeu de temps d'exécution de caractérisation à partir de la pluralité de vecteurs d'estimation et des différences entre les temps d'exécution de référence et les temps d'exécution de caractérisation d'indices identiques, 25 et ensuite en calculant itérativement à partir d'une fenêtre glissante comprenant pour chaque itération et pour chaque jeu de temps d'exécution de caractérisation un nombre de temps d'exécutions égal au nombre d'éléments du jeu de temps d'exécution de référence et qui sont les plus récents : - une pluralité d'estimateurs pour l'itération courante, à partir d'une pluralité de lois 30 normales pour chaque jeu de temps d'exécution de caractérisation qui ont en commun une variance tirée de celle de l'itération précédente, et dont la moyenne est tirée à chaque fois d'un temps d'exécution de caractérisation sélectionné par 4 la fenêtre glissante de l'itération courante, lesquelles loi normales sont évaluées chacune au temps d'exécution du jeu de temps d'exécution de référence qui correspond à celui à partir duquel est déterminé la moyenne, une variance et un coefficient caractéristique pour chaque jeu de de temps 5 d'exécution de caractérisation à partir de l'estimateur de l'itération courante, des différences entre les temps d'exécution de référence et les temps d'exécution de caractérisation d'indices identiques sélectionnés par la fenêtre glissante de l'itération courante, et le nombre d'éléments du jeu de temps d'exécution de référence, 10 un nouveau temps d'exécution de caractérisation pour chaque jeu de temps d'exécution de caractérisation en appliquant une loi normale dont la variance est celle calculée pour chaque jeu de temps d'exécution de caractérisation pour l'itération courante et la moyenne est le temps d'exécution de caractérisation d'indice le plus élevé dans la fenêtre glissante, laquelle loi normale est évaluée au 15 temps d'exécution du jeu de temps de référence d'indice le plus élevé dans la fenêtre glissante, et un nouveau temps d'exécution de référence à partir des nouveaux temps d'exécution de caractérisation pour chaque jeu de temps d'exécution de caractérisation et des coefficients caractéristiques pour chaque jeu de de temps d'exécution de caractérisation pour l'itération courante, 20 les itérations étant répétées jusqu'à ce qu'une condition portant sur le nombre d'itérations ou sur une différence entre les coefficients de caractérisation pour chaque jeu de de temps d'exécution de caractérisation d'itérations consécutives soit remplie, le jeu de coefficients de caractérisation étant défini à partir des coefficients de caractérisation de la dernière itération, 25 - le constructeur est agencé pour calculer les estimateurs selon la formule suivante : z(j)(k, = N,sig(j - 1) (k)2) /_+1-1N,sig(j - 1) (k)2) où chaque z est un élément d'indice i dans l'estimateur z, N désigne la loi normale de moyenne m et de variance s, Mk désigne le temps d'exécution d'indice i dans le k-ième jeu de temps d'exécution de caractérisation, sig est la variance pour le k-ième jeu de temps 30 d'exécution de caractérisation et Mo désigne le temps d'exécution d'indice i dans le jeu de temps d'exécution de référence, 5 - le constructeur est agencé pour calculer les variances selon la formule suivante : ET-Fi zu)(k, 0 * (m0(0 Mk(0)2) sig(j)(02 = ETI +1-1 zu)(k, 0 où z est l'élément d'indice i dans l'estimateur z pour le k-ième jeu de temps d'exécution de caractérisation, Mk désigne le temps d'exécution d'indice i dans le k-ième jeu de temps 5 d'exécution de caractérisation, et Mo désigne le temps d'exécution d'indice i dans le jeu de temps d'exécution de référence, - le constructeur est agencé pour calculer les coefficients de caractérisation selon la formule suivante : alph(j)(0 = z(i)(k'IT 10 où z est l'élément d'indice i dans l'estimateur z pour le k-ième jeu de temps d'exécution de caractérisation et T est le nombre d'éléments du jeu de temps d'exécution de référence Mo, - le constructeur est agencé pour calculer les nouveaux temps d'exécution de caractérisation selon la formule suivante : 15 Mk = N , sig(j - 1)(02) où N désigne la loi normale de moyenne m et de variance s, Mk désigne le temps d'exécution d'indice i dans le k-ième jeu de temps d'exécution de caractérisation, et sig est la variance pour le k-ième jeu de temps d'exécution de caractérisation, et - le constructeur est agencé pour calculer les nouveaux temps d'exécution de référence 20 selon la formule suivante : Mo(T +j) = alph(k)Mk k=1 où Mo désigne le temps d'exécution d'indice i dans le jeu de temps d'exécution de référence, Mk désigne le temps d'exécution d'indice i dans le k-ième jeu de temps d'exécution de caractérisation, et alph est le coefficient de caractérisation associé au k- 25 ième jeu de temps d'exécution de caractérisation dans la j-ième itération. L'invention concerne également un dispositif de calcul d'une base de temps d'exécution pire-cas d'un programme par un processeur comprenant une mémoire agencée pour recevoir des données de programme, des jeux de données de configuration de 6 caractérisation et un jeu de coefficients de caractérisation obtenu par l'exécution du dispositif décrit plus haut, et un modélisateur agencé pour : - déterminer une pluralité de jeux de valeurs d'initialisation pour chaque jeu de données de configuration de caractérisation, le nombre de jeux de valeurs 5 d'initialisation étant le même pour tous les jeu de données de configuration de caractérisation, - déterminer une pluralité de temps d'exécutions en exécutant le programme par le processeur configuré avec chaque jeu de données de configuration de caractérisation et avec à chaque fois la pluralité de jeux de valeurs 10 d'initialisation correspondante, et - ajouter dans une base de temps d'exécution pire-cas une pluralité de temps d'exécution pire-cas, qui sont chacun égaux à la somme pour chaque les jeux de données de configuration de caractérisation du produit d'un des temps d'exécutions par le coefficient de caractérisation associé au jeu de données de 15 configuration de caractérisation qui a permis d'obtenir ce temps d'exécution, de sorte que la base de temps d'exécution pire-cas comprend un nombre de temps d'exécution égale au nombre de jeux de valeurs d'initialisation pour chaque jeu de données de configuration de caractérisation. 20 Selon diverses variantes, le dispositif peut présenter une ou plusieurs des caractéristiques suivantes : - le modélisateur est en outre agencé pour extrapoler des temps d'exécution pire-cas, et - le modélisateur est en outre agencé pour déterminer un temps d'exécution pire-cas avec une probabilité correspondante en appliquant un algorithme pWCET à la base de temps 25 d'exécution pire-cas. L'invention concerne également un procédé de caractérisation de temps d'exécution par un processeur, comprenant les opérations suivantes : a) recevoir des données de programme banc, des jeux de données de configuration 30 de caractérisation et des jeux de données de cas d'exécution, b) pour chaque jeu de données de cas d'exécution, déterminer un jeu de données de configuration pire-cas du processeur et un jeu de valeurs d'initialisation à partir 7 d'un jeu de données de cas d'exécution, et déterminer un temps d'exécution de référence en exécutant le programme banc selon le jeu de données de cas d'exécution par le processeur configure avec le jeu de données de configuration avec le jeu de valeurs d'initialisation, l'ensemble des temps d'exécution de 5 référence formant un jeu de temps d'exécution de référence, c) pour chaque jeu de données de configuration de caractérisation, déterminer un jeu de temps d'exécution de caractérisation, chaque jeu de temps d'exécution de caractérisation comprenant un nombre de temps d'exécution de caractérisation égal au nombre d'éléments du jeu de temps d'exécution de référence et chaque 10 temps d'exécution de caractérisation étant déterminé en exécutant le programme banc par le processeur configure avec un jeu de données de configuration de caractérisation et avec un jeu de valeurs d'initialisation représentatif du programme banc et du processeur, d) déterminer un jeu de coefficients de caractérisation en appliquant un algorithme 15 de détermination du maximum de vraisemblance entre le jeu de temps d'exécution de référence et les jeux de temps d'exécution de caractérisation, et e) retourner le jeu de données de configuration de caractérisation et le jeu de coefficients de caractérisation. 20 Selon diverses variantes, le procédé peut présenter une ou plusieurs des caractéristiques suivantes : - l'opération d) comprend calculer les coefficients de caractérisation en déterminant, pour chaque jeu de temps d'exécution de caractérisation, une pluralité de vecteurs d'estimation dans lequel, pour chaque indice, la valeur est nulle ou vaut un si le temps d'exécution de 25 caractérisation d'indice est le plus proche du temps d'exécution de référence pour cet indice parmi tous les temps d'exécution de caractérisation pour cet indice, ainsi qu'une variance pour chaque jeu de temps d'exécution de caractérisation à partir de la pluralité de vecteurs d'estimation et des différences entre les temps d'exécution de référence et les temps d'exécution de caractérisation d'indices identiques, et ensuite en calculant 30 itérativement à partir d'une fenêtre glissante comprenant pour chaque itération et pour chaque jeu de temps d'exécution de caractérisation un nombre de temps d'exécutions égal 8 au nombre d'éléments du jeu de temps d'exécution de référence et qui sont les plus récents : - une pluralité d'estimateurs pour l'itération courante, à partir d'une pluralité de lois normales pour chaque jeu de temps d'exécution de caractérisation qui ont en 5 commun une variance tirée de celle de l'itération précédente, et dont la moyenne est tirée à chaque fois d'un temps d'exécution de caractérisation sélectionné par la fenêtre glissante de l'itération courante, lesquelles loi normales sont évaluées chacune au temps d'exécution du jeu de temps d'exécution de référence qui correspond à celui à partir duquel est déterminé la moyenne, 10 - une variance et un coefficient caractéristique pour chaque jeu de de temps d'exécution de caractérisation à partir de l'estimateur de l'itération courante, des différences entre les temps d'exécution de référence et les temps d'exécution de caractérisation d'indices identiques sélectionnés par la fenêtre glissante de l'itération courante, et le nombre d'éléments du jeu de temps d'exécution de 15 référence, - un nouveau temps d'exécution de caractérisation pour chaque jeu de temps d'exécution de caractérisation en appliquant une loi normale dont la variance est celle calculée pour chaque jeu de temps d'exécution de caractérisation pour l'itération courante et la moyenne est le temps d'exécution de caractérisation 20 d'indice le plus élevé dans la fenêtre glissante, laquelle loi normale est évaluée au temps d'exécution du jeu de temps de référence d'indice le plus élevé dans la fenêtre glissante, et un nouveau temps d'exécution de référence à partir des nouveaux temps d'exécution de caractérisation pour chaque jeu de temps d'exécution de caractérisation et des coefficients caractéristiques pour chaque jeu 25 de de temps d'exécution de caractérisation pour l'itération courante, les itérations étant répétées jusqu'à ce qu'une condition portant sur le nombre d'itérations ou sur une différence entre les coefficients de caractérisation pour chaque jeu de de temps d'exécution de caractérisation d'itérations consécutives soit remplie, le jeu de coefficients de caractérisation étant défini à partir des coefficients de 30 caractérisation de la dernière itération, - l'opération d) comprend calculer les estimateurs selon la formule suivante : 9 N, sig - 1) (k)2) z(j)(k, = / N, sig(j- 1) (k)2) où chaque z est un élément d'indice i dans l'estimateur z, N désigne la loi normale de moyenne m et de variance s, Mk désigne le temps d'exécution d'indice i dans le k-ième jeu de temps d'exécution de caractérisation, sig est la variance pour le k-ième jeu de temps 5 d'exécution de caractérisation et Mo désigne le temps d'exécution d'indice i dans le jeu de temps d'exécution de référence, - l'opération d) comprend calculer les variances selon la formule suivante : z(j)(k, 0 où z est l'élément d'indice i dans l'estimateur z pour le k-ième jeu de temps d'exécution 10 de caractérisation, Mk désigne le temps d'exécution d'indice i dans le k-ième jeu de temps d'exécution de caractérisation, et Mo désigne le temps d'exécution d'indice i dans le jeu de temps d'exécution de référence, - l'opération d) comprend calculer les coefficients de caractérisation selon la formule suivante : z(i)(k, / alph(j)(k) = 1-J / T où z est l'élément d'indice i dans l'estimateur z pour le k-ième jeu de temps d'exécution de caractérisation et T est le nombre d'éléments du jeu de temps d'exécution de référence Mo, - l'opération d) comprend calculer les nouveaux temps d'exécution de caractérisation 20 selon la formule suivante : Mk = N, sig(j - 1)(k)2) où N désigne la loi normale de moyenne m et de variance s, Mk désigne le temps d'exécution d'indice i dans le k-ième jeu de temps d'exécution de caractérisation, et sig est la variance pour le k-ième jeu de temps d'exécution de caractérisation, et 25 - l'opération d) comprend calculer les nouveaux temps d'exécution de référence selon la formule suivante : + j) = alph(k)Mk k=1 ET-Fi zu)(k, 0 * (m0(0 Mk(0)2) sig(j)(02 = 15 10 où Mo désigne le temps d'exécution d'indice i dans le jeu de temps d'exécution de référence, Mk désigne le temps d'exécution d'indice i dans le k-ième jeu de temps d'exécution de caractérisation, et alph est le coefficient de caractérisation associé au kième jeu de temps d'exécution de caractérisation dans la j-ième itération. 5 L'invention concerne également un procédé de calcul d'une base de temps d'exécution pire-cas d'un programme par un processeur comprenant a) recevoir des données de programme, des jeux de données de configuration de caractérisation et un jeu de coefficients de caractérisation obtenu par l'exécution 10 du dispositif ou du procédé décrits plus haut, b) déterminer une pluralité de jeux de valeurs d'initialisation pour chaque jeu de données de configuration de caractérisation, le nombre de jeux de valeurs d'initialisation étant le même pour tous les jeu de données de configuration de caractérisation, 15 c) déterminer une pluralité de temps d'exécutions en exécutant le programme par le processeur configure avec chaque jeu de données de configuration de caractérisation et avec à chaque fois la pluralité de jeux de valeurs d'initialisation correspondante, et d) ajouter dans une base de temps d'exécution pire-cas une pluralité de temps 20 d'exécution pire-cas, qui sont chacun égaux à la somme pour chaque les jeux de données de configuration de caractérisation du produit d'un des temps d'exécutions par le coefficient de caractérisation associé au jeu de données de configuration de caractérisation qui a permis d'obtenir ce temps d'exécution, de sorte que la base de temps d'exécution pire-cas comprend un nombre de temps 25 d'exécution égale au nombre de jeux de valeurs d'initialisation pour chaque jeu de données de configuration de caractérisation. Selon diverses variantes, le procédé peut présenter une ou plusieurs des caractéristiques suivantes : 30 - e) extrapoler des temps d'exécution pire-cas, et 11 - el) déterminer un temps d'exécution pire-cas avec une probabilité correspondante en appliquant un algorithme pWCET à la base de temps d'exécution pire-cas. D'autres caractéristiques et avantages de l'invention apparaîtront mieux à la lecture de la 5 description qui suit, tirée d'exemples donnés à titre illustratif et non limitatif, tirés des dessins sur lesquels : - la figure 1 représente un diagramme schématique d'un dispositif selon invention, - la figure 2 représente un exemple de mise en oeuvre d'une fonction par un élément de la figure 1, 10 - la figure 3 représente un exemple de mise en oeuvre d'une fonction de la figure 2, - la figure 4 représente un exemple de mise en oeuvre d'une fonction de la figure 2, - la figure 5 représente un exemple de mise en oeuvre d'une fonction de la figure 2, - la figure 6 représente un exemple de mise en oeuvre d'une fonction par un élément de la figure 1, et 15 - la figure 7 représente un exemple de mise en oeuvre d'une fonction de la figure 6. Les dessins et la description ci-après contiennent, pour l'essentiel, des éléments de caractère certain. Ils pourront donc non seulement servir à mieux faire comprendre la présente invention, mais aussi contribuer à sa définition, le cas échéant. 20 La présente description est de nature à faire intervenir des éléments susceptibles de protection par le droit d'auteur et/ou le copyright. Le titulaire des droits n'a pas d'objection à la reproduction à l'identique par quiconque du présent document de brevet ou de sa description, telle qu'elle apparaît dans les dossiers officiels. Pour le reste, il 25 réserve intégralement ses droits. En outre, la description détaillée est augmentée de l'annexe A, qui donne la formulation de certaines formules mathématiques mises en oeuvre dans le cadre de l'invention. Cette Annexe est mise à part dans un but de clarification, et pour faciliter les renvois. Elle est 30 partie intégrante de la description, et pourra donc non seulement servir à mieux faire comprendre la présente invention, mais aussi contribuer à sa définition, le cas échéant. 12 La figure 1 représente un dispositif 2 selon l'invention dans son environnement. Le dispositif 2 comprend un constructeur 4, un modélisateur 6 et une mémoire 8. Dans le cadre de l'invention, la mémoire 8 peut être tout type de stockage de données 5 propre à recevoir des données numériques : disque dur, disque dur à mémoire flash (SSD en anglais), mémoire flash sous toute forme, mémoire vive, disque magnétique, stockage distribué localement ou dans le cloud, etc. Les données calculées par le dispositif peuvent être stockées sur tout type de mémoire similaire à la mémoire 8, ou sur celle-ci. Ces données peuvent être effacées après que le dispositif ait effectué ses tâches ou conservées. 10 Les données stockées dans la mémoire 8 sont des données de programme à tester, des jeux de facteurs de processeur et des n-uplets représentant des temps d'exécution d'un programme donné par un processeur configuré avec un jeu de facteurs donné. Dans l'exemple décrit ici, ces données sont calculées par le modélisateur 6. En variante, elles 15 pourraient être obtenues différemment. Les données stockées dans la mémoire 8 pourraient également être agencées sous une autre forme. Le constructeur 4 et le modélisateur 6 sont des éléments accédant directement ou indirectement à la mémoire 8. Ils peuvent être réalisés sous la forme d'un code 20 informatique approprié exécuté sur un ou plusieurs processeurs. Par processeurs, il doit être compris tout processeur adapté aux calculs décrits plus bas. Un tel processeur peut être réalisé de toute manière connue, sous la forme d'un microprocesseur pour ordinateur personnel, d'une puce dédiée de type FPGA ou SoC (« system on chip » en anglais), d'une ressource de calcul sur une grille, d'un microcontrôleur, ou de toute autre forme 25 propre à fournir la puissance de calcul nécessaire à la réalisation décrite plus bas. Un ou plusieurs de ces éléments peuvent également être réalisés sous la forme de circuits électroniques spécialisés tel un ASIC. Une combinaison de processeur et de circuits électroniques peut également être envisagée. 30 Le constructeur 4 a pour fonction la détermination d'un jeu de coefficients stocké dans un vecteur alph[]. Ce jeu de coefficients est déterminé sur la base d'un programme banc (« benchmark program » en anglais) pour un processeur que l'on cherche caractériser, 13 ainsi que pour un jeu de facteurs de processeur choisi pour le processeur que l'on cherche caractériser. En effet, un processeur peut être caractérisé par certains facteurs qui vont affecter son 5 fonctionnement. Par exemple, ces facteurs peuvent être l'état d'activation de l'un ou de plusieurs des coeurs du processeur et/ou leur fréquence de fonctionnement, l'état de fonctionnement d'une ou plusieurs mémoires vives bas niveau, l'état de fonctionnement de l'un ou de plusieurs des bus de communication au sein du processeur, l'état de fonctionnement de l'une ou de plusieurs des mémoires tampons du processeur, l'état 10 d'activation de fonction spécifiques de traitement de données, etc. Dans ce qui suit, le constructeur 4 va déterminer un jeu de données de temps d'exécution pire cas pour le programme banc pour le processeur donné dans une configuration pire cas, ainsi que pour chacun des jeux de facteurs de processeur. Ensuite, le jeu de 15 coefficients sera calculé pour représenter une correspondance entre les jeux de données de temps d'exécution associés à chacun des jeux de facteurs de processeur et le jeu de temps d'exécution pire cas. Le modélisateur 6 a pour rôle l'exploitation du jeu de coefficients. Ainsi, le modernisateur 20 6 reçoit des données de simulation 10 comprenant des données de programme à qualifier, le programme à qualifier étant considéré comme suffisamment similaire au programme banc. Les données de simulations 10 sont utilisées avec les jeux de facteurs de processeur pour déterminer des jeux de données de temps d'exécution du programme à qualifier pour chacun des jeux de facteurs de processeur, puis le jeu de coefficients est utilisé pour 25 générer un jeu de données de temps d'exécution pire cas pour le programme à qualifier. Ce jeu de données de temps d'exécution pire cas peut ensuite être étendu de manière synthétique afin de générer un grand nombre de temps d'exécution qui sont caractéristiques de l'exécution du programme à qualifier par le processeur donné en 30 conditions pire cas. Ces données étendues sont stockées dans des données pire cas 12 qui peuvent être utilisées conformément à ce qui a été décrit dans la demande de brevet 14 français FR 15 51828 (ou par une autre manière) pour déterminer un temps d'exécution pire cas par le processeur donné pour le programme à qualifier. Le temps pour obtenir le jeu de données de temps d'exécution pire cas et son extension 5 est bien plus court que le temps qui serait nécessaire à l'acquisition directe de temps d'exécution pour ce même programme en l'exécutant sur le processeur donné pour l'ensemble des évènements. Ainsi, le modélisateur 6 permet d'obtenir un jeu de données de temps d'exécution pire 10 cas comprenant un très grand nombre de données de manière bien plus rapide que ce qui était possible précédemment. Cela est obtenu en réalisant la quantité de calculs la plus intensive une seule fois pour calculer le jeu de coefficients, et réutilisant ceux-ci pour permettre de qualifier tous les programmes ultérieurs, dès lors qu'ils sont suffisamment semblables au programme banc. 15 Selon les variantes, le dispositif 2 peut comprendre le constructeur 4 et le modélisateur 6 ensemble, ou l'un seulement d'entre eux. En particulier, le modélisateur 6 pourrait recevoir, en plus des données de simulation 10, des données contenant le jeu de coefficients ainsi que les jeux de facteurs de processeur. 20 En variante, le dispositif de l'invention peut être utilisé dans d'autres applications que la détermination de temps « pire-cas » d'une tâche par un processeur, dès lors qu'il s'agit d'étudier la prise de valeurs extrêmes d'un paramètre physique. Tout comme les autres éléments, le constructeur 4 et le modélisateur 6 peuvent être réalisés de très nombreuses 25 manières et être, par exemple, codé sous la forme d'un programme informatique. La figure 2 représente un exemple d'une fonction mise en oeuvre par le constructeur 4 pour calculer le jeu de coefficients. 30 Dans une opération 200, le constructeur 4 exécute une fonction Uni() pour calculer le jeu de données de temps d'exécution pire cas pour le programme banc pour le processeur 15 donné dans une configuration pire cas. La figure 3 représente un exemple de mise en oeuvre de la fonction Trnl(). Dans une opération 300, un indice i est initialisé à zéro, et le programme banc B et le 5 processeur P sont reçus. Dans une opération 310, une fonction Cas() recevant le programme banc B est exécutée afin de déterminer tous les cas d'exécution possibles pour le programme banc B. Ces cas d'exécution possibles sont stockés dans un vecteur J. Pour cela, le programme banc et 10 découper de manière automatique ou manuelle en une pluralité de blocs d'appel relié entre eux par un graphe de séquencement du programme banc B, et les cas d'exécution sont générés en tenant compte des diverses possibilités matérielles d'exécution de ces blocs d'appel, sur l'ensemble des combinaisons possibles de blocs d'appel au sein du graphe de séquencement du programme banc B. En variante, le vecteur J peut être reçu 15 comme un paramètre, par exemple par l'utilisateur. Une boucle est alors lancée à partir d'une opération 320 dans laquelle l'ensemble des cas d'exécutions parcouru et exécuté par le processeur afin d'en tirer un temps d'exécution pire cas. Ainsi, dans l'opération 320, le vecteur J est dépilé dans une variable S, puis le 20 jeu de facteurs de processeur F est déterminé dans une opération 330, le processeur est initialisé dans une opération 340, et un vecteur de valeurs d'initialisation V est généré par une fonction Rand() qui reçoit la variable S comme argument dans une opération 350. Dans l'exemple décrit ici, la fonction Rand() génère le vecteur de valeurs d'initialisation V de manière aléatoire En variante, la fonction Rand() pourrait définir le 25 vecteur de valeurs d'initialisation V en le choisissant parmi un groupe de vecteurs qui sont représentatifs d'un point de vue statistique par rapport au cas d'exécution S sur le processeur P. Dans l'opération 330, une fonction Wc() recevant le processeur P et la variable S comme 30 arguments est exécutée afin de déterminer un jeu de facteurs de processeur F correspondant au fonctionnement pire cas pour le processeur P dans le cas d'exécution S. Par exemple, la fonction Wc() va générer un jeu de facteurs de processeur dans lequel un 16 seul des coeurs est activé, avec une fréquence de fonctionnement minimale, en désactivant les mémoires tampons, et en prévoyant un dysfonctionnement du bus de communication sur le processeur. En variante, le jeu de facteurs de processeur F peut être reçu comme paramètre, par exemple par l'utilisateur. Une fonction Init() est alors exécutée dans l'opération 340 avec le processeur P et le jeu de facteurs de processeur F comme arguments. Cette fonction accède au processeur P et le configure conformément au jeu de facteurs de processeur F. L'opération 350 peut être réalisé après l'opération 340, avant celle-ci ou en parallèle. Le temps d'exécution pire cas correspondant à la variable S est déterminé en exécutant une fonction Ex() dans une opération 360. La fonction Ex() exécute le cas d'exécution défini par la variable S avec le vecteur de valeurs d'initialisation V sur le processeur P initialisé à l'opération 340. 15 Le temps d'exécution résultant est stocké dans le jeu de données de temps d'exécution pire cas MO[i], puis l'indice i est incrémenté dans une opération 370 et la boucle reprend avec l'opération 340. Lorsque tous les cas d'exécution ont été parcourus, la fonction Uni() se termine dans une opération 399 avec le renvoi du jeu de données de temps 20 d'exécution pire cas MO. Le constructeur 4 exécute ensuite une fonction Trn2() dans une opération 210 dans laquelle il détermine une pluralité de jeux de données de temps d'exécution respectif à des jeux de facteurs de processeur choisis dans un ensemble de jeux de facteurs de 25 processeur. Comment on l'a décrit plus haut, l'ensemble de jeux de facteurs de processeur est choisi de manière à caractériser le comportement pire cas du processeur P, à la manière des vecteurs propres d'une matrice. Typiquement, chaque jeu de facteurs de processeur est défini en activant et/ou optimisant un ou plusieurs facteurs du processeur P, et en définissant tous les autres facteurs à leur valeur pire cas. 30 La figure 4 représente un exemple de mise en oeuvre de la fonction Trn2(). 5 10 17 Dans une opération 400, un indice i est initialisé à zéro, et l'ensemble de jeux de facteurs de processeur F, le programme banc B, le processeur P sont reçus, ainsi que le jeu de données de temps d'exécution pire cas MO. Il convient de noter que l'ensemble de jeux de facteurs de processeur F reçus dans l'opération 400 est distinct de celui déterminé dans 5 l'opération 330. Ici, chaque jeu de facteurs de l'ensemble de jeux de facteurs de processeur F représente une configuration que la fonction vise à qualifier. Dans une opération 410, une variable T est créée et reçoit le nombre de temps d'exécution contenus dans le jeu de données de temps d'exécution pire cas MO. De manière similaire, 10 dans une opération 420, une variable K est créée et reçoit le nombre de jeux de facteurs de processeur contenus dans l'ensemble de jeux de facteurs de processeur F. Une boucle est alors lancée dans laquelle un ensemble de jeux de données de temps d'exécution M1 à MK va être généré pour chaque jeu de facteurs de processeur, chaque 15 jeu de données de temps d'exécution M1 à MK recevant un nombre de temps d'exécution égal à la variable T. L'indice k du jeu de facteurs de processeur pour lequel un temps d'exécution doit être déterminé pour une instance donnée de la boucle est déterminé dans une opération 430 20 en calculant l'indice i modulo la variable K. L'indice j du temps d'exécution dans le jeu de données de temps d'exécution Mk est déterminé pour une instance donnée de la boucle est déterminé dans une opération 440 en calculant la partie entière de la division de l'indice i par la variable T. Les opérations 430 et 440 ont pour conséquence que les jeux de données de temps d'exécution Mk sont déterminés de manière croissante, un temps d'exécution à la fois. Cela peut être réalisé dans un autre ordre, dès lors qu'un aléa est préservé afin de ne pas biaiser la construction des jeux de données de temps d'exécution Mk. 25 30 Ensuite, le processeur P est initialisé avec le jeu de facteurs de processeur d'indice k dans l'ensemble de jeux de facteurs de processeur dans une opération 450 similaire à 18 l'opération 340, puis un vecteur de valeurs d'initialisation V est généré en appliquant une fonction Rand2() au programme banc B dans une opération 460 de manière similaire à l'opération 350. Dans l'exemple décrit ici, la fonction Rand2() génère le vecteur de valeurs d'initialisation V de manière aléatoire En variante, la fonction Rand2() pourrait 5 définir le vecteur de valeurs d'initialisation V en le choisissant parmi un groupe de vecteurs qui sont représentatifs d'un point de vue statistique par rapport au cas d'exécution S sur le processeur P. Enfin, le temps d'exécution pire cas correspondant au vecteur de valeurs d'initialisation V 10 est déterminé en exécutant une fonction Ex() dans une opération 470. La fonction Ex() exécute le cas d'exécution défini par le vecteur de valeurs d'initialisation V pour le programme banc B sur le processeur P initialisé à l'opération 450. Le temps d'exécution résultant est stocké dans le jeu de données de temps d'exécution 15 Mk[j], puis l'indice i est testé dans une opération 480 afin de déterminer si tous les jeux de données de temps exécution Mk ont été calculés. Si ce n'est pas le cas, alors l'indice i est incrémenté dans une opération 480 et la boucle reprend avec l'opération 430. Sinon, la fonction Trn2() se termine dans une opération 499 20 avec le renvoi de l'ensemble de jeux de données de temps d'exécution M1 à MK. Le constructeur 4 exécute ensuite une fonction Fit() dans une opération 220 dans laquelle il détermine un jeu de coefficients alph[] qui caractérise la correspondance entre chacun des jeux de données de temps d'exécution M1 à MK avec le jeu de données de temps 25 exécution pire cas MO. Cela est réalisé en appliquant un modèle bayésien (« Bayesian Model Averaging » en anglais). 30 Selon ce modèle, la fonction de distribution de probabilité d'une prédiction, sur la base d'une pluralité de modèles M1 à MK pour expliquer un modèle MO peut être peut-être écrite conformément à la formule [10] de l'annexe A. 19 Les travaux de la Demanderesse ont révélé qu'en corrigeant le biais des jeux de données de temps d'exécution M1 à MK, ceux-ci peuvent être réécrits sous la forme de prédicteurs fi à fK, ce qui permet de définir une fonction de distribution de probabilité conditionnelle 5 sur chaque prédicteur fk, et de réécrire la formule [10] conformément à la formule [20] de l'annexe A. Dans cette formule, chaque fonction de distribution de probabilité conditionnelle sur un prédicteur fk peut alors être approchée au moyen d'une loi normale centrée sur une fonction linéaire du prédicteur fk. 10 La détermination de l'ensemble des lois normales sur la base des prédicteurs fk permet alors de déterminer tous les coefficients du vecteur alph[]. Pour cela, la Demanderesse utilise la fonction de vraisemblance dont elle maximise le logarithme conformément à l'algorithme EM (« The Eill algorithm and extensions » par Geoffrey J. McLachlan, et Thriyambakam Krishnan, 1997) qui est une extension de l'article « Maximum Likelihood 15 from Incomplete Data via the Eill Algorithm » de Dempster, Laird et Rubin dans Journal of the Royal Statistical Society. Series B (Methodological), Vol. 39, No. 1. (1977), pp. 138. Cela est réalisé en utilisant la formule [30] de l'annexe A. La Figure 5 représente un exemple de mise en oeuvre de la fonction permettant de 20 déterminer le vecteur alph[] pour les jeux de données de temps d'exécution M1 à MK par rapport au jeu de données de temps d'exécution MO. Dans une opération 500, les jeux de données de temps d'exécution MO à MK sont reçues, ainsi que le nombre T de données dans chaque jeu de données de temps d'exécution, et 25 un indice j est initialisé à 1. Dans une opération 510, l'algorithme est initialisé en calculant un estimateur z(0) et une vecteur de variance sig(0) au moyen d'une fonction Min(). La fonction Min() reçoit les jeux de données MO à MK, et, pour chaque temps d'exécution de chaque jeu M1 à MK, 30 définit une valeur qu'elle stocke dans z(0) qui vaut 1 si un temps d'exécution d'indice donné est le plus proche parmi tous les temps d'exécution de même indice du temps d'exécution ayant ce même indice dans MO. Dit autrement, si les jeux d'exécutions sont 20 indiciés par la lettre i, alors z(0)(r,i) vaut 1 si Mr(i) est le plus proche de MO(i) parmi tous les Mk(i). Tous les autres z(0)(k,i) sont mis à 0. Ensuite, le vecteur de variance sig(0) est calculé pour chaque k selon la formule [40] de l'annexe A, avec j = 0. 5 Une boucle est alors lancée dans laquelle l'estimateur z(j), le vecteur de variance sig(j) et le vecteur de poids alph(j) sont évalués séquentiellement, et les jeux de données sont étendus en utilisant une fenêtre glissante. La boucle commence la mise à jour de l'estimateur z(j) est mis à jour dans une opération 10 530. Pour cela, chaque z(j)(k,i) est calculé à partir de la formule [50] de l'annexe A, où N(X,Y)(z) désigne la loi normale de moyenne X, de variance Y, calculée en z. L'indice i est compris entre j et T+j-1, et l'indice k est compris entre 1 et K. Le vecteur z(j) contient donc T*K valeurs. 15 Le vecteur sig(j) est alors évalué dans une opération 530 en appliquant la formule [40] de l'annexe A, et le vecteur de poids alph(j) est évalué dans une opération 540 en appliquant la formule [60] de l'annexe A. Les vecteurs sig(j) et alph(j) permettent de définir K lois normales déterminées sur une 20 fenêtre d'indice i compris entre j et T+j-1 pour chacun des jeux de données de temps d'exécution Mk pour k compris entre 1 et K. Enfin, de nouveaux temps d'exécution sont déterminés à partir de ces estimations dans une opération 550. Pour cela, une fonction M() est exécutée, qui calcule dans un premier 25 temps un nouveau temps d'exécution Mk(T+j) pour chaque k compris entre 1 et K en appliquant la formule [70] de l'annexe A, c'est-à-dire en appliquant la loi normale dont les paramètres viennent d'être évalués pour la fenêtre de temps d'exécution d'indice k dont les valeurs sont celles associées aux indices compris entre j-1 et T+j-1, avec comme moyenne le dernier temps d'exécution de cette fenêtre (c'est-à-dire Mk(T+j-1)), comme 30 variance la valeur d'indice k du vecteur sig(j), évaluée au point M0(T+j-1). Une fois que la fenêtre a été étendue pour tous les k entre 1 et K, le jeu de données de temps d'exécution MO est également étendue conformément à la formule [80] de l'annexe A. 21 Un test est alors réalisé dans une opération 560 pour déterminer si le vecteur alph(j) est suffisamment proche du vecteur alph(j-1), ce qui permet de déterminer que l'algorithme a convergé. Si ce n'est pas le cas, alors j est incrémenté dans une opération 570. Sinon, la 5 fonction Fit() se termine alors en renvoyant le jeu de coefficients alph[j] dans une opération 599. Dans l'exemple de la Figure 5, la longueur de la fenêtre glissante utilisée est égale à T, c'est-à-dire le nombre d'éléments de MO. Cependant, cette longueur représente un 10 maximum et pourrait être inférieur. Par exemple, la longueur de la fenêtre glissante pourrait être choisie à partir de critères tels que le Continous Rank Probability Score (CRPS) ou le Root Mean Square Error (RMSE). Dans ce cas, les opérations 510, 530 et 550 pourront être adaptées à une longueur plus petite. 15 La Figure 6 représente un exemple de mise en oeuvre d'une fonction de calcul du temps de calcul pire cas pour un programme TP sur la base de la caractérisation qui vient d'être faite. En effet, le modèle de comportement pire cas MO du processeur P ayant été caractérisé au moyen des jeux de facteurs F[1] à F[K] et des poids alph[1] à alph[k] correspondants, il devient possible de caractériser un nouveau programme TP différent 20 du programme banc B en testant le nouveau programme TP un nombre R de fois avec les jeux de facteurs F[1] à F[K], tout en ayant R très inférieur aux nombre d'exécutions du modèle MO du programme banc originel. Les travaux de la Demanderesse ont démontré qu'un nombre T = 1000 ou 10 000 et un nombre R = 100 d'exécutions suffisent pour obtenir des résultats satisfaisants. Cela signifie que l'invention permet de réduire par un 25 ordre de 100 le nombre d'exécutions nécessaires de programme, par rapport aux 100 000 exécutions de l'art antérieur. Ainsi, dans une opération 600, le modèle de temps d'exécution pire-cas pour le programme TP est déterminé en exécutant une fonction Use() qui reçoit le programme 30 TP, le vecteur de poids alph[] et les jeux de facteurs F[1] à F[K] comme arguments. 22 La Figure 7 représente un exemple de mise en oeuvre de la fonction Use(). Dans une opération 700, un indice i est initialisé à 0, et les jeux de facteurs F, le nouveau programme TP, le processeur P et le nombre d'exécutions R sont reçus. 5 Dans une opération 705, K est déterminé comme le nombre de jeux de facteurs F. Une boucle est alors exécutée pour réaliser R exécutions du nouveau programme TP sur le processeur P, initialisé selon chacun des jeux de facteurs F. Pour cela, un indice k est calculé dans une opération 710 comme le reste de l'indice i 10 modulo K, et indique quel jeu de facteur va être utilisé. Ensuite, ou parallèlement, un indice j est défini dans une opération 715 comme la partie entière de l'indice i divisé par K. Cela indiquera le rang du temps d'exécution déterminé. Dans une opération 720, la fonction Rand() est exécutée avec le nouveau programme TP pour générer un vecteur de valeurs d'initialisation V, comme pour les opérations 350 et 460. Enfin, le processeur P 15 est initialisé dans une opération 725 avec le jeu de facteurs F[k] de manière identique aux opérations 340 et 450, et dans une opération 730 le programme TP est exécuté sur le processeur P initialisé avec le vecteur de valeurs d'initialisation V et le temps d'exécution correspondant est stocké dans le vecteur Mk[] à l'indice j. 20 Enfin, un test d'une opération 735 détermine si i est strictement inférieur à R. Si c'est le cas, alors il est incrémenté dans une opération 740. Sinon, alors le nouveau programme TP a été caractérisé et le modèle pire cas MTPO est calculé dans des opérations 745 à 775. Dans l'opération 745, l'indice j est réinitialisé à 0. Une double boucle est alors lancée 25 dans laquelle chaque contribution d'indice j tirée de chaque jeu de facteurs est regroupée pour former un temps d'exécution pire cas d'indice j pour le nouveau programme TP. Pour cela, l'indice k est initialisé à 0 dans l'opération 750, et tous les jeux de facteurs sont traversés pour l'indice j donné en ajoutant à MTPO[j] la valeur Mk[j] multipliée par alph[k] dans une opération 755. Ainsi, MTPO[j] reçoit progressivement les contributions 30 Mk[j] de chaque jeu de facteurs, un test dans l'opération 760 détermine si tous les jeux de facteurs ont été parcourus ou pas. Si ce n'est pas le cas, alors l'indice k est incrémenté dans l'opération 765 et la boucle en k reprend avec l'opération 755. Si c'est le cas, alors 23 un test dans l'opération 770 détermine si toutes les lignes de MTPO[] ont été remplies. Si ce n'est pas le cas, alors l'indice j est incrémenté dans l'opération 775 et la boucle en i reprend avec l'opération 750. Si c'est le cas, alors la fonction se termine en 799. 5 Ensuite, une fonction Extr() est exécutée dans une opération 610 sur le jeu de temps d'exécution pire cas MTPO. La fonction Extr() extrapole des données supplémentaires afin de compléter le jeu de temps d'exécution pire cas MTPO. Pour cela, elle applique les lois normales de chaque jeu de facteurs F[1] à F[K] en fenêtre glissante, comme cela a été fait avec l'opération 550, sauf que la variance sig(k) est fixée pour chaque jeu de 10 facteurs. Enfin, dans une opération 620, une fonction pWCET() calcul le temps d'exécution pire cas avec une probabilité correspondante avec le résultat de l'opération 630. Avantageusement, cette fonction peut être réalisée conformément aux enseignements de 15 la demande de brevet français FR 15 51828 ou de toute autre manière adaptée. L'invention permet donc d'obtenir des résultats permettant de déterminer les temps d'exécutions pire-cas d'un programme par un processeur à partir d'un nombre d'exécutions nettement inférieur à ce qui était connu précédemment (de l'ordre de 1000 20 exécutions contre plus de 100 000 avant). Cela permet donc de modifier avec plus de sûreté les programmes, puisque la question de la validation de ces derniers par les processeurs ne constitue plus un problème critique en termes de temps d'exécution. De plus, cela permet également de réaliser des bancs de comparaison de processeurs pour l'exécution d'un programme donné. En effet, il devient rapidement possible de comparer 25 les processeurs entre eux. Annexe A [10] p(M0) = EL, Km° imop(mk ImoT) 5 [20] p(M0) = P(Moi fi, fK) = =iakgk (mo I fk), mk-gk(molfk)-N(fk, 0-k2) [30] 1(6) = L log( Mi akgk (moilfki)) (z(j)(k, * (Mo(i) Mx (i))2)/ [40] sig(j)(02 = 1-J E Z (i)(k , 10 [50] z(j)(k, 0 = N(Mk (0, si9(j - 1)(102)(M0 (0) [60] alph(j)(k) =ri zu)(k, iy [70] Mk(T +1) = N(Mk(T +1 - 1), sig(j - 1)(02)(M0(T +1 - 1)) 15 [80] mo(T +1) = a 1P h (i) (k)mk (T +1) 24 T+ j-1 i= N (Mk(i), sig (j - 1)(102)(M0(0) REVENDICATIONS1. Dispositif informatique de caractérisation de temps d'exécution par un processeur (P), comprenant une mémoire (8) agencée pour recevoir des données de programme banc (B), des jeux de données de configuration de caractérisation (F[k]) et des jeux de données de cas d'exécution (S), et un constructeur (4) agencé, pour chaque jeu de données de cas d'exécution (S), pour déterminer un jeu de données de configuration pire-cas du processeur (F) et un jeu de valeurs d'initialisation (V) à partir d'un jeu de données de cas d'exécution (S), et déterminer un temps d'exécution de référence (MO[i]) en exécutant le programme banc (B) selon le jeu de données de cas d'exécution (S) par le processeur (P) configure avec le jeu de données de configuration (F) avec le jeu de valeurs d'initialisation (V), l'ensemble des temps d'exécution de référence formant un jeu de temps d'exécution de référence (MO), le constructeur (4) étant en outre agencé, pour chaque jeu de données de configuration de caractérisation (F[k]), pour déterminer un jeu (Mk) de temps d'exécution de caractérisation (Mk[j]), chaque jeu (Mk) de temps d'exécution de caractérisation (Mk[j]) comprenant un nombre de temps d'exécution de caractérisation (Mk[j]) égal au nombre (T) d'éléments du jeu de temps d'exécution de référence (MO) et chaque temps d'exécution de caractérisation (Mk[j]) étant déterminé en exécutant le programme banc (B) par le processeur (P) configure avec un jeu de données de configuration de caractérisation (F[k]) et avec un jeu de valeurs d'initialisation (V) représentatif du programme banc (B) et du processeur (P), le constructeur (4) étant en outre agencé pour déterminer un jeu de coefficients de caractérisation (alph[k]) en appliquant un algorithme de détermination du maximum de vraisemblance entre le jeu de temps d'exécution de référence (MO) et les jeux de temps d'exécution de caractérisation (M[k]), le dispositif étant agencé pour retourner le jeu de données de configuration de caractérisation (F) et le jeu de coefficients de caractérisation (alph[k]). 25 2. Dispositif selon la revendication 1, dans lequel le constructeur (4) est agencé pour calculer les coefficients de caractérisation (alph[k]) en déterminant, pour chaque jeu 26 (Mk) de temps d'exécution de caractérisation (Mk[j]), une pluralité d'estimateurs (z(0)(k)) dans lequel, pour chaque indice (j), la valeur est nulle ou vaut un si le temps d'exécution de caractérisation (Mk[j]) d'indice (j) est le plus proche du temps d'exécution de référence (MOU]) pour cet indice (j) parmi tous les temps d'exécution 5 de caractérisation (M1 [j]...MK[j]) pour cet indice (j), ainsi qu'une variance (sig(0)(k)) pour chaque jeu de temps d'exécution de caractérisation (Mk) à partir de la pluralité de vecteurs d'estimation (z(0)(k)) et des différences entre les temps d'exécution de référence (MO[i]) et les temps d'exécution de caractérisation (Mk[i]) d'indices identiques, 10 et ensuite en calculant itérativement à partir d'une fenêtre glissante comprenant pour chaque itération et pour chaque jeu (Mk) de temps d'exécution de caractérisation (Mk[j]) un nombre de temps d'exécutions égal au nombre (T) d'éléments du jeu de temps d'exécution de référence (MO) et qui sont les plus récents : - une pluralité de vecteurs d'estimation (z(k)(j+1)) pour l'itération courante, à partir 15 d'une pluralité de lois normales pour chaque jeu de temps d'exécution de caractérisation (Mk) qui ont en commun une variance tirée de celle de l'itération précédente (sig(k)(j-1)), et dont la moyenne est tirée à chaque fois d'un temps d'exécution de caractérisation (Mk[i]) sélectionné par la fenêtre glissante de l'itération courante, lesquelles loi normales sont évaluées chacune au temps 20 d'exécution du jeu de temps d'exécution de référence (MO[i]) qui correspond à celui à partir duquel est déterminé la moyenne, - une variance (sig(j)(k)) et un coefficient caractéristique (alph(j)(k)) pour chaque jeu de (Mk) de temps d'exécution de caractérisation (Mk[j]) à partir de l'estimateur (z(j)(k)) de l'itération courante, des différences entre les temps 25 d'exécution de référence (MO[i]) et les temps d'exécution de caractérisation (Mk[i]) d'indices identiques sélectionnés par la fenêtre glissante de l'itération courante, et le nombre (T) d'éléments du jeu de temps d'exécution de référence (MO), - un nouveau temps d'exécution de caractérisation (Mk[T+j]) pour chaque jeu de 30 temps d'exécution de caractérisation (Mk) en appliquant une loi normale dont la variance est celle calculée pour chaque jeu de temps d'exécution de caractérisation pour l'itération courante (sig(j)(k)) et la moyenne est le temps 27 d'exécution de caractérisation (Mk[T+j-1]) d'indice le plus élevé dans la fenêtre glissante, laquelle loi normale est évaluée au temps d'exécution du jeu de temps de référence (MO[T+j-1]) d'indice le plus élevé dans la fenêtre glissante, et un nouveau temps d'exécution de référence (MO[T+j]) à partir des nouveaux temps 5 d'exécution de caractérisation (Mk[T+j]) pour chaque jeu de temps d'exécution de caractérisation (Mk) et des coefficients caractéristiques (alph(j)(k)) pour chaque jeu de (Mk) de temps d'exécution de caractérisation (Mk[j]) pour l'itération courante, les itérations étant répétées jusqu'à ce qu'une condition portant sur le nombre 10 d'itérations ou sur une différence entre les coefficients de caractérisation (alph(j)(k)) pour chaque jeu de (Mk) de temps d'exécution de caractérisation d'itérations consécutives soit remplie, le jeu de coefficients de caractérisation (alph[k]) étant défini à partir des coefficients de caractérisation (alph(j)(k)) de la dernière itération. 15 3. Dispositif selon la revendication 2, dans lequel le constructeur (4) est agencé pour calculer les estimateurs (z(j)(k)) selon la formule suivante : z(j)(k, i) = N(Mk(i),sig(j - 1)(k)2)(M0 (0) ET:il 1 N(Mk (i), sig(J - 1)(02)(/0(0) où chaque z(j)(k,i) est un élément d'indice i dans l'estimateur z(j)(k), N(m,$) désigne 20 la loi normale de moyenne m et de variance s, Mk(i) désigne le temps d'exécution d'indice i dans le k-ième jeu de temps d'exécution de caractérisation (Mk), sig(j-1)(k) est la variance pour le k-ième jeu de temps d'exécution de caractérisation (Mk) et Mo(i) désigne le temps d'exécution d'indice i dans le jeu de temps d'exécution de référence. 25 4. Dispositif selon la revendication 2 ou 3, dans lequel le constructeur (4) est agencé pour calculer les variances (sig(j)(k)) selon la formule suivante : sig (j) (k) 2 = 1-j ET:Ej. (z(j)(k,* (MO(0 Mk(0)2) Lii=j vT+j-1 z(j)(k, où z(j)(k,i) est l'élément d'indice i dans l'estimateur z(j)(k) pour le k-ième jeu de 30 temps d'exécution de caractérisation, Mk(i) désigne le temps d'exécution d'indice i 28 dans le k-ième jeu de temps d'exécution de caractérisation (Mk), et Mo(i) désigne le temps d'exécution d'indice i dans le jeu de temps d'exécution de référence. 5. Dispositif selon l'une des revendications 2 à 4, dans lequel le constructeur (4) est 5 agencé pour calculer les coefficients de caractérisation (alph(j)(k)) selon la formule suivante : alph(j)(k) / z(i)(1c, j)IT où z(j)(k,i) est l'élément d'indice i dans l'estimateur z(j)(k) pour le k-ième jeu de temps d'exécution de caractérisation et T est le nombre d'éléments du jeu de temps 10 d'exécution de référence MO. 6. Dispositif selon l'une des revendications 2 à 5, dans lequel le constructeur (4) est agencé pour calculer les nouveaux temps d'exécution de caractérisation (Mk(T+j)) selon la formule suivante : 15 Mx (7' + /) = N(Mic (7' + - 1), si9(/ - 1) (k)2) (Ma + - 1)) où N(m,$) désigne la loi normale de moyenne m et de variance s, Mk(i) désigne le temps d'exécution d'indice i dans le k-ième jeu de temps d'exécution de caractérisation (Mk), et sig(j-1)(k) est la variance pour le k-ième jeu de temps d'exécution de caractérisation (Mk). 20 7. Dispositif selon l'une des revendications 2 à 6, dans lequel le constructeur (4) est agencé pour calculer les nouveaux temps d'exécution de référence (MO[T+j]) selon la formule suivante : Mo(T + =alph(j)(k)Mk(T +1) k=1 25 où Mo(i) désigne le temps d'exécution d'indice i dans le jeu de temps d'exécution de référence, Mk(i) désigne le temps d'exécution d'indice i dans le k-ième jeu de temps d'exécution de caractérisation (Mk), et alph(j)(k) est le coefficient de caractérisation associé au k-ième jeu de temps d'exécution de caractérisation (Mk) dans la j-ième itération. 30 29 8. Dispositif de calcul d'une base de temps d'exécution pire-cas d'un programme par un processeur (P) comprenant une mémoire (8) agencée pour recevoir des données de programme (TP), des jeux de données de configuration de caractérisation (F[k]) et un jeu de coefficients de caractérisation (alph[k]) obtenu par l'exécution du dispositif 5 selon l'une des revendications précédentes, et un modélisateur (6) agencé pour : - déterminer une pluralité de jeux de valeurs d'initialisation (V) pour chaque jeu de données de configuration de caractérisation (F[k]), le nombre (Ent(R/K)) de jeux de valeurs d'initialisation (V) étant le même pour tous les jeu de données de 10 configuration de caractérisation (F[k]), - déterminer une pluralité de temps d'exécutions (Mk[j]) en exécutant le programme (TP) par le processeur (P) configure avec chaque jeu de données de configuration de caractérisation (F[k]) et avec à chaque fois la pluralité de jeux de valeurs d'initialisation (V) correspondante, et 15 - ajouter dans une base de temps d'exécution pire-cas une pluralité de temps d'exécution pire-cas (MTP0[j+1]), qui sont chacun égaux à la somme pour chaque les jeux de données de configuration de caractérisation (F[k]) du produit d'un des temps d'exécutions (Mk[j]) par le coefficient de caractérisation (alph[k]) associé au jeu de données de configuration de caractérisation (F[k]) qui a permis d'obtenir 20 ce temps d'exécution (Mk[j]), de sorte que la base de temps d'exécution pire-cas comprend un nombre de temps d'exécution (MTPO[j+1]) égale au nombre de jeux de valeurs d'initialisation (V) pour chaque jeu de données de configuration de caractérisation (F[k]). 25 9. Procédé de caractérisation de temps d'exécution par un processeur (P), comprenant les opérations suivantes : a) recevoir des données de programme banc (B), des jeux de données de configuration de caractérisation (F[k]) et des jeux de données de cas d'exécution (S), 30 b) pour chaque jeu de données de cas d'exécution (S), déterminer un jeu de données de configuration pire-cas du processeur (F) et un jeu de valeurs d'initialisation (V) à partir d'un jeu de données de cas d'exécution (S), et déterminer un temps 30 d'exécution de référence (MO[i]) en exécutant le programme banc (B) selon le jeu de données de cas d'exécution (S) par le processeur (P) configuré avec le jeu de données de configuration (F) avec le jeu de valeurs d'initialisation (V), l'ensemble des temps d'exécution de référence formant un jeu de temps d'exécution de 5 référence (MO), c) pour chaque jeu de données de configuration de caractérisation (F[k]), déterminer un jeu (Mk) de temps d'exécution de caractérisation (Mk[j]), chaque jeu (Mk) de temps d'exécution de caractérisation (Mk[j]) comprenant un nombre de temps d'exécution de caractérisation (Mk[j]) égal au nombre (T) d'éléments du jeu de 10 temps d'exécution de référence (MO) et chaque temps d'exécution de caractérisation (Mk[j]) étant déterminé en exécutant le programme banc (B) par le processeur (P) configuré avec un jeu de données de configuration de caractérisation (F[k]) et avec un jeu de valeurs d'initialisation (V) représentatif du programme banc (B) et du processeur (P), 15 d) déterminer un jeu de coefficients de caractérisation (alph[k]) en appliquant un algorithme de détermination du maximum de vraisemblance entre le jeu de temps d'exécution de référence (MO) et les jeux de temps d'exécution de caractérisation (M[k]), et e) retourner le jeu de données de configuration de caractérisation (F) et le jeu de 20 coefficients de caractérisation (alph[k]). 10. Procédé de calcul d'une base de temps d'exécution pire- d'un programme par un processeur (P) comprenant les opérations suivantes : a) recevoir des données de programme (TP), des jeux de données de configuration 25 de caractérisation (F[k]) et un jeu de coefficients de caractérisation (alph[k]) obtenu par l'exécution du dispositif selon l'une des revendications 1 à 7 ou le procédé selon la revendication 9, b) déterminer une pluralité de jeux de valeurs d'initialisation (V) pour chaque jeu de données de configuration de caractérisation (F[k]), le nombre (Ent(R/K)) de jeux 30 de valeurs d'initialisation (V) étant le même pour tous les jeu de données de configuration de caractérisation (F[k]), 31 c) déterminer une pluralité de temps d'exécutions (Mk[j]) en exécutant le programme (TP) par le processeur (P) configure avec chaque jeu de données de configuration de caractérisation (F[k]) et avec à chaque fois la pluralité de jeux de valeurs d'initialisation (V) correspondante, et 5 d) ajouter dans une base de temps d'exécution pire-cas une pluralité de temps d'exécution pire-cas (MTPO[j+1]), qui sont chacun égaux à la somme pour chaque les jeux de données de configuration de caractérisation (F[k]) du produit d'un des temps d'exécutions (Mk[j]) par le coefficient de caractérisation (alph[k]) associé au jeu de données de configuration de caractérisation (F[k]) qui a permis d'obtenir 10 ce temps d'exécution (Mk[j]), de sorte que la base de temps d'exécution pire-cas comprend un nombre de temps d'exécution (MTPO[j+1]) égale au nombre de jeux de valeurs d'initialisation (V) pour chaque jeu de données de configuration de caractérisation (F [k]).