Title: On the Power of Concurrent Read

Speaker: Navin Goyal, Rutgers University

Date: Tuesday April 1, 2003, 4:30-5:30

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

PRAMs, which are abstract models of parallel computation come in several avatars. One of the most important distinction is whether more than one processors are allowed to read from a memory cell in a single time step. Models which allow this are called Concurrent Read (CR), and those which do not are called Exclusive Read (ER). To fully specify a model one also needs to define concurrency rules for how the processors write. One of the several important ways in which this can be done is Owner Write (OW), in which each memory cell is owned by a processor and only the owner of a memory cell can write into that cell. An important issue in parallel computation is to understand the relative power of these different models. In particular, does allowing the processors the power of concurrent read give any extra computational power? In this talk we will answer this question in affirmative in the setting of CROW and EROW models.

This is done by exhibiting a problem on which CROW performs well but EROW does not. Specifically, we consider the Pointer Chasing problem: Given an directed graph $G$ on $n$ vertices with each vertex having outdegree one. Pointer Chasing problem asks for the vertex obtained by following $k$ outgoing edges starting from vertex $1$. By the well-known Pointer Jumping technique this problem can be solved in time $\log{k}$ on CROW. Our main result is that it requires time $k$ (for small $k$) on most of the inputs for EROW. Hence, EROW is essentially no better than the trivial sequential algorithm of reading the path. Improving on the previous work, our results provide the optimal separation between the power of CROW and EROW PRAMs for computing boolean functions on complete domains.

This is joint work with Mike Saks and S. Venktesh.