| Cellular automata (CA) are a class of fine-grained, massively-parallel computational paradigms for describing discrete, spatially distributed dynamical systems governed by a discrete, homogeneous, local dynamics. CA computing applications include discrete physical models and empirical studies in algorithmic self-assembly, computation, complexity, and the statistical mechanics of emergence.; Despite a number of existing CA applications, programming environments, and special-purpose hardware and software techniques for implementing them, there exists no implementation-independent architecture for computing with CA that is analogous to those used in similar types of co-processing applications such as computer graphics. It is our thesis that, by analyzing the recurring high-level conceptual constructs and methods employed by the human designers of CA systems and the various low-level implementation strategies employed to achieve high performance in running them, one may arrive at a rational software architecture that makes these dynamical systems natural to express yet amenable to efficient, automated implementation.; We motivate and present a software architecture called STEP, short for space-time event processor, that targets these goals. The STEP architecture consists of an abstract CA co-processor, an application program interface for controlling it, and a programming environment called SIMP for building CA applications. We show that SIMP applications are considerably shorter and simpler than corresponding C programs, but, nevertheless, achieve performance equal to that of compiled C.; Novel aspects of this work include (a) the first realization of a simple conceptual and computing environment that can deal equally well with CA and variants such as lattice gas automata and partitioning cellular automata; (b) direct support for CA state variables and updates defined on non-orthonormal integer lattices; (c) a new method performing CA updates via a scan loop that efficiently processes the uniform part of the CA volume and employs a virtual-interrupt based interpreter to handle exceptions at the boundaries; and (d) techniques for converting and compiling Python CA transition function code into C procedures on-the-fly. |
