  Prior work on Automatically Scalable Computation (ASC) suggests that it is
possible to parallelize sequential computation by building a model of
whole-program execution, using that model to predict future computations, and
then speculatively executing those future computations. Although that prior
work demonstrated scaling, it did not demonstrate speedup, because it ran
entirely in emulation. We took this as a challenge to construct a hardware
prototype that embodies the ideas of ASC, but works on a broader range of
programs and runs natively on hardware. The resulting system is similar in
spirit to the original work, but differs in practically every respect.
  We present an implementation of the ASC architecture that runs natively on
x86 hardware and achieves near-linear speedup up to 44-cores (the size of our
test platform) for several classes of programs, such as computational kernels,
map-style programs, and matrix operations. We observe that programs are either
completely predictable, achieving near-perfect predictive accuracy, or totally
unpredictable, and therefore not amenable to scaling via ASC-like techniques.
We also find that in most cases, speedup is limited only by implementation
details: the overhead of our dependency tracking infrastructure and the
manipulation of large state spaces. We are able to automatically parallelize
programs with linked data structures that are not amenable to other forms of
automatic parallelization.
