On Separating the EREW and CREW PRAM Models,

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1988
Accession Number
ADA324003

Entities

People

  • Eli Gafni
  • Joseph Naor
  • Prabhakar Ragde

Organizations

  • Stanford University

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Availability
  • Classification
  • Computations
  • Computer Science
  • Computers
  • Contracts
  • Monitoring
  • Parallel Computing
  • Procurement
  • Security
  • Trees (Data Structures)
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research