
%Date: Tue, 24 Mar 92 
\documentstyle[12pt]{article}
% HORIZONTAL MARGINS
% Left margin 1 inch (0 + 1)
\setlength{\oddsidemargin}{0in}
% Text width 6.5 inch (so right margin 1 inch).
\setlength{\textwidth}{6.5in}
% ----------------
% VERTICAL MARGINS
% Top margin 0.5 inch (-0.5 + 1)
\setlength{\topmargin}{-0.5in}
% Head height 0.25 inch (where page headers go)
\setlength{\headheight}{0.25in}
% Head separation 0.25 inch (between header and top line of text)
\setlength{\headsep}{0.25in}
% Text height 9 inch (so bottom margin 1 in)
\setlength{\textheight}{9in}

\input{urls.sty}

\begin{document}
\thispagestyle{empty}
\begin{center}
\begin{verbatim}
******************************************************************************
**   THESIS DEFENSE    THESIS DEFENSE    THESIS DEFENSE    THESIS DEFENSE   **
******************************************************************************
\end{verbatim}
\bigskip
{\Large \bf Reversibility} \\
{\Large \bf for}\\
{\Large \bf Efficient Computing}\\
\bigskip				   
\bigskip				   
{\Large Michael P. Frank}\\
\bigskip
\begin{tabular}{||l|l||}
\hline
{\bf DATE:}   &   Mon.\ May 3rd, 1999\\
{\bf TIME:}   &   10:45am refreshments\\
              &   \& 11am seminar\\
{\bf PLACE:}  &   NE43 (545 Tech. Sq.)\\
	      &   8th floor playroom\\
\hline
\end{tabular}
\end{center}                     

I review the ultimate limits that fundamental physics places on information
processing, with particular attention to the implications of
thermodynamics.  I advocate the study of models of computation that give
the best asymptotic scaling behavior that is physically possible.  I argue
that one such model will consist of 3-D meshes of a class of
{\emph{reversible}} computing elements.  I show that such meshes scale
better than {\emph{any}} physically possible architecture based on
traditional irreversible computing techniques, by factors that grow
polynomially with machine size.

Next, I review reversible computing techniques based on existing
semiconductor technology, and present a proof-of-concept mesh processor
based on these techniques.  With only present-day technology, I project
that reversible techniques would not begin to improve supercomputing
performance/cost until a multi-billion-dollar cost level.  But reversible
techniques can still be useful in the near term, in energy-limited
applications.

In the longer term, device technology improvements (such as
lower-resistance switches) will only improve the ``reversible advantage''
in supercomputing.  I review a number of proposals that have been made for
nano-scale logic devices.  Under some of these proposals, we can show that
any computer larger than a few microns to millimeters across can be made to
run faster if it is mostly reversible.

Finally, I discuss issues in the design of instruction sets, programming
languages, and algorithms for reversible machines.  In general, to attain
optimal asymptotic efficiency, it seems that the underlying reversibility
of physics must be exposed at every level, all the way up to the algorithm
design level.  I show how to choose reversible primitives at each level so
as not to reduce the asymptotic efficiency that can be achieved.  I show an
example reversible language I created.  Finally, I list straightforward
reversible algorithms for a variety of problems, and show a reversible
simulation of basic quantum mechanics.

\vspace{0.25in}
\noindent
Committee: Tom Knight (Advisor), Norm Margolus, Gill Pratt, Gerry Sussman.

\vspace{0.25in}
\noindent
For related materials, see {\url
http://www.ai.mit.edu/~mpf/thesis/defense.html}.

\begin{center}
\begin{verbatim}
******************************************************************************
**   THESIS DEFENSE    THESIS DEFENSE    THESIS DEFENSE    THESIS DEFENSE   **
******************************************************************************
\end{verbatim}
\end{center}
\end{document}

