Reversible Logic

(Also known as Charge Recovery Logic or Adiabatic Logic)

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:

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.

Wikipedia has an article on reversible computing.

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.

A workshop on the Physics of Computation was held at MIT in 1981; the papers were printed in the April, June and December issues of the 1982 International Journal for Theoretical Physics, Volume 21.

The Physics and Computation workshop series was held for several years starting in 1992. See the final program for PhysComp '94. PhysComp '96 was held in Boston in November of 1996. These workshops covered reversible logic and several other areas related to physics and computation.

A popular article is Silicon in Reverse by Peter Wayner, Byte Magazine, August 1994, page 67.

In the last few years, several researchers independently realized that reversible logic could be implemented using conventional CMOS circuits. This has stimulated several research groups to pursue the subject.

Paul Vitanyi maintains a page with papers and links on reversible computing.

There is a related page about the Physics of Computation at MIT.

The April 1995 issue of the Proceedings of the IEEE (Vol. 83, No. 4, pages 493-700) is a special issue on Low-Power Electronics. It provides useful background information for those interested in reversible logic, even though it has little direct discussion of the subject.

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 (pdf), 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.

A 2006 article on reversible logic from the American Scientist is available on the web.

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



This page is part of the nanotechnology web site.