composition.al

“Taming the Parallel Effect Zoo” and the PLDI artifact evaluation process

My co-authors Aaron Todd, Sam Tobin-Hochstadt, Ryan Newton, and I have just finished up the camera-ready version of our new paper, “Taming the Parallel Effect Zoo: Extensible Deterministic Parallelism with LVish”, which will appear at PLDI 2014 in Edinburgh this June. In addition to having the paper accepted, we were happy to learn a few weeks ago that our submission passed the PLDI artifact evaluation process.

Disorder and determinism

My research on LVars is all about deterministic parallel programming: writing programs so that they can be scheduled onto parallel hardware with the goal of running faster, and doing so in such a way that the observable results of a program are guaranteed to be the same on every run.

But, as much time as I spend insisting that LVars enforce determinism, there’s actually a huge amount of nondeterminism in LVar programs! For instance, the order in which writes to an LVar occur isn’t deterministic at all. Writes can happen in any order, and, in fact, that’s the whole point.