The presense of data and control dependencies often prevents programmers and compilers from parallelizing computations. 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 project, we focus on the use of speculation by programmers as an algorithmic paradigm to parallelize seemingly sequential computations.
Consider two computations, a (long running) producer P and a consumer C such that C depends on P for the value of some variable V. If the value of V is predictable, we can execute C speculatively using a predicted value in parallel with P. If the prediction turns out to be correct, we gain performance since C doesnt wait for P anymore. If the prediction is incorrect (which we can find out when P completes), we have to take corrective action, cancel C and restart C with the right value of V again.
Several real-world applications such as lexical analysis, huffman decoding, dynamic programming etc. can be parallelized using speculative parallelism. These computations contain loops with cross iteration dependencies. By using a domain specific function for predicting the value of these dependencies, these algorithms show almost linear speedup! Check our paper for more details on speculative parallel versions of these algorithms.
Library for speculative parallelism
Writing speculative parallel algorithms is a non-trivial, bug-prone programming exercise. As part of the implementation, programmers must create threads for producers, consumers and prediction functions, check predictions, cancel and roll-back consumers if predictions go wrong and deal with exceptions. More importantly, programmers must also reason about correctness of a speculatively parallel program. This is hard in the presence of side-effects.
We propose two programming language constructs, speculative composition and speculative iteration, that simplify the implementation of speculatively parallel algorithms. Speculative iteration, for example, is best thought of asa variant of the standard parallel do all construct for loops with cross-iteration dependencies.
- Prakash Prabhu, G Ramalingam, and Kapil Vaswani, Safe Programmable Speculative Parallelism, in Proceedings of Programming Language Design and Implementation (PLDI), Association for Computing Machinery, Inc., June 2010
Downloads (coming soon!)
- Speculative parallel library for .NET
- Static analysis for purity and rollback freedom