Nid de boucles, modèle polyédrique et parallélisation automatique

Nid de boucles, modèle polyédrique et parallélisation automatique

Modèle polyédrique

Définition 1.3.1 Polyèdre rationnel Un polyèdre rationnel P est l’intersection d’un nombre fini de demi espaces fermés [18]. 11 Un polyèdre est défini par un système d’égalités et d’inégalités : P = x ∈ Q d | Ax ≥ c ∧ A ′x = c ′ avec A ∈ Z m×d , A′ ∈ Z m′×d , c ∈ Z m, c′ ∈ Z m′ , ou m est le nombre des inégalités et m′ est le nombre des égalités [33]. Définition 1.3.2 Polytope Un polytope est un polyèdre borné ou fini. L’image suivante présente des exemples des polytopes : Définition 1.3.3 Dimension (géométrique) d’un polyèdre rationnel La dimension (géométrique) d’un polyèdre rationnel P ⊂ Qd est de la dimension de son enveloppe affine, ou d’autre manière, la dimension d de son espace ambiant Qd moins le nombre d’équations (implicites), linéairement indépendantes. Un polyèdre de dimension d est appelé un d-polyèdre [33]. Définition 1.3.4 Sommet Un sommet de polytope est un point extrême de polytope, c-à-d, il ne peut pas être exprimé par une combinaison convexe de ses autres points [32]. Définition 1.3.5 Rayon Un rayon d’un polyèdre rationnel P est un vecteur non nul r, tel que (x + µr) ∈ P quels que soient x ∈ P et µ ∈ Q avec µ ≥ 0. Un rayon représente une direction vers laquelle le polyèdre va à l’infini [33]. Définition 1.3.6 Ligne Une ligne d’un polyèdre rationnel P est un vecteur non nul l, tel que (x + λl) ∈ P quels que soient x ∈ P et λ ∈ Q. Une ligne est aussi appelée rayon bidirectionnel [33]. Définition 1.3.7 Face, facette Une face F d’un polyèdre rationnel P est l’intersection de P avec {x ∈ Qd |A ′x = c ′}, où A′x ≥ c ′ est un sous système de Ax ≥ c. 12 Les facettes d’un polyèdre rationnel sont ses (n − 1)−faces (faces de dimension n − 1), où n est la dimension (géométrique) du polyèdre. Les faces de dimension 0 sont les sommets du polyèdre [33]. Définition 1.3.8 m- simplexe Si x1, x2, .., xm+1 sont des points affinement indépendant (c-à-d, x2−x1 x3−x1 . . . xm+1−x1 sont linéairement indépendants), alors l’enveloppe convexe de x1, x2, .., xm+1 est nommé m- simplexe (ou simplexe de dimension m) avec les sommets x1, x2, .., xm+1. [18]

Parallélisation Automatique en utilisant le modèle polyédrique

La parallélisation automatique est le processus de conversion automatique de programme séquentiel à une version qui peut être directement exécutée en parallèle sans toucher la sémantique du programme.[13]. La plupart des nids de boucles qui apparaissent dans des programmes sont affines, c’est-à-dire qu’ils s’expriment par des indices bornées par des expressions affines, et des accés à des tableaux par des fonctions affines des indices. On basant sur le modèle polyédrique, chaque instruction entourée par n boucles est présentée par un polytope de dimension n. Les coordonnées d’un point dans le polytope (vecteur d’itération) correspondent aux valeurs des indices des boucles commençant par la boucle extérieure. Chaque point dans le polytope correspond à une instance de l’exécution d’instruction S . Le passage de système d’inéquations au nid de boucles peut être fait par l’élémination de Fourier-Motzkin Définition 2.3.2 Elimination de Fourier-Motzkin Elimination de Fourier-Motzkin est un algorithme mathématique pour éliminer les variables à partir d’un système d’inégalités linéaires. Si on élimine toutes les variables d’un système d’inégalités linéaires, on obtient un système d’inégalités constant . Ce système a des solutions si et seulement si le système d’origine a des solutions. En conséquence, l’élimination de toutes les variables peuvent être utilisées pour détecter si un système d’inégalités a des solutions ou non. Cette méthode est utilisée aussi pour trouver « les boucles de parcours » du polytope, comme illustré

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Liste des figures
Introduction Générale
1 Notions de base
1.1 Introduction
1.2 Définitions mathématiques
1.3 Modèle polyédrique
1.4 Polynôme d’Ehrhart
1.5 Conclusion
2 Nid de boucles, modèle polyédrique et parallélisation automatique
2.1 Introduction .
2.2 Définitions
2.3 Parallélisation Automatique en utilisant le modèle polyédrique
2.3.1 Principe
2.3.2 Démarche .
2.3.3 Dépendances
2.3.4 Transformation de programme
2.4 Optimisation de la mémoire et le calcul parallèle
2.5 Utilisation de nombre de points entiers dans un polytope dans la parallélisation
2.6 Conclusion
3 Méthodes de dénombrement de points entiers dans un polytope et exemples
de l’utilité de ce nombre (État de l’art)
3.1 Introduction
3.2 Méthodes de dénombrement des points dans un réseau polytope
3.2.1 Méthode des sommes
3.2.2 Méthode d’interpolation de Clauss et Loechner .
3.2.3 Méthode des fractions partielles .
3.2.4 Méthode de comptage par automates à états finis déterministes
3.2.5 Méthode de Barvinok pour les polytopes non paramétriques
3.2.6 Généralisation de Méthode de Barvinok pour les polytopes paramétrés
3.2.7 Méthodes approximatives de dénombrement des points entiers dans
un polytope
3.3 Comparaison entre les méthodes
3.4 Exemples d’utilisation de dénombrement des points entiers dans un polytope dans le parallélisation automatique
3.4.1 Optimisation de la localité spatiale par réorganisation des données
3.4.2 Réutilisation des distances .
3.4.3 Optimisation de copier des données de mémoire globale en mémoire
partagée et estimation de trafic mémoire dans GPU .
3.5 Conclusion