Safe Programmable Speculative Parallelism [abstract] (ACM DL, PDF)
Prakash Prabhu, G Ramalingam, and Kapil Vaswani
Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2010.
Execution order constraints imposed by dependences can serialize
computation, preventing parallelisation of code and algorithms.
Speculating on the value(s) carried by dependences is one way
to break such critical dependences. Value speculation has been
used effectively at a low level, by compilers and hardware. In this
paper, we focus on the use of speculation by programmers as an
algorithmic paradigm to parallelize seemingly sequential code.
We propose two new language constructs, speculative composition
and speculative iteration. These constructs enable programmers
to declaratively express speculative parallelism in programs:
to indicate when and how to speculate, increasing the parallelism
in the program, without concerning themselves with mundane implementation
We present a core language with speculation constructs and mutable
state and present a formal operational semantics for the language.
We use the semantics to define the notion of a correct speculative
execution as one that is equivalent to a non-speculative execution.
In general, speculation requires a runtime mechanism to undo
the effects of speculative computation in the case of mispredictions.
We describe a set of conditions under which such rollback can be
avoided.We present a static analysis that checks if a given program
satisfies these conditions. This allows us to implement speculation
efficiently, without the overhead required for rollbacks.
We have implemented the speculation constructs as a C# library,
along with the static checker for safety. We present an empirical
evaluation of the efficacy of this approach to parallelization.