Writing pseudocode for parallel programming

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?

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.

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

Try "writing the diagrams" here: http://www.websequencediagrams.com/

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.

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.

After some web research, I have realized that a kind of "standard" still does not exits. As @Larry Watanabe says, "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"."

So here my personal solution using algorithm2e: there are no so many details on "shared memory", "local variable" etc.. but, with the same strategy, you can find a way of describing your idea:

\usepackage[linesnumbered,ruled,vlined]{algorithm2e}
...
\begin{algorithm}
    \DontPrintSemicolon 
    \SetKwBlock{DoParallel}{do in parallel}{end}
    \KwIn{Some inputs}
    \KwOut{The ouput}
    \DoParallel{
        Compute a \;
        Compute b \;
        Compute c \;
    }
    \DoParallel{
        a1\;
        b1\;
        c1\;
    }
    \Return{the solution}\;
    \caption{Parallel Algo}
    \label{algo:parallelAlgorithm}
\end{algorithm}

The result is:

It is based on defining a new command using the expression \SetKwBlock. The manual of the packege can be found here. I originally posted the answer to this question also here.

Using the strategy of defining your key words in order to describe your algorithm with the details you prefer, it should be always possible. Take in consideration that:

1. more details → more you will be close to your programming languages.
2. less details → more it can be seen as a pseudo-code.

Concluding: it is always a matter of trade-offs: you decide where is the limit (taking into account the target people you refer to).

The same strategy has been used in journal papers (for instance, see Algorithm 3 and 4 of this IEEE paper).

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

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.