4. Parallel Computing 14. Introduction

Cellular Automata

A cellular automaton is a theoretical model that, in some ways, is the ultimate data

parallel machine. The machine consists of an infinite array of cells. Each cell contains a

state drawn from a finite set, as well as a finite state machine, which is typically the same

for every cell. The state transitions of the machine use the cell's own state, as well as the

states of selected other cells (known as the cell's neighbors), to determine the cell's next

state. All cells compute their next states simultaneously. The entire infinite array

therefore operates in locked-step fashion.

In most problems of interest, only a finite number of the cells are in a non-quiescent state.

In other words, most of the cells are marking time. The state-transition rules are usually

designed this way. The automaton is started with some specified cells being non-

quiescent. This is how the input is specified. Then non-quiescent states generally

propagate from those initial non-quiescent cells.