General Parallel Computation without CPUs: VLSI Realization of a Particle Machine
Report ID: TR-484-95Author: Jakubowski, Mariusz H. / Steiglitz, Kenneth / Squier, Richard K.
Date: 1995-02-00
Pages: 18
Download Formats: |Postscript|
Abstract:
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.