Dénombrement des points d'un réseau contenus dans un polytope dans les calculs parallèles.

Abstract

La parallélisation automatique permet de convertir automatiquement un programme séquentiel à une version qui peut être directement exécutée en parallèle sans toucher la sémantique du programme séquentiel. Les parties de ce dernier qui portent généralement plus de parallélisme sont les nids de boucles. Par nature, la plupart des nids de boucles qui apparaissent dans des programmes sont affines. Le domaine d’itération d’un nid de boucles affines peut être décrit par les points entiers appartenant à un polytope. Les problèmes d’analyse et d’optimisation de nids de boucles - nécessaires dans la parallélisation automatique - se réduisent souvent au comptage de points entiers dans des polytopes. Le résultat du comptage peut être donné par un ou plusieurs polynômes ayant des coefficients périodiques. Ces polynômes sont connus sous le nom de quasi-polynômes d’Ehrhart. Le travail réalisé dans ce mémoire consiste en l’élaboration d’un algorithme de dénombrement de points entiers pour une famille de polyèdres (enveloppes convexes de n points à coordonnées entières affinement indépendants dans un espace affine de dimension n) basée sur la méthode d’interpolation pour le calcul de quasi-polynômes d’Ehrhart. L’évaluation de son temps de calcul et la présentation des données en entrée sont comparés à ceux d’algorithme d’interpolation de Clauss qui est implémenté dans la librairie Polylib. Notre algorithme est plus rapide pour la résolution du problème restreint à la classe de polyèdres considérés. Mots clés : Dénombrement, Points entiers, Polytope, Quasi-polynômes d’Ehrhart, Parallélisation automatique.