Andreas Griewank
Abstract
In its basic form, the reverse mode of computational differentiation yields the gradient of a scalar-valued function at a cost that is a small multiple of the computational work needed to evaluate the function itself. However, the corresponding memory requirement is proportional to the run-time of the evaluation program. Therefore, the practical applicability of the reverse mode in its original formulation is limited despite the availability of ever larger memory systems. This observation leads to the development of checkpointing schedules to reduce the storage requirements. This article presents the function revolve, which generates checkpointing schedules that are provably optimal with regard to a primary and a secondary criterion. This routine is intended to be used as an explicit “controller” for running a time-dependent applications program.
Supplemental Material
Available for Download
Software for "revolve: an implementation of checkpointing for the reverse or adjoint mode of computational differentiation"
- GRIMM, J., POTTIER, L., AND ROSTAING-SCHMIDT, N. 1996. Optimal time and minimum space-time product for reversing a certain class of programs. In Computational Differentiation: Techniques, Applications, and Tools, M. Berz, C. Bischof, G. Corliss, and A. Griewank, Eds. SIAM, Philadelphia, PA, 161-172.Google Scholar
- GRIEWANK, A. 1992. Achieving logarithmic growth of temporal and spatial complexity in reverse automatic differentiation. Optim. Meth. Softw. 1, 1, 35-54.Google ScholarCross Ref
- GRIEWANK, A. 2000. Evaluating Derivatives, Principles, and Techniques of Algorithmic Differentiation. SIAM Frontiers in Applied Mathematics Series, vol. 19. SIAM, Philadelphia, PA. Google ScholarDigital Library
- RESTREPO, J. M., LEAF, G. K., AND GRIEWANK, A. 1998. Circumventing storage limitations in variational data assimilation studies. SIAM J. Sci. Comput. 19, 5, 1586-1605. Google ScholarDigital Library
- LEVEQUE, R. 1992. Numerical Methods for Conservation. Birkh user-Verlag, Basel, Switzerland.Google Scholar
- LIONS, J. L. 1971. Optimal Control of Systems Governed by Partial Differential Equations. Springer-Verlag, New York, NY.Google Scholar
- OSHER, S. AND SOLOMON, F. 1982. Upwind difference schemes for the hyperbolic systems of conservation laws. Math. Comput. 38, 158, 339-374.Google ScholarCross Ref
- SYMES, W. 1997. Framework for automatic differentiation applied to time-dependent problems. In Proceedings of SIAM's 45th Anniversary Meeting (Stanford, CA, July 14-18), SIAM, Philadelphia, PA.Google Scholar
- WALTHER, A. 1999. Program reversal schedules for single- and multi-processor machines. Ph.D. Dissertation. Technical University Dresden, Dresden.Google Scholar
Index Terms
- Algorithm 799: revolve: an implementation of checkpointing for the reverse or adjoint mode of computational differentiation
Recommendations
Real-Time In-Memory Checkpointing for Future Hybrid Memory Systems
ICS '15: Proceedings of the 29th ACM on International Conference on SupercomputingIn this paper, we study real-time in-memory checkpointing as an effective means to improve the reliability of future large-scale parallel processing systems. Under this context, the checkpoint overhead can become a significant performance bottleneck. ...
A fully informed model-based checkpointing protocol for preventing useless checkpoints
Checkpointing and rollback recovery are widely used techniques for handling failures in distributed systems. When processes involved in a distributed computation are allowed to take checkpoints independently without any coordination with each other, ...
Sleep-Mode Voltage Scaling: Enabling SRAM Data Retention at Ultra-Low Power in Embedded Microcontrollers
Special Issue on VIPES, Special Issue on ICESS2015 and Regular PapersIn heavily duty-cycled embedded systems, the energy consumed by the microcontroller in idle mode is often the bottleneck for battery lifetime. Existing solutions address this problem by placing the microcontroller in a low-power (sleep) mode when idle ...
Reviews
Frank Stenger
This is an excellent paper, describing a variant (“revolve”) of the basic form for reverse differentiation for computing the gradient of a scalar valued function, which enables computing this gradient of a function using no more than five times the number of operations needed for evaluating the function. This basic algorithm usually requires a large memory for storage of intermediate computations. The variant presented here circumvents this large memory requirement. A detailed description of the variant is given, along with motivation and proofs. The authors then illustrate the application of their algorithm to the solution of Burger's equation.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments