We study the problem of asymptotically reducing the runtime of serial computations with circuits of polynomial size. We give
an algorithmic size-depth tradeoff for parallelizing time
t random access Turing machines, a model at least as powerful as logarithmic cost RAMs. Our parallel simulation yields logspace-uniform
t
O(1) size,
O(
t/log
t)-depth Boolean circuits having semi-unbounded fan-in gates. In fact, for appropriate
d, uniform
t
O(1)2
O(t/d) size circuits of depth
O(
d) can simulate time
t. One corollary is that every log-cost time
t RAM can be simulated by a log-cost CRCW PRAM using
t
O(1) processors and
O(
t/log
t) time. This improves over previous parallel speedups, which only guaranteed an Ω(log
t)-speedup with an exponential number of processors for weaker models of computation. These results are obtained by generalizing
the well-known result that
DTIME[t] Í ASPACE[logt]\textsf{DTIME}[t]\subseteq \textsf{ASPACE}[\log t].
Keywords Circuit complexity – Alternation – Parallel speedup
This work was performed while the author was a student at Carnegie Mellon University, supported by the NSF ALADDIN Center
(NSF Grant No. CCR-0122581). A preliminary version of this work appeared in the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’05) [25].