Optimal Separations Between Concurrent-Write Parallel Machines

We obtain tight bounds on the relative powers of the Priority and Common models of parallel random-access machines (PRAMs). Specifically we prove that: The Element Distinctness function of n integers, though solvable in constant time on a Priority PRAM with n processors, requires Ω( A ( n,p )) time to solve on a Common PRAM with p ≥ n processors, where A ( n , p ) = n log n / p log ( n / p log n + 1). One step of a Priority PRAM with n processors can be simulated on a Common PRAM with p processors in Ο ( A ( n , p )) steps. As an example, the results show that the time separation between Priority and Common PRAMs each with n processors is Θ(log n /log log n ).

Authors

• Ravi B. Boppana

Keywords

No keywords are indexed for this paper.