Browse Prior Art Database

Reversibility for efficient computing

IP.com Disclosure Number: IPCOM000128124D
Original Publication Date: 1999-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 9 page(s) / 28K

Publishing Venue

Software Patent Institute

Related People

Frank, Michael Patrick: AUTHOR [+3]

Related Documents

http://theses.mit.edu:80/Dienst/UI/2.0/Describe/0018.mit.theses/1999-164: URL

Abstract

Today's computers are based on irreversible logic devices, which have been known to be fundamentally energy-inefficient for several decades. Recently, alternative reversible logic 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 increase asymptotic computational efficiency, as machine sizes increase. I project real benefits for supercomputing at a large (but achievable) scale in the 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 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. Finally, I describe techniques for programming reversible computers. I present a high-level language and a compiler suitable for coding efficient reversible algorithms, and I describe a variety of example algorithms, including efficient reversible sorting, searching, arithmetic, matrix, and graph algorithms. As an example application, I present a linear-time, constant-space reversible program for simulating the Schrodinger wave equation of quantum mechanics.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 17% of the total text.

Page 1 of 9

 This record is the front matter from a document that appears on a server at MIT and is used through permission from MIT. See http://theses.mit.edu:80/Dienst/UI/2.0/Describe/0018.mit.theses/1999-164 for copyright details and for the full document in image form.

Reversibility for Efficient Computing

by

Michael P. Frank
S.B., Stanford University (1991) S.M., Massachusetts Institute of Technology (1994) Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy at the Massachusetts Institute of Technology May 1999 [June 1999]

SIGNATURE OF author: [[signature omitted]]

Department of Electrical Engineering and Computer Science May 14, 1999
CERTIFIED BY: [[SIGNATURE OMITTED]]

Thomas F. Knight, Jr Senior Research Scientist Thesis Supervisor ACCEPTED BY: [[SIGNATURE OMITTED]]

Arthur C. Smith Chairman, Departmental Committee on Graduate Students ARCHIVES MASSACHUSETTS INSTITUTE OF TECHNOLOGY LIBRARIES

Massachusetts Institute of Technology Page 1 Dec 31, 1999

Page 2 of 9

Reversibility for efficient computing

Reversibility for Efficient Computing

By

Michael P. Flank

Submitted to the Department of Electrical Engineering and Computer Science on May 14, 1999, in partial fulfillment of the Requirements for the degree of Doctor of Philosophy

Abstract

Today's computers are based on irreversible logic devices, which have been known to be fundamentally energy-inefficient for several decades. Recently, alternative reversible logic 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 increase asymptotic computational efficiency, as machine sizes increase. I project real benefits for supercomputing at a large (but achievable) scale in the 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 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.

Finally, I describe techniques for programming reversible computers. I present a high-level language and a compiler suitable for coding efficient reversible algorithms, and I describe a variety of example algo...