Paper by Erik D. Demaine

Reference:

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.

BibTeX

@InProceedings{Energy_ITCS2016,
  AUTHOR        = {Erik D. Demaine and Jayson Lynch and Geronimo J. Mirano and Nirvan Tyagi},
  TITLE         = {Energy-Efficient Algorithms},
  BOOKTITLE     = {Proceedings of the 7th Annual ACM Conference on Innovations in Theoretical Computer Science (ITCS 2016)},
  bookurl       = {https://projects.csail.mit.edu/itcs/},
  ADDRESS       = {Cambridge, Massachusetts},
  MONTH         = {January 14--16},
  YEAR          = 2016,
  PAGES         = {321--332},

  withstudent   = 1,
  papers        = {EnergyCompiler_RC2016},
  doi           = {https://dx.doi.org/10.1145/2840728.2840756},
  dblp          = {https://dblp.org/rec/conf/innovations/DemaineLMT16},
  comments      = {This paper is also available as <A HREF="https://arXiv.org/abs/1605.08448">arXiv:1605.08448</A>, and from <A HREF="https://doi.org/10.1145/2840728.2840756">ACM</A>.},
}

Abstract:

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.

Comments:

This paper is also available as arXiv:1605.08448, and from ACM.

Availability:

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)