=Paper=
{{Paper
|id=None
|storemode=property
|title=Mapping Multi Objectifs d'une Application Intensive sur Architecture MPSOC
|pdfUrl=https://ceur-ws.org/Vol-942/paper_9.pdf
|volume=Vol-942
}}
==Mapping Multi Objectifs d'une Application Intensive sur Architecture MPSOC==
https://ceur-ws.org/Vol-942/paper_9.pdf
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.