Approaches to Assess Validity of Derivatives and to Improve Efficiency in Automatic Differentiation of Programs

Overview & Synopsis

Ce travail concerne la Differentiation Automatique (DA) de codes. La DA transforme un programme calculant une fonction mathematique en un nouveau programme calculant ses derivees, gagnant ainsi un temps de developpement consequent. L'usage de la DA se repand en Calcul Scientifique, mais souffre encore de quelques problemes. Cette these propose des elements de solution a deux de ces problemes. Le premier probleme est la non-differentiabilite des programmes reels, pour certaines entrees. Les outils de DA negligent souvent ce probleme, alors que les utilisateurs ont besoin d'une grande confiance dans ces derivees avant de les utiliser, par exemple dans des boucles d'optimisation. Quelle que soit son origine reelle, cette non-differentiabilite se traduit dans la structure de controle des programmes. Plutot que d'etudier des extensions de la notion de derivee, nous preferons ici caracteriser le domaine autour des entrees courantes pour lequel le controle reste constant et la differentiabilite est conservee. Nous proposons plusieurs approches et evaluons leurs complexites. Nous etudions formellement une construction du domaine entier, mais sa complexite limite son application. Alternativement, nous proposons une methode directionnelle moins couteuse, que nous avons implementee et validee sur plusieurs exemples. Le second probleme est l'efficacite du mode inverse de la DA, qui produit des codes 'adjoints' calculant des gradients. Ces codes utilisent les valeurs intermediaires du programme initial dans l'ordre inverse, ce qui necessite une combinaison de sauvegarde et de recalcul de ces valeurs. Une tactique fondamentale, nommee 'ckeckpointing', economise de la memoire au prix de la reexecution de segments de code. Dans notre travail, nous formalisons les analyses de flot de donnees necessaires a la differentiation inverse, y compris dans le cas du checkpointing. A partir de cette formalisation, nous proposons deux avancees aux strategies de la DA inverse. D'une part ces analyses nous fournissent des ensembles de valeurs a sauvegarder, que nous pouvons prouver minimaux. D'autre part nous en tirons des indications sur les meilleurs segments de code candidats au checkpointing. Pour experimenter ces choix, nous etendons les analyses et l'algorithme de differentiation inverse de notre outil de DA. Nous montrons les benefices que l'on peut attendre sur des codes reels.