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.