Partitionnement logiciel / matériel

Le partitionnement logiciel/matériel consiste à diviser les fonctions d'un système informatique entre celles qui seront exécutées par un logiciel classique et celles qui seront réalisées par un matériel spécifique. On parle de co-design, la conception est double, une conception logicielle et une conception matérielle.

Un système informatique est généralement constitué d'un logiciel destiné à la réalisation de différentes tâches. Ce logiciel est exécuté par un matériel généraliste, c'est-à-dire conçu indépendamment de la fonction réalisée. Dans certains cas, par exemple lorsque le système informatique est un téléphone portable, un décodeur numérique ou encore dans une carte à puce, les rôles respectifs du logiciel et du matériel peuvent être redéfinis. Il s'agit alors le plus souvent d'améliorer les performances et la rapidité d'exécution des tâches, en tirant parti de matériels spéciaux.

Dans une démarche de définition du partitionnement logiciel/matériel, l'objectif est de réfléchir aux différentes actions que peut réaliser le matériel afin d'alléger le logiciel tout en tenant compte des contraintes de coût, des bénéfices sur le plan des performances et des limites intrinsèques à toute implémentation matérielle d'un traitement automatique.

Plusieurs méthodologies permettent de raisonner sur le partitionnement logiciel/matériel le plus approprié pour un système informatique.

Parmi elles, certaines reposent sur une analyse du langage source dans lequel une première version, entièrement logicielle, du système informatique a été créée. Le fruit de cette analyse consiste en la synthèse d'un matériel spécial exploitant tout ou partie du système informatique. Ainsi, idéalement, la redéfinition du partitionnement logiciel/matériel est automatique. Certains algorithmes sont alors utilisés pour rechercher un partitionnement optimal.

D'autres familles de méthodologies se proposent de prendre en compte ce partitionnement au plus tôt dans la définition du système informatique, au moment de la conception et de la spécification de celui-ci. Il s'agit d'approches qui raisonnent directement sur les modèles d'applications notamment au niveau des diagrammes uml.

Cibles

Si on parcourt les différents travaux de recherche qui ont déjà été réalisés sur le partitionnement logiciel/matériel, on remarque qu'il traite surtout des systèmes embarqués et aussi des systèmes embarqués en temps réel. Un système embarqué est un système électronique spécifique comme un téléphone mobile ou un lecteur mp3, conçu pour effectuer des tâches spécifiques avec des ressources limitées et des contraintes variées (consommation d'énergie, espace mémoire restreint...)

Le partitionnement d'un système entre le matériel et le logiciel a une importance critique car il est le premier impact sur le coût et la performance du système applicatif final. Le fait de diviser les processus applicatifs entre le matériel et le logiciel surmonte les traditionnels problèmes de temps et de consommation (Cela permet de gagner du temps lors de l'exécution d'un programme et d'économiser les ressources utilisées par un logiciel en effectuant une partie du travail au niveau matériel).

Les méthodologies de partitionnement font appel à des systèmes possédant une architecture reconfigurable, CAD, une architecture avec du matériel pouvant être configuré pour qu'il soit plus adapté aux tâches qu'on souhaite lui confier. Dans cette optique, les systèmes les plus utilisés sont ceux qui placent la logique reconfigurable à l'intérieur du cœur de processeurs ou l'inverse, comme les systèmes CSoC (Configurable System on Chip), RSoC (Reconfigurable System on Chip), SoPC (System on Programmable Chip) et SoRC (System on Reconfigurable Chip). Contrairement aux architectures ayant une unité reconfigurable qui est connectée à un processeur hôte, ces systèmes permettent de faire face aux problèmes de performances qui restent souvent limitées par les délais de communication et de reconfiguration.

Le partitionnement logiciel/matériel ouvre de nouvelles perspectives pour le développement de produits qui consomment peu d'énergie mais qui sont très rapides comme les applications embarquées (lecture de la puce de carte bancaire avec chiffrement et déchiffrement des informations), la communication, le multimédia (encodage de vidéos, traitement de photos) et les systèmes de transports intelligents.

Expression haut niveau

La reconfigurabilité

Un algorithme peut être implémenté en matériel (utilisant un Application-specific integrated circuit (ASIC)) ou en logiciel en utilisant un micro-processeur. Un ASIC est très rapide et efficace mais il n'est pas destiné à un usage général. Une fois, un ASIC optimisé pour un travail donné, il ne peut plus être reconfiguré. Une solution plus flexible est d'implémenter l'algorithme comme un ensemble d'instructions qui peut être exécuté par un micro-processeur. Sans altérer le matériel, le micro-processeur peut être reprogrammé en changeant l'ensemble d'instructions. Cependant le micro -processeurs doit lire et décoder chaque instruction ce qui induit une surcharge significative. Le matériel reconfigurable combine la flexibilité des micro-processeurs avec la vitesse des ASICs. Le matériel reconfigurable le plus utilisé est FPGA dont la propriété la plus importante est qu'un tel matériel peut être utilisé pour créer des circuits spécifique à l'application qui peuvent accroitre les performances des CPU habituels. De plus cela permet de gagner en vitesse d'exécution. Le matériel reconfigurable est utilisé comme base pour construire des ordinateurs reconfigurables. Les ordinateurs reconfigurables font référence à la possibilité de reconfiguré à la demande un matériel qui avait été auparavant configuré pour une tâche spécifique. Avec ce concept vient l'idée d'augmenter le but général d'un processeur avec des matériaux reconfigurables. De cette manière, des parties logiciels peuvent être accélérées en matériel. Finalement, il est possible de distinguer deux types de reconfigurabilité :

• La reconfigurabilité statique (ou compile-time reconfiguration, noté CTR) : selon ce mode de reconfiguration, chaque application consiste en une configuration (ou un contexte) unique. Pour reconfigurer un tel système, on doit l’interrompre pour procéder à la reconfiguration et le redémarrer avec la nouvelle configuration ;
• La reconfigurabilité dynamique (ou run-time reconfiguration, notée RTR) : Il y a deux modes de reconfiguration dynamique selon la manière de construire des contextes ;
  • La reconfiguration dynamique totale (ou global RTR) : chaque application est divisée en un ensemble de configurations temporelles distinctes dont chacune occupe la totalité des ressources matérielles du composant. On distingue deux types de composants reconfigurables dynamiquement et totalement selon la structure de leurs mémoires de configuration :
    • Les unités reconfigurables à contexte unique. Elles possèdent un plan de configuration unique (plan de mémoire Static Random Access Memory (SRAM) contenant les données de configuration). Tout changement de contexte implique la reconfiguration totale du composant qui nécessite un temps de l’ordre de quelques millisecondes dans de nombreuses architectures de ce type. Ceci limite l’utilisation de ce genre de composants à des applications où la fréquence de changements au niveau matériel est relativement faible : de l’ordre de quelques heures, jours ou semaines ;
    • Les unités reconfigurables multi-contextes : elles possèdent plusieurs plans de configuration. Un plan de configuration unique peut être actif à un certain moment sur le reconfigurable mais le passage à un autre plan peut être très rapide (de l’ordre de quelques nanosecondes). Dans le même sens, il y a aussi des architectures qui ont opté pour l’utilisation de la notion de cache de reconfiguration. Elle consiste à stocker un nombre de configurations dans des buffers (généralement en mémoire locale du composant) et de changer de contexte pendant l’exécution en un temps comparativement très faible par rapport à un chargement de contexte à partir d’une mémoire externe;
  • La reconfiguration dynamique partielle (ou local RTR) : dans ce mode reconfiguration, on reconfigure sélectivement une zone du composant, ce qui réduit considérablement le temps de reconfiguration. On distingue deux principaux types de reconfiguration dynamique partielle :
    • Les unités reconfigurables partiellement : Ces composants permettent de reconfigurer sélectivement une zone du composant alors que le reste du système reste inactif tout en conservant ses informations de configuration. Le temps de reconfiguration dans ce cas dépend de la surface en ce qui concerne les éléments logiques du contexte à reconfigurer ;
    • Les unités à reconfiguration partielle à chaud ou active : permet de reconfigurer sélectivement une zone de l’architecture pendant que le reste du composant poursuit son fonctionnement. Elle est basée sur le concept de ’matériel virtuel’ qui est similaire à l’idée de mémoire virtuelle. Plusieurs contextes peuvent être actifs à la fois sur le composant selon le nombre de zones actives. Le temps de reconfiguration d’un contexte sur une zone de ce composant est masqué par l’exécution d’un autre contexte sur une autre zone.

La reconfiguration en général offre d’énormes opportunités, sur le plan des performances, du fait qu’elle permet d’adapter plus étroitement le composant matériel à la nature du traitement, et sur le plan de l'adaptabilité (flexibilité) du fait qu’elle permet de réagir à des stimuli venant :

• de l’environnement (une Qualité de service (QoS) donnée par l’utilisateur utilisant la reconfiguration partielle) ;
• du système lui-même (des résultats intermédiaires de calcul, des valeurs de capteurs...) en changeant de mode (mode basse consommation, mode dégradé, mode haute résolution...).

Le couplage

Dans le cadre du partitionnement logiciel/matériel, l’architecture peut contenir plusieurs cœurs basés sur différents modèles de traitement et qui participent à l’exécution de l'application. Les parties critiques d’une application sont identifiées puis affectées à un cœur de traitement spécial ou reconfigurable, afin d’en accélérer le traitement.

En tirant parti des propriétés respectives des systèmes programmables et des systèmes reconfigurables il est possible d’améliorer l’adéquation du système global avec l’application développée. C'est l'un des principes de l'approche "plateforme" qui privilégie la généricité et la flexibilité. Dans une approche mixte, le partitionnement de l’application influence le niveau de couplage entre le processeur et le coprocesseur.

La finesse du partitionnement fixe le degré de communication nécessaire entre chaque partie.

Il existe trois modes de couplage d’une ressource reconfigurable avec un processeur. Le premier mode consiste à coupler la partie reconfigurable avec le processeur comme un périphérique. Les échanges s’effectuent par l’intermédiaire du bus d’entrées/sorties à l’aide, par exemple, d’accès DMA (Direct Memory Access). Le temps de latence est élevé, mais la bande passante disponible assure une alimentation efficace de la ressource reconfigurable. Les traitements peuvent s’effectuer en recouvrement avec ceux du processeur.

Il est possible aussi de coupler directement le processeur et l’accélérateur matériel reconfigurable via un bus local, c’est le second mode. Après reconfiguration, le reconfigurable manipule les données stockées dans la mémoire du processeur, sans intervention du processeur.

Le troisième mode de couplage est direct : le processeur et l’accélérateur sont intégrés sur la même puce de silicium. La ressource reconfigurable est placée dans les chemins de données internes du processeur ce qui minimise le temps de latence.

Circuit logique programmable

Un FPGA (field-programmable gate array, réseau de portes programmables in situ) est un matériel composé de blocs logique et d'un réseau de routage. Un bloc logique est de manière générale constitué d'une table de correspondance (LUT ou Look-Up-Table) et d'une bascule (Flip-Flop en anglais). La LUT sert à implémenter des équations logiques ayant généralement 4 à 6 entrées et une sortie. Elle peut toutefois être considérée comme une petite mémoire, un multiplexeur ou un registre à décalage. Le registre permet de mémoriser un état (machine séquentielle) ou de synchroniser un signal (pipeline). Les blocs logiques, présents en grand nombre sur la puce sont connectés entre eux par une matrice de routage configurable. Ceci permet la reconfiguration à volonté du composant, mais occupe une place importante sur le silicium et justifie le coût élevé des composants FPGA.

Dans le cadre du matériel reconfigurable, comme vu plus haut, il existe un type de circuit qu'il est possible de configurer en fonction de la tâche. On parle alors de circuit logique programmable (FPGA). Il existe deux types de technologies pour ce genre composant reconfigurable selon que la configuration est effectuée en utilisant des éléments Anti-Fuse ou des mémoires SRAM. La technologie Antifuse utilise un fort courant électrique pour créer la connexion entre deux fils et est généralement non-reprogrammable. La technologie basée sur les SRAM permet de reconfigurer le composant en chargeant différents bits de configuration dans les cellules mémoire SRAM.

Résoudre le problème de partitionnement avec un tel système peut être effectué en plusieurs étapes :

1. Analyse de code : Dans cette étape du partitionnement, un graphe des processus est créé. Cela est réalisé grâce à l'analyse des fonctions de configuration des entrées du programme. Finalement, on obtient un graphe orienté dans lequel les sommets représentent les processus et les liaisons des flux de données.
2. Collecte de données : Tout l'algorithme de partitionnement est basé sur un ensemble d'informations sur les processus (temps d'exécution du logiciel, temps d'exécution du matériel, espace nécessaire. Après que le graphe des processus ait été construit, chaque processus est exécuté individuellement à la fois sur le CPU pour obtenir le temps d'exécution logiciel et sur le FPGA pour obtenir le temps d'exécution matériel et l'espace occupé.
3. Le partitionnement proprement-dit : En se basant sur les informations collectées et modélisées aux précédentes, le partitionnement proprement-dit peut être réalisé en utilisant un algorithme de partitionnement. Les différentes techniques de partitionnement sont décrites dans la section Algorithme.

La granularité

La granularité d’un composant reconfigurable représente la taille du plus petit élément fonctionnel. Les FPGAs ont typiquement une faible granularité avec des unités fonctionnelles à deux ou à quatre entrées (bien qu’il existe des architectures de FPGA intégrant des multiplieurs sur des mots de 18 bits). D’autres architectures reconfigurables implémentent des unités arithmétiques à plus gros grain (32 bits pour le Chameleon par exemple, pour plus d'informations, le site de l'architecture Chameleon est en lien externe). Typiquement, un composant reconfigurable est configuré en chargeant dans celui-ci une séquence de bits (ou bitstream). Le temps de chargement est directement proportionnel à la taille de la séquence. Les architectures à gros grain nécessitent des séquences plus courtes que les architectures à grain fin donc un temps de configuration plus faible. Une faible granularité procure une plus grande flexibilité d’adaptation du matériel à la structure de calcul souhaitée mais elle entraîne un temps de configuration important. De plus, le grand nombre d’interconnexions entre les unités rajoute un délai conséquent à l’exécution du module implanté (malgré des structures permettant de réduire ce délai, comme les chaînes de propagation de retenue que l’on peut trouver maintenant sur quelques FPGA).

On peut distinguer deux types de granularité : la granularité de traitement, la granularité de la communication.

Granularité de traitement

Les architectures reconfigurables considèrent généralement deux types de granularités : grain fin et gros grain. Le premier correspond à des ressources logiques souvent de type LUT (Look Up Table). Les LUT sont de petite mémoire que l’on retrouve dans le FPGA. Elles sont capables de réaliser n’importe quelle fonction booléenne simple sur ses entrées. Le deuxième concerne plutôt des architectures construites autour des matrices d’ALU, voir des cœurs de processeurs élémentaires. D’autres architectures gros grain sont composées d’opérateurs arithmétiques de type additionneur, multiplieur ou MAC. Souvent les architectures reconfigurables sont hétérogènes, c'est-à-dire qu’elles ont des ressources de calcul de granularités différentes. Nous pouvons avoir par exemple dans la même architecture une partie grain fin pour traiter les manipulations binaires et des parties avec une granularité plus importante pour les calculs arithmétiques.

Granularité de la communication

Certaines architectures, vu le nombre de connexions, utilisent des réseaux de connexion locaux. Les connexions se font alors point à point. Ce type de réseaux facilite les communications locales en limitant le nombre de connexions possibles au niveau global. La connectivité des modules est assurée par les matrices de connexions configurables. Ces dernières diminuent les performances pour des communications éloignées (en fréquence de fonctionnement et consommation de puissance) et nécessitent des outils de placement routage efficaces. Dans les technologies actuelles, les délais des commutations sont bien inférieurs à ceux de la propagation des signaux le long des fils. Les connexions longues distances sont donc lentes et consommatrices d’énergie.

Modèle

Le partitionnement opère sur un modèle de l'application (ou une spécification). Le choix du formalisme pour décrire l'application a donc un fort impact sur la qualité des résultats. Ces modèles de description ont en général été développés pour spécifier un comportement ou une structure et/ou vérifier des propriétés. C'est un moyen clair permettant de saisir la fonctionnalité désirée d’un système. Étant donné une séquence de valeurs en entrée, une spécification permet de déterminer ce que devrait être la réponse du système.

Réseau de Petri

Un réseau de Petri ordinaire décrit une relation de causalité entre les évènements affectant un système (changement d'état, modification d'une variable, etc.), ce qui les ordonne dans le temps. Le temps est pris en compte de manière qualitative. Plusieurs modèles fondés sur les réseaux de Petri permettent de prendre en compte le temps de manière quantitative en associant des durées (des temporisations) aux transitions ou aux places comme les réseaux de Petri temporisés, les réseaux de Petri temporels et les réseaux de Petri stochastiques.

Pour avoir une idée du partitionnement logiciel/matériel, il est intéressant de se baser sur une approche où le système est décrit en Occam. Car un programme Occam est construit par la combinaison de processus primitif et qu'il est facile de les représenter. Dans ce cadre-là, pour préserver la sémantique de la description originale, le partitionnement est le résultat de l'application d'un ensemble de règles au programme. Ces règles incluent le fractionnement de la description en Occam en un ensemble de processus de communication. Une fois que le choix des processus logiciels est fait, un processus de clustering peut démarrer. Durant cette phase, il y a des règles de regroupement des processus en cluster selon leur similarité, leur coût de communication et la minimisation du coût de propagation. Le processus de clustering est guidé par une analyse de temps réalisé dans un réseau de Petri des processus. L'avantage de l'utilisation d'un réseau de Petri est la possibilité d'appliquer des techniques formelles pour une analyse quantitatives et qualitatives ainsi qu'une famille de formalisme qui partagent les mêmes principes de base dans les spécifications de l'architectures utilisées permettant ainsi une étape de transformation entre les différents aspects de la conception. Le processus de partitionnement est réalisé en utilisant un algorithme à plusieurs étapes hiérarchiques de clustering. Cet algorithme construit un arbre de cluster (figure : Construction d'un arbre de cluster) en utilisant une matrice de distance.

Construction d'un arbre de cluster

Cette matrice fournit la distance entre deux objets. Après la construction de cet arbre, il est divisé en cluster (figure découpage de l'arbre de cluster) en suivant une fonction qui observe les possibilités de partage des ressources et les coûts de propagation.

Découpage de l'arbre de cluster

Finalement, le processus de clustering génère N objets où 1 est implémenté par le logiciel et N - 1 par le matériel.

Approche par l'UML

La modélisation et la simulation du design et de l'implémentation de systèmes comme les systèmes embarqués en temps réels sont de plus en plus abordées selon les canons de ingénierie dirigée par les modèles (de l'anglais Model Driven Engineering noté MDE) . Dans ce contexte, le langage de modélisation unifié (de l'anglais Unified Modeling Language noté UML) a été adopté pour représenter différentes vues de systèmes avec leurs propriétés fonctionnelles, qui correspondent aux fonctionnalités que le système doit réaliser, et non fonctionnelles, qui représentent les fonctionnalités du système comme la sécurité, la performance et la portabilité. La mise en œuvre d'une telle modélisation permet une meilleure compréhension de la conception du système même pour les personnes ayant peu d'expérience avec le système modélisé.

La méthodologie de partitionnement comprend trois étapes :

1. Modélisation de système ;
2. L'extraction automatique de l'architecture et des modèles d'applications. Dans le cadre de système embarqué en temps réel, ces modèles devront être annotés avec MARTE qui est un profil UML pour le développement de système en temps réel (Site du projet en lien externe) ;
3. L'analyse de planification et le partitionnement.

Pour passer des modèles UML vers un modèle de la plateforme d'exécution, il est nécessaire d'utiliser un outil. Dans le cadre de système en temps réels, un outil pouvant être utilisé est Real Time Design Trotter (associé à l'acronyme RTDT). Le processus de partitionnement avec cet outil est le suivant :

• Dans un premier temps, les exigences de l'application et de l'architecture sont spécifiées y compris les contraintes de dépendance, de puissance, de consommation d'énergie et particulièrement les contraintes de temps. Cette description est réalisée en UML/MARTE.
• Ensuite, à l'aide des spécifications, une modélisation de l'application et l'architecture est créé. On obtient ainsi un modèle applicatif et un modèle d'architecture en RTDT. Le modèle d'application donne des informations sur les tâches en traitement, comme le comportement (temps d'exécution, période, etc.), des contraintes de temps, les coûts dynamique et statique et ainsi de suite. Tandis que le modèle d'architecture représente la plate-forme d'exécution.
• Enfin RTDT produit une analyse de planification du partitionnement. Cette étape est basée sur la transformation d'XML Metadata Interchange (XMI) provenant des sources UML vers un XMI pour le système ciblé par les modèles créés à l'étape précédente. Cette transformation est basée sur Kermeta

La figure ci-dessus résume ces différentes étapes.

De l'UML vers le partitionnement

Modélisation du problème en flux de données

Il est possible de représenter les problèmes de partitionnement sous la forme d'un graphe d'un flux de données. Chaque nœud du graphe représente un module de base de travail. Et le problème de partitionnement et de savoir où placer ces nœuds, en matériel ou en logiciel. Le partitionnement logiciel peut donc être formalisé de cette manière :

Pour un ensemble d'objets système :

$G=(N,A)$

Où N est l'ensemble de toutes les nodes du graphe de flux de données et A indique l'ensemble des arcs dans de modèle de données.

$(i,j)\in A,i,j\in N$

Et le partitionnement logiciel/matériel peut être défini comme une collection H et S

$H=\{h_{1},h_{2},....,h_{n}\},H\in N$

$S=\{s_{1},s_{2},...,s_{n}\},S\in N$

Où H représente le matériel et S le logiciel.

Les conditions suivantes doivent être satisfaites:

$H\cup S=N$

$H\cap S=\varnothing$

La fonction cible peut être définie de cette manière :

$f(H,S),H\subset N,S\subset N$

Le problème de partitionnement est d'obtenir une valeur minimum pour $f(H,S)$ en respectant les contraintes énoncées ci-dessus. Si on modélise l'application, on peut la représentée comme une collection $p=\{p_{1},p_{2},...,p_{n}\}$, chaque élément P étant implémenté en logiciel ou matériel. Le but du système de partitionnement est d’assigner les éléments de P, CAD, décider la méthode d'implémentation de ces éléments, soit matériel, soit logiciel. Mais le temps total d'exécution doit être minimal. Supposons un vecteur X qui est l'affection de P (la solution du problème). $X=\{x_{1},x_{2},...,x_{n}\}$. Dans lequel les xi appartiennent à l'ensemble (0,1) et xi=1 signifie une implémentation matérielle tandis que xi=0 signifie une implémentation logiciel. Comme le matériel et le logiciel s'exécute en parallèle, le temps total d'exécution de l'application est décrit comme ceci :

$T(x)=Max\{H(x),S(x)\}$

Où H(x) est le temps total d'exécution de l'implémentation matérielle et S(x), le temps total de l'implémentation logicielle.

Algorithme

La coconception logicielle/matérielle de systèmes embarqués peut être le plus simplement représentée par un diagramme classique en Y :

Diagramme-Y

L'une des principales étapes de conception est celle du partitionnement (figure ci-dessus). Dans le cas général, cette étape se subdivise en quatre parties:

1. Une partie qui effectue l’allocation en choisissant le type et le nombre de ressources matérielles et logicielles nécessaires.
2. Une partie qui effectue le partitionnement spatial en prenant des décisions sur l'affectation (assignation) des tâches sur le matériel et le logiciel.
3. Une partie qui effectue le partitionnement temporel en agençant les tâches matérielles dans des segments temporels (ou contextes) différents.
4. Une partie qui effectue l’ordonnancement des exécutions des tâches et des communications.

Le problème d'allocation et d'ordonnancement est un problème NP-difficile dans sa forme générale, dû au grand nombre de paramètres à considérer. Beaucoup d'heuristiques ont été proposées sur la base de différentes techniques dont l'objectif est de satisfaire les nombreuses contraintes de conception (coût, performance, surface, consommation, flexibilité...).

Compilation

L'approche de compilation est la plus classique du partitionnement. Le résultat de partitionnement est valable (optimisé au mieux) pour toutes les exécutions du système. Pour cela le pire est cas est envisagé : WCET (Worst-Case Execution Time). Afin de garantir la satisfaction des contraintes. C'est ici un travail de partitionnement Off-line (hors ligne) qui nécessite une préanalyse de l'application, de l'architecture et de l'environnement d'exécution.

Le recuit simulé

Le recuit simulé (RS) est inspiré du processus de recuit dans l'industrie (la matière est chauffer puis refroidie rapidement ou lentement de manière contrôlé pour avoir des propriétés complètement différentes), l'idée du RS est de simulé le processus de l'industrie pour fournir une solution optimale pour le problème du partitionnement.
Quand la température est élevée, les atomes peuvent se déplacer vers les états d'énergie les plus élevés. Mais, avec la baisse de la température (on parle alors de paliers de température) la probabilité de ces déplacements (ou mouvements) est réduite. Dans la procédure d'optimisation, l'énergie d'un état correspond à l'inverse de la valeur de la fonction qualité. La température devient un paramètre de contrôle qui va être réduit durant l'exécution de l'algorithme.
À chaque itération, après un mouvement, un voisin de la solution courante est retenu, s'il est meilleur que la solution courante. Dans le cas contraire, la température courante est retenu ainsi que le mouvement avec une probabilité fonction de la différence de qualité. Les premières itérations accordent une probabilité élevée d'accepter des mauvaise solutions, mais avec la baisse de température, l'acceptation devient de moins en moins possible. Les principaux inconvénients résident dans le choix des paramètres : température initiale, décroissance de la température, critères d'arrêt... Ces paramètres sont souvent choisis de manière expérimentale.

L'algorithme génétique

Les algorithmes génétiques (AG) sont des algorithmes d'optimisation s'appuyant sur des techniques dérivées de l'évolution naturelle : croisements, mutations et sélections basées sur la survie du meilleur. L'avantage de l'AG se trouve dans sa capacité à résoudre des problèmes NP. En considèrent le nombre de paramètres pour résoudre le problème du partitionnement, l'AG semble être une solution. L'objectif est d'adapter une espèce aux changements de son environnement. Les étapes suivantes présentent l'AG :

1. créer la population initiale
2. calculer et évaluer la santé de chaque individu dans la population.
3. répéter l'itération jusqu'à la fin
   1. choisir les meilleurs individus pour se reproduire
   2. utilisez la roulette de sélection pour choisir les populations à générer de la prochaine génération (opérations génétiques)
   3. croisement
   4. mutation
   5. calculer et évaluer la santé de chaque individu dans la population.

L'AG semble répondre favorablement d'après les résultats de Shuang Dou, en comparaison à un algorithme de recherche exhaustive. L’expérimentation a été réalisé en C sur un Intel Pentium Dual 1.80GHZ et 0.99GB RAM.

Algorithme	Blocs	temps système (ms)	espace	temps d’exécution (ms)
AG	1011110	246	110	0.3270
recherche exhaustive	1011110	246	97	0.4295

List Scheduling

L'objectif du list scheduling est de traverser une liste de nœuds (plus communément du nœud père aux nœuds feuilles) et sur chaque nœud, une implantation est choisie pour minimiser une fonction objective. La limite de cette méthode est que le fait de traverser en série la liste des nœuds conduit à des décisions locales qui peuvent conduire à des solutions éloignées de l'optimum.
L'algorithme GCLP (Global Criticality/Local Phase) essaie de surmonter cet inconvénient. À chaque nœud, il choisit d'une façon adaptative l'objectif approprié de l'implémentation. Le choix est fait suivant le critère GC (Global Criticality) qui estime le temps critique à chaque étape de l'algorithme. Si le temps est critique, une fonction objective qui minimise le temps d’exécution est choisie, sinon une autre fonction qui minimise la surface est prise en compte.
Le critère Local Phase (LP) est utilisé dans le choix de la fonction objective. Ainsi une classification des nœuds est ajoutée au list scheduling, avec pour base l'hétérogénéité et les propriétés intrinsèques. Un nœud est classé en "extrémité" (LP1), en "repeller" (LP2) ou en "normal" (LP3). Le processus est répété jusqu'à ce que toutes les tâches soient implémentées.

Automatisation/Semi-automatisation

Les approches de partitionnement automatique et semi-automatique sont en général plus récentes que l'approche compilation. Il s'agit d'une étude off-line (hors ligne) et suivi d'une analyse complémentaire online (en ligne). L'approche de partitionnement automatique marque une différence, avec l'approche de compilation et semi-automatique, en l’absence de tout ou une partie du traitement effectué off-line. Cette approche peut donc résoudre à la demande le problème du partitionnement online, en parallèle avec l’exécution de application.
Une étape d'analyse du code de l'application est réalisée afin de détecter les boucles logicielles critiques du point de vue du temps d'exécution. Celles-ci sont implémentées en reconfigurable pour diminuer la consommation d'énergie. Pour ce faire, il est nécessaire d'avoir les spécifications du système VHDL (Hardware Description Language) à partir duquel il faut générer un modèle VHDL constitué de deux ensembles de processus d'interactions. Le premier ensemble sera les processus pour l'implémentation matérielle tandis que l'autre ensemble contiendra les processus pour l'implémentation logicielle. Ensuite, ces ensembles sont compilés avec un compilateur VHDL. Le pré partitionnement est compris en trois étapes (cf figure ci-dessous):

Architectural design

1. L'extraction des boucles et sous-routines : Des boucles et des sous-routines sont extraites de l'ensemble initiale des processus pour être placées dans des processus séparés. Le but est d'identifier les sections d'une implémentation qui prennent le plus de temps d'exécution au sein d'un processus. Ces sections pourront être considérées pour une implémentation matérielle. Ces sections étant séparées du processus original, il faudra établir un processus de communication entre les processus matériels et logiciels qui n'affectent que les processus spécifique à la communication. Par cette manière, la sémantique original du VHDL peut être préservée. La technique de communication est une technique basé sur l'envoi et la réception de message entre les processus;
2. Génération et partitionnement du graphe des processus : Cette étape crée des ensembles de processus, un pour le matériels et les autres pour le logiciel. Cette tâche est formulée comme un problème de graphe de partitionnement. Chaque nœud du graphe correspond à un processus des nouvelles spécifications VHDL réalisées à l'étape 1. La connexion entre deux nœuds précise qu'il existe un canal de communication entre ces processus. En d'autres mots, cela signifie qu'il y a au moins signal qu'un processus envoi et que l'autre reçoit. De plus, sur chaque liaison, il y a un poids faisant référence au nombre de communication entre les deux processus. Une fois ce graphe construit, le graphe est divisé entre un sous-graphe matériel et un sous-graphe logiciel. Cette division est réalisée en fonction du poids. Certaines limites de poids définissent les bornes des sous-graphes.;
3. Récupération de certains processus qui ont été divisés à l'étape 1 : A la première étape certains processus enfant ont été séparés de leur processus parent. Après l'étape 2, il est possible que certains enfants se retrouvent dans la même partition que leur parent. Il faut donc les fusionner.

Exemples d'algorithmes

Une méthode algorithmique ciblé sur les systèmes MPSoC (systèmes multiprocesseurs intégrés sur puce), proposé par H. Youness, est de séparer le processus de partitionnement en 2 tâches distinctes : Le processus de planification et le processus de partitionnement. L'objectif principal est de prévoir les tâches les plus longues pour pouvoir les exécuter par le matériel et ainsi avoir un gain de performance sur le temps d'exécution. Cette étape de planification utilise l'algorithme A* comme algorithme de recherche spatial d'état. Le processus de planification optimise la planification des tâches en cas de multiprocesseurs homogènes. Tandis que l'autre processus utilise le graphe de tâches à poids et à niveaux, généré par l'étape précédente, sur le système MPSoC en utilisant le matériel ou le logiciel. Ces processus ont l'avantage d'utiliser des algorithmes rapides, de minimiser le temps d'exécution en utilisant un graphe de tâches, et en réduisant la communication du Bus.

N. Li propose, en 2005, d'utiliser l'algorithme de colonies de fourmis (ACF) sur l'architecture suivante : Processeurs S3C4510 fonctionnant sur un noyau multitâche, avec un composant matériel ASIC ou FPGA. Les critères sont l'espace mémoire, le temps d’exécution et le coût du système. l'ACF est présenté avec quatre étapes:

1. Initialisation de Production de Fourmi : les colonies de fourmis sont d'abord produites. Elles sont placées sur l'état initial tandis que l'on donne aussi la valeur de phéromone initiale de q à cette étape. Toutes les permutations possibles constituent un espace de recherche. Chaque étape contient plusieurs états. L'ordre des états, de chaque étape peut être une solution faisable du problème.
2. Égalisation de santé : La santé de toutes les fourmis est évaluée avec une fonction objective. Avec la santé évaluée de chaque fourmis, une phéromone peut être ajoutée.
3. Expédition de Fourmi : Les fourmis sont expédiées, basées sur la distance et le niveau de phéromone. Chaque fourmi choisit l'état/espace suivant pour se déplacer.
4. Critères d'arrêt : Le processus de calcul continu jusqu'à ce que le nombre d'itérations atteint le seuil maximum prédéfini, ou si la fonction objective atteigne la valeur maximale admissible. Tous les tours visités par les fourmis à chaque itération doit être évaluée. Le meilleur chemin choisi parmi toutes les itérations implique la solution d'ordonnancement optimal pour le problème.
   

En guise de conclusion, N. Li, compare l'algorithme de colonies de fourmis avec d'autres, tel que l'algorithme génétique et la programmation évolutive. l'ACF obtient de bonnes performances, du point de vue du temps d’exécution et du speed up.

En 2010, XiaoHua Liu propose d'utiliser la programmation dynamique basé sur les diagrammes de flux de données. L'idée est d'utiliser la programmation dynamique pour diviser le problème du partitionnement en sous-problèmes, puis à partir des solutions de ces sous-problèmes, obtenir la solution du problème général. Plusieurs solutions sont possibles, et chacune d'entre elles est une valeur optimale (minimum ou maximum). Il y a quatre sous-problèmes :

1. trouver la nature des solutions optimales i et décrire leurs caractéristiques
2. définition récursive de la valeur optimale
3. calculer la valeur optimale avec la méthode "bottom to up"
4. selon les valeurs précédentes, construire la solution optimale

L'architecture, utilisée par XiaoHua Liu, est un Pentium III 800 simulé sur un environnement Matlab. Les résultats de simulation montrent qu'a petite échelle, la programmation dynamique est faisable pour le problème du partitionnement.

il y a d'autres méthodes qui accordent une grande attention à l'algorithme lui-même, tels que l'algorithme de l'évolution, programmation en nombres entiers, algorithme de simulation de recuit, programmation dynamique et l'algorithme de colonies de fourmis...

Annexes

Bibliographie

• (en) H. Youness, M. Hassan, K. Sakanushi, Y. Takeuchi, M. Imai, A. Salem, A. Wahdan et M. Moness, « A high performance algorithm for scheduling and hardware-software partitioning on MPSoCs », 4th International Conference on Design & Technology of Integrated Systems in Nanoscal Era,‎ avril 2009, p. 71-76 (ISBN 978-1-4244-4320-8)
• (en) Silviu Horia Baranga et Adriana Szekeres, « Software/Hardware Partitioner », Roedunet International Conference,‎ septembre 2009, p. 252-257 (ISBN 978-1-4244-7335-9)
• (en) Na Li et YAN-JUN FANG, « Software/Hardware partition in multiple processors embedded system », Conference on Machine Learning and Cybernetics,‎ août 2005, p. 165-170 (ISBN 0-7803-9091-1)
• (en) Yang Liu et Qing Cheng Li, « Hardware Software Partitioning Using Immune Algorithm Based on Pareto », International Conference on Artificial Intelligence and Computational Intelligence,‎ novembre 2009, p. 176-180 (ISBN 978-1-4244-3835-8)
• Karim Ben Chehida, « Méthodologie de Partitionnement Logiciel/Matériel pour Plateformes Reconfigurables Dynamiquement », Thèse de L’UNIVERSITE DE NICE-SOPHIA ANTIPOLIS,‎ novembre 2004
• (en) Jigang Wu, Sun Qiqiang et T. Srikanthan, « Multiple-choice hardware/software partitioning: Computing model and algorithms », Conference on Computer Engineering and Technology,‎ avril 2010, p. 61-65 (ISBN 978-1-4244-6347-3)
• (en) Jigang Wu, Lei Ting et T. Srikanthan, « Efficient Approximate Algorithm for Hardware/Software Partitioning », Conference on Computer and Information Science,‎ juin 2009, p. 261-265 (ISBN 978-0-7695-3641-5)
• (en) XiaoHua Liu, Yuan Da et Li JinJiang, « A hardware/software partitioning algorithm based on data flow chart », Conference on Computer Design and Applications,‎ juin 2010, p. 28-31 (ISBN 978-1-4244-7164-5)
• (en) G. Marosy, Z. Kovacs et G. Horvath, « Effective mars rover platform design with Hardware / Software co-design », International Symposium on Design and Diagnostics of Electronic Circuits & Systems,‎ avril 2009, p. 148-152 (ISBN 978-1-4244-3341-4)
• (en) Jigang Wu, T. Srikanthan et Guang Chen, « Algorithmic Aspects of Hardware/Software Partitioning: 1D Search Algorithms », Transactions on Computers,‎ avril 2010, p. 532-544 (ISSN 0018-9340)
• (en) Dou Shuang, Ding Shan, Zhang Shi et Zhu Liucun, « GA-based algorithm for hardware/software partitioning with resource contentions », Conference on Advanced Computer Control,‎ mars 2010, p. 68-72 (ISBN 978-1-4244-5845-5)
• (en) Z. Pele, D. Majstorovic et M. Katona, « An Approach for Software/Hardware Co-design in Embedded Systems », Conference on the Engineering of Computer Based Systems,‎ septembre 2009, p. 19-23 (ISBN 978-1-4244-4677-3)
• (en) Lee Trong-Yen, Fan Yang-Hsin, Cheng Yu-Min, Tsai Chia-Chun et Hsiao Rong-Shue, « Enhancement of Hardware-Software Partition for Embedded Multiprocessor FPGA Systems », Conference on Intelligent Information Hiding and Multimedia Signal Processing,‎ novembre 2007, p. 19-24 (ISBN 978-0-7695-2994-3, OCLC 213473212)
• (en) Yessine Hadj Kacem, Adel Mahfoudhi, Hedi Tmar et Mohamed Abid, « From UML/MARTE to RTDT: A model driven based method for scheduling analysis and HW/SW partitioning », Conference on Computer Systems and Applications,‎ mai 2010 (ISBN 978-1-4244-7716-6)
• (en) An Liu, Jinfu Feng et Jie Hu, « Research on SoC Hardware/Software Co-design Platform based on MDA », Conference on Computer-Aided Industrial Design & Conceptual Design,‎ novembre 2009, p. 2105-2109 (ISBN 978-1-4244-5266-8)
• (en) Lanying Li et Min Shi, « Software-Hardware Partitioning Strategy Using Hybrid Genetic and Tabu Search », Conference on Computer Science and Software Engineering,‎ décembre 2008, p. 83-86 (ISBN 978-0-7695-3336-0)
• (en) Paulo Maciel, Edna Barros et Wolfgang Rosenstiel, « Computing communication cost by Petri nets for hardware/software codesign », IEEE International Workshop on Rapid System Prototyping,‎ juin 1997, p. 44-56 (ISBN 0-8186-8064-4)
• (en) Fred Cruz Filho, Paulo Maciel et Edna Barros, « A Petri net based approach for hardware/software partitioning », Symposium on Integrated Circuits and Systems Design,‎ septembre 2001, p. 72-77 (ISBN 0-7695-1333-6)
• (en) Petru Eles, Zebo Peng et Alexa PDoboli, « VHDL system-level specification and partitioning in a hardware/software co-synthesis environment », The 3rd international workshop on Hardware/software co-design (CODES '94),‎ 1994, p. 49-55 (ISBN 0-8186-6315-4)
• (en) Mingxuan Yuan, Xiuqiang He et Zonghua Gu, « Hardware/Software Partitioning and Static Task Scheduling on Runtime Reconfigurable FPGAs using a SMT Solver », Real-Time and Embedded Technology and Applications Symposium,‎ 2008 2008, p. 295-304 (ISBN 978-0-7695-3146-5)
• Fakhreddine Ghaffari, « Partitionnement en ligne d’applications flots de données pour des architectures temps réel auto-adaptatives », Thèse de Université de Nice-Sophia Antipolis,‎ novembre 2006

Liens externes

• Site de UML MARTE
• Site de l'architecture Chameleon