Some Complexity Issues in Parallel Computing

                           Oscar H. Ibarra
                    Department of Computer Science
                      University of California
                      Santa Barbara, CA 93106

                              Abstract

We give an overview of the computational complexity of (linear and mesh-
connected) cellular arrays with respect to well known models of sequential
and parallel computation. We discuss one-way communication versus two-way
communication, linear-time versus real-time, 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 loops. We also point out
some important and fundamental open problems that remain unresolved.

Two operations commute if they generate the same result regardless of the 
order in which they execute. Commuting operations enable significant
optimizations in the areas of parallel computing, parallelizing compilers
and database concurrency control. We discuss the complexity of commutativity
analysis for a variety of basic instructions and control constructs. 

----------------------------------------


Oscar H. Ibarra received the B.S. degree in Electrical Engineering from
the University of the Philippines in 1962 and the M.S. and Ph.D. degrees,
also in Electrical Engineering, from the University of California, Berkeley,
in 1965 and 1967, respectively.  He is currently a Professor of Computer
Science at the University of California, Santa Barbara.  He has previously
been with the faculties of UC Berkeley (1967-1969) and the University of
Minnesota (1969-1990).  Dr. Ibarra's research interests include the design
and analysis of algorithms, the theory of computation, computational
complexity, and parallel computing.  He is a Fellow of the Association for
Computing Machinery (ACM), the Institute of Electrical and Electronics
Engineers (IEEE), the American Association for the Advancement of Science
(AAAS), and the Minnesota Supercomputer Institute.  He is a recipient of
a Guggenheim Fellowship.

Dr. Ibarra is on the editorial boards of IEEE Transactions on Parallel and
Distributed Systems, Journal of Parallel and Distributed Computing,
Theoretical Computer Science, International Journal of Foundations of Computer
Science, Journal of Computing and Information, and Journal of VLSI Signal
Processing.  He was on the editorial board of IEEE Transactions on Computers
from 1991-1994.  He is on the advisory board of the Parallel Computing Book
Series for Chapman and Hall.