Reversible 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.

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.

A more recent source of technical information is the Physics and Computation workshop series, held every other year since 1992. Ordering information for the proceedings of PhysComp '92 and PhysComp '94 is available, as well as the final program for PhysComp '94. New! PhysComp '96 is already being planned. Information on these and other events is available from the physics of computation mailing list. These workshops cover reversible logic and several other areas related to physics and computation.

A recent 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.

A group at USC's Information Sciences Institute has been developing prototype VLSI chips that use adiabatic switching (reversible logic) to reduce energy dissipation. Several papers on both theoretical and experimental results are available electronically from them.

Tom Knight's home page has links to some of his group's papers on Charge Recovery Logic.

Related pages are the physics of computation page at Caltech, and the information mechanics page 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 (6KB html abstract), 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 (also available as a text only HTML version with a separate file containing the figures in postscript); and Two types of mechanical reversible logic (188KB ps), by Ralph C. Merkle, Nanotechnology 4 (1993) pages 114-131.

This brief introduction to reversible logic is provided courtesy of Ralph C. Merkle. Suggestions can be sent to merkle@xerox.com.



This page is part of the nanotechnology web site.