Skip to Main content Skip to Navigation
Reports

Periodicity is Optimal for Offline and Online Multi-Stage Adjoint Computations

Abstract : 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.
Complete list of metadatas

https://hal.inria.fr/hal-01244584
Contributor : Julien Herrmann <>
Submitted on : Wednesday, December 16, 2015 - 11:50:36 PM
Last modification on : Thursday, November 21, 2019 - 1:42:09 AM
Long-term archiving on: : Thursday, March 17, 2016 - 11:01:23 AM

Files

RR-8822.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01244584, version 1

Collections

Citation

Guillaume Aupy, Julien Herrmann. Periodicity is Optimal for Offline and Online Multi-Stage Adjoint Computations. [Research Report] RR-8822, INRIA Grenoble - Rhône-Alpes. 2015. ⟨hal-01244584⟩

Share

Metrics

Record views

323

Files downloads

150