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

Preview

Download (6MB) | Preview

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.

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 (http://creativecommons.org/licenses/by-nc-nd/4.0/), 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:	https://doi.org/10.1080/10556788.2018.1459621
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)
URI:	https://www.tandfonline.com
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)

Item control page

Downloads

Origin of downloads