On Cellular Arrays and Other Topics in Parallel Computing

Oscar H. IBARRA  

IEICE TRANSACTIONS on Information and Systems   Vol.E85-D   No.2   pp.312-321
Publication Date: 2002/02/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
cellular array,  computational complexity,  parallel complexity,  reachability,  commutativity analysis,  

Full Text: PDF(259.6KB)>>
Buy this Article

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.