Excerpt

Introduction

With the ever-increasing demands for computing resources— at home, in supercomputers, and in massive data centers—the issue of how much energy is used to run computers is becoming a major challenge for modern society.1 At the broadest scale, it is estimated that 2.2% to 5% of all US energy is already expended on computing, resulting in a major component of our carbon footprint.2 At a smaller scale, a supercomputer powerful enough to accurately model the future of the Earth’s climate would need to be one hundred times faster than today’s fastest supercomputers, but such an “exascale computer would consume electricity equivalent to 200,000 homes and might cost $20 million or more annually to operate” (Markoff 2015). As a final example, well known to everyone who uses a mobile phone or a laptop, one of the major limitations constraining the use of mobile computing is how to store enough energy to run such computers.

By conservation of energy, so long as all configurations of the bits in a computer have the same energy level, all of the energy used by that computer is ultimately dumped into the world as heat. (Indeed, one of the major challenges in constructing exascale computers is how to keep them from melting.) In other words, computers are energy transducers, converting one kind of energy into another kind, processing information at the same time. The science of energy transduction—the science that governs how much energy is needed to run a computer—is statistical physics. More specifically, it is nonequilibrium statistical physics, since computational systems are far from thermal equilibrium.

Because the energy transduction in computation is so intimately coupled to the processing of information, to fully understand the thermodynamics of computation, we need to exploit the relation between information theory and statistical physics. Landauer (1961, 1991, 1996a, 1996b), following the work of Brillouin (1953, 1962) and Szilard (1964), highlighted the connection between Shannon’s information-theoretic entropy and thermodynamic entropy, arguing that erasing a bit necessarily pumps kT ln 2 bits of physical entropy— essentially, heat—into the environment. Following this line of reasoning, Bennett (1973) began studying how one might design algorithms that needed less energy to run by making more of their steps reversible. This was followed by a series of papers over several decades clarifying and improving the various time-space trade-offs in making computations reversible (Bennett 1982; Fredkin and Toffoli 1982; Bennett 1989; Levine and Sherman 1990; Shizume 1995; Crescenzi and Papadimitriou 1995; Li, Tromp, and Vitányi 1998a, 1998b; Frank, Knight, and Margolus 1998; Lange, McKenzie, and Tapp 2000; Plenio and Vitelli 2001; Buhrman, Tromp, and Vitányi 2001a, 2001b; Bennett 2003; Sutner 2004; Vitányi 2005; Morita 2008; Tyagi, Lynch, and Demaine 2016; Demaine et al. 2016).

Bibliography

Alman, J., and R. Williams. 2016. Probabilistic Rank and Matrix Rigidity. arXiv:1611.05558 [cs.CC]. 49th ACM Symposium on the Theory of Computing, STOC '17.

Arora, S., and B. Barak. 2009. Computational Complexity: A Modern Approach. Cambridge University Press.

Augustine, J., K. Palem, and Parishkrati. 2017. Sustaining Moore’s Law through Inexactness. arXiv:1705.01497 [cs.CC].

Baek, W., and T. M. Chilimbi. 2010. “Green: A Framework for Supporting Energy-Conscious Programming Using Controlled Approximation.” In Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation, 198–209. PLDI '10. Toronto, Ontario, Canada: ACM.

Balas, E., S. Ceria, and G. Cornuéjols. 1993. “A Lift-and-Project Cutting Plane Algorithm for Mixed 0–1 Programs.” Math. Programming 58 (3, Ser. A): 295–324.

Ben-David, S., B. Chor, O. Goldreich, and M. Luby. 1992. “On the Theory of Average Case Complexity.” J. Comput. System Sci. 44 (2): 193–219.

Bennett, C. H. 1973. “Logical Reversibility of Computation.” IBM Journal of Research and Development 17 (6): 525–532.

————. 1982. “The Thermodynamics of Computation—A Review.” Internat. J. Theoret. Phys. 21 (12): 905–940.

————. 1989. “Time/Space Trade-Offs for Reversible Computation.” SIAM Journal on Computing 18 (4): 766–776.

————. 2003. “Notes on Landauer’s Principle, Reversible Computation, and Maxwell's Demon.” Studies In History and Philosophy of Science Part B: Studies In History and Philosophy of Modern Physics 34 (3): 501–510.

Bloom, B. H. 1970. “Space/Time Trade-Offs in Hash Coding with Allowable Errors.” Commun. ACM (New York, NY, USA) 13, no. 7 (July): 422–426.

Bogdanov, A., and L. Trevisan. 2006. “Average-Case Complexity.” Found. Trends Theor. Comput. Sci. 2 (1): 1–106.

Boyar, J., P. Matthews, and R. Peralta. 2013. “Logic Minimization Techniques with Applications to Cryptology.” Journal of Cryptology 26 (2): 280–312.

Boyd, A. B. 2018. “Thermodynamics of Modularity: Structural Costs Beyond the Landauer Bound.” Physical Review X 8 (3).

Brillouin, L. 1953. “Negentropy Principle of Information.” Journal of Applied Physics 24:1152–1163.

————. 1962. Science and Information Theory. Academic Press.

Buhrman, H., J. Tromp, and P. Vitányi. 2001a. “Time and Space Bounds for Reversible Simulation.” In Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Proceedings, edited by F. Orejas, P. G. Spirakis, and J. van Leeuwen, 1017–1027. Berlin, Heidelberg: Springer Berlin Heidelberg.

————. 2001b. “Time and Space Bounds for Reversible Simulation.” J. Phys. A 34 (35): 6821–6830.

Chejne Janna, F., F. Moukalled, and C. A. Gómez. 2013. “A Simple Derivation of Crooks Relation.” Internat. J. Thermodyn. 16 (3): 97–101.

Chung, F., and L. Lu. 2006. Complex Graphs and Networks. 107:viii+264. CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI.

Chvátal, V. 1983. Linear Programming. A Series of Books in the Mathematical Sciences. W. H. Freeman / Company, New York.

Codenotti, B. 2000. “Matrix Rigidity.” Linear Algebra Appl. 304 (1-3): 181–192.

Cormen, T. H., C. E. Leiserson, R. L. Rivest, and C. Stein. 2009. Introduction to Algorithms. Third. MIT Press, Cambridge, MA.

Cover, T. M., and J. A. Thomas. 2012. Elements of Information Theory. John Wiley & Sons. Accessed January 11, 2014.

Crescenzi, P., and C. H. Papadimitriou. 1995. “Reversible Simulation of Space-Bounded Computations.” Theoret. Comput. Sci. 143 (1): 159–165.

Crooks, G. E. 1998. “Nonequilibrium Measurements of Free Energy Differences for Microscopically Reversible Markovian Systems.” J. Stat. Phys. 90 (5--6): 1481– 1487.

————. 1999. “Entropy Production Fluctuation Theorem and the Nonequilibrium Work Relation for Free Energy Differences.” Phys. Rev. E 60 (3): 2721.

Dantzig, G. B. 1990. “Origins of the Simplex Method.” In A History of Scientific Computing, edited by S. G. Nash, 141–151. New York, NY, USA: ACM.

Deffner, S., and C. Jarzynski. 2013. “Information Processing and the Second Law of Thermodynamics: An Inclusive, Hamiltonian Approach.” Physical Review X 3 (4): 041003.

Demaine, E. D., J. Lynch, G. J. Mirano, and N. Tyagi. 2016. “Energy-Efficient Algorithms.” In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 321–332. ITCS '16. Cambridge, Massachusetts, USA: ACM.

Diethelm, K. 2016. “Tools for Assessing and Optimizing the Energy Requirements of High Performance Scientific Computing Software.” PAMM 16 (1): 837–838.

Een, N., A. Mishchenko, and N. Sörensson. 2007. “Applying Logic Synthesis for Speeding Up SAT.” In Theory and Applications of Satisfiability Testing—SAT 2007: 10th International Conference, Lisbon, Portugal, May 28-31, 2007. Proceedings, edited by J. Marques-Silva and K. A. Sakallah, 272–286. Berlin, Heidelberg: Springer Berlin Heidelberg.

Esposito, M., and C. Van den Broeck. 2010. “Three Faces of the Second Law. I. Master Equation Formulation.” Physical Review E 82 (1): 011143.

————. 2011. “Second Law and Landauer Principle Far from Equilibrium.” EPL (Europhysics Letters) 95 (4): 40004.

Frank, M., T. Knight, and N. Margolus. 1998. “Reversibility in Optimally Scalable Computer Architectures.” In Unconventional Models of Computation (Auckland, 1998), 165–182. Springer Ser. Discrete Math. Theor. Comput. Sci. Springer, Singapore.

Fredkin, E., and T. Toffoli. 1982. “Conservative Logic.” Internat. J. Theoret. Phys. 21 (3): 219–253.

Grochow, J. A., and D. H. Wolpert. 2018. “Beyond Number of Bit Erasures: New Complexity Questions Raised by Recently Discovered Thermodynamic Costs of Computation.” SIGACT News 54 (2).

Halpern, N. Y., A. J. P. Garner, O. C. O. Dahlsten, and V. Vedral. 2015. “Introducing One-Shot Work into Fluctuation Relations.” Focus Issue on Quantum Thermodynamics. Preprint available as arXiv:1409.3878 [condmat.stat-mech], New J. Phys. 17 (095003).

Hasegawa, H.-H., J. Ishikawa, K. Takara, and D. J. Driebe. 2010. “Generalization of the Second Law for a Nonequilibrium Initial State.” Physics Letters A 374 (8): 1001–1004.

Hirahara, S., I. C. Oliveira, and R. Santhanam. 2018. “NP-Hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits.” In 33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA, 5:1–5:31.

Hopcroft, J. E., R. Motwani, and U. Rotwani. 2000. JD: Introduction to Automata Theory, Languages and Computability.

Horowitz, J. M., and M. Esposito. 2014. “Thermodynamics with Continuous Information Flow.” Phys. Rev. X 4 (3): 031015.

Jarzynski, C. 1997. “Nonequilibrium Equality for Free Energy Differences.” Physical Review Letters 78 (14): 2690.

Karmarkar, N. 1984. “A New Polynomial-Time Algorithm for Linear Programming.” Combinatorica 4 (4): 373–395.

Khačijan, L. G. 1979. “A Polynomial Algorithm in Linear Programming.” Dokl. Akad. Nauk SSSR 244 (5): 1093–1096.

Kol, G., S. Moran, A. Shpilka, and A. Yehudayoff. 2014. “Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound.” In Automata, Languages, and Programming (ICALP 2014), 701–712. Springer.

Kolchinsky, A., and D. H. Wolpert. 2016. Dependence of Dissipation on the Initial Distribution over States. Preprint available as arXiv:1607.00956 [cond-mat.statmech].

Kugler, L. 2015. “Is ‘Good Enough’ Computing Good Enough?” Commun. ACM 58, no. 5 (April): 12–14. doi:10.1145/2742482.

Landauer, R. 1961. “Irreversibility and Heat Generation in the Computing Process.” IBM Journal of Research and Development 5 (3): 183–191.

————. 1991. “Information is Physical.” Physics Today 44:23.

————. 1996a. “Minimal Energy Requirements in Communication.” Science 272 (5270): 1914–1918.

————. 1996b. “The Physical Nature of Information.” Physics Letters A 217 (4): 188–193.

Lange, K.-J., P. McKenzie, and A. Tapp. 2000. “Reversible Space Equals Deterministic Space.” Twelfth Annual IEEE Conference on Computational Complexity (Ulm, 1997), J. Comput. System Sci. 60 (2, part 2): 354–367.

Lasserre, J. B. 2001a. “An Explicit Exact SDP Relaxation for Nonlinear 0–1 Programs.” In Integer Programming and Combinatorial Optimization (Utrecht, 2001), 2081:293–303. Lecture Notes in Comput. Sci. Springer, Berlin. doi:10.1007/3-540-45535-3_23.

————. 2001b. “Global Optimization with Polynomials and the Problem of Moments.” SIAM J. Optim. 11 (3): 796–817. doi:10.1137/S1052623400366802.

————. 2010. Moments, Positive Polynomials and their Applications. 1:xxii+361. Imperial College Press Optimization Series. Imperial College Press, London.

Lasserre, J. B. 2015. An Introduction to Polynomial and Semi-Algebraic Optimization. xiv+339. Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge.

Levin, L. A. 1974. “Laws on the Conservation (Zero Increase) of Information, and Questions on the Foundations of Probability Theory.” Problemy Peredači Informacii 10 (3): 30–35.

————. 1986. “Average Case Complete Problems.” SIAM J. Comput. 15 (1): 285– 286.

Levine, R. Y., and A. T. Sherman. 1990. “A Note on Bennett’s Time–Space Tradeoff for Reversible Computation.” SIAM J. Comput. 19 (4): 673–677.

Leyffer, S., S. M. Wild, M. Fagan, M. Snir, K. Palem, K. Yoshii, and H. Finkel. 2016. Doing Moore with Less—Leapfrogging Moore’s Law with Inexactness for Supercomputing. arXiv:1610.02606 [cs.OH].

Li, M., J. Tromp, and P. Vitányi. 1998a. “Reversible Simulation of Irreversible Computation.” In Proceedings of the Fourth Workshop on Physics and Computation, 168–176. PhysComp96. Boston, Massachusetts: Elsevier Science Publishers B. V.

————. 1998b. “Reversible Simulation of Irreversible Computation.” Phys. D 120, nos. 1-2 (September): 168–176.

Lokam, S. V. 2000. “On the Rigidity of Vandermonde Matrices.” Theoret. Comput. Sci. 237 (1–2): 477–483.

Lovász, L., and A. Schrijver. 1991. “Cones of Matrices and Set-Functions and 0–1 Optimization.” SIAM J. Optim. 1 (2): 166–190.

Lynch, N. A. 1996. Distributed Algorithms. Morgan Kaufmann, San Francisco, CA.

Markoff, J. 2015. “A Climate-Modeling Strategy That Won’t Hurt the Climate.” The New York Times (May).

MathWorks, Inc. 2017. MATLAB. Natick, MA, USA.

Mitzenmacher, M., and E. Upfal. 2005. Probability and Computing. Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge.

Moore, C., and S. Mertens. 2011. The Nature of Computation. Oxford University Press.

Morita, Kenichi. 2008. “Reversible computing and cellular automata—a survey.” Theoret. Comput. Sci. 395 (1): 101–131. http://dx.doi.org/10.1016/j.tcs.2008.01.041.

Motwani, R., and P. Raghavan. 1995. Randomized Algorithms. Cambridge University Press, Cambridge.

Müller, M., and J. Scharlau. 2014. Single-Shot Quantum Thermodynamics—Lecture Notes. Course materials available at http://www.mpmueller.net/lecture2.html.

Mulmuley, K. D. 1993. Computational Geometry: An Introduction through Randomized Algorithms. Pearson.

Newman, M., A.-L. Barabási, and D. J. Watts. 2006. The Structure and Dynamics of Networks. Princeton Studies in Complexity. Princeton University Press.

Owen, J., A. Kolchinsky, and D. H. Wolpert. 2019. Number of Hidden States Needed to Physically Implement a Given Conditional Distribution, January.

Palem, K., A. Lingamneni, C. Enz, and C. Piguet. 2013. “Why Design Reliable Chips when Faulty Ones are Even Better.” In 2013 Proceedings of the ESSCIRC. IEEE.

Palmer, T., P. Düben, and H. McNamara. 2014. “Stochastic Modelling and Energy-Efficient Computing for Weather and Climate Prediction.” Phil. Trans. R. Soc. A 372:20140118.

Parrondo, J. M. R., J. M. Horowitz, and T. Sagawa. 2015. “Thermodynamics of Information.” Nature Physics 11 (2): 131–139.

Plenio, M. B., and V. Vitelli. 2001. “The Physics of Forgetting: Landauer’s Erasure Principle and Information Theory.” Contemp. Phys. 42 (1): 25–60.

Pollard, B. S. 2016. “A Second Law for Open Markov Processes.” Preprint available as arXiv:1410.6531 [cond-mat.stat-mech], Open Syst. Inf. Dyn. 23:1650006.

Prokopenko, M., and I. Einav. 2015. “Information Thermodynamics of Near-Equilibrium Computation.” Phys. Rev. E 91 (6): 062143.

Sagawa, T. 2014. “Thermodynamic and Logical Reversibilities Revisited.” Journal of Statistical Mechanics: Theory and Experiment 2014 (3): P03025.

Sagawa, T., and M. Ueda. 2009. “Minimal Energy Cost for Thermodynamic Information Processing: Measurement and Information Erasure.” Phys. Rev. Lett. 102 (25): 250602.

————. 2012. “Fluctuation Theorem with Information Exchange: Role of Correlations in Stochastic Thermodynamics.” Phys. Rev. Lett. 109 (18): 180602.

Savage, J. E. 1998. Models of Computation. Vol. 136. Addison-Wesley.

Schrijver, A. 1986. Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. A Wiley-Interscience Publication. John Wiley & Sons, Ltd., Chichester.

Seifert, U. 2012. “Stochastic Thermodynamics, Fluctuation Theorems and Molecular Machines.” Rep. Progress Phys. 75 (12): 126001.

Selman, B., H. A. Kautz, and B. Cohen. 1993. “Local Search Strategies for Satisfiability Testing.” In Cliques, Coloring, and Satisfiability, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, October 11–13, 1993, 521–532.

Sherali, H. D., and W. P. Adams. 1990. “A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero–One Programming Problems.” SIAM J. Discrete Math. 3 (3): 411–430.

Shizume, K. 1995. “Heat Generation Required by Information Erasure.” Phys. Rev. E 52 (4): 3495.

Sipser, M. 2012. Introduction to the Theory of Computation. 3rd. Cengage Learning.

St. Amant, R., A. Yazdanbakhsh, J. Park, B. Thwaites, H. Esmaeilzadeh, A. Hassibi, L. Ceze, and D. Burger. 2014. “General-Purpose Code Acceleration with Limited-Precision Analog Computation.” In Proceeding of the 41st Annual International Symposium on Computer Architecuture, 505–516. ISCA ’14. Minneapolis, Minnesota, USA: IEEE Press.

Sutner, K. 2004. “The Complexity of Reversible Cellular Automata.” Theoret. Comput. Sci. 325 (2): 317–328.

Szilard, L. 1964. “On the Decrease of Entropy in a Thermodynamic System by the Intervention of Intelligent Beings.” Behavioral Science 9 (4): 301–310.

Takara, K., H.-H. Hasegawa, and D. J. Driebe. 2010. “Generalization of the second law for a transition between nonequilibrium states.” Phys. Lett. A 375 (2): 88–92.

Touchette, H., and S. Lloyd. 2004. “Information-Theoretic Approach to the Study of Control Systems.” Physica A 331 (1): 140–172.

Tyagi, N., J. Lynch, and E. D. Demaine. 2016. “Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms.” In Reversible Computation, 9720:121–136. Lecture Notes in Comput. Sci. Springer.

Valiant, L. G. 1976. “Graph-Theoretic Properties in Computational Complexity.” Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, NM, 1975), J. Comput. System Sci. 13 (3): 278–285.

Van den Broeck, C., et al. 2013. “Stochastic Thermodynamics: A Brief Introduction.” Phys. Complex Colloids 184:155–193.

Van den Broeck, C., and M. Esposito. 2015. “Ensemble and Trajectory Thermodynamics: A Brief Introduction.” Physica A: Statistical Mechanics and its Applications 418:6–16.

Vazirani, V. V. 2001. Approximation Algorithms. Springer-Verlag, Berlin.

Vitányi, P. 2005. “Time, Space, and Energy in Reversible Computing.” In Proceedings of the 2nd Conference on Computing Frontiers, 435–444. CF ’05. Ischia, Italy: ACM.

von Neumann, J. 1956. “Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components.” In Automata Studies, 43–98. Annals of Mathematics Studies, no. 34. Princeton University Press, Princeton, N. J.

Wikipedia Contributors. 2017. List of random number generators. Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/wiki/List_of_random_number_generators.

Wolfram, S. 1999. The Mathematica® Book. Fourth. Wolfram Media, Inc., Champaign, IL; Cambridge University Press, Cambridge.

Wolpert, D. H., and A. Kolchinsky. 2018. “The Entropic Costs of Straight-Line Circuits.” arXiv preprint arXiv:1806.04103.

Wolpert, D. H., A. Kolchinsky, and J. Owen. 2017. The Minimal Hidden Computer Needed to Implement a Visible Computation. arXiv:1708.08494.

Yannakakis, M. 1991. “Expressing Combinatorial Optimization Problems by Linear Programs.” J. Comput. System Sci. 43 (3): 441–466.

BACK TO The Energetics of Computing in Life & Machines