文章基本信息

标题：Pointer Jumping Requires Concurrent Read
本地全文：下载
作者：Noam Nisan, Ziv Bar-Yossef
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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
关键词：CREW, EREW, lower bound, pointer jumping