Fats : Programming : Parallel Programming

Concepts in Parallel Programming

Parallel Programming in Distributed Memory and in Shared Memory Machines

The basic idea of parallel programming consists in decomposing an algorithm into parts or computations that can be performed independently by different processors, and assigning those separate tasks to different processors. Often times some of the data computed by one processor is required by another processor, to complete its own computation. Hence, in a parallel algorithm, the processors have to coordinate with each other, to ensure that the required data is available timely to those processors that need it.

When all processors share a single pool of memory, this process coordination is enough to ensure that the computation is done correctly. However, if each processor has its private pool of memory, besides coordinating with others, it also needs to communicate its results to others, otherwise the parallel computation cannot proceed. Machines that have a single pool of memory, accessible by all of its processors, are called shared memory machines. Machines that have private memory for each processor, not directly accessible by other processors, are called distributed memory machines. In shared memory machines, once it is computed by one processor, data becomes readily and directly available to all other processors from the single pool of memory. By contrast, in distributed memory machines, a first processor cannot access the data that was computed by and is resident in a second processor's private memory, unless that second processor communicates its data to the first.

Hence, in shared memory machines, parallel programming requires three basic conditions: 1) the algorithm should be decomposed into independent tasks; 2) those tasks should be assigned to separate processors; and 3) the processors need to coordinate their activity. However, in distributed memory machines, besides the three conditions listed above, parallel programs require also a fourth condition: 4) processors must communicate their results to each other, whenever the other processors require these results.

The good news about shared memory machines is that it is easier to write parallel programs for them, because the programming requirements are less. The bad news about shared memory machines it that single large pools of memory are expensive, and the channels to reach this memory are expensive proprietary hardware, which makes the machines themselves also expensive.

The good news about distributed memory machines is that they can be built from off-the-shelf commodity hardware. Hence, they are relatively cheap. The bad news about distributed memory machines is that they are harder to program, because of the additional requirement of communication among processors.

Fats is a 32-node Beowulf cluster. The nodes are standard PCs, with their own processors and private memory, connected to each other by a network called Myrinet , which is dedicated to the communication among the nodes. Hence, fats is a distributed memory machine. (See our resources or more details about fats' hardware.)

However, each of fats' nodes is a dual processor PC, with a single, yet modest, 1GB pool of memory shared by these two processors. Hence, in this restricted sense, each of fats' nodes is also a mini- shared memory machine.

Therefore, the good news here is that on fats you can experiment with parallel programs written for both distributed memory and for shared memory machines. You can even play around with programs that explore both parallel programming models simultaneously, if you dare to!

The dominant parallel programming model paradigm in distributed memory machines today is the Message Passing Interface ( MPI ). MPI is a library of functions with interfaces (a.k.a. bindings) to the dominant scientific programming languages: Fortran (77 and 90), C and C++. Several implementations of MPI have been developed by computer vendors, but our preferred one, available free from Argonne National Laboratory ( ANL ) is MPICH . For several technical reasons related to hardware and software support, the current version of MPICH on fats is MPICH-1 , not the latest standard is MPICH-2 . However, most of the parallel programming functionality is present in MPICH-1.

The MPICH version we have on fats is called MPICH-GM, and it is a port of ANL's MPICH-1, optimized for the Myrinet network, and provided free by Myricom . MPICH-GM utilizes a lower level Myrinet communication library library called GM . (Note: This is by contrast with other implementations of MPICH that utilize the Ethernet hardware, called in general MPICH-P4.)

The dominant parallel programming model paradigm in distributed memory machines today is OpenMP . OpenMP is an industry standard multi-platform application program interface (API) implemented through pre-processor directives added to what is otherwise serial (i.e. non-parallel) Fortran, C, or C++ code. A number of modern compilers do understand these OpenMP directives, and can generate parallel code for shared memory machines when the appropriate compilation flag is used. In particular, the PGI compilers, available on fats, have this OpenMP capability.

Parallel Programming resources and tutorials

1. The IEEE maintains the (very technical) Parascope parallel processing site.

2. The University of Kent at Canterbury keeps an Internet Parallel Computing Archive .

3. NPACI's Parallel Computing Portal ( PCOMP ).

4. Lawrence Livermore National Lab put together this nice parallel computing tutorial .

5. Here is yet another tutorial in parallel processing from the Maui High Performance Computing Center at the University of Hawaii.

Parallel Programming books

1. Ian Foster, Desigining and Building Parallel Programs , Addison-Wesley, Reading, MA, 1995.
   Ian Foster's book is available online , along with several other great materials on the same subject.

2. Timothy G. Mattson, Beverly A. Sanders, and Berna L. Massingill, Patterns for Parallel Programming Addison-Wesley, Reading, MA, 2004.

MPI

MPI resources and tutorials

1. Argonne National Lab maintains the main MPI , MPICH-1 , and MPICH-2 web sites, with a rich suite of standards, documentation, manuals, tutorials, links, etc.

2. Myricom has additional (and quite technical) documentation on the GM library.

3. Several MPI tutorials are available from Argonne National Lab, which developed and maintains MPICH.

4. Another group of MPI tutorials , long and short, is available from the National Center for Supercomputing Applications (NCSA). These NCSA tutorials are based on a version of MPI developed at NCSA, called LAM-MPI. However, both LAM-MPI and MPICH follow the MPI standard, and there must be no difference between LAM-MPI and MPICH from the programming standpoint.

5. A short beginner MPI tutorial is provided by the Lawrence Livermore National Lab (LLNL). LLNL also has an advanced MPI tutorial .

MPI books

1. Peter Pacheco, Parallel Programming with MPI , Morgan Kaufmann, San Francisco, CA, 1996.
   Peter Pacheco maintains a web site for this book, with errata, some useful links, and a downloadable compressed PostScript version of a previous draft of the book, called A User's Guide to MPI .

2. William Gropp, Ewing Lusk, and Anthony Skjellum, Using MPI - 2nd Edition , The MIT Press, Cambridge, MA, 1999.

3. William Gropp, Ewing Lusk, and Rajeev Thakur, Using MPI-2 , The MIT Press, Cambridge, MA, 1999.

4. Marc Snir et al., MPI: The Complete Reference (Vol. 1) - 2nd Edition , The MIT Press, Cambridge, MA, 1998.
   The full online version of the 1st. edition is available from NetLib, and in pdf format .

5. William Gropp et al., MPI: The Complete Reference (Vol. 2) - The MPI-2 Extensions , The MIT Press, Cambridge, MA, 1998.

SPMD & MPMD

Most MPI programs are written as single program multiple data (SPMD). However, for very large computations (e.g. a coupled climate model), the executable may become too big to fit the available memory on a node. This is particularly critical if one tries to allocate memory at compile time (static memory), which leads to faster executables, instead of using the more flexible, but less efficient, dynamic memory allocation.

A solution is to launch different executables to perform different parts of the computation. In a coupled climate model, for instance, this is very convenient, as often times each component was developed as a separate program: one program for the atmosphere, another for the ocean, another for the land surface, and so on.

This model of multiple programs cooperating in parallel to perform a computation is called multiple program multiple data (MPMD). MPMD programs are supported by the MPI standard. However, most implementations of the mpi program launcher (mpirun) don't handle MPMD programs properly.

This was the case with the original version of mpirun we had on fats. However, we have rewritten fats' mpirun to handle MPMD programs correctly, and have been using it successfully to run the large MPMD CCSM3 coupled climate model from NCAR .

If you want to run MPMD programs on fats, please contact Gus Correa .

OpenMP

OpenMP resources and tutorials

1. The official OpenMP web site has a number of programming resources, the OpenMP specification, links to tutorials, etc. Check in particular their resources and sample programs links.

2. Lawrence Livermore National Lab has a comprehensive OpenMP tutorial .

3. A recent (2005) presentation style tutorial by Rudd van der Pas, from Sun Microsystems.

4. This 2002 presentation style tutorial is authored by Gabriel Mateescu, from the National Research Council Canada.

5. Here is a short OpenMP tutorial from Boston University.

OpenMP books

1. Rohit Chandra et al., Parallel Programming in OpenMP , Morgan Kaufmann, San Francisco, CA, 2001.

2. Michael J. Quinn, Parallel Programming in C with MPI and OpenMP , McGraw-Hill, Boston, MA, 2003.