Reversible computing

Reversible computing

Reversible computing is a model of computing where the computational process to some extent is reversible, i.e., time-invertible. A necessary condition for reversibility of a computational model is that the transition function mapping states to their successors at a given later time should be one-to-one. Reversible computing is generally considered an unconventional form of computing.

There are two major, closely related, types of reversibility that are of particular interest for this purpose: physical reversibility and logical reversibility.[1]

A process is said to be physically reversible if it results in no increase in physical entropy; it is isentropic. These circuits are also referred to as charge recovery logic or adiabatic computing. Although in practice no nonstationary physical process can be exactly physically reversible or isentropic, there is no known limit to the closeness with which we can approach perfect reversibility, in systems that are sufficiently well-isolated from interactions with unknown external environments, when the laws of physics describing the system's evolution are precisely known.

Probably the largest motivation for the study of technologies aimed at actually implementing reversible computing is that they offer what is predicted to be the only potential way to improve the energy efficiency of computers beyond the fundamental von Neumann-Landauer limit [2] of kT ln(2) energy dissipated per irreversible bit operation.

As was first argued by Rolf Landauer of IBM,[3] in order for a computational process to be physically reversible, it must also be logically reversible. Landauer's principle is the loosely formulated notion that the erasure of n bits of information must always incur a cost of nk ln(2) in thermodynamic entropy. A discrete, deterministic computational process is said to be logically reversible if the transition function that maps old computational states to new ones is a one-to-one function; i.e. the output logical states uniquely defines the input logical states of the computational operation.

For computational processes that are nondeterministic (in the sense of being probabilistic or random), the relation between old and new states is not a single-valued function, and the requirement needed to obtain physical reversibility becomes a slightly weaker condition, namely that the size of a given ensemble of possible initial computational states does not decrease, on average, as the computation proceeds forwards.

Contents

The reversibility of physics and reversible computing

Landauer's principle (and indeed, the second law of thermodynamics itself) can also be understood to be a direct logical consequence of the underlying reversibility of physics, as is reflected in the general Hamiltonian formulation of mechanics, and in the unitary time-evolution operator of quantum mechanics more specifically.

In the context of reversible physics, the phenomenon of entropy increase (and the observed arrow of time) can be understood to be consequences of the fact that our evolved predictive capabilities are rather limited, and cannot keep perfect track of the exact reversible evolution of complex physical systems, especially since these systems are never perfectly isolated from an unknown external environment, and even the laws of physics themselves are still not known with complete precision. Thus, we (and physical observers generally) always accumulate some uncertainty about the state of physical systems, even if the system's true underlying dynamics is a perfectly reversible one that is subject to no entropy increase if viewed from a hypothetical omniscient perspective in which the dynamical laws are precisely known.

The implementation of reversible computing thus amounts to learning how to characterize and control the physical dynamics of mechanisms to carry out desired computational operations so precisely that we can accumulate a negligible total amount of uncertainty regarding the complete physical state of the mechanism, per each logic operation that is performed. In other words, we would need to precisely track the state of the active energy that is involved in carrying out computational operations within the machine, and design the machine in such a way that the majority of this energy is recovered in an organized form that can be reused for subsequent operations, rather than being permitted to dissipate into the form of heat.

Although achieving this goal presents a significant challenge for the design, manufacturing, and characterization of ultra-precise new physical mechanisms for computing, there is at present no fundamental reason to think that this goal cannot eventually be accomplished, allowing us to someday build computers that generate much less than 1 bit's worth of physical entropy (and dissipate much less than kT ln 2 energy to heat) for each useful logical operation that they carry out internally.

The motivation behind much of the research that has been done in reversible computing was the first seminal paper on the topic,[4][5] which was published by Charles H. Bennett of IBM research in 1973. Today, the field has a substantial body of academic literature behind it. A wide variety of reversible device concepts, logic gates, electronic circuits, processor architectures, programming languages, and application algorithms have been designed and analyzed by physicists, electrical engineers, and computer scientists.

This field of research awaits the detailed development of a high-quality, cost-effective, nearly reversible logic device technology, one that includes highly energy-efficient clocking and synchronization mechanisms. This sort of solid engineering progress will be needed before the large body of theoretical research on reversible computing can find practical application in enabling real computer technology to circumvent the various near-term barriers to its energy efficiency, including the von Neumann-Landauer bound. This may only be circumvented by the use of logically reversible computing, due to the Second Law of Thermodynamics.

See also

References

  1. ^ http://www.cise.ufl.edu/research/revcomp/
  2. ^ J. von Neumann, Theory of Self-Reproducing Automata, Univ. of Illinois Press, 1966.
  3. ^ R. Landauer, "Irreversibility and heat generation in the computing process," IBM Journal of Research and Development, vol. 5, pp. 183-191, 1961.
  4. ^ C. H. Bennett, "Logical reversibility of computation," IBM Journal of Research and Development, vol. 17, no. 6, pp. 525-532, 1973.
  5. ^ C. H. Bennett, "The Thermodynamics of Computation -- A Review," International Journal of Theoretical Physics, vol. 21, no. 12, pp. 905-940, 1982.

Review of later theoretical work: P.M.B. Vitanyi, Time, space, and energy in reversible computing, Proceedings of the 2nd ACM conference on Computing frontiers, 2005, 435–444.

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Reversible Computing/3 input universal logic gates — Logic gates are used to build computer chips. Reversible logic gates are of interest because they could in principle generate useful results for less heat generated (Landauer 1961). The nand gate is universal among irreversible logic gates, in… …   Wikipedia

  • Reversible process (thermodynamics) — For articles on other forms of reversibility, including reversibility of microscopic dynamics, see reversibility (disambiguation). In thermodynamics, a reversible process, or reversible cycle if the process is cyclic, is a process that can be… …   Wikipedia

  • Reversible dynamics — Mathematics In mathematics, a dynamical system is invertible if the forward evolution is one to one, not many to one; so that for every state there exists a well defined reverse time evolution operator.The dynamics are time reversible if there… …   Wikipedia

  • Unconventional computing — is computing by a wide range of new or unusual methods. It is also known as alternative computing. The different methods of unconventional computing include optical computing, quantum computing, chemical computing, natural computing, biologically …   Wikipedia

  • Reversibles Computing — Der Begriff Rechnerreversibilität oder englisch Reversibles Computing bezeichnet eine Architektur für Computer, die (wenigstens näherungsweise) reversibel ist, bei deren Berechnungen also aus dem Endresultat auch der Anfangszustand… …   Deutsch Wikipedia

  • Natural computing — For the scientific journal, see Natural Computing (journal). Natural computing, also called Natural computation, is a terminology introduced to encompass three classes of methods: 1) those that take inspiration from nature for the development of… …   Wikipedia

  • Timeline of quantum computing — Timeline of quantum computers1970s* 1970 Stephen Wiesner invents conjugate coding.* 1973 Alexander Holevo publishes a paper showing that n qubits cannot carry more than n classical bits of information (a result known as Holevo s theorem or Holevo …   Wikipedia

  • Timeline of computing hardware 2400 BC–1949 — History of computing Hardware before 1960 Hardware 1960s to present Hardware in Soviet Bloc countries Artificial intelligence Computer science Operating systems Programming languages …   Wikipedia

  • Orders of magnitude (computing) — This list compares various amounts of computing power in instructions per second organized by order of magnitude. Scientific E notation index: 1 | 0 | 3 | 6 | 9 | 12 | 15 | 18 | 24 Contents 1 10 1 2 10 …   Wikipedia

  • Construction Field Computing — is the use of handheld devices that augment the construction superintendent s ability to manage the operations on a construction site. These information appliances (IA) must be portable devices which can be carried or worn by the user, and have… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”