Next: Évaluation incrémentale
Up: Travaux Théoriques
Previous: Analyse de flot
avec C. JULIé (DEA [Jul86], puis thèse [Jul89]) En collaboration avec Catherine JULIé , nous avons travaillé sur les
méthodes d'optimisation mémoire introduites sur les GA l-ordonnées. Dans ce
domaine il existe un résultat théorique ``gênant'': la recherche d'un schéma
optimal de stockage des attributs devient très vite (même pour des sous-classes
de GA très étroites) un problème NP-complet. Malgré cela, des méthodes ont été
définies dans le cadre des GA l-ordonnées, et donnent des résultats très
satisfaisants, bien que le schéma d'allocation ne soit pas optimal. En effet,
avec la connaissance de l'ordre total d'évaluation, il est possible sous
certaines conditions de décider que tel attribut peut s'implanter, soit en
variable globale soit en pile (c'est-à-dire hors de l'arbre). Nous avons
amélioré ces méthodes au point de déterminer des conditions nécessaires et non
plus seulement suffisantes. Nos résultats pratiques [Jul89,JP90b]
montrent qu'environ 50% à 70% des attributs sont implantés en variables, et
que de 20% à 40% des attributs sont implantés en pile.
Les résultats que nous avons acquis en 1990 nous permettent de stocker hors de
l'arbre, outre tous les attributs temporaires, c'est-à-dire ceux dont la
durée de vie est limitée à une seule visite du n
ud qui les porte, une bonne
partie des attributs non temporaires: ceux qui peuvent être stockés dans des
variables globales ou dans des piles strictes [JP90b,JP90c]. Nous savons
aussi, au moins théoriquement, comment implanter ceux qui restent dans des
piles ``cactus''.
Le fait de pouvoir stocker tous les attributs hors de l'arbre, outre
ses effets bénéfiques sur la consommation de mémoire, permettra d'augmenter la
puissance d'expression des GA en réutilisant les mêmes techniques d'évaluation
(cf. la section 2.10). Ce travail a aussi eu de l'importance pour
d'autre travaux de recherche (cf. la section 2.11 ou la
section 2.12.1).
Didier Parigot
Mon Apr 7 11:02:46 MET DST 1997