Algorithm 799: revolve: an implementation of checkpointing for the reverse or adjoint mode of computational differentiation

By Andreas Griewank, Andrea Walther. 2000

603 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Hardware and Architecture, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Hardware and Architecture

In Optimization & Training

Citations in the corpus

Learning Transferable Visual Models From Natural Language Supervision (2021, methodology): “To save additional memory, gradient checkpointing (Griewank & Walther, 2000; Chen et al., 2016), half-precision Adam statistics (Dhariwal et al., 2020), and half-precision stochastically rounded text encoder weights were used.”
Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM (2021, background): “Activation recomputation [12, 18, 20, 21] is an optional technique that trades off an increase in the number of compute operations performed for additional memory footprint, by running the forward pass a second time just before the backward pass (and stashing only the input activations for a given p”
Memory-Efficient Pipeline-Parallel DNN Training (2020, methodology): “PipeDream-2BW’s planner determines the size of each model partition, per-GPU microbatch size, and whether to use memory-saving optimizations like activation recomputation [5,9] while taking into account both the throughput and memory footprint ramifications of these decisions.”
Training Deep Nets with Sublinear Memory Cost (2016, background): “long standing topic in systems research. Although not widely known, the idea of dropping intermediate results is also known as gradient checkpointing technique in automatic differentiation literature [9]. We bring this idea to neural network gradient graph construction for general deep neural networ”
Combined Scaling for Zero-shot Transfer Learning (2021, methodology): “Three well-known techniques to relieve memory burden are gradient accumulation (GradAccum) [61, 98], re-materialization (or gradient checkpointing) [9, 26] and model parallelism [35, 48, 70].”
FILIP: Fine-grained Interactive Language-Image Pre-Training (2021, methodology): “To save memory and scale up the batch size, automatic mixed-precision (Micikevicius et al., 2018) and gradient checkpoint (Griewank & Walther, 2000; Chen et al., 2016) are used The input images are resized to 224 × 224 resolution during pre-training and the maximum length of the text is limited to…”
Checkmate: Breaking the Memory Wall with Optimal Tensor Rematerialization (2019, methodology): “In work from the differential equation community that inspired later work in reverse-mode automatic differentiation, Griewank and Walther [22] develop a procedure for checkpointing in idealized linear computation graphs with O (log n ) memory usage, where n denotes the number of computation nodes.”
Automated Derivation of the Adjoint of High-Level Transient Finite Element Programs (2012, methodology): “Of particular note is the algorithm of Griewank and coworkers, which achieves logarithmic growth of the storage requirements and recomputation costs [17, 18] and is provably optimal for the case in which the number of timesteps to be performed is known in advance [19].”
Topology Optimization of Turbulent Flows (2018, background): “It should be pointed out that such black box differentiation brings immense memory requirements, and requires check-point algorithms [30] to store intermediate computations and to reduce the memory consumption.”
Low-Memory Neural Network Training: A Technical Report (2019, background): “Gradient checkpointing was originally introduced by Griewank and Walther (2000), and studied in the context of deep learning by Chen et al. (2016).”
Revisiting Stereo Depth Estimation From a Sequence-to-Sequence Perspective with Transformers (2020, methodology): “Following [8], we adopt gradient checkpointing [14] for each self- and cross-attention layer, where the intermediate variables are not saved during the forward pass.”
ANODE: Unconditionally Accurate Memory-Efficient Gradients for Neural ODEs (2019, methodology): “Similar approaches to the optimal checkpointing, originally proposed in [17, 18], were recently explored for memory efficient NNs in [9, 19].”
Reverse time migration with optimal checkpointing (2007, methodology): “My understanding of optimal checkpointing owes a great deal to discussions with Prof. Andreas Griewank and Dr. Joakim Blanch.”
Efficient Rematerialization for Deep Networks (2019, background): “When studied on computation graphs derived from training neural networks (i.e., graphs with forward computation and backward computations), rematerialization is often referred to as gradient checkpointing [10, 6, 8, 1, 15].”
Finite-frequency sensitivity kernels for global seismic wave propagation based upon adjoint methods (2008, background): “A compromise—an approach generally known as ‘checkpointing’ (Restrepo & Griewank 1998; Griewank & Walther 2000; Hinze et al. 2005)—is to solve the backward equations with attenuation on, but only for a number of time steps that is within the numerically stable regime, and then ‘resetting’ the…”
Theoretical background for continental‐ and global‐scale full‐waveform inversion in the time–frequency domain (2008, background): “(3) Checkpointing algorithms provide a balance between storage and time efficiency (e.g. Griewank & Walther 2000; Charpentier 2001).”