'Reversible' Computers More Energy Efficient

James Clark writes "As Congress continues work on a federal energy bill, a group of University of Florida researchers is working to implement a radical idea for making computers more energy efficient -- as well as smaller and faster." Reversible computing rears its head again.

Comments

Vaporware?

[Carnildo]

Has anyone ever built even a very simple reversible computer? Or is this like quantum computers: all theory, no practice?

Re:Vaporware?

[nestler]

This is more practical than quantum computers because it is much easier to build and can be used for general purpose things other than search and factoring.

The idea is to (down at the gate level) keep everything reversible. For example, current OR gates are not reversible (given a true output you can't definitively tell what either input was individually). If you have two outputs on the gate instead of one, you make the gate reversible. However, since you are just using it for OR, you are free to ignore the second bit you added on to make it reversible.

The bit doesn't help your computation in the sense of the answer you are looking for, but it can make things more energy efficient at the gate level.

Re:Vaporware?

[randyest]

I think you completely misunderstood the article, though in your defense it didn't do a very good job of explaining. The idea is not to be able to reverse logical operations -- that is of little value to anyone. Rather, they're trying to make the electrical changes (the energy transfer) reversible. That's a fundamentally differeent thing. A decent analogy, mentioned in the article is:

The concept is somewhat analogous to hybrid cars now on the market that take the energy generated during braking and recycle it into electricity used to power the car.

So, the logical realm is no different here. Physically, and electrically, there is a big difference from existing computers. Now, when a bit changes from 1->0, the voltage (accumulated charge) is simply shorted to ground (via resistive path that dissipates heat). That energy is lost. In a reversible computer, that charge would be stored, in the electrical equivalent of a spring or flywheel in a mechanical system. So, next time it needs to go 0->1, the energy is sitting there, ready to be re-used(stored in the spring's compression or flywheel's rotation).

I assume these electrical "springs or flywheels" need to be phsycally close to the transistors they're storing energy for. If all transistor's storage were common, the heat loss (and time delay) to get the energy back to where it's needed would defeat the entire purpose.

In the article, they mention that current prototypes use oscillators to store the energy (which are more like a flywheel than a spring, to continue the mechanical analogy), but the efficiency is not quite good enough to be called "reversible". Too much energy is lost in storing and un-storing the energy. The current work is focused on improving the efficiency of storing and un-storing energy from state changes.

However, as a chip designer, I know that oscillators are usually (1) much much bigger than simple logic gates and (2) much more difficult to design with (it's analog design stuff, really). So, my concerns are (1) how much bigger will dice need to be to use this system (linear increase in die size equals exponential increase in manufacturing cost) and (2) how much longer is it going to take to close a design with all those little analog cells all over the place.

I don't even want to think about the implications for STA (static timing analysis) or LVS (layout versus schematic verification) -- it makes my head hurt. :)

Re:Vaporware?

[cgb8176]

I think you completely misunderstood the article, though in your defense it didn't do a very good job of explaining. The idea is not to be able to reverse logical operations -- that is of little value to anyone. Rather, they're trying to make the electrical changes (the energy transfer) reversible. That's a fundamentally differeent thing.

Actually, you are wrong, in that the two things are very intimately related. I will assume that, as a chip designer, you are aware of what AND, OR, and NOT gates are, and that NAND is an example of a universal gate. NAND, however, is not reversible; you cannot in general determine the inputs by looking at the output.

The Fredkin Gate is an example of a reversible gate. As it happens, it is impossible to do reversible computing with two input gates. The Fredkin Gate (a controlled swap; two inputs, two outputs, and a control wire that passes through) has the property that it is

reversible (Fredkin inverts Fredkin), and

it has the same number of non-zero outputs as it does non-zero inputs.

To achieve reversible computing, you need reversible gates. Furthermore, with reversible gates, you can perform any computation with an arbitrarily small amount of energy; the catch is that you need more time (see adiabatic circuits, Carnot engines).

Re:Vaporware?

[Bingo Foo]

Sorry, but reversible computing is about having N distinct ouputs for N distinct inputs in any logical operation. Think thermodynamics and statistical mechanics, where reversibility is intimately coupled with "no production of entropy" which means "no loss of information."

It is at the information theory and logic level of description where reversible computing must be implemented.

Re:Vaporware?

[Chris Burke]

Furthermore, with reversible gates, you can perform any computation with an arbitrarily small amount of energy; the catch is that you need more time (see adiabatic circuits, Carnot engines).

Hey, thanks for the keywords. Google turned up lots of nice stuff.

Though that catch is rather a big one. According to the links, as E->0, T->infinity, which I don't like one bit. Arbitrarily low power, but arbitrarily lengthy computation.

So I've now got my own low-power logic idea. I call it the "apathetic circuit", and it works by not doing the computation at all. Same zero energy/infinite time tradeoff, but with the advantage that the basic "meh" gate can be arbitrarily small even to the point of zero area! :)

"Reversible" a bad name?

[cant_get_a_good_nick]

Wouldn't "regenerative", like regenerative braking on most electrics/hybrids been a better term?

How exactly am I supposed to ...

[burgburgburg]

fry eggs if this sort of thing becomes the norm?

Insensitive clod!

sort of like recycling....

[smd4985]

your computer could spit out: "these CPU cycles made of 75% post-CPU-consumed waste" :)

Something to worry about...

[Nom du Keyboard]

In fact, unless reversible computing is achieved, computer chips are expected to reach their maximum performance capabilities within the next three decades

Boy, that's something to worry about today. I'll just have to find a spot to insert it on my Worry List. Maybe I can drop Global Warming to make space.

Sigh... I knew I shouldn't RTFA

[winkydink]

Here I thought it was an Intel box that, when turned inside out, became a Mac.

Sigh.

Re:Sounds good, but...

[pclminion]

Because it seemed totally pointless. It was a theoretical curiosity.

People started looking at reversibility in earnest when quantum computing came on the scene. A quantum computer HAS to be reversible in order to function. That made it a very important field of study.

We only recently realized that reversible circuits are also more energy efficient. So basically, we didn't do it before because we didn't know. There is no "catch."

Thermodynamics 101

[majid]

You get the most energy efficiency from a machine when it works in a thermodynamically reversible way, for instance the most efficient thermal motor possible is one that uses a Carnot cycle. Most real-world engines use different, less efficient cycles like the Otto or Stirling cycle because they yield higher speeds or torque.

Losing the ability to reverse computations means increasing entropy and thus lower efficiency. Interestingly, there is a whole class of functional programming methods that is intrinsically reversible (because evaluating expressions without side effects is reversible).

The best explanations of the issues involved is in Richard Feynman's "Lectures on Computation", that show how thermodynamics constrain what is ultimately possible with a computer.

Re:Thermodynamics 101

[iggymanz]

funny this topic has popped up again after I saw it featured in Scientific American over 10 years ago....the real problem is that no one wants to halve the number of useful gates on a chp in order to bulid all the extra circuitry required to reduce (of course, not eliminate, entropy still will increase though at lessened rate) the thermodynamic cost of "forgetting" data.

I attack instead the basic premise, that there is a shortage of energy, or that we must accept lower standard of life or lower capability in our machinery. What we DO need to do is get smarter about where we get our energy - instead of adding to net heat budget and pollution budget of earth getting really serious about solar energy (which might just mean making hydrocarbon fuel out of plant & suitable waste materials)

Read the Feynman book

[rarose]

http://www.amazon.com/exec/obidos/tg/detail/-/0738 202967/103-2222180-5559862?v=glance

He has a great deal of info about how reversable computers work and why they save energy.

HOW does it make it more efficent?

[autopr0n]

I mean, say you have a CMOS OR gate. If both of the inputs are high, then the NMOS transistors will close and the PMOS transistors will open. Energy is lost only when electrons 'leak through' when the gate changes (and of course, electrons that leak through but don't affect the computation, which I guess happens all the time). How would reversing the computation affect this? Maybe if you were using plain PMOS or something...

Re:HOW does it make it more efficent?

[randyest]

Enegy is lost always (leakage current) because the gate is not a perfect insulator. The smaller the gates, the more ther leakage. This is called static power.

Energy is also lost during switching, as the charge needed to switch is moved around. This is called dynamic power.

Reversible computing endeavors to reduce/eliminate dynamic power. It does nothing for static power. A long time ago, dynamic power was dominant and static power was negligble. Now, gates are so small, static power is approaching the same order of magnitude as dynamic.

So, even though they're only addressing about 1/2 of the problem, it would be great to have the magnitude of that big problem halved.

Re:What about cars?

[Jerf]

And if it is realistic, then how much more powerful are oil companies politically than electric power companies that the latter are going to just stand by and let this happen?

You mean, the power companies are going to force Intel to make their chips more wasteful, causing progress to halt and people to buy fewer Intel chips? Yeah, sure.

I mean, there's paranoia, and there's paranoia.

Come on, wake up. I won't claim that kind of thing never happens but by and large capatalism is too powerful; Intel isn't going to act against its own best interests for any mere money the power companies can throw at it, because it won't be worth it. Growth is worth more then mere money to Intel. (If you don't understand why, go learn about business; the explanation is too complicated for a Slashdot posting.)

The power company is made of people like you and me; far too busy to hover over various scientific journals and swoop around like super-villians repressing "dangerous" information.

Photographs of "a very simple reversible computer"

[Dlugar]

Universiteit Gent has some pictures of reversible logic gates, including a four-bit adder composed out of Feynman's "NOT, the CONTROLLED NOT, and the CONTROLLED CONTROLLED NOT" reversible logic gates, and some other circuits they've built.

They also have links to other sites about reversible logic and reversible computing, such as Ralph Merkle's Reversible Computing page (from Xerox).

Also note the bottom of the page: there's a vacancy in the research group, for all those just aching for a chance to work on reversible computing! (Looks like you'll have to speak Dutch, though.) ;-)

Dlugar

Stirling engine

[bs_02_06_02]

Isn't it just easier to use the excess heat to power a Stirling engine to recapture waste energy?
Maybe the Stirling idea is going too far.
How about a more efficient circuit? It's been awhile since college, but isn't excess heat a sign that the circuit is inefficient?
While it's not completely frivolous research, it's not the first avenue I would approach when looking at this problem. It seems more difficult and time-consuming to add in circuitry to re-use the energy to perform other actions inside of a CPU. It seems like you'd have a better chance at compounding the problem, rather than helping it.
However, make the circuit more efficient, you'll generate less heat. That would be my first goal. What kind of efficiency do they get with today's CPUs?

With this reversible thinking, I have an idea. I need a little help from the anti-SUV crowd... wouldn't all gasoline engines be better off with really big flywheels?

Asynchronous Logic will be here first.

[Cordath]

Asynchronous Logic (i.e. no clock) has many of the same benefits, as well as potentially increasing the speed of processors significantly.

A rather large portion of the heat genreated by a processor is just from the clock signal propagating to every bloody logic gate in the mess including the parts not in use. With asynchronous logic, if a part isn't in use, it gets no current. Of course, clock signals have been used for the last half century for a reason. Clock signals are used to time signals so that you don't have 3 digits of a number showing up before the rest, etc. With asynchronous logic you have to worry about path lengths down to the picometer so you don't need the clock to act like a traffic warden. The biggest holdup to asynchronous logic has been the immense design difficulty involved, but that is changing as new design tools are developed.

Anyways, the big reason why Asynchronous logic is going to arrive on the processor scene long before reversable logic is that it already has. Intel and other manufacturers are already incorporating asynchronous logic into their designs, and plan to increase the ammount used as time goes by. The different manufacturing techniques required are slowly being phased in. Reversible computing, on the other hand, has virtually no chance of showing up within the decade.

My point is that the article linked made no allowance for the increasing use of asynchronous logic. It's going to have a significant impact on heat dissipation in the neBuew years.

Re:Asynchronous Logic will be here first.

[Yobgod Ababua]

"Asynchronous blows for non-trivial computation."

Please cite your references or evidence to this statement if you wish to be taken seriously.

Several companies are currently working on complex and high-performance designs using asynchronous techniques. It's true that it is currently more difficult, predominantly because current design tools are all geared towards generating and testing "standard" clocked logic, but it is being done and it does not by any stretch "blow".

It will be quite some time before all of the components on a motherboard are asynchronous, but groups -have- designed processors, memory controllers, and other components in asynchronous.

For but the briefest of examples... check out this article or this article. No, it isn't the answer to everything... but it's much farther along than you seem to realize

Feynman Lectures on Computation

[John Sokol]

This book by Richard Feynman is based on a series of lectures given at CalTech in the mid 1980s.

In it he discusses Reversible Computation and the Thermodynamics of Computing and quantum computing.

As usual, Feynman was way ahead of his time.

I highly recomend this book.

The basic idea is heat is only generated when information is destroyed. So don't destroy information when performing computations.

How this relates to something actualy practical is hard to say, but it didn't strike me as something that would apply to silicon very easily.

John

Re:Huh?

[Aardpig]

Thermodynamics also says that you lose non-heat energy in reversable systems as well. If you throw a ball into the air, you lose some energy from wind resistance, from converting chemical energy in your arm into mechanical energy, etc.

Sure, but mechanical losses can always be recovered and put back into a system. Heat losses can't, which is the point of the second law of thermodynamics.

Size penalty

[toybuilder]

The problem with reversability is that for any given semiconductor process, it effectively doubles the number of gates that need to be built on the chip, and manufacturers are currently more interested in cramming more features into the chip; not to make them more efficient.

It might be theoretically possible to build smaller and faster chips by reducing the energy/thermal issues, but I suspect most companies are not willing to take that leap of faith.

I bet the first places we'll see reversible gates being used in a full-fledged MCU/CPU would be for a mobile/handheld processor running reversified version of an older (less gates) core using latest processes...

Reversable versus Probabilistic Computation

[John.P.Jones]

If you are interested in reversable circuits read what Feynman had to say about them in his lectures on computation.

While they may be helpful for certain things, especially quantum computers (but that is a whole different story) there is a snag. They are deterministic; great CS people like Rabin have taught us the value of probabilistic turing machines and today we use them as the basis of determining what is computationally efficient (BPP, see Michael Sipser's intro to computation and complexity). Every once in a while you have to take a non-reversable step to pick a random number (as well as through away garbage you don't want to store any more) and this negates the thermodynamic advantages of reversible computing.

No Free Lunch

Re:Theory

[TeknoHog]

Entropy S = k ln W
(k = Boltzmann's constant, W = number of states)
Information (in bits) I = log_2 W = ln W / ln 2
Hence S = kI/ln 2 or roughly S = kI.

Heat Q = ST = kTI.

Let's say we destroy 100 gigabits of information at a temperature of 300 K. Since k = 1.38E-23 J/K, this means a heat of about 4E-10 Joules. Which is not very much, and does not really contribute to the heat produced by CPUs.

In fact, I think this is the way to find a theoretical minimum for the heat produced from information processing. We can try and make more efficient processors to get closer, just like we can increase the efficiency of engines to get closer to the thermodynamic limit.