Publications | Pending | Theses | Proposals | Press | Talks | Web-Published | Hosted | Unwritten | To
Do
Within each category, the most recent items are listed first.
This paper presented at MLPD ‘04, June 2004, discusses the new AdiaMEMS project’s early design efforts on a MEMS-based power supply for adiabatic circuits.
· Venkiteswaran Anantharam, Maojiao He, Krishna Natarajan, Huikai Xie, Michael P. Frank, “Driving Fully-Adiabatic Logic Circuits Using Custom High-Q MEMS Resonators,” presented at the 2004 workshop on Methodologies for Low Power Design, part of the ESA ’04 (Embedded Systems and Applications) conference, held in Las Vegas, Nevada, June 21-24, 2004. Paper in PDF format at http://revcomp.info/legacy/revcomp/AdiaMEMS/MLPD-04.pdf. Published in Proceedings of the International Conference on Embedded Systems & Applications, ESA ’04, H.R. Arabnia, M. Guo, & L. T. Yang, eds., CSREA Press, pp. 5-11. Talk slides in PDF format at http://revcomp.info/legacy/revcomp/AdiaMEMS/MLPD04-Talk.pdf.
This paper and poster presented at the Nanotech 2004 Conference and Trade show analyzes the minimum entropy generation per logic operation for nanoscale logic devices in a generic, technology-independent model.
·
The following is a general introductory article about
reversible computing written for Developer 2.0, a programmers’ magazine
in
·
Most so-called “adiabatic” circuit styles in the literature are actually not truly adiabatic. This paper presented at MLPD ’03 discusses some particularly widespread mistakes in adiabatic circuit design, and how to avoid them.
· M. P. Frank, “Common Mistakes in Adiabatic Logic Design and How to Avoid Them,” presented at the workshop on Methodologies in Low-Power Design 2003, March 2003, .doc, .pdf, .ps; talk: .ppt, .pdf, .ps.
This paper and talk presented at the 2003 NanoEngineering World Forum discusses Nanocomputer Systems Engineering and Physical Computing Theory, including the beginnings of what I am now calling CORP (Computing with Optimal, Realistic Physics), a physics-based model of computing for future nanocomputing purposes.
·
In this talk, I compared Reversible Computing with Quantum Computing, and argued that Reversible Computing can reasonably be expected to have significantly more economic impact on the computer industry as a whole than will Quantum Computing.
·
The following 100-page manuscript lays out the key
requirements for any theoretical model of nanocomputing
that is sufficiently realistic and powerful to carry computer engineering
through the 21st century, in the face of the various fundamental
limiting considerations from thermodynamics and quantum mechanics. It is noted that none of the models of computation that have previously been
introduced by computer scientists actually meet all of these requirements; we
give a detailed example of a new one that does.
The model is essentially a 3D mesh of reversible, quantum processors obeying
realistic physical as well as algorithmic constraints. We characterize a key measure of bit-device quality and show how energy dissipation
and information redundancy should scale with this quantity in an optimized
reversible machine. We also discuss how
a variety of specific nanocomputing technologies
relate to this model, and evaluate which technologies we think have the best
potential to win out in the long run.
The article also includes a summary of relevant recent revelations about
how basic physical quantities such as energy, entropy, temperature, momentum,
mass, length, time, etc. can all be
understood in terms of computation. [WARNING: Somewhat buggy. Needs revision.]
·
A poster presented at the NanoTech
2003 conference and trade show in
·
An invited review article, leading a special issue of an IEEE/AIP magazine, discussing the physical nature of information and surveying the fundamental limits of computing. The pre-edited version at the link has a section discussing open problems in reversible computing.
·
Next 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.
·
M. P. Frank and Thomas F. Knight, Jr., "Ultimate Theoretical Models
of Nanocomputers", Nanotechnology 9(3):162-176,
1998. Presented at the Fifth Foresight Conference on Molecular
Nanotechnology,
The first implementation of an optimally scalable parallel
adiabatic computer (again, in the low-leakage limit). We designed and
fabricated a fully-adiabatic chip implementing the Billiard Ball Model Cellular
Automaton, a simple reversible system capable of universal computation.
· M. P. Frank, Carlin Vieri, M. Josephine Ammer, Nicole Love, N. H. Margolus, and T. F. Knight, Jr., "A Scalable Reversible Computer in Silicon", in Calude, Casti, Dineen, eds., Unconventional Models of Computation, Springer, 1998, pp. 183-200. (Proc. of the First International Conference on Unconventional Models of Computation (UMC'98), held at the University of Auckland, Jan. 5-9, 1998.) http://revcomp.info/legacy/mpf/rc/flattop/ft.html.
The following paper was the first to show that reversibility
can actually help performance. In this paper and talk, which were
presented at UMC-98, we show that the asymptotically fastest possible computers
must be based on reversible primitives (in the negligible-leakage limit), and
we describe one version of the fastest possible architecture.
·
M. P. Frank, Thomas F. Knight, Jr., and
Norman H. Margolus, "Reversibility
in Optimally Scalable Computer Architectures", in ibid., pp.
165-182. http://revcomp.info/legacy/mpf/rc/scaling_paper/scaling.html.
This is an old paper (first version written in 1996) that uses a fairly traditional complexity theory approach to try to show lower bounds on the algorithmic spacetime overhead required for a reversible machine to execute an algorithm specified using an irreversible machine model. We were able to prove a lower bound only for a restricted type of black-box scenario. The question of whether a lower bound still exists more generally remains open.
·
M. P. Frank and M. J. Ammer,
"Relativized Separation of Reversible and
Irreversible Space-Time Complexity Classes", submitted to Information and Computation, May 2001. Currently under revision. http://revcomp.info/legacy/mpf/rc/memos/M06_oracle.html.
On reversible computing, by myself, students in my group at
UF, and various present & past members of the MIT reversible computing
community.
· Steve Lewis, "Techniques for Efficiently Recording State Changes of a Computer Environment to Support Reversible Debugging," UF master's thesis, 2001. http://revcomp.info/legacy/revcomp/users/sal/jims/StateHistoryRecordingTechniques.pdf.
· DoRon B. Motter, "Reversible Simulation and Visualization of Quantum Evolution", Highest Honors B.S. Thesis, UF CISE, June 2000. http://revcomp.info/legacy/mpf/sch.
·
· Carlin J. Vieri, "Reversible Computer Engineering and Architecture", Ph.D. thesis, MIT EECS, June 1999. http://revcomp.info/legacy/mpf/vieri-phd.pdf.
· M. Josephine Ammer, "A Highly Integrated Adiabatic Energy Recovery Digital to Analog Converter", ME thesis, MIT EECS, Feb. 1999. http://revcomp.info/legacy/revcomp/hw/josie-thesis.ps.gz.
· Carlin Vieri, "Pendulum: A reversible computer architecture," MS thesis, MIT EECS, 1995. http://revcomp.info/legacy/mpf/vieri-ms.pdf.
· Saed G. Younis, "Asymptotically Zero Energy Computing Using Split-Level Charge Recovery Logic", Ph.D. thesis, MIT EECS, June 1994, http://revcomp.info/legacy/mpf/younis-phd.ps.
· Norman H. Margolus, "Physics and computation", Ph.D. Thesis, MIT Physics, 1988. (Laboratory for Computer Science technical report 415). Cambridge, Mass: Laboratory for Computer Science, Massachusetts Institute of Technology, 1988. http://www.ai.mit.edu/people/nhm/thesis.pdf.
· Andrew Ressler, "The design of a conservative logic computer and a graphical editor simulator," MIT master's thesis, 1981.
· The design of a conservative logic computer and a graphical editor simulator," MIT master's thesis, 1981.
· Linda Dailey Paulson, “Reversible Computing May Improve Mobile Performance,” news article in IEEE Computer, March 2004, p. 21.
·
Ram Mohan Rao, “Reversible Computing,” interview
in
· Mention in Michael Swaine, “Backward to the Future,” article in Dr. Dobb’s Journal, CMP publishers, February 2004.
· Shane Peterson, “Researching Reversible Computing,” Government Technology Spectrum, January 2004.
· “Are “reversible” computers more energy efficient, faster?” Planet Analog, January 26, 2004.
·
Winn L. Rosch, “Chip designers try to beat
the heat,” The Plain
Dealer (
·
Ashlee Vance, “Reversible computing is ‘the only way’ to
survive Intel’s heat,” The Register (IT News site),
·
Amit Asaravala, “Chip Design Reverses a Hot Trend,”
Wired News,
·
James Clark, “ ‘Reversible’ Computers More Energy
Efficient,” Slashdot,
·
Aaron Hoover, “UF Researcher: ‘Reversible’ Computers More
Energy Efficient, Faster,” UF press release,
· Jay Stein, “More Computing Power, Less Electrical Power,” ET Currents (power industry newsletter), no. 7, March 2001.
This article about the FlatTop chip and the MIT Reversible Computing Project ran on the front page of the June 15, 1999 science section of the New York Times!
· George Johnson, “A Radical Computer Learns to Think in Reverse,” New York Times Science section, June 15, 1999.
The title in the online edition sounded a little cooler…
· George Johnson, “The Ultimate Computer Learns to Think in Reverse,” New York Times, June 15, 1999. http://www.nytimes.com/library/national/science/061599sci-computer-theory.html.
· Venkiteswaran Anantharam, Maojiao He, Krishna Natarajan, Huikai Xie, Michael P. Frank (presenter), “Driving Fully-Adiabatic Logic Circuits Using Custom High-Q MEMS Resonators,” presented at the 2004 workshop on Methodologies for Low Power Design, part of the ESA ’04 (Embedded Systems and Applications) conference, held in Las Vegas, Nevada, June 21-24, 2004. Talk slides in PDF format at http://revcomp.info/legacy/revcomp/AdiaMEMS/MLPD04-Talk.pdf.
·
Michael P. Frank (with slides by Xie and He),
“Adiabatic,
Reversible Computing for Ultra-Power-Efficient DSP,”
invited talk given at Texas Instruments,
·
Michael P. Frank, “Reversible Supercomputing: Beyond the Limits of Moore’s Law,”
invited talk presented at Sandia National Labs,
·
·
· M. P. Frank, “Common Mistakes in Adiabatic Logic Design and How to Avoid Them,” presented at the workshop on Methodologies in Low-Power Design 2003, March 2003, .doc, .pdf, .ps; talk: .ppt, .pdf, .ps.
· Michael Frank, "Physical Computing Theory, Ultimate Models, and the Tight Church's Thesis: A More Accurate Complexity Theory for Future Nanocomputing," invited talk given to the Algorithms & Theory Club, CISE dept., UF, Tue., Sep. 17, 2002. Slides in PowerPoint at http://revcomp.info/legacy/revcomp/talks/Theory-talk.ppt.
· Michael Frank and DoRon Motter, "Quantum Computer Architectures for Physical Simulations," invited talk presented by Frank at the Quantum Computation for Physical Modeling workshop sponsored by the Air Force research labs, held at Martha's Vineyard, Wed., May 8, 2002. Slides in PowerPoint at http://revcomp.info/legacy/revcomp/talks/QCPM-talk.ppt.
· Michael Frank, "Systems Engineering for Reversible Quantum Nanocomputers," invited talk given at University of Southern California, Dept. of Electrical Engineering (Architecture), Wed., May 1, 2002. Slides in PowerPoint at http://revcomp.info/legacy/revcomp/talks/USC-talk.ppt.
· Michael Frank, "Cost/Performance/Power Efficiency of Adiabatic Circuits, as a function of Device On/Off Power Ratios,"talk given in the Brown Bag Seminar series, ECE Dept., UF, March 2002. Slides in PowerPoint at http://revcomp.info/legacy/revcomp/talks/Brown-Bag-Spr02.ppt.
· Michael Frank, Lecture on adiabatic circuits, untitled guest lecture delivered in Bill Eisenstadt's VLSI class, ECE dept., Spr. 2002, http://revcomp.info/legacy/revcomp/talks/LecForBill.ppt.
· Michael Frank and David Wood, "Robust and Universal Reversible Machines & High-Level Programming Languages in a Recombinase DNA System," talk given at the DARPA/NSF BioComp PI meeting, Nov. 2001.
· Michael Frank, "DNA Computing, Reversibility, and Physical Models of Computing", invited talk given at the University of Delaware's ECE/CIS department, April 2001.
· Michael Frank, "Quantum Computational Networks," lecture series delivered as part the Quantum Computing seminar, Mathematics Department, University of Florida, March 2001.
· Michael Frank, "Reversible Logic and Its Looming Importance", Logic Seminar lecture, Mathematics Department, University of Florida, February 2001.
· Michael Frank, "Adiabatic circuits and reversible logic: Prospects for Improving Computational Efficiency in Present and Future Computing Technologies," AeMES seminar, AeMES Department, University of Florida, September 2000.
· Michael Frank, "Adiabatic logic circuits for ultra-low-power computing," presentation to Intersil corporation, June 2000.
· Michael Frank, "Ultra-Low-Power Computing via Adiabatic CMOS: Current Status and Future Prospects," Brown Bag Seminars in Electronics, Electrical and Computer Engineering Department, University of Florida, May 2000.
· Michael Frank,“Nanotechnology Research at the UF Computer & Information Science & Engineering Department (CISE),'' presentation to Sandia National Labs, April 2000.
· Michael Frank, ``Adiabatic logic circuits for energy-limited applications,'' presentation to Siemens Corporation, March 2000.
· Michael Frank, ``Thermodynamically reversible computing technology for low-power/high-performance applications,'' presentation to Harris Corporation, December 1999.
· Michael Frank, ``Thermodynamically reversible computing technology for low-power/high-performance applications,'' presentation to the UF Industrial Advisory Board, October 1999.
· Michael Frank, ``Reversibility for Efficient Computing,'' job talk, University of Florida, June 1999. (Job was offered.)
· Michael Frank, ``Reversibility for Efficient Computing,'' thesis defense, MIT EECS Dept., May 1999. (Thesis was approved.)
·
Michael
Frank, Tom Knight, and
· Michael Frank, ``A Scalable Reversible Computer in Silicon,'' talk prepared by Frank and presented by Knight at the First International Conference on Unconventional Models of Computation, Auckland, New Zealand, January 1998.
· Michael Frank, ``Reversibility for Efficient Computing,'' job talk, Texas Instruments DSP Research Division, December 1997. (Job was offered.)
· Michael Frank, ``Ultimate Theoretical Models of Nanocomputers,'' presented at the Fifth Foresight Conference on Molecular Nanotechnology, November 1997. http://revcomp.info/legacy/mpf/rc/Nano97/abstract.html.
· Michael Frank, ``Low-Energy Computing for Implantable Medical Devices,'' MIT Clinical Decision-Making Group research seminar, February 1996. http://revcomp.info/legacy/mpf/rc/MedG_talk/webpage.html.
· Michael Frank, ``Quantum Computation Primitives,'' area exam talk, MIT EECS Dept., February 1996.
This paper recently submitted to ISLPED ’03 debunks the many myths, fallacies, and pitfalls that have been associated with reversible/adiabatic computing over the years.
· M. P. Frank, “Adiabatic Circuits and Reversible Computing: Dispelling the Misconceptions”, submitted to 2003 International Symposium on Low-Power Electronics and Design, March 2003, http://revcomp.info/legacy/revcomp/Frank-ISLPED-03.doc.
This memo is similar in spirit to memos 15, 16, and 18, but attacks the special case of the energy-hardware tradeoff in low-leakage technologies. It concludes that worst-case hardware overheads scale with about the 1.57 power of energy savings.
·
In this research memo, we use considerations from Memo #M17 to derive the lower limit on entropy generation per bit-op for MOSFET-like adiabatic devices, when the quantum quality factor of the entire system (device plus timing source) is taken into account. We also derive an optimum degree of logical bit redundancy for minimizing entropy generation of individual bit-operations.
·
In this working-draft research memo, I am trying to elucidate how all physical concepts such as energy, entropy, temperature, momentum, velocity etc. can all be understood in terms of information processing. Much of this is still speculative, however.
·
Integrates analysis of cost-efficiency, 3-d scaling, algorithmic overheads, etc. into a single model, and plugs in forecasted real numbers for future technology. Includes a nice graph showing how reversible computing will become steadily more cost-efficient than ordinary computing by factors of 1000 or more over the next 50 years.
·
Analyzes a new, more spacetime-efficient variation of Bennett's algorithm to derive the optimal cost-efficiency advantage of general-purpose reversible computing in energy-cost-dominated scenarios, as a function of devices' on/off power-transfer ratios, taking leakage & algorithmic overheads into account.
·
·
Research memo, Aug. 2001. Derives the E~1/t scaling law of adiabatic systems from first principles, in a completely technology-independent way. Probably too short to publish by itself, but a potential component of some longer publication.
·
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.
·
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.
·
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.
·
A unfinished new working memo. Contains some useful info though.
·
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.
·
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.
·
· Michael P. Frank, “Programming Reversible Computers”, MIT Ph.D. thesis proposal., Dec. 1996, http://revcomp.info/legacy/mpf/rc/proposal/proposal.html.
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 below document is a preliminary report on Tick's design, in postscript format, 8MB long due to detailed layouts.
· Michael P. Frank and Scott Rixner, “Tick: The First Reversible CPU”, Project Report for MIT course 6.371, Intro to VLSI, May 1996, http://revcomp.info/legacy/mpf/rc/tick-report.ps.
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.
·
A shared resource in our project. This is actually a fairly old version; I need to put the latest one online sometime.
·
MIT Reversible Computing Group, Bibliography on Reversible
Computing, http://revcomp.info/legacy/mpf/rc/bib/bib.html.
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.
·
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.
· Chris Lutz and Howard Derby, “JANUS: A Time-Reversible Language”, CalTech class project, 1982, http://revcomp.info/legacy/mpf/rc/janus.html.
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. (Whatever could he have been thinking?) With the help of the Altavista Translation Service, I have translated this historic paper into English.
·
Yves Lecerf, “Reversible Turing
machines. Recursive insolubility in n in N of the equation u = thetan u, where theta is an ‘isomorphism of codes.’ ”,
Weekly Proceedings of the (French)
Academy of Science, 257:2597-2600, Oct. 1963, translated by
1. Reversible Schroedinger equation simulator & Motter's analysis of it (with Fredkin, Motter).
2. Relative scalability of reversible and irreversible machines (various analyses).
3. Bug in SCRL & how to fix it (with Margolus, Knight, Younis?)
4. Relative inefficiency of SCRL vs. Retractile Cascades for some problems (w. Athas, Knight, Younis?)
5. Parameter optimization of Bennett-89 algorithm.
6. Various new adiabatic circuits (patent first).
7. Efficient reversible algorithms for various specific problems (with Ammer?).
9. PISA instruction set architecture (with Carlin).
10. Pendulum implementation (with Carlin).
11. Backwards debugging techniques (with Lewis, Williams).
1. Experimental characterization of Bennett's alg. on a real architecture (Vermette's project)
2. An object-oriented reversible programming language (King)
3. Reversible computing for unrolling speculative executions (Outman, Carothers).
4. Projection of adiabatic efficiency of future device technologies.
6. Quantum computer simulator including space optimization and path integral (Nathan's project).
7. Fourier networks of resonators for powering adiabatic circuits (with ECE guys). (Patent first?)
8. Analysis of how power supply Q scales with freqency. (with ECE guys)
9. MEMS-based power supplies for adiabatic circuits (with ECE guys). (Patent first?)