Writing pseudocode for parallel programming

Question

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?

Solution 1

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

Solution 2

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.

Solution 3

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.

Solution 4

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.

Solution 5

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).

View more solutions