Accession Number : ADA324003

Title :   On Separating the EREW and CREW PRAM Models,

Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Gafni, Eli ; Naor, Joseph ; Ragde, Prabhakar

PDF Url : ADA324003

Report Date : DEC 1988

Pagination or Media Count : 7

Abstract : Snir proposed the Selection Problem (searching in a sorted table) to show that the CREW PRAM is strictly more powerful than the EREW PRAM. This problem defines a partial function, that is, one that is defined only on a restricted Set of inputs. Recognizing whether an arbitrary input belongs to this restricted set is hard for both CREW and EREW PRAMs. The existence of a total function that exhibits the power of the CREW model over the EREW model was an open problem. Here we solve this problem by generalizing the selection problem to a Decision Tree problem which is defined on a full domain and to which Snir's lower bound applies.

Descriptors :   *PARALLEL PROCESSING, DISTRIBUTED DATA PROCESSING, INPUT OUTPUT PROCESSING, PARALLEL PROCESSORS, RANDOM ACCESS COMPUTER STORAGE.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE