Reversible Logic

Introduction

If energy is continuously being dissipated in the form of heat, then a power supply will also be needed to replace that which is being lost.

Estimates concerning the relative importance of the heat dissipation due to irreversibility in microprocessors suggest that this energy has started to become important already - and will probably become one of the primary limiting factors to progress by around 2020.

The main idea of reversible logic is to allow the construction of reversible computers - by using components which preserve information content, and can thus potentially be run backwards.

Logically reversible components are defined as having logic tables that allow reconstruction of their inputs from their outputs. An example is the Fredkin gate - which has 3 inputs and 3 outputs.

By using exclusively logically reversible components, a physically reversible computer may be more closely realised - potentially resulting in reduced heat dissipation and power consumption.

Problems with reversiblity

Wiping out the noise resulting from computations at the end of the processing in some other way would result in exactly the same generation of heat as would arise if ordinary, irreversible logic elements were used during the computation.

This point does not seem to be popularly understood - e.g.:

Ed Fredkin has demonstrated that we don't even have to bother running the algorithm in reverse after obtaining a result.

 - The Singularity is Near Ray Kurzweil, page 130

Now, running the reversible machine backwards may be possible. It would probably take as long as the computation itself - halving the effective number of components in the computer that can operate sustainably. However, that is not much of a problem: you can just use twice as big a computer.

Another problem, is that you must make sure your computation was perfomed with no errors - otherwise chaos (and not the original starting condition) may result when the machine is run backwards.

A "no errors" requirement implies error correction in hardware. Error correction in hardware means identifying errors, and then overwriting them with correct values - inevitably an irreversible process that generates heat.

Unfortunately, if you have a large parallel machine which you need to reverse there is also a far more severe problem. In order to reverse such a machine, typically, some kind of "reverse" signal must be synchronously propagated to all the elements in the system - so they can reverse operation at a specified point in time. This is a serious problem in any large system - requiring a counter of substantial size to be associated with each computing element, or an external signal wire to be connected to each one - or something equivalent to these.
The "cost" associated with this synchronisation problem seems likely to be equal to the price of a counter on each element, capable of counting up to the machine's largest dimension (measured in element diameters).

In something like a cellular automaton, processing elements supporting that would typically be larger than the rest of the associated cell, and this would represent an intolerable cost.

In machines with less fine-grained parallelism this might be more practical. e.g. if such a counter was only 1/10th the size of a processing element, its addition would not reduce performance by very much.

If you have a serial machine, or a machine with very little parallelism, then this problem does not apply - but such machines are extremely limited in what tasks they can perform quickly.

Without running a reversible machine backwards, the main benefits of using reversible logic - namely dramatically reduced heat dissipation and power consumption - cannot be realised in a sustainable fashion.

So: is reversible logic a waste of time?

No. Reversible logic is of substantial significance.

Benefits of reversiblity

What do digital power management and digital heat management even mean? Digital power refers to ordered bit patterns, which can be used to do digital work. Digital heat refers to disordered bit patterns that are no good to anyone. Management of digital power involves moving it to where it is needed. Management of digital heat involves moving it to where it can be dumped.

Inside a digital environment there are broad range of components available for these tasks - and they are dynamically reconfigurable.

One benefit is that digital heat pipes are available that conduct in one direction highly efficiently without dissipating digital heat in other directions.

That allows you to pipe entropy away from the location where the computation is being performed while it is still in a manageable, digital form - before transforming it into real heat.

The generation of real heat may also be deferred - by storing digital heat in a reservoir.

Digital heat pipes may be applied where they are most needed, and their locations can change over time in a manner controlled by software.

There are similar advantages to doing digital power management. The result is like having a range of different voltage power rails available, and being able to control their locations. Digital capacitors of configurable sizes can be constructed, so that power is available when and where it is required.

Error correction should also be done primarily digitally. Computing hardware should be made reliable, but should not attempt to perform error correction - due to the additional complexity and heat issues this introduces. Digital error correction is well understood, and is immensely flexible and adaptable compared to doing error correction in hardware.

Of course, without running things backwards, such digital power management must eventually be backed up by a real power supply. Similarly a digital heat dissipation system must eventually exude the heat into the real world. However the additional control offered by handling these things digitally is worth something.

These benefits may well result in a modest reduction of heat generation - and in lower power requirements.

However probably their main significance is that they make it easier for most power supply and heat dissipation issues to be kept remote from the main computing device.

That should help make processing units more uniform - and should simplify the design constraints on individual components. Those effects should help facilitate their construction via molecular self-assembly.

The existence of extremely effective digital heat pipes should also help relieve some of the heat-dissipation issues of computing in three dimensions.

Links