Periodicity in optimal hierarchical checkpointing schemes for adjoint computations - Archive ouverte HAL Access content directly
Journal Articles Optimization Methods and Software Year : 2017

Periodicity in optimal hierarchical checkpointing schemes for adjoint computations

(1, 2) , (3, 4)
1
2
3
4

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.
Fichier principal
Vignette du fichier
main-revision.pdf (878.79 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01654632 , version 1 (04-12-2017)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More