\documentclass{llncs}
%\input psfig
\input urls.sty

\begin{document}

% POSSIBLE TITLES:
% Scalable architectures and the limits of computing.
% Scalable architectures and reversible computing.
% Reversible computing for optimal scalable architectures.
% Reversible computing in optimal scalable architectures.
% Reversible computing enables optimal scalable architectures.
% Reversibility in optimal scalable computer architectures.

\title{Reversibility in optimally scalable computer architectures
\thanks{This work was supported by DARPA contract DABT63-95-C-0130.}}
\author{Michael Frank, Tom Knight, Norm Margolus}
\institute{MIT Artificial Intelligence Laboratory, Cambridge, MA 02139, USA}
\maketitle 

\begin{abstract}
  An important goal for computer science is to find practical, scalable
  models of computation that are as efficient as is permitted by the laws
  of physics.  Given a constant upper bound on entropy density, physics
  implies fundamental constraints on the efficiency of any computation that
  produces entropy.  As a result, it appears that the most efficient
  possible computer architectures must use reversible primitive operations
  which produce arbitrarily little entropy.  In this paper we show that a
  \mbox{3-D} mesh of reversible processing elements, constructible using
  existing technology, scales better than any physically possible computer
  based on irreversible primitives.
\end{abstract}

\section{Introduction}

In the quest for ever-more-powerful computers, one
compelling ultimate goal is to design a physically
implementable, scalable computer architecture that is
capable of performing any computation with the maximum
asymptotic space-time efficiency permitted by the laws
of physics.

The recent studies of quantum computing ({\em e.g.} \cite{Shor94}, brief
review in \cite{mpf-qc}) suggest that if it is possible to implement
machines that can maintain and manipulate indefinitely large coherent
states, then it is this class of machine that will achieve the
asymptotically highest possible efficiency on certain classes of problems,
such as factoring.  However, since the practicality and scalability of
large-scale quantum-coherent computers has not yet been established, in
this paper we will primarily consider the maximum asymptotic power of
physical systems that are {\em not} able to utilize large-scale coherent
superpositions of computational states; in other words, ``classical''
systems.  However we expect that many of our conclusions about the optimal
classical systems will carry over to the optimal quantum systems as well.

Due to the finiteness of the speed of light, the most
efficient architectures appear to be meshes of
processors, communicating locally on a regular grid
\cite{Hillis82,Vit88,BilPrep-93,Vit95}.  For maximum
physically-scalable connectivity, the mesh should be
three-dimensional.

But with conventional technology, 3-D meshes can lead to a problem.  If
each computational operation produces some minimum amount of entropy
(indestructible discarded information), and if the density with which
information or entropy can exist per unit volume is limited (by the
technology and/or by fundamental physics), then, as we will show, it
follows that the number of operations per second that can be performed in a
computer {\em per unit area of its enclosing surface\/} is also limited.
Thus in conventional technology, expanding a mesh in the third dimension
is, after a point, effectively useless for making computations faster.

Moreover, conventional abstract models of computation preclude any
resolution of this problem, because the primitive computational operations
specified by those models are {\em irreversible\/}---a given computational
state resulting from an operation could usually have been reached from more
than one possible immediate predecessor.  This is important because the
laws of physics {\em are themselves reversible\/} at a microscopic level;
any microstate can only be reached by a unique path.  Therefore, whenever a
physical computer attempts to perform one of the logically irreversible
operations specified by its abstract model, the discarded information about
the prior state is not physically destroyed, but is merely transfered
somewhere else, normally to contribute to the thermal entropy of the
computer and its surroundings. This relationship between irreversible
computational operations and physical entropy was apparently first pointed
out by Landauer '61 {\cite{land1}}.  A good, though somewhat dated review
of the resulting research is provided by Bennett '82 {\cite{ben3}}.

Thus, direct execution of conventional irreversible models requires a
certain minimum amount of physical entropy be generated with each
operation, in proportion to (and no less than) the number of bits of
computational state that are discarded by the operation.  Moreover, we
calculate that present-day standard irreversible circuit technology
inefficiently generates at least $10^6$ bits of physical entropy per bit of
computational state that is discarded! (See Frank and Knight '97
\cite{Frank-Knight-97}, \S 2.5 for one such calculation.)

However, irreversible operations and the accompanying production of entropy
are actually not required for any computation, as was shown by Lecerf '63
{\cite{Lecerf63}} and independently by Bennett '73 {\cite{ben1}}.
Unfortunately, it seems that computations that produce no entropy may, at
least in some cases, require either more computational space or more time
(by an unboundedly large factor) than their counterparts in the
traditional, nonphysical irreversible models in which unwanted information
is permitted to simply disappear with no consequences (see Frank and Ammer
'97 {\cite{FrankAmmer97}}).

But it is important to remember that in real, reversible physics,
information is {\em not} permitted to simply disappear, and that physics
itself is the reversible machine upon which any real-world irreversible
algorithms must ultimately be run.  At worst, a computer that is internally
reversible can still dispose of any unwanted information in a way analogous
to the use of fans or coolant flows in ordinary physical computers, namely
by simply moving it out of the way, away from where it was generated, and
out to a more spacious external environment.  So ultimately, reversible
models need be no less space or time efficient than any real physical
implementation of any irreversible model, when one keeps in mind the
physical resources consumed in either kind of machine by the storage and
transport of entropy.

For many problems, the most time efficient algorithms may turn out to be
essentially 2-D algorithms that constantly produce entropy which is removed
along the third dimension; this is what happens in computers today.  But
for other problems, reversible algorithms that avoid producing entropy in
the first place should be able to effectively use all three dimensions, in
contrast to any model based on irreversible primitives.  We already know of
some important classes of problems for which efficient 3-D algorithms can
indeed be completely reversible and, in principle, produce no entropy.  In
particular, there is volumetric simulation of 3-D reversible physical
systems; see the examples in \cite{MTV86,TofMarg91}.  As we will see, a
parallel 3-D reversible model of computation can solve such problems more
efficiently than any irreversible machine (parallel or not).

This result is not just theoretical.  In our group we have developed an
electronic technology called Split-Level Charge Recovery Logic (SCRL)
{\cite{yk2,you}} that can implement arbitrary reversible operations, and in
which the physical entropy generated per operation, though comparable to
normal electronics when running at maximum speed, {\em scales down as the
  cycle time increases}.  The only lower limit, due to leakage currents
through nominally ``off'' transistors, can easily be made insignificant.
(Likharev {\cite{likh}} has also proposed a reversible electronic
technology based on superconducting Josephson junctions that is even more
efficient.)

Given this sort of asymptotically reversible technology, the third
dimension is no longer useless.  Making the third dimension thicker, adding
more processors per unit area, still requires the speed of each operation
to decrease, but now (as we will show) only in proportion to the {\em
  square root} of the thickness.  Thus, the total number of operations per
second per unit area can increase without bound.  This technology will be
able to execute some problems, such as large 3-D physical simulations,
unboundedly faster than any technology based on any irreversible model of
computation.

Moreover, we propose that our abstract model of computation, the R3M, which
we will specify in more detail later, is ultimately the most efficient
physically implementable classical architecture.  On problems where the
reversibility of the model does not help, then at worst, the R3M should be
able to directly simulate any physical implementation of any competing
model with no asymptotic inefficiencies.

In view of the apparent asymptotic optimality of the
R3M model among scalable architectures, we suggest that
designers of parallel algorithms should try targeting
the R3M model to see if they might gain real-world
efficiency from it.  Also, we suggest that computer
engineers should try building scalable implementations
of the R3M architecture using appropriate electronic
device technologies that are already beginning to
become available.

As for quantum-coherent computers, if large-scale quantum coherence can
indeed be stably maintained and manipulated at meaningful scales, it is
likely that the most efficient quantum-coherent computers will also turn
out to be 3-D meshes of processing elements.  Work done now on algorithms
for classical reversible 3-D meshes may give us experience that will help
later in designing good quantum-coherent reversible 3-D algorithms, if and
when a workable technology for their implementation becomes feasible.

\section{Reversibility, Information, and Entropy}

We start by defining reversibility and informally
describing some concepts of information and entropy.

The definition of a reversible operation is very
simple.  An operation is reversible if it can, in
principle, be undone.  This means that the
transformation performed on the accessible degrees of
freedom has a functional inverse.  That is, the
operation is reversible if, for each state that may
result from the operation, there is a unique immediate
predecessor state that could have yielded that result
under the given operation.  Put another way,
reversibility is simply determinism looking backwards
in time.

A computation is reversible insofar as it is composed
entirely of reversible primitive operations; a model of
computation, or of a system in general, is reversible
insofar as it permits only reversible operations to be
performed within the model.  Physicists like to say of
reversible systems that their ``state space is
incompressible.''  Reversibility and determinism are
both fundamental properties of microscopic physics.
Despite the popular view of quantum mechanics as having
overthrown determinism, quantum mechanics can be viewed
as perfectly deterministic at the level of the unitary
wavefunction evolution.  The indeterminism that we
perceive in ``wavefunction collapse'' can be
interpreted as only a subjective, emergent phenomenon.

As for information, we can adopt an informal concept of
information, relating to information theory's
definition based on statistical occurrences of symbols.
In information theory, the information in a message can
be estimated by counting the number of symbols in the
message, while giving more weight to the symbols which
occur less frequently.  A message may contain many
symbols, but little information if most of the symbols
are the same.

In our informal concept, the information in a state consists of those bits
of state that are actually being used to represent something.  If bits of
state that are not being used to represent anything are always left
containing zeroes by convention, and bits that do represent something are
approximately equally likely to be zeros or ones, then a crude measure of
the number of bits of information in a state is just double the number of 1
bits that are present.

Even in a deterministic system, the amount of information that is present
can increase over time, because new, redundant information can simply be
deterministically derived from old information.  Similarly, the amount of
correlated, redundant information that is present can decrease in
controlled reversible systems, because correlated pieces of information can
be brought together in a controlled way, and the redundant information in
them can be un-derived; the reversible operation that does this underiving
is just the inverse of the deterministic operation that would have produced
the derived copy in the first place.

As an example, suppose a state is representing a pair
of integers $(A, B)$.  Such a state can be transformed
by a deterministic operation to a state representing
the triple $(A, B, A\cdot B)$, which contains ``more
information,'' but only of a correlated, redundant
type.  Furthermore, a redundant state of this form can
be transformed by a reversible operation back into the
state $(A, B)$ which contains ``less information'' in
the sense of less redundancy.  But an arbitrary triple
$(A, B, C)$, in which there is no redundancy, cannot be
made into $(A, B)$ reversibly, just as $(A, B)$ cannot
be turned into $(A, B, C)$ deterministically, with $C$
being arbitrary.

Now, suppose that a particular computation, or an arbitrary physical
system, is entirely deterministic and reversible, but that it happens to
produce a piece of redundant, derived information in such a way that the
inverse operation that would remove the redundancy is for some reason not
effectively available.  For example, perhaps the redundant information is
moving away from the information that it was derived from, and its motion
cannot be turned around.  Or, perhaps the information has moved to a part
of the system that is uncontrolled, or has otherwise become mixed up with
some other, unrelated information by some operation whose inverse, though
it theoretically exists, isn't physically available in the forwards time
direction.

If, through circumstances such as these, some information produced by a
system is never un-derived, then we call this information ``entropy.''
Disassociated from the information elsewhere with which it is correlated,
it can appear random and meaningless.  Since entropy is, by definition,
never un-derived, its amount always increases over time in a reversible
system.

This definition of entropy is appropriate both for physical systems and in
reversible computation systems.  Physical and computational entropy are
really the same thing; they are interconvertible.  Computational entropy
can be turned into physical entropy by allowing energy involved in
representing a bit to dissipate.  And physical entropy can be turned back
into computational entropy: a thermal system can be cooled by allowing it
to interact with and randomize a sufficiently sensitive and volatile
digital memory that is initially in a low-energy, low-entropy state ({\em
  e.g.}, all zeros).

Entropy in either its physical or digital form is annoying because, once it
is created, it permanently increases the complexity of a state and takes up
space (physical and computational).  If the total space available for
storing information is limited, or if we cannot move the excess entropy
away quickly enough, from some small region of the system where it is being
generated outward to another part of the system where there is more room to
store it, then eventually the accumulating entropy will overflow its
acceptable limits, and will creep into and alter the state of the part of
the system that we care about.  (For example, by melting its structure.)

We will see that this becomes a fundamental factor limiting the performance
of computational systems that produce entropy.  But the creation of entropy
in the course of a computation is not actually necessary.  There are
universal models of computation whose primitive operations are completely
reversible at the level of computational state (see, for example, Bennett
'73 \cite{ben1}, Fredkin and Toffoli '82 \cite{fred2}, and Vieri '96
\cite{Vieri96}).  And moreover, there are workable technologies for
implementing these models that can arbitrarily closely approach perfect
physical reversibility as well {\cite{yk2,you}}.  That is, the physical
entropy produced per operation can be made arbitrarily close to zero.

In addition to physical entropy, there is also computational entropy to
worry about.  Even if a computer uses only reversible circuits, and it
executes all instructions reversibly, if its programming model does not
actually make the inverse instructions available to the programmer, then
there may be no way to execute a program without continuously producing
entropy at the computational level.  For example, suppose there is an
instruction that computes the logical AND of two registers reversibly, by
placing the result in a previously-empty location.  But if there is no way
to undo this operation, then the results of past AND operations will tend
to accumulate in memory over time.  Since they are never uncomputed, they
are a form of entropy.

But with careful design of the set of computational primitives provided to
the programmer, it is possible to perform any desired high-level
computation in a way that produces no computational entropy, and instead
reabsorbs all intermediate results back into the computation.  However,
avoiding all entropy production may hurt other measures of performance
{\cite{FrankAmmer97}}, so this strategy is not necessarily always useful.

In the following sections we will see exactly how
entropy (whether in physical or computational form)
limits the efficiency of computation, and how avoiding
the production of entropy can allow certain
computations to be performed arbitrarily faster than
they could be performed otherwise.

\section{How entropy limits efficiency}

In this section we analyze how the production of entropy in a computer
limits the asymptotic efficiency of computation.

We wish to restrict our attention to classes of physical systems in which
there is some constant upper bound to the entropy density that may exist
within the computer, a bound that is not permitted to scale up as problem
sizes increase.  This seems a reasonable restriction, since achieving
unboundedly high entropy densities in a controlled system will probably
remain technologically infeasible for the foreseeable future.  For example,
in a photon gas, the entropy per unit volume $S/V$ scales proportionally to
the cube of the temperature (\cite{JQ92}, p.571), so achieving unboundedly
high entropy densities in a stream of photons would require unboundedly
high temperatures.

Furthermore, there seems to be a fundamental physical upper bound on the
entropy of any system of bounded size \cite{Bek84,JQ92} which is apparently
only achieved in the case of black holes, which have entropy proportional
to their surface area.  Thus, the upper bound on entropy density actually
decreases as system sizes increase, so allowing entropy density to be a
constant independent of system size is actually too generous.

However, these ultimate limits on entropy density are very far away, and
for the foreseeable future, entropy densities will be limited by more
pragmatic concerns such as the heat capacity of available materials, and
the temperatures that can be tolerated in working electrical, mechanical,
and optical components.  There will certainly be technological limits to
entropy density in controlled systems for the foreseeable future.

In any case, let $\rho$ denote the highest spatial density of storage of
information or entropy, in any form, that is achievable under a technology
in question, and assume $\rho$ is independent of the size of the system.
Example units for $\rho$: bits per cubic centimeter.

Now, consider a computation that produces entropy as it proceeds, and
consider the convex hull (least-area convex enclosure) bounding the region
of space within which that computation is performed.  Given the limit
$\rho$ on the density of information (including entropy), eventually the
capacity for information storage within the convex hull will be exceeded,
and in order for the computation to proceed, the entropy must pass outwards
through the hull.  Asymptotically, the rate at which entropy is produced
inside the region cannot exceed the rate at which entropy leaves through
the convex hull.

What is the fastest rate at which entropy may leave the hull?  We have
already assumed a maximum entropy density of $\rho$.  We can also assume
some maximum entropy removal velocity $v$, which is, at most, equal to the
speed of light $c$.  If entropy crossing the hull is packed at the maximum
density and is moving at the maximum velocity, we get an upper bound on the
information flux $F$ per unit area of:
\begin{equation}
F = \rho v.
\end{equation}

As an example: if entropy is encoded (either thermally or digitally) in
some material at the atomic scale at a density around 1 bit per cubic
Angstrom, and if the material is passing through the surface at a modest 1
centimeter per second, the flux is $10^{24}$ bits per square centimeter per
second.  This roughly corresponds to the maximum entropy flux that might be
achieved in a stream of coolant moving at that velocity.

This may sound like a high value, but it is actually only about a factor of
30 times higher than what routinely occurs with more passive
entropy-removal methods.  A chip dumping 100 W of heat from a 1 cm$^2$
surface (not uncommon today) to a room-temperature thermal reservoir is
emitting internal thermal entropy at something like $3.5\times 10^{22}$
bits per second per square centimeter.  (See \cite{Frank-Knight-97}, \S 7.1
for the calculation.)

The maximum entropy flux $F$, whatever its exact value, asymptotically
limits the rate at which entropy can be produced inside a given region of
space, per unit of convex hull surface area.

If each computational operation, on average, produces some nonzero minimal
amount of entropy $I$, then the limit $F$ on the rate of entropy production
per unit area leads directly to a limit $r$ on the total rate of
computation within a volume, per unit area of the volume's surface.
\begin{equation}
r = F/I.\label{eq:rate}
\end{equation}

Recalling our second entropy flux example, of $F\approx 3\times 10^{22}$
bits/sec/cm$^2$, corresponding to 100 W/cm$^2$ at room temperature, if $I =
10^8$ bits/operation (a typical entropy we calculated for today's logic
gate operations), then we have $r = 3\times 10^{14}$ operations per second
per square centimeter.  This may sound like too high a limit to worry
about, but with, say, a million logic gates per square centimeter in a flat
layer of circuitry, and with each gate operating 100 million times per
second (both quite reasonable numbers today), this means that, with that
technology, the maximum amount of circuitry operable at that speed within
any region of space is equal to only {\em a single layer} of circuitry over
the region's convex hull!  Note that this limit holds independently of the
particular spatial arrangement of the circuitry and cooling mechanisms
inside the region.

This sort of scaling of raw computational capability in proportion to
convex surface area severely limits the asymptotic efficiency of
entropy-producing computers on certain classes of problems.  For example,
consider the problem of simulating a 3-dimensional array of elements, such
as voxels (volume pixels) in a volumetric physical simulation, such as of
weather, air flow over a wing, or a nuclear blast.  Imagine a cube-shaped
simulated space, $N$ voxels across in each dimension, in which each voxel
must be updated on each step of simulation.  Performing all the voxel
updates in the entire space for $\Theta(N)$ simulation steps thus requires
$\Omega(N^4)$ operations.\footnote{This notation is widespread in computer
  science.  Informally speaking, $\Theta$ might be read as roughly ``a
  quantity proportional to'' and $\Omega$ as ``a quantity at least
  proportional to.''  Later we will also use $O$ meaning roughly ``a
  quantity at most proportional to.''  For the precise formal definition of
  the $\Omega,\Theta,O$ order-of-growth notation, see \cite{CLR}, chapter
  2.}

Suppose we want the simulation of this space to be computed within a region
of real space whose longest diameter is bounded by $O(N)$.  The convex hull
of such a region will have a surface area bounded by $O(N^2)$.  Thus the
highest sustainable rate of entropy-producing computation within the region
is $O(N^2)$.  Performing $\Omega(N^4)$ operations at this rate will require
$\Omega(N^2)$ time, for an average of $\Omega(N)$ time per simulation step.

That is, continuous simulation of an $N\times N\times N$ voxel system
within a real space of width $O(N)$ requires an average of $\Omega(N)$ time
{\em per step} of simulation, in {\em any} situation in which there is a
lower bound independent of $N$ on the entropy produced by each voxel update
operation, and in which there is an upper bound $F$ independent of $N$ on
the maximum entropy flux attainable per unit area.  Note that {\em any}
irreversible technology will indeed have a lower bound on entropy
production per voxel update operation, namely, at least as many bits as are
irreversibly discarded during the operation.

Note however that if we could perform each voxel update in some constant
time and space with absolutely {\em zero} entropy production, then these
simulations could be performed in $O(1)$ time per step, by simply using
$\Theta(N^3)$ processing elements to perform the updates in parallel.
However, it may be unrealistic to suppose that any technology could ever
achieve this.  But we will see that in a realistic reversible technology,
in which the entropy per operation, though nonzero, can be made as low as
desired, some of these 3-D simulations can actually be run in only
$O(\sqrt{N})$ time per step---that is, $\Omega(\sqrt{N})$ times faster than
if conventional, irreversible technology is used.

First, however, let us examine a slightly different problem.  Above we
assumed that we wished the diameter of our computer to be restricted to be
proportional to the logical diameter of the problem.  Without any such
restriction, and without specifying a need for communication between parts
of the computation, we could spread out $\Theta(N^3)$ processing elements
as far apart as needed to assure that entropy removal is not the limiting
factor, and thereby perform each simulation step in $O(1)$ time.  Indeed,
this is practical if the ``space'' being ``simulated'' is actually only a
large search through a space of independent items, such as a search for
primes or cryptographic keys.  Known algorithms for these applications are
not communication-limited, and thus performance on them need never be
heat-limited, and reversibility cannot help with speed on such
computations.

However, if we add the requirement that each voxel update depend on the
values of the neighboring voxels, as is typical in real physical simulation
problems, we find that although spreading out the computation a little bit
can allow the asymptotic time per step to be smaller, reversible
technologies can asymptotically still beat any irreversible technology.

Consider the irreversible case.  Even with local
interactions only, after simulating the entire space
for $\Theta(N)$ steps, each voxel may potentially
affect $\Theta(N^3)$ others over $\Theta(N)$ steps, for
$\Theta(N^4)$ total voxel-update operations that may
depend on the original voxel's value.  Similarly, each
new voxel value that is computed depends on
$\Theta(N^4)$ prior computations over the past
$\Theta(N)$ simulation steps.

But in real time $t$, the localized datum which represents a newly computed
voxel value can only possibly affect or be affected by a region of real
space of radius $tc$ (where $c$ is the speed of light), which is bounded by
a convex surface area of $O(t^2)$.  Only a rate $r=O(t^2)$ of
entropy-producing operations can be sustained within such a region, for a
total number $O(t^3)$ of operations that can possibly affect the datum.
Therefore, performing the $O(N^4)$ operations that are required to compute
a voxel value resulting from $O(N)$ simulation steps must require at least
real time $t=\Omega(N^{4/3})$.

So, sustained simulation of an $N\times N\times N$ 3-D
voxel-based system with local interactions requires at
least $t=\Omega(N^{1/3})$ average real time per
simulation step, in any situation where there is a
lower bound on the entropy generated per operation, and
an upper bound on entropy flux.  Note that this bound,
in contrast to the previous $\Omega(N)$ bound, holds
true independently of the shape and size of the region
within which the simulation occurs.  It is also
independent of the arrangement of times and places for
the individual computations within this region.

The bound can actually be achieved, using a 3-D array
of ordinary irreversible processing elements spaced a
distance $\Theta(N^{1/3})$ apart from each other, and
performing updates every $\Theta(N^{1/3})$ time units.
A single column of processing elements contains $N$
elements, each producing entropy at a rate
$\Theta(N^{-1/3})$, for a total rate of entropy
production within the column of $\Theta(N^{2/3})$. The
surface area available for entropy removal at each end
of the column has area $\Theta(N^{2/3})$.  Therefore,
entropy removal does not prevent running the processors
at the given rate of $\Theta(N^{1/3})$ time per step.

%\begin{figure}
%\centerline{\psfig{width=\textwidth,file=irrev.epsi}}
%\caption{How to achieve $O(N^{1/3})$ time per step for an $N\times N\times
%  N$ physical simulation using irreversible processors.}
%\vskip 0.15in\hrule
%\label{fig:irrev}
%\end{figure}

We will see that our reversible technology can beat
this, and achieve $\Theta(N^{1/4})$ time per step.

\section{How reversibility can help}

Clearly, if we could perform a computation perfectly
{\em isentropically} (without any production of
entropy), this would completely change the above
analysis, since there would be no issue of entropy
removal.  The rate of computation that could be
sustained within a given region would then be limited
only by the packing density and maximum rate of the
individual processing elements.

However, it may be physically impossible to achieve
true zero-entropy computation while maintaining a
constant non-zero rate of processing.  Bennett
\cite{ben3} has described a hypothetical clockwork
computer that can operate solely via Brownian motion,
and produces no entropy.  However, it does not run at
any non-zero constant speed; when running purely
isentropically, it makes a random walk through the
computation, which takes $\Omega(n^2)$ expected time to
reach the $n$th computational step.

Thus, the pure Brownian approach does not lead to
time-efficient computation.  Another approach is what
we might call the ``ballistic'' approach.  If the
physical entities that carry information around inside
a computer move totally frictionlessly, and interact
without any loss of energy, then no entropy need be
produced.  For example, ballistic motion is the basis
for the idealized ``billiard ball'' model of reversible
computation proposed by Fredkin and Toffoli
\cite{fred2}.

However, we do not know of any way to make a system
that operates purely ballistically, at some constant
nonzero speed.  Indeed, this may not be physically
possible.

Nevertheless, using reversible technologies, we do know how to make the
entropy production per operation arbitrarily small, by decreasing the speed
at which operations are performed, in proportion to the decrease in entropy
per operation.  In other words, if an operation is performed over a time
$t$, the entropy $I$ produced by the operation scales as
\begin{equation}
I = \Theta(1/t).\label{eq:ivst}
\end{equation}
This scaling law comes out of the analysis of the energy dissipation
mechanisms of all the different asymptotically reversible logic device
technologies that we know about.  A variety of such technologies, and
references to further information on them are listed in Frank \& Knight '97
\cite{Frank-Knight-97}, \S 7.3.

Note this scaling is not the same as just decreasing the {\em rate} of
entropy production by performing operations more slowly, with the entropy
per operation staying the same.

Bennett's Brownian computer can be operated with speed
proportional to entropy per operation, if a small
driving force is used to keep the machine running
forwards steadily.  Fredkin and Toffoli '78
\cite{fred1} proposed an early reversible electronics
that had this scaling, based on inductors and
capacitors.  Merkle has proposed nanomechanical logic
mechanisms \cite{Merkle93b} that exhibit this scaling
as well.

Let us now analyze how this inverse dependence of $I$
on $t$ affects the asymptotic efficiency that can be
achieved on the problems discussed in the previous
section.

For a given technology, let $e$ denote the constant
scaling factor implied in eq.~(\ref{eq:ivst}), which we may call the
``entropy coefficient.''  It denotes the entropy
produced per primitive operation, per inverse of the
time over which the operation is performed.  Its units
are bits of entropy per Hertz.  The entropy production of a reversible
operation can then be expressed as
\begin{equation}
I = e/t.\label{eq:ivst2}
\end{equation}

As an example, we estimate that $e$ for SCRL reversible
logic gates built with current VLSI technology and
operating at around room temperature is around 0.66
bits per Hertz.

Next, let $n$ designate the average number of primitive
operations that are being performed simultaneously at
any given time, per unit of convex hull surface area.
Units for $n$ might be operations per square
centimeter.  For example, if all circuits that perform
primitive operations are active simultaneously, then
$n$ is just the number of such circuits per unit
surface area.  Remember, this is the area of the entire
computer's convex hull we are talking about, not the
total area of the individual chips. So, $n$ becomes
larger if we just pile up more layers of circuit boards
inside the surface, for example.

Now, if each individual operation is performed over a
time $t$, the rate of computation per unit area is
\begin{equation}
r = n/t.\label{eq:rvst}
\end{equation}

Now, we just substitute equations (\ref{eq:ivst2}) and
(\ref{eq:rvst}) back into the flux-limited rate
equation, eq.~(\ref{eq:rate}) from the previous
section, and get:
\begin{equation}
n/t = \frac{F}{e/t},
\end{equation}
which we can transform algebraically into
\begin{equation}
\frac{1}{t} = \sqrt{\frac{F}{ne}}\label{eq:invt}
\end{equation}
and so
\begin{equation}
r = \sqrt{\frac{nF}{e}}.
\end{equation}

This final equation tells us that with reversible
technology, the maximum entropy flux $F$ no longer
implies a fixed bound on the rate of computation $r$
per unit of surface area, as was the case in
eq.~(\ref{eq:rate}) when $I$ was constant.  Instead,
the total rate $r$ of computation per unit surface area
can be increased arbitrarily, by increasing $n$, the
number of operations performed simultaneously per unit
area.  This can be done by just stacking more layers of
circuitry over a surface.  Also each layer is run more
slowly by a factor $1/\sqrt{n}$.  The total rate of
computation per unit area then increases proportionately
to the square root of the number of simultaneous
operations per unit area;
\begin{equation}
r = \Theta(\sqrt{n}).
\end{equation}

Note that $r$ can also be increased separately from $n$
by just reducing the entropy coefficient $e$.
Different reversible technologies differ widely in
their $e$ values, but we currently know of no
technology-independent, fundamental physical lower
bounds on the value of $e$.

Now, with this equation in mind, to simulate a $N\times
N\times N$ array of voxels in a machine of width
$O(N)$, we can just let $n$ grow as $\Theta(N)$, by
stacking up $n$ layers of circuitry per unit area, and
then $t$, the time per step of simulation, can scale
(see eq.~(\ref{eq:invt})) as $\Theta(\sqrt{N})$.

%\begin{figure}
%\centerline{\psfig{width=\textwidth,file=rev2.epsi}}
%\caption{How to achieve $O(N^{1/2})$ time per step and $O(N)$ machine
%  diameter for an $N\times N\times N$ physical simulation using
%  asymptotically reversible processors.} \vskip 0.15in\hrule
%\label{fig:rev2}
%\end{figure}

An important caveat is that this approach will generally only work if the
voxel update function is inherently an invertible function to start with.
Otherwise, updating the voxel discards information about its past state.
Even if the information is kept in computational form, instead of being
dissipated to heat, it is still effectively entropy, and will still limit
the asymptotic rate of computation just as if irreversible hardware were
used.  Fortunately, the types of systems we are most interested in
simulating, namely real physical systems, are always reversible at some
level.  Systems that behave chaotically, such as in turbulent flows, may be
difficult to simulate reversibly at a coarse-grained level.  However, we
can use massive parallelism to simulate at a more fine-grained level.
Systems of interest usually involve bounded energy densities and
temperatures, and thus bounded information per unit volume.  In these
systems there is no danger of the entropy per volume element needing to
increase beyond bound, and so a purely reversible simulation should be able
to keep up with the information flow.

In any case, since some 3-D simulations are indeed
reversible, the above analysis substantiates our
earlier claim that reversible machines can perform some
classes of computations asymptotically faster than
irreversible machines, because, as we proved in the
previous section, irreversible machines require time
$N$ per step of simulation to perform this class of
computations on a width $N$ machine, whereas the reversible
machine only requires time $\sqrt{N}$.

In the other case we considered, where the size of the machine is not
specified to be particularly limited but there is interaction between
neighboring parts of the simulated space, we can use a 3-D array of
$N\times N\times N$ processing elements in which $t$, the time per step,
and $\ell$, the distance between neighboring processing elements, both
scale as $\Theta(N^{1/4})$.  The entropy $I$ per processor per operation is
thus $\Theta(N^{-1/4})$, the entropy production rate per processor per unit
time is $\Theta(N^{-1/2})$, the rate for an entire column of $N$ processors
is $\Theta(N^{1/2})$, and with an $\Theta(N^{1/2})$ surface area at the end
of each column, the entropy generation rate per unit area is $O(1)$.  Thus
the simulation can be sustained with this $t=\Theta(N^{1/4})$ time per
simulation step, faster than the maximum asymptotic rate of
$\Theta(N^{1/3})$ that we established in the previous section for
irreversible technologies, in which the minimum entropy generation per
operation is independent of $t$.

%\begin{figure}
%\centerline{\psfig{width=\textwidth,file=rev.epsi}}
%\caption{How to achieve $O(N^{1/4})$ time per step for an $N\times N\times
%  N$ physical simulation using asymptotically reversible processors.}
%\vskip 0.15in\hrule
%\label{fig:rev}
%\end{figure}

Unfortunately for our argument, the difference in
speeds between reversible and irreversible approaches
in this situation is only a factor of
$\Theta(N^{1/12})$.  Thus, demonstrating a factor of
ten increase in the speed of reversible technology
relative to irreversible technology in this scenario
requires considering a voxel space $10^{12}$ (a
trillion) times wider.  Even worse, with current slow
switching technology, but assuming dissipationless
light-speed communication, the optimal configuration of
large reversible or irreversible heat-limited machines
has the processors spread apart fairly widely.  For
example, for a very simple 3-D voxel update rule, and
given the parameters of a typical current CMOS circuit
technology and 10 W/cm$^2$ of surface cooling, we
estimated the minimum size of a reversible computer
that would be faster than any possible irreversible
computer (no matter what size) implemented using
standard gates in the same technology.  It would
require an amount of silicon with about the mass of the
entire planet Saturn, spread out with 16 meters of
lateral spacing between 100-micron wide processing
elements, over a disc having the diameter of the entire
solar system, with a total power output 60,000 times
that of the Sun!  (Running at an 18 MHz clock speed, it
would perform an astounding $1.8\times 10^{43}$ voxel
update operations per second!)

The lesson to learn from that amusing calculation is that if we are
desperate enough for speed that we are willing to spread out our current
energy-inefficient computers over such a wide area that heat dissipation is
no more of a limiting factor than is communications latency, then in that
case, current reversible technologies such as SCRL do not offer any
additional speed benefit until an extremely large scale is reached.

However, in real applications, we will generally want our computers to be
as compact as possible, for reasons beyond just speed, such as portability
and ease of manufacture.  Thus it seems reasonable to levy the restriction
that the diameter of the machine should grow linearly in the diameter $N$
of the simulated space.  In this case, as we saw earlier, reversible
machines win by a factor of $O(\sqrt{N})$, so demonstrating a factor of 10
increase in the relative benefit from reversibility only requires a factor
of 100 increase in scale.  In particular, we calculate that with a typical
current VLSI technology and with a heat removal limit of 100 W/cm$^2$, a
surface covered with 100 layers of circuitry packed at the maximum planar
circuit density could perform about 10 times more operations per second if
it used reversible circuits rather than standard circuits.  A machine of
this scale could feasibly be demonstrated today within the scope of a
university research project.

Furthermore, as reversible computing technologies improve in efficiency in
the future, the size of the machines where reversibility wins will decrease
as well.  In Frank \& Knight '97 \cite{Frank-Knight-97} \S 7.3, we calculate that
some projected future reversible technologies will be faster than {\em any
  possible} irreversible technology in computers of all scales larger than
a few microns to a few millimeters across (depending on the technology).
If highly efficient reversible technologies such as these are developed,
the scale at which reversibility wins even if machines are {\em not}
maximally compact will decrease as well.

\section{A Reversible 3-D Mesh Model}

We will discuss in this section how existing mesh-communication models of
computation might be modified and augmented in order to arrive at a model
that achieves at least as good an asymptotic scaling behavior as any
physically possible (and non-quantum-coherent) digital computer, and that
scales strictly better than any real implementation of any existing model.
We intend this discussion to be of direct relevance to the architecture of
future large-scale computers.  The modifications and additions we outline
here also ensure that no algorithm analyzed with the help of this model
will be predicted to have better scaling behavior than is physically
achievable.

\paragraph{Mesh computers.}
Mesh-organized computing structures have previously been studied
extensively in the context of parallel algorithms (see, for example,
Leighton '92 \cite{Leighton92} ch. 1), parallel computing theory
\cite{Vit88,BilPrep-93} and real parallel architectures (Dally {\em et al.}
'89 \cite{Dally89}, Shoemaker {\em et al.} '97 \cite{Shoe97}), and also in
the form of the systolic arrays of VLSI Theory (Leiserson '83
\cite{Lei83}).  They accurately capture the physical constraint that
information is transported with a finite maximum velocity: processors that
are closer together can interact more rapidly than distantly separated
processors.

\paragraph{Adding reversibility.}
We would like to capture the physical constraint of microscopic
reversibility in a mesh architecture.  We claim that this is all that needs
to be added to the model in order to describe a computing medium that has
the same asymptotic scaling behavior that is achievable for any digital
physical system without large-scale quantum-coherence.

Thus we begin with a 3-D array of asymptotically reversible processing
elements, interconnected by a reversible mesh communication network.  In
such a computer, one has the opportunity and the need to explicitly manage
entropy removal.  Recall that even with asymptotically reversible devices,
thermal entropy and heat is generated due to dissipative losses (see
eq.~(\ref{eq:ivst2}).  We imagine that our system includes a {\em cooling}
mesh that removes this waste heat, as well as a power mesh that supplies
the free energy and replenishes this heat loss.

Unwanted bits of digital entropy that are generated in the course of the
computation are removed from the interior of the machine by directly using
the communications mesh and transporting these bits to the edge of the
system as part of the normal communication process.  (Depending on
technology parameters, this may be more or less efficient by a constant
factor than transforming these bits into thermal entropy and removing them
using the cooling system, which is what takes place in present-day
computers.)

As discussed earlier, this architecture is modularly scalable: we can
increase the size of the system without changing the parameters of the
processing elements.  However, we need to be able to adjust the clock rate
of the processors, in order that we can implement the reversible algorithms
discussed in the previous section.  Those algorithms adjusted the rate at
which individual reversible operations are performed in order to achieve a
higher total rate of operation within a volume than is possible if the
operations are irreversible.

\paragraph{Running conventional computations.}
One can look at the reversible mesh as a digital computing substrate: it is
a space in which the computer architect has only provided the digital
abstraction, and a uniform array of computing elements.  One can of course
use this space to simulate the placement and functionality of the digital
logic that governs any computer.  As long as our reversible implementation
of the digital abstraction is as good as any existing technology, the
asymptotic performance of any computer simulation will be as good as the
``real'' thing.

\paragraph{Super-fast reversible algorithms.}
The real interest comes, of course, when we take advantage of the locality
and reversibility of the model to restructure and reorganize computations
to be more efficient, as in the example explored in earlier sections of
simulating reversible 3-D physical systems more efficiently that on any
irreversible computer.  When the computing model reflects the structure of
real space, the programmers can, if they choose, make the decisions that
today are the domain of the computer architect.  They can also, if they
choose, build on top of this substrate programming models and abstractions
(for example, a SIMD multiprocessor with PRAM-style shared memory) that
hide these low-level choices, much as modern computer architectures do.  An
implementation of any high-level programming model in software using the
reversible mesh substrate will be at least as efficient as any direct
physical implementation of the model.  But leaving a low-level physics-like
substrate visible to the programmer opens up the brand-new possibility that
programmers and computer scientists can create clever reversible algorithms
that are more efficient than any possible algorithm for traditional
irreversible architectures, as was the case for our earlier example of 3-D
physical simulations.

\section{Conclusion}

In this paper we have presented a strong argument, based on fundamental
physical constraints, that at least for large instances of certain classes
of (non-quantum) computations, a computer based on reversible primitive
operations is faster than any computer that is not.

Reversible computers that demonstrate this performance improvement can
actually be implemented by using the SCRL circuit techniques of Younis and
Knight {\cite{yk2,you}} together with commercially available VLSI
fabrication processes.  Large 3-D arrays of reversible processors of this
type (perhaps several meters across) should be able to perform physical
simulations faster than any conventional computer of comparable size.

Based on these insights, we have proposed a general-purpose architecture and
abstract model of computation called the Reversible 3-D Mesh.  The model
apparently permits expressing any physically possible scheme for the
storage, manipulation and transport of both information and the entropy
that is inevitably produced whenever information is discarded.  We
conjecture that therefore the model can solve any class of problems using
asymptotically no more time or space than any other non-quantum-coherent
digital architecture, within a reasonable constant factor.

\subsection{Future Work}

One very big area for future study is to try optimizing parallel algorithms
for various problems to run on the R3M model.  Due to the spatial nature of
the R3M, this is somewhat like designing specialized hardware to solve the
problem, in that one must think about the physical location of information
and how it flows through the system.  The R3M model makes sure that one
does not forget about the constraints imposed by the speed of light and the
reversibility of physics.

One important advance would be a high-level programming language for
expressing these ``physical'' algorithms.  Such a language would do
for the design of physical algorithms what current programming
languages do for the design of ordinary serial algorithms.  The
language would provide ways of expressing new high-level abstractions
of different ways of organizing the physical flow of information.

Finally, the classical approach of this paper begs the question, what about
quantum-coherent computers?  The research on quantum computers is extremely
interesting, and if implementation technologies get to the point where the
decoherence times are long enough to permit quantum error correction
techniques to be applied, it is possible that in the long run the
asymptotically fastest machines will actually be quantum computers.

But locality and entropy are realities of quantum mechanics as well as of
classical physics, so arguments analogous to those in this paper should
still apply, and so if coherent quantum computation works out, we expect
that the optimal architecture will likely be a {\em quantum} reversible 3-D
mesh, that directly generalizes our current classical R3M model.

\bibliographystyle{plain}
\bibliography{shortstr,refs}

\end{document}
