Reversibility for Efficient Computing
Manuscript based on Ph.D. Thesis

Copyright ©1999 Michael P. Frank. All rights reserved.

Abstract:

Today's computers are based on irreversible logic devices, which have been recognized as being fundamentally energy-inefficient for several decades. In the last few years, alternative reversible logic device technologies have improved rapidly, and are near the threshold of practicality. This thesis examines how the use of such reversible technologies can improve computational efficiency.

We show that when the effects of energy dissipation are taken into account, approximately reversible machines of physical diameter D are capable of asymptotically higher throughput than diameter-D irreversible machines, by a factor of order D1/2. Also, reversible machines of mass M are both faster and more cost-efficient than mass-M irreversible machines by a factor of order M1/18. These asymptotic factors are expected to translate into real benefits for large-scale supercomputing in the fairly near term, and in the long term for computers at every scale.

The inclusion of real physical laws in our computational model was crucial for obtaining our results. Underscoring this point, we prove rigorously that in an (unrealistic) nonphysical model of computation, adding reversibility would strictly decrease asymptotic efficiency---exactly the wrong conclusion as far as physical reality is concerned.

Additionally, we study how to design asymptotically optimal computers using the ``adiabatic'' reversible electronic logic technology that is already available today. We describe an exemplar universal parallel reversible processor that we recently fabricated, and compare it with a reversible version of a more traditional RISC-style uniprocessor.

Finally, we describe how to effectively program reversible computers. We give an instruction set architecture and a compiled high-level language for coding efficient reversible algorithms, and show a variety of example algorithms, including efficient reversible sorting, searching, arithmetic, matrix, and graph algorithms, plus, as an example application, a linear-time, zero-garbage reversible algorithm for simulating the Schrödinger wave equation of quantum mechanics.

The Entire Document (12/20/99, 430 pp.):

Individual chapters:

Here we have the document broken into pieces, for mercy on one's printer. To save even more trees, you might want to print at 4 pages per page (psnup -4 on Unix); it's still readable if you have good eyes and a high-DPI printer.

Chapter Pages Formats
  • Frontal matter (title page, abstract, table of contents, etc.)
18 pp. PS (550 kB) | Gzipped PS (87 kB) | PDF (1.6 MB) | Gzipped PDF (330 kB)
  • Chapter 1. Introduction & Background
12 pp. PS (370 kB) | Gzipped PS (68 kB) | PDF (1.6 MB) | Gzipped PDF (350 kB)
  • Part I. Foundations of reversible computing.
    • Chapter 2. Physical constraints on computation
16 pp. PS (640 kB) | Gzipped PS (120 kB) | PDF (2.7 MB) | Gzipped PDF (620 kB)
    • Chapter 3. Reversible computing theory
42 pp. PS (1.1 MB) | Gzipped PS (230 kB) | PDF (7.5 MB) | Gzipped PDF (1.7 MB)
    • Chapter 4. Quantum Computing
42 pp. PS (6.8 MB) | Gzipped PS (223 kB) | PDF (234 kB) | Gzipped PDF (145 kB)
    • Chapter 5. Ultimate physical models of computation
14 pp. PS (390 kB) | Gzipped PS (73 kB) | PDF (2.2 MB) | Gzipped PDF (460 kB)
    • Chapter 6. Reversibility and physical scaling laws
24 pp. PS (800 kB) | Gzipped PS (150 kB) | PDF (3.8 MB) | Gzipped PDF (850 kB)
  • Part II. Engineering reversible computational systems.
    • Chapter 7. Adiabatic circuits
66 pp. LaTeX (170 kB) | DVI (240 kB) | PS (2.3 MB) | Gzipped PS (400 kB) | PDF (11 MB) | Gzipped PDF (2.3 MB)
    • Chapter 8. Alternative reversible device technologies
10 pp. LaTeX (24 kB) | DVI (30 kB) | PS (270 MB) | Gzipped PS (50 kB) | PDF (1.2 MB) | Gzipped PDF (270 kB)
    • Chapter 9. Design & programming of reversible computers
24 pp. LaTeX (58 kB) | DVI (75 kB) | PS (2.2 MB) | Gzipped PS (160 kB) | PDF (4.4 MB) | Gzipped PDF (770 kB)
    • Chapter 10. Alternative applications for reversibility
8 pp. LaTeX (18 kB) | DVI (23 kB) | PS (280 kB) | Gzipped PS (49 kB) | PDF (980 kB) | Gzipped PDF (210 kB)
    • Chapter 11. Future work & conclusion
8 pp. LaTeX (18 kB) | DVI (24 kB) | PS (280 kB) | Gzipped PS (51 kB) | PDF (1.0 MB) | Gzipped PDF (220 kB)
  • Part III. Appendices.
    • Appendix A. Flattop processor schematics and layout
8 pp. LaTeX (8.2 kB) | DVI (11 kB) | PS (2.8 MB) | Gzipped PS (400 kB) | PDF (18 MB) | Gzipped PDF (3.3 MB)
    • Appendix B. The Pendulum instruction set architecture (PISA)
20 pp. LaTeX (30 kB) | DVI (41 kB) | PS (420 kB) | Gzipped PS (70 kB) | PDF (2.1 MB) | Gzipped PDF (460 kB)
    • Appendix C. The R reversible programming language
16 pp. LaTeX (29 kB) | DVI (39 kB) | PS (460 kB) | Gzipped PS (81 kB) | PDF (2.1 MB) | Gzipped PDF (460 kB)
    • Appendix D. The R language compiler
66 pp. LaTeX (130 kB) | DVI (160 kB) | PS (650 kB) | Gzipped PS (130 kB) | PDF (8.2 MB) | Gzipped PDF (1.7 MB)
    • Appendix E. Reversible Schrödinger wave simulation
30 pp. LaTeX (61 kB) | DVI (74 kB) | PS (470 kB) | Gzipped PS (93 kB) | PDF (3.2 MB) | Gzipped PDF (650 kB)
    • Appendix F. Symbols, units, and constants
4 pp. LaTeX (6.8 kB) | DVI (11 kB) | PS (180 kB) | Gzipped PS (32 kB) | PDF (290 kB) | Gzipped PDF (65 kB)
  • Back matter (bibliography, index)
16 pp. LaTeX (2.1 kB) | DVI (43 kB) | PS (290 kB) | Gzipped PS (63 kB) | PDF (2.4 MB) | Gzipped PDF (550 kB)

Thesis Defense Talk (delivered 5/3/99)

Michael Frank <mpf@ai.mit.edu>

Last modified: Sat May 22 16:09:30 EDT