Méthodes de dénombrement de points entiers de polyèdres et applications à l'optimisation de programmes
Institution:
Université Louis Pasteur (Strasbourg) (1971-2008)Disciplines:
Directors:
Abstract EN:
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.
Abstract FR:
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.