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.