Valiant's Maximum Algorithm with Sequential Memory Accesses

Abstract

This paper examines the performance of Valiant's PRAM algorithm for finding the maximum of a set of numbers, assuming that a modified PRAM model is used. The modified PRAM is like a standard CRCW PRAM, except that multiple read or write requests to a single memory location are handled sequentially. It is shown that using this model, Valiant's algorithm requires O(sqrt(N)) time to find the maximum of N numbers using N processors, and that it does require time proportional to sqrt(N) infinitely often.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1988
Accession Number
ADA203713

Entities

People

  • Robert Cypher

Organizations

  • University of Washington

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Computer Science
  • Computers
  • Contracts
  • Information Systems
  • Instructions
  • Military Research
  • Monitoring
  • Security
  • Standards
  • Universities

Readers

  • Computer Science.
  • Graph Algorithms and Convex Optimization.