Abstracts for RC’05
The 1^st Int’l Wkshp. on Reversible Computing
Ischia, Italy, May 4-6, 2005

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 (USA)

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 (USA)

“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. Normal irreversible logic operations dissipate roughly the logic signal energy, which itself has a lower bound due to thermal noise. This fact threatens to end improvements in practical computer performance within the next few decades. However, computers based mainly on 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 (USA)

“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 (USA)

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, Notre Dame (USA)

“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_BT 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 (Germany)

“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, Seoul Nat’l Univ. (Korea)

“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² and 1.0 x 0.6 mm², 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 (Germany) & Infineon

“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 (Netherlands)

“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 (USA)

Reversible Logic Circuit Optimization [invited talk]

[Abstract not yet available.]

Paper #107, Lev B. Levitin and Tommaso Toffoli, Boston Univ. (USA)

“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: “What next steps should the field of reversible computing take?”

Moderator: Michael P. Frank, FAMU-FSU (USA)

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 (Belgium)

“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 (USA)

“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, Boston Univ. (USA)

“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 (USA)

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.