Brevet FR3045870A1 — publié le 20170623

-1 PROCEDE HORS LIGNE D'ALLOCATION D'UN LOGICIEL EMBARQUE TEMPS REEL SUR UNE ARCHITECTURE MULTICONTRÔLEUR MULTICOEUR, ET SON UTILISATION POUR DES APPLICATIONS EMBARQUEES DANS UN VEHICULE AUTOMOBILE DOMAINE TECHNIQUE DE L'INVENTION. La présente invention concerne un procédé hors ligne d'allocation d'un logiciel sur une architecture multicceur. L'invention concerne également une utilisation de ce procédé pour des 10 applications embarquées dans un véhicule automobile. ARRIERE PLAN TECHNOLOGIQUE DE L'INVENTION. De nos jours, des systèmes d'exploitations (ou OS, acronyme en terminologie anglaise de "Operating System") embarqués sont couramment utilisés 15 dans les unités de calcul électroniques (ECU ou "Electronic Control Unit" en terminologie anglaise) de véhicules automobiles. En général, il revient à un système d'exploitation l'enchaînement des tâches, le traitement des interruptions, et la gestion des ressources. Les enjeux classiques des systèmes d'exploitation embarqués sont la 20 capacité de réponse temporelle (c'est-à-dire assurer le déterminisme temps réel des applications) et l'extensibilité (c'est-à-dire maintenir la robustesse des applications tout en ajoutant de plus en plus de fonctionnalités). En ce qui concerne les applications dans l'automobile, les véhicules devenant autonomes et connectés, la complexité du logiciel s'accroît, et des 25 standards tels qu'AUTOSAR (acronyme en terminologie anglaise de "AUTomotive Open System ARchitecture", c'est-à-dire "Architecture de Système Ouvert d'Automobile"), permettant de standardiser la conception des produits logiciels automobiles, conduisent également à une augmentation de la taille du code à embarquer. 30 De plus, avec l'arrivée de la norme ISO 26262, les systèmes d'exploitation embarqués sont de plus soumis à un nouvel ensemble d'exigences pour satisfaire aux contraintes de sûreté de fonctionnement. Le respect de ces contraintes nécessite des mécanismes logiciels de tolérance aux fautes spécifiques. 3045870 - 2 - Dans ce contexte, des microcontrôleurs multicceurs sont vus comme essentiels. Une architecture multicceur peut être vue comme un ensemble de coeurs fonctionnant en parallèle dans une même puce. Chaque coeur peut exécuter son propre élément de code. Contrairement à ce qui se passe dans l'utilisation de 5 multiples contrôleurs, tous les coeurs partagent les mêmes composants matériels (alimentation, bus, E/ S, mémoires). De tels processeurs sont apparus sur le marché de l'embarqué ces dernières années et sont actuellement mis en avant par des fabricants tels que Freescale (par exemple les types Cobra ou McKinley), Infineon (par exemple le TC277 ou TC279 dans la famille AURIX), ou Texas 10 Instruments (par exemple la famille TI Vision), etc... Une application peut être vue comme un ensemble de composants logiciels qui communiquent entre eux. Si l'on prend les applications sous AUTOSAR par exemple, ces composants sont appelés SoftWare Components (SWCs) et nteragissent indépendamment d'une plateforme matérielle particulière grâce à un 15 environnement abstrait appelé Virtual Functionnal Bus (VFB, c'est-à-dire "Bus Fonctionnel Virtuel"). Chaque SWC contient un ou plusieurs "runnables" (vocable propre à AUTOSAR désignant un élément de code appelé "exécutable" par l'homme de métier). Les exécutions des "runnables" peuvent être programmées indépendamment. 20 Cette méthodologie de description permet aux développeurs et aux intégrateurs de concevoir logiquement une ECU. La catégorie d'applications visées par la présente invention est celle des applications de contrôle/ commande (par exemple celle concernant le système de contrôle moteur, l'habitacle, le chassis, les modules de pilotage des systèmes d'aide à la conduite avancés, ou ADAS en 25 terminologie anglaise, acronyme de "Advanced Driver Assistance System", etc...) pour lesquelles des contraintes temps-réel fortes et de strictes coopérations fonctionnelles doivent être respectées, même au travers des frontières des coeurs. C'est la raison pour laquelle l'utilisation d'une architecture multicceur dans le domaine de l'automobile n'est pas triviale, dans la mesure où les applications cibles 30 interagissent avec des systèmes physiques, et sont tenues par de strictes contraintes temps réel. Malgré des avantages indéniables en termes de performances, l'introduction des architectures multicceurs conduit à de nombreux problèmes: - allocation du logiciel aux coeurs, c'est-à-dire l'allocation d'une composante 3045870 -3 logicielle à un des plusieurs coeurs; - définition d'un ensemble des tâches dans le système d'exploitation et affectation puis séquencement des éléments fonctionnels aux tâches; - distribution des variables dans les mémoires dans le cas d'architecture 5 matérielle avec plusieurs niveaux de mémoires; - synchronisation du flux de traitement entre les coeurs. L'entité inventive a principalement porté son attention sur les deux premiers problèmes. Le troisième problème peut être traité de la même manière par extension des contraintes et des fonctions de coût utilisés dans le procédé de io l'invention. En ce qui concerne l'allocation hors ligne du logiciel, on connaît des procédés basés sur une analyse manuelle et sur une validation par simulation. Par exemple, des outils commerciaux tels que Timing Architect ou SymtaVision proposent une validation au niveau de la simulation. A partir d'une 15 solution d'allocation fournie par l'utilisateur, ces outils simulent un ensemble de tâches déployées sur l'architecture multicceur, et vérifient un ensemble de contraintes (par exemple les contraintes temps réel, la contention entre les ressources partagées, etc...). Par l'utilisation d'un de ces deux outils, le concepteur peut analyser le 20 diagramme de Gantt du séquencement des tâches, analyser les dépendances des données, ou encore faire la synthèse du temps système de la charge des communications. Ces deux outils ont fait l'objet de demandes de brevets par leurs concepteurs, et leurs principes sont notamment décrits dans la demande 25 internationale W02012146406, et le brevet américain US6947868, respectivement. La simulation est proche du modèle matériel réel et les résultats de l'analyse pourraient être une aide pour les modifications de l'allocation (proposée initialement par ces outils. Ces outils sont des produits commerciaux, bien industrialisés, et pouvant 30 être interfacés avec un standard logiciel tel qu'AUTOSAR, cependant: - le choix d'allocation peut encore ne pas être optimal; - l'aide fournie par ces outils pour l'étape d'allocation est limitée car elle nécessite de connaître par avance l'enchaînement des tâches devant assurer le respect des contraintes fonctionnelles. L'entité inventive revendique une invention 3045870 - 4 - basée sur l'analyse complète des composantes logicielles et de leurs interactions. Il est également connu de l'entité inventive des procédés hors ligne d'allocation d'un logiciel basés sur des méthodes heuristiques, tels que ceux mis en oeuvre dans les outils issus des programmes de recherche européens AMALTHEA 5 et parMerasa (acronyme de "Multicore Execution Parallelized liard Real-time Applications Supporting Analysability."). Des méthodes heuristiques telles qu'évoquées ci-dessus sont décrites dans l'article de B. Miramond, J.-M. Delosme, « Decision guide environment for design space exploration », 10th IEEE Conference on Emerging Technologies and Factory 10 Automation, 2005. L'outil AMALTHEA évalue les solutions d'allocation en utilisant des fonctions de coût. En appliquant un algorithme métaheuristique tel qu'un algorithme génétique, l'outil explore l'espace des solutions pour trouver la meilleure solution qui satisfait aux conditions des fonctions de coût prédéterminées. Cependant: 15 - la définition des fonctions de coût à partir de l'outil est principalement basée sur des critères temps réel: la métrique de quantification de la conformité avec le délai au niveau du système, la consommation des ressources et le temps système pour la communication des données; - l'aspect lié aux séquences d'exécution, tel que les chaînes événementielles 20 et les ordres d'exécution, n'est pas considéré. L'outil du projet parMerasa prend la dépendance des composantes en compte, cependant : - le temps système des communications entre coeurs n'est pas considéré par l'outil; 25 - seul les runnables d'une même tâche peuvent être exécutés en parallèle, dans le but de toujours assurer l'enchaînement des tâches dans le bon ordre. Cela ne permet pas de tirer profit du parallélisme offert par le multicoeur. Cet aspect est traité notamment dans l'article de Milos Panic, Sebastian Kehr, Eduardo Quinones, Bert Bôddeker, Jaume Abella and Francisco J. Cazorla, " RunPar: An Allocation 30 Algorithm for Automotive Applications Exploiting Runnable Parallelism in Multicores," ACM International Conference on Hardware/Software Codesign and System Synthesis (CODES), New Delhi, India, October 12-17, 2014. De plus, aucun de ces outils issus des projets européens n'est encore industrialisé, et une mise en pratique dans un procédé industriel doit encore être 3045870 -5 évaluée. Les problèmes d'allocations ont également été considérés par le domaine de la recherche académique. Dans l'article de A. Monot, N. Navet, B. Bavoux, and F. Simonot-Lion, " Multi-source software on multicore automotive ecus - combining 5 runnable sequencing with task scheduling," IEEE Trans. Ind. Electron, vol. 59, no. 10, pp.3934-3942, October, 2012, les auteurs proposent un algorithme heuristique pour allouer des « runnables » AUTOSAR sur des coeurs. Dans les articles de H. R. Faragardi, B. Lisper, and T. Nolte, "Towards a communication-efficient mapping of Autosar runnables on multi-cores," IEEE 18th Conf. on Emerging Technologies & Factory Automation (ETFA), vol. 18, pp. 1-5, Spetember, 2013, et de S. E. Saidi, S. Cotard, K. Chaaban, and K. Marteil, "An ilp approach for mapping autosar runnables on multi-core architecutures," Proceeding of the 2015 Workshop on Rapid Simulation and Performance Evaluation: Methods and Tools, 2015, les auteurs modélisent le problème d'allocation à l'aide d'une approche ILP, acronyme en terminologie anglaise de « Integer Linear Programming », c'est-à-dire, une optimisation linéaire en nombre entier. Ces travaux, non industriels, ne considèrent que des contraintes temps réels, et ne ciblent pas les séquencements des traitements.II existe donc un besoin pour un procédé hors ligne d'allocation d'un logiciel sur les coeurs, assurant la configuration de l'ensemble des tâches et le séquencement des exécutables aux tâches et qui soit industrialisable. DESCRIPTION GENERALE DE L'INVENTION. La présente invention vise par conséquent à satisfaire ce besoin et concerne en particulier l'allocation des composantes applicatives sur des coeurs. Elle a précisément pour objet un procédé hors ligne d'allocation d'un logiciel sur une architecture multicceur, ce logiciel étant compatible avec un système d'exploitation prédéfini comprend: - des composantes applicatives; - un environnement d'exécution; - un logiciel de base temps réel fournissant des services aux composantes applicatives; - une couche d'abstraction matérielle de l'architecture multicceur. Selon l'invention, le procédé comprend: - une première étape d'analyse des dépendances des composantes applicatives 3045870 - 6 - produisant un graphe orienté comportant un premier ensemble de noeuds formés par des éléments fonctionnels s'identifiant aux composantes applicatives ou bien à des exécutables selon un niveau de granularité permis par le système d'exploitation, et un second ensemble de transitions entre ces éléments 5 fonctionnels; et en outre dans une itération courante: - une deuxième étape de distribution des éléments fonctionnels sur des coeurs de l'architecture multicceur, celle-ci résultant typiquement d'une optimisation courante d'une fonction de coût par les noeuds et les transitions sous des contraintes io prédéterminées; - une troisième étape de validation de cette optimisation courante calculant un temps d'exécution de chacun des éléments fonctionnels exécutés sur les coeurs au moyen du logiciel de base et de la couche d'abstraction matérielle; - une quatrième étape d'évaluation de l'optimisation courante calculant une 15 distance à un objectif prédéterminé et effectuant un retour à la deuxième étape pour une itération supplémentaire des deuxième, troisième et quatrième étapes si cette distance est supérieure à un seuil prédéterminé. Dans le procédé selon l'invention, cette optimisation courante est basée sur un algorithme métaheuristique. 20 Selon l'invention, les contraintes prédéterminées comprennent des charges nominales des coeurs, un équilibrage de charges courantes des coeurs, et des stratégies d'implémentation. Selon l'invention encore, la fonction de coût comprend des critères choisis parmi: 25 - une utilisation de l'architecture multicceur; - un temps système de communication entre les coeurs; - un temps de réponse global d'exécution d'enchaînements des éléments fonctionnels; - une estimation du temps d'exécution de chacun des éléments fonctionnels; 30 - un temps d'accès de données; L'estimation du temps d'exécution de chacun des éléments fonctionnels est selon l'invention un pire temps d'exécution, un temps d'exécution moyen ou un modèle probabiliste. Selon l'invention toujours, les critères peuvent être déterminés dans une 3045870 - 7 - itération initiale des deuxième, troisième et quatrième étapes en utilisant une plateforme monocceur de référence de l'architecture multicceur. Dans le procédé selon l'invention, la première étape comprend: - une première phase dans laquelle, d'une part, les noeuds sont modélisés chacun 5 par un premier groupe comprenant des premiers paramètres choisis parmi le temps d'exécution, un mode de déclenchement, une première période, et dans laquelle, d'autre part, les transitions sont modélisées chacune par un deuxième groupe comprenant des seconds paramètres choisis parmi un poids fonction d'une taille de données transmises, une seconde période d'un producteur; 10 - une deuxième phase de classification des transitions selon un troisième groupe comprenant des classes prédéterminées choisies parmi une première classe dans laquelle les transitions sont périodiques, une deuxième classe dans laquelle les producteurs ou des consommateurs sont périodiques, une troisième classe sans périodicité, une quatrième classe dans laquelle les transitions sont invoquées sur 15 un évènement; - une troisième phase d'analyse des taux de transfertdes données, comprenant à la fois les accès en production et en consommation; - une quatrième phase d'analyse de séquences de communications et d'extraction de flux de ces données présentant des taux de transfert identiques. 20 Dans le procédé selon l'invention encore, la deuxième étape comprend: - une première phase de préparation transformant le graphe orienté en un graphe orienté acyclique au moyen d'une première opération consistant à placer les noeuds sur une ligne horizontale, des arcs directs étant placés au dessus de cette ligne et des arcs rétrogrades étant placés au dessous de cette même ligne d'une 25 deuxième opération consistant à modifier un ordre des noeuds de manière à former une succession de ces noeuds avec un minimum de coût d'arcs rétrogrades, et d'une troisième opération consistant à supprimer provisoirement ces arcs rétrogrades; - une deuxième phase réalisant l'optimisation courante en se basant sur le graphe 30 orienté acyclique et la fonction de coût; - une troisième phase de génération de fichiers de configuration du système d'exploitation et de l'environnement d'exécution. Selon une autre caractéristique, chaque arc est associé avec un coût en fonction de la classification et du taux de transfert des données. 3045870 - 8 - Dans le procédé selon l'invention toujours, la troisième étape est une évaluation sur cible matérielle comprenant en outre une mesure de durées d'exécution des services utilisés en communiquant entre les coeurs. Dans le procédé selon l'invention enfin, dans la quatrième étape la distance 5 est donnée par l'expression: D = Sortie(e) Entrée(0) où 0 sont les critères de la fonction de coût, Entrée(0) sont des valeurs de référence de ces critères et Sortie(0) sont des valeurs courantes des critères dans l'itération courante. 10 L'invention vise également une utilisation du procédé hors ligne d'allocation d'un logiciel sur une architecture multicceur décrit ci-dessus pour des applications sous un système d'exploitation temps réel de type AUTOSAR destinées à être embarquées dans un véhicule automobile. Ces quelques spécifications essentielles auront rendu évidents pour 15 l'homme de métier les avantages apportés par le procédé selon l'invention par rapport à l'état de la technique antérieur. Les spécifications détaillées de l'invention sont données dans la description qui suit en liaison avec les dessins ci-annexés. Il est à noter que ces dessins n'ont d'autre but que d'illustrer le texte de la description et ne constituent en aucune 20 sorte une limitation de la portée de l'invention. BREVE DESCRIPTION DES DESSINS. La Figure 1 est une représentation générale du procédé selon l'invention Les Figures 2a et 2b illustrent respectivement une transformation d'un 25 graphe orienté en un graphe orienté acyclique dans le procédé selon l'invention. Les Figures 3a et 3b montrent respectivement un graphe orienté d'une application avec une modélisation des noeuds par un temps d'exécution et une période, et un résultat d'une analyse de dépendances pour cette application dans le procédé selon l'invention. 30 La Figure 4 illustre une allocation sur deux coeurs obtenue par le procédé selon l'invention pour l'application montrée sur la Figure 3a. La Figure 5 représente un graphe orienté d'une autre application montrant 3045870 - 9 - des taux de transfert de données entre exécutables. La Figures 6 illustre une analyse du temps d'exécution d'un exécutable. Les Figures 7a et 7b montrent deux exemples de temps de réponse global d'exécution d'enchaînements sur un des coeurs montrés sur la Figure 4. 5 DESCRIPTION DU MODE DE REALISATION PREFERE DE L'INVENTION. Dans le mode de réalisation préféré de l'invention, montré sur la Figure 1, l'architecture logicielle 1 est compatible avec le standard AUTOSAR; toutefois le procédé hors ligne d'allocation d'un logiciel sur une architecture multicceur selon 10 l'invention n'est pas spécifique à AUTOSAR. Dans une première étape 2 du procédé, on effectue une analyse des dépendances entre les éléments fonctionnels d'une application. Etant donné la grande sensibilité des applications cibles à un ordre d'exécution de ces éléments fonctionnels et la faible proportion de parallélisme 15 existante, la répartition d'applications du domaine de l'automobile entre de multiples coeurs nécessite une analyse des dépendances particulièrement fine. Un premier outil d'analyse des dépendances implémentant cette première étape 2 est basé sur un environnement de développement dédié aux applications en langage Java (Eclipse). Il permet d'analyser un logiciel d'application en faisant 20 l'analyse syntaxique des fichiers de description au format .xml (par exemple les fichiers *.arxml dans un contexte AUTOSAR). Ce premier outil analyse les caractéristiques de l'application 1 dans les phases suivantes: 1 - Remodelage de l'architecture logicielle 3 25 - l'architecture logicielle 1 est modélisée en utilisant un graphe orienté G(V, T), dont plusieurs exemples sont montrés sur les Figures 2 à 5, où V est un premier ensemble de noeuds A, B, C, D, E, F, G, H formés par des composantes applicatives ou bien des exécutables (ou "runnables" pour des applications AUTOSAR), et T est un second ensemble de transitions entre ces éléments 30 fonctionnels. Un noeud V est modélisé par un temps d'exécution, un mode de déclenchement, une périodicité. Une transition T a un poids qui dépend de la taille des données échangées, des périodicités des exécutables qui produisent et consomme ces données 3045870 -10- - une dimension du graphe G est optimisée par la création de bus entre les noeuds V. 2 - Construction de statistiques 4 sur les transitions T entre les noeuds V Chaque transition appartient à l'une des quatre classes C1, C2, C3, C4 5 suivantes: - classe 1: transition T périodique divisée en trois séries S1, S2, S3 (Série 1: mêmes deuxième et troisième périodes e c JC n lateur et un producteur; série 2: troisième période du producteur plus petite que la deuxième période du consommateur; série 3: troisième période du producteur plus grande que la 10 deuxième période du consommateur); - classe 2: producteur OU consommateur (exclusivement) périodique divisée en deux séries 51, S2 (Série 1: le producteur est périodique; série 2: le consommateur est périodique); - classe 3: aucune périodicité; 15 - classe 4: transitions T invoquées sur des évènements (par exemple évènement de commutation de mode, opération client/ serveur). Si AUTOSAR est le système d'exploitation ciblé, deux niveaux de granularités sont permis: analyse au niveau des composantes applicatives SWC, ou analyse au niveau des "runnables". Dans tous les autres cas, l'analyse est faite 20 au niveau des composantes applicatives, mais dans le cas d'AUTOSAR, cette facilité permet de réduire la complexité de l'analyse et par conséquent de diminuer le temps nécessaire pour trouver une solution d'allocation. 3 - Analyse des taux de transfert des données entre les exécutables. 4 - Analyse de séquences de communications (extraction des flux de 25 données appartenant à la classification Cl S1). Les premières entrées 1 de ce premier outil réalisant la première étape 2 du procédé selon l'invention sont: - les composantes applicatives (SWCs dans AUTOSAR); - les relations qui structurent ces composantes. 30 Il convient de noter que, dans la mesure où l'architecture logicielle (aussi appelée architecture statique) est une donnée d'entrée, cette première étape 2 du procédé est réalisée seulement une fois, et est exclue du processus itératif. Un logiciel de base temps réel (BSW ou "Basic Software" dans AUTOSAR) et une couche d'abstraction matérielle de l'architecture multicceur (HW dans 3045870 - 11 - AUTOSAR par exemple pour le bus CAN, etc...) ne sont pas inclus dans l'analyse conduisant à une solution d'allocation, mais seulement au niveau de la validation de la solution, où les impacts du logiciel de base BSW et de la couche d'abstraction matérielle HW sont pris en compte implicitement dans des mesures. 5 Les premières sorties de ce premier outil réalisant la première étape 2 du procédé selon l'invention sont: - des informations sur les transitions T: l'exécutable producteur et l'exécutable consommateur, les composantes applicatives SWC qui les contiennent et leur environnement d'exécution associé (mode de déclangement, leur 10 périodicité), et les données transmises; - une classification des transitions T: chaque transition T est classée dans une des classes Cl C2 C3 ou C4 selon des critères de l'environnement d'exécution pour les exécutables producteurs et consommateurs; - des informations sur les données: l'information sur les données pour 15 chaque transition contient une taille des données, une unité des données, un type de données et un taux de transfert des données; - une identification des enchaînements des éléments fonctionnels, "runnables" ou SWC. La Figure 5 montre un exemple d'enchaînements avec indication des 20 classes et des séries des transitions T entre les noeuds A, B, C, D, E, F, G, ainsi que des taux de transfert des données en octets par milliseconde. Les résultats de l'analyse de dépendances pilotent la deuxième étape 5 de distribution des éléments fonctionnels de l'application, par exemple: - la classification des transitions T et les informations sur les données sont 25 utilisées pour évaluer un temps système des communications; - les enchaînements identifiés servent à déterminer un temps de réponse global d'exécution de ces enchaînements. Un second outil implémentant la deuxième étape 5 du procédé selon l'invention effectue une exploration de l'espace de conception (ou DSE, acronyme 30 de l'expression anglaise "Design Space Exploration") du graphe orienté élaboré dans la première étape 2 pour distribuer les applications dans des systèmes multicceurs. Ainsi que cela a été indiqué dans l'analyse de l'état de la technique, le problème est formalisé sous la forme d'un problème d'optimisation combinatoire, 3045870 - 12 - qui repose principalement sur la définition de fonctions d'objectif par rapport à des contraintes prédéterminées. Par conséquent, deux éléments essentiels sont pris en compte dans cette deuxième étape 5 du procédé selon l'invention comme l'indique la Figure 1: les 5 contraintes 6 qui doivent être respectées et une fonction de coût qui doit être optimisée 7. Les contraintes prédéterminées 6 sont des paramètres statiques qui doivent être vérifiés pour chaque solution possible. Ces contraintes 6 peuvent prendre en considération aussi bien des caractéristiques temps réel (par exemple la charge de 10 chaque coeur) que les stratégies d'implémentation (par exemple interdire la séparation d'un client et de son serveur). La fonction de coût 7 est calculée à partir des éléments essentiels suivants: - utilisation de l'architecture multicceur; - temps système de communication inter-coeur; 15 - temps de réponse global d'exécution d'enchaînements ("makespan" dans le vocabulaire de l'homme du métier) qui peut aussi prendre en compte des contraintes en termes d'ordre d'exécution. Outre les résultats de la première étape 2, d'autres types d'entrées provenant de l'exécution sur la plateforme des versions précédentes sont 20 nécessaires pour calculer la fonction de coût 7: - un temps d'exécution de chaque exécutable, qui n'est pas constant à chaque exécution. Une estimation de ce temps d'exécution peut se décliner en trois formats: un pire temps d'exécution, un temps d'exécution moyen ou un modèle probabiliste; 25 - un temps d'accès de données qui pourrait être utilisé pour évaluer un surcoût de temps système de communication pour les communications inter-coeur; Les entrées ci-dessus correspondant à des informations de rétroaction d'une quatrième étape du procédé selon l'invention, décrite ci-dessous, provenant d'une itération précédente.On 30 notera aussi que ces entrées peuvent être déterminées au moment d'une itération initiale, par exemple en utilisant une analyse de l'exécution du logiciel sur une plateforme monocceur de référence (sur la même cible). Ces résultats sont ensuite mis à jour après itération des étapes du procédé. De manière détaillée, on procède comme suit pour effectuer la distribution 3045870 - 13 - des éléments fonctionnels de l'application: - préparation du graphe orienté G fourni par la première étape 2: dans le but de calculer le temps de réponse global d'exécution d'enchaînements, le modèle de l'application doit être un graphe orienté acyclique (ou DAG, acronyme de "Direct 5 Acyclic Graph" en terminologie anglaise); la préparation du graphe orienté G consiste à transformer le graphe orienté initial en un graphe orienté acyclique de la manière suivante: 1- Placer les noeuds A, B, C, D, E, F sur une ligne horizontale comme le montre la Figure 2a, des arcs directs (traits pleins) étant placés au dessus de cette 10 ligne et des arcs rétrogrades (traits en pointillé) étant placés au dessous de cette ligne; 2 - Modifier un ordre de ces noeuds A, B, C, D, E, F de manière à former une succession de noeuds C, F, B, D, A, E avec un minimum de coût d'arcs rétrogrades comme le montre la Figure 2b; 15 3 - Supprimer les arcs rétrogrades, le reste du graphe est alors un graphe orienté acyclique. Les dépendances telles que les contraintes séquentielles sont prises en compte. Tous les noeuds qui sont fortement connectés ne seront pas répartis sur plusieurs coeurs. L'existence d'une solution dépend fortement du fait qu'il existe 20 plus d'un groupe. - optimisation basée sur le graphe orienté acyclique généré par la phase de préparation précédente qui implique une allocation des noeuds C, F, B, D, A, E du graphe G sur les différents coeurs de l'architecture multicceur; il y a deux degrés d'optimisation: 25 1 - le degré d'équilibrage des charges qui implique une optimisation des charges (c'est-à-dire équilibrage des charges d'une unité centrale de traitement ou processeur, minimisation des charges de communication inter-coeur, etc...) quand les noeuds C, F, B, D, A, E du graphe sont répartis entre les différents coeurs; 2 - le degré de performance qui implique une optimisation du makespan pour 30 chaque coeur, et optimise l'ordre d'exécution des noeuds dans chaque coeur. Ces deux degrés d'optimisation peuvent être formulés dans une approche d'exploration de l'espace de conception (DSE). La solution d'optimisation est évaluée par la fonction de coût 7, et une recherche de la solution qui minimise la fonction de coût peut être effectuée par 3045870 - 14 - des algorithmes métaheuristiques tels que MOSA (acronyme de "Multi-Objective Simulated Annealing", c'est-à-dire "Analyse Spécifique d'Objets Multi-échelle", ou MOGA (acronyme de "Multi-Objective Genetic Algorithm", c'est-à-dire "Algorithme Génétique de Tri Non-dominé"), etc... 5 Comme le montre la Figure 1, les résultats de cette deuxième étape 5 sont intégrés dans le procédé pour générer les fichiers de configuration 8, 9 au format .xml (ou plus précisément *.arxml dans un contexte AUTOSAR): - un premier fichier de configuration 8 du système d'exploitation; - un second fichier de configuration 9 de l'environnement d'exécution (RTE 10 ou Runtime Environnement dans AUTOSAR), c'est-à-dire la configuration effective de l'allocation déterminé par le procédé selon l'invention. Dans une troisième étape 10 du procédé selon l'invention, on évalue la solution obtenue 11 à l'issue de la deuxième étape 5. Cette évaluation nécessite une vérification complète du comportement 15 fonctionnel et temps réel de la solution 11. Les informations d'entrée de la validation pourraient être des contraintes tirées des spécifications (déjà utilisées dans la deuxième étape 5 pour les décisions d'allocation des composantes applicatives 1), par exemple l'une des entrées requises dans cette deuxième étape 5 est le temps d'exécution des 20 exécutables, ou plus généralement un fichier de spécifications 12 au format *cmm décrivant des performances imposées. A l'itération initiale, le temps d'exécution des exécutables peut être calculé en utilisant une analyse temps réel sur une plateforme monocceur. Pour chaque exécutable, une distribution du temps d'exécution Tex, pour un grand nombre N 25 d'exécutions est calculé, et des résultats statistiques sont fournis (temps moyen d'exécution, temps d'exécution minimum, temps d'exécution maximum, écart type, etc...). Un exemple d'une telle distribution est donné sur la Figure 6. Pour les itérations ultérieures, la distribution des temps d'exécution des exécutables est calculée sur l'architecture multicceur pour la solution obtenue à 30 l'issue de la deuxième étape à chaque itération. Les impacts sur le comportement temps réel de la distribution sont analysés et pris en compte pour les itérations suivantes. La même chose est faite pour les services 14 utilisés pour communiquer entre les coeurs (services 10C dans AUTOSAR, acronyme de "Inter-OS application 3045870 - 15 - Communication", c'est-à-dire "Communicateur d'inter-Os Application"). Comme ces interfaces de programmation d'applications (ou APIs, acronyme de "Application Programming Interface") sont principalement responsables d'un accroissement de la fonction de coût 7, la charge de la communication inter-coeur 5 est observée au moment de l'exécution. La couche d'abstraction matérielle 15 étant introduite dans cette troisième étape 10, on obtient une validation HIL (acronyme de "Hardware In the Loop", c'est-à-dire "Matériel dans la Boucle") très proche de l'environnement réel. Dans la quatrième étape 16 du procédé selon l'invention, les résultats 10 provenant de la troisième étape 13 sont utilisés pour évaluer la performance des solutions et mettre à jour les données d'entrée de la deuxième étape 5 si une itération supplémentaire est nécessaire. Un modèle de métrique de rétroaction/ mise à jour pour cette évaluation 16 est construit par les critères suivants (liste non exhaustive): 15 - le temps d'exécution des exécutables: pour chaque exécutable, le temps d'exécution peut être modifié; la charge globale de l'architecture multicceur doit être optimisée; le paramètre d'accélération est calculé pour chaque solution de distribution (De combien de fois est-il possible d'accroître la performance avec une architecture multicceur par comparaison à une architecture monocceur). 20 - le temps système de communication: le temps d'accès aux données peut être modifié particulièrement pour le service du canal 10C; - le temps de réponse global d'exécution d'enchaînements (makespan); - la robustesse de l'application due à l'ajout d'un temps système additionnel; - etc... 25 Une distance 17 construite sur un ensemble de critères 0 pour mesurer un écart entre des valeurs de référence Entrée(0) de ces critères et des valeurs courantes Sortie(0) de ces critères calculés à partir des résultats des étapes précédentes 10, 5 peut être donnée par l'expression: D = Sortie(e) 0 Entrée(0) 30 Cette distance D est voisine de zéro si les critères Sortie(0) calculés pour la solution sont proches des critères visés Entrée(0). Si dans la quatrième étape 16, la distance D est supérieure à un seuil prédéterminé Do, un retour 18 est effectué à la deuxième étape 5, sinon la solution 3045870 - 16 - est satisfaisante et peut être implémentée 19, c'est-à-dire, embarquée sur un véhicule. Un exemple d'application dont le graphe orienté est représenté sur la Figure 3a permettra de bien comprendre le procédé hors ligne d'allocation d'un 5 logiciel sur une architecture multicceur selon l'invention. Dans cette application, chaque noeuds A, B, C, D, E, F, G, H représente une composante applicative avec un temps d'exécution C et une période T indiqués par un couple (C,T) sur la Figure 3a et les figures suivantes. Une composante D non périodique est notée (C, (I)); par exemple le noeud D est non périodique. 10 Le but de cet exemple est de distribuer l'application sur une architecture à deux coeurs 20, 21 illustrée sur la Figure 4, les deux coeurs 20, 21 étant identiques. Selon le procédé de l'invention, dans la première étape 2, les traitements suivants sont réalisés: 1 - Synthèse du modèle: les dépendances existantes dans l'application sont 15 analysées en termes de classifications 22, de taux de transfert de données, etc..., comme l'illustre la Figure 3b. 2- Préparation du graphe: étant donné que l'application montrée sur la Figure 3a contient un cycle B, C, D, le graphe orienté de l'application doit être transformé en un graphe orienté acyclique; le procédé identifie la transition de D à 20 B comme un arc rétrograde 23 et l'ignore dans l'optimisation de l'étape suivante. Dans cette deuxième étape 5, les traitements suivants sont réalisés: 3 - Optimisation: l'application est distribuée sur les deux coeurs 20, 21 en évaluant une fonction de coût 7 qui prend en compte les critères suivants: a) équilibrage de la charge et temps système de communication: ces deux 25 critères sont concurrents; sans contrainte d'équilibrage de charge, il n'y aurait pas de temps système de communication si tous les noeuds étaient alloués à un seul coeur. i) l'équilibrage de charge: les charges de l'architecture multicceur pour chaque coeur 20, 21 doit être réalisé autant que possible; 30 ii) le temps système de communication entre les coeurs 20, 21 doit être minimisé. Sur ces bases, l'application peut être distribuée comme le montre la Figure 4. 3045870 - 17 - b) performance: pour les résultats d'allocation sur le premier coeur 20, il y a deux possibilités d'enchaînement, soit A-F-G-H, soit A-*F-*H-*G; le choix entre ces deux possibilités dépend du makespan (dans la fonction de coût 7). En supposant que le coût d'une commutation de contexte est l'unité, pour 5 l'ordre A-F-G-H, le makespan est 23 comme le montre la Figure 7a. Pour l'ordre A-F-H-G, le makespan est 17 comme le montre la Figure 7b. c) vérification des contraintes: il convient de noter que pour chaque solution, les contraintes 6 temps réel et fonctionnelles doivent être respectées. Dans cette 10 application, la solution d'allocation est: - premier coeur 20: B-*C-*E-*D; - second coeur 21: A-*F-*H-*G; Les contraintes 6 suivantes doivent être respectées: i) une charge maximum pour chaque coeur 20, 21 ne doit pas être dépassée; 15 ii) l'exécution de chacun des noeuds doit respecter leurs délais; iii) les transitions spécifiées comme ne passant pas par un coeur 20, 21 ne doivent pas passer par ce coeur; iv) l'ordre des noeuds sur chaque coeur doit respecter les spécifications fonctionnelles; 20 y) les contraintes autres, si elles existent dans les spécifications. 4 - Configuration des tâches: l'allocation des noeuds V à plusieurs tâches est basée sur les critères de chaque noeud V. Par exemple, dans le premier coeur 20, les noeuds A et F sont fortement connectés car leurs périodes (égales à 6) sont identiques; les noeuds A et F seront 25 donc alloués à une première tâche 24. Pour la même raison, dans le second coeur 21, les noeuds B, C, et E sont fortement connectés car leurs périodes sont égales à 12; ces noeuds B, C et E sont alloués à une seconde tâche 25. Dans la troisième étape 10 du procédé selon l'invention appliqué à l'application montrée sur la Figure 3a, on effectue le traitement suivant: 30 5 - Test d'ordonnançabilité et de synchronisation: l'ordonnançabilité est satisfaite si chaque tâche 24, 25 satisfait à son délai (égale à sa période dans l'exemple). L'arc rétrograde 23 qui a été ignoré doit être pris en compte pour la synchronisation. Dans la quatrième étape 16 du procédé selon l'invention appliqué à 3045870 - 18 - l'application montrée sur la Figure 3a, on effectue le traitement suivant: 6 - Evaluation et rétroaction: les résultats de la troisième étape peuvent être utilisés pour évaluer la performance des solutions et mettre à jour les données d'entrée de la deuxième étape 5 de distribution. La métrique de rétroaction/ mise à 5 jour telle que le temps d'exécution de chaque noeud, un temps d'accès de variable pour transition T, ou le temps de réponse global des enchaînements sera utilisé pour mettre à jour les données d'entrée de la distribution pour la boucle/ itération suivante. Comme il va de soi, l'invention ne se limite pas au seul mode de réalisation 10 préférentiel décrit ci-dessus. Notamment, le système d'exploitation AUTOSAR, et les éléments de l'architecture logicielle correspondante (SWC, BSW, 10C, RTE, VFB, HW, etc...) cités, n'est qu'un exemple parmi d'autres de systèmes d'exploitation. Une description analogue pourrait porter sur d'autres modes de réalisations 15 avec d'autres systèmes d'exploitation temps réel, notamment EUROS ®, visant ou non, les applications embarquées dans un véhicule automobile. Ces autres modes de réalisation ne sortiraient pas du cadre de la présente invention dans la mesure où ils résultent des revendications ci-après. REVENDICATIONS1) Procédé hors ligne d'allocation d'un logiciel (1, 8, 9, 15) sur une architecture multicceur (20, 21), ledit logiciel (1, 8, 9, 15) étant compatible avec un système d'exploitation prédéfini (8) et comprenant des composantes applicatives (1), un environnement d'exécution (9), un logiciel de base temps réel fournissant des services auxdites composantes applicatives (1), et une couche d'abstraction matérielle (15) de ladite architecture multicceur (20, 21), caractérisé en ce qu'il comprend: - une première étape (2) d'analyse des dépendances desdites composantes applicatives (1) produisant un graphe orienté comportant un premier ensemble (V) de noeuds formés par des éléments fonctionnels s'identifiant auxdites composantes applicatives (1) ou bien à des exécutables selon un niveau de granularité permis par ledit système d'exploitation (8), et un second ensemble (T) de transitions entre lesdits éléments fonctionnels; et en outre dans une itération courante: - une deuxième étape (5) de distribution desdits éléments fonctionnels sur des coeurs (20, 21) de ladite architecture multicceur (20, 21) résultant d'une optimisation courante d'une fonction de coût (7) par lesdits noeuds (V) et lesdites transitions (T) 20 sous des contraintes prédéterminées (6); - une troisième étape (10) de validation de ladite optimisation courante calculant un temps d'exécution (Texe) de chacun desdits éléments fonctionnels exécutés sur lesdits coeurs (20, 21) au moyen dudit logiciel de base et de ladite couche d'abstraction matérielle (15); 25 - une quatrième étape (16) d'évaluation de ladite optimisation courante calculant une distance (D) à un objectif prédéterminé et effectuant un retour (18) à ladite deuxième étape (5) pour une itération supplémentaire desdites deuxième, troisième et quatrième étapes (5, 10, 16) si ladite distance (D) est supérieure à un seuil prédéterminé (DO). 30 2) Procédé hors ligne d'allocation d'un logiciel (1, 8, 9, 15) sur une architecture multicceur (20, 21) selon la revendication 1 précédente, caractérisé en ce que ladite optimisation courante est basée sur un algorithme métaheuristique. 3045870 - 20 - 3) Procédé hors ligne d'allocation d'un logiciel (1, 8, 9, 15) sur une architecture multicceur (20, 21) selon la revendication 1 précédente, caractérisé en ce que lesdites contraintes prédéterminées (6) comprennent des charges nominales desdits coeurs (20, 21), un équilibrage de charges courantes desdits coeurs (20, 5 21), et des stratégies d'implémentation. 4) Procédé hors ligne d'allocation d'un logiciel (1, 8, 9, 15) sur une architecture multicceur (20, 21) selon la revendication 1 précédente, caractérisé en ce que ladite fonction de coût (7) comprend des critères choisis parmi: 10 - une utilisation de ladite architecture multicceur (20, 21); - un temps système de communication entre lesdits coeurs (20, 21); - un temps de réponse global d'exécution d'enchaînements desdits éléments fonctionnels; - une estimation dudit temps d'exécution (Texe) de chacun desdits éléments 15 fonctionnels; - un temps d'accès de données. 5) Procédé hors ligne d'allocation d'un logiciel (1, 8, 9, 15) sur une architecture multicceur (20, 21) selon la revendication 4 précédente, caractérisé en ce que 20 ladite estimation est un pire temps d'exécution, un temps d'exécution moyen ou un modèle probabiliste. 6) Procédé hors ligne d'allocation d'un logiciel (1, 8, 9, 15) sur une architecture multicceur (20, 21) selon la revendication 4 précédente, caractérisé en ce que 25 lesdits critères sont déterminés dans une itération initiale desdites deuxième, troisième et quatrième étapes (5, 10, 16) en utilisant une plateforme monocceur de référence de ladite architecture multicceur (20, 21). 7) Procédé hors ligne d'allocation d'un logiciel (1, 8, 9, 15) sur une architecture 30 multicceur (20, 21) selon la revendication 1 précédente, caractérisé en ce que ladite première étape (2) comprend: - une première phase dans laquelle, d'une part, lesdits noeuds (V) sont modélisés chacun par un premier groupe comprenant des premiers paramètres choisis parmi ledit temps d'exécution (Texe), un mode de déclenchement, une première période, et 3045870 - 21 - dans laquelle, d'autre part, lesdites transitions (T) sont modélisées chacune par un deuxième groupe comprenant des seconds paramètres choisis parmi un poids fonction d'une taille de données transmises, une seconde période d'un producteur; - une deuxième phase de classification desdites transitions (T) selon un troisième 5 groupe comprenant des classes prédéterminées (C1, C2, C3, C4) choisies parmi une première classe (C1) dans laquelle lesdites transitions (T) sont périodiques, une deuxième classe (C2) dans laquelle lesdits producteurs ou des consommateurs sont périodiques, une troisième classe (C3) sans périodicité, une quatrième classe (C4) dans laquelle lesdites transitions (T) sont invoquées sur un 10 évènement; - une troisième phase d'analyse des taux de transfert desdites données; - une quatrième phase d'analyse de séquences de communications et d'extraction de flux desdites données présentant desdits taux de transfert identiques. 15 8) Procédé hors ligne d'allocation d'un logiciel (1, 8, 9, 15) sur une architecture multicceur (20, 21) selon la revendication 1 précédente, caractérisé en ce que ladite deuxième étape (5) comprend: - une première phase de préparation transformant ledit graphe orienté en un graphe orienté acyclique au moyen d'une première opération consistant à placer lesdits noeuds (V) sur une ligne horizontale, des arcs directs étant placés au dessus de ladite ligne et des arcs rétrogrades étant placés au dessous de ladite ligne, d'une deuxième opération consistant à modifier un ordre desdits noeuds (V) de manière à former une succession desdits noeuds avec un minimum de coût desdits arcs rétrogrades, et d'une troisième opération consistant à supprimer lesdits arcs rétrogrades; - une deuxième phase réalisant ladite optimisation courante en se basant sur ledit graphe orienté acyclique et ladite fonction de coût (7); - une troisième phase de génération de fichiers de configuration (8, 9) dudit système d'exploitation (8) et dudit environnement d'exécution (9). 9) Procédé hors ligne d'allocation d'un logiciel (1, 8, 9, 15) sur une architecture multicceur (20, 21) selon la revendication 1 précédente, caractérisé en ce que ladite troisième étape (10) comprend en outre un calcul de durées d'exécution desdits services utilisés en communiquant entre lesdits coeurs (20, 21). 3045870 -22- 10) Procédé hors ligne d'allocation d'un logiciel (1, 8, 9, 15) sur une architecture multicceur (20, 21) selon la revendication 4 précédente, caractérisé en ce que dans ladite quatrième étape (16) ladite distance (D) est donnée par l'expression: Sortie(e) 5 D = Ilog Entrée(0) e où 0 sont lesdits critères, Entrée(0) sont des valeurs de référence desdits critères et Sortie(0) sont des valeurs courantes desdits critères dans ladite itération courante. 10 11) Utilisation du procédé hors ligne d'allocation d'un logiciel (1, 8, 9, 15) sur une architecture multicceur (20, 21) selon l'une quelconque des revendications 1 à 10 précédentes pour des applications sous un système d'exploitation temps réel (8) de type AUTOSAR destinées à être embarquées dans un véhicule automobile.