Pointers versus Arithmetic in PRAMs

摘要

Manipulation 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Ω(log log n) per step. Second, we show that this lower bound is tight— we 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 variety of problems, including deterministic context-free language recognition.