SIAM Journal on Computing · 1986 · 339 citations · 3 references
ComputingComputer EngineeringComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingAlgorithm AnalysisInstruction-level ParallelismParallel Complexity TheoryParallel Computing SystemsComputational Lower BoundsKeysLower Bound ComputationLower BoundsParallel Algorithmic Lower BoundsParallel Random Access MachineRandom-access MemorySynchronous Parallel Algorithms
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, $\Omega (\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 _2 n$ steps for these functions, which beats the obvious algorithms requiring $\log _2 n$ steps.If simultaneous writes are allowed, there are simple algorithms to compute these functions in a constant number of steps.
3
Parallelism in random access machines
Steven Fortune, James Wyllie · 1978 · 885 citations