Array processing machines: an abstract model (Q1094879)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Array processing machines: an abstract model |
scientific article |
Statements
Array processing machines: an abstract model (English)
0 references
1987
0 references
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.
0 references
model of parallel computation
0 references
array processing machine
0 references
polynomial space
0 references
sequential random access machine
0 references
polynomial time
0 references
0 references