by Holger Bock Axelsen, Robert Glück, Alexis De Vos and Michael Kirkedal Thomsen
Physics tells us that at the microscopic level the evolution of a (micro-) state is reversible, ie deterministic both forward and backward in time. In contrast, our best models of computation are usually not reversible at the microscopic level, and this carries over to actual implementations in computers. As a consequence of basic thermodynamics, this irreversibility directly contributes to heat dissipation, and therefore power consumption. However, there is nothing inherently irreversible about computation, and using reversible computation models could therefore lead to lowered power consumption. In the new MicroPower project, the Department of Computer Science at the University of Copenhagen is collaborating with the University of Ghent and the hearing-aid company Oticon, to advance the theory and practice of reversible computing at the language, logic and circuit level.
The fundamental assumption about theoretical computation models (eg Turing machines, random access machines) is that they fundamentally reflect how the computations we make take place in nature, be it on paper or in a computer. However, our best physical understanding of nature reveals a striking disparity between computation models and physics models. While physical models of nature are reversible at the microscopic level, our computational models are not. In computing, we usually cannot determine a unique predecessor to any given state: the information to do so has been lost in the computation process (see Figure 1).
Figure 1: Irreversible and reversible computation paths. Red states show where the computations are irreversible.
When we build a computer based on a fundamentally irreversible model (eg using irreversible logic gates such as the ubiquitous NAND-gate) this information loss carries over into the implementation (the physical layout of the processor). Thermodynamics tells us that such irreversible machines necessarily dissipate heat (and consume power) proportional to the information erased. While the lower limit on this heat dissipation is tiny (measured in zepto-Joules, 10-21 Joules, per erased bit at room temperature) the actual dissipation is usually much higher, and proportional to the signal energy of the erased information. In fact, this is now a central problem of modern microprocessor design, and such power issues have effectively prevented clock speeds from rising in the last several years.
However, there is nothing about computation that actually requires irreversibility. Basic theoretical results show that any computation can be performed both reversibly and irreversibly; if we build a reversible computing device however, it does not need to dissipate energy due to (irreversible) information loss, because nowhere in the computational process is any information erased. Of course, in practice there are many other factors that contribute to power dissipation, so we do not actually expect any reversible computing system to be dissipation-free. The hope is simply to reduce (rather than eliminate) power consumption, by using reversible computing principles.
Historically, the incentive to develop reversible computing systems has been limited, since it is really only in the last decade that power issues have become such a dominant factor. As a consequence, reversible computing is seriously underdeveloped at this point. This gap in our knowledge of computing has become much more apparent in recent years, because reversibility has turned up in some completely different areas of computer science with advantageous properties unrelated to the original issues of power. For example, reversibility is a useful property in static timing analysis for programs, reliability analysis for embedded systems, quantum computing, and bidirectional model transformations in connection with the view-update problem for databases.
At the Department of Computer Science at the University of Copenhagen (DIKU), we study reversible computing models from the perspective of programming languages and logic design. In the new MicroPower project supported by the Danish Council for Strategic Research, DIKU has set up a collaboration with the Electronics and Information Systems Department at Ghent University (ELIS, a leading centre for reversible microelectronics) and the international hearing-aid company Oticon. The purpose of this basic research project, which will run from 2009 to 2012, is to advance and develop the theory and practice of reversible computing at the programming language, logic and circuit-design level, taking us one step closer to an actual, reversible microprocessor.
Figure 2: A fully reversible computing system must be reversible at every layer from program to circuit level.
A fundamental challenge in this setting is that every abstraction layer must be reversible (see Figure 2). We cannot expect to reap the full benefits of reversibility if we run, say, a reversible program on an irreversible architecture (even though significant benefits are still possible in this case; eg automatic program inversion, simple debugging). Thus, understanding how the different layers of reversible computing systems interact is a central goal of our research.
Links:
DIKU: http://www.diku.dk
ELIS: http://www.elis.ugent.be/en
Oticon: http://www.oticon.com
Please contact:
Robert Glück
Dept. of Computer Science, University of Copenhagen, Denmark
Tel: +45 35321400
E-mail:
