Reversible Computation and Freeing Memory

[MrMormon]

What's the concern with a complex system? The only concern is reducing heat generated near the main processor(s).

I'm not sure you understand garbage bits - memory is 'filled' because the unneeded bits of every reversible operation are preserved, and gates are part of computing, not memory. You can't just shift around and keep the garbage bits forever, because information is always increasing with input into the computer.

 

[arfa brane]

Here's the wiki on Landauer's principle (note: "the erasure problem" appears to be an adapted terminology, I think Bennet uses it though)

"Landauer's Principle, first argued in 1961[1] by Rolf Landauer of IBM, holds that "any logically irreversible manipulation of information, such as the erasure of a bit or the merging of two computation paths, must be accompanied by a corresponding entropy increase in non-information bearing degrees of freedom of the information processing apparatus or its environment". (Bennett 2003)[2].

The Landauer's Principle describes the Landauer limit, which is the minimum possible amount of energy required to change one bit of information, as follows:

kT · ln 2

Where…
k is the Boltzmann constant
T is the absolute temperature of the circuit in kelvins
ln 2 is the natural logarithm of 2, which is approximately 0.69315

At 25 °C (room temperature, or 298.15 kelvins), the Landauer limit represents an energy of approximately 0.0178 electron volt. Theoretically, room‑temperature computer memory operating at the Landauer limit could be changed at a rate of one billion bits per second with only 2.85 trillionths of a watt of power being expended in the memory media.

If no information is erased, computation may in principle be achieved which is thermodynamically reversible, and require no release of heat. This has led to considerable interest in the study of reversible computing."

 

[MrMormon]

If no information is erased

I can imagine a computer with several TB of RAM that can run with no heat for a long time, but eventually one would have to stop using it for a little while to let it erase garbage bits so that it can be reused. Still, not ideal.

 

[arfa brane]

I'm not sure you understand garbage bits - memory is 'filled' because the unneeded bits of every reversible operation are preserved, and gates are part of computing, not memory.

But if you build a computer with "sufficient" gates that a separate memory isn't needed, that is, you use every gate once and "keep the inputs" then the inputs are equivalent to memory, the computer "remembers" all the inputs for a computation.

Modern digital computers do use gates more than once, hence the outputs of gates are stored in a separate set of memory registers, but the memory is also reused, hence "the erasure problem" and heat that has to dissipate (equivalent to the information which is erased according to Landauer's principle).

Then a computer with no separate memory and a large enough number of gates can perform a reversible computation, as long as none of the inputs corresponding to any computation are erased or dissipated. Then there aren't any garbage bits.

 

[MrMormon]

It's true that one doesn't need intermediate memory with the right combination of gates to implement any finite algorithm, but most computers aren't just used for running algorithms like supercomputers. Much more importantly, I don't think configurable reversible circuits would be as fast as static ones. Look at FPGAs.

 

[arfa brane]

It's true that one doesn't need intermediate memory with the right combination of gates to implement any finite algorithm, but most computers aren't just used for running algorithms like supercomputers.

But aren't we discussing reversible computation? The "right combination" is logic gates whose outputs include some (or all) of their inputs so that logical reversibility (by computing the inputs from the outputs) is possible.

Physical reversibility

Known laws of physics are reversible. This is the case both of classical mechanics, based on lagrangian/hamiltonian dynamics, and of standard quantum mechanics, where closed systems evolve by unitary transformations, which are bijective and invertible. As a consequence, when a physical system performs an irreversible computation, the computation model’s mapping indicates that the computing system cannot stay closed.

More precisely, since an irreversible computation reduces the space of physical information-bearing states, then their entropy must decrease by increasing the entropy of the non-information bearing states, representing the thermal part of the system.

In 1961 Landauer studied this thermodynamical argument, and proposed the following principle: if a physical system performs a logically irreversible classical computation, then it must increase the entropy of the environment with an absolute minimum of heat release of kT x ln(2) per lost bit (where k is Boltzmann’s constant and T the temperature, ie. about 3 x 10-21 joules at room temperature), which emphasizes two facts:

* the logical irreversibility of a computation implies the physical irreversibility of the system performing it (”information is physical”);

* logically reversible computations may be at least in principle intrinsically nondissipative (which bears a relationship with Carnot’s heat engine theorem, showing that the most efficient engines are reversible ones, and Clausius theorem, attributing zero entropy change to reversible processes).

 

[MrMormon]

But aren't we discussing reversible computation? The "right combination" is logic gates whose outputs include some (or all) of their inputs so that logical reversibility (by computing the inputs from the outputs) is possible.

Yes, but individually. Gates modify memory - they aren't memory.

Also, why aren't others commenting too?

 

[arfa brane]

Yes, but individually. Gates modify memory - they aren't memory.

I think you misunderstand. If say a 2-input gate doesn't change either input and computes an output, then it remembers the inputs.

So maintaining inputs is the same thing as storing their states in memory. All you need to do is make the inputs into outputs and you have the equivalent of memory--as long as the inputs don't change.

In other words, if you use each gate once only, and pass the inputs through to another gate you use at some later time to compute reversibly. Which means, recover the inputs from all the outputs. This is exactly what Toffoli and Fredkin gates do.

 

[MrMormon]

I think you misunderstand. If say a 2-input gate doesn't change either input and computes an output, then it remembers the inputs.

So maintaining inputs is the same thing as storing their states in memory.

It sounds like you're proposing flash memory or something else that can only maintain a state as long as the computer is running.

 

[arfa brane]

It sounds like you're proposing flash memory or something else that can only maintain a state as long as the computer is running.

It sounds like you don't actually understand the subject of reversible computing.

Do you know what a 3-input/3-output gate is, and why anyone would bother to design one?
Do you understand why your idea means you would need a fairly complex memory system, and why it would restrict the speed of a reversible computer if it had to erase information? So there wouldn't be any overall improvement in computational efficiency, unless the memory was large enough that information wasn't erased, in which case the circuit controlling the memory would be at least as complex, if not more complex, than the rest of the computer?

Which means, your idea hasn't been implemented because it isn't practical?

Sorry, but I think this thread isn't really going anywhere.

 

[MrMormon]

A complex memory system may or may not be a bottleneck. I agree that this conversation is going nowhere, especially since no one else is commenting...

 

[arfa brane]

I agree that this conversation is going nowhere, especially since no one else is commenting...

Yeah. And I was getting bored with repeating myself, too.

 

[MrMormon]

I felt the same way. We're even.

Thanks for talking, though.

 

[funkstar]

Ok, I didn't notice this thread earlier, or I would have replied.

I'd like to comment on one aspect. You both seem to think (please correct me if I'm wrong) that using reversible gates necessarily means that inputs of each individual gate must be conserved, and that they are no longer useful once the gate has been applied. This is not the case, and a large part of coming up with good reversible (and quantum) logic design is finding ways to use the other outputs as well. Indeed, it is perfectly possible to make reversible logic designs where only a tiny number of the input lines (as summed over the number of gates) is conserved.

For example, here's a ripple-carry adder which maps (a,b) to (a,a+b)), with a single ancillae bit, and no "garbage" bits. Note that not all inputs are conserved. This means that you can restrict the growth of "garbage information".

 

[arfa brane]

You both seem to think (please correct me if I'm wrong) that using reversible gates necessarily means that inputs of each individual gate must be conserved, and that they are no longer useful once the gate has been applied.

No, using reversible logic means restoring the initial inputs. So you need to keep enough information around to do this. With the logical OR operation on two inputs, it's possible to restore both input states reliably from the output and one (initial) input.

[ed: oops, actually that's only true of XOR with two-input gates. That's why three-input gates are a better choice, apart from being able to configure such gates by using one or two inputs to control the gate's function.]

So you need an OR gate that preserves one of its inputs. Inversion is obviously logically reversible. That leaves Boolean AND, which can only be logically reversible if both the initial inputs are preserved. AND logic is not affine (it can't be expressed as a linear transformation of its inputs), which is why Boolean logic is not universal.

 

[MrMormon]

In addition (no pun intended), mapping (a,b) to (a,a+b) should be entirely reversible. If you have another example though, that would be great.

 

[funkstar]

No, using reversible logic means restoring the initial inputs.

It doesn't have to. The reversible adder I linked to doesn't, for example: it only conserves one of its two n-bit inputs.

In addition (no pun intended), mapping (a,b) to (a,a+b) should be entirely reversible. If you have another example though, that would be great.

I'm not sure I understand your meaning. I explicitly mentioned it as a reversible example.

 

[arfa brane]

It doesn't have to. The reversible adder I linked to doesn't, for example: it only conserves one of its two n-bit inputs.

You mean, it only conserves or keeps enough of the input information that it can restore all of it?
Isn't that what I've said a number of times?

Anyway, this from the wiki on Toffoli gates:

Reversible gates have been studied since the 1960s. The original motivation was that reversible gates dissipate less heat (or, in principle, no heat). In a normal gate, input states are lost, since less information is present in the output than was present at the input. This loss of information loses energy to the surrounding area as heat, because of thermodynamic entropy. Another way to understand this is that charges on a circuit are grounded and thus flow away, taking a small charge of energy with them when they change state. A reversible gate only moves the states around, and since no information is lost, energy is conserved.

More recent motivation comes from quantum computing. Quantum mechanics requires the transformations to be reversible but allows more general states of the computation (superpositions). Thus, the reversible gates form a subset of gates allowed by quantum mechanics and, if we can compute something reversibly, we can also compute it on a quantum computer.

 

[MrMormon]

a large part of coming up with good reversible (and quantum) logic design is finding ways to use the other outputs as well. Indeed, it is perfectly possible to make reversible logic designs where only a tiny number of the input lines (as summed over the number of gates) is conserved.

I didn't really understand, but I thought your example was trying to demonstrate that 'garbage' bits can be reused. If they can't, then the problem of erasure still hasn't been solved at all.

 

[funkstar]

I didn't really understand, but I thought your example was trying to demonstrate that 'garbage' bits can be reused.

That was pretty much it, yes. You can do more complicated things as well, like reversible ALUs.