7/28/2012 3:02 PM EDT

More...

7/4/2012 12:34 AM EDT

More...

ParaSail: Less is more with multicore

What are the impediments to easy parallel programming? With apologies to David Letterman, we would identify the following as the biggest impediments to doing things efficiently and safely in a highly parallel multicore world:

* Global Variables
* Garbage-Collected Global Heap
* Parameter Aliasing
* Run-Time Exception Handling
* Explicit Threads
* Explicit Lock/Unlock
* Explicit Wait/Signal
* Race Conditions
and worst of all …
* Pointers

In what sense are these impediments, and how do we avoid them?

ParaSail (Parallel Specification and Implementation Language) [1] is a new parallel programming language with a familiar class-and-interface-based object-oriented programming model, but designed specifically to eliminate impediments to easy parallel programming.

In ParaSail, it is easier to write parallel algorithms than sequential ones. If sequential execution is needed, the programmer has to work harder. The default execution semantics are parallel. Pointers are eliminated in favor of expandable and shrinkable objects.

Race conditions are eliminated at compile-time, as are other possible run-time errors such as use of null values or uninitialized data, indexing outside of an array, numeric overflow, dangling references, etc. The net effect is a language that feels familiar, is a pleasure to program in, but nevertheless results in highly parallel, race-condition-free, well-structured programs.

Here is a simple recursive ParaSail function which counts the number of words in a string S, using Separators as the set of characters that separate one word from another:

Click on image to enlarge.

One interesting thing about this ParaSail function is that it doesn't appear to be explicitly parallel, but in fact the basic semantics of ParaSail imply that the two recursive calls of Word_Count used to initialize the value of Sum can in fact be evaluated in parallel.

Those recursive calls then continue the divide-and-conquer approach to counting the words in the string, with the net effect that for a string of length N, N picothreads are spawned, with their results added together in a computation tree of depth log2(N), providing a potential speedup of order N/log2(N) relative to a sequential algorithm.

In the remainder of this article we will go through each of the impediments mentioned above, discuss the problems they create, and illustrate how parallel programming in ParaSail is simplified by doing without them.