Structured Parallel Programming

By Michael McCool (Intel) (25 posts) on October 20, 2009 at 3:34 pm

One way of looking at parallel patterns (sometimes called algorithmic skeletons) is through an analogy with "structured programming". The premise of structured programming is that a small number of control flow and data management patterns can be composed to implement the necessary control flow and data access logic in most serial programs. There is some evidence (see, for example, work by Skillicorn, Campbell, Cole, and the Berkeley Dwarfs) that a relatively small number of patterns can also express the necessary task and data organization in a large fraction of parallel programs.

Back in the '70s there was a heated argument about structured vs. unstructured control flow. Basically, you can obviously do anything you want with a conditional goto, which is usually the only control flow construct made available in machine language. From the point of view of completeness, this is all a programming language really needs to support. However, many computer scientists noted that there were certain maintainability advantages to restricting control flow to the composition of a small number of patterns supporting iteration (do/while, repeat/until, for) and selection (if/then/else, switch) in high-level languages. It was also noted that certain patterns that made it easy to express common problem-solving techniques were useful. The most important of these is recursion, which supports the divide-and-conquer problem solving approach. Recursion is also usually associated with efficient stack-based memory allocation and deallocation (of course you can also replace iteration with recursion and still get a universal programming language) and more general but still tightly encapsulated dynamic memory allocation (if closures are supported). Proponents of the structured approach even designed programming languages around these patterns.

Of course the structured programming proponents won, and these days goto is a deprecated feature in most programming languages. Over time some additional patterns around data management were added, such as objects, but the number of basic computational patterns directly supported by most structured imperative languages is fairly low.

For parallel programming we are seeing the same evolution. Of course you can do anything you want using a basic thread library and vector intrinsics... but it's probably not a good idea to program at such a low level. Instead, some common repeatable patterns have emerged, and there are maintainability and even performance advantages to sticking to those patterns. I've blogged about a few of these patterns in the past, and will continue that series shortly (coming back and updating the hyperlinks from this blog as I go) but for the record here is a list of the patterns I've noted along with a short description of each:

Superscalar sequence: A sequence of functions only needs to be ordered by its data dependencies.
Speculative selection: A function can be speculatively executed before it is known if its result is needed.
Map: A function can be replicated an applied to all elements of a collection.
Recurrence: A multi-dimensional map with dependencies on neighbouring outputs in a causal neighbourhood.
Scan: A 1-dimensional recurrence with an associative operator.
Reduce: Pairwise combination of the elements of a collection with an associative operator.
Pack/split/expand: Variable-rate output from a map function.
Nest: Recursive nesting of other patterns combined with local data allocation.
Pipeline: Producer/consumer tasks with local state that can be serially updated.
Partition/segment:Collections can be divided into non-overlapping partitions that can be operated on independently.
Stencil: Overlapping neighborhoods can be accessed relative to output postions in a map.
Search/match: Input data and output locations can be selected using pattern matching.
Gather: A collection of input data can be accessed using a collection of indices.
Scatter: A collection of output locations can be updated using a collection of update values and locations.

These terse descriptions really don't do these patterns justice, but there are three points worth mentioning. First, these are "computation semantics specification" patterns. These patterns are primarily about specifying computations with minimal constraints on ordering but independent of exact timing or implementation mechanisms. If order and timing is in fact important, then an additional set of patterns may be needed, for example in user interfaces and real-time systems. There are also some other patterns not included here that are primarily about use of specific low-level mechanisms or optimizations rather than high-level intentions, for example the use of particular data layouts like SOA form to make it easier to vectorize computations. These "implementation" patterns can be accommodated in a programming system using pragmatics. Second, there are many variants and extensions of these patterns. Pipelines, for example, can come in many flavors. I will discuss some of these in my blogs. Third, and this is very interesting from a maintainability point of view, these patterns can all be given deterministic definitions. One troublesome pattern is scatter, but there are deterministic versions of even this pattern.

Please note that these patterns are NOT a feature list for any particular programming system. They are abstractions. Unfortunately few parallel programming systems directly support all these patterns simultaneously, and this list is probably not complete. However, this set of patterns can be used to discuss and evaluate programming platforms and how well they support particular classes of algorithms.