Simulations among concurrent-write PRAMs (Q1104097)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Simulations among concurrent-write PRAMs |
scientific article |
Statements
Simulations among concurrent-write PRAMs (English)
0 references
1988
0 references
The paper is concerned with the relative power of the two most popular concurrent-write models of parallel computation, the PRIORITY PRAM [\textit{L. M. Goldschlager}, J. Assoc. Comput. Mach. 29, 1073-1086 (1982; Zbl 0489.68042)], and the COMMON PRAM [\textit{L. Kučera}, Inf. Process. Lett. 14, 93-96 (1982; Zbl 0498.68029)]. Improving the trivial and seemingly optimal O(log n) simulation, we show that one step of a PRIORITY machine can be simulated by O(log n/(log log n)) steps of a COMMON machine with the same number of processors (8C25 A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the first n/log n processor, O(log n)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.
0 references
parallel random access machines
0 references
write-conflict resolution
0 references
lower bounds. centroid decomposition
0 references
list ranking
0 references
concurrent-write models of parallel computation
0 references
PRIORITY PRAM
0 references
COMMON PRAM
0 references
parallel algorithm
0 references
EREW PRAM algorithm
0 references
expression tree
0 references