%----------------------------------------------------------------------
% The following LaTeX document constitutes Michael Frank's Ph.D. thesis
% proposal on the topic of ``Programming Reversible Computers.''
%----------------------------------------------------------------------

\documentstyle{article}
%----------------------------------------------------------------------
% First, some Friendly Neighborhood Macros...

% 
% The following hack (original version by Carl Witty) defines a \url
% macro, so that if you write a long URL as
%
%     {\url http://foo.bar.baz.bot/bim/bom/bam/buzz/biff.html}
%
% TeX will print the URL in typewriter font, and will know that it is
% allowed to break a line after any colon, slash, dot, hyphen, or
% @-sign in the URL. Without this, TeX will break lines containing
% URLs really poorly.  Unfortunately, this macro doesn't seem to work
% for allowing line breaks when it's used within footnotes, for
% unknown reasons.
%

{\catcode`\:=\active
\catcode`\/=\active
\catcode`\.=\active
\catcode`\-=\active
\catcode`\@=\active
\gdef\url{\tt\catcode`\/=\active
\catcode`\:=\active
\catcode`\.=\active
\catcode`\-=\active
\catcode`\@=\active
\def:{\char`\:\discretionary{}{}{}}%
\def/{\char`\/\discretionary{}{}{}}%
\def.{\char`\.\discretionary{}{}{}}%
\def-{\char`\-\discretionary{}{}{}}%
\def@{\char`\@\discretionary{}{}{}}}}

% 
% I don't know why something like the following macro wasn't built
% into TeX from the beginning.  Use this for standalone tildes, e.g.,
% in URLs or UNIX filenames.
% 

\def\tilde{\char126}

% End of macros.
%----------------------------------------------------------------------
% The document itself.

\title{Programming Reversible Computers\\ \vskip 0.2in
Ph.D. Thesis Proposal\\ \vskip 0.2in
(Concise Version for Submission)\\
$\ $Revision: 2.10 $\ $}

\author{Michael P. Frank\\
MIT AI Lab, Rm. 747\\
545 Technology Sq.\\
Cambridge, MA 02139\\
{\url http://www.ai.mit.edu/\tilde mpf}}

\date{Started August 27, 1996.\\
Concise version started December 5, 1996.\\
Revision$\ $Date: 1996/12/30 00:08:57 ${\rm GMT}$\\
Formatted \today.\\ \vskip 2.0in
A current version and the earlier,\\
more verbose version are available online at \\
{\url http://www.ai.mit.edu/\tilde mpf/proposal/proposal.html}}

\begin{document}
\maketitle
\newpage

\begin{abstract}
Reversibility offers tantalizing prospects for enabling computations
to take place in a denser, faster, and more energy efficient manner by
making the total heat production arbitrarily small.  Unfortunately,
known general-purpose reversible computing techniques can only reduce
energy dissipation by a small factor before incurring prohibitive
asymptotic increases in the space and/or time complexity of
algorithms.  Therefore it is still an open question whether the impact
of reversibility on the limits of general-purpose computing can ever
be very significant.

I propose, for my Ph.D. thesis research, to delve into this question,
and study in detail the relationship between the efficiency of a
computation, and the amount of irreversible information destruction it
performs.  This investigation will involve both theoretical and
experimental work.

On the theoretical side, I propose to formalize a new measure of
computational complexity in terms of the amount of information that a
computer erases, and determine where existing algorithms studied by
computer scientists fall on this spectrum.  I will attempt to develop
efficient reversible versions of these algorithms.  Some particular
algorithms can be made reversible without affecting their asymptotic
efficiency; I will describe these algorithms and attempt to
characterize how this sort of transformation might be applied more
generally.  Finally, I will study how the efficiency of algorithms is
affected if only partial reversibility is required.

On the experimental side, I propose to develop new abstractions,
programming techniques, languages, and compilers that will allow
programmers to easily write partially or fully reversible programs
that are as space and time efficient as can be provided for, given the
best known theoretical results to date.  To the degree that time
permits, I will write and compile example programs using this system,
simulate the programs' execution on a reversible computer
architecture, and experimentally measure the programs' efficiency and
degree of reversibility, to validate the theoretical predictions.

By this work, I hope to show that a requirement for reversibility is
not actually prohibitive for general-purpose computation, or at least,
to show that the amount of information erasure in a computation can be
greatly reduced (if not eliminated) without severely affecting its
efficiency.  If successful, this work will provide a crucial
foundation for the programming of possible future generations of
extremely high density computers, by allowing them to be
energy-efficient enough to operate at high speeds without suffering
severe cooling problems.

The proposed nominal period of research is one year, from December
1996 to December 1997.  Out of this, I propose to spend approximately
three months on theoretical work, five months on experimental work,
and four months writing and revising the thesis.  The period of
research may be extended by approximately one semester, if necessary.

\end{abstract}

\newpage
% Maybe later add tableofcontents on its own page here.

\section{Motivation for Reversible Computing}

For several decades, researchers studying the physics of computation
have known that physics, as it is currently understood, sets no
fundamental lower bound on the energy expenditure required for
computation, in the case where the computation is performed
reversibly, {\em i.e.}, without discarding information.

If, on the other hand, a bit of information is thrown away (meaning
that a computational state is reached that could have been reached
from either of two preceding states), then the second law of
thermodynamics requires an unavoidable energy dissipation of $k_BT\ln
2$, where $k_B$ is Boltzmann's constant and $T$ is the temperature of
the system.  Current digital circuit technologies actually dissipate
around six orders of magnitude more energy than this minimum whenever
a bit is erased, because bit erasure is done by dumping large numbers
of electrons from a high-voltage circuit node down to ground.  But
even this much larger energy dissipation can be avoided if the
computation is done reversibly, using adiabatic circuit techniques
such as SCRL \cite{you}.

The energy dissipated when bits are erased becomes a serious problem
as we extrapolate current trends in computer technology to ever-higher
component densities and speeds.  If every logic element erases a bit
(namely, its previous output) on every cycle, as typically occurs in
current digital circuits, the rate of heat production will eventually
exceed the heat flow capacity of the computing material, leading to
high temperatures and thermal noise that can prevent circuits from
functioning properly.  Active cooling, {\em e.g.}, with coolant
flowing through channels in the computing material, will eventually be
required, leading to severe logistical problems of its own.  Moreover,
in mobile computing devices, the total power and/or energy available
for computation is usually limited, and will thus restrict the total
rate and/or amount of computation that the device can perform.

Reversibility offers a way to deal with these problems.  If we can
avoid discarding most or all of the information that current computers
throw away, we can reduce the energy that is dissipated to heat,
allowing faster computation with a given rate of cooling, or more
computation for a given supply of energy.

Full reversibility also offers potential benefits unrelated to energy
usage, namely, for detecting errors, preventing tampering, and
diagnosis of software problems.  I will discuss these other benefits
in more detail in the thesis, but not in this short proposal.

\section{The Efficiency of Reversible Computing}

Theorists have shown that reversible computers can do anything that
normal computers can do, via the simple expedient of saving all the
information (such as intermediate results) that a normal computer
would throw away (\cite{ben1},
\cite{Toffoli-77}).  Unfortunately, this approach simply transforms
the problem of how to get rid of unwanted heat into the problem of how
to get rid of unwanted information.  The memory capacity of any
computer is limited, just like its heat capacity, and actively sending
all unwanted information outside the computer presents logistical
problems analogous to those involved in active cooling.  Therefore, we
would prefer to compute in a way that produces less of this ``garbage
data'' in the first place.

Bennett \cite{ben4} has shown that any algorithm can be transformed
into a form that produces garbage data at a rate that decreases
steadily as the algorithm runs, so that the total accumulation of
garbage data is only a logarithmic function of run time, and is thus
reasonable to store.  However, Bennett's technique suffers from the
drawback that the run time $t$ of the algorithm is multiplied by a
polynomial factor of $O(t^\epsilon)$; $\epsilon$ can be made
arbitrarily small, but only at the cost of exponentially increasing
space \cite{levine}.

\subsection{Important Open Questions}

Other techniques besides the above are known for transforming
arbitrary irreversible algorithms into reversible ones, but all known
techniques involve prohibitive asymptotic increases in either time
complexity, space complexity, or both.  However, no one has proven
that such inefficiencies are actually required to compute reversibly.
Moreover, no one has even thoroughly investigated the question of
whether we can compute efficiently if we relax the reversibility
constraint a little bit, and merely require that very little
information (rather than none at all) be discarded.  This suggests
several very interesting open questions:

\begin{enumerate}
\item Can we prove whether full reversibility actually requires greater
	asymptotic (ignoring constant factors) space and/or run time on
	some classes of problems?
\item Can we find and characterize other classes of problems or
	algorithms in which full
	reversibility does {\em not} decrease efficiency?
\item Can we describe how to reduce the amount of information erasure
	needed for a computation by arbitrarily large finite factors,
	without incurring asymptotically decreased efficiency?  How
	quickly does efficiency fall off as erasure decreases?
\item Can we organize and facilitate the programming process so
	that the theoretical techniques for providing reversibility
	(to various degrees) can be applied to make it practical
	to actually write fairly efficient programs for reversible
	computers?
\end{enumerate}

The first question is extremely difficult, since proving it would
involve showing that no reversible algorithm, out of the enormous
space of all possible algorithms, could solve a problem with a certain
efficiency; this sort of proof has historically been very difficult
for complexity theorists to come up with.  (Witness the unresolved
status of the ${\rm P}={\rm NP}$ question.)  I am sure I cannot do it,
but it is an interesting question to raise.

The second question might be more approachable, since I am aware of
certain classes of algorithms that can be transformed into a
reversible form without increasing either their asymptotic time or
space complexity.  However, this does not rule out the existence of a
better irreversible algorithm for solving the same problem.  Still, it
would be of interest to know what features of a given algorithm allow
it to be made reversible without incurring inefficiency.

I believe the third question can be answered straightforwardly, using
a restricted version of Bennett's full-reversibility transformation.
Other techniques such as traditional data compression might be used to
improve the answer even further.

The fourth question is practical rather than theoretical, and is very
straightforward since it is mostly involves just some software
engineering design work, rather than proving new and difficult
theorems.

These questions can be summed up as a single question: ``Can we make
it practical to program computers to compute highly efficiently while
requirements for reversibility become more stringent, up to and
including the limit of full reversibility?''  This question will be
crucially important if we ever wish our computing technology to
achieve extremely high computational speeds and densities, without
being limited by the need to export to the outside world all the
unwanted intermediate results that are generated, in some form such as
heat.

The thesis will explore this question, and the various components of
it that are listed above.

\section{Research Plan}

The thesis work can be subdivided into two major parts: the
theoretical work, and the practical work.  I will start with the
theoretical work, since in the course of it I might discover some new
techniques and algorithms that could be applied in the practical work.

\subsection{Theory of Reversible Computational Complexity}

The aim of the theoretical work will be to develop the beginnings of a
theoretical study of computational complexity that accounts for
reversibility, and measures it by counting the amount of information
that is erased during a given procedure (this is zero for a
fully-reversible computation).  We might call this the ``thermodynamic
complexity'' of an algorithm, as opposed to its time or space
complexity.  Because of the $k_BT\ln 2$ energy dissipation per bit
erased, the thermodynamic complexity of an algorithm is the
fundamental measure of the minimum amount of energy required to
execute the algorithm.

As is usual with computational complexity, we will characterize
thermodynamic complexity in a way that ignores constant factors, since
the exact number of bits erased internally during a particular
operation are assumed to vary depending on the particular computer
architecture being used.  However, we will assume that the
architecture provides a universal set of reversible computational
primitives which all incur a thermodynamic cost of zero, that is, they
are implemented in a way that does not erase any bits internally.  The
Pendulum architecture designed by Carlin Vieri \cite{vieri} is an
example of such an architecture.  In fact, Pendulum does not provide
any irreversible primitives, and is not meant to be used to program
partially-reversible algorithms.  In contrast, we will assume an
architecture that also provides an ``{\sc erase}'' instruction that
erases a fixed-size unit of information at a thermodynamic cost that
is bounded by a machine-specific constant.  The zero-cost reversible
primitives, together with the {\sc erase} instruction, constitute a
sufficient language for describing arbitrary algorithms and analyzing
their thermodynamic complexity.

My plan for my study of thermodynamic complexity is as follows:

\begin{enumerate}
\item For a number of practical and interesting algorithms from
traditional computer science (e.g., from \cite{CLR}), such as
algorithms for sorting, searching, and optimization problems,
I will determine the algorithms' thermodynamic complexity when they are
translated to the form of reversible primitives plus {\sc erase} in
the most straightforward way.  I expect most of the traditional
algorithms will constantly perform irreversible operations, and thus
have thermodynamic complexity equal to their time complexity.
\item I will attempt to find ways to modify the existing algorithms in ways
that reduce their thermodynamic complexity without increasing their
asymptotic time or space complexity, or else increasing it as little as
possible.
\item I already know some examples of algorithms that can be transformed
into an equally-efficient reversible form.  I will describe these
algorithms and attempt to characterize more generally what it is about
these algorithms that allows this transformation to be done, and apply
that characterization to try to translate other algorithms to an
efficient reversible form.
\item I will study and describe the existing very general techniques
such as Bennett's for translating arbitrary algorithms into a
less-efficient but reversible form.  I will attempt to improve on
these techniques, but I do not anticipate finding a better
transformation for achieving total reversibility.  However, I will
describe variations on these techniques that achieve greater space and
run-time efficiency by incurring a non-zero, but small, cost in
thermodynamic complexity.
\end{enumerate}

I plan to spend only three months, January through March of 1997,
exploring these issues.  Some of the theoretical questions I am asking
are very difficult, and so I will not expect to be able to answer all
of them to my satisfaction.  It will be necessary to cut short the
time spent on them, in order to avoid the risk of using up all the
time available for the thesis on what might be an impossibly difficult
task that may produce no new hard results.

However, I expect that even if all I can do is to formalize the
questions, and describe particular examples of efficient reversible
algorithms, it will still be worth the effort, and may provide
important insights necessary for more far-reaching future work.

\subsection{Programming Reversible Computers}

The theoretical study of the efficiency of reversible computing is
certainly very interesting, but it's difficult to make progress on.

In contrast, the accompanying area, of how to apply the known theory
to actually program reversible computers effectively, is ripe for
advancement.  My plan for my work in this area will involve the
following steps, in approximately the following order:

\begin{enumerate}
\item Define a high-level programming language that leverages off of
appropriate new reversible programming abstractions in order to make
it easy to describe algorithms having arbitrary degrees of
reversibility, up to and including full reversibility.
\item Demonstrate the expressiveness of the language by writing
programs in it that implement the partially-to-fully reversible
algorithms that will have already been studied in the theoretical
work.
\item Write a compiler that can translate programs in the high-level
language into instructions for a processor architecture that supports
reversible computing, such as Pendulum or something like it.
\item Enable the compiler to optionally apply its own transformations for
automatically reducing the thermodynamic complexity of the program as
part of the compilation process.  These transformations might include
Bennett's technique, traditional data compression, or any new
techniques that I might have discovered in my theoretical work.  The
user of the compiler should be able to specify how he wishes to trade off
thermodynamic complexity versus space and time complexity.
\item Compile my various example programs using a variety of different
automatic transformations for reducing thermodynamic complexity.
\item Execute the compiled programs on a simulated reversible
processor.  Check the correctness of the results to validate the
compiler.  Measure the actual time, space, and thermodynamic
complexities of the executions to verify the theoretical predictions.
\item Compare the thermodynamic, time, and space efficiency of
programs that are hand-designed to be highly reversible against that
of nominally irreversible programs whose thermodynamic efficiency is
optimized by the compiler using the general, automatic techniques.
\end{enumerate}

I intend to spend approximately five months, from April through August
of 1997, on this experimental work.  If it seems to be moving too
slowly, I can always limit the ambitiousness of the compiler, reduce
the number of example programs being explored, or extend the period of
research a few months.  Since this experimental side of the research
mainly consists of just software design and programming, as opposed to
an all-or-nothing struggle to prove a possibly false theorem, I have
high confidence in the success of the work, so there is less risk
involved in extending the amount of time spent on it, if necessary.
However, I would very much like to wrap it up by, at latest, the end
of the year, if not in August as currently planned.

\subsection{Thesis Writeup}

Finally, after the above-mentioned theoretical studies and
experimental work have been completed, I will spend the Fall semester
writing up the results in the thesis document.  In addition to
relating the work done as described above, the thesis document will,
as time permits, discuss a variety of related issues, many of which
were mentioned in the earlier, longer version of this proposal
(available at {\url http://www.ai.mit.edu/\tilde
mpf/proposal/proposal.html}).

For example, there are possible applications of reversibility for
error detection, debugging, and auditability which should be
discussed.  There are also questions about how to manage multiple,
inter-communicating reversible processes within a multiprocessing
framework, and about how to relate reversibility to rollback in
transactional database systems.

Also, there is the very interesting issue of how to extend
computational complexity theory to incorporate facts of physical
reality other than just the second law of thermodynamics, such as,
notably, the finiteness of the speed of light (which traditional
complexity theory conveniently ignores by assuming that any of an
unlimited number of RAM cells can be accessed in constant time).  The
longer version of the proposal mentions numerous other interesting
issues as well.

However, all these tangential discussions will be optional, and will
be undertaken only after the main core of the thesis research,
proposed here, has been successfully completed and documented.  If no
time remains to pursue these other directions, the coverage of these
topics in the thesis will be limited to the short discussions already
written up in the longer version of this proposal.

\section{Schedule Summary}

The following chart summarizes the planned schedule for the thesis
work.

\begin{verbatim}
1997

Jan \ Theoretical Studies---   - Characterize known algorithms
Feb  > Reversible Complexity   - Invent new algorithms
Mar /  Theory                  - Generalize techniques
Apr \ Experimental Studies---  \_ Design reversible language,
May  | Programming             /    write compiler.
Jun  |                         \ Implement example programs,
Jul  |                          >  run them, measure results.
Aug /                          /
Sep \ Thesis Writeup           - First draft.
Oct  | and Revision            - Second draft.
Nov  |                         - Optional extra discussion.
Dec /                          - Final draft, defense.
\end{verbatim}

\bibliography{../../RevComp/bib/refs,prop}
\bibliographystyle{plain} 

\end{document}
