Reversible computation

As we pack more and more logic elements into smaller and smaller volumes and clock them at higher and higher frequencies, we dissipate more and more heat. This creates at least three problems:

   * Energy costs money.
   * Portable systems exhaust their batteries.
   * Systems overheat. 

When a computational system erases a bit of information, it must dissipate ln 2 x kT energy, where k is Boltzmann's constant and T is the temperature. For T = 300 Kelvins (room temperature), this is about 2.9 x 10^-21 joules. This is roughly the kinetic energy of a single air molecule at room temperature.

Today's computers erase a bit of information (in the sense used here) every time they perform a logic operation. These logic operations are therefore called "irreversible." This erasure is done very inefficiently, and much more than kT is dissipated for each bit erased. If we are to continue the revolution in computer hardware performance we must continue to reduce the energy dissipated by each logic operation. Today, because we are dissipating much more than kT, we can do this by improving conventional methods, i.e., by improving the efficiency with which we erase information.

An alternative is to use logic operations that do not erase information. These are called reversible logic operations, and in principle they can dissipate arbitrarily little heat. As the energy dissipated per irreversible logic operation approaches the fundamental limit of ln 2 x kT, the use of reversible operations is likely to become more attractive. If current trends continue this should occur sometime in the 2010 to 2020 timeframe. If we are to reduce energy dissipation per logic operation below ln 2 x kT we will be forced to use reversible logic.

Nanotechnology should let us build mole quantities of logic elements. Unless energy dissipation per logic operation can be reduced below kT, the raw cost of electricity might well prove prohibitive and the system might quickly overheat.

Even today the use of reversible logic operations can be a useful heuristic in the design of systems that use very little power. To achieve a completely reversible system (which erases no bits at all) is very difficult. As we allow more and more bits to be erased during normal system operation, it becomes easier and easier to design the system. Today's systems erase a bit for every logic operation they perform and are very dissipative. Systems that perform some operations in a reversible fashion can dissipate less energy and might prove competitive (particularly in niche applications) today.

For an excellent review of the basic principles, see The Fundamental Limits of Computation by Charles H. Bennett and Rolf Landauer, Scientific American, July 1985, pages 48-56 (38-53 in some versions). For the history, see Notes on the History of Reversible Computation by Charles Bennett, IBM J. Research and Development, Vol. 32, No. 1, January 1988, pages 16-23. See also Ed Fredkin and Fredkin gates.

Three articles that discuss some possible implementations of reversible logic and provide references to further reading are Helical Logic, by Ralph C. Merkle and K. Eric Drexler; Reversible electronic logic using switches (249KB ps), by Ralph C. Merkle, Nanotechnology 4 (1993) pages 21-40; and Two types of mechanical reversible logic, by Ralph C. Merkle, Nanotechnology 4 (1993) pages 114-131.

This brief introduction to reversible logic is provided courtesy of Ralph C. Merkle.