A MODEL OF SEQUENTIAL-COMPUTATION WITH PIPELINED ACCESS TO MEMORY

We introduce a new sequential model of computation, called the Logarit hmic Pipelined Model (LPM), in which a RAM processor of fixed size has pipelined access to a memory of m cells in time log m. Our motivation is that the usual assumption that a memory can be accessed in constan t time becomes theoretically unacceptable as m increases, while an acc ess time of log m is consistent with VLSI technologies. For a problem PI of size n, PI is-an-element-of P, we denote by S(n) the time requir ed by the fastest known sequential algorithm, and by T(n) the time req uired by the fastest algorithm solving PI in the LPM. Letting O(log n) = O(log m), we define several complexity classes; in particular, LP0 = {PI is-an-element-of P: T(n) = O(S(n))}, the class of problems for w hich the LPM is as efficient as the standard model, and LP(infinity) = {PI is-an-element-of P: T(n) = O(S(n) log n)}, where the problems are less adequately solved in the new model. We first study the relations between the LPM and other models of computation. Of particular releva nce is comparison with the PRAM model. Then we discuss several problem s and derive the relative upper and lower bounds in the LPM. Our resul ts lead to a new organization of parallel algorithms for list-linked s tructures.