A fine-grain asynchronous VLSI cellular array processor architecture

The cellular iterative computation model bears upon three broad-ranging application domains: pixel-level image processing, finite-difference approximation of continuum problems (boundary value PDEs) in computational physics, and cellular automata as discrete models of complex locally-interacting systems, aimed at probing their emergent collective properties. The common underlying idea is to compute the global dynamics of a lattice-structured state-space through the iterative propagation of purely local computational dependencies between state-components. A past generation of mesh-connected SIMD array-processors, among which the MPP [Bat 80], CLIP [Pre 84] and CAM [Tof 87] machines, were canonical architectural mappings of this fruitful concept. All were fine-grain synchronous solutions. The new generation of MIMD RISC-based parallel computers that superseded them are essentially coarse-grain and asynchronous; They can simulate a cellular iterative model in a parallel pseudo-synchronous SPMD mode with global coordination mechanisms. A fine-grain asynchronous architectural model departs in a somewhat paradoxical way from these two mainstream approaches. The idea is to match an architecture with a functional concept of a synchronism, specific to cellular relaxation algorithms. As we show in the following, benefits accrue at both levels from this matching