CIS 6930.3753X Spr.'02
Readings for Part V: 
Reversible Computing

Continue following the general advice on reading assignments from the first readings page.

Index to the below:

Lecture 21: Fundamental principles of adiabatic processes

Carnot's original paper where he invents reversible heat engines and shows that they have the greatest possible thermodynamic efficiency. Some relevant modern textbook sections discussing adiabatic processes (the original definition), thermodynamics, and reversible engines: Discussion of the evolution of the meaning of the word "adiabatic": Discussion of the quantitative adiabatic principle (time-proportional reversibility):

Lecture 22: Fundamental adiabatics cont.; categorization of adiabatic logic & memory

The Adiabatic Theorem of quantum mechanics: Adiabatic transitions in logic:

Lectures 23 & 24: Adiabatic electronics & CMOS Implementations

Other sources: A good technical overview of adiabatic switching from a leading textbook: Two references for the detailed formula for dissipation for voltage-ramp charging through a resistance, in case you're interested in how it was derived: These guys actually made sensitive experimental measurements (using Peltier coolers) verifying the predicted low energy dissipation of adiabatic circuits:
  • Paul Solomon and David Frank, "Power measurements of adiabatic circuits by thermoelectric technique," Symposium on Low Power Electronics, pp. 18-19, 1995.  Scanned PDF.
    • Here's Hall's 1992 paper on a not fully-pipelined, but otherwise fine adiabatic circuit style based on abstract swiches (which could actually be implemented in CMOS using transmission gates and dual-rail signals). Even in a more heavily pipelined reversible architecture like SCRL, this "retractile cascade" idea is still useful within individual pipeline stages. The idea also permits avoiding the order N2 delay elements (and dissipation multiplier) that would be required in a reversible N-bit adder in pure fully-pipelined style such as SCRL. A detailed example of a pipelineable, fully reversible, universal logic family, SCRL: To find oodles of more recent articles on adiabatic circuits, go to IEEE Xplore's search page (http://ieeexplore.ieee.org/lpdocs/epic03/VSearch.htm), and search for anything containing the word "adiabatic" in the title, abstract or subject.  You should be able to access any of these publications online from any .ufl.edu host.

    Lectures 25 & 26: Limits of Adiabatics: Leakage & Power Supplies

    The following sequence of papers establishes that clockless (self-timed) serial and parallel reversible computing is compatible with quantum mechanics.  However, no one has physically implemented these schemes as of yet. Other material on adiabatic power supplies: The following papers describe a resonant clock-waveform generation technique. Although these papers focus on square wave generation, the same technique can also be used to approximate any desired periodic waveform, including the trapezoidal waveforms required for driving adiabatic circuits. The following web page presents some data I gathered in late 1997 regarding the suitability (or lack thereof) of MEMS switches/relays for use in adiabatic circuits. Better MEMS switches than these are probably available by now.

    Lectures 27 & 28: Reversible Computing Theory: Logic Models, Emulation, Lower Bounds

    The paper that introduces the "Landauer embedding" of irreversible computations in reversible ones.  But this wasn't originally seen as useful because it accumulated "garbage" information which Landauer thought would still have to be eventually thermalized. Here is the first rigorous formal description of a irreversible-to-reversible embedding.  Lecerf's method uncomputes the garbage, but unfortunately also the computation's output.  This is the paper that introduced "Lecerf reversal" for disposing of garbage from a Landauer embedding: Bennett's early paper fixes the problem with Lecerf's method and resolves the issue.  This was the first complete irreversible-to-reversible embedding that actually does something useful.This historic paper first established that it is theoretically possible to compute usefully in an entirely logically-reversible fashion without accumulating garbage information (digital entropy). This next paper applies the same insights to a boolean logic-circuit model of computation, showing that reversible boolean circuits are capable of universal computation. This next paper by Bennett gives a class of more space-efficient algorithms.  This is still the best simulation in terms of overall spacetime requirements; probably the best possible.  Levine and Sherman analyze it thoroughly. This paper shows that the time/space tradeoff in reversibility extends to the point where linear space is possible, but with exponential time. Some progress towards proving the standing conjecture that no general-purpose simulation of irreversible machines by reversible ones can be more spacetime-efficient than Bennett's 1989 algorithm.

    Lectures 29 & 30.  Scaling Advantages of Reversible Computing

    Lectures 31 & 32. Reversible gate-array, instruction-set, & CPU architectures: FlatTop, Pendulum.

    Lectures 32 & 33.  Reversible high-level languages & algorithms.


    More readings left over from Y2K, not yet organized under one of this year's lectures
    Y2K Lecture 17: Adiabatic Circuits: Wrap-Up (Slides in PDF here)

    Additional Resources

    Here are some web links where you can find additional papers, information, and resources on adiabatic circuits and reversible logic.