Reversibility for Efficient Computing
(Mike's Ph.D. Thesis Defense)

Abstract:

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 be 3-D meshes of some class of reversible computing elements. I show that such meshes scale better than any physically possible machine based on traditional irreversible computing techniques, by factors that are polynomial in the machine size.

Next, I review reversible computing techniques based on semiconductor technology, and present a proof-of-concept mesh processor based on these techniques. With present-day technology, I project that reversible techniques do not improve supercomputing performance/cost below a multi-billion-dollar cost level. But reversible techniques can still be useful in the near-term, in low-energy 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 will be faster if it is mostly reversible.

Finally, I discuss issues in the design of processor 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. I show how the primitives at each level should be chosen so as not to reduce the asymptotic efficiency that can be achieved. I illustrate straightforward reversible algorithms for a variety of problems, including a reversible simulation of quantum mechanics.

You can read the thesis itself here.

My other related work can be found here.

Slides for the defense talk:

These were the actual slides presented in the defense. Notes are available for some slides in the LaTeX source.

Auxilliary slides:

These were mainly for more detailed explanations in the audience were to ask for them. Notes are available for some slides in the LaTeX source.

Original thesis defense announcement:

Text | LaTeX | DVI | PS
Michael Frank
Last modified: Thu May 6 12:45:32 EDT