  Known simulations of random access machines (RAMs) or parallel RAMs (PRAMs)
by Boolean circuits incur significant polynomial blowup, due to the need to
repeatedly simulate accesses to a large main memory.
  Consider a single modification to Boolean circuits that removes the
restriction that circuit graphs are acyclic. We call this the cyclic circuit
model. Note, cyclic circuits remain combinational, as they do not allow wire
values to change over time.
  We simulate PRAM with a cyclic circuit, and the blowup from our simulation is
only polylogarithmic. Consider a PRAM program $P$ that on a length-$n$ input
uses an arbitrary number of processors to manipulate words of size $\Theta(\log
n)$ bits and then halts within $W(n)$ work. We construct a size-$O(W(n)\cdot
\log^4 n)$ cyclic circuit that simulates $P$. Suppose that on a particular
input, $P$ halts in time $T$; our circuit computes the same output within $T
\cdot O(\log^3 n)$ gate delay.
  This implies theoretical feasibility of powerful parallel machines. Cyclic
circuits can be implemented in hardware, and our circuit achieves performance
within polylog factors of PRAM. Our simulated PRAM synchronizes processors via
logical dependencies between wires.
