MURAL - Maynooth University Research Archive Library

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

    Siskind, Jeffrey Mark and Pearlmutter, Barak A. (2018) Divide-and-conquer checkpointing for arbitrary programs with no user annotation. Optimization Methods and Software, 33 (4-6). pp. 1288-1330. ISSN 1055-6788

    Download (6MB) | Preview

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    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.

    Item Type: Article
    Additional Information: © 2018 The Author(s). Published by Informa UK Limited, trading as Taylor & Francis Group This is an Open Access article distributed under the terms of the Creative Commons Attribution-NonCommercial-NoDerivatives License (, which permits non-commercial re-use, distribution, and reproduction in any medium, provided the original work is properly cited, and is not altered, transformed, or built upon in any way. Cite as: Jeffrey Mark Siskind & Barak A. Pearlmutter (2018) Divide-and-conquer checkpointing for arbitrary programs with no user annotation, Optimization Methods and Software, 33:4-6, 1288-1330, DOI: 10.1080/10556788.2018.1459621
    Keywords: Reverse-mode automatic differentiation; binomial checkpointing; treeverse; programming language theory; compiler theory; lambda calculus;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 10241
    Identification Number:
    Depositing User: Barak Pearlmutter
    Date Deposited: 22 Nov 2018 17:17
    Journal or Publication Title: Optimization Methods and Software
    Publisher: Taylor & Francis
    Refereed: Yes
    Funders: National Science Foundation, US (NSF), Intelligence Advanced Research Projects Activity (IARPA), Science Foundation Ireland (SFI)
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only(login required)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads