A scalable configurable architecture for the massively parallel GCA model

Abstract

The global cellular automata model (GCA) is a massively parallel computation model which extends the classical cellular automata (CA) model with dynamic global neighbours. 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). Therefore each pipeline can execute one cell operation in every clock cycle. 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 neighbourhood search space are interchanged. The pointers are modified in each generation by a pseudo random function. For that application, an application-specific data parallel machine with up to 32 pipelines was synthesised for an Altera field-programmable gate array. In addition, this application was described in the high-level language GCAL. The RULE instruction can also automatically be extracted from the GCAL program leading to the same generated application specific DPA machine.

Keywords:

• global cellular automata
• data parallel architecture
• configurable field programmable gate array (FPGA) architecture
• application specific processor
• multi-pipeline processor
• GCA language