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 metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-01654632
Contributor : Guillaume Pallez (aupy) <>
Submitted on : Monday, December 4, 2017 - 11:10:02 AM
Last modification on : Wednesday, November 20, 2019 - 3:18:06 AM

File

main-revision.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

508

Files downloads

243