Array processing machines: An abstract model

We present a new model of parallel computation called the array processing machine or APM (for short). The APM was designed to closely model the architecture of existing vector- and array processors, and to provide a suitable unifying framework for the complexity theory of parallel combinatorial and numerical algorithms. It is shown that every problem that is solvable in polynomial space on an ordinary, sequential random access machine can be solved in parallel polynomial time on an APM (and vice versa). The relationship to other models of parallel computation is discussed.This work was carried out while the second author was visiting the Dept. of Computer Science, University of Utrecht, the Netherlands (Fall 1984). A preliminary version of this paper was presented at the 5th International Conference on Fundamentals of Computation Theory (FCT 85), Cottbus, Sept. 9–13, 1985.