COMPUTING SCIENCE
Reverse Engineering
backward and forward both run to need may they ,faster run to are computers If
Brian Hayes
Reversible Logic
A Turing machine is fine for reasoning about computers, but it's not
an ideal model for building them. Some more practical components of
reversible logic were introduced in the 1980s by Edward F. Fredkin
and Tommaso Toffoli, who were then working together at MIT. (Fredkin
is now at Carnegie Mellon University, Toffoli at Boston University.)
The components are logic gates, somewhat like AND and OR gates but
designed for reversibility.
In any reversible gate the number of inputs must equal the number of
outputs. Moreover, each possible set of inputs must yield a distinct
set of outputs. If this were not the case—that is, if two or
more input patterns had the same output—then the reverse
action of the gate would be ambiguous.
The devices now known as the Fredkin gate and the Toffoli gate
(see illustration on page 109) both have three inputs
and three outputs; and, as required for reversibility, each input
pattern maps to a unique output. In the Fredkin gate, one signal
controls whether the other two data lines pass straight through the
gate or else have their positions swapped. In the Toffoli gate, two
of the signals control the third; if the first two bits are both 1,
then the third bit is inverted.
Like the NOT gate, both the Fredkin and the Toffoli gates are their
own inverses: No matter what the values of the three input signals,
running them through two successive copies of the same gate will
return the signals to their original values. Both gates are also
computationally universal, meaning that a computer assembled from
multiple Fredkin or Toffoli gates (and no other components) could
simulate a Turing machine or any other device of equivalent
computational power. Thus the gates might be considered candidates
for a real reversible computer.
Of course logic gates are still just abstract devices; they have to
be given some physical implementation with transistors or other
kinds of hardware. Starting in the early 1990s, several groups have
been designing and building prototypes of reversible (or nearly
reversible) digital circuits. For example, at MIT a group including
Michael Frank and Thomas F. Knight, Jr., fabricated a series of
small but complete processor chips based on a reversible technology;
Frank continues this work at Florida State University. At the
University of Gent in Belgium, Alexis De Vos and his colleagues have
built several reversible adders and other circuits.
It's important to note that building a computer according to a
reversible logic diagram does not guarantee low-power operation.
Reversibility removes the thermodynamic floor at kT ln 2,
but the circuit must still be designed to attain that level of
energy savings. The current state of the art is far above the
theoretical floor; even the most efficient chips, reversible or not,
dissipate somewhere between 10,000 and 10 million times kT
ln 2 for each logical operation. Thus it will be some years before
reversible technology can be put to the ultimate test of challenging
the three-zeptojoule barrier. In the meantime, however, it turns out
that some concepts derived from reversible logic are already useful
in low-power circuits. One of these is charge recovery, which
attempts to recycle packets of electric charge rather than let them
drain to ground. Another is adiabatic switching, which avoids
wasteful current surges by closing switches only after voltages have
had a chance to equalize.
» Post Comment