Méthodes de dénombrement de points entiers de polyèdres et applications à l'optimisation de programmes Counting integer points in polyhedra and applications to program optimization Ehrhart, Polynômes d' Pas de mots clés en anglais 518.1 Ehrhart, Polynômes d' Thèses et écrits académiques Optimisation mathématique Thèses et écrits académiques Le modèle polyédrique est un formalisme utilisé en optimisation automatique de programmes. Il permet notamment de représenter les itérations et les références à des tableaux, dans des nids de boucles affines, par des points à coordonnées entières de polyèdres bornés, ou Z-polytopes (paramétrés). Dans cette thèse, trois nouveaux algorithmes de dénombrement ont été développés : des points entiers dans un Z-polytope paramétré, dans une union non disjointe de Z-polytopes paramétrés et dans leurs images par des fonctions affines. Le résultat de ces dénombrements est donné par un ou plusieurs polynômes multivariable à coefficients périodiques. Ces polynômes, connus sous le nom de quasi-polynômes d'Ehrhart, sont définis sur des sous-ensembles de valeurs des paramètres, dits domaines de validité. De nombreuses méthodes d'analyse et d'optimisation de nids de boucles affines font appel à ces algorithmes. Nous les avons en particulier appliqués à la linéarisation de tableaux, dont l'objectif est la compression mémoire et l'amélioration de la localité spatiale. Outre l'optimisation de programmes, les algorithmes proposés ont des applications dans bien d'autres domaines, tels que les mathématiques et l'économie. The polyhedral model is a well-known framework in the field of automatic program optimization. Iterations and array references in affine loop nests are represented by integer points in bounded polyhedra, or (parametric) Z-polytopes. In this thesis, three new counting algorithms have been developed: counting integer points in a parametric Z-polytope, in a union of parametric Z-polytopes and in their images by affine functions. The result of such a counting is given by one or many multivariate polynomials in which the coefficients may be periodic numbers. These polynomials, known as Ehrhart quasipolynomials, are defined on sub-sets of the parameter values called validity domains or chambers. Many affine loop nest analysis and optimization methods require such counting algorithms. We applied them in array linearization which achieves memory compression and improves spatial locality of accessed data. Besides program optimization, the proposed algorithms have many other applications, as in mathematics and economics. Electronic Thesis or Dissertation Text fr France PDF https://publication-theses.unistra.fr/public/theses_doctorat/2006/SEGHIR_Rachid_2006.pdf Université de Strasbourg Strasbourg Seghir Rachid 1977-01-01T00:00:00 FR 132637162 http://www.theses.fr/2006STR13208 2006STR13208 2006-12-07T00:00:00 Informatique Université Louis Pasteur (Strasbourg) 026404540 Doctorat Docteur es non oui Mongenet Catherine 113506996 Loechner Vincent 114245908 École doctorale Mathématiques, sciences de l'information et de l'ingénieur (Strasbourg ; 1997-....) ED269 156504863 ddc:510