Which comes first: parallel languages or parallel programming patterns?

On the shuttle to the recent UPCRC (Universal Parallel Computation Research Center) Annual Summit meeting on the Microsoft campus in Redmond, WA, I was listening in on a discussion about parallel programming patterns.  Being a parallel programmer, I was interested in what people (and these were some of the experts in the field) had to say about parallel programming patterns, how they are evolving and how they will impact future parallel coders. The discussion turned to whether patterns would affect programming languages directly or remain something that would be constructed from statements of the language. I think I'm in the former camp. Here's why.

For those of us that were programming when Elvis was still alive, think back to writing with assembly language. For the most part, there were instructions for Load, Store, Add, Compare, Jump, plus some variations on these and other miscellaneous instructions. To implement a counting/indexing loop you would use something like the following:

      Initialize counter
LOOP: test end condition, goto EXIT if done
      Loop Body
      increment counter
      goto LOOP
EXIT: next statement


This is a programming pattern. (Surprised?) With the proper conditional testing and jumping (goto) instructions within the programming language, this pattern can be implemented in any imperative language.

Since this pattern proved to be so useful and pervasive in the computations being written, programming language designers added syntax to "automate" the steps above.  For example, the for-loop in C.

for (i = 0; i < N; ++i) {
   Loop Body


Once we had threads and the supporting libraries to create and manage threads, parallel coding in shared memory was feasible, but at a pretty crude level since the programmer had to be sure the code handled everything explicitly. For example, dividing the loop iterations among threads can be done with each thread executing code that looks something like this:

   start = (N/num_threads) * (myid)
   end = (N/num_threads) * (myid + 1)
   if (myid == LAST) end = N
   for (i = start; i < end; ++i) {
Loop Body


Parallel programming patterns will be abstractions that can be "crudely" implemented in current languages and parallel libraries, like the pseudocode above. New languages (or language extensions) will make programming parallel patterns easier and less error prone. From the example above, OpenMP has the syntax to do this, but it only takes a single line added to the serial code...

#pragma omp for
   for (i = 0; i < N; ++i) {
Loop Body


From the evidence above, I think future parallel programming languages or language extensions supporting parallelism will be influenced by the parallel programming patterns we define and use today. And nothing will remain static. Ralph Johnson (Design Patterns), during his presentation, remarked that some of the original patterns saw early use, but this use has slacked off. Two reasons he noted for this was that some of the patterns couldn't easily be implemented in Java and modern OO languages had better ways to accomplish the same tasks--most likely these new languages found inspiration from the patterns and their usage.

For an answer to the quesiton posed in the title it boils down (no pun intended) to the old chicken and egg paradox. There were algorithms (patterns) to do computations before there were computers; prior to that, those algorithms were modifications of previous algorithms influenced by the tools available. Looking forward, though, we're still in the relative stages of  infancy for programming, let alone parallel programming. Clearly, the next generation of parallel programming languages or libraries or extensions bolted onto serial languages will be influenced by the patterns we use now for specifying parallel computations.
For more complete information about compiler optimizations, see our Optimization Notice.