RecomputationEdit
Recomputation is the practice of discarding certain intermediate results and re-deriving them as needed rather than storing them. This approach is not new; it has long stood in the toolkit of algorithm designers and system engineers who face limits on memory, storage bandwidth, and energy use. In many contexts, the costs saved by not retaining every intermediate value justify the extra computation, yielding scalable, cost-conscious systems. The idea rests on a simple, hard-headed principle: when memory is scarce or expensive, it can be wiser to recompute than to cache.
The core concept centers on a space-time trade-off. By trading time (additional CPU cycles) for space (memory), a computation can operate within tighter resource budgets or with lower hardware investment. In modern practice, recomputation appears in fields ranging from large-scale machine learning to real-time data processing, compiler optimization, and numerical simulation. For example, in training large neural networks, activation recomputation through checkpointing allows models that would exceed GPU memory to be trained successfully, while in streaming pipelines, selective recomputation helps keep state small and robust to failures. See also memory bandwidth and space-time trade-off.
Core idea
Recomputation relies on the fact that intermediate results are often expensive to retain and cheap to reproduce given the original inputs or earlier stages of computation. When a result is needed later, the system can re-create it from earlier data rather than reading it from memory. This is not merely a theoretical trick; it is a practical design choice guided by concrete costs in a given environment. The relationship between recomputation and caching (or memoization) is central: caching stores selected results to avoid repeated work, while recomputation deliberately forgoes some storage in favor of recomputing when needed. See memoization and dynamic programming for related ideas about how past results influence future work. In the literature, this trade-off is framed as the broader space-time trade-off.
The formal study of recomputation interacts with several subfields. In algorithm design, the Sethi–Ullman algorithm provides a framework for choosing evaluation orders that minimize register use and, by extension, the need to recompute values. In numerical methods and scientific computing, the cost of memory access and data movement often dominates compute time, making recomputation a viable option. In the domain of automatic differentiation, checkpointing strategies balance forward computation with backward passes to manage memory consumption during gradient calculation. See Sethi–Ullman algorithm, automatic differentiation, and memory.
Techniques and variants
Checkpointing and gradient checkpointing: A controlled set of saved points (checkpoints) allows recomputation of intermediate states during later phases of a computation, reducing peak memory demand. This approach is central to training deep models when activations would otherwise exceed hardware limits. See checkpointing and gradient checkpointing.
Binary and multi-level checkpointing: Methods that place checkpoints at strategic intervals to optimize the overall time-space cost of recomputation. See checkpointing.
Divide-and-conquer and wavefront strategies: These schedules break a computation into pieces and decide where to recompute versus where to store results, aiming to minimize overhead. See space-time trade-off.
Sethi–Ullman style evaluation and register pressure: The choice of evaluation order can minimize the need to store and retrieve intermediate results, influencing whether recomputation is beneficial. See Sethi–Ullman algorithm.
Memoization vs recomputation: While memoization caches results to avoid future work, recomputation chooses to redo work instead of caching. See memoization and dynamic programming.
Applications in data processing and databases: In streaming and distributed systems, recomputation can reduce the need to persist large state or logs, trading some latency for lower storage and throughput costs. See data processing and stream processing.
In machine learning and AI: Activation recomputation and related techniques enable training of very large models on finite hardware, sometimes with modest increases in training time but substantial reductions in memory requirements. See neural network and automatic differentiation.
Applications
High-performance computing and numerical simulations: Large simulations can benefit from recomputation to stay within memory constraints on clusters and supercomputers. See high-performance computing.
Machine learning and deep learning: Gradient checkpointing and related methods allow training of models that would not fit entirely in memory, balancing the cost of extra computation against the savings in memory. See gradient checkpointing and automatic differentiation.
Data processing, streaming, and fault tolerance: In large data pipelines, recomputation can improve resilience and reduce the need for storing extensive state, especially when storage costs or bandwidth are limiting factors. See data processing and checkpointing.
Compiler optimization and program synthesis: Algorithms for expression evaluation, register allocation, and code generation often involve decisions about recomputation versus storage, aiming to minimize resource use while maintaining performance. See Sethi–Ullman algorithm and dynamic programming.
Real-time systems and embedded computation: In environments with strict energy, thermal, or latency constraints, recomputation can provide predictable performance characteristics and lower hardware requirements. See real-time systems and embedded systems.
Rendering and simulation: Certain rendering pipelines and physical simulations reuse recomputation to manage memory bandwidth and cache behavior, enabling smoother operation on devices with limited resources. See computer graphics.
Controversies and debates
Performance vs. resource use: Critics note that recomputation increases total compute time and may worsen latency, which matters in real-time or interactive applications. Proponents counter that when memory bandwidth, cache efficiency, or hardware costs are the bottlenecks, recomputation yields a better overall cost profile.
Energy and cost considerations: In large data centers, memory movement is often energy-intensive; reducing memory footprint can cut energy use and equipment costs. Detractors worry about the energy cost of extra computation in settings where CPUs and GPUs are already energy-hungry. The right balance depends on the specific workload, hardware, and energy prices; the goal is a predictable, cost-efficient operation rather than maximizing one metric in isolation. See energy efficiency and data center.
Reliability and determinism: Recomputing instead of storing intermediate results introduces new failure modes. If recomputation depends on exact circumstances or inputs, small changes can complicate fault tolerance and reproducibility. Advocates emphasize robust checkpointing schemes and deterministic recomputation paths to mitigate these risks. See fault tolerance and reproducibility.
Public policy and investment context: Advocates for recomputation argue it can lower capital expenditure and stretch the life of existing hardware, aligning with market-driven efficiency and steady improvement in performance per watt. Critics may frame the discussion in broader terms about energy use or resilience, sometimes oversimplifying the practical trade-offs. The practical view focuses on the measurable cost-benefit of computing workloads, not abstract moral calculus.