www.Autodiff.org - Publication: Divide-and-conquer checkpointing for arbitrary programs with no user annotation

Divide-and-conquer checkpointing for arbitrary programs with no user annotation

- Article in a journal -

Author(s)
Jeffrey Mark Siskind , Barak A. Pearlmutter

Published in
Special issue of Optimization Methods & Software: Advances in Algorithmic Differentiation Optimization Methods & Software

Editor(s)
Bruce Christianson, Shaun A. Forth, Andreas Griewank

Year
2018

Publisher
Taylor & Francis

Abstract
Classical reverse-mode automatic differentiation (ad) imposes only a small constant-factor overhead in operation count over the original computation, but has storage requirements that grow, in the worst case, in proportion to the time consumed by the original computation. This storage blowup can be ameliorated by checkpointing, a process that reorders application of classical reverse-mode ad over an execution interval to tradeoff space vs. time. Application of checkpointing in a divide-and-conquer fashion to strategically chosen nested execution intervals can break classical reverse-mode ad into stages which can reduce the worst-case growth in storage from linear to sublinear. Doing this has been fully automated only for computations of particularly simple form, with checkpoints spanning execution intervals resulting from a limited set of program constructs. Here we show how the technique can be automated for arbitrary computations. The essential innovation is to apply the technique at the level of the language implementation itself, thus allowing checkpoints to span any execution interval.

Cross-References
Christianson2018Sio

AD Theory and Techniques
Checkpointing

BibTeX
@ARTICLE{
         Siskind2018Dac,
       crossref = "Christianson2018Sio",
       author = "Jeffrey Mark Siskind and Barak A. Pearlmutter",
       title = "Divide-and-conquer checkpointing for arbitrary programs with no user annotation",
       journal = "Optimization Methods \& Software",
       volume = "33",
       number = "4--6",
       pages = "1288--1330",
       year = "2018",
       publisher = "Taylor \& Francis",
       doi = "10.1080/10556788.2018.1459621",
       url = "https://doi.org/10.1080/10556788.2018.1459621",
       eprint = "https://doi.org/10.1080/10556788.2018.1459621",
       abstract = "Classical reverse-mode automatic differentiation (AD) imposes only a small
         constant-factor overhead in operation count over the original computation, but has storage
         requirements that grow, in the worst case, in proportion to the time consumed by the original
         computation. This storage blowup can be ameliorated by checkpointing, a process that reorders
         application of classical reverse-mode AD over an execution interval to tradeoff space vs. time.
         Application of checkpointing in a divide-and-conquer fashion to strategically chosen nested
         execution intervals can break classical reverse-mode AD into stages which can reduce the worst-case
         growth in storage from linear to sublinear. Doing this has been fully automated only for
         computations of particularly simple form, with checkpoints spanning execution intervals resulting
         from a limited set of program constructs. Here we show how the technique can be automated for
         arbitrary computations. The essential innovation is to apply the technique at the level of the
         language implementation itself, thus allowing checkpoints to span any execution interval.",
       booktitle = "Special issue of Optimization Methods \& Software: Advances in
         Algorithmic Differentiation",
       editor = "Bruce Christianson and Shaun A. Forth and Andreas Griewank",
       ad_theotech = "Checkpointing"
}

back

autodiff.org
Username:
Password: