Field-Programmable Gate Arrays: Reconfigurable Logic for Rapid Prototyping and Implementation of Digital Systems

6.6    CELLULAR AUTOMATON

Recently, much attention has been focused on cellular automata simulations of physical problems: [Wolfram86] contains a collection of important cellular automata papers, and [Toffoli87] provides a much more approachable introduction to the topic based on one particular cellular computer, the CAM-6.

The goal of these models is to set up a “universe,” based on a particular cellular automaton rule that mimics physical reality in some way, and observe its evolution. This is to be contrasted with the more traditional approach in [Prest84], where automata are used as data-processing devices to produce desired transformations in image processing. Of particular interest are the cellular automata models for fluid flow simulation: currently, a large fraction of the world’s supercomputer time is consumed by this type of problem, and cellular automata models promise cheaper and more powerful computers for this application. Although there was initially a degree of skepticism about cellular automata models in the physics community, much work has been done in the last few years in validating the cellular models, and they have gained wide acceptance. Validation has been done both against experimental results and by showing mathematically that the cellular models approach known differential equations (e.g., the Navier-Stokes equation) for particular “regions” of interest.

In this section, we outline the design of a CAL-based machine for solving such problems. This work ...