On Reversible Computation in Asynchronous Systems

Jia Lee, Ferdinand Paper, Susumu Adachi, Shinro Mashiko Communications Research Laboratory, Nanotechnology Group, 588-2 Iwaoka, Iwaoka-cho, Nishi-ku, Kobe-city, 651-2401 Japan E-mail: {lijia,paper,sadachi,mashiko}@crl.go.jp

Abstract

Reversible computation has attracted much attention over the years, not only for its promise for computers with radically reduced power consumption, but also for its importance to Quantum Computing, Though studied extensively in a great variety of synchronous computa- tion models, it is virtually unexplored in an asynchronous framework. This paper studies reversibility of asynchronous systems, focussing in particular on delay-insensitive circuits, a type of asynchronous circuit, whose correctness of operation is unaffected by arbitrary delays of sig- nals. We start with Morita's Rotary Element (RE), a delay-insensitive reversible element that can process one signal at a time, and which has four input lines, four output lines, and two states. An RE is univer- sal, because a universal Reversible Turing Machine can be constructed from it, as shown by Morita. We embed an RE on a two-dimensional Self-Timed Cellular Automaton (STCA) , a type of cellular automaton that is asynchronous, i.e., that updates its cells at random times that are independent of each other. This proves that the STCA is capa- ble of universal and reversible computation. We then propose a new delay-insensitive reversible element that can process one signal at a time, and which has only three input lines, three output lines, and two states. We prove the universality of this element, by constructing an RE from it. Finally, we investigate reversible delay-insensitive circuits that can process more than one signal at a time. Such circuits are more subtle than their single-signal counterparts, because a simple reorder- ing of signal arrival times may (or may not) destroy their reversibility. We analyze an example in which an irreversible multi-signal circuit is constructed from reversible elements, and speculate about reasons why reversibility is not closed under circuit composition, and about ways to repair this shortcoming.