Quick links

General Parallel Computation without CPUs: VLSI Realization of a Particle Machine

Report ID:
January 1995
Download Formats:


We describe an approach to parallel computation using particle
propagation and collisions in a one-dimensional cellular automaton
using a particle model -- a Particle Machine (PM). Such a machine has
the parallelism, structural regularity, and local connectivity of
systolic arrays, but is general and programmable. It contains no
explicit multipliers, adders, or other fixed arithmetic operations;
these are implemented using fine-grain interactions of logical
particles which are injected into the medium of the cellular
automaton, and which represent both data and processors. We sketch a
VLSI implementation of a PM, and estimate its speed and size. We next
discuss the problem of determining whether a rule set for a PM is free
of conflicts. In general, the question is undecidable, but enough side
information is usually available in practice to answer the question in
polynomial time. We then show how to implement division in time
linear in the number of significant bits of the result, using an
algorithm of Leighton. This complements similar previous results for
fixed-point addition/subtraction and multiplication. The precision of
the arithmetic is arbitrary, being determined by the particle groups
used as input.

Follow us: Facebook Twitter Linkedin