TR97-008 Authors: Noam Nisan, Ziv Bar-Yossef

Publication: 17th March 1997 09:24

Downloads: 1682

Keywords:

We consider the well known problem of determining the k'th

vertex reached by chasing pointers in a directed graph of

out-degree 1. The famous "pointer doubling" technique

provides an O(log k) parallel time algorithm on a

Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that

this problem requires Omega(k) steps on an Exclusive-Read

Exclusive-Write (EREW) PRAM, for every k < (c sqrt(log n)),

where n is the number of vertices and c is a constant.

This yields a boolean function which can be computed in

O(log log n) time on a CREW PRAM, but requires

Omega(sqrt (log n)) time on even an `ideal' EREW PRAM. This

is the first separation known for boolean functions between the

power of EREW and CREW PRAMs. Previously, separations between

EREW and CREW PRAMs were only known for functions on `huge'

input domains, or for restricted types of EREW PRAMs.