Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Guillaume Pallez (aupy) Connect in order to contact the contributor
Submitted on : Monday, December 4, 2017 - 11:10:02 AM
Last modification on : Friday, January 7, 2022 - 3:55:04 AM


Files produced by the author(s)




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



Les métriques sont temporairement indisponibles