Recursive Star-Tree Parallel Data-Structure
Abstract
The model of parallel computation that is used in this paper is the concurrent-read concurrent-write (CRCW) parallel random access machine (PRAM). We assume that several processors may attempt to write at the same memory location only if they are seeking to write the same value (the so called, Common CRCW PRAM). We use the weakest Common CRCW PRAM model, in which only concurrent writes of the value one are allowed. Given two parallel algorithms for the same problem one is more efficient than the other if: (1) primarily, its time- processor product is smaller, and (2) secondarily (but important), its parallel time is smaller. Optimal parallel algorithms are those with a linear time- processor product. A fully-parallel algorithm that runs in constant time using an optimal number of processors. An almost fully-parallel algorithm is a parallel algorithm that runs in alpha(n) (the inverse of Ackermann function) time using on optimal number of processors. The notion of fully-parallel algorithm represents an ultimate theoretical goal for designers of parallel algorithms. Research on lower bounds for parallel computation (see references later) indicates that for nearly any interesting problem this goal is unachievable. These same results also preclude almost fully-parallel algorithms for the same problems. Therefore, any result that approaches this goal is somewhat surprising.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1990
- Accession Number
- ADA227803
Entities
People
- Omer Berkman
- Uzi Vishkin
Organizations
- University of Maryland