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.
