A Game-of-Life-based Paradigm for Massively Parallel Computing on Asynchronous Circuits
Ya-Hui Ye, Jia Lee and Li-Wei Zhu
Cellular automata (CAs), such as the best-known Game of Life (GL), has been studied extensively as theoretical models for massively parallel computation. Implementation of CAs in hardware may not only establish a fully parallel architecture but also facilitate the inclusion of bio-inspired mechanisms, e.g., self-reproduction and self-organization, into computational processes. Previous implementations of CAs usually depend on combinational logic circuits, in which a clock signal must be distributed in parallel to all modules each simulating a CA’s cell. This paper proposes an effective scheme for constructing the GL via a delay-insensitive (DI) circuit, a special type of asynchronous circuits whose correctness of operation is not affected by arbitrary delays in modules or interconnection lines. In order to simulate the synchronous transitions of all GL’s cells, the scheme adopts a natural handshaking mechanism which enables all modules that are interconnected uniformly within the circuit to operate in lockstep at local scale. This actually eliminates the distribution of a clock signal and allows a scalable structure for the DI-circuit. Moreover, the DI-circuit is composed by simple elements without extra elements used for arbitrating unexpected inputs, which may benefit the implementation of the circuit in RSFQ, or other post-CMOS technologies.
Keywords: Asynchronous circuit; Game of Life; delay-insensitive circuit; cellular automaton; parallel computing