Array processing machines: an abstract model
type: Item
instance of: scholarly article
title: Array processing machines: an abstract model
zbMATH Open document ID: 0631.68053
DOI: 10.1007/BF01937352
published in: BIT
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4026839
zbMATH Keywords: model of parallel computation
zbMATH Keywords: array processing machine
zbMATH Keywords: polynomial space
zbMATH Keywords: sequential random access machine
zbMATH Keywords: polynomial time
author: J. Van Leeuwen
author: Jiří Wiedermann
MaRDI profile type: Publication
cites work: Q4091421
cites work: Alternation
cites work: Towards a complexity theory of synchronous parallel computation
cites work: Q3311653
cites work: Time bounded random access machines
cites work: Q4061923
cites work: Some Computer Organizations and Their Effectiveness
cites work: Parallelism in random access machines
cites work: A universal interconnection pattern for parallel computers
cites work: Q3674026
cites work: Q4057549
cites work: A characterization of the power of vector machines
cites work: On uniform circuit complexity
cites work: Parallel random access machines with powerful instruction sets
cites work: Time Bounded Random Access Machines with Parallel Processing
cites work: Simulation of Parallel Random Access Machines by Circuits
cites work: Parallel Processing with the Perfect Shuffle
cites work: An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations
cites work: Q4029597
cites work: Q3666269
full work available at URL: https://doi.org/10.1007/bf01937352
OpenAlex ID: W2013834840
description: scientific article; zbMATH DE number 4026839