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
    0 references
    0 references
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    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
    0 references