DESCRIPTION

DOMAINE TECHNIQUE

Le domaine de l'invention est celui des systèmes informatiques temps-réel pour lesquels le temps d'exécution des tâches, et notamment le temps d'exécution dans le pire des cas (dit WCET pour « Worst Case Execution Time »), doit être connu pour en assurer la validation et en garantir la sûreté. L'invention vise plus particulièrement à améliorer la précision de l'estimation du WCET d'un programme en rendant possible la fourniture d'un WCET garanti sans être trop pessimiste.

ÉTAT DE LA TECHNIQUE ANTÉRIEURE

Les systèmes temps-réel doivent réagir de manière fiable, ce qui implique à la fois d'être certain du résultat produit par leurs programmes mais aussi de connaître le temps qu'ils prennent pour s'exécuter. Les temps d'exécution pire-cas sont ainsi des données fondamentales pour la validation et la sûreté de tels systèmes temps-réel, et encore plus dans le contexte des systèmes temps-réels autonomes (robotique, voiture autonome, GPS) pour lesquels la sûreté de fonctionnement est primordiale.

Cependant calculer un WCET, à la fois garanti (majorant strict) et pas trop pessimiste afin de réduire les coûts et la complexité de tels systèmes temps-réels, est un problème difficile à résoudre du fait de l'impact temporel qu'ont les unités matérielles qui exécutent les programmes et du nombre de chemins d'exécution possibles des programmes.

La technique de transformation de code appelé « single-path » (ou chemin unique en français) permet de rendre prédictible le temps d'exécution d'un programme et donc de fournir un WCET fiable. Selon cette technique, les différentes séquences de code qui doivent sélectivement être exécutées selon le résultat d'un branchement conditionnel venant examiner des données d'entrée (on peut ainsi également parler de séquences conditionnellement concurrentes ou encore de séquences d'une alternative car constituant les choix possibles d'une alternative) sont amenées en un code séquentiel, en s'appuyant sur les capacités de certains processeurs à associer des prédicats à leurs instructions assembleur pour conserver la sémantique d'origine du programme.

L'application de cette technique de transformation « single-path » permet donc de réduire la combinatoire des chemins d'exécutions possibles d'un programme en aboutissant à l'obtention d'un seul chemin d'exécution. La mesure d'un unique temps d'exécution du programme ainsi transformé est donc suffisante pour fournir le WCET du programme. La démarche par mesure pour déterminer le WCET s'en trouve simplifiée car le problème du taux de couverture d'un programme atteint par une campagne de mesures est éliminé.

L'utilisation de cette technique de transformation de code « single-path » présente toutefois l'inconvénient d'accroître le temps d'exécution d'un programme puisque les séquences conditionnellement concurrentes d'une alternative sont exécutées de manière séquentielle.

EXPOSÉ DE L'INVENTION

L'invention a pour objectif de proposer une technique permettant d'éliminer cet accroissement du temps d'exécution WCET. Elle propose à cet effet un procédé d'exécution d'un programme par un système informatique disposant de ressources de calcul capables d'exécuter des séquences d'instructions, comprenant une sélection conditionnelle d'une séquence d'instructions parmi une séquence dite satisfaite et au moins une séquence dite non-satisfaite. Ce procédé comprend les étapes suivantes :

- sur exécution d'une instruction de répartition de séquences par une première ressource de calcul du système informatique, répartition de l'exécution de la séquence satisfaite et de l'au moins une séquence non-satisfaite entre la première ressource de calcul et au moins une deuxième ressource de calcul du système informatique ; - exécution en parallèle de la séquence satisfaite et de l'au moins une séquence non-satisfaite chacune par une ressource de calcul parmi la première et l'au moins une deuxième ressource de calcul ;

- une fois la séquence satisfaite et l'au moins une séquence non-satisfaite intégralement exécutées, poursuite de l'exécution du programme par une ressource de calcul parmi la première et l'au moins une deuxième ressource de calcul.

Ainsi, lorsqu'un programme exécuté sur une ressource de calcul A atteint une instruction de répartition de séquences d'instructions, l'une des séquences satisfaite et non-satisfaite est exécutée sur une autre ressource de calcul B tandis que l'autre des séquences satisfaite et non-satisfaite est exécutée sur la ressource de calcul A. Cette exécution en parallèle permet de réduire le WCET du programme. Le procédé selon l'invention permet donc de dégager du temps processeur supplémentaire pour, soit exécuter des programmes supplémentaires sur une même architecture matérielle, soit permettre de sélectionner une architecture matérielle moins performante mais plus économique pour exécuter un ensemble de programmes donné. Ce procédé permet donc d'optimiser l'utilisation des ressources de calcul lors de la conception d'un système temps réel nécessitant la détermination de WCET.

Certains aspects préférés mais non limitatifs de ce procédé sont les suivants :

- la répartition de l'exécution de la séquence satisfaite et de la séquence non- satisfaite consiste à faire exécuter la séquence non-satisfaite par la première ressource de calcul et la séquence satisfaite par la deuxième ressource de calcul ;

- lors de l'exécution en parallèle de la séquence satisfaite et de la séquence non- satisfaite, une donnée écrite en mémoire par l'une de la première et de la deuxième ressource de calcul fait l'objet d'une restriction de visibilité pour n'être visible que par celle de la première et de la deuxième ressource de calcul qui a réalisé l'écriture de la donnée en mémoire ;

- il comprend, lors de la poursuite de l'exécution du programme, la terminaison de la restriction de visibilité des données écrites en mémoire par la ressource de calcul parmi la première et la deuxième ressource de calcul qui a exécuté, lors de l'exécution en parallèle de la séquence satisfaite et de la séquence non-satisfaite, la séquence d'instructions sélectionnée ;

- il comprend, lors de la poursuite de l'exécution du programme, l'invalidation des données écrites en mémoire par la ressource de calcul parmi la première et la deuxième ressource de calcul qui n'a pas exécuté, lors de l'exécution en parallèle de la séquence satisfaite et de la séquence non-satisfaite, la séquence d'instructions sélectionnée ;

- chacune des première et deuxième ressources de calcul notifie à l'autre des première et la deuxième ressources de calcul de la terminaison de l'exécution de celle des séquences satisfaite et non-satisfaite qu'elle exécute ;

- la poursuite de l'exécution du programme est réalisée par la ressource de calcul ayant exécuté la séquence d'instructions sélectionnée par la sélection conditionnelle lors de l'exécution en parallèle de la séquence satisfaite et de la séquence non- satisfaite ;

- lorsque qu'un nombre maximal autorisé d'exécutions en parallèle simultanées de séquences est atteint, la répartition de l'exécution de la séquence satisfaite et de l'au moins une séquence non-satisfaite entre la première ressource de calcul et l'au moins une deuxième ressource de calcul du système informatique n'est pas réalisée et la séquence sélectionnée par la sélection conditionnelle est exécutée par la première ressource de calcul ;

- lorsque que le nombre maximal autorisé d'exécutions en parallèle simultanées de séquences est atteint, les séquences sélectionnée et non sélectionnée par la sélection conditionnelle sont exécutées l'une après l'autre par la première ressource de calcul ;

- il comprend en outre une étape de mesure de la durée d'exécution du programme et une étape de détermination d'un temps d'exécution dans le pire des cas du programme. BRÈVE DESCRIPTION DES DESSINS

D'autres aspects, buts, avantages et caractéristiques de l'invention apparaîtront mieux à la lecture de la description détaillée suivante de formes de réalisation préférées de celle-ci, donnée à titre d'exemple non limitatif, et faite en référence aux dessins annexés sur lesquels :

la figure 1 illustre une structure de branchement conditionnelle standard du type « Test si sinon » ;

la figure 2 illustre les étapes du procédé selon l'invention de répartition des séquences d'une alternative et de leur exécution en parallèle chacune par une ressource de calcul différente ;

la figure 3 illustre les étapes du procédé selon l'invention de terminaison de l'exécution en parallèle des séquences d'une alternative et de poursuite de l'exécution du programme par une ressource de calcul.

EXPOSÉ DÉTAILLÉ DE MODES DE RÉALISATION PARTICULIERS

L'invention porte sur un procédé d'exécution d'un programme par un système informatique, notamment un système temps-réel, disposant de ressources de calcul capables d'exécuter des séquences d'instructions. Le système informatique est par exemple un processeur de calcul, mono-cœur ou multi-cœur. Le programme peut notamment exécuter des tâches, par exemple des tâches temps réel, programmées selon la technique de programmation « single-path », le procédé selon l'invention permettant d'accélérer l'exécution de ce programme à chemin unique.

On a représenté sur la figure 1 le traitement d'une structure de branchement conditionnelle standard présente au sein d'un programme P exécuté par une ressource de calcul A. Ce programme est constitué de trois séquences d'instructions li, l ₂ et l ₃ . La séquence d'instructions li se termine par une instruction de branchement conditionnelle standard dont l'exécution provoque l'évaluation « CS ? » de la satisfaction d'une condition de branchement et la sélection, en fonction du résultat de cette évaluation, d'une séquence d'instructions à exécuter parmi les deux séquences possibles l ₂ et I ₃ . Ces deux séquences possibles sont conditionnellement concurrentes (une seule est exécutée, sélectionnée en fonction du résultat de l'évaluation de la satisfaction de la condition) et sont dénommées par la suite séquence satisfaite l ₂ (il s'agit de la séquence qui est exécutée lorsque la condition est satisfaite, « O ») et séquence non-satisfaite l ₃ (il s'agit de la séquence qui est exécutée lorsque la condition est non-satisfaite, « N »).

L'invention propose un nouveau type d'instruction dite de répartition de séquences conditionnellement concurrentes (ou plus simplement instruction de répartition dans ce qui suit) qui, lorsqu'elle est exécutée, réalise, du fait de la présence d'une sélection conditionnelle d'une des séquences, une répartition de l'exécution de ces différentes séquences en parallèle sur différentes ressources de calcul.

La sélection conditionnelle peut être une sélection du type si-alors-sinon permettant de venir sélectionner l'une de deux séquences possibles d'une alternative, une séquence satisfaite et une séquence non-satisfaite. L'invention s'étend à une sélection conditionnelle de type aiguillage (ou « switch ») permettant de venir sélectionner une séquence parmi une pluralité de séquences possibles (typiquement au moins trois séquences possibles), une séquence satisfaite et au moins une séquence non- satisfaite. On prend dans ce qui suit l'exemple d'une sélection de type si-alors-sinon, étant entendu qu'une sélection de type aiguillage peut aisément se ramener à cet exemple en venant la remplacer par une série de sélections de type si-alors-sinon en cascade.

Comme représenté sur la figure 2, le programme P est initialement exécuté par une première ressource de calcul A et l'exécution de la séquence d'instructions li comprend une sélection conditionnelle d'une séquence d'instructions parmi une séquence satisfaite et au moins une séquence non-satisfaite. Cette sélection conditionnelle peut comprendre l'évaluation de la satisfaction d'une condition de branchement et la sélection, en fonction du résultat de cette évaluation, d'une séquence d'instructions à exécuter parmi deux séquences possibles.

La séquence d'instructions li se termine par une instruction de répartition qui, lorsqu'elle est exécutée par la ressource de calcul A, entraîne la répartition de l'exécution de la séquence satisfaite et de la séquence non-satisfaite entre la première ressource de calcul A et une deuxième ressource de calcul B du système informatique différente de la ressource A.

Dans un mode de réalisation possible, la sélection conditionnelle résulte de l'exécution, préalablement à l'instruction de répartition, d'une instruction de test de la satisfaction de la condition. Le résultat de l'exécution de l'instruction de test est stocké dans une partie de registre d'état de la micro-architecture et l'instruction de répartition vient exploiter cette information pour déterminer l'adresse à laquelle le programme se poursuit, c'est-à-dire l'adresse de la séquence sélectionnée par la séquence conditionnelle.

Dans un autre mode de réalisation possible, la sélection conditionnelle résulte de l'exécution de l'instruction de répartition elle-même. L'instruction de répartition prend en paramètres les registres sur lesquels la condition doit être évaluée et le résultat de cette évaluation est exploité directement lors de l'exécution de l'instruction pour déterminer l'adresse à laquelle le programme se poursuit, i.e. l'adresse de la séquence sélectionnée par la séquence conditionnelle.

Dans chacun de ces modes de réalisation, l'instruction de répartition est une instruction de branchement enrichie pour désigner la deuxième ressource de calcul B. L'instruction de branchement peut ainsi prendre en argument la deuxième ressource de calcul B, et dans ce cas, c'est lors de la construction du binaire que cette information doit être produite. Alternativement, l'instruction de branchement peut prendre en argument un registre spécifique (registre ressources_utilisables dans l'exemple ci-après) pour identifier la deuxième ressource de calcul B parmi un ensemble de ressources utilisables.

Comme représenté en figure 2, la répartition peut consister à faire exécuter la séquence non-satisfaite l ₃ par la première ressource de calcul A et la séquence satisfaite l ₂ par la deuxième ressource de calcul B. Le choix de déporter la séquence satisfaite permet, sur la première ressource de calcul A exécutant la séquence non-satisfaite, de continuer à précharger les instructions du programme d'une manière séquentielle et ainsi d'éviter l'introduction de tout aléas dans l'exécution du programme au niveau du pipeline d'exécution d'instructions d'une micro-architecture. La répartition comprend une demande de déport RQ. de l'exécution de l'une des séquences satisfaite et non-satisfaite, cette demande étant formulée par la première ressource de calcul A à destination de la deuxième ressource de calcul B. Lorsque cette demande de déport est acceptée ACK par la deuxième ressource de calcul B, le programme X qui était en train d'être exécuté par la deuxième ressource de calcul B est suspendu. Cette suspension est considérée comme une interruption dans le fonctionnement de la ressource de calcul B, et le contexte d'exécution du programme X est alors sauvegardé. Un transfert TS, de la ressource A à la ressource B, de l'état nécessaire pour entamer l'exécution de celle des séquences satisfaite et non-satisfaite que le ressource B doit exécuter est réalisé. Ce transfert concerne les valeurs des registres manipulés par le programme P avant l'instruction de répartition, la structure de pile courante du programme P ainsi que l'identification de la ressource de calcul A.

La séquence satisfaite l ₂ et la séquence non-satisfaite l ₃ sont alors exécutées en parallèle, chacune par une ressource de calcul parmi la première ressource A et la deuxième ressource B.

Une fois ces deux séquences l ₂ et I ₃ intégralement exécutées, l'exécution du programme P se poursuit sur une ressource de calcul parmi la première ressource A et la deuxième ressource B.

Plus particulièrement, comme représenté sur la figure 3, le programme P comprend une quatrième séquence d'instructions l ₄ qui doit s'exécuter une fois que l'exécution en parallèle des séquences l ₂ et U se termine.

L'invention propose que les séquences d'instructions U et I ₃ se terminent chacune par une instruction de terminaison de parallélisme. Dans l'exemple représenté, la séquence d'instructions I ₃ exécutée par la ressource de calcul A est la première à se terminer et l'exécution de l'instruction de terminaison de parallélisme fait que la ressource de calcul A notifie TR la ressource de calcul B de la terminaison de la séquence I ₃ . Lorsque la séquence d'instructions U exécutée par la ressource de calcul B se termine, l'exécution de l'instruction de terminaison de parallélisme fait que la ressource de calcul B notifie la ressource de calcul A de cette terminaison. Dans cet exemple, la ressource B a exécuté la séquence l ₂ qui s'avère être la séquence sélectionnée par la sélection conditionnelle (la condition était en l'occurrence satisfaite). Dans cet exemple, l'exécution du programme P est poursuivie sur la ressource de calcul B en exécutant les instructions du bloc d'instructions l ₄ , après que la ressource B ait demandé TE à la ressource A le transfert NE de l'état de registres de notification pour la mise à jour de ceux-ci localement.

La ressource de calcul A peut alors reprendre alors l'exécution du programme X qui s'exécutait sur la ressource de calcul B avant l'exécution en parallèle des séquences satisfaite et non-satisfaite l ₂ et l ₃ , en venant restaurer le contexte d'exécution de ce programme depuis sa sauvegarde.

Ainsi, chacune des ressources de calcul A et B fait appel à cette instruction de terminaison de parallélisme afin, tout d'abord, d'attendre la terminaison de l'autre séquence pour ainsi conserver la propriété de prédictibilité temporelle d'un programme, puis, ensuite, de déterminer à quelle instruction l'exécution du programme se poursuit. Par ailleurs, cette instruction de terminaison de parallélisme a pour effet de sélectionner la ressource de calcul sur laquelle l'exécution du programme va se poursuivre ainsi que de conserver uniquement les données produites par la séquence sélectionnée.

Les instructions de répartition et de terminaison proposées par l'invention peuvent être générées de manière classique par un compilateur lors de la construction d'un binaire du programme traité.

On relèvera qu'il est nécessaire de réaliser l'ensemble des accès mémoires des séquences l ₂ , 13 de l'alternative pour garantir la prédictibilité temporelle de l'exécution du programme. En effet, la connaissance de la séquence sélectionnée par la sélection conditionnelle ne peut pas être utilisée pour éliminer les accès mémoires de la séquence non-sélectionnée car cela engendrait des variations dans le temps d'exécution des alternatives.

On a vu que l'exécution du programme P peut se poursuivre sur l'une ou l'autre des ressources de calcul A et B utilisées dans l'exécution en parallèle des séquences satisfaite et non-satisfaite. Une première stratégie peut consister à poursuivre l'exécution du programme P sur la ressource de calcul qui a exécuté l'alternative non-satisfaite, ce qui peut induire un transfert de données depuis l'autre ressource de calcul si la séquence sélectionnée est la séquence satisfaite. Comme représenté sur la figure 3, une autre stratégie peut consister à poursuivre l'exécution du programme P sur la ressource qui a exécutée la séquence sélectionnée afin d'éviter ce transfert de données.

On notera que si un programme (comme le programme X sur les figures 2 et 3) a été interrompu pour permettre l'exécution en parallèle des séquences satisfaite et non satisfaite, le contexte d'exécution de ce programme doit être restauré afin de permettre la poursuite de son exécution. Si la poursuite de l'exécution de ce programme se poursuit sur la même ressource ce calcul, cette restauration peut être réalisée dès lors que la séquence, parmi les séquences satisfaite et non satisfaite, exécutée par cette ressource de calcule se termine. Cette restauration peut également être réalisée à la terminaison du parallélisme, voire ultérieurement. Et comme on l'a vu précédemment, cette restauration peut éventuellement être réalisée sur l'autre ressource de calcul impliquée dans l'exécution en parallèle.

Lors de l'exécution en parallèle des séquences satisfaite et non-satisfaite l ₂ et l ₃ , un fonctionnement spécifique de la hiérarchie mémoire stockant des données manipulées par un programme est nécessaire. En effet, une même donnée peut être manipulée par les deux séquences l ₂ et I3. Mais si des accès en lecture ne posent pas de problème, des accès en écriture soulèvent le problème de la cohérence de ces données. Ainsi, les accès en écriture depuis une ressource de calcul exécutant l'une des séquences de l'alternative ne doivent pas être visibles depuis la ressource de calcul exécutant l'autre séquence de l'alternative.

Pour ce faire, chaque accès en écriture crée une nouvelle copie d'une donnée et un identifiant de la ressource de calcul propriétaire de cette donnée est alors ajouté aux méta-informations associées à la donnée. Cet identifiant est ainsi utilisé pour déterminer si une ressource de calcul peut accéder à cette donnée. Ce mécanisme de restriction de la visibilité des données manipulées par une ressource de calcul permet de privatiser un niveau de la hiérarchie mémoire partagé entre les ressources de calcul.

Par ailleurs, outre le besoin d'isoler les copies d'une donnée manipulée par les différentes ressources exécutant en parallèle les différentes séquences d'une alternative, cette donnée ne doit pas être rendue visible à d'autres programmes ou, via des Entrées/Sorties (E/S), à l'environnement externe du système exécutant les programmes. Une donnée ayant parmi ses méta-informations un identifiant d'une ressource de calcul utilisée pour mettre en œuvre l'exécution en parallèle d'une séquence d'une alternative ne peut alors être mise à jour dans une mémoire pour cet objectif ou vers une E/S. Cette restriction contraint le développeur de programmes à implémenter les communications vers d'autres programmes ou vers des E/S en-dehors de l'exécution en parallèle de séquences d'une alternative.

D'une manière optionnelle, afin de limiter l'intrusion de ce mécanisme de restriction de la visibilité des données dans le fonctionnement standard d'une mémoire centrale, par exemple de type DRAM, l'utilisation de ce mécanisme se limite à la hiérarchie mémoire entre les ressources de calcul et la mémoire centrale.

Ainsi selon le procédé de l'invention, lors de l'exécution en parallèle de la séquence satisfaite l ₂ et de la séquence non-satisfaite l ₃ , une donnée écrite en mémoire par l'une de la première A et de la deuxième B ressource de calcul fait l'objet d'une restriction de visibilité pour n'être visible que par celle de la première et de la deuxième ressource de calcul qui a réalisé l'écriture de la donnée en mémoire.

Par ailleurs, lors de la poursuite de l'exécution du programme après la terminaison de l'exécution en parallèle des séquences de l'alternative, le procédé comprend la terminaison de la restriction de visibilité des données écrites en mémoire par la ressource de calcul parmi la première et la deuxième ressource de calcul qui a exécuté, lors de l'exécution en parallèle de la séquence satisfaite et de la séquence non- satisfaite, la séquence d'instructions sélectionnée. Ces données, celles de la séquence l ₂ exécutée par la ressource B dans l'exemple de la figure 3, sont ainsi rendues visibles à l'ensemble des ressources de calcul.

Et a contrario, le procédé comprend lors de la poursuite de l'exécution du programme, l'invalidation des données écrites en mémoire par la ressource de calcul parmi la première et la deuxième ressource de calcul qui n'a pas exécuté, lors de l'exécution en parallèle de la séquence satisfaite et de la séquence non-satisfaite, la séquence d'instructions sélectionnée. Dans l'exemple de la figure 3, les données de la séquence I3 exécutée par la ressource A sont ainsi rendues invalides. Il est possible de spécifier pour un programme donné un nombre maximal autorisé d'exécutions en parallèle simultanées de séquences d'une alternative. Ce nombre maximal autorisé ne peut être supérieur au nombre de ressource de calcul de l'architecture matérielle considérée.

Lorsque ce nombre maximal autorisé est atteint, les séquences d'une alternative ne peuvent plus faire l'objet d'une exécution en parallèle et des instructions de branchement conditionnel standards (cf. figure 1) doivent être utilisées. Si cette utilisation est faite lors de la génération du code assembleur d'un programme par un compilateur, alors le binaire généré du programme est dépendant de ce nombre maximal autorisé. Si cette utilisation est faite à l'exécution par le matériel par substitution aux instructions de répartition de séquences d'une alternative, alors le binaire généré est indépendant du degré de parallélisme d'alternative maximal.

Si ce nombre maximal autorisé est trop faible pour couvrir toutes les alternatives du programme, celui-ci est alors constitué de plusieurs chemins d'exécution. Un compromis est donc à trouver entre l'utilisation des ressources de calcul et la complexité d'une analyse WCET qui est en partie liée au nombre de chemins d'un programme.

Dans une variante de réalisation, lorsque le programme atteint son nombre maximal autorisé d'exécutions en parallèle simultanées de séquences d'une alternative, la technique de transformation de code « single-path » peut être appliquée aux alternatives ne pouvant faire l'objet de la répartition selon l'invention afin de maintenir la construction d'un unique chemin d'exécution. Dans un tel cas de figures, les séquences sélectionnée et non sélectionnée par la sélection conditionnelle sont exécutées l'une après l'autre par la première ressource de calcul.

Le procédé selon l'invention permet de ne pas solliciter les unités classiques de prédiction de branchement puisque par construction les deux séquences d'une alternative sont exécutées. Aucune transmission arrière pour la mise à jour du compteur d'instruction à l'étape de lecture des instructions au sein d'une microarchitecture n'est donc nécessaire. Toutefois, une exploration des choix de la ressource de calcul à utiliser pour poursuivre l'exécution du programme après terminaison de l'exécution en parallèle de séquences d'une alternative peut être réalisée pour, par exemple, réduire le WCET du programme.

On décrit dans ce qui suit une implémentation possible du procédé selon l'invention.

Une table est associée à chaque ressource de calcul et chaque entrée de la table contient un identifiant de programme actuel P, un nombre maximal autorisé d'exécutions en parallèle simultanées EPSmax, un compteur EPSact d'exécutions en parallèle simultanées (initialisé à 0) pour ce programme P et deux ensembles de taille égale au nombre de ressources de calcul de l'architecture matérielle.

Le premier ensemble, noté ressources_utilisables, indique les ressources de calcul utilisables pour une exécution en parallèle des séquences des alternatives du programme P, tandis que le second ensemble, noté ressources_utilisees, indique les ressources de calcul actuellement utilisées par ce même programme P. L'initialisation de ressources_utilisables est du ressort d'une phase d'élaboration du binaire, tandis que ressources_utilisees contient initialement la ressource de calcul utilisée pour démarrer l'exécution du programme P. Une exécution sans parallélisme se traduit par une taille d'un élément pour l'ensemble ressources_utilisees, alors qu'une exécution avec parallélisme nécessite que la taille de ce même ensemble soit supérieur à 1.

Deux ensembles de registres de notification permettent par ailleurs d'indiquer, par ressource de calcul, 1) le premier échec d'une demande de déport d'une séquence d'une alternative, la valeur du compteur d'instruction lors de l'échec de cette demande (initialement à 0) et l'occurrence d'échecs ultérieurs, appelé champ de notification d'échecs supplémentaires, par exemple un bit, (initialement invalidé) et 2) la première tentative de dépassement du nombre maximal autorisé EPSmax, la valeur du compteur d'instruction lors de cette tentative de dépassement (initialement à 0) et l'occurrence de tentatives de dépassement ultérieures, appelé champ de notification de tentative de dépassement supplémentaire (initialement invalidé). D'une manière optionnelle, un mécanisme d'interruption peut être utilisé afin de notifier une ressource de calcul de l'occurrence de tels évènements. L'ensemble de ces informations peuvent faire partie du contexte d'exécution du programme qu'il faut sauvegarder/restaurer à chaque préemption/reprise d'exécution du programme.

A chaque unité élémentaire de stockage de données dans une hiérarchie mémoire, mémoire centrale exclue, les méta-informations sont complétées par une information indiquant si la donnée est globalement visible par l'ensemble des ressources (noté globale, par défaut valide), et une identification de la ressource de calcul propriétaire de la donnée (noté propriétaire, par défaut invalidé). Ces deux éléments permettent de mettre en œuvre le mécanisme de restriction de la visibilité des données manipulées durant une exécution en parallèle des séquences d'une alternative.

Les étapes du procédé sont alors les suivantes pour le traitement d'une instruction de répartition de séquences d'une alternative.

Etape A-l

Lorsqu'une instruction de répartition de séquences d'une alternative d'un programme est décodée par une première ressource de calcul A, la valeur du compteur EPSact est comparée au nombre maximal autorisé EPSmax.

Si ces valeurs sont identiques, l'instruction de répartition est traitée comme instruction de branchement conditionnelle classique et le présent procédé n'est pas mis en œuvre. L'ensemble des registres de notification de tentative de dépassement du nombre maximal autorisé sont en revanche mis à jour avec, s'il s'agit de la première tentative de dépassement (identifiable par une valeur de compteur d'instruction à 0), l'adresse de l'instruction de répartition. S'il ne s'agit pas d'une première tentative de dépassement, seul le champ de notification de tentative de dépassement supplémentaire est validé. Le procédé attend alors une nouvelle instruction de répartition pour reprendre l'étape A-l.

Si ces valeurs ne sont pas identiques, une ressource de calcul B utilisable par ce programme mais non encore utilisée est identifiée par différence entre les ensembles ressources_utilisables et ressources_utilisees. Le procédé se poursuit alors à l'étape A-2.

Si aucune ressource de calcul n'est identifiée, le procédé se poursuit à l'étape A-

5. Etape A-2

La ressource de calcul A notifie une demande de déport de l'exécution de l'une des séquences parmi la séquence satisfaite et la séquence non-satisfaite à la ressource de calcul B et attend une réponse de cette dernière. Une demande de déport de l'exécution consiste en un couple comprenant l'identifiant du programme P et l'identifiant de la ressource de calcul A.

Lorsque la demande de déport est reçue par la ressource de calcul B, l'identifiant de la ressource de calcul A émettrice de la demande est vérifié comme faisant partie des ressources de calcul pouvant émettre une telle demande, à savoir si la ressource de calcul A appartient à l'ensemble ressources_utilisees associé à ce programme.

Si c'est le cas, le procédé se poursuit alors à l'étape A-3.

Si ce n'est pas le cas, la ressource de calcul B notifie le rejet de la demande de déport à la ressource de calcul A émettrice de la demande. L'ensemble des registres de notification d'échec de demande de déport d'une séquence d'une alternative sont mis à jour sur la ressource de calcul A avec, s'il s'agit de la première demande de déport (identifiable par une valeur de compteur d'instruction à 0), l'adresse de l'instruction de répartition. S'il ne s'agit pas d'une première tentative de déport, seul le champ de notification d'échec de demande de déport supplémentaire est validé. Le procédé se poursuit à l'étape A-4.

Etape A-3

Si cette demande de déport est acceptée, côté ressource de calcul A émettrice de la demande de déport, le compteur EPSact est incrémenté. Puis, les informations suivantes sont transmises par la ressource de calcul A vers la ressource de calcul B : l'ensemble des registres volatils et non-volatils manipulés par le programme, le pointeur de pile, la structure de pile courante, l'identifiant de la première ressource de calcul, la valeur du compteur EPSact, l'adresse de branchement spécifiée par l'instruction de répartition d'alternative ainsi que la valeur de condition générant la sélection de l'une des séquences de l'alternative. Ces transferts peuvent être mis en œuvre de différentes manières selon la microarchitecture sous-jacente, par exemple en totalité par le matériel après l'exécution d'une barrière mémoire et des extensions matérielles adéquates ou via des instructions permettant d'accéder aux registres de la ressource de calcul A depuis la ressource de calcul B ou encore purement via des instructions classiques d'accès à la mémoire pour transférer ces informations.

L'ensemble de ces valeurs sont positionnées sur la ressource de calcul B réceptrice de la demande de déport, tandis que les registres non manipulés par le programme sont réinitialisés sur cette même ressource de calcul B.

Le procédé poursuit son exécution à l'étape A-6.

Etape A-4

Si la demande de déport n'est pas acceptée par la ressource B, la ressource B est retirée de l'ensemble ressources_utilisables associé à la ressource de calcul A et une autre ressource de calcul utilisable mais non encore utilisée est identifiée (de la même manière qu'à l'étape A-l du procédé) et le procédé se poursuit alors à l'étape A-2 sur la ressource de calcul A.

La ressource B peut éventuellement être ultérieurement ajoutée à l'ensemble ressources_utilisables associé à la ressource de calcul A lorsque des conditions sont réunies, par exemple lorsque la charge applicative de la ressource B est plus faible ou lorsque la configuration du système change et que la ressource B peut de nouveau être utilisée.

Etape A-5

Si aucune ressource de calcul n'est identifiée, l'exécution du programme se poursuit sans utiliser le procédé selon l'invention. L'instruction de répartition est alors traitée comme une instruction de branchement conditionnelle classique. L'ensemble des registres de notification d'échec de demande de déport sont en revanche mis à jour avec, s'il s'agit de la première tentative de déport pour ce programme (identifiable par une valeur de compteur d'instruction à 0), l'adresse de l'instruction de répartition d'alternative. S'il ne s'agit pas d'une première tentative, seul le champ de notification d'échec de demande de déport supplémentaire est validé. Le procédé attend alors une nouvelle instruction de répartition pour reprendre l'étape A-l.

Etape A-6 La valeur du compteur d'instruction de la ressource de calcul A, émettrice d'une demande de déport, est positionné à l'instruction suivante et l'exécution de l'alternative non-satisfaite se poursuit sur la ressource de calcul B, réceptrice d'une demande de déport d'alternative, à l'instruction spécifiée dans l'instruction de répartition.

Sur chacune des deux ressources de calcul, l'ensemble ressources_utilisables est mis à jour pour inclure la ressource de calcul B, ayant acceptée la demande de déport.

Les étapes du procédé sont les suivantes durant l'exécution en parallèle des séquences de l'alternative (identifiable par le fait que le compteur EPSact présente une valeur supérieure à 1). En dehors de ces étapes, aucune donnée manipulée ne peut avoir son champ propriétaire valide.

Etape B-l

Pour chaque exécution d'une instruction générant depuis une ressource de calcul A ou B un accès mémoire en écriture, une nouvelle copie de la donnée modifiée est insérée dans la hiérarchie mémoire et les champs de ses méta-informations globale et propriétaire sont respectivement invalidé et positionné à l'identifiant de la ressource de calcul A ou B. Lorsque la hiérarchie mémoire s'appuie sur des caches, la stratégie de mise à jour (qu'elle soit immédiate ou différée) concerne uniquement ces caches et exclue donc un impact sur la mémoire centrale ou sur des E/S afin d'éviter toute mise à disposition de données incohérentes à d'autres programmes ou à l'environnement externe. Pour ce faire, le mécanisme de mise à jour d'un cache du dernier niveau de la hiérarchie mémoire est désactivé lorsque les champs globale et propriétaire sont respectivement invalidé et positionné à l'identifiant d'une ressource de calcul. Cette règle pour un accès en écriture peut s'appliquer uniquement pour un accès au premier niveau partagé d'une hiérarchie mémoire, si aucune cohérence matérielle n'est assurée entre les niveaux privés de la hiérarchie mémoire.

Etape B-2

Pour chaque exécution d'une instruction générant un accès mémoire en lecture au premier niveau de la hiérarchie mémoire d'une ressource de calcul A, et avant toute transmission de la requête au niveau supérieur de la hiérarchie mémoire de la ressource de calcul A, la requête est transmise au premier niveau de la hiérarchie mémoire de l'autre ressource de calcul B utilisée dans ce niveau d'exécution en parallèle de séquences d'une alternative.

Une variante est de réaliser cette transmission en parallèle avec la transmission de la requête au premier niveau de la hiérarchie mémoire de la ressource de calcul A, toutefois ceci augmente la latence pire cas d'une requête mémoire depuis une ressource de calcul. Un compromis peut être exploré pour autoriser une telle simultanéité pendant un certain nombre de cycles matériels et réduire la latence de ces accès mémoire réalisés par la seconde ressource de calcul.

Une autre variante est de transmettre en parallèle des requêtes à l'ensemble des premiers niveaux de la hiérarchie mémoire des ressources de calcul utilisées par le programme (celles identifiées par l'ensemble ressources_utilisees).

L'ensemble de ces variantes sont applicables pour passer d'un niveau n à un niveau n+1 d'une hiérarchie mémoire. La requête mémoire d'une ressource de calcul A ne peut que consulter les données dont les champs de ses méta-informations globale et propriétaire sont respectivement valide et invalidé (donnée modifiée par aucune autre séquence d'une alternative) ou respectivement invalidé et égal à l'identifiant de la ressource de calcul A (donnée ayant été préalablement modifiée par la séquence s'exécutant sur la ressource de calcul A).

Les étapes du procédé sont les suivantes pour le traitement de l'instruction de terminaison de parallélisme.

Etape C-l

Lorsqu'une instruction de terminaison d'alternative est décodée par une ressource de calcul A, l'information de terminaison de cette alternative est transmise à la ressource de calcul B impliquée dans l'exécution en parallèle. Si la ressource de calcul B n'a pas terminée l'exécution de la séquence qui lui a été assignée, la ressource de calcul A attend alors la notification de la terminaison par la ressource de calcul B.

Etape C-2

La ressource de calcul A inspecte alors la valeur de l'évaluation de la condition (par exemple calculée lors de l'exécution de l'instruction de répartition, ou encore en s'appuyant sur le registre d'état de la ressource de calcul) pour déterminer si la séquence qu'elle vient d'exécuter correspond à la séquence sélectionnée par la sélection conditionnelle.

Si c'est le cas, la ressource de calcul A propage une requête à la hiérarchie mémoire pour rendre valide le champ globale présent dans les méta-informations associées à chaque donnée modifiée durant l'exécution en parallèle, identifiables par le fait que le champ propriétaire est positionné à l'identifiant de la ressource de calcul A. Le champ propriétaire est également invalidé lors du traitement de cette requête.

Si ce n'est pas le cas, la ressource de calcul A propage une requête pour invalider d'une manière classique les données modifiées durant l'exécution en parallèle, identifiables par le fait que le champ propriétaire est positionné à l'identifiant de la ressource de calcul A. Ce dernier champ est également invalidé et le champ globale est réinitialisé. Par ailleurs, le pipeline est vidé, la zone mémoire utilisée par la pile de la ressource A est invalidée.

Etape C-3

Sur chaque ressource de calcul, le compteur ESPmax est décrémenté et la ressource de calcul qui n'est pas retenue pour poursuivre l'exécution est retirée de l'ensemble ressources_ u tilisees .

Si la ressource de calcul choisie pour poursuivre l'exécution du programme n'a pas exécuté la séquence sélectionnée, le contexte d'exécution de la séquence sélectionnée (l'ensemble des registres volatils et non-volatils manipulés par le programme, le pointeur de pile, la structure de pile complète) doit être transféré depuis la ressource de calcul ayant exécutée cette séquence sélectionnée. Par ailleurs, les données manipulées par le programme et stockées dans les niveaux privés de la hiérarchie mémoire associée à la ressource de calcul ayant exécutée la séquence sélectionnée doivent être propagés jusqu'au premier niveau partagé entre les deux ressources de calcul de la hiérarchie mémoire. Quel que soit le choix de la ressource de calcul, si les registres de notification associés à deux ressources de calcul, utilisées dans l'exécution en parallèle qui se termine, notifient des premiers échecs de demande de déport ou de tentative de dépassement, seuls les champs de notification supplémentaires associés à ces évènements sont validés sur la ressource de calcul retenue pour poursuivre l'exécution du programme. Sinon, chaque registre de notification associé à la ressource de calcul retenue pour poursuivre l'exécution du programme est mise à jour avec les informations de l'autre ressource de calcul utilisée.

Enfin, la valeur du compteur d'instruction de la ressource de calcul retenue pour poursuivre l'exécution du programme est positionnée à l'adresse de saut spécifiée dans l'instruction de terminaison de parallélisme. Sur la ressource de calcul n'ayant pas été retenue pour poursuivre l'exécution du programme, une interruption de fin d'exécution en parallèle est notifiée, ceci afin de permettre par exemple la reprise de l'exécution d'autres programmes.

Il est à noter que cette étape C-3 peut être anticipée à l'étape C-2 pour éventuellement réduire le surcoût de cette notification en venant paralléliser son exécution avec l'attente de la terminaison du parallélisme. Pour éviter toute incohérence sur les valeurs manipulées par les autres séquences de l'alternative, cette anticipation doit être menée sur des données non exploitées par ces mêmes séquences en cours d'exécution.

Le procédé tel que précédemment décrit comprend une étape de mesure de la durée d'exécution du programme et une étape de détermination d'un WCET du programme. L'invention n'est pas limitée au procédé tel que précédemment décrit mais s'étend également à un produit programme d'ordinateur comprenant des instructions de code de programme, notamment les instructions précédemment décrites de répartition de séquences et de terminaison de parallélisme, qui, lorsque le programme est exécuté par un ordinateur, conduisent celui-ci à mettre en œuvre ce procédé.