SEPARATING THE POWER OF EREW AND CREW PRAMS WITH SMALL COMMUNICATION WIDTH

Authors
BEAME P FICH FE SINHA RK
Citation
P. Beame et al., SEPARATING THE POWER OF EREW AND CREW PRAMS WITH SMALL COMMUNICATION WIDTH, Information and computation, 138(1), 1997, pp. 89-99
Citations number
13
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
138
Issue
1
Year of publication
1997
Pages
89 - 99
Database
ISI
SICI code
0890-5401(1997)138:1<89:STPOEA>2.0.ZU;2-Z
Abstract
We prove that evaluating a Boolean decision tree of height h requires Omega(h/(m + logh)) time on any EREW PRAM with communication width m and any number of processors. Since this function can be easily comput ed in time O(root h) on a CREW PRAM with communication width 1 using 2 (o(h)) processors, this gives a separation between the two models when ever the EREW PRAM has communication width m is an element of o(root h ). (C) 1997 Academic Press.