Télécharger le fichier pdf d’un mémoire de fin d’études
Le logiciel YAO
Dans ce chapitre, nous faisons une présentation générale de YAO. Nous présentons en détail le graphe modulaire, qui est la structure sous-jacente de YAO. Nous présentons ensuite les directives YAO, qui permettent la création de ce graphe et sa traversée. Avoir unemaîtrise complète de ces aspects est essentiel pour comprendre le reste de ce manuscrit. L’objectif de cette thèse est de traiter l’automatisation de tâches telles que :
– le contrôle de la cohérence et
– la génération automatique de certaines spécifications de l’utilisateur, ainsi que
– la parallélisation automatique du code généré par YAO.
C’est à partir des directives YAO relatives au graphe modulaire et à son parcours que l’analyse de la génération automatique prend forme.
Concept de graphe modulaire
On définit les termes suivants :
– Module : un module F est une entité de calcul, il reçoit un vecteur en entrée et calcule un vecteur en sortie. Le graphe modulaire, qui est présenté ci-dessous,est formé de plusieurs modules, un module reçoit ses entrées d’autres modules ou du contexte extérieur1 au graphe et transmet ses données en sortie à d’autres modules ou au contexte extérieur.
– Connexion de base : on schématise les transmissions de données entre modules par des connexions qui seront appelées par la suite lesconnexions de base. Une connexion de base qui lie la ieme` sortie d’un module Fs (F source) à la jieme` entrée d’un moduleFd (F desti-nation) indique que la ieme` valeur calculée parFs sera transmise à la jieme` entrée deFd . Les transmissions de données vers l’extérieur du graphe seront représentées par desconnexions de base partant de sorties de certains modules et se terminant à des points particulier s que nous appelons output data points. De même la transmission de données du contexte exté-rieur vers les entrées de certains modules se fait par l’intermédiaire deconnexions de base qui débutent en des points qui seront ditsinput data points.
– Graphe modulaire : un graphe modulaire est un ensemble de modules interconnectés. Les modules représentent les sommets du graphe et un arc (orienté) du moduleFs vers le module Fd signifie que Fs transmet une partie de ses sorties à Fd .
La figure 3.1a donne un exemple de modules interconnectés par des connexions de base. Ainsi, le module Fp transmet sa sortie yp1 à l’entrée xq1 de Fq et sa sortie yp2 à l’entrée xq2 de Fq, cette même sortieyp2 sera aussi transmise à l’entrée xl1 de Fl . La figure 3.1a représente donc les connexions de base décrivant la transmission de données, elle montre qu’une seuleconnexion de base peut aboutir à une entrée donnée, mais que plusieursconnexions de base peuvent être issues(a) d’une même sortie. La figure 3.1b montre le graphe(b) modulaire associé au graphe de figure 3.1a, en général un arc du graphe modulaire représente plusieursconnexions de base. Le graphe modulaire décrit donc l’ordonnancement du calcul. Un arc deFs vers Fd indique que le module Fd ne peut déclencher son calcul qu’après celui deFs. Par contre, les connexions de base seront utilisées afin de transmettre les données.
Le graphe modulaire est un graphe sans circuit, il existe donc au moins un sommet d’entrée (sans prédécesseurs) et au moins un sommet de sortie (sans successeurs), on distingue donc trois types de modules :
– Les modules d’ entrée(sans prédécesseurs) reçoivent leurs données uniquement du contexte extérieur du graphe et transmettent leur sorties à d’autres modules ou au contexte extérieur.
– Les modules de sortie (sans successeurs) transmettent leurs sorties uniquement au contexte extérieur du graphe et reçoivent des données d’autres modules ou du contexte extérieur.
– Les modules internes reçoivent nécessairement des entrées des modules prédécesseur set éventuellement du contexte extérieur et transmettent les résultats aux modules successeurs et éventuellement au contexte extérieur.
Le graphe modulaire étant sans circuit, il est alors possible de numéroter les modules suivant un ordre appelé ordre topologique. Ainsi, relativement à cet ordre, l’existence d’un arc de Fs à Fd (Fs → Fd ) implique nécessairement que le numéro attribué Fàs est inférieur au numéro attribué à Fd . L’ensemble des entrées d’un moduleFs constitue un vecteur notéxs, l’ensemble de ses sorties constitue un vecteur notéys (ys= Fs(xs)). De ce qui précède, un module donnéFd ne peut être activé que s’il dispose de son vecteur d’entréexd , ce qui implique que tous ses modules prédé-cesseurs Fs aient préalablement été activés. Les entrées correspondant à desconnexions de base entrant de l’extérieur (à partir des input data point) sont initialisées par le contexte extérieur. Le tri topologique permet de propager correctement le calcul à travers le gr aphe des input data points aux output data points, tous les input data points du graphe sont initialisés par le contexte exté-rieur. La propagation des calculs intermédiaires qui suivent le tri topologique est appelée procédure forward.
Quand un modèle direct complexe peut être décomposé en entités de calcullusppetites, il est alors possible de le représenter par un graphe modulaire. La procédure forward permet de produire la valeur finale recherchée de l’ensemble du calcul de ce modèle direct. Sinous notons x le vecteur correspondant à toutes les valeurs input data point du graphe et y le vecteur correspondant à toutes les valeurs output data point du graphe, le graphe modulaire représente une fonction globale et rend possible de calculer y =(x). Ce calcul est effectué par l’algorithmeforward.
Algorithme 1 Algorithme forward.
Nous supposons que, pour chaque module Fd nous pouvons calculer la fonction Fd (xd ), où xd est son vecteur d’entrée.
1. Initialiser les input data points, on note x le vecteur défini par ses valeurs.
2. Traverser tous les modules en suivant l’ordre topologique. Pour chaque module Fd construire son vecteur d’entréexd , en utilisant les connexions de base, et calculer yd = Fd (xd ).
3. Récupérer le vecteur résultaty sur les output data points du graphe. Ce vecteur représente les sorties de la fonction globale.
Globalement, un graphe modulaire reçoit une partie de ses données sur les entrées de ses mo-dules d’entrée, il propage le calcul dans ce graphe en récupérant éventuellement autresd’ données du contexte extérieur. L’ensemble des données qui seront transmises ua contexte extérieur consti-tue un vecteur y, ce vecteur correspond aux résultats à restituer au contexte extérieur du graphe modulaire. Ainsi, un graphe modulaire peut être considéré lui-même comme un module F . La représentation par graphe modulaire s’applique donc à différents niveaux d’intégration, ce qui permet de former des modèles de plus en plus complexes.
La suite du chapitre montre comment, grâce à la notion de graphe modulaire, on ca lcule le tan-gent linéaire et l’adjoint d’un modèle. Les calculs nécessitent l’application edrésultat de multipli-cations matricielles faisant intervenir, suivant les cas, les matrices jacobiennes de chaque module ou leurs transposées.
Tangent linéaire et adjoint de la fonction globale
Une fois que le modèle direct complexe est représenté par un graphe modulaire, il est pos-sible de proposer deux algorithmes, qui permettent de calculer le modèle tangent linéaire et adjoint de.
Modèle tangent linéaire d’un graphe modulaire
On suppose que, dans le cadre d’un graphe modulaire, qui implémente unefonction, on sait calculer le tangent linéaire de chaque moduleFp, celui-ci se calcule pour une perturbation dxp (en un point de référencexp). On note Fp la matrice correspondante au tangent linéaire, qui est égale à la matrice jacobienne de Fp calculée enxp, la perturbation correspondante en sortie du module est égale à dyp = Fpdxp. De la même façon que le vecteur d’entréexp, le vecteur dxp provient des perturbations en sorties des modules prédécesseurs deFp ou des perturbations transmises par le contexte extérieur.
Le tangent linéaire du modèle global peut se calculer par une propagation avant dans le graphe de façon similaire à la procédure forward. L’algorithme linward décrit cette procédure. Un exemple de ce calcul est donné en figure 3.2.
Algorithme 2 Algorithme linward.
Avant de déterminer le tangent linéaire de la fonction globale pour une entrée donnéex, tous les vecteurs d’entréexp des différents modulesFp doivent être déterminés. Ceci est fait en exécutant la procédureforward avec x en entrée.
1. Initialiser la perturbation dx en attribuant à chaque input data point i du graphe sa perturba-tion correspondante dxi.
2. Traverser tous les modules en suivant le tri topologique. Pour chaque module Fp, considérer son vecteur de perturbation d’entréedxp. Cela peut être fait en transmettant les perturbations calculées de la sortie de ses modules prédécesseurs, ou de ceux initialiséspar le contexte extérieur pour lesinput data points. Ensuite calculer dyp = Fpdxp (la matrice jacobienne Fp est calculée au point de référencexp).
3. Récupérer le vecteur résultatdy sur les output data points du graphe. Ce vecteur représente le produit matriciel dx.
Modèle adjoint d’un graphe modulaire
Comme pour le modèle tangent linéaire, on suppose que l’on sait calculer le modèle adjoint de chaque module. Ainsi, pour un module Fp, ayant en entrée un vecteurxp, s’il reçoit un vecteur dyp de même dimension que son vecteur de sortie, son modèle adjoint calculé enxp est alors dxp = FTp dyp, qui a la même dimension que le vecteur d’entrée deFp. La matrice FTp est la transposée de la matrice jacobienne du module Fp calculée au pointxp. On démontre alors (voir annexe B), que l’on peut calculer le modèle adjoint du modèle global pour chaque vecteur dy ayant la même dimension que son vecteur de sortie (dx = T dy). On a besoin pour faire ce calcul de parcourir le graphe dans l’ordre topologique inverse, ce qui revient à utiliser les ar cs en sens opposé, il s’agit du parcours en passe arrière, ou rétropropagation, du graphe modulaire.
Cet algorithme nécessite, pour chaque module sourceFs, la définition de deux vecteurs αs et βs. Le vecteur αs a la même dimension que le vecteur d’entrée du moduleFs et on notesi son ieme` élément. Le vecteurβs a la même dimension que le vecteur de sortie du moduleFs et on note s j son jieme` élément. En outre, les paramètres sont également définis pour lesoutput data points et les paramètres sont définis pour les input data points. Nous notonsi le paramètre de l’output data point i et j le paramètre de l’input data point j. Si (s, j) est l’indice de la jieme` sortie de Fs, on note :
– SUCCM(s, j) l’ensemble d’indices (d, i), où i est la ieme` entrée du moduleFd , qui prennent la valeur de (s, j) en entrée.
– SUCCO(s, j) l’ensemble de tous les output data points, qui prennent la valeur de (s, j) en entrée. Si j est un input data point, nous notons SUCCI( j) l’ensemble des indices (d, i), où i est la ieme` entrée du moduleFd , qui prend sa valeur de l’input data point j.
L’adjoint du modèle global peut se calculer par une rétropropagation dans le graphe. L’algo-rithme backward décrit cette procédure. Un exemple de ce calcul est donné en figure 3.2.
Algorithme 3 Algorithme backward.
Avant d’exécuter cet algorithme, les vecteurs d’entréexs de tous les modules Fs doivent être cal-culés. Pour cela, il est nécessaire d’exécuter l’algorithmeforward avec le vecteur d’entréex. Pour chaque output data point j, nous supposons que la perturbation correspondante est déjà définie par dy j .
1. Initialiser les paramètres ai relatifs aux output data points i du graphe en faisant ai = dyi.
2. Traverser tous les modules dans le sens inverse du tri topologique. Pour chaque module Fs calculer βs et αs comme suit :
– Pour l’ensemble de ses indices de sortie (s, j), effectuer les opérations suivantes afin de calculer βs :
a) affecter bs j = 0,
b) si SUCCM(s, j) n’est pas vide alors calculer bs j = å(d,i)∈SUCCM(s, j) adi,
c) si SUCCO(s, j) n’est pas vide alors calculer bs j = bs j + åi∈SUCCO(s, j) ai.
– Calculer αs = FTs βs, où FTs est la transposée de la matrice jacobienne deFs calculée au point de référencexs.
3. Pour chaque input data point j, calculer b j = å(d,i)∈SUCCI( j) adi.
Le vecteur dx, dont les composantes sont les b j de tous les input data points du graphe, vérifie dx = T dy, où dy est le vecteur dont les composantes sont les valeurs dyi définies aux output data points du graphe.
Remarque : Les deux algorithmes linward et backward supposent que l’on peut calculer le tangent linéaire et l’adjoint de chaque moduleFs. Les modules peuvent avoir une très différente complexité. Dans un cas simple, où le module est une fonction analytique, on peut calculer la matrice jacobienne Fs explicitement et calculer les produits Fsdxs et FTs dys. En outre, il est im-portant de définir le graphe modulaire, afin d’avoir des modules simples (pe tites entités de calcul) ainsi le calcul analytique de Fs devient facile. En ce qui concerne des modules plus complexes, l’utilisateur peut utiliser des logiciels qui font ces calculs, par exemple un code obtenu en utilisant un logiciel de différentiation automatique [Griewank et Walther, 2008, Hascoët et Pascual, 2004, Naumann et al., 2006, Giering et Kaminski, 1998]. Un module lui même peut être un graphe mo-dulaire, un réseau de neurones multicouches ou un programme précompiléAinsi. le formalisme de graphe modulaire permet de combiner différentes méthodes pour construire des modèles de calcul complexes. Les algorithmes 2 et 3 permettent, grâce au parcours avant et arrière du graphe, de calculer directement les résultats du tangent linéaire et de l’adjoint pour des modèles complexes.
|
Table des matières
1 Introduction
2 Principes théoriques de l’assimilation variationnelle
2.1 Introduction et notations
2.2 Calcul de l’adjoint
2.3 Méthode incrémentale
2.4 Quelques extensions
2.4.1 Transformation du vecteur d’état
2.4.2 Prise en compte du bruit du modèle, méthode duale
2.5 Conclusion
3 Le logiciel YAO
3.1 Concept de graphe modulaire
3.2 Tangent linéaire et adjoint de la fonction globale G
3.2.1 Modèle tangent linéaire d’un graphe modulaire
3.2.2 Modèle adjoint d’un graphe modulaire
3.3 Représentation d’une application par graphe modulaire
3.4 Mise au point d’expériences de simulation et/ou d’assimilation
3.5 Présentation de YAO
3.5.1 Le fichier description
3.5.2 Le fichier instructions
3.5.3 Les fichiers module
3.5.4 Le fichier chapeau
3.5.5 Applications et quelques considérations techniques
3.6 Présentation de quelques directives de description
3.6.1 Directive trajectory
3.6.2 Directive space
3.6.3 Directive module
3.6.4 Directive ctin
3.6.5 Directive order
3.7 Exemple numérique : le Shallow-water
3.8 Implémentation des méthodes incrémentales et duales dans YAO
3.9 Conclusion
4 Cohérence dans l’ordre de calcul
4.1 Introduction
4.2 Règles de vérification : cas des références relatives
4.3 Algorithme de cohérence
4.4 Références absolues
4.5 Résultats et conclusion
5 Génération automatique des directives order
5.1 Graphe de Dépendance Réduit (GDR)
5.2 Analyse structurelle du GDR
5.3 Anomalies dans la définition des ctin
5.4 Méthode de génération des directives order
5.4.1 Présentation de la méthode
5.4.2 Procédures de génération
5.5 Fusion de boucles
5.5.1 Fusion par mise en niveaux
5.6 Références absolues dans la génération automatique
6 Génération automatique de codes parallèles
6.1 La génération de code
6.1.1 Quelques aspects génériques du générateur YAO
6.1.2 Génération de la procédure forward
6.2 Une technique de parallélisation de directives order existantes
6.2.1 Décomposition de domaine
6.2.2 Un algorithme de parallélisation automatique de la procédure forward
6.2.3 Exemple de l’acoustique marine
6.3 Parallélisation lors de la génération automatique des directives order
6.4 Génération et parallélisation de la procédure backward
7 Conclusion et perspectives
Annexes
A Checkpointing
A.1 Stockage des sorties de la procédure forward
A.2 Analyse de l’allocation mémoire
A.2.1 L’application de l’acoustique marine
A.2.2 L’application NEMO
A.3 Recalculer versus stocker
A.4 Une application à YAO
A.4.1 Possible extension à l’espace
B Démonstration de la formule de la procédure backward
C Stockage de matrices et performances du programme séquentiel
Index
Télécharger le rapport complet
