In an essay on Cilk Arts, Professor Guy Blelloch argues that parallel programming is not intrinsically hard, but rather a question of abstraction. The three problems identified by Blelloch are a lack of training in parallel thinking, separating parallel implementation from algorithms, and determinism. After detailing each, he explains why he thinks they can be overcome.
In the question of “Parallel Thinking”, he puts forth the Quicksort algorithm. Quicksort is intrinsically parallel, both in its recursive call and in comparing the pivot element to each element in the list.
Yet most of our classes teach Quicksort without pointing out it is parallel. We carefully go through the sequential execution and analysis and argue it takes O(n log n) expected time. Most students are left clueless of the amount of parallelism in the algorithm, and certainly on how to analyze the parallelism. For example, what if one only took advantage of one or the other form of parallelism, how much is left.
Blelloch believes that since the algorithms are already at the correct level of abstraction, it is just a matter of training programmers to think in those terms.
The second issue he addresses is the separation of low-level and high-level details. Forty years ago, most algorithm books would include notes on memory allocation, simulating recursion with stacks, and a non-trivial amount of assembly. These days, programmers don’t think twice about recursion and most don’t even think about memory management. Yet many parallel libraries still require developers to “specify stack sizes for forked tasks, implement their own schedulers or specify scheduling policies, or understand mapping of memory to processors.”
Blelloch promotes Cilk++ as a good example of “separating the wheat from the chaff”. Of course other initiatives are also going in that direction such as Microsoft’s CCR/DSS, Parallel LINQ, Java’s fork-join framework and specialized languages like Erlang.
The third issue is that of determinism, also known as concurrent programming. Blelloch argues that non-deterministic code should be very rare, and where it exists, it should be hidden inside a component that is externally deterministic.
Unfortunately, this is where his argument falls flat. Systems that deal with external connections are inherently non-deterministic, both in sequence and in behavior. No amount of abstraction is going to change the fact that you cannot predict when, if at all, another player in a video game is going to move his character. Nor can you predict if a trader at your various partner companies is going to hit or pass on a particular stock offer.
Still, two things can be taken away from this essay. Schools really need to spend more time teaching students to think in terms of parallel algorithms and the next generation of libraries are showing great promise for parallel, though not concurrent, systems.