%======================================================================
% front.tex
%
% Frontal matter that goes at the start of the dissertation: title page,
% abstract, table of contents, etc.
%======================================================================

\def\draftid{$\ $Id: front.tex,v 1.7.2.14.2.11 1999/05/21 19:41:28 mpf Exp $\ $}

%----------------------------------------------------------------------
% My Personal Style of Title Page.
% Don't turn this page in!
%----------------------------------------------------------------------

\thispagestyle{empty}
%::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
% This page is numbered -1 so that its numbering is consistent with it
% being 2 pages (1 page front & back) prior to page 1, which must be the
% implicit (though not necessarily printed) number of the official title
% page according to MIT guidelines.
%::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
\setcounter{page}{-1}
\begin{centering}
\parskip .5in
\LARGE
	       {\bf Reversibility for Efficient Computing}\\
\vskip 0.2in\large
			      (Ph.D. Thesis)\\
\vskip 0.4in\LARGE
			    Michael P. Frank

\large			  MIT AI Lab, Rm.\ 821\\
			   545 Technology Sq.\\
			   Cambridge, MA 02139\\
		     {\url http://www.ai.mit.edu/~mpf}

			       Final Version\\
		       	       May 14, 1999\\
\vfill
			Available online through\\
	  {\url http://www.ai.mit.edu/~mpf/thesis/phdthesis.html}
\newpage
\end{centering}
\thispagestyle{empty}

%-----------------------------------------------------------------
% Official Title Page.

\cleardoublepage % Make sure real thesis starts on the front of a page.
\setcounter{page}{1} % Reset page counter to 1, as required.

	       \title{Reversibility for Efficient Computing}			

		      \author{Michael Patrick Frank}

	     \prevdegrees{S.B., Stanford University (1991) \\			
	    S.M., Massachusetts Institute of Technology (1994)}			

  \department{Department of Electrical Engineering and Computer Science}	
		       \degree{Doctor of Philosophy}
			  \degreemonth{May}
			     \degreeyear{1999}
		      \thesisdate{May 14, 1999}

		    \supervisor{Thomas F. Knight, Jr.}				
			{Senior Research Scientist}

% This is the department committee chairman, not the thesis committee chairman
			\chairman{Arthur C. Smith}				
	  {Chairman, Departmental Committee on Graduate Students}

\maketitle
\index{title page}
\index{this thesis!author of}\index{author}
\index{this thesis!title of}\index{title}
\index{Frank, Michael Patrick}
\index{Frank, Michael Patrick!previous degrees of}
\index{Stanford University}
\index{MIT}
\index{this thesis!department of}
\index{this thesis!department of!chairman of}
\index{Knight, Jr., Thomas F.}
\index{Knight, Jr., Thomas F.!title of}
\index{this thesis!advisor for}
\index{this thesis!advisor for!position of}
\index{this thesis!completion date}
\index{Smith, Arthur C.}
\index{this thesis!frontal material of|(}

%---------------------------------------------------------------------------
% Abstract page.
\begin{abstractpage}								\index{abstract}\index{this thesis!abstract of}
Today's computers are based on {\emph{irreversible}} logic devices, which
have been\index{logic devices, irreversible} known to be fundamentally
energy-inefficient for several decades.  Recently, alternative
{\emph{reversible}} logic \index{logic devices, reversible} technologies
have improved rapidly, and are now becoming practical.  

In traditional models of computation, pure reversibility seems to decrease
overall computational efficiency; I provide a proof to this effect.
However, traditional models ignore important physical constraints on
information processing.

This thesis gives the first analysis demonstrating that in a realistic
model of computation that accounts for thermodynamic issues, as well as
other physical constraints, the judicious use of reversible computing can
strictly {\emph{increase}} asymptotic computational efficiency, as machine
sizes increase.  I project real benefits for supercomputing at a large (but
achievable) scale in the\index{supercomputing} fairly near term.  And with
proposed future computing technologies, I show that reversibility will
benefit computing at all scales.

Next, the thesis demonstrates that reversible computing techniques do not
make computer design much more difficult.  I describe how to design
asymptotically efficient processors using an ``adiabatic'' reversible
electronic logic technology that can be built with today's
\index{circuits!adiabatic} microprocessor fabrication processes.  I
describe a simple universal reversible parallel processor chip that our
group recently fabricated, and a reversible instruction set for a more
traditional RISC-style uniprocessor.
\index{RISC}

Finally, I describe techniques for programming reversible computers.  I
present a high-level language and a compiler suitable for
\index{reversible!languages} coding efficient reversible algorithms, and
I describe a variety of example algorithms, including efficient reversible
sorting, searching, arithmetic, \index{algorithms} matrix, and graph
algorithms.  As an example application, I present a linear-time,
constant-space reversible program for simulating the
\index{reversible!simulations of physics} Schr\"odinger wave equation of
quantum mechanics.\index{Schrodinger equation@Schr\"odinger
equation}\end{abstractpage}
\index{this thesis!abstract of}

%----------------------------------------------------------------------
% Acknowledgments page.

\thispagestyle{plain}

\section*{Acknowledgments}							\index{acknowledgments}

First and foremost, I am enduringly grateful to my advisor Tom Knight and	\index{Knight, Jr., Thomas F.}\index{this thesis!advisor for}
also to Norm Margolus, for taking me into their fold, for their extensive	\index{Margolus, Norman H.}\index{this thesis!committee for}
and wise guidance in all areas of this research, for the many things I
learned from them, and for providing an exceptionally supportive and
stimulating work environment.  Thanks very much also to the other readers
Gill Pratt and Gerry Sussman, for kindly agreeing to serve on my thesis		\index{Pratt, Gill}
committee and lend their expertise to the evaluation of this work.		\index{Sussman, Gerald J.}

I would also like to thank the Pendulum group's head graduate student,		\index{Pendulum!group}
Carlin Vieri, for inventing the Pendulum architecture, which provided the	\index{Vieri, Carlin}
context for much of this work; for taking it upon himself to do most of the	\index{Pendulum!architecture}
project's administrative chores; and for the fun we had working
together on the nuts and bolts of various aspects of the project such as
the Pendulum ISA and the {\FlatTop} chip.  (Also, thanks for all the
Nolios!)
	\index{Pendulum!ISA}\index{FlatTop@\FlatTop!collaborators}
	\index{Nolio pizza}\index{this thesis!fuel for|see{Nolio pizza}}

I should also thank a number of other MIT students: Matt DeBergalis created
\index{DeBergalis, Matthew}\index{collaborators} many helpful software
tools, such as the Pendulum assembler and
emulator. \index{Pendulum!assembler}\index{Pendulum!emulator} Josie Ammer
assisted with chip design, and made important contributions to the theory
and algorithms work.  Scott Rixner and Nicole Love were my primary
\index{Rixner, Scott}\index{Love, Nicole} design partners on the Tick and
{\FlatTop} processors, respectively.  Matt \index{Tick!collaborators}
Becker often popped into my office for a friendly greeting and an
\index{Becker, Matt} interesting conversation.

Prof.~Michael Sipser deserves thanks for his informal but very helpful
\index{Sipser, Michael} guidance during the development of the proof
in~\S\ref{sec:separation}.  I am also grateful to Alain Tapp and Pierre
McKenzie of the University of \index{Tapp, Alain}\index{McKenzie, Pierre}
Montreal, for providing much helpful feedback on that result, and for
\index{Montreal, University of} inviting me to visit their lab.  Thanks
also to Prof.~Tom Leighton for \index{Leighton, F. Thomson} communicating
the reversible shortest-path algorithm, and to both him and Prof.~Charles
Leiserson for feedback on the scaling results of \index{Leiserson, Charles}
chapter~\ref{ch:scaling}.

Finally, I would like to thank Carl R.~Witty and Warren D.~Smith {\ed{and
any other commentators}} for helpful editorial comments on drafts of this
document, my family and my wife Lori for their love, and all my friends
throughout my years at MIT for their companionship and encouragement.

\vfill
\noindent
This research was supported by DARPA (the Defense Advanced Research		\index{funding source}\index{DARPA}
Projects Agency of the United States of America) as part of the Scalable	\index{United States government}
Computing Systems research program {\cite{DARPA-program}}, under contract	\index{Scalable Computing Systems research program}
number {\mbox{DABT63-95-C-0130}}.						\index{contract number}

%----------------------------------------------------------------------
% Dedication.

\newpage
\thispagestyle{plain}
\vspace*{2in}
\emph{to my father, Patrick Gene Frank}
\index{dedication}\index{Frank, Patrick}\index{Frank, Michael!father of}

%----------------------------------------------------------------------
% Table of Contents, Lists of Figures & Tables

\cleardoublepage
\thispagestyle{plain}
\index{table of contents|(}
\tableofcontents
\index{table of contents|)}

\cleardoublepage
\thispagestyle{plain}
\index{list of figures|(}
\listoffigures
\index{list of figures|)}

\cleardoublepage
\thispagestyle{plain}
\index{list of tables|(}
\listoftables
\index{list of tables|)}

%----------------------------------------------------------------------
% List of Symbols

% Comment this out if I don't complete it before turn-in.
% \input{symbols.tex}
\cleardoublepage

\index{this thesis!frontal material of|)}
