CIS 4930.1194X/6930.1078X
Spr.'00
Assignment #8 (Course Part VI, Weeks 11-12):
Reversibility in Computer Science
Please continue to follow the general
advice on reading assignments from the
first week's assignment. Slides for this section's lectures will
be placed on reserve when available.
Reading assignment:
The topic for these two weeks is on the computer-science implications of
logical reversibility, which we have seen is needed both in order to maximize
thermodynamic efficiency, and to avoid decoherence in quantum computing.
Irreversible-to-Reversible Interconversions (Lec. 30):(Slides
in PDF.)
The following section of the course manuscript gives an overview of
this subject:
-
Section 3.3, "Review of existing reversible computing theory," pp. 59-67
of Michael Frank, "Reversibility for Efficient Computing," manuscript of
Dec. 1999. Green course reader at bookstore, also online at http://www.cise.ufl.edu/~mpf/manuscript.
This paper, which I've assigned before, informally describes the first
embedding of irreversible machines into reversible ones, in section 3.
But this wasn't originally seen as useful because it accumulated "garbage"
information which Landauer thought would still have to be eventually thermalized.
-
Rolf Landauer, "Irreversibility and Heat Generation in the Computing Process,"
IBM
Journal of Research and Development 5:183-191, 1961. On reserve.
Here is the first rigorous formal description of a irreversible-to-reversible
embedding. Lecerf's method uncomputes the garbage, but unfortunately
also the computation's output.
-
Yves Lecerf, "Reversible Turing machines. Recursive insolubility
for n in N of the equation u = theta to the n, where theta is an `isomorphism
of codes.'", Weekly Proceedings of the Sessions of the [French]
Academy of Science 257:2597-2600, Oct. 28, 1963. http://www.ai.mit.edu/~mpf/rc/Lecerf/lecerf.html.
Bennett's early paper fixes that problem and resolves the issue.
This was the first complete irreversible-to-reversible embedding that actually
does something useful.
-
Charles H. Bennett, "Logical reversibility of computation," IBM Journal
of Research and Development, 17(6):525-532, 1973. On reserve.
This next paper by Bennett gives a class of more space-efficient algorithms.
This is still the best simulation in terms of overall spacetime requirements;
probably the best possible. Levine and Sherman analyze it thoroughly.
-
C. H. Bennett, "Time/space trade-offs for reversible computation," SIAM
Journal of Computing, 18(4):766-776, 1989. Will be on
reserve.
-
Robert Y. Levine & Alan T. Sherman. "A note on Bennett's time-space
tradeoff for reversible computation." SIAM J. Computing, 19(4):673-677,
1990. Will be on reserve.
This paper shows that the time/space tradeoff in reversibility extends
to the point where linear space is possible, but with exponential time.
Minimum Overheads for Irreversible-Reversible Conversions (Lec. 31):
Progress towards proving the standing conjecture that no general-purpose
simulation of irreversible machines by reversible ones can be more spacetime-efficient
than Bennett's 1989 algorithm.
-
M. Li, J. Tromp, and P. Vitanyi, "Reversible simulation of irreversible
computation." Physica D, 120:168-176, 1998.
-
Section 3.4, "Reversible vs. irreversible space-time complexity," pp. 67-87
of Michael Frank, "Reversibility for Efficient Computing," manuscript of
Dec. 1999. Green course reader at bookstore, also online at http://www.cise.ufl.edu/~mpf/manuscript.
Reversible Computer Architectures (Lec. 32)
The following sections of the course manuscript
describe the reversible RISC-style architecture we worked on at MIT, and
general issues in reversible ISA design.
-
Chapter 9, "Design and programming of reversible processors," sections
9.1-9.3, pp. 225-236 of course manuscript.
-
Appendix B, "The Pendulum instruction set architecture (PISA)," pp. 275-293
of course manuscript.
For comparison, here is the reversible cellular-automaton architecture
we discussed earlier in the course.
-
Section 7.7, "Experimental SCRL Circuits," pp. 199-208 of course MS.
Here are the references to all of the other reversible computer architectures
I know of. I'll try to provide some of these papers online.
Temporarily, some of the readings from the Spring 2000 course reserve can
be found here.
-
Edward Barton, "A reversible computer using conservative logic," MIT term
paper, 1978.
-
Andrew Ressler, "The design of a conservative logic computer and a graphical
editor simulator," MIT master's thesis, 1981.
-
Josh Hall, "A reversible instruction set architecture and algorithms,"
PhysComp94 conference, pp. 128-134. Will be on reserve.
-
Carlin Vieri, "Pendulum: A reversible computer architecture," MIT master's
thesis, 1995. http://www.cise.ufl.edu/~mpf/vieri-ms.pdf
-
Michael Frank & Scott Rixner, "Tick: A Simple Reversible Processor,"
MIT term project report, 1996. http://www.cise.ufl.edu/~mpf/tick.pdf.
-
Carlin Vieri, "Reversible Computer Engineering and Architecture," MIT PhD
thesis, 1999.
Reversible Programming Languages (Lec. 33)
-
Section 9.4, "Reversible programming languages," pp. 236-239 of course
MS.
-
Appendix C, "The R reversible programming language," pp. 295-310 of course
MS.
-
Christopher Lutz and Howard Derby, "Janus: A time-reversible language,"
Caltech class project, 1982. http://www.ai.mit.edu/~mpf/rc/janus.html
-
Henry Baker, "NREVERSAL of fortune - The thermodynamics of garbage collection,"
International Workshop on Memory Management, 1992, pp. 507-524. Will
be on reserve.
Reversible Algorithms (Lec. 34)
-
Section 9.5, "Reversible Algorithms," pp. 239-243 of course manuscript.
-
Appendix E, "Reversible Schroedinger wave simulation," pp. 377-406 of course
MS.
-
Click here for Schroedinger
wave simulation source code.
-
Ed Fredkin, "Feynman, Barton and the Reversible Schroedinger Difference
Equation," chapter 20 (pp. 337-348) of Feynman and Computation (recommended
book in UF bookstore).
In addition to the above, Shor's article on his factoring algorithm from
the week on quantum computation describes an efficient reversible algorithm
for modular exponentiation. This
article by Vedral et al. describes some reversible arithmetic algorithms
in more detail.
Written assignment #8: (due Mon. 4/10)
This is our standing written assignment. It should be on the subject
of the above lectures and reading material.