Periodicity in optimal hierarchical checkpointing schemes for adjoint computations

Guillaume Aupy 1, 2 Julien Herrmann 3, 4
1 TADAAM - Topology-Aware System-Scale Data Management for High-Performance Computing
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
3 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We reexamine the work of Aupy et al. on optimal algorithms for hierarchical adjoint computations , where two levels of memories are available. The 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 and space, with appropriate pre-processing. We also provide an asymptotically optimal algorithm for the online problem, when the adjoint chain size is not known beforehand. Again, these algorithms rely on the proof that the optimal solution for hierarchical adjoint computations is weakly periodic. We conjecture a closed-form formula for the period. Finally, we assess the convergence speed of the approximation ratio for the online problem through simulations.
Type de document :
Article dans une revue
Optimization Methods & Software, Taylor and Francis Online, 2017, 32 (3), pp.594-624. 〈10.1080/10556788.2016.1230612〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01654632
Contributeur : Guillaume Aupy <>
Soumis le : lundi 4 décembre 2017 - 11:10:02
Dernière modification le : mardi 16 janvier 2018 - 15:30:13

Fichier

main-revision.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Guillaume Aupy, Julien Herrmann. Periodicity in optimal hierarchical checkpointing schemes for adjoint computations. Optimization Methods & Software, Taylor and Francis Online, 2017, 32 (3), pp.594-624. 〈10.1080/10556788.2016.1230612〉. 〈hal-01654632〉

Partager

Métriques

Consultations de la notice

35

Téléchargements de fichiers

6