CHAPITRE 3
914itfiode exfiaustive
developpie
3.1 Introduction :
Ce chapitre sera consacré à la
présentation de la méthode exhaustive que nous avons
développée. Encore une fois, nous rappelons que le
développement d'une telle méthode est doublement
bénéfique :
- l'exécuter à des fins d'obtention d'une solution
exacte lorsque le temps CPU le permet,
- l'utiliser comme repère pour le développement
d'une méthode approchée à base d'une heuristique ou d'une
méta heuristique
L'exploration exhaustive dans l'espace des solutions
nécessite aussi bien des procédures algorithmiques
adéquates que des structures de données efficaces. Ceci, du fait
que la taille de la mémoire principale est limitée et qu'il faut
judicieusement l'utiliser afin de ne pas recourir à de nombreux
?swappings? entre cette mémoire et la mémoire secondaire
(ce qui est très néfaste pour le temps d'exécution de
l'application).
Ce sont essentiellement ces aspects qui seront abordés,
de manière technique, dans ce chapitre. Auparavant, nous donnerons une
explication globale de notre méthode en nous appuyant sur un
schéma synoptique. Les détails des structures de données
et des formats des enregistrements des fichiers utilisés par notre
application suivront. Enfin, nos procédures algorithmiques,
commentées, seront décrites, puis nous terminerons ce chapitre
par une conclusion qui sera une synthèse du contenu de ce chapitre.
3.2 Présentation générale de notre
méthode:
Notre application, décrite dans la Figure 3.1, se compose
de deux grandes parties: - une partie principale qui contient les fonctions
suivantes :
main (), la fonction récursive configuration (), inserer
(), inserer2 (), inserer3 (),
inserer4 (), calculer_S_T_P (), surface_temps_puissance (),
reporter_t_p (), maj_dp (), maj2_dp ()
- une autre partie qui contient les fonctions suivantes :
create_lists () et la fonction récursive t_arrgts ().
Ces fonctions seront définies et présentées
dans la suite de ce chapitre.
Les fichiers de données utilisés par notre
application sont :
- NB_TRACES : il inclut le nombre de traces dans l'algorithme
à implémenter en Hardware
- DONNEES : il décrit le nombre d'instances dans le
circuit et dans la bibliothèque, et ce, pour chaque type
d'opérateur
- TRACEi : ce fichier décrit pour chaque pas
d'exécution, les opérations qui sont exécutées pour
la trace i (ce fichier est en fait un résultat de la tâche
d'ordonnancement des opérations)
En sortie, les fichiers des résultats obtenus sont :
- DP1, DP2, ..., DPNb_T où Nb_T est le
nombre de traces dans l'algorithme
- T_CPU_AFFECT : indique le temps CPU qui a été
nécessaire pour l'exécution de notre application sur un jeu de
données
Des exemples concrets concernant ces fichiers d'entrée et
de sortie seront ultérieurement donnés afin de rendre plus
compréhensible ce chapitre.
main ()
DONNEES
TRACE1
inserer4 ()
DP2 DPN
DP1
COMBOPS*
create_lists()
inserer ()
t_arrgts ()
OPERATEURS*
DP1
inserer2 ()
inserer3 ()
maj2_dp ()
DP2
INSTANCE*
maj_dp ()
DPN
COMB_TYP_OP*
configuration ()
calculer S_T_P()
TRACE2 TRACEN
T_CPU_AFFECT
NB_TRACES
surface_temps_puissance()
reporter_t_p ()
DP1 DP2
DPN
Figure 3.1 : Schéma synoptique de l'application
| 
