Is Parallel Programming Hard? Prof. Guy Blelloch Argues That It Isn’t

Posted by Jonathan Allen on Apr 21, 2009

Sections

Development,

Architecture & Design

Topics

.NET ,

Performance & Scalability

Tags

Concurrency ,

Parallel Programming

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.

1. Back to top

   Oversimplification?

   by Maciek Makowski

   Members of academia sometimes seem tempted to claim that something considered difficult is in fact easy. Not long ago Peter Van Roy argued that shared-memory concurrency is a solved problem and the solution is dataflow programming; see www.info.ucl.ac.be/~pvr/vanroy-mc-panel.pdf. An interesting discussion that ensued on LtU shows it is a controversial claim: lambda-the-ultimate.org/node/2874.
   
   For the sake of making a point, short essays like Blelloch's or Van Roy's do tend to oversimplify matters and gloss over some issues that would be addressed in a proper scientific paper. I suspect that "determinism" remark would require some more clarification.

   Reply

2. Back to top

   Determinism

   by James Reinders

   When speaking of determinism in a parallel program, one can assume it is implied "given the same inputs." Sources of non-determinism in parallel programs most often come from race conditions, where a synchronization is missing and the program becomes potentially dependent on things other than the inputs the programmer intended. A non-deterministic program can be incredibly difficult to debug, since it is relatively unpredictable.

   Reply

• Older >