View Related Documents

Abstract

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].

Fulltext Preview

Image of the first page of the fulltext document