id: 03949714
dt: j
an: 03949714
au: Cook, Stephen; Dwork, Cynthia; Reischuk, Rüdiger
ti: Upper and lower time bounds for parallel random access machines without
    simultaneous writes.
so: SIAM J. Comput. 15, 87-97 (1986).
py: 1986
pu: Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA
la: EN
cc: 
ut: parallel computation; time lower bounds; synchronous parallel computer;
    sorting
ci: 
li: doi:10.1137/0215006
ab: Summary: One of the frequently used models for a synchronous parallel
    computer is that of a parallel random access machine, where each
    processor can read from and write into a common random access memory.
    Different processors may read the same memory location at the same
    time, but simultaneous writing is disallowed. We show that even if we
    allow nonuniform algorithms, an arbitrary number of processors, and
    arbitrary instruction sets, $Ω$ (log n) is a lower bound on the time
    required to compute various simple functions, including sorting n keys
    and finding the logical "or" of n bits. We also prove a surprising time
    upper bound of.72 log$\sb 2n$ steps for these functions, which beats
    the obvious algorithms requiring $\log\sb 2n$ steps. If simultaneous
    writes are allowed, there are simple algorithms to compute these
    functions in a constant number of steps.
rv: