Mike's Reversible Computing Page

What's Reversible Computing?

This means computing in such a way that it always remains possible to reconstruct the previous state of the computation from the current state. (Follow the above link for more details.) Doing this enables the use of thermodynamically reversible, energy-recovering circuit techniques.

See this link for a more recent, 7-paragraph overview.

The MIT Reversible Computing Project

The MIT Reversible Computing project (a.k.a. the Pendulum Project) aims to build a working electronic CPU that is capable of totally reversible operation, and that can take advantage of its reversibility to function using vastly less energy per operation than traditional circuits. Our approach may enable new computational applications in energy-limited environments within the next decade.

For the longer term, we argue that the laws of physics imply that the most efficient computers that can physically exist will necessarily be composed out of reversible or nearly-reversible processing elements, and that therefore it is important for the future success of computer science to study the design and programming of these reversible architectures.

Project Status

The Pendulum chip has been (essentially) completed, the MIT reversible computing project's students have all graduated, and its faculty are currently focusing on other projects. However, graduated student Michael Frank is continuing the project's work in his faculty position at the Computer & Information Science & Engineering department at the University of Florida.

Press

There was an article about our project on the front page of the June 15, 1999 science section of the New York Times.

Mike's Work on the Project

Here are some things that I've done (or helped do) relating to reversible computing. I have studied both the high-level impact of reversibility--on scalability, complexity theory, programming languages, operating systems, and applications--and also the low-level end of circuit analysis, instruction sets and circuit designs as well.

These are listed in reverse chronological order, most recent work first.

New Reversible & Quantum Computing Group Homepage
My Research Proposals: Mostly relating to reversible computing
Reversible Schrödinger wave equation simulator: As described in Appendix E of my working manuscript. A bit more work has been done on it recently.
Physical Limits of Computing: Web site for my research survey course taught at the University of Florida, Spring 2000. Includes extensive reading lists, lecture notes, and slides.
Reversibility for Efficient Computing: Working manuscript derived from my my Ph.D. thesis, Dec. '99. Used as a course reader for my Physical Limits of Computing course. Slated to evolve into an MIT Press book.
Dynamic Optimization of Semi-Adiabatic Power-Managed Architectures: Pre-proposal submitted to DARPA's Power-Aware Computing and Communication program, October '99. (Postscript format.)
Research and Teaching Plan: My preliminary proposal to start up a new, long-term research and educational program, to further study the theory and practical application of reversible computing and related techniques, and to train graduate student researchers in areas such as low-power computing, the thermodynamics of large-scale parallel computing, and future high-performance computing technologies.
Reversibility for Efficient Computing -- Now finished! (Finally!): The final draft of my Ph.D. thesis, reporting on most of my reversible computing research, including some newer results not otherwise reported in any of the below. Also included are the slides from my thesis defense presentation.
JANUS, Lutz & Derby's Reversible Language: Recently, I found out that Chris Lutz and Howard Derby created the first known high-level reversible language, called JANUS, in 1982 at Caltech. Here is an HTML reproduction of a letter describing the language that Lutz wrote to Rolf Landauer in 1986.
Table of MEMS Switch Characteristics: Collected from the MEMS community for use in my research. I briefly considered MEMS switches or relays as a possible device technology for adiabatic computation, but concluded that the devices are currently still much too large to be competitive with adiabatic CMOS for overall computational density.
Translation of Lecerf '63 article.: In 1963, Yves Lecerf created the first formal description of a simulation of arbitrary Turing machines on reversible ones. Unfortunately, he wrote it in French. (What a maroon!) With the help of the Altavista Translation Service, I have translated this historic paper into English.
Optimal Voltages for CMOS Circuits: This memo derives the optimal power-supply voltage for heat-limited high-performance ordinary irreversible CMOS circuits. The work is not finished, but already we can see that aggressively-pipelined, dense, locally-connected circuits with high activity factors require supply voltages that are several times lower than is standardly suggested, in order to achieve the maximum performance/price that is possible.
Ultimate Theoretical Models of Nanocomputers: This is a paper and talk presented at Nanotech '97 which discusses asymptotic scaling issues and compares the performance of a variety of reversible and irreversible technologies.
The R Programming Language and Compiler: This document describes the current state of the reversible high-level language I am working on, and the compiler that translates programs from that language into our reversible machine instruction set.
Reversibility in optimal scalable computer architectures: In this paper and talk, to be presented at UMC-98, we show that the asymptotically fastest possible computers must be based on reversible primitives, and we describe one version of the fastest possible architecture.
Modifications to PISA architecture to support guaranteed reversibility and other features: A unfinished new working memo. Contains some useful info though.
Separations of reversible and irreversible space-time complexity classes: If abstract nonphysical reversible and irreversible computers can both access a black-box input, the irreversible models prove to be fundamentally more powerful. This may imply that some of the most ambitious proposed computer architectures cannot be efficiently implemented within our micro-reversible universe. Instead, the corresponding reversible designs may ultimately yield the most powerful computers that are physically possible.
Physically-Motivated Models of Computation for Complexity Theory: This memo proposes models of computation that are conjectured to represent the true capabilities of physics, and thus constitute an appropriate basis for the study of algorithms and computational complexity in a way that is not based on an artificial model of computation that may be asymptotically more or less powerful than real computers can possibly be.
Voltage Scaling and Limits to Energy Efficiency for CMOS-based SCRL.: This is a working memo (not yet finished) that analyzes how the energy/operation of the SCRL adiabatic circuit technique scales with speed, threshold, and temperature, and how it compares to standard CMOS.
Flattop: The First Fully Adiabatic Computer: We recently designed and fabricated a fully-adiabatic chip implementing the Billiard Ball Model Cellular Automaton, a simple reversible system capable of universal computation.
Programming Reversible Computers.: My Ph.D. thesis proposal, submitted and approved.
Tick: The First Reversible CPU.: We recently created a chip that is, as far as we know, the first-ever fabricated CPU that executes a fully reversible instruction set. The chips worked in simulation, but unfortunately, when tested they were found to be defective, due most likely to problems with our design software. The above document is a preliminary report on Tick's design, in postscript format, 8MB long due to detailed layouts.
Low-Energy Computing for Implantable Medical Devices.: I delivered this talk to an audience of our colleagues in MEDG on 2/21/96.
Quantum Computing studies.: This page conveys the results of my studies on this topic for my area exam in Feb. '96. Quantum computing is a topic that is closely related to reversible computing.
Bibliography on Reversible Computing.: A shared resource in our project. This is actually a fairly old version; I need to put the latest one online sometime.
Memo on reversible control flow instructions.: This is an old working memo I wrote which outlines an early version of the reversible control flow instructions used in our instruction set architecture. It is flawed and badly needs revision, so please don't quote it or redistribute it. See chapter 8 of my thesis for a more up-to-date discussion of most of the same issues.

Some Interesting Related Conferences

Upcoming:

Past:

SPAA '98.: Tenth Annual ACM Syposium on Parallel Algorithms and Architectures.
ISCA '98.: 25th Annual International Symposium on Computer Architecture.
UMC '98.: First International Conference on Unconventional Models of Computation.
Nanotech '97.: Fifth Foresight Conference on Molecular Nanotechnology.
FOCS '97.: 38th IEEE Symposium on Foundations of Computer Science.
CCC '97.: Twelfth Annual IEEE Conference on Computational Complexity.
PhysComp '96.: Fourth Workshop on Physics and Computation.
ISLPE&D '96.: International Symposium on Low Power Electronics and Design.

[At some point the information above should perhaps be merged into the home page created for our project earlier by Carlin.]

Mike Frank, 6/9/99