Mapping multi Objectifs d‘application intensive Sur architecture MPSOC B.FARID, AH.BENYAMINA Dept. Informatique Université d’Oran, Algérie Dept. Informatique Université d’Oran, Algérie farid.pgia@Gmail.com benyanabou@yahoo.fr Résumé— Ce travail nous permet de vulgariser une phase très démarche proposant une solution globale hybride basée sur les importante du cycle de développement des systèmes embarqués : algorithmes génétiques, Dijkstra multi objectif et la méthode la conception software. Dans cette phase, le défi à relever est celui Branch and bound. 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 II. DEFINFITION ET FORMULATION différentes approches exactes et heuristiques tout en adoptant un modèle permettant de représenter une structure à différents Les communications entre les tâches de notre application et niveaux d’abstraction, dans le but d’être plus proche des les composantes de notre architecture cible sont représentées problèmes d’association d’arbre hiérarchique : application et par deux graphes orientés. architecture. A. Définition 1 Mots clés— MPSoC, NOC, Dijkstra, Optimisation multi- Le graphe d‗application (TG : Task Graph) est un graphe objectifs, algorithme génétique, Branch and bound. orienté G(T,E) où chaque sommet représente un module (tâche) de l‘application et l‘arc orienté ( , ) noté I. INTRODUCTION représente les communications entre les modules et . Le poids de l‗arc noté par représente le volume des Un système embarqué [1] peut être défini comme un système électronique et informatique autonome ne possédant communications de à (Fig1). 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 Fig. 1 Graphe d‘application 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 B. Définition 2 ensemble de processeurs P = {P1,P2, . . .,Pn} .Comme le graphe d‗architecture NT (NoC Topology graph) est un hypothèse les processeurs Peuvent fonctionner en plusieurs graphe orienté P(S,F) où chaque sommet représente un modes m1, m2,m3. (Mettre les processeurs en plusieurs modes nœud de la topologie et l‗arc ( , ) noté par représente nous donne plus de diversité dans l‘optimisation de un lien physique direct entre les éléments de et de placement) l‗architecture. Le poids de l‗arc noté par représente la bande passante,l‘energié consomé et la latence disponible à  Le temps d‘exécution (D): travers le lien physique (Fig. 2). 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. ( ) () Soit : le plus court chemin entre et , alors : ( ∑ ( )) ( | |) | | Donc () () Après l‘ordonnancement: ( ) /i=1……nombre de tâche Tel que : : Le temps total d‘exécution ( ) : La durée d'exécution d‘une tâche i placée sur un Fig. 2 Graphe d‘architecture 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 Le mapping du graphe d‗application G(T,E) sur le graphe considération les communications. d‗architecture P(S,F) est définit par la fonction de mapping ( ) : Le nombre de cycles nécessaires d‘une tache pour suivante : s‘exécuter sur un processeur. map : T → , s.t map ( )= . : La fréquence d‘horloge d‘un processeur au mode m. le mapping est définit si : (Fig3). ( ) : 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): Energie d‘exécution : ( ) () Energie de communication : ∑ ( ) Energie totale : ∑ ( ) Tel que : ( ) : L‘énergie consommée par la tâche i affectée au processeur j au mode m Fig. 3 Mapping de graphe de tache sur architecture NOC : Energie d‘exécution unitaire : La consommation d‗énergie due à la communication de la tâche i C. Formulation mathématique : La consommation d‗énergie totale, en prenant en considération la consommation des processeurs et des liens. Notre application est définie comme un ensemble de tâches [7], T = {t1, t2, . . ., tn}, et l‘architecture cible comme un III. METHODE DE RESOLUTION mais, l'analyse des propriétés du problème permet d'éviter Le problème à résoudre dans sa globalité est un problème l'énumération de larges classes de mauvaises solutions. Dans d‘assignation, d‘affectation et d‘ordonnancement «AAS». un bon algorithme par séparation et évaluation, seules les Ceci consiste principalement à assigner et ordonnancer les solutions potentiellement bonnes sont donc énumérées [9]. taches et les communications de l'application sur les ressources d'architecture cible de telle façon que les objectifs L‘algorithme de branch and bound se résume par : spécifiés soient atteints. Dans notre approche il y‘a des objectifs à respecter comme la minimisation de la consommation d‘énergie, maximisation du Algorithm 2 Algorithme Branch and baund temps de Performance. Ces objectifs sont très importants car le fonctionnement des systèmes embarqués mobiles dépendent Initialisation : Best_Sol =∞; Bi ( p0 ) : f ( p0 ) ; de la durée de vie de la batterie [10] ce qui nécessite la p  ( p0 , Bi ( p0 )) réduction de la consommation d´énergie et maximiser de la vitesse d'exécution ce qui revient à dire minimiser le temps Tant que p   faire d'exécution. En réalité ces objectifs sont contradictoires car en Sélection: sélectionner un nœud p de P : réduisant l´énergie consommée on va augmenter le temps p := p /{ p }; d‘exécution des composants(CPU), fonctionnant en mode économie. Pour cela, on est obligé de faire du multi-objectifs Pour i=1 …k faire afin de trouver un compromis entre les différents objectifs Evaluation Bi ( pi ) : f ( pi ) contradictoires. Si ( Bi ( pi )  f ( x) ), x réalisable et ( f (x) < Best_Sol) alors Donc nous proposons une approche multi-objectifs basée sur Best_Sol:= f (x) la technique d‘optimisation par les algorithmes génétiques et Solution := x ; l‘algorithme de B&B pour résoudre notre problème AAS. Sinon 1) Algorithme1: Algorithme génétique(AG): appartient à la Si Bi ( pi ) > Best_Sol alors famille des algorithmes évolutionnistes. Leur but est d'obtenir Elaguer pi ; une solution approchée à un problème d'optimisation, lorsqu'il Sinon n'existe pas de méthode exacte (ou que la solution est Séparation: Décomposer p en inconnue) pour le résoudre en un temps raisonnable. Les algorithmes génétiques utilisent la notion de sélection p1 , p2 ,..., pk ; naturelle et l'appliquent à une population de solutions p  ( pi , Bi ( pi )) potentielles au problème donné [8]. Fin Si Fin Si L‘algorithme génétique se résume par : Fin Pour Algorithme 1 Algorithme Génétique 3) Description de notre approche :  Initialisation de la population. Dans le flot de conception, l‘étape de placement et  Evaluation des fonctions objectives. ordonnancement est directement liée à l‘implémentation de  pour i = 0 à MaxIter faire l‘application sur une architecture spécialisée. Les entrées de  Sélection cette phase sont :  Croisement  Mutation  Un modèle d‘application  Evaluation des fonctions objectives  Un modèle d‘architecture cible  fin pour  Des contraintes de performance et d‘énergie,  Des fonctions objectives à optimiser. 2) Algorithme2: Algorithme de branch and bound (B&B) : La sortie de cette phase est une affectation des différentes Un algorithme par séparation et évaluation, également tâches et communications aux ressources physiques, selon un appelé selon le terme anglo-saxon branch and bound, est une ordonnancement d‘exécution des différentes tâches sur ces méthode générique de résolution de problèmes d'optimisation, ressources. 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 Objectif Début Modèle D‘application Meilleur placement AG Des taches sur Charger à partir disque (Fichier XML) l‘architecture NOC B&B Modèle D‘architecture Contrainte Graphe d‘application Graphe d‘architecture Valider Fig. 4 Problématique de placement et d‘ordonnancement Introduction des paramètres + Lancement des calculs : IV. EXPERIMENTATION ET ANALYSE DES RESULTAT AG ,B&B et Dijkstra 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. Affichage des Après l'exécution de notre approche hybridée (GA et B & B) résultats en utilisant les propriétés et les paramètres de base indiqués (Front Pareto) dans le tableau 1, les résultats obtenus sont comme suit: Fin Algorithme Paramètre de base -Nombre de tache 21 Algorithme -Nombre de processeur 9 génétique -Architecture Topologie en étoile Fig. 5 Le modèle hybride proposé -Latence 1 unité -Taille de la Population 80 -Nombre de Génération 40 -Probabilité de croisement 80% -Probabilité de Mutation 1% B. Affichage des résultats : -Nombre de tache 290 Algorithme -Nombre de processeurs 9 branch&bound -Architecture Mesh 2D (3*3) -Latence 1 unité Tableau1 : représentation des paramètres de base A. Le modèle hybride proposé : Le modèle hybride proposé est illustré par la figure 5 : Fig. 6 Front Pareto pour B&B REFERENCES [1] Y. A. Laribi, ― Environnement de mapping pour la Conception des réseaux sur puce(NoCs),‖ pour obtenir le titre de Magistère. L‘école nationale d‘informatique ESI, Algérie, Juillet 2010. [2] R.A. Mohamed, ― Optimisation multicritère pour le placement d‘applications intensives sur système sur puce (SoC),‖ pour obtenir le titre de Master. l‘Université de Lille Mention : Informatique. Juin 2010. [3] B. Abou-El Hassen, ― Ordonnancement Hiérarchique Multi - Objectif D'Application Embarquées Intensives,‖ thèse pour l'obtention du Diplôme De Doctorat D'Etat, université d‘Oran , Algérie, décembre 2008. [4] B. Henri et H. Matthew , ― Approaches for integrating task and data parallelism,‖ IEEE Concurrency, 6(3):74 –84, Fig. 7 Front Pareto pour AG 1998. [5] A..Benyamina, B.Beldjilali et S.Eltar, ― Time Applications on NoC Architecture with Hybrid Multi-objective PSO Algorithm,‖ COSI'2010 . Ouaragla, Algerie, Avril, 2010. V. CONCLUSIONS [6] A. Liefooghe, B. Matthieu, L. Jourdan, and T. El-Ghazali, Dans cet article nous avons présenté notre approche, basée ― Paradiseo-moeo : A framework for evolutionary multi- sur l‘algorithme Génétique et algorithme de Branch and objective optimization,‖ In Evolutionary Multi-criterion Bound. Ces derniers sont hybridés avec l‘algorithme de plus Optimization (EMO 2007), vol 4403 of Lecture Notes in Computer Science, pp. 386–400, Matsushima, Japan: court chemin dijkstra multi objectifs afin de résoudre le Springer-Verlag, 2007. problème de placement et d‘ordonnancement d‘une [7] A. Abdelkader, ― Ordonnancement multi objectif d‘application application hiérarchique sur une architecture MPSoC. intensif sur une architecture régulières,‖ pour obtenir le Nous considérons pour le moment que notre solution est très diplôme de magistère, université d‘Oran, Algérie, février 2012. efficace parce qu‘on a utilisé une meilleur méta heuristique et exact pour traiter les deux types de taches régulières et [8] T. El-Ghazali, ― Metaheuristics : From Design to irrégulières et assurer le parallélisme de tache et de donnés Implementation,‖ Wiley-Blackwell (an imprint of John Wiley (GILR : Globally Irregular Locally Regular). sons Ltd ), juillet 2009. En attendant des expérimentations et simulations plus [9] M. ashish , ― Allocation, Assignation, et Ordonnancement poussées, nous considérons que notre solution est très efficace pour les systèmes sur puce multiprocesseurs,‖ thèse pour parce qu‘on a utilisé une meilleur méta heuristique et un l'obtention du Diplôme De Doctorat D'Etat, université de Lille , France, décembre 2006. algorithme exact pour traiter les deux types de tâches. [10] A. Mehran,S. Saeidi,A. khademzadeh, and A. Afzali-khusha , ―Spiral : A heuristic mapping algorithm for network on chip,‖ IEICE Electronics Express, 4(15) :478–484, 2007.