Résumé- Ce travail nous permet de vulgariser une phase très importante du cycle de développement des systèmes embarqués : la conception software. Dans cette phase, le défi à relever est celui d'une application hiérarchique NOC hétérogène. Ceci Dans le but de satisfaire des objectifs contradictoires et de fournir des résultats dans des délais raisonnables. Nous utilisons pour cela les différentes approches exactes et heuristiques tout en adoptant un modèle permettant de représenter une structure à différents niveaux d'abstraction, dans le but d'être plus proche des problèmes d'association d'arbre hiérarchique : application et architecture.
objectifs, algorithme génétique, Branch and bound.
Un système embarqué [1] peut être défini comme un système électronique et informatique autonome ne possédant pas d‘entrées/sorties standards comme un clavier ou un écran. On peut avoir un ou plusieurs systèmes embarqués sur puces (SOC, System On Chip), de nature hétérogènes et donc complexes. Ils sont souvent constitués de plusieurs processeurs de types différents (FPGA, DSP, GP par exemple), avec des fonctions dédiées ou reconfigurables [4]. Les applications embarquées qu‘on a l‘habitude de traiter sont généralement complexes [2] et parfois sont hiérarchiques telles les encodeurs MPEG, H263, H264…….etc. Ce type d‘applications est caractérisé par des parties le constituant de types différents. L‘un a trait au traitement irrégulier, l‘autre a trait au traitement régulier [3]. Ce dernier représente le calcul intensif qu‘on trouve en grande partie dans les applications temps réel embarquées [5]. A ces deux types d‘applications correspondent deux types de traitements parallèles l‘un est dit (irrégulier) correspond au parallélisme de taches et l‘autre (régulier) corresponde au parallélisme de données. C‘est pour cette raison et afin d‘avoir plus de performance qu‘on ne traite pas ce type d‘application dans sa globalité avec une seule stratégie. Pour faire le mapping de ce type d‘application on dont réaliser le mapping des deux parties le constituant différemment. Ce qui nous amène à proposer une stratégie hybride sous le mapping hiérarchique constitué d‘une part de stratégie de mapping pour le globale irrégulier et d‘une stratégie pour le locale régulier [6]. D‘où notre démarche proposant une solution globale hybride basée sur les algorithmes génétiques, Dijkstra multi objectif et la méthode Branch and bound.
II. DEFINFITION ET FORMULATION
Les communications entre les tâches de notre application et les composantes de notre architecture cible sont représentées par deux graphes orientés.
Le graphe d‗application (TG : Task Graph) est un graphe orienté G(T,E) où chaque sommet représente un module (tâche) de l‘application et l‘arc orienté ( , ) noté représente les communications entre les modules et . Le poids de l‗arc noté par représente le volume des communications de à (Fig1).
le graphe d‗architecture NT (NoC Topology graph) est un graphe orienté P(S,F) où chaque sommet représente un noeud de la topologie et l‗arc ( , ) noté par représente un lien physique direct entre les éléments de et de l‗architecture. Le poids de l‗arc noté par représente la bande passante,l‘energié consomé et la latence disponible à travers le lien physique (Fig. 2).
Le mapping du graphe d‗application G(T,E) sur le graphe d‗architecture P(S,F) est définit par la fonction de mapping suivante : map : T → , s.t map ( )= . le mapping est définit si : (Fig3).
Notre application est définie comme un ensemble de tâches [7], T = {t1, t2, . . ., tn}, et l‘architecture cible comme un ensemble de processeurs P = {P1,P2, . . .,Pn} .Comme hypothèse les processeurs Peuvent fonctionner en plusieurs modes m1, m2,m3. (Mettre les processeurs en plusieurs modes nous donne plus de diversité dans l‘optimisation de placement)
Le temps d‘exécution (D): Soit une tâche (Ti) place sur un processeur (Pj), calculer la communication Dcom(i) revient à chercher le plus court chemin entre (Pj) et tout autre processeur (PL), là où les tâches successeurs sont placées.
( )
( (
| () |) ( ) ∑ |
| ( ) /i=1……nombre de tâche () : le plus court chemin entre et , alors : ( )) Tel que : : Le temps total d‘exécution
( ) : La durée d'exécution d‘une tâche i placée sur un processeur j s'exécutant au mode d‘exécution m (sans prendre en compte les communications).
: Le temps total d‗exécution d‗une tâche i en prenant en considération les communications.
() : Le nombre de cycles nécessaires d‘une tache pour s‘exécuter sur un processeur.
: La fréquence d‘horloge d‘un processeur au mode m. () : Durée de communication prise le transfert de données (résultat) de la tâche (i) ver ses successeurs. : Quantité de données échangées entre les tâches i et k ( | |): La bande passante minimale dans le chemin de à .
L‘énergie consommée (E):
( ) ( ∑
) () ( ) Tel que :
( ): L‘énergie consommée par la tâche i affectée au processeur j au mode m : Energie d‘exécution unitaire
: La consommation d‗énergie due à la communication de la tâche i
: La consommation d‗énergie totale, en prenant en considération la consommation des processeurs et des liens.
Le problème à résoudre dans sa globalité est un problème d‘assignation, d‘affectation et d‘ordonnancement «AAS». Ceci consiste principalement à assigner et ordonnancer les taches et les communications de l'application sur les ressources d'architecture cible de telle façon que les objectifs spécifiés soient atteints.
Dans notre approche il y‘a des objectifs à respecter comme la
minimisation de la consommation d‘énergie, maximisation du
temps de Performance. Ces objectifs sont très importants car
le fonctionnement des systèmes embarqués mobiles dépendent
de la durée de vie de la batterie [
Donc nous proposons une approche multi-objectifs basée sur
la technique d‘optimisation par les algorithmes génétiques et
l‘algorithme de B&B pour résoudre notre problème AAS.
1) Algorithme1: Algorithme génétique(AG): appartient à la
famille des algorithmes évolutionnistes. Leur but est d'obtenir
une solution approchée à un problème d'optimisation, lorsqu'il
n'existe pas de méthode exacte (ou que la solution est
inconnue) pour le résoudre en un temps raisonnable. Les
algorithmes génétiques utilisent la notion de sélection
naturelle et l'appliquent à une population de solutions
potentielles au problème donné [
L‘algorithme génétique se résume par :
Algorithme Génétique
Croisement Mutation Evaluation des fonctions objectives fin pour 2) Algorithme2: Algorithme de branch and bound (B&B) :
Un algorithme par séparation et évaluation, également
appelé selon le terme anglo-saxon branch and bound, est une
méthode générique de résolution de problèmes d'optimisation,
et plus particulièrement d'optimisation combinatoire ou
discrète. C'est une méthode d'énumération implicite : toutes
les solutions possibles du problème peuvent être énumérées
mais, l'analyse des propriétés du problème permet d'éviter
l'énumération de larges classes de mauvaises solutions. Dans
un bon algorithme par séparation et évaluation, seules les
solutions potentiellement bonnes sont donc énumérées [
Initialisation : Best_Sol =∞; Bi ( p0 ) : f ( p0 ) ; Sélection: sélectionner un noeud p de P : p := p /{ p }; Pour i=1 …k faire
Evaluation Bi ( pi ) : f ( pi )
Si ( Bi ( pi ) f (x) ), x réalisable et ( f (x) < Best_Sol) alors
Best_Sol:=
f (x)
Solution := x ; Sinon
Si Bi ( pi ) > Best_Sol alors
Elaguer pi ; Sinon
Séparation: Décomposer p en p1, p2 ,..., pk ;
p ( pi , Bi ( pi ))
Fin Si
Fin Si
Fin Pour
Dans le flot de conception, l‘étape de placement et ordonnancement est directement liée à l‘implémentation de l‘application sur une architecture spécialisée. Les entrées de cette phase sont :
La sortie de cette phase est une affectation des différentes tâches et communications aux ressources physiques, selon un ordonnancement d‘exécution des différentes tâches sur ces ressources.
AG B&B
Meilleur placement
Des taches sur l‘architecture NOC
IV. EXPERIMENTATION ET ANALYSE DES RESULTAT Pour le développement de notre approche, on a opté pour le langage de programmation JAVA, et toutes les expériences ont été réalisées sur un Pentium double core 2.04 GHZ sous Windows 7.
Après l'exécution de notre approche hybridée (GA et B & B) en utilisant les propriétés et les paramètres de base indiqués dans le tableau 1, les résultats obtenus sont comme suit:
Le modèle hybride proposé est illustré par la figure 5 : Charger à partir disque (Fichier XML) Graphe d‘application
Graphe d‘architecture Début
Valider Introduction des paramètres
+ Lancement des calculs :
AG ,B&B et Dijkstra
Affichage des
résultats (Front Pareto)
Fin
Dans cet article nous avons présenté notre approche, basée sur l‘algorithme Génétique et algorithme de Branch and Bound. Ces derniers sont hybridés avec l‘algorithme de plus court chemin dijkstra multi objectifs afin de résoudre le problème de placement et d‘ordonnancement d‘une application hiérarchique sur une architecture MPSoC. Nous considérons pour le moment que notre solution est très efficace parce qu‘on a utilisé une meilleur méta heuristique et exact pour traiter les deux types de taches régulières et irrégulières et assurer le parallélisme de tache et de donnés (GILR : Globally Irregular Locally Regular).
En attendant des expérimentations et simulations plus poussées, nous considérons que notre solution est très efficace parce qu‘on a utilisé une meilleur méta heuristique et un algorithme exact pour traiter les deux types de tâches.