Embedding universal delay-insensitive
circuits
in asynchronous cellular spaces
Jia Lee, Susumu Adachi,
Ferdinand Peper, Kenichi Morita
Abstract:
Asynchronous Cellular Automata (ACA)
are cellular automata which allow cells to be
updated at times that are random and independent of each other.
Due to their
unpredictable behavior, ACA are usuallu dealt with by simulating
a timing mechanism
that forces all cells into synchronicity. Though this allows
the use of well-established
synchronous methods to conduct computations, it comes at the price
of an increased
number of cell states. This paper presents a more effective
approach based on a 5-state
ACA with von Neumann neighborhood that uses rotation- and reflection-symmetric
transition rules to describe the interactions betweeb cells.
We achieve efficient
computation on this model by embedding so-called Delay-Insensitive
circuits in it, a type
of asynchronous circuits in which signals may be subject to
arbitrary delays, without
this being an obstacle to correct operation. Our constructions
not only imply the
computational universality of the proposed cellular automaton, but
also allow the efficient
use of its massive parallelism, in the sense that the circuits operate
in parallel and there
are no signals running around indefinitely in the circuits in the
absence of input.
Fundamenta Informaticae (2004), in press.
Movies:
Colors are used to denote the five states of the ACA (rather
than the black & white patterns used in the paper):
0 = blank
1 = pink
2 = red
3 = purple
4 = blue
This ACA uses a probabilistic updating scheme, meaning that cells
are updated at random times. Two neighboring cells may undergo transitions
simultaneously. Simultaneous updating of
all the cells (pure synchronicity)
is also allowed. Simulations of the ACA are below, showing the processing
of signals by various delay-insensitive circuits and primitives implemented
on the cellular automaton: