Source-linked AI summary
Limits on Fundamental Limits to Computation
Igor L. Markov
TL;DR
Computing scaling faces practical and fundamental limits across manufacturing, energy, physical space, design, verification, and algorithms. The paper reviews these limits, examines how some have been circumvented, and compares their tightness. It concludes that space-time limits appear tighter than energy-time limits, while many other limits remain loose or conjectural.
Problem
Emerging technologies promise advantages over integrated circuits, but evaluating them requires accounting for serious limitations and distinguishing loose from potentially tight fundamental limits.
Method
The paper reviews limits across manufacturing, energy, physical space, design and verification effort, and algorithms, including historical circumventions and the assumptions behind each limit.
Results
Space-time limits appear tighter than energy-time limits, while some limits remain substantially loose and others remain conjectured from empirical evidence.
Takeaways & Limitations
Understanding a limit’s assumptions helps identify when it can be circumvented, while loose limits can be discounted and conjectured limits require further study.
Takeaways & Limitations
Many nonphysical computing limits have not been proven and depend on faith in conjectures despite substantial empirical evidence.
Abstract
from arXiv · showhide
An indispensable part of our lives, computing has also become essential to industries and governments. Steady improvements in computer hardware have been supported by periodic doubling of transistor densities in integrated circuits over the last fifty years. Such Moore scaling now requires increasingly heroic efforts, stimulating research in alternative hardware and stirring controversy. To help evaluate emerging technologies and enrich our understanding of integrated-circuit scaling, we review fundamental limits to computation: in manufacturing, energy, physical space, design and verification effort, and algorithms. To outline what is achievable in principle and in practice, we recall how some limits were circumvented, compare loose and tight limits. We also point out that engineering difficulties encountered by emerging technologies may indicate yet-unknown limits.
1 Introduction
The paper frames emerging computing technologies against established hardware by reviewing practical obstacles and fundamental limits, distinguishing limits that remain loose from those that may be tight.
- Emerging computing technologies may improve bandwidth, speed, power consumption, manufacturing cost, or form factor, but their limitations can be overlooked.
- The review studies limits on manufacturing, energy, physical space, design effort, and algorithms to clarify what computation can achieve in principle and in practice.
- General-purpose computers combine broad applicability with reliable, long-running computation, while specialized hardware can deliver large application-specific speedups at higher design cost and reduced adaptability.Domain-specific hardware can speed biomolecular simulation 100-fold and video decoding 500-fold.
- Evaluating emerging technologies requires separating near-term engineering extrapolations from fundamental limits, because obstacles can sometimes be circumvented.The paper cites sub-wavelength lithography as an example of overcoming an apparent manufacturing limit.
2 Engineering obstacles
Engineering obstacles constrain manufacturing, interconnects, transistor scaling, design effort, and verification, but redesign and automation have repeatedly extended practical integrated-circuit scaling.
- Manufacturing: Integrated-circuit manufacturing packs billions of transistors and wires into several cm2 of silicon while requiring astronomically low defect rates.Material deposition and laser patterning fabricate circuit components simultaneously.
- Manufacturing: 193nm ArF lasers supported sub-wavelength lithography for 45nm–22nm technology nodes through asymmetric illumination and computational lithography.The method alters optical masks to compensate for image blurring.
- Interconnects: Interconnects cannot be simultaneously fast and dense: smaller cross-sections raise resistance, while larger wires increase parasitic capacitance and RC delay.Interconnect stacks evolved from four equal-pitch layers in 2000 to 16 layers with pitches varying by 32 times.
- Transistors: Gate dielectrics approaching several atoms create missing-atom, manufacturing-variation, and leakage problems, motivating wider dielectric layers around fin-shaped transistors.FinFETs can also use multiple fins.
- Design and verification: Design optimization problems remain hard, so practical integrated-circuit design relies on heuristics, continuing innovation, and increasingly indispensable automation.Technology generations require new CAD software, while design costs have doubled in a few years.
- Design and verification: Hardware and software are now co-designed and co-verified, with platform-based design and reusable hardware supporting specialization through software.
3 Energy-time limits
Computing faces fundamental energy and power constraints, but their practical severity depends on physical scale, dissipation, and system-level communication. These limits motivate slower parallel cores and broader alternatives, while many first-principles energy bounds remain loose.
- Energy and power limits reflect available resources, physical-space properties, power dissipation, and energy waste.
- 3.1 Reversibility: Erasing one bit dissipates at least kT ln 2, while faster computation requires greater energy under the energy-time uncertainty relation.At room temperature, the Landauer threshold is 2.85×10^-21 J.
- 3.1 Reversibility: Reversible circuits can dissipate below the thermodynamic threshold, but superconducting and quantum implementations remain impractical or fail to scale.Quantum implementations also incur system-level energy inefficiency and heavy fault-tolerance overhead.
- 3.2 Power constraints and CPUs: A cancelled 4GHz CPU project and subsequent 1-6GHz designs marked the end of frequency scaling, shifting effort toward multicore parallelism.Dynamic circuit power grows with clock frequency and supply voltage squared, favoring slower, lower-voltage cores when parallelization overhead is small.
- 3.2 Power constraints and CPUs: Dennard scaling broke down, producing utilization limits in which modern CPUs cannot activate all circuits simultaneously and may approach 99% dark silicon.Slowing cores to save power is termed dim silicon.
- 3.3 Broader limits: Binary switching density is constrained when charge-based switches consume energy, motivating information carriers such as spin states, photon polarizations, and magnetic flux.The review also identifies bounds involving matter, atomic properties, particle wavelengths, and basic physical constants.
4 Asymptotic space-time limits
Physical space and communication impose tighter asymptotic limits than many energy bounds. Parallel speedups are constrained by finite communication speed and interconnect, while 3D integration offers significant but bounded improvements.
- Engineering limits in deployed technologies can often be circumvented, whereas first-principles energy and power limits are usually loose.Reasonably tight limits are rare.
- Parallel computation cannot generally achieve an N-fold speedup because finite communication speed and physical space constrain the required steps.
- A more realistic speedup from ∼n^k to ∼log n is possible in abstract models for matrix multiplication and fast Fourier transforms, but not in physical space.
- Interconnect has become a major bottleneck: wires account for much physical volume and circuit delay, and a clock cycle is too short for signals to cross an entire chip.Gate delays dominated until 2000, but wires have slowed relative to gates at each technology node.
- Implications to 3D ICs and other emerging technologies: In 3D, asymptotic integration reduces time from t to t^3/4, but this requires an unbounded number of 2D layers; practical two- or three-layer benefits are narrower.Current benefits include improved manufacturing yield, I/O bandwidth, and combining specialized 2D circuits.
5 Complexity-theoretic limits
Complexity theory supplies abstract limits on computation, including conjectured barriers to efficient optimization and parallelization and a proven undecidability result. Their practical interpretation is tempered by the absence of proofs for most conjectured limits.
- The P≠NP conjecture is used to explain the lack of satisfactory, scalable solutions for problems such as IC-design optimization and verification.
- The P≠NC conjecture addresses why many efficiently solvable algorithmic problems have not parallelized efficiently.
- Most complexity-theoretic limits discussed remain unproven, despite substantial empirical evidence, making faith an important limitation.Quantum computers can theoretically factor numbers in polynomial time but do not affect P≠NP.
- Turing’s halting result proves that no algorithm decides for every program whether it eventually halts, regardless of runtime.
6 Conclusions
The paper concludes that computing limits span economic, physical, engineering, and algorithmic constraints, with their tightness determining which obstacles can be bypassed. Some limits are loose or conjectural, so understanding assumptions is essential for evaluating alternatives and guiding optimization.
- 6 Conclusions: Only CPUs, GPUs, FPGAs, and dense memory ICs may remain viable after Moore scaling ends, while specialized circuits may use less advanced technologies.Memory has scaled faster by exploiting simpler structure and more controllable manufacturing, although its scaling is slowing.
- 6 Conclusions: Space-time limits appear tighter than energy-time limits, highlighting interconnect and communication bottlenecks.Suggested responses include three-dimensional gate placement, optimizing gate locations and sizes, and adapting algorithms to spatial embeddings.
- 6 Conclusions: The gap between current technologies and energy-time limits indicates potential rewards from charge recovery, power management, voltage scaling, and near-threshold computing.The paper identifies simultaneous optimization of algorithms and circuits as another way to reduce energy waste.
- 6 Conclusions: Physical room for miniaturization is becoming scarce, while using energy for computation raises heat-removal problems constrained by energy conversion and acceptable thermal envelopes.The paper presents heat removal as a central boundary on exploiting available energy for computation.
- 6 Conclusions: Design limits include losses at abstraction boundaries, overdesign from resource overestimation, and optimization losses caused by inaccurate physical models under uncertainty.These issues arise in hierarchical complex-system design and motivate clearer engineering limits.
- 6 Conclusions: Known limits can be loose or circumventable, whereas other limits remain conjectural from empirical evidence and may be difficult to establish rigorously.The paper calls for further study of limits on limits to computation.