Periodicity is Optimal for Offline and Online Multi-Stage Adjoint Computations
Résumé
We reexamine the work of Aupy et al. on optimal algorithms for multi-stage
adjoint computations, where two levels of memories are available. Previous
optimal algorithm had a quadratic execution time. Here, with structural
arguments, namely periodicity, on the optimal solution, we provide an optimal
algorithm in constant time, with appropriate pre-processing.
We also provide an asymptotically optimal algorithm for the online problem,
when the adjoint graph size is not known before-hand. Again, this algorithms
rely on the proof that the optimal solution for multi-stage adjoint computations
is weakly periodic.
We conjecture a closed-form formula for the period. Finally, we experimentally
access the convergence speed of the approximation ratio for the online problem,
through simulations.
Dans cet article, nous améliorons le travail de Aupy et al. sur les algorithmes à plusieurs étages optimaux pour le calcul d'adjoints, avec deux niveaux de mémoire disponibles. L'algorithme optimal précédent avait un temps d'exécution quadratique. Ici, avec une analyse de la solution optimale, nous proposons un algorithme optimal en temps constant, avec précalculs. Nous proposons également un algorithme asymptotiquement optimal pour la version en ligne du problème, lorsque la taille du graphe adjoint n'est pas connue à l'avance. Ces algorithmes reposent sur la preuve que les solutions optimales pour le calcul d'adjoint sont périodiques.
Nous conjecturons la formule close de cette période. Enfin, nous évaluons la vitesse de convergence du ratio d'approximation pour le problème en ligne, à travers une campagne de simulations.
a travers une campagne de simulations.
Origine : Fichiers produits par l'(les) auteur(s)