Abstracts for RC’05

The
1^{st} Int’l Wkshp. on Reversible Computing

**NOTE:** The workshop’s scope includes talks in
Computing Frontiers track 1 on *Non-Conventional Computing*, to be held on Wednesday, the day before
the special session, as well as a talk in track 13 on *Special-Purpose
Architectures*, the day after the special session. The abstracts for these extra talks are
listed after the ones for the main special session.

** Special Session on
Reversible Computing** (Thursday)

This
session is focused on addressing the main theme of the workshop, which is on
progress and strategies towards practical implementation of reversible
computing. Sub-sessions: 1, 2, 3, 4.

__Welcome & Opening Remarks, Michael P. Frank,
FAMU-FSU (__

A brief overview is given of the structure of the special session, and the keynote speaker is introduced.

__Invited keynote speech: Charles H. Bennett, IBM
(USA)__

“Is Information Physical, or is Physics Informational?”

Landauer's work on the thermodynamics of computation, and more recently the theory of quantum computers, have drawn attention to previously neglected physical aspects of information. Conversely one may ask, as Wheeler did, whether some fundamental questions about physics can be more clearly posed using informational or computational notions.

__Sub-session 1:
Perspectives on Reversible Computing__

This sub-session is intended to
provide some general background on the field, and both its promise and its
difficulties, for benefit of the general audience. However, even reversible computing experts
can expect to still learn a few interesting new things here…

__Michael P. Frank____, FAMU-FSU (__

“Introduction to Reversible Computing: Motivation, Progress, and Challenges”

Reversible computing is motivated by the von Neumann-Landauer
(VNL) principle, an unassailable theorem of modern physics that tells us that
irreversible logic operations must incur a fundamental minimum energy
cost. *reversible* logic operations can
reuse a fraction of the signal energy that can theoretically approach
arbitrarily close to 100% as the quality of the devices is improved, opening
the door to arbitrarily high computer performance at fixed levels of power
dissipation. In the 32 years since the
theoretical possibility of this approach was first shown by Bennett, our
understanding of how to design and engineer practical machines based on reversible
logic has improved dramatically, but a number of significant research
challenges remain, *e.g.*, (1) the
development of fast and cheap switching devices with adiabatic energy
coefficients far below those of transistors, (2) and of clocking systems that are
themselves of very high reversible quality; and (3) the design of
highly-optimized reversible logic circuits and algorithms. Finally, the field faces an uphill social
battle in overcoming the enormous inertia of the established semiconductor
industry, with its extreme resistance to revolutionary change. A more evolutionary path that aims to
introduce reversible computing concepts only gradually might well turn out to
be a more successful strategy. This talk
explains these basic issues, to set the stage for the rest of the workshop,
which aims to address them in more depth.

__Paper #49: Erik
DeBenedictis, Sandia Nat’l Labs (__

“Reversible Logic for Supercomputing” [invited talk]

This paper is about making reversible logic a reality for supercomputing. Reversible logic offers a way to exceed certain basic limits on the performance of computers, yet a powerful case will have to be made to justify its substantial development expense. This paper explores the limits of current, irreversible logic for supercomputers, thus forming a threshold above which reversible logic is the only solution. Problems above this threshold are discussed, with the science and mitigation of global warming being discussed in detail. To develop the idea of using reversible logic in supercomputing, a design for a 1 Zettaflops supercomputer as required for addressing global climate warming is presented. However, to create such a design requires deviations from the mainstream of both the software for climate simulation and research directions of reversible logic. These deviations provide direction on how to make reversible logic practical.

__Wolfgang Porod____, Univ. of Notre Dame (__

Reversible Computing: A Skeptic’s Perspective [invited talk][CANCELED]

[This speaker was unable to attend due to a scheduling conflict. A substitute speaker is being sought.]

__Sub-session 2:
Novel Implementation Technologies__

Ordinary field-effect transistors are nearing the
limits of their capabilities. The
following talks present some of the more well-explored concepts for how to go
beyond them in reversible computing.

__C.S. Lent, S.E. Frost____ (presenting) , P.M. Kogge__

“Reversible Computation with Quantum-dot Cellular Automata”

[invited talk]

Quantum-dot cellular automata (QCA) is a strategy in which binary data is represented by charge configuration within a multi-dot cell. Data is transmitted to nearest neighbors by the Coulombic interaction. An electric field acts as a clock and imposes directionality on circuits.

We have explored the connection between logical reversibility and physical reversibility in the context of a QCA system, explicitly calculating the energy dissipated by performing an erasure as a function of the time over which it is performed.

Further, we present a Bennett-style clocking scheme to implement reversible computation that is natural to the circuits to minimize the amount of information that is erased. Molecular QCA may provide a practical implementation of reversible computing.

__Dmitri Averin____ and Vasili Semenov
(presenting), SUNY Stony Brook (USA)__

“Reversible computation with superconducting circuits” [invited talk]

Although theoretical understanding of reversible information
processing was developed many years ago, computation in the thermodynamically-reversible
regime has not yet been demonstrated so far on any reasonable integration
scale. Superconducting circuits of
Josephson junctions based on “negative-inductance SQUIDs” (nSQUIDs) hold promise
for implementation of thermodynamically-reversible computation. Several advantages offered by these circuits
include the absence of intrinsic energy dissipation in dynamics of
superconducting elements and the possibility to avoid the need for external
clock pulses due to intrinsic generation of ac signals by dc-biased Josephson
junctions. The talk will discuss the
results of numerical modeling and experimental testing of simple reversible
circuits of nSQUIDs, in particular eight-cell circular shift register, which
gives evidence of energy dissipation of about 20 k_{B}T per operation
at temperature T≈4K.

__Paper #25: Erik
Forsberg, KTH/Zhejiang U. (Sweden/China)__

“Electron Waveguide Y-branch Switch: A Review and Arguments for its Use as a Base for Reversible Logic” [invited talk]

Utilization of the wave-like properties of the electron as a basis for functional devices to be used in logical circuitry has been discussed ever since the first demonstrations of quantized conductance in quantum point contacts (QPCs). One rationale for such research is the predicted end-of-the-road of the scaling of MOSFETs and within this context electron waveguide devices have been considered potential successors of present-day MOSFETs. Of several proposed electron waveguide devices the Y-branch switch has been found to be especially interesting. This is due to two reasons: the response to applied bias is monotonic, and the applied bias necessary to achieve switching when the electron waveguide Y-branch switch is operated in a single mode coherent regime is not thermally limited. Combined, these two factors promise a device suitable for high-density packing through an expected tolerance to fabrication defects and very low power dissipation. In the following the electron waveguide Y-branch switch is reviewed and arguments for using this device as a base for reversible logic presented.

__Sub-session 3: Adiabatic and
Energy-Recovery Circuits__

These approaches rely on conventional transistors,
and often sacrifice full asymptotic reversibility for improved performance, in
light of the non-ideal characteristics of transistors. This now well-established line of work can be
viewed as a first step along an evolutionary path leading towards more highly
reversible computing in the longer term.
Experts whose interests lie in more theoretical areas may still find it
enlightening to see the complexity of the issues that can arise in the
engineering of practical circuits that are even only partially reversible.

__Paper #98:
V. Sathe, J.-y. Chueh, J. Kim, C.H. Ziesler, S. Kim, M.C. Papaefthymiou,
Univ. of Michigan (USA), Seoul Nat’l U. (Korea), MultiGig, Inc.__

“Fast, Efficient, Recovering, and Irreversible”

Recent advances in CMOS VLSI design have taken us to real working chips that rely on controlled charge recovery to operate at substantially lower power dissipation levels than their conventional counterparts. In this paper, we present three such chips that were designed in our research group and highlight some of the promising charge-recovery techniques in practice. Although their origins can be traced back to the early adiabatic circuits, these charge-recovering chips approach energy recycling from a more practical angle, shedding reversibility to achieve operating frequencies in excess of 1 GHz with relatively low overheads.

__Paper #74: S. Henzler, T. Nirschl, M.
Eireiner, E. Amirante, D. Schmitt-Landseidel, Tech. Univ. Munich (__

“Making Adiabatic Circuits Attractive for Today’s VLSI Industry: Adiabatic Mode Circuits”

Quasi adiabatic circuits like the efficient charge recovery logic (ECRL) are known to reduce dynamic power dissipation of digital CMOS circuits significantly. The possible operation frequencies have been continuously increased due to technology scaling. Anyway, the field of operation is limited to medium performance applications. If it was possible to operate a given adiabatic circuit also at extremely high frequencies there would be many new applications: A circuit working at a medium frequency most of the time and at high frequencies only for some burst mode operations can be implemented in adiabatic logic. This paper presents a new perspective of adiabatic circuits called adiabatic mode circuits. These circuits can be operated in a quasi adiabatic low-power mode but also in a high frequency domino mode if required. A novel 3-transistor memory cell capable of adiabatic and conventional operation is presented. Thus new systems with a small total power consumption but temporarily high performance can be constructed.

__Paper #76: Seokkee Kim and Soo-Ik Chae, __

“Implementation of a simple 8-bit microprocessor with reversible energy recovery logic”

In this paper, we describe a simple 8-bit microprocessor
implemented with nMOS reversible energy recovery logic (RERL) circuits. We limited its instruction set to reduce its
complexity. It supports only 19
instructions, which is a subset of the DLX instruction set. We integrated it together with an
energy-efficient 6-phase clocked power generator (CPG) excluding an off-chip
inductor. By exploiting the 6 phases in
the clocked power, we employed phase scheduling to minimize the number of the
buffers required in the microprocessor architecture. Furthermore, we employed the self-energy
recovery circuits (SERCs) to reduce their energy consumption by breaking logic
reversibility for all the parts of the microprocessor core. The 8-bit microprocessor and its on-chip
6-phase CPH that are implemented in 0.18-µm CMOS technology occupy 2.62 x 2.03
mm^{2} and 1.0 x 0.6 mm^{2}, respectively and the number of the
transistors is about 78,000 altogether.
From the measurements, we found that its minimum power consumption is
7.5µW at V_{dd}=1.8V and *f*=880kHz.

__Paper #82: J. Fischer, P. Teichmann, A.
Gargagli-Stoffi, E. Amirante, D. Schmitt-Landseidel, Tech. Univ. Munich (__

“Scaling Trends in Adiabatic Circuits”

Adiabatic circuits which are able to dissipate less energy than the fundamental limit of static CMOS are promising candidates for low-power circuits in the frequency range in which signals are digitally processed. This paper shows the main sources of the energy dissipation in adiabatic circuits. It will be presented that with state-of-the-art transistors the distinction between quasi- and fully adiabatic circuits has become obsolete. With the shrinking of the transistor dimensions, new leakage mechanisms like gate leakage occur. As the adiabatic circuits work with an oscillating power supply, leakage currents flow only a part of the period. Without any further effort adiabatic circuits save about 30% of energy dissipation caused by leakage. As in static CMOS, adiabatic circuits benefit from voltage scaling. The Efficient Charge Recovery Logic scales linearly down to supply voltages near the threshold voltage. Simulations with a sinusoidal power supply showed no significant difference to a trapezoidal supply at most frequencies. For overall dissipation accounting also for generator efficiency and attenuation on the wiring, the sinusoidal supply voltage should be preferred.

__Sub-session 4: Reversible
Computing Theory__

If we wish to go well beyond the limits of session
3’s MOSFET-based energy-recovery circuits (perhaps using session 2’s new
devices), then the logic architecture will need to be reversible to an
arbitrarily great extent. The following
talks address the optimization of reversible algorithms and circuits, and
explore the fundamental tradeoffs between energy and speed that may apply to
all reversible computing systems.

__Paul Vitanyi, ____CWI (__

“Time, Space and Energy in Reversible Computing” [invited talk]

We survey some results of a quarter century of work on general reversible computation about energy-, time- and space requirements.

__Colin Williams____, NASA JPL (__

Reversible Logic Circuit Optimization [invited talk]

[Abstract not yet available.]

__Paper #107, Lev B.
Levitin and Tommaso Toffoli, __

“Thermodynamical cost of reversible computing” [invited talk]

Since reversible computing requires preservation of information throughout the entire computational process, it implies that all the errors that appear as a result of the interaction of the information-carrying system with uncontrolled degrees of freedom must be corrected. This can only be done at the expense of an increase in the entropy of the environment corresponding to the dissipation of the “noisy” part of the energy of the system in the form of heat.

This paper gives an expression of that energy in terms of the effective noise temperature, and calculates the relationship between the energy dissipation rate and the rate of computation.

** PANEL
DISCUSSION:** Theme:
“

Moderator: **Michael
P. Frank**, FAMU-FSU (

Invited panel members include: **Baker**, **Bennett**, **Porod**, **Vitanyi**…

(Additional panelists may be added. Audience members are also encouraged to
participate in the discussions.)

** Track 1: Non-conventional computing**
(Wednesday)

This track of the regular
conference consists of additional reversible computing talks (all in the general
area of reversible computing theory) that overflowed from the special
session. The talk by **De Vos** reviews a promising mathematical
approach to the optimization of reversible logic. **Miller
**and **Fredkin** present their model
for a 3D reversible cellular automaton, which might turn out to be easily
chemically synthesized in self-assembling 3D arrays. **Toffoli**
and **Levitin** show us a new
theoretical measure of the degree of interconnectedness of a parallel dynamical
system, which could serve as an important clue to the potential of a CA model
or a physical substrate as a basis for computation.

Paper #15, **Alexis De Vos**
and **Yvan Van Rentergem**, Univ. Gent (

“Reversible computing: from mathematical group theory to electronical circuit experiment”

Reversible logic gates of a certain logic width *w* form a group (isomorphic to the
symmetric group of order (2* ^{w}*)!). Study of the sub-groups of this group both
teaches us a lot about properties of reversible gates and guides us to
synthesize particular circuits. After
design, circuits are implemented in prototype silicon chips.

Paper #44, **Daniel B. Miller**
and **Edward Fredkin**, CMU West (

“Two-state, Reversible, Universal Cellular Automata in Three Dimensions”

A novel two-state, Reversible Cellular Automata (RCA) is described. This three-dimensional RCA is shown to be capable of universal computation. Additionally, evidence is offered that this RCA is capable of universal construction.

Paper #105, **Tommaso Toffoli** and **Lev B.
Levitin**,

“Specific ergodicity: An informative indicator for invertible computational media”

*Specific
ergodicity* asks, for an invertible cellular automaton, lattice gas, or
similar indefinitely-extended computational medium, what fraction of the
information needed to specify an individual state is still missing after one is
told the computational trajectory to which that state belongs. While the well-known distinction between
“ergodic” and “nonergodic” for a dynamical system is an *all-or-nothing* classification, specific ergodicity—with range in
the [0,1] interval—provides a continuous parameter which may be interpreted as
“*degree of ergodicity*.” Moreover, while the property of a system’s
being ergodic can only refer to the system *as
a whole*, specific ergodicity is an *intensive*
quantity (i.e., it factors out the size of the system); thus, for a
spatially-distributed, homogeneous computational system such as a cellular
automaton or a lattice gas, in the limit of infinite system size this quantity
reflects an intrinsic property of the *material*
that makes up the computational medium, abstracting from its specific size or
shape.

We provide the conceptual background, present theoretical and numerical results, and discuss the relevance of specific ergodicity to a number of concrete research questions.

Values of specific
ergodicity for a variety of systems of actual interest turn out to be well
distributed over its entire range; in this sense, this quantity is an *informative indicator*. Indeed, besides representing a useful
parameter in the classification of distributed computational media, specific
ergodicity provides a “sense of direction” in issues such as protection from
noise, design of self-organizing media, effectiveness of a parallel
architecture as a “programmable medium,” and a number of topics in
nanotechnology.

** Track 13: Special-Purpose Architectures**
(Friday)

The following talk by noted reversible logic pioneer **Ed Fredkin** presents his progress in
working towards a reversible cellular automaton model of fundamental physics.

Paper #43, **Edward Fredkin**, CMU West (

*A Computing
Architecture for Physics*

Two future problems for programmers are Artificial Intelligence and Physics. In both cases there are ultimate goals: for AI it is human level intelligence and beyond, for Physics it is programming the TOE (Theory of Everything). Of course, if and when we have an AI system far more intelligent than anyone we can let it solve the remaining programming problems. The reason AI research has proved so difficult is because we don’t yet know how to program AI. It’s also true that our understanding of physics is far from complete. We assume, rightly or wrongly, that the only reason we cannot program a perfect model of fundamental processes in physics is that we don’t yet understand the physics. However we may also be in need of new computing paradigms. We want to believe that there is no magic in physics, just things we don’t yet understand. Our ignorance mustn’t discourage us from trying to make progress. This paper is a report on one frontier in computation; steps towards inventing computing architectures that might let us understand aspects of fundamental processes in physics.