composition.al

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.

Music as preparation for a computer science career

Today on Twitter, an informal survey is making the rounds on the experiences of software developers who came to the field from “non-traditional”, that is, non-CS backgrounds. I’m not sure if I should consider myself the target audience for the survey: on one hand, I do have a couple of “traditional” CS degrees by now, and I’m in mainstream CS academia; on the other hand, I didn’t set out to study computer science when I started college (and certainly didn’t consider doing so prior to college, either), and I was a music major for two years before I added a second undergrad major in CS. I did go ahead and fill out the survey, and I thought I’d also share my answers here. I’m curious to hear from others whose experiences are like mine.

The LVar that wasn’t

Suppose we want to write a program in which two threads, say, t1 and t2, each contribute a Boolean value, either True or False, to a shared result. If both threads write True, we want the result to be True; if either writes False (or if both do), then we want the result to be False. That is, we want the shared result to be the outcome of a logical “and” operation.

Let’s further suppose that we want the threads to be able to run in parallel, with their writes arriving in arbitrary order, and we want to be able to guarantee a deterministic result in spite of parallel execution. Sounds like a job for LVars!

Update (February 19, 2014): I’ve updated the links in this post to point to code that runs against the 1.1.2 release of LVish.