Bounds on the time for parallel RAM's to compute simple functions

1 January 1982

conference paper
Published by Association for Computing Machinery (ACM)

p. 231-233
https://doi.org/10.1145/800070.802196

Abstract

We prove that a parallel RAM with no write conflicts allowed requires -&-Ohgr;(log n) steps to compute the Boolean or of n bits stored in the first n global memory cells. We first argue that this result is subtler than it appears, and in fact the -&-ldquo;obvious-&-rdquo; lower bound of log2n steps can be beaten.

Keywords

SIMPLE FUNCTION
N BIT
N GLOBAL MEMORY CELL
PARALLEL RAM
LOG N
LOG2N STEP
LOWER BOUND

This publication has 0 references indexed in Scilit: