\documentclass[12pt]{report}
%----------------------------------------------------------------------
% package loading
%----------------------------------------------------------------------
\usepackage{psfig}		% For including postscript figures.
\usepackage{makeidx}		% For automatically-generated indexes.
\usepackage{amssymb}		% Extra math fonts and symbols.
\usepackage{amsbsy}		% Bold math symbols.
\usepackage{amstext}		% Text in math formulas.
\usepackage{amsmath}		% Lots more AMS math stuff.
\usepackage{amsthm}		% Theorems and such.
\usepackage{latexsym}		% Some extra math symbols in standard LaTeX.
\usepackage[dvips]{color}	% For color text

\usepackage{urls}		% My package for formatting URLs properly.
\usepackage{myslides}		% My custom package for slides.
\input{macros}			% My custom macros
\input{defmacs}		% defense-specific macros

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%				INTRO STUFF
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------
\slidetitle{The MIT Reversible Computing Project:\\
Personnel}

{\footnotesize
Present group members:
\mitem{Tom Knight - PI}
\mitem{Norm Margolus - physics \& computation, cellular automata}
\mitem{Grad students:
  \mitem{Carlin Vieri - circuits, reversible RISC}
  \mitem{Michael Frank - algorithms \& analysis}
  \mitem{Matt Becker - power supplies}
  \mitem{Josie Ammer - layouts, A/D converter}
  \mitem{Raissa D'Souza - reversible CA models of physics}}
\mitem{Undergraduates:
   \mitem{Matt DeBergalis - simulators, tools}}

Past group members:
\mitem{Saed Younis (now @ Qualcomm) - reversible logic circuit family (SCRL)}

Collaborators:
\mitem{ISI: Amory Wakefield, Lars Svensson, Bill Athas
   \mitem{Partially reversible circuits for near-term low-energy applications}
}}

\endslide
\note{This work was done as part of the MIT Reversible Computing Project;
here's who we are.

The work divisions are not sharp... most of us have been involved to some
degree in many different parts of the project.}

%----------------------------------------------------------------------
\slidetitle{The MIT Reversible Computing Project:\\
Major Accomplishments to Date}
{\footnotesize\setlength{\parindent}{0pt}
Reversible circuits:
\begin{mitems}
\item{SCRL circuit technique}
\item{Transmission line power supplies}
\item{Test chips: 4$\times$4 multiplier, systolic array, memory}
\end{mitems}

Full reversible RISC architecture:
\begin{mitems}
\item{Verilog simulation}
\item{Standard CMOS implementation}
\item{ISA simulators}
\item{Assembler, compiler}
\item{Test programs}
\end{mitems}

Theory of reversible computing:
\begin{mitems}
\item{Space/time complexity of reversible algs}
\item{Efficient physical simulations}
\end{mitems}

Engineering analysis:
\begin{mitems}
\item{Power/speed/cost tradeoffs}
\item{Accounting for leakage}
\item{Scaling laws for reversible 3-D arrays}
\end{mitems}
}
\endslide
\note{Do I even want to bother with this slide?}

%----------------------------------------------------------------------
\slidetitle{Motivation for this work}

\begin{mitems}
\item Efficient computing is valuable for society/economy.
\item Important for future of computing:
	\mitem{Understand physical constraints on computation.}
\item A goal for theory \& engineering:
	\mitem{Compute as efficiently as possible, within constraints.}
\item Near-term applications:
	\mitem{More efficient computing in constrained situations.}
\item Long-term application: 
	\mitem{Focus engineering to approach limits more\\ quickly/closely.}
\end{mitems}

\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{Reversible computing---The basic story:}
\vspace{-0.2in}
\noindent
\begin{mitems}
\item {\Irreversible} computers are thermodynamically crippled.
	{\small
	\begin{mitems}
	\item Microscopic physics is reversible.
	\item Information/entropy cannot be destroyed.
	\item Normal computers constantly ``erase'' bits.
	\item Really, discarded bits just become entropy.
	\item Remove entropy, or computer will melt.
	\item Entropy removal rates are bounded per area.
	\item So processing rates are also.
	\end{mitems}}
\item {\Reversible} computing to the rescue!
	{\small
	\begin{mitems}
	\item Can compute {\emph{without}} discarding bits.
	\item Instead, can {\emph{uncompute}} leftover data.
	\item Yields arbitrarily {\emph{lower}} entropy generation per
		operation.
	\item Arbitrarily {\emph{higher}} rate of computation per unit area.
	\item Can pack computing elements more densely in 3-D.
	\item Communication delays are lower.
	\item {\bf Overheads for reversibility are superseded by benefits.}
	\item Overall: large computers are faster if reversible!
	\end{mitems}}
\end{mitems}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{Overview of Contents}

\mitem{Motivation \& History}
\mitem{Fundamentals
	\mitem{Physical limits on computation}
	\mitem{Reversible computing theory}
	\mitem{Scaling of physical machines}}
\mitem{Engineering
	\mitem{Adiabatic logic circuits}
	\mitem{{\FlatTop} reversible mesh processor}
	\mitem{Future device technologies}
	\mitem{Programming reversible machines}}
\mitem{Conclusion \& Future work}

\endslide
\note{(Quickly talk through overview.) }

%----------------------------------------------------------------------
\slidetitle{History of Related Research}

\begin{mitems}
\item Early thermodynamics of computation:
	\mitem{\small von Neumann '49, Landauer '61.}
\item Reversible models of computation:
	\mitem{\small Lecerf '63, Bennett '73, Fredkin and Toffoli ('70's
		and '80's).}
\item Efficient reversiblizations: 
	\mitem{\small Bennett '89, Levine/Sherman '90, Lange/McKenzie/Tapp
		'94.}
\item Exotic reversible logic devices: 
	\mitem{\small Bennett '73, Fredkin '82, Likharev '82,
		Drexler '92, Merkle '96.}
\item Reversible electronics:
	\mitem{\small Watkins '67, Fredkin/Toffoli '78, Seitz '85,
Koller/Athas '92,\\Younis/Knight '93, many others\ldots}
\item Physics and scalability:
	\mitem{\small Vit\'anyi '88, Bilardi/Preparata '93, Smith '95.}
\end{mitems}
\endslide
\note{(No notes on this slide yet.)}

%######################################################################
%%
%%			      PHYSICS SECTION
%%
%######################################################################


%----------------------------------------------------------------------
\slidetitle{Physical limits on computation}
\begin{mitems}
\item Information propagation velocity $\leq c$.
\item Various theoretical/practical limits on density of\\
entropy/information.
\item Information flux limits: follow from above.
\item Connectivity limits, due to 3-dimensionality of space.
\item Quantum limit on rate of state transitions.
	\mitem{\small (Margolus \& Levitin '96)}
\item Thermodynamic minimum energy dissipation for bit erasure.
	\mitem{\small (Laundauer '61)}
\end{mitems}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{Reversibility of Physics}

\begin{itemize}
\item The dynamical equations of mechanics are time-sym\-met\-ric
and forward-deterministic, thus also reverse-de\-ter\-min\-is\-tic.
\item True in classical mechanics, QM, QED, GR, etc.
\item Example: {\Schroedinger} equation of quantum\\mechanics:
\end{itemize}
\vspace{-0.4in}
\[
-{\frac{\hbar^2}{2}}\sum_{j=0}^{N-1}{\frac{1}{m_j}}{\frac{\partial^2}{\partial
x_j^2}}\Psi(\vec{x},t)
	+ {\cal V}(\vec{x},t)\Psi(\vec{x},t)
	= i\hbar{\frac{\partial}{\partial t}}\Psi(\vec{x},t).\]
A differential equation determining how $\Psi$ changes with time---in
either time direction.
\endslide
\note{\small
When looking the implications of thermodynamics for computing, the first
essential thing you need to understand is the reversibility of physics.

This comes out of the fact that the dynamical equations of physical
mechanics are time-symmetric; that is, they have essentially the same form
whether one is looking in the forwards or reverse time direction.  In
particular, they are deterministic in both directions.

This is true in every variety of fundamental physics---classical Newtonian
mechanics, Maxwell's equations of electromagnetism, quantum mechanics,
quantum field theories such as quantum electrodynamics, special and general
relativity---whatever you like.

As an example, here is {\Schroedinger}'s basic equation of quantum
mechanics.  For now the details are not important.  What is important is
just that this is a differential equation that gives you the rate of change
of this wavefunction $\Psi$ here over time, which determines how $\Psi$
changes as you look forwards in time, or equally well backwards in time.

[From time to time, you may hear people talk about the ``nondeterminism''
of quantum mechanics, but this can be interpreted as an entirely subjective
phenomenon, that emerges from this underlying deterministic mechanics.]}

%----------------------------------------------------------------------
\figureslidew{incentropy.epsi}{3in}{Why entropy increases}{}
\note{\tiny
Given the reversibility of physics, it is easy to understand some important
concepts of thermodynamics.  Suppose we have a physical system that in
general has a certain number $N\tg{max}$ of possible states that it may be
in.  But suppose we happen to know, in a particular instance, that the
system is actually in some state in a relatively small, easily described
subset of these states, such as these 7 states here.  Now suppose that the
system undergoes some physical changes whose exact details are not
completely known.  Then afterwards, although we know from the determinism
and invertibility of physics that the system really is still in one of only
7 states, we may not know {\emph{which}} 7 states, and so from our point of
view more states have become ``possible,'' perhaps all of them.  So in this
sense the number of possible states has increased.

Now, suppose we wished that the system would now undergo some other
transformation such that, at some particular later time, we will know it is
back in this set of 7 states again.  Unless there is some reason to expect
that the further evolution of the system will exactly undo whatever is in
here, this is impossible!  Since all 23 states are now, from our point of
view, possible, any further isolated dynamical evolution of the system will
have just as many possible states---otherwise we would have a case where
two states deemed ``possible'' have merged into one.

Thus, the number of possible states of an isolated system, from the point
of view of our knowledge of the system, can only increase, as we lose
information about the state of the system.  The logarithm of the number of
possible states, which measures the amount of new information we would need
to pin down the state completely to only 1 possible state, is called the
system's entropy.  So we have just shown that entropy can only increase.

There is another way to use this same diagram.  One interesting measure of
the complexity of a system is minimum description length, that is, what is
the length of the shortest description of a system?  Initially this system
has a simple description, namely, it is in one of the ``bottom'' 7 states.
After some arbitrary unknown reversible transformation takes place, the
system will almost certainly become more complex, by a simple combinatoric
argument which shows there are much more complex states than there are
simple ones.  The overwhelming majority of states are incompressible, which
means there is no description of the system that is simpler than just
writing out all the details, which in this case means ``state 2, 5, 6, 9,
13, 19, or 21.''  So the complexity of a system also increases.
}

%----------------------------------------------------------------------
\figureslide{entropy.epsi}{Venn diagram of types of information/entropy}{
\begin{mitems}
\item Any closed system with finite energy and volume has a finite maximum
entropy $S\tg{max}$. (Although if volume increases, $S\tg{max}$ may also.)
\item Out of this, the bits that are uncorrelated, or whose correlations
have been lost, are entropy.  Other bits can be considered ``free memory''
or negentropy.
\item In general some bits of a system are manipulable by us, some not.
Some manipulable bits may also be entropy.
\end{mitems}
}
\note{Venn diagram of entropy and information.  Any system of finite size and
energy has a finite maximum entropy; however, if the system expands without
bound, the maximum entropy may also.  The maximum entropy may be considered
the total amount of information of all kinds in the system.  However, much
of it may be redundant and cross-correlated.  Bits of information that are
uncorrelated, or whose correlations have become lost beyond all hope of
recovery, are entropy, which can only increase in a reversible universe.
Some portion of the system, and the information in it, is within our
ability to manipulate and control, such as bits within a computer.  These
bits, too, may either be entropy or not, depending on our ability to know
their correlations.}

%----------------------------------------------------------------------
\slidetitle{Various limits on entropy density for meter-scale objects}
\centerline{\begin{tabular}{|l|c|l|}
\hline\hline
	       & Limit               &\\
Material       & in $\bit/\Ang$$^3$  & Caveats \\
\hline\hline
Black hole     & $\e{4.14}{39}$      & Need mass $\approx$ Saturn;\\
	       &                     & can't get info.\ out!\\
\hline
Non-BH         & $\e{1.53}{22}$      & Requires nearly as\\
	       &		     & much mass.\\
\hline
Normal density & $\sim \e{3}{5}$     & May require billion-degree\\
	       &		     & temperatures.\\
\hline
Atomic matter  & $\sim 1\mbox{--}10$ & Hand-waving estimate.\\
\hline\hline
\end{tabular}}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{Summary of physical limits on computation}
  \centerline{
    \begin{tabular}{|l|c|l|}
      \hline
      Quantity & Symbol & Limit \\
      \hline\hline
Info.\ propagation speed & $v$ &
	$ \leq c\approx3\times10^8\:\meter/\second$ \\
Information density & $\sdens$ &
	$\lesssim$ 1--10$\units{\bit}/\Ang $$^3$ ?? \\
Information flux & $\sflux$ &
	$ \leq \sdens v$ \\
Rate of state change & $\orthrate$ &
	$ \leq 4(E-\lowestE)/h$ \\
Diss.\ per bit erased & $\Delta E$ &
	$ \geq \kB T\ln 2$ \\
      \hline
    \end{tabular}
  }
\vspace{0.5in}
\begin{mitems}
\item Some bound on $\sdens$ exists, but its value is uncertain.
\end{mitems}
\endslide
\note{Summary of the
    fundamental physical constraints on information processing we've discussed.
    The value of the bound on
    $\sdens$ is very uncertain, but the assertion that some such bound
    exists is not.  For any particular computing technology through the
    foreseeable future, there will generally be much stricter limits than
    the above on most of these quantities.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%			     QUANTUM COMPUTING
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------
\figureslide{shor1.epsi}{Shor's algorithm: Initial preparation}{
\begin{mitems}
\item Number to factor is $N=33$.
\item Range of exponents to compute (mod N) goes up to $q=256$ (ideally 2048).
\item Register $a$ is put into an equal superposition of all values 0 to
	$q-1$.
\item Register $b$ is initially 0.
\end{mitems}
}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{shor2.epsi}{Shor state after classical exponentiation}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{shor-smooth2.epsi}{Shor state after quantum Fourier transform}{}
\note{(No notes on this slide yet.)}

%######################################################################
%%
%%			     CIRCUITS SECTION
%%
%######################################################################

%----------------------------------------------------------------------
\figureslide{inv.epsi}{Ordinary CMOS inverter}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{cmos1.epsi}{CMOS inverter dynamic behavior}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{Energy dissipation in {\irreversible} switching}
\vspace{-.1in}
\centerline{\psfig{file=switch.epsi,width=2.5in}}
{\setlength{\parindent}{0pt}
Energy supplied: $E_{\rm supp} = QV = CV^2$.

Energy stored: $\displaystyle E_{\rm stor} = \int dE = \int v\,dq = \int
{\frac{q}{C}}\,dq = \frac{1}{C} \int_0^Q q\,dq \\
= \frac{1}{C}\,\left.{\frac{1}{2}}q^2\right|_{q=0}^Q = {\frac{1}{2C}} Q^2 = {\frac{1}{2C}} (CV)^2 = {\frac{1}{2}} CV^2$.

Energy dissipated: $\displaystyle E_{\rm diss} 
= E_{\rm supp} - E_{\rm stor} = CV^2 - {\frac{1}{2}}CV^2 = \fbox{$\displaystyle {\frac{1}{2}}CV^2$}$.}
\endslide
\note{Note that the dissipation is completely independent of switch resistance.

At a given voltage, $R$ affects the speed of charging, but not the dissipation.}

%----------------------------------------------------------------------
\slidetitle{Reliability bound on $CV^2$}

\begin{center}
\[
\frac{1}{2} CV^2 \geq \kB T\,\ln N
\]

where $N$ is desired \# ops btw.\ errors
\end{center}

\begin{mitems}
\item Provable from basic thermodynamics.
\item Necessary to avoid logic errors due to thermal (``$kT/C$'') noise.
\item Applies to {\emph{both}} {\irreversible} \& {\reversible} circuits.
\item Difference is: 
  \mitem{In {\reversible} circuits, this energy need not be {\emph{dissipated}}.}
\end{mitems}

\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslidew{current.epsi}{3in}{Charging with constant current}{
\vspace{0.5in}
\begin{eqnarray*}
E_{\rm diss} &=& \int p\,dt 
= \int i^2R\,dt 
= I^2RT
= \left(\frac{Q}{t}\right)^2Rt\\
&=& {\frac{Q^2}{t}}R
= {\frac{(CV)^2}{t}}R
= \fbox{$\displaystyle CV^2\,{\frac{RC}{t}}$}\,.
\end{eqnarray*}
}
\note{Using a constant current source, we can charge the load capacitance up to
$V$ in time $t$ with dissipation that scales inversely to the time taken.

Note that at a given speed, the dissipation also scales down as we lower
the switch resistance, and scales down with the square of the capacitance.}

%----------------------------------------------------------------------
\figureslidew{cmos.epsi}{3in}{Controlled {\reversible} charging in CMOS}{
\begin{mitems}
\item Approximate current source by voltage ramp.
\item Replace resistor with a MOSFET (semiconductor transistor).
\item Must have $V < V_{\rm G} - V_{\rm T}$.
\item Can be discharged by a similar ramp.
\end{mitems}
\begin{eqnarray*}
t \gg RC&\colon& E\tg{diss} \rightarrow CV^2\,{\frac{RC}{t}}\\
t \ll RC&\colon& E\tg{diss} \rightarrow \frac{1}{2}CV^2
\end{eqnarray*}
}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{curves.epsi}{Voltage curves for slow and fast charging}{
\begin{mitems}
\item (a) Slow charging: Load lags behind power supply by a small voltage
drop $V\tg{ds}$ across the transistor, which scales with $1/t\tg{r}$.
\item (b) Fast charging: Load approaches supply level in exponential-decay
fashion.  Most charge is delivered from a voltage of $\Vdd$.
\end{mitems}
}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{SCRL inverter}
\centerline{\psfig{file=scrl-inv.epsi,width=3in}}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{general.epsi}{SCRL generalized inverter}{
\begin{mitems}
\item There may be several input signals.
\item Uses complementary pull-up and pull-down networks like standard
static CMOS.
\item Schematic icon labeled with function computed and clock phase.
\end{mitems}
}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{latch.epsi}{SCRL bidirectional latch}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{pipe.epsi}{SCRL pipeline}{
\begin{mitems}
\item Each stage may be many gates in parallel, considered as an $n$-input,
$m$-output invertible Boolean logic function.
\item Reverse stages uncompute the inputs to forward stages.
\item Each stage has its own clock phase, until repeat.
\item A stage may use 2 nested levels of gates to compute non-inverting
functions.
\item Sequential circuits with feedback fine, if phases aligned properly.
\end{mitems}
}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{timing.epsi}{Timing diagram for 3-phase SCRL}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslidew{modelv3.epsi}{2in}{Simplified SCRL circuit model}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{scrl-snag.epsi}{A problematic case for the original SCRL}{
{\footnotesize
\begin{mitems}
\item Inner n-FET asked to pass a high voltage.
\item Barely turns off as inner node voltage approaches threshold.
\item $V\tg{x}$ crawls up by several $\Vth$s over a substantial voltage
drop.
\item In numerical experiments, dissipation was still $\sim 3000\,\kT$ in
this case, when other dissipations were $< \kT$.
\item This dissipation not eliminated unless circuit so slow that leakage
dominates.
\end{mitems}}
}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslidew{scrl-fix.epsi}{2in}{Fixing the problem case}{
\vspace{0.25in}
\begin{mitems}
\item Add p-FET to pulldown network, as shown.
\item Interior node now tracks all the way to $\Vdd$.
\item General solution: use dual-rail logic and transmission gates
everywhere.
\end{mitems}
}
\note{The problem described in the previous slide can be fixed easily by
adding a p-FET to the pulldown network, wired as follows.  In the case
show, the interior node now can easily follow the output voltage all the
way to $\Vdd$.  More generally, the problem could be fixed by using
dual-rail logic signals and CMOS transmission gates everywhere in place of
single transistors, at the cost of increased area.}

%----------------------------------------------------------------------
\figureslidew{evstr.epsi}{3in}{Scaling of energy/op in SCRL with speed, given
nonzero leakage}{
{\setlength{\parindent}{0pt}
Optimum $\displaystyle t\tg{r} \propto
C\tg{L}\sqrt{\frac{V\tg{T0}}{kP\tg{lk}}}$,
$\displaystyle E\tg{min} \propto C\tg{L}\sqrt{\frac{V\tg{T0}P\tg{lk}}{k}}$.
}}
\note{(No notes on this slide yet.)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%			      FLATTOP SECTION
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------
\figureslide{bbgates.epsi}{The Billiard Ball Model of computation}{
Idealized ``billiard balls'' bounce of walls \& each other in
digitally-precise trajectories. (Fredkin \& Toffoli, '82)
\begin{mitems}
\item Extremely simple.
\item Reversible.
\item Universal.
	\begin{mitems}
	\item Efficiently simulates arbitrary 2-D reversible cellular
		automata or reversible circuits.
	\item Extensible to 3-D.
	\end{mitems}
\end{mitems}
}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{Flattop analysis}
\begin{mitems}
\item Estimated room-$T$ minimum energy/op.
\item $10\units{fJ}$/cycle/cell.
\item iCMOS estimated at $20 pJ$.
\item Factor of 2000 energy savings!
\item Optimal cycle time: 12$\mu$s (83 kHz)
\end{mitems}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{The BBM cellular automaton\\(Margolus '88)}
\centerline{\psfig{file=margneigh.epsi,width=1.5in}~\psfig{file=bbmrules.epsi,width=2.5in}}
\begin{mitems}
\item Updated in 2 alternating, overlapping partitionings of array into
2$\times$2 blocks of cells. (``Margolus neighborhood.'')
\item Each block updated independently \& reversibly.
\end{mitems}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslidew{bbmcalogic.epsi}{3in}{Boolean logic form of\\BBMCA update
rule}{
\begin{mitems}
\item Simplest logic found to date (in terms of \# transistors).
\item Computed in two logic levels: first for S, and second for A',B',C',D'.
\end{mitems}
}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{pegrid.epsi}{Grid of FlatTop processing elements}{
\begin{mitems}
\item Each 2$\times$2 block of cells handled by one PE.
\item PE visualized at center of each block.
\item Cell state passed between diagonally adjacent PEs.
\item PE mesh oriented 45$^\circ$ to cell grid.
\item Chip edges chosen parallel to PE mesh.
\item Implements two non-interacting BBMCA systems.
\end{mitems}
}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{pe.eps}{Block diagram of a FlatTop processing element}{
\begin{mitems}
\item Note 3 SCRL stages proceeding left to right.
\item First stage computes S.
\item 2nd stage updates the 4 cells.
\item Third stage uncomputes S (and handles initialization).
\end{mitems}
}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslidew{icon.eps}{3in}{Icon for a single FlatTop cell}{
\begin{mitems}
\item Mnemonic graphic evoking CA functionality
\end{mitems}
}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{corner.eps}{One corner of an array of FlatTop PEs}{
\begin{mitems}
\item PE icons overlap each other at corners
\item Note some edge cells go to pads, others wrap around
\item Initialization/readout path at upper left.
\end{mitems}
}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{array.eps}{The full 20$\times$20 array of PEs}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{stage1.eps}{FlatTop stage 1 logic gate}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{arbiter.eps}{FlatTop stage 2 logic}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{celllayout.eps}{Layout of a FlatTop PE}{
\begin{mitems}
\item 0.5 $\mu$m process (HP14)
\item $\sim 300$ transistors
\item $\sim 170\units{\mu m}\times 90\units{\mu m}$
\end{mitems}
}
\note{(No notes on this slide yet.)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%			    PROGRAMMING SECTION
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------
\slidetitle{PISA instruction set:\\simulator/compiler version}

{\footnotesize
\begin{verbatim}
Key:
rsd,rt = 5-bit register identifier. 
  No-Op if rsd is same reg as rt.
imm,amt = 16 bit signed immediate
  [imm] = imm sign-extended to 32 bits

"Non-expanding" arith./logical operations:

Mnem.   Args.      Forwards behavior
-----   ---------  ---------------------
NEG     rsd        rsd = -rsd
ADD     rsd,rt     rsd += rt (mod 2^32)
ADDI    rsd,imm    rsd += [imm] (mod 2^32)
SUB     rsd,rt     rsd -= rt (mod 2^32)
XOR     rsd,rt     rsd ^= rt
XORI    rsd,imm    rsd ^= [imm]
RL      rsd,amt    rsd = rsd rol amt
RLV     rsd,rt     rsd = rsd rol rt
RR      rsd,amt    rsd = rsd ror amt
RRV     rsd,rt     rsd = rsd ror rt
\end{verbatim}}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{PISA instruction set, cont'd.}

{\footnotesize
\begin{verbatim}
Key:
rd,rs,rt = 5-bit register identifier. 
  No-Op if rd is same reg as rs or rt.
imm,amt = 16 bit signed immediate
  [imm] = imm sign-extended to 32 bits

"Expanding" arith./logical operations:

Mnem.   Args.      Forwards behavior
-----   ---------  ---------------------
ANDX    rd,rs,rt   rd ^= rs&rt
ANDIX   rd,rs,imm  rd ^= rs&[imm]
NORX    rd,rs,rt   rd ^= ~(rs|rt)
ORX     rd,rs,rt   rd ^= rs|rt
ORIX    rd,rs,imm  rd ^= rs|[imm]
SLLX    rd,rs,amt  rd ^= rs<<amt
SLLVX   rd,rs,rt   rd ^= rs<<rt
SLTX    rd,rs,rt   rd ^= (rs<rt)?1:0
SLTIX   rd,rs,imm  rd ^= (rs<imm)?1:0
SRAX    rd,rs,amt  rd ^= rs>>amt
SRAVX   rd,rs,rt   rd ^= rs>>rt
SRLX    rd,rs,amt  rd ^= (unsigned)rs>>amt
SRLVX   rd,rs,rt   rd ^= (unsigned)rs>>rt
\end{verbatim}
}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{PISA instruction set, cont'd.}

{\scriptsize
\begin{verbatim}
Key:
rd,ra,rb = 5-bit register identifier. 
off = 16 bit signed offset
loff = 26 bit signed offset
dir = +1/-1 bit where +1=forward, -1=reverse
BR = internal "branch register"

Branch instructions:

BEQ     ra,rb,off  if ra=rb, BR+=off*dir
BGEZ    rb,off     if rb>=0, BR+=off*dir
BGTZ    rb,off     if rb>0, BR+=off*dir
BLEZ    rb,off     if rb<=0, BR+=off*dir
BLTZ    rb,off     if rb<0, BR+=off*dir
BNE     ra,rb,off  if ra!=rb, BR+=off*dir
BRA     loff       BR+=loff*dir
RBRA    loff       dir=-dir, BR+=loff*dir
SWAPBR  r          r<->BR

PC update between instructions:
  if (BR=0) pc+=dir else pc+=BR*dir

Memory & I/O instructions:

EXCH    rd,ra      rd <-> mem[ra]
READ    ra         ra ^= next word from input str.
TAKE    ra         ra <-> next word on I/O stream
SHOW    ra         Copies ra to output stream.
EMIT    ra         Emit ra to garbage stream.
\end{verbatim}
}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslidew{revers.epsi}{3in}
	{Reversible and irreversible machine configuration graphs}{
\begin{mitems}
\item Out-degree is always no more than 1 (determinism).
\item Reversible in-degree is also no more than 1 (reversibility).
\item Reversible configuration graph consists of disjoint loops and chains,
which may be infinite (if the configuration space is infinite).
\end{mitems}
}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{Reversible algorithms}
\begin{mitems}
\item Sorting $n$ items:
	\begin{mitems}
	\item Generates $\Exactly(\log n!)$ garbage in worst case.
	\item Hall '94 reversible insertion sort achieves this in
		time $n^2$.
	\item Quicksort \& other $\Exactly(n\log n)$ time sorts can
		be made reversible with no slowdown and
		$\Exactly(n\log n)$ garbage
	\item Radix sort (time $\Exactly(n)$): no slowdown and
		$\Theta(n)$ garbage.
	\end{mitems}
\item Arithmetic on $n$-bit integers.
	\begin{mitems}
	\item Addition or subtraction: time $\Exactly(n)$, zero garbage.
	\item Multiplication: $\Exactly(n^2)$ grade-school alg.\ with
		no slowdown \& no garbage except operands.
		\begin{mitems}
		\item Can often eliminate 1 op by division.
		\item Can sometimes eliminate both ops by factoring.
		\end{mitems}
	\item Naive $\Exactly(n^3)$ matrix multiplication algorithm
		also w.\ no slowdown \& no garbage.
		\item Matrix inversion to eliminate 1 operand.
	\end{mitems}
\end{mitems}
\endslide
\note{(No notes on this slide yet.)}
%----------------------------------------------------------------------
\slidetitle{Reversible algorithms, cont'd.}
{\small
\begin{mitems}
\item Search algorithms:
	\begin{mitems}
	\item Breadth-first or depth-first search with no increase
		in time or space \& no garbage.
	\end{mitems}
\item Graph problems on $n$ nodes:
	\begin{mitems}
	\item All-pairs shortest path: Floyd-Warshall alg.\ takes time
		$\Exactly(n^3)$, space $\Exactly(n^2)$.
	\item Naive reversible version seems to take space $\Exactly(n^3)$.
	\item Alternative ``matrix squaring'' alg.: reversible
		time $\Exactly(n^3\log n)$, space $\Exactly(n^2\log n)$.
		(Leighton)
	\item Illustrates that the best rev.\ algs.\ may have a very
		different structure from the best irrev.\ algs
	\item Algorithm designer must be aware of machine's reversibility.
	\end{mitems}
\item Physical simulations (Margolus, D'Souza, others):
	\begin{mitems}
	\item Reversible models of physics have no overhead, good stability.
	\item Reflect underlying reversibility of physics.
	\item Example: {\Schroedinger} wave simulation.
	\end{mitems}
\end{mitems}}
\endslide
\note{(No notes on this slide yet.)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%			      THEORY SECTION
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------
\slidetitle{Traditional reversible computing theory---Results}

\vspace{-.2in}
{\setlength{\parindent}{0pt}Results in the traditional theory context:}
\begin{mitems}
	\item {\Reversible} machines are universal and can sim.\
{\icolor{irrev.}}\ machs.\ in linear time. (Save a history.)
		\mitem{\footnotesize{(Landauer '61)}}
		\vspace{-.1in}
	\item History can be uncomputed,
		leaving no output.
		\mitem{\footnotesize{(Lecerf '63)}}
		\vspace{-.1in}
	\item Desired output can be copied before reversing
		\mitem{\footnotesize{(Bennett '73)}}
		\vspace{-.1in}
	\item Above results extend to parallel models, 
		including cellular automata and boolean circuits 
		\mitem{\footnotesize{(Toffoli '77, Toffoli \& Fredkin,
		'80-'82)}}
		\vspace{-.1in}
	\item \icolor{Irrev}$\rightarrow$\rcolor{rev} translation
		w.\ polynomial time increase \& logarithmic space increase.
		\mitem{\footnotesize{(Bennett '89)}}
		\vspace{-.1in}
	\item Linear-space simulation (w.\ exponential time increase) 
		also possible.
		\mitem{\footnotesize{(Lange \etal\ '97)}}
		\vspace{-.1in}
	\item Linear space \& time simulation is probably impossible
		\mitem{\bf (Frank \& Ammer '97)}
\end{mitems}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{Reversible simulation in linear space}
\vspace{-.2in}
\centerline{\psfig{file=lmt.epsi,width=3in}}
{\footnotesize
\begin{mitems}
	\item Lange, McKenzie, Tapp (1997).
	\item We can reversibly iterate through possible predecessors of an
		irreversible machine configuration.
	\item Use this for an ``Euler tour'' of irreversible
		machine's entire configuration tree (above).
	\item Though tree has branches, traversal around entire tree is
		reversible.
	\item Cut off search wherever space limit is exceeded.
	\item Space requirement: just initial state ($\Atmost(\SP)$) plus
		current state ($\Atmost(\SP)$).
	\item Time for search is $\Atmost(2^\SP)$.
	\item Correct space limit can be found by successively trying higher
		and higher bounds until final state is found.  (My own
		contribution.)
\end{mitems}}
\endslide
\note{(No notes on this slide yet.)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%			      ORACLE SECTION
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------
\slidetitle{{\Reversible} vs.\ {\irreversible} space-time complexity}

{\setlength{\parindent}{0pt}
Ignoring thermodynamic issues, how efficiently can {\reversible} machines
simulate {\irreversible} machines?}
\begin{mitems}
\item Bennett '73: Linear time, but polynomially greater space.  
\item Lange {\etal}\ '97: Linear space, but exponentially greater time.
\item Important open question: Is there a single simulation
technique that takes only linear space {\emph{and}} only linear time?\\
($\forall\,\SP,\TI\colon\;\RST{\SP}{\TI}=\ST{\SP}{\TI}$)?
\item Frank \& Ammer '97: Any such technique would fail if you:
	\begin{mitems}
	\item Add a (computable) reversible oracle.  
	\item Or, provide input in the form of a reversible ROM (whose
		size you don't count).
	\end{mitems}
\item Remember: this negative result is in the context of traditional
models of computation, which ignore the potential algorithmic costs of
entropy generation.
\end{mitems}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{Elements of Frank-Ammer '97 proof:}
{\footnotesize
\begin{mitems}
\item Initial insight: traversing a singly-linked list seems hard to do
	reversibly.
\item Provide links in the form of an oracle or a ROM, mapping {\tt
	(node)} {$\leftrightarrow$} {\tt (node + successor)}.
	\begin{mitems}
	\item Individual oracle/ROM calls are reversible \& easy to undo.
	\item Hard part is forgetting nodes previously visited.
	\item Analogy w.\ reversible computation of a 1-way cryptographic
		function (invertible, but hard to invert).
	\end{mitems}
\item Choose a chain of nodes that is algorithmically incompressible.
	\begin{mitems}
	\item Can be proven to exist.
	\item Specified by diagonalization over all possible machines.
	\end{mitems}
\item Show that if a reversible machine can traverse this chain (using much
less space than Bennett '89, and much less time than Lange \etal '97) then:
	\begin{mitems}
	\item You can reconstruct previous nodes in the chain from
		a given machine state, by running the machine in reverse.
	\item Provides a way to compress the chain. (Contradiction.)
	\end{mitems}
\item Uses Li \& Vit\'anyi '96 result that Bennett '89 is space-optimal
among a certain class of reversible simulation techniques.
\end{mitems}}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{permut.epsi}
	{Structure of permutation oracles}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{grapho.epsi}
	{Encoding outdegree-1 directed graphs in permutation oracles}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{chain.epsi}
	{Problem graph defined by our oracle}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{game.epsi}
	{Bennett's optimal reversible pebble game strategy}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{triang.epsi}
	{Triangle representation of oracle queries}{}
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\figureslide{pebble.epsi}
	{Visualizing the definition of the set of pebbled nodes}{}
\note{(No notes on this slide yet.)}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%			  ULTIMATE MODELS SECTION
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------
\slidetitle{A worthwhile goal for\\Computer Science:}

\begin{center}
\fbox{\parbox{2.5in}{\centering Develop \& study\\\emph{ultimate} models\\of physical computation}}
\end{center}

\setlength{\parindent}{0in}
Such a model should:
\begin{mitems}
\item Be physically realizable.
\item Accurately model physical constraints affecting asymptotic scaling
	behavior (time \& space requirements).
\item Given that, scale as well as possible.
\end{mitems}

Benefits of model:
\begin{mitems}
\item Basis for designing efficient, scalable computers.
\item Unchanging framework for algorithms design.
\end{mitems}

\endslide
\note{
I think a lot of people here would agree that a very good goal for Computer
Science, as a scientific and engineering enterprise, would be to develop
what we might call ``ultimate'' models of physical computation---that is,
models of computation that are physically realistic, and their scaling
behavior matches that of their physical implementation; and yet that are
also as powerful as physically possible.

Having such a model would be great for computer engineering, because it
would steer us towards the right kind of architectures, and it would be
great for software engineering as well, because it would be kind of a
``fixed'' platform for algorithms design... Once you've found the best
algorithm for something, you won't have to redesign it when the next
generation of machine comes out, because that machine will have essentially
the same scaling behavior as the previous one, and will just have better
constant factors.  Right now, that isn't true because of all the different
parallel architectures and computing models that have wildly different
scaling behavior.  An ultimate model would bring order to this chaos.
}

%----------------------------------------------------------------------
\slidetitle{Physical constraints shape the ultimate model}

{\small
\begin{center}
\begin{tabular}{|l|l|} \hline
\textbf{Constraint}       & \textbf{Implications for model} \\ \hline\hline
Speed-of-light limit      & Locally-connected mesh \\
			  & {\small (Vitanyi '88)} \\ \hline
3-Dimensionality of space & 3-D connectivity \\ \hline
Entropy density limits    & 	\begin{minipage}{5in}
			    	\begin{tabbing}
				Finite state per processor /\\
				finite information flux 
			    	\end{tabbing}
				\end{minipage} \\ \hline
\begin{minipage}{5in}
\begin{tabbing}
Micro-reversibility /\\
2$^{\rm nd}$ law of thermo.
\end{tabbing}
\end{minipage} &	\begin{minipage}{5in}
			\begin{tabbing}
			Reversible logic /\\
			entropy accounting
			\end{tabbing}
			\end{minipage} \\ \hline
\end{tabular}
\end{center}}

\endslide

\note{\small
\begin{mitems}
\item Assuming only a speed-of-light bound and a non-zero processor size,
Vitanyi '88 proved that meshes are asymptotically optimal, even if wires
have zero thickness and can pass through processors.
\item In 3-D space, no network can select from more than $O(n^3)$ data items
in $n$ constant-time steps.
\item Processors must have limited state per unit volume; bandwidth per
unit area through machine is limited.
\item Claim: the reversibility of physics implies that the ideal
model must allow reversible processing, and account for flows of any
entropy produced.
\end{mitems}}
\note{\scriptsize
So here are some physical constraints shaping what we think the ultimate
model ought to look like.  People such as Vit\'anyi have already
established that a fixed speed limit implies that the optimal architecture
should be locally connected.  And of course, the fact that space is
3-dimensional means the topology of the connection mesh should be 3-D as
well.

But we're going to concentrate on these last two items here.

There are physicists such as Bekenstein that have studied fundamental
limits on entropy density.  The issue is still under debate, but it seems
that unless you allow unbounded temperatures or energy densities in a
system, entropy density is bounded.  In fact, it seems that the upper bound
on entropy density would only be achieved by a black hole, in which the
entropy scales with surface area, and so entropy density actually scales
down with volume.  So even picking a constant bound on entropy density is
generous.  But anyway, we'll ignore gravity issues for today.  Now, finite
entropy density implies finite memory per processor, and also a finite rate
of flow of entropy or information per unit area through any surface.

The next thing is that physics is reversible... this implies that you can
only get rid of a piece of information if it is actually redundant with
some other information you have, and you uncompute it... Otherwise it
sticks around in some form or another... This leads to the need for
reversible logic, and a careful accounting of all the information that
isn't uncomputed, which can be considered entropy.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%			      SCALING SECTION
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------
\slidetitle{{\Reversible} logic devices}

\begin{mitems}
\item {\em Logically} {\reversible}:
	\begin{mitems}
	\item Post-state determines pre-state.
	\end{mitems}
\item Asymptotically {\em physically} {\reversible}:
	\begin{mitems}
	\item Entropy per op typically proportional to speed.\\ $\entropy=\entco f=\entco/\timeop$.
	\item Entropy rate quadratic in speed. $\entropy/\timeop = \entco /\timeop^2$.
	\end{mitems}
\item Many technologies achieve this behavior.
	\begin{mitems}
	\item But entropy coefficient $\entco$ varies widely.
	\item No known fundamental lower bound on $\entco$.
	\item If $\entco=0$ is possible, we don't know how yet.
	\end{mitems}
\end{mitems}
\endslide
\note{
So suppose our devices don't throw bits away, and instead are logically
reversible---their state after an operation determines what their state was
prior to the operation.  Then it might be possible for them to operate in a
purely physically reversible way, producing no entropy.  But even if we
can't achieve this level of perfection, we can implement them in a way
where, the entropy per op is proportional to speed. (That is, the entropy
generation rate is quadratic in speed.)  Later we'll see a whole list of
existing and proposed implementation technologies that have this scaling
behavior, but there's a huge variation of this proportionality constant or
``entropy coefficient'' $\entco$, many orders of magnitude.  We don't know
of any fundamental lower bound on $\entco$, and it may be possible to
achieve values so infinitesimally close to zero that the difference is
meaningless... but if so, we don't know how.  }

%----------------------------------------------------------------------
\slidetitle{Spreading things out}

\begin{mitems}
\item How does performance scale with the number of processors?
\item If algorithm requires sufficiently little communication:
	\begin{mitems}
	\item Use {\irreversible} processors spread in a 2-D layer.
	\item Can remove entropy along perpendicular dimension.
	\item No speed advantage to reversibility.
	\item Still, {\reversible} machine dissipates less energy.
	\end{mitems}
\item If alg.\ requires local communication,\\ latency $\propto$ cycle time,
	then for an $N\times N\times N$ array:
	\begin{mitems}
	\item {\Reversible} machine still asymptotically faster!
	\item \icolor{Irreversible $t = \Exactly(\sqrt[3]{N})$}
	\item \rcolor{Reversible $t = \Exactly(\sqrt[4]{N})$}
	\item {\Reversible} advantage of $\Exactly(\sqrt[12]{N})$
	\mitem{\small $10^{36}\times$ more processors to increase
		rev.\ advantage by $10\times$!}
	\end{mitems}
\end{mitems}
\endslide
\note{\scriptsize
You might say the previous comparison was unfair because it only took into
account the machine's size but not its cost; that the reversible machine
was only faster because it could use many more processors within the given
volume of space.  What about speed with a given number of processors?

Well, this depends on the problem to be solved.  If there's a good
algorithm that requires no communication between processors, like a
brute-force search for cryptographic keys or large primes or something,
then we can spread out the processors arbitrarily until entropy removal is
no longer a factor and there is no speed advantage to reversibility---but
the reversible machine does dissipate less energy.

However, if we're doing a computation that requires frequent local
communication between processors, such as certain kinds of physical
simulations, then the speed-of-light limit prevents us from spreading the
processors too far apart.  It turns out that in this case, reversible
machines are still asyptotically faster because if you've got an N by N by
N array of processors, you can show (see paper) that the irreversible
machine takes time cube root of N per step, while the reversible one can
run in only fourth root of N per step.  But this is only a difference of
twelfth root of N, so your reversible technology had better have superior
constant factors to start out with, because to make up for a constant
factor of 10 requires looking at scales a trillion times larger, with 10 to
the 36 more processors.

We estimated that current reversible technology doesn't start to outperform
current irreversible technology with a given number of processors until one
compares machines having an amount of silicon with the mass of the planet
Saturn, with processors spread out over the entire solar system.
}

%----------------------------------------------------------------------
\figureslidew{imesh.epsi}{4in}{Best {\irreversible} machine for 3-D array
computations}{}
\note{Let's look at that scaling argument in a little more detail.  The
problem definition is to simulate an arbitrary 3-D locally-connected array
of constant-size irreversible processors.  The following irreversible
architecture is easily proved to be optimal for that task.  You have a 3-D
array of NxNxN processors, spaced apart a distance $N^{1/3}$, and with
their speed turned down to $N^{1/3}$ time per step.  This spreading apart
allows exactly enough space between columns of processors for the entropy
produced by the column to be removed through the area at the end of the
column at the maximum flux.  If the processors were closer together, the
array would have to run more slowly to give time for the entropy to escape.
If they were farther apart, the array would have to run more slowly to give
time for data to propagate between neighboring processors.  The thesis
gives a rigorous proof that applies to any arrangement of processors.}

%----------------------------------------------------------------------
\figureslidew{rmesh.epsi}{3in}{A faster {\reversible} machine for 3-D array
simulations}{}
\note{Now, here's what we can do on a reversible machine.  First, suppose
the CA to be simulated is reversible, so a reversible processor can
simulate it in O(1) time with no accumulation of garbage information.  Now,
slow the processors down and space them out by a factor of only $N^{1/4}$.
Due to the time-proportionate nature of the devices, they process $N^{1/4}$
times less entropy per operation, and there are $N^{1/4}$ times fewer
operations per unit time, so the rate of entropy generation per processor
goes down by $N^{1/2}$.  So the entire column of $N$ processors is only
producing entropy at a rate that scales up with $N^{1/2}$, and this is
exactly how the area for entropy removal scales up.  So the upshot is that
by slowing the processors down just a little bit and spacing them out just
a little bit, we run faster overall while still getting all the entropy out
than in the irreversible case, where we had to slow things down and spread
things out by a larger amount.  So the reversible machine is more cost
effective.}

%----------------------------------------------------------------------
\figureslidew{fold.epsi}{3in}{``Folding'' a column of processors to minimize volume}{}
\note{You might criticize all these solutions on the grouds that though
they are maximally cost-effective per processor, they waste all this
physical space because you have to spread the processors out.  But
actually, this isn't true: you can convert each of those machines to an
equivalent one that runs at the same speed (within a constant factor) but
in which the processor density is constant, as follows...}

%----------------------------------------------------------------------
\slidetitle{Further scaling results}
\begin{mitems}
\item Fully {\ballistic} machines:
	\begin{mitems}
	\item Full use of 3rd dimension.
	\item Faster per unit area than {\icolor{irr.}}\ by $\Exactly(d)$.
	\item Faster in 3-D mesh by $\Exactly(\Ndiam^{1/3})$.
	\end{mitems}
\item Longer communication distances:
	\begin{mitems}
	\item $\Exactly(\sqrt{\Ndiam})$ distance best for {\rcolor{rev.}}\ advantage
	\item {\Reversible} speedup $\Exactly(\Ndiam^{1/6})$.
	\end{mitems}
\item Reversible simulation of {\irreversible} arrays:
	\begin{mitems}
	\item Run Bennett alg.\ for limited \#steps.
	\item $\Exactly(\log{\Ndiam})$ processor size.
		(Approximate as $\Exactly(1)$.)
	\item {\Reversible} speedup of
		$\Exactly(\Ndiam^{\frac{1}{12}-\epsilon})$,
		for any constant $\epsilon > 0$.
		\mitem{Optimal $\epsilon$ varies w.\ $\Ndiam$.}
	\end{mitems}
\end{mitems}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{Summary of scaling results}

{\tiny
\begin{center}
\begin{tabular}{|l|l|c|c|c|c|c|}
\hline
                      &                       & \multicolumn{3}{|c|}{Cost in each model}               & \multicolumn{2}{|c|}{Advantage factors}                          \\ 
                                                \cline{3-5}                                              \cline{6-7}
Cost                  &                       & \FIA             & \TRA             & \BRA             & Reversible                      & Ballistic                      \\ 
measure               & Task type             & (\irrcost)       & (\revcost)       & (\balcost\label{pg:balcost})       & $\Revad=\irrcost/\revcost$      & $\Balad=\irrcost/\balcost$ {\label{pg:balad}}    \\\hline
\hline
$\cost=\entropy$      & any                   & \Nops            & $\probsize$      & $\probsize$      & $\Nops/\probsize$               & $\Nops/\probsize$              \\\hline
$\cost=\Time$         & no comm.              & $1$              & $1$              & $1$              & 1                               & 1                              \\
                      & local comm.           & $\Ndiam^{1/3}$   & $\Ndiam^{1/4}$   & $1$              & $\Ndiam^{1/12},\revcost^{1/3}$  & $\Ndiam^{1/3}$                 \\
                      & $\sqrt{\Ndiam}$ comm. & $\Ndiam^{2/3}$   & $\Ndiam^{1/2}$   & $\Ndiam^{1/2}$   & $\Ndiam^{1/6},\revcost^{1/3}$   & $\Ndiam^{1/6},\balcost^{1/3}$  \\\hline
$\cost=A\Time$        & no comm.              & \Nops            & $\Nops^{5/6}$    & $\Nops^{2/3}$    & $\Nops^{1/6},\revcost^{1/5}$    & $\Nops^{1/3},\balcost^{1/2}$   \\\hline
$\cost=\volume\Time$, & no comm.              & $\Ndiam^3$       & $\Ndiam^3$       & $\Ndiam^3$       & 1                               & 1                              \\
\ \ $\Mass\Time$,     & local comm.           & $\Ndiam^{3+1/3}$ & $\Ndiam^{3+1/4}$ & $\Ndiam^3$       & $\Ndiam^{1/12},\revcost^{1/39}$ & $\Ndiam^{1/3},\balcost^{1/9}$  \\
\ \ $\ldots$, $\cpcc$ & $\sqrt{\Ndiam}$ comm. & $\Ndiam^{3+2/3}$ & $\Ndiam^{3+1/2}$ & $\Ndiam^{3+1/2}$ & $\Ndiam^{1/6},\revcost^{1/21}$  & $\Ndiam^{1/6},\balcost^{1/21}$ \\ 
\hline
\end{tabular}
\end{center}}
\endslide
\note{(No notes on this slide yet.)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%			  FUTURE DEVICES SECTION
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------
\slidetitle{Projections for present \& future technologies}

\noindent
Rough estimates based on above scaling results, with actual constant
factors included, for several technologies.
\begin{mitems}
  \item Present/near-future VLSI, w.\ ordinary cooling:
	\begin{mitems}
	\item Circuits w.\ $\gtrsim$ a few hundred layers are
	      faster per area\\if {\reversible}.
	\item A $1\units{m^3}$, $1\units{MW}$ {\rcolor{rev.}}\ machine
	      could do $\sim~24$ PetaFLOPS\\
	      (vs.\ 1 PetaFLOPS in a superconductor-based
		{\icolor{irrev.}}\ design).
	\item Above a {\dlr}25 billion cost level,
	      {\rcolor{rev.}}\ machines become faster/processor
	      at some problems.
	\end{mitems}
  \item Various nano-scale {\reversible} technologies,
	w.\ aggressive cooling:
	\begin{mitems}
	\item Faster/area than {\emph{best
		possible}} {\icolor{irrev.}}\ tech.\ if thickness
		$>$ microns to millimeters.
	\end{mitems}
\end{mitems}
\endslide
\note{(No notes on this slide yet.)}

%----------------------------------------------------------------------
\slidetitle{Entropy transport / cooling technologies}

\begin{center}
\begin{tabular}{|l|c|}\hline
Technology
&
	\begin{minipage}{5in}
	\begin{tabbing}
	Max entropy\\
	flux $F$,
	$\displaystyle\left(\frac{{\rm bit}}{{\rm sec}\cdot {\rm cm}^2}\right)$
	\end{tabbing}
	\end{minipage} \\ \hline\hline
\begin{minipage}{5in}
\begin{tabbing}
1 Tb/s optic fiber\\
10 $\mu$m thick
\end{tabbing}
\end{minipage} & $\sim 10^{18}$ \\ \hline
\begin{minipage}{5in}
\begin{tabbing}
Passive emission\\
100 W/cm$^2$\\
$T\geq 300 K$
\end{tabbing}
\end{minipage} & $\leq 3.5\times 10^{22}$ \\ \hline
\begin{minipage}{5in}
\begin{tabbing}
Tuckerman\\
microcapillaries\\
$\sim 1$ kW/cm$^2$
\end{tabbing}
\end{minipage} & $\sim 3\times 10^{23}$ \\ \hline
\begin{minipage}{5in}
\begin{tabbing}
Drexler fractal\\
nano-plumbing\\
$\sim 10$ kW/cm$^2$
\end{tabbing}
\end{minipage} & $\sim 3\times 10^{24}$ \\ \hline
1 bit/\AA$^3$ @ 1 m/s & $10^{26}$ \\ \hline
1 bit/\AA$^3$ @ .1 c & $3\times 10^{33}$ \\ \hline
\end{tabular}
\end{center}
These are also approximately the limits on irreversible processing rates,
in bit-ops/sec-cm$^2$.
\endslide
\note{
This slide is for reference if people are curious about typical values for
entropy flux.  It is skippable, if short on time.

Tell audience these tables can be found in the paper prepared for the
nanotechnology conference, which is listed in our references.

Here are the maximum rates of entropy removal you could get with various
technologies.

If entropy were encoded digitally, then an optimistic projection for
bundles of optic fibers gives only about 10 to the 18 bits per second per
square centimeter.  This is already beaten by normal passive conduction
through chip packages which approaches 100 W per square cm, or about 10 to
the 22nd bits per second.  Using micro-channels through the silicon we
might be able to get up to around 10 to the 24th or so.  Finally, for
comparison, if you store 1 bit per cubic Angstrom, or about 1 bit per atom,
then at 1 meter per second you get 10 to the 26th, and at a tenth the speed
of light you get 10 to the 33.  You're probably never going to see real
values that high.
}

%----------------------------------------------------------------------
\slidetitle{Entropy generation in irreversible device technologies}
\begin{center}
\begin{tabular}{|l|c|}\hline
	   & Entropy (bits)\\
Technology & per bit erased\\ \hline\hline
$.5\mu$m CMOS @ 300K & $\sim 10^8$\\ \hline
best CMOS today & $\sim 10^6$ \\ \hline
\begin{minipage}{5in}
\begin{tabbing}
Likharev RSFQ\\
$10^{-18}$ J @ 5K
\end{tabbing}
\end{minipage}
		& $2\times 10^4$ \\ \hline
Lowest possible & 1 \\ \hline
\end{tabular}
\end{center}

\endslide
\note{
Another skippable reference slide.

This table shows the amount of physical entropy that is generated per bit
erasure in various irreversible logic technologies.

Modern CMOS typically generates anywhere from about a million to 100
million bits of physical entropy per bit erased.  There's this guy Likharev
who has this very cool (literally) superconducting technology that gets
down to around 20 kilobits of entropy per bit erased.  And of course, the
lowest possible is 1.
}

%----------------------------------------------------------------------
\slidetitle{Entropy coefficients of reversible device technologies}

\begin{center}
\begin{tabular}{|l|c|}\hline
Technology & \begin{minipage}{5in}
		\begin{tabbing}
		Entropy coefficient\\
		$\entco$ (bits/GHz)
		\end{tabbing}
		\end{minipage}\\ \hline
SCRL today & $\sim 10^9$ \\ \hline
\begin{minipage}{5in}\begin{tabbing}
optimistic\\
reversible\\
CMOS
\end{tabbing}\end{minipage}
	 & $\sim 10^5$ \\ \hline
Merkle Quantum FET & $\sim 1.2$ \\ \hline
Nano-rod logic & $\sim 0.07$ \\ \hline
\begin{minipage}{5in}\begin{tabbing}
Likharev\\
parametric\\
quantron
\end{tabbing}\end{minipage}
	 & $\sim 0.025$ \\ \hline
Helical logic & $\sim 10^{-5}$ \\ \hline
\end{tabular}
\end{center}
\endslide

\note{\small
Another skippable reference slide.

This is the constant of proportionality between amount of physical entropy
generation per operation, and speed of operation.  It is taken in bits per
gigahertz, although today's reversible technology probably can't quite run
at a gigahertz. (Maybe it could, in the latest processes.)

The main thing to note is the wide variation between the existing and
proposed technologies.  There's lots of room for improvement.

The second line is adiabatic logic projected a few generations ahead, and
assumes that some of the overheads of SCRL can be decreased.

The ``Quantum FET'' entry shows an extrapolation Merkle did to analyze
shuttling a 100-electron charge packet through some quantum-limited FET.

The ``Nano-rod logic'' is Drexler's nano-scale mechanical logic
technology... molecular clockwork.

Then we have Likharev's reversible superconducting magnetic flux thingies.

Finally we have something Merkle and Drexler proposed for moving charge
packets along helical wires using a rotating electric field.  They claim
extremely low dissipation, but someone else should take a look at it
sometime.}

%----------------------------------------------------------------------
\slidetitle{Scales above which\\reversible computing wins}
\begin{center}
\begin{tabular}{|l|c|c|c|} \hline
	& \multicolumn{3}{c|}{Irrev.\ device / cooling tech.} \\ \hline
\begin{minipage}{4in}\begin{tabbing}
Reversible\\
Technology
\end{tabbing}\end{minipage} &
\begin{minipage}{4in}\begin{tabbing}
CMOS/\\
passive
\end{tabbing}\end{minipage} &
\begin{minipage}{4in}\begin{tabbing}
RSFQ/\\
capillaries
\end{tabbing}\end{minipage} &
\begin{minipage}{4in}\begin{tabbing}
perfect/\\
1 bit/\AA$^3$\\
@ 1 m/s
\end{tabbing}\end{minipage} \\ \hline\hline
SCRL today & 0.2 mm & 50 m & 4 a.u. \\ \hline
Quantum FET & any & any & 1 mm \\ \hline
Rod logic & any & any & 3 $\mu$m \\ \hline
Helical logic & any & any & $< 1 {\rm mm}$ \\ \hline
\end{tabular}
\end{center}
\endslide
\note{\small
This slide is fairly interesting.  Earlier we showed
the formula for the diameter $d$ of machine for which 
reversible technology is faster.  Here we show what
that size is for various combinations of reversible
devices, irreversible devices, and cooling capacities.

First, SCRL already beats today's passively-cooled CMOS with only about 200
layers of circuits, which could be as small as .2 millimeters if the dies
were thinned to 1 micron thick.  With more traditional packaging, 200
layers of circuits would probably be more like a meter thick.

To beat Likharev's efficient superconducting logic with aggressive cooling,
we'd need to compare computers the size of a large building.  And to beat
the best possible irreversible technology, with some super-duper cooling
technology, we'd have to be the size of the inner solar system.  A solid
mass of silicon that big would collapse into a black hole.

But anyway, when you look at some of the better projected reversible
technologies, you see that they beat ordinary irreversible technologies at
any scale, and beat even the best possible irreversible technology at
reasonable scales ranging from microns to millimeters.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%				CONCLUSIONS
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------
\slidetitle{Summary of major contributions}
\begin{mitems}
\item Itemization of various physical constraints on computation.
\item In models ignoring therodynamics, reversibility seems asymptotically
sub-optimal (result with Ammer).
\item Proposed the study of {\emph{ultimate}} (physically optimal) models of
computation.
\item Presented the reversible 3-D mesh (with irreversibility at edges).
\item Conjectured some form of R3M is an asymptotically optimal model.
\item In physically realistic models, TP-reversible machines are faster per
unit area, by $\sqrt{d}$.
\item Also, faster per processor by a factor of $\Ndiam^{1/12}$ or even
$\Ndiam^{1/6}$.
\item No logical barriers to designing a reversible mesh processing element
using conventional semiconductor tech.
\item Future reversible devices projected to be highly advantageous for
supercomputing at reasonable scales.
\item To attain optimal efficiency, reversibility must be exposed at the
algorithms level.
\item Reversible instruction sets and programming languages are
straightforward.
\item Good reversible algorithms are different, but not significantly more
difficult to design.
\end{mitems}
\endslide
\note{(No notes on this slide yet.)}

\end{document}
