Mémoires de Fin d’Etudes
Etablissement
Université de Béjaia - Abderrahmane Mira
Affiliation
Département d’Informatique
Auteur
MERIAMA, Mahamdioua
Directeur de thèse
Ali,Melit (Docteur)
Filière
Informatique
Diplôme
Magister
Titre
Le denombrement des points d’un réseau contenus dans un polytope dans les calculs paralleles
Mots clés
Calcul parallèle: Complexité algorithmique Polytope : Réseau : Dénombrement
Résumé
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 Clause qui est implémenté dans la librairie Polylobe. 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.
Date de soutenance
2008
Cote
004M/117
Pagination
97 f.
Illusatration
Tabl.graph.
Format
30cm
Notes
Bibliogr. f.97 Annexes f.96
Statut
Soutenue