For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On Cellular Arrays and Other Topics in Parallel Computing
Oscar H. IBARRA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2002/02/01
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
cellular array, computational complexity, parallel complexity, reachability, commutativity analysis,
Full Text: PDF(259.6KB)>>
We give an overview of the computational complexity of linear and mesh-connected cellular and iterative arrays with respect to well known models of sequential and parallel computation. We discuss one-way communication versus two-way communication, serial input versus parallel input, and space-efficient simulations. In particular, we look at the parallel complexity of cellular arrays in terms of the PRAM theory and its implications, e.g., to the parallel complexity of recurrence equations and loops. We also point out some important and fundamental open problems that remain unresolved. Next, we investigate the solvability of some reachability and safety problems concerning machines operating in parallel and cite some possible applications. Finally, we briefly discuss the complexity of the "commutativity analysis" technique that is used in the areas of parallel computing and parallelizing compilers.