On Cellular Arrays and Other Topics in Parallel Computing(<特集>Special Issue on Selected Papers from LA Symposium)

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2002-02-01

著者

• Ibarra Oscar

  Department Of Computer Science University Of California

関連論文

• On Cellular Arrays and Other Topics in Parallel Computing(Special Issue on Selected Papers from LA Symposium)
• Some Complexity Issues in Parallel Computing (Algorithm Engineering as a New Paradigm)

スポンサーリンク