POINTERS VERSUS ARITHMETIC IN PRAMS

Manipulation of pointers in shared data structures is an important com munication mechanism used in many parallel algorithms. Indeed, many fu ndamental algorithms do essentially nothing else. A parallel pointer m achine (or PPM) is a parallel model having pointers as its principal d ata type. PPMs have been characterized as PRAMs obeying two restrictio ns--first, restricted arithmetic capabilities and, second, the CROW me mory access restriction (concurrent read, owner write, a commonly occu rring special case of CREW). We present results con cerning the relati ve power of PPMs (and other arithmetically restricted PRAMs) versus CR OW PRAMs having ordinary arithmetic capabilities. First, we prove lowe r bounds separating PPMs from CROW PRAMs. For example, any step-by-ste p simulation of an n-processor CROW PRAM by a PPM requires time Omega( log log n) per step. Second, we show that this lower bound is tight--w e give such a step-by-step simulation using O(log log n) time per step . As a corollary, we obtain sharply improved PPM algorithms for a vari ety of problems, including deterministic context-free language recogni tion. (C) 1996 Academic Press, Inc.