Institut de Formation Supérieure

CONCLUSION

1. Objectifs atteints

Arrivés à la fin de notre projet, nous pouvons faire le bilan des objectifs que nous avons atteints.

• 
  La réalisation tient compte de la modularité recherchée : nous avons découpé un type en champs que nous avons donné à ranger aux procédures d’alignements selon une certaine heuristique. Nous avons donc séparé la partie analyse du type de la partie rangement en mémoire.
  
• 
  L’allocation mémoire est effective pour tous les types possibles.
  

• 
  Pour la partie de l’alignement des objets en mémoire, la solution mise au point nous a permis de répondre au premier objectif fixé, à savoir : l’optimisation de l’espace mémoire utilisé. En effet, tous les objets sont stockés en mémoire dans l’espace le plus petit possible.
  

2. Critiques objectives

Certaines remarques peuvent encore être formulées et nous en faisons ici une liste.

• 
  Il peut être remarqué une certaine lourdeur du code, qui est à mettre au compte des contraintes de modularité et de récursivité.
  
• 
  Un grand nombre de fichiers est généré pour l’utilisateur (environ 80 pour définir trois types), mais ceci est dû encore à la modularité.
  
• 
  La partie sur le contrôle d’instance du type n’a pas été réalisée (hook, wrapper, debug) => notion sur l’environnement d’exécution pas assez vu en cours (cf. Annexe : Scratchy Development Environment, Reference Manual).
  

• 
  Bien que l’actuelle optimisation mémoire soit efficace, plusieurs tests nous ont démontrés qu’elle n’était pas, dans tous les cas, la meilleure. En effet, nous avons envisagé une autre technique basée sur une recherche par arbre de la meilleure solution. Mais pour garder un rapport temps/qualité suffisamment bon, nous n’avons pas implémenté ce raisonnement.
  

3. Proportions hommes/mois

4. Difficultés

Les principales difficultés de ce projet proviennent du fait que n’importe quel genre de type peut être créé et qu’il fallait concevoir une certaine abstraction entre l’analyse des types et l’alignement mémoire.

5. Perspectives du travail

Arrivés à la fin de notre projet, il nous reste à formuler quelques propositions qui, à notre sens, permettraient d’améliorer la version actuelle du SDE.

En ce qui concerne l’analyse des types :

• 
  Une interface graphique pourrait facilité la création des fichiers *.idl et *.imp.
  
• 
  La génération automatique d’un fichier Makefile faciliterait l’usage des fichiers générés, de même que pour les squelettes de fichiers utilisateurs.
  
• 
  Une séparation entre nos classes java et le langage d’implémentation serait à réaliser.
  

En ce qui concerne l’alignement des objets en mémoire :

• 
  Nous pouvons donc considérer que l’optimisation mémoire selon un algorithme de recherche par arbre fait partie des améliorations possibles du projet.
  
• 
  De plus, le deuxième objectif qui nous était fixé, l’optimisation de la vitesse d’accès mémoire, n’a pas été satisfait pour des raisons de temps. Il est donc possible de poursuivre le projet en répondant à ce critère. Néanmoins, ce travail sera facilité par la structure de l’actuel algorithme qui prend en compte une éventuelle évolution vers cette solution.
  

Ce deuxième objectif impose donc une nouvelle optimisation :
Optimisation 2 : Le temps d’accès aux objets placés en mémoire doit être minimal.

• 
  Enfin, notre alignement actuel utilise une fonction donnant l’alignement d’un objet en fonction de sa taille. La version actuelle de cette fonction est implémentée de manière arbitraire. La version finale doit prendre un fichier de description du matériel utilisé (processeur, mémoire …) et doit retourner l’alignement conforme à cette description.
  

5. ANNEXE

1. Fonction principale de placement des éléments en mémoire

Fonction Remplissage (liste_entrée, liste_sortie, offset_début, offset_fin)

début

ajouter à la liste des trous de structure_englobante le doublet : offset_début, offset_fin

alignement de structure_englobante 1

offset_fin_objet  offset_début

offset_deb_objet  offset_début

taille_restante  offset_fin - offset_début

si taille_restante > 0 alors
// boucle cherchant un objet entrant dans l'espace vide propose

pour i  0 jsq i >= taille de liste_entrée faire

objet_courant  i^ème élément de liste_entrée

taille_objet  taille de objet_courant

si taille_objet <= taille_restante alors
// recherche de l'offset de l'objet

si alignement de objet_courant = -1 // non défini : opaque simple

alors alignement de objet_courant  Alignement_processeur(taille_objet)

fsi

offset_deb_objet  Recherche_offset(offset_début, offset_fin, taille_objet,

alignement de objet_courant)

offset_fin_objet  offset_deb_objet + taille_objet

si offset_deb_objet  -1 alors // si pas d'erreur
// modification de l'offset de l'objet

offset de objet_courant  offset_deb_objet

// déplacement de l'objet modifie

ajouter objet_courant à liste_sortie

retirer objet_courant de liste_entrée
// remplissage de l'espace vide avant l'offset de l'objet

structure_englobante_pre  Remplissage(liste_entrée, liste_sortie,

offset_début, offset_deb_objet)
// remplissage de l'espace vide apres l'offset de l'objet

structure_englobante_post  Remplissage(liste_entrée, liste_sortie,

offset_fin_objet, offset_fin)

// taille de la structure englobante

premier_trou  premier élément de la liste des trous de structure_englobante_pre

dernier_trou  dernier élément de la liste des trous de structure_englobante_post

taille de structure_englobante  dernier_trou.first – premier_trou.second
// offset de la structure englobante

offset de structure_englobante  premier_trou.second

// alignement de la structure englobante

alignement de structure_englobante  ppcm(alignement de structure_englobante_pre,

alignement de structure_englobante_post )

alignement de structure_englobante  ppcm(alignement de structure_englobante,

alignement de objet_courant)
// gestion de la liste de trous

vider la liste des trou de structure_englobante

// ajout des trous dans le cas d'un objet comprenant des trous

pour j  0 jsq j >= taille de la liste des trous de objet_courant faire

premier  premier champ du j^ème élément de la liste des trous de objet_courant

second  second champ du j^ème élément de la liste des trous de objet_courant
// on décale tous les offsets des trous internes à l'objet de son offset et

// on les ajoute à la liste de trous de la structure englobante

ajouter à la liste des trous de structure_englobante le doublet :

offset de objet_courant + premier, offset de objet_courant + second

j  j + 1

fin
// éliminer les espaces mémoire nuls (de type : 20<->20)

si premier élément de la liste des trous de structure_englobante_pre est vide alors

retirer cet élément

ajouter tous les trous de structure_englobante_pre à la liste des trous de structure_englobante

fsi

si premier élément de la liste des trous de structure_englobante_post est vide alors

retirer cet élément

ajouter tous les trous de structure_englobante_post à la liste des trous de structure_englobante

fsi
tri de la liste des trous de la structure englobante
sortir de la boucle for

fsi

fsi

i  i + 1

fait

fsi
retourner structure_englobante

fin

2. Fonction finale d’optimisation mémoire

Variables globales :
début_mémoire  0

fin_mémoire  100000 (arbitraire)

liste_trous  liste composée du seul doublet (début_mémoire  fin_mémoire)

Procédure Optimisation_mémoire_finale (liste_entrée)

début

// indexage de la liste d'entrée pour retourner la liste dans le même ordre

Affect_ordre(liste_entrée)
// trier la liste des opaques

Sort_by_size(liste_entrée)
trier la liste des trous
pour i  0 jsq i >= taille de liste_trous ou taille de liste_entrée <= 0 faire

offset_début  premier champ du i^ème élément de liste_trous

offset_fin  deuxième champ du i^ème élément de liste_trous
// partie remplissage de l'espace mémoire resté vide

structure_englobante  Remplissage(liste_entrée, liste_sortie, offset_début, offset_fin)

// mise à jour de la liste des trous principale

ajouter à liste_trous les éléments de la liste des trous de structure_englobante

// suppression du trou en cours

retirer le i^ème élément de liste_trous

trier la liste des trous

i  i + 1

fait

// remettre dans l’ordre initial des éléments de la liste

vider liste_entrée

ajouter à liste_entrée les éléments de liste_sortie

Sort_by_ident(liste_entrée)

fin

3. Fonction intermédiaire d’optimisation mémoire des structures

Fonction Optimisation_mémoire_structure(liste_entrée)

début

// indexage de la liste d’entrée pour retourner la liste dans le même ordre

Affect_ordre(liste_entrée)
// trier la liste des opaques

Sort_by_size(liste_entrée)
// pour chaque objet de la structure, l'aligner

structure_englobante  Remplissage(liste_entrée, liste_sortie, 0, fin_mémoire)

// suppression du dernier trou n'appartenant pas à la structure englobante

retirer le dernier élément de la liste des trous de structure_englobante

// remettre dans l’ordre initial des éléments de la liste

vider liste_entrée

ajouter à liste_entrée les éléments de liste_sortie

Sort_by_ident(Liste_entrée)

retourner structure_englobante

fin

4. Fonction intermédiaire d’optimisation mémoire des tableaux

Fonction Optimisation_mémoire_sous_tableau(structure, nb_élément)

début

// taille d'un élément du tableau + taille du vide située entre 2 éléments du tableau

taille_elem_tab  taille de structure
// alignement d'un élément du tableau

si alignement de structure = -1 // cas d’un opaque simple

alors alignement de structure  Alignement_processeur(taille)

fsi

alignement  alignement de structure

// calcul de la taille d'un élément du tableau

si taille_elem_tab modulo alignement  0

alors taille_elem_tab  taille_elem_tab + alignement - taille_elem_tab modulo alignement

fsi
// mise à jour de la liste des trous temporaires pour chaque élément du tableau

ajouter à la liste des trous de structure_englobante les élément de la liste des trous de structure

pour i  0 jsq i >= taille de la liste des trous de structure faire

pour j  1 jsq j >= nb_élément faire

déplacement  taille_elem_tab * j

ajouter à la liste des trous de structure_englobante le doublet :

premier champ du i^ème élément de la liste des trous de structure + déplacement,

second champ du i^ème élément de la liste des trous de structure + déplacement

j  j + 1

fait

i  i +1

fait
// ajout dans la liste des trous temporaires situes entre chaque élément

déplacement  taille de structure

taille_vide  taille_elem_tab - déplacement

pour i  0 jsq i >= nb_élément -1 ou taille_vide <= 0 faire

ajouter à la liste des trous de structure_englobante le doublet :

déplacement, déplacement + taille_vide

déplacement  déplacement + taille_elem_tab

i  i + 1

fait
trier la liste des trous de structure_englobante

taille de structure_englobante  taille_elem_tab * (nb_élément - 1) + taille de structure

alignement de structure_englobante  alignement de structure

taille de structure  taille_elem_tab

offset de structure  0
retourner structure_englobante

fin

5. Fonction intermédiaire d’optimisation mémoire des unions

Fonction Optimisation_mémoire_sous_union (liste_entrée)

début

alignement_struct  1

taille_struct  0
pour i  0 jsq i >= taille de liste_entrée faire

struct_tmp  i^ème élément de liste_entrée

// calcul de la taille max de toutes les structures de liste_entrée

taille  taille de struct_tmp

si taille_struct < taille alors taille_struct  taille fsi

// calcul de l'alignement de la structure englobante (ppcm)

align_tmp  alignement de struct_tmp

si align_tmp = -1 alors alignement de struct_tmp  Alignement_processeur(taille) fsi

alignement_struct  ppcm(alignement_struct, alignement de struct_tmp)

i  i + 1

fait
// modification et ajout de la liste des trous provisoire

pour i  0 jsq i >= taille de liste_entrée faire

struct_tmp  i^ème élément de liste_entrée

si taille de struct_tmp < taille_struct

alors ajouter à la liste des trous de struct_tmp le doublet :

taille de struct_tmp, taille_struct

fsi

i  i + 1

fait

liste_trous_tmp  liste des trous du premier élément de liste_entrée

pour i  0 jsq i >= taille de liste_entrée faire

liste_trous_tmp  Intersection(liste des trous du i^ème élément de liste_entrée, liste_trous_tmp)

i  i + 1

fait

ajouter à la liste des trous de structure_englobante les éléments de liste_trous_tmp

trier la liste des trous de structure_englobante

alignement de structure_englobante  alignement_struct

taille de structure_englobante  taille_struct

offset de structure_englobante  0

retourner structure_englobante

fin

6. Fonction de recherche d’offset

Fonction Recherche_offset(offset_début, offset_fin, taille_objet, alignement)

début

i  offset_début

si alignement = 0 alors retourner -1

tant que i modulo alignement  0 et i < offset_fin – taille_objet faire

i  i + 1

fait

si i modulo alignement = 0

alors retourner i

sinon retourner –1

fsi

fin

7. Bibliographie

1. 
   Cabillic G., Lesot J.-P., Banâtre M., Parain F., Higuera T., Issarny V., Chauvel G., D’Inverno D., Lasserre S., Scratchy : a Modular Java Virtual Machine for Embedded Systems, soumis Usenix, TAC 2001.
   

2. 
   Document interne, Solidor, Scratchy Development Environment, Reference Manual, IRISA, 2000.
   

3. 
   Intel, Intel Architecture Software Developer’s Manual dans System Programming Guide, Intel, 1997.
   

4. 
   Pinchinat S., Schmitt V., Polycopié 109 : Algorithmique et Complexité, IFSIC, 2000.
   

5. 
   Tasso A., Livre de java premier langage, Eyrolles, 2000.
   

6. 
   Le Certen P., Ungaro L., Polycopié 103 : Programmation par objets en Java, IFSIC, 2000.
   

7. 
   Delannoy C., Le Livre du C premier langage, Eyrolles, 1994.
   

8. 
   Nebut J.L., Polycopié 81 : Le langage C, IFSIC, 2000.