Are today's massive parallel processing units able to run cellular automata efficiently?

Question

I wonder whether the massively parallel computation units provided in graphic cards nowadays (one that is programmable in OpenCL, for example) are good enough to simulate 1D cellular automata (or maybe 2D cellular automata?) efficiently.

If we choose whatever finite grid would fit inside the memory of the chip, can we expect one transition of a cellular automaton defined on this grid to be computed in (quasi)constant time?

I assume 2D cellular automata would require more bandwidth for communication between the different parts of the chips than 1D automata.

I'd also be interested by the same question in the case of FPGA programming or custom chips.

Answer 1

Excellent question. I believe the answer is yes.

Evolving a cellular automaton is essentially equivalent to performing a stencil computation. On some 1D, 2D, or 3D grid, successive values of points (or cells) are computed based on the last value of point's neighborhood. In a simple 1D CA, this neighborhood might be the cell and the two cells to the left and right. There are lots of examples of stencil computations being performed on GPUs; ORNL's SHOC benchmark suite for OpenCL/CUDA contains a 2D stencil example, for instance.

The basic idea is to have each thread get a local copy of the neighborhood for several points, then compute the next values for points determined by that neighborhood. By appropriately using the memory hierarchy in e.g. CUDA (registers, shared, constant, texture, and global memories) and the SIMT processing model (e.g., by appropriately computing the transition function without introducing excessive warp divergence), good performance can be achieved.

This answer would be a lot better if I were to give an example, but I am too busy to write any code right now... But in theory, I think it should be feasible to efficiently simulate CAs on GPUs by modeling them after stencil computations. Lots of considerations go into writing a good stencil computation for GPUs, though.

Answer 2

Whatever you do, computing the next state for a cellular automaton ask for as many computation than there are cells in the automaton. Thus to get a constant time, you need as many computing core as there are cells.

The number of these in GPU are currently at most a few thousands, while the computation of the next state is so simple that I expect the result to be IO bound, i.e. you can get a very good approximation of the time needed by just considering the data movement needed (and if it isn't a good approximation, either the implementation has an inefficiency or the architecture isn't suitable, but that would be very surprising).

For FPGA, the question is more difficult and will probably depend on the mix of memory and computation units available. If I'm not too far out, you won't have enough memory to keep all units busy and if you rely on external memory, you are in the same seat as GPU, memory bandwidth will be the limiting factor and I'd not be surprised if the conclusion is that there is no advantage over GPU. (Note that while I've worked with FPGA, it was years ago, there may now be FPGA models with a right mix).

ASIC offers more flexibility. You can easily have a systolic like implementation (but with bidirectional data flow, some systolic is usually restricted to unidirectional data flow), each physical cell is one logical one: bit of memory and the needed logic to compute it's next state and is layed out so that it's physical neighbor are it's logical one. You are obviously in constant time realm. Depending on which hard macros you have, you may be better to be a little less obvious and have physical cells which regroup several logical one. The goal is to maximize what is done in one chip, in other word to minimize the communication with the outside of the chip as as soon as your communication needs are proportional to the number of cells, you'll be bandwidth limited. Yes, that mean that if you need to look at all the cells for each step, you are probably not a lot better than with GPU. (Full custom would provide only better integration, i.e. more cells per chip).

Summary: - if you want to look at all the intermediate states, GPU is the most effective approach - if you don't, you need the volume to justify an ASIC to have something better, FPGA probably won't offer enough advantage if they have any.

Answer 3

I wonder whether the massively parallel computation units provided in graphic cards nowadays are good enough to simulate 1D cellular automata (or maybe 2D cellular automata?) efficiently.

being very general, yes GPU computing is the best alternative in standard hardware available for everybody.

More in detail; in theory, under the PRAM model, the cost per time step is indeed $O(1)$, you already know that. However the GPU differs a little from PRAM since memory acceses cost more and it is divided in different hierarchies (one should consider the PMH model for a finer theoretical analysis). Additionally, threads work in groups or warps, they are lockstep computations that progress in a SIMD way. The programming model of the GPU works with the concept of grid (CUDA) or workspace (OpenCL) which is practically a 1-to-1 mapping to the space of computation of the cellular automata. This is the key feature to identify and realize that GPUs are CA-friendly. Tecnical details: If the warp divergence is treated correctly (replacing if-else conditionals by closed math expressions), memory acceses are coalesced and $n \le P$ ($n$ number of cells and $P$ number of processors), then one could say that the computational complexity is sort of $O(1)$.

on the FPGA and ASIC side, i know that there is research on building a physical CA as a grid of logic gates with states, all connected by their neighbors; i.e systolic arrays. The idea would be to not use a global memory anymore but instead rely on the states of each node in the grid. A machine of this type would be revolutionary since then we could stop talking about a computer simulating a CA and start talking about a CA running as a computer (some CA are turing complete).