Reversible Logic

Suppose you have a bit, it doesn't matter what it is, zero or one (in fact, the argument below depends on your not knowing).

Consider it as a thermodynamic ensemble. There's one degree of freedom with two states available. Now destroy the bit, force it into a known state. The "ensemble" now has no degrees of freedom and one state. The entropy of the system has been reduced by:

 k ln 2 Joules/Kelvin (k = Boltzmann's Constant)

(provided certain other conditions are met, which in practice they are).

It used to be thought that the information talked about in thermodynamics (as the converse of entropy) was different from the information talked about in informatics. This is now known not to be so: they are identical.

This is quite wrong; see, for instance, http://www.secondlaw.com/six.html

I would not say "quite wrong". See for instance http://en.wikipedia.org/wiki/Information_entropy

So, now consider a three-terminal logic gate, NAND, for instance. Shaeffer and Pearce showed that you can build any logic network you like given only one kind of gate, and you have a set of possible kinds from which to choose that one. For reasons of easy fabrication NAND is a popular choice for microelectronics. Anyway, you've got your gate:

  a | b |  a NAND b
 ===================
  0 | 0 |     1
  0 | 1 |     1
  1 | 0 |     1
  1 | 1 |     0

Notice that in a circuit, on every change of state two bits go in, one bit comes out. Therefore, over and above resistive losses in the material, the gate must dissipate:

 k log 2 T Joules per state transition (T is the absolute temperature)

How does this compare to the total power consumption of gates on modern processors, at their typical operating temperatures?

Answer: Suppose we have a 1GHz processor with 20M gates switching every cycle: http://www.google.com/search?lr=&ie=UTF-8&q=k+*+log%282%29+*+%2860%2B273%29+Kelvin+*+1+GHz+*+%282+*+10%5E7%29&btnG=Search Google says we're talking about 0.00003 watts. -- AdamBerger

If the processor has 20M gates total, this approximates an upper limit, since real life processors do not switch every gate on every cycle, so the average figure would be even lower. BTW I had remembered a significantly lower number, so it surprised me to hear something as high as 3e-5 watts. Perhaps it was with different assumptions.

this places an upper limit on the efficiency of circuits built from three-port gates.

But , it is possible to build circuits from many-port gates that do not destroy the capacity to store information (and are hence an example of ReversibleLogic). Because each state-change is reversible, the (logical) states are thermodynamically identical. No destruction of information = no decrease in entropy = arbitrarily efficient circuits.

Actually, for logic circuits this effect doesn't matter so much at the moment, but it has a big impact on memory.

Sounds like this to me: http://en.wikipedia.org/wiki/Von_Neumann-Landauer_limit -- AaronRobson

executive summary

Anyway, the upshot is that by running your processor sufficiently slowly, you can reduce its power consumption arbitrarily.

Um, no. I think you missed the point: With circuits built from reversible logic gates, you can (in theory) reduce power consumption arbitrarily while running at full speed. (The "minimum amount of energy dissipated per switch" only applies to circuits built from non-reversible gates, such as NAND and NOR).

Would you give an example of such a "reversible logic gate"?

The classic is the six-port "Fredkin Gate" which behaves like this:

 a|b|c| Fa| Fb| Fc|
 ====================
 0|0|0| 0 | 0 | 0 |
 0|1|0| 0 | 1 | 0 |
 1|0|0| 1 | 0 | 0 |
 1|1|0| 1 | 1 | 0 |
 0|0|1| 0 | 0 | 1 |
 0|1|1| 1 | 0 | 1 |
 1|0|1| 0 | 1 | 1 |
 1|1|1| 1 | 1 | 1 |

that is, when the "control" line is high, the other two inputs are exchanged.

With four such gates, a four-port gate can be built that simultaneously generates the AND and OR of two bits. See http://www.research.ibm.com/journal/sj/mit/sectione/gershenfeld.html, figure 6.

ReversibleLogic requires non-destruction of information. Therefore the number of inputs must be equal to the number of outputs. (If there were more outputs than inputs, the reverse direction wouldn't be reversible!)

An AND gate with an output of zero (or OR with op=1) has 3 possible input combinations (00, 01, 10). To provide sufficient information at the output to reverse an AND gate requires 3 output values.

These two results lead to the conclusion that reversible universal computation requires gates with a minimum of 3 inputs and outputs.

The Fredkin gate, above, gives

  Fa = b AND c when a=0;
  Fb = b OR c  when a=1;
  Fb = NOT c   when a=0 and b=1.

So it is clearly a universal gate. As long as you don't lose the garbage bits (it is possible to reversibly erase them), you can build a reversible universal computer out of it.

I showed above that gates with 3 inputs and outputs are required for reversible computation. This is only true if you stick with classical physics. If you build gates based on quantum bits (qbits), then 2 inputs/outputs are sufficient. The system will remain reversible until you look at its output. In its reversible state it will use no energy, yet it can still calculate a result!

-- DaveWhipp

Reversible logic can be implemented in microelectronics, and at http://www.ai.mit.edu/~cvieri/reversible.html there is a design of a reversible processor.

Other approaches to ReversibleLogic use BallisticComputation?, MechanicalComputation? and CellularAutomata as their basis technology.

Also, it's interesting to note that QuantumComputation? is inherently reversible, since it relies on quantum ensembles evolving under the "control" of some UnitaryOperator?, which is necessarily self-adjoint and so self-inverse.

ClocklessLogic?

I read somewhere that the NullConventionLogic? described on http://theseus.com/ is also partially ReversibleLogic. Does anyone have conclusive information? -- ShaeErisson

A brief glance at that website shows me that they use gates with more inputs than outputs. Therefore, those gates cannot possibly be (perfectly) ReversibleLogic.

ClocklessLogic?, like ReversibleLogic, is a technique that (theoretically) can lead to circuits that run just as fast as normal Synchronous CMOS BooleanLogic, but use less power.

They seem to be orthogonal approaches. (Hmm, I wonder if anything interesting happens if I connect ReversibleLogic gates in a NullConventionLogic? fashion ?)

(I'm tempted to make a ClocklessLogic? page for my info on ClocklessLogic? and metastability http://rdrop.com/~cary/html/vlsi.html#clockless ... or would that be OffTopic ?)

-- DavidCary

Aside from low power consumption, reversible programs have properties that make them interesting to debug. From http://www.cise.ufl.edu/~mpf/rc/memos/M08/doc/node2.html -

'If the conditions [of program correctness] are not met, then the program will silently proceed anyway, with nonsensical (but still reversible) behavior. However, this is not as fatal as it sounds, because the reversibility of execution allows the errant program to be debugged, after the misbehavior is discovered, by running it in reverse from the error to see what caused it.'

Aha! YouDontWantAnExceptionYouWantaTimeMachine

See ReversibleProgrammingLanguage

CategoryLogic