Sign up ×

How do you write pseudo-code for parallel programming? Especially, how do you differentiate local and shared variables? How do you represent operations like scatter, gather, reduce, broadcast, and point-to-point communications? Is there some standards about that?

share|improve this question

6 Answers 6

Pseudo code is pretty much just English. So, you can use whatever is clear and unambiguous. It's not a programming language, so you don't need to represent operations like "scatter" .. you can just say "scatter".

There are no standards for pseudo-code, but good pseudo-code is simple and easy to understand.

share|improve this answer
Since English isn't something parallel, I need a way to formalize parallel aspects of programming. That's why this answer doesn't satisfy me. – Charles Brunet Apr 23 '11 at 10:44
up vote 3 down vote accepted

I found at least one pseudolanguage for parallel programming: Peril-L. It is formal, but a little bit too low level for my taste.

share|improve this answer

Try "writing the diagrams" here:

You will end up with best of both worlds, fairly simple English statements ("pseudo code") and clean diagrams. I've been able to explain fairly complex parallel programming to my managers and peers using these diagrams. Last but not least, one can check in the diagram 'source' into the source control system.

share|improve this answer

This essay by Matthew Adams is probably the best introduction I've seen to walking through the multithreading process using a form of pseudocode.

share|improve this answer
Your link isn't available... – Charles Brunet Apr 23 '11 at 10:41
Still not available :( – stej Oct 18 '13 at 9:54

Have you considered taking a Behavior Driven Development approach? I recently put together a fairly complicated multiprocess/multicore piece of code using a BDD approach and found it very helpful. The best part of the approach was I could both describe everything in plain English and focus on the problem rather than the implementation details. My first few iterations were single threaded to ensure the code passed all the tests and solved the problem. I enhanced performance of the system by leveraging multiprocessing in selected places while making sure that it wouldn't break the tests the single-threaded system passed. Refactoring was much easier because the code was already significantly simpler than if I'd designed things around optimization design details prematurely and I could focus on monitoring processing times of the re-factored systems since I was getting exactly the same results as previous iterations.

Take a look at the book Test Driven Development for Embedded C for some ideas. I leveraged this book during my development and have made it a permanent part of my library.

share|improve this answer

The short answer to your question is that there is no conventional way to write pseudocode for parallel programming.

This is due to there being a variety of ways to do parallel programming, in terms of different parallel architectures (e.g. SMPs, GPUs, clusters, and other exotic systems) and parallel programming approaches. I refer to 'programming approaches' because, in general, most are libraries or annotations rather than languages (see MPI, OpenMP, TBB etc.). So, even if you can pick an architecture and language, you will have difficulty defining the semantics of a library or system of annotations.

Fortunately, more rigorously-defined programming approaches have been developed. However, they are generally based either on shared memory or message passing. Finding a suitable notation/pseudocode will depend on to what degree you require the semantics to be defined and what types of parallel programming problems you are trying to express.

Here are two suggestions:

  • PRAM. Shared-memory programming is closely related to the parallel random-access machine (PRAM) model of computation. This has been widely studied and many algorithms developed in it. A quick search of the literature will bring up suitable PRAM notations.
  • CSP. Communicating sequential processes (CSP) is a formalism (algebra) for expressing and reasoning about message-passing systems. It has been influential in the design of many languages, notably occam.

The PRAM model is very simple and should be used as a basis for shared-memory programming notations. CSP itself may be too mathematical for a pseudocode and the occam notation may be too verbose. This was the view of Brinch Hansen (a great in concurrent programming) who designed his own related language, SuperPascal, to be used as a notation for the explanation of parallel algorithms in publications.

To my knowledge, no other languages for parallel computing have been developed that can be defined in a rigorous way and/or are suitable to be used as a high-level notation.

share|improve this answer

Your Answer


