PARALLELIZATION OF SHORT- AND LONG-RANGE CELLULAR AUTOMATA ON SCALAR, VECTOR, SIMD AND MIMD MACHINES

Abstract

Algorithms exhibiting parallelization on many different levels are discussed for short-and long-range cellular automata implemented on scalar, vector, SIMD and MIMD machines. Short range cellular automata are commonly used for simulating hydrodynamic fluid flows, while long range cellular automata are applicable to neural networks at zero temperature. A common programming approach based upon multi-spin coding and including higher levels of parallelization when possible, has been used to implement these models on the SUN SPARC-1, the IBM-3090, the Alliant FX/2800, the NEC-SX3/11, the Cray-YMP/832 and the Connection Machine, CM-2. Section 4 of the paper compares the performance of these computers for the algorithms discussed in the text. Additionally, the major subroutines for each computer type are given in the Appendix.