Paper by Erik D. Demaine
- Erik D. Demaine, Jayson Lynch, Geronimo J. Mirano, and Nirvan Tyagi, “Energy-Efficient Algorithms”, in Proceedings of the 7th Annual ACM Conference on Innovations in Theoretical Computer Science (ITCS 2016), Cambridge, Massachusetts, January 14–16, 2016, pages 321–332.
We initiate the systematic study of the energy complexity of algorithms
(in addition to time and space complexity) based on Landauer's Principle in
physics, which gives a lower bound on the amount of energy a system must
dissipate if it destroys information. We propose energy-aware variations of
three standard models of computation: circuit RAM, word RAM, and
transdichotomous RAM. On top of these models, we build familiar high-level
primitives such as control logic, memory allocation, and garbage collection
with zero energy complexity and only constant-factor overheads in space and
time complexity, enabling simple expression of energy-efficient algorithms.
We analyze several classic algorithms in our models and develop low-energy
variations: comparison sort, insertion sort, counting sort, breadth-first
search, Bellman-Ford, Floyd-Warshall, matrix all-pairs shortest paths, AVL
trees, binary heaps, and dynamic arrays. We explore the time/space/energy
trade-off and develop several general techniques for analyzing algorithms and
reducing their energy complexity. These results lay a theoretical foundation
for a new field of semi-reversible computing and provide a new framework for
the investigation of algorithms.
- The paper is available in PDF (334k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- EnergyCompiler_RC2016 (Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated March 27, 2017 by