Parallelism Always Helps
Louis Mak · SIAM Journal on Computing · 1997
It is shown that every unit-cost random-access machine (RAM) that runs in time T can be simulated by a concurrent-read exclusive-write parallel random-access machine (CREW PRAM) in time $O(\rt{T} \log T)$. The proof is constructive; thus it gives a mechanical way to translate any sequential algorithm designed to run on a unit-cost RAM into a parallel algorithm that runs on a CREW PRAM and obtain a nearly quadratic speedup. One implication is that there does not exist any recursive function that is "inherently not parallelizable."