Pointers versus Arithmetic in PRAMs

AbstractManipulation of pointers in shared data structures is an important communication mechanism used in many parallel algorithms. Indeed, many fundamental algorithms do essentially nothing else. Aparallel pointer machine(or PPM) is a parallel model having pointers as its principal data type. PPMs have been characterized as PRAMs obeying two restrictions—first, restricted arithmetic capabilities and, second, the CROW memory access restriction (concurrent read, owner write, a commonly occurring special case of CREW). We present results concerning the relative power of PPMs (and other arithmetically restricted PRAMs) versus CROW PRAMs having ordinary arithmetic capabilities. First, we prove lower bounds separating PPMs from CROW PRAMs. For example, any step-by-step simulation of ann-processor CROW PRAM by a PPM requires timeΩ(loglogn) per step. Second, we show that this lower bound is tight— we give such a step-by-step simulation using O(loglogn) time per step. As a corollary, we obtain sharply improved PPM algorithms for a variety of problems, including deterministic context-free language recognition