A scalable configurable architecture for the massively parallel GCA model

The global cellular automata model (GCA) is a massively parallel computation model which extends the classical cellular automata model (CA) with dynamic global neighbors. We present for that model a data parallel architecture which is scalable in the number of parallel pipelines and which uses application specific operators (adapted operators). The instruction set consists of control and RULE instructions. A RULE computes the next cell contents for each cell in the destination object. The machine consists of P pipelines. Each pipeline has an associated primary memory bank and has access to the global memory (real or emulated multiport memory). The diffusion of particles was used as an example in order to demonstrate the adaptive operators, the machine programming and its performance. Particles which point to each other within a defined neighborhood search space are interchanged. The pointers are modified in each generation by apseudo random function. The machine with up to 32 pipelines was synthesized for an Altera FPGA for that application.

1 Introduction

The GCA (Global Cellular Automaton) model [6], [2] is an extension of the classical CA (Cellular Automaton) model [13], [15]. In the CA model the cells are arranged in a fixed grid with fixed connections to their local neighbors. Each cell computes its next state by the application of a local rule depending on its own state and the states of its neigh-bors. The data accesses to the neighbors' states are read-only and therefore no write conflicts can occur. The rule can be applied to all cells in parallel and therefore the model is inherently massively parallel. The GCA model is a generalization of the CA model which is also massively parallel. It is not restricted to the local communication because any cell can be a neighbor. Furthermore the links to the global neighbors are not fixed; they can be changed by the local rule from generation to generation. Thereby the range of parallel applications for the GCA model is much wider than for the CA model. Typical applications for the GCA model are - besides all CA applications - graph algorithms, hypercube algorithms, logic simulation, numerical algorithms, communication networks, neural networks, games, and graphics. Typical CA applications, included in the GCA model, are physical fields, lattice gas mod-els, models of growth, moving particles, fluid flow, routing problems, picture processing, genetic algorithms, and cellular neural networks. Generally speaking the GCA model allows describing all kinds of applications with global data access and local processing. The model is powerful and flexible, e.g., it allows also to emulate hardware or even computers [14]. The general aim of our research

Project “Massively Parallel Systems for GCA” supported by Deutsche Forschungsgemeinschaft

is the hardware and software support for this model.