# Presentation: 169579

## A Crash Course in Supercomputing: MPI

**Rebecca Hartman-Baker**
**Oak Ridge National Laboratory**
_**[hartmanbakrj@ornl.gov](mailto:hartmanbakrj@ornl.gov)**_

- © 2004-2006 Rebecca Hartman-Baker.  Reproduction permitted for non-commercial, educational use only.

## Outline

**Parallelism**
**Supercomputer Architecture**
**MPI**
**Debugging and Performance Evaluation**

## I. Parallelism

**Concepts of parallelization**
**Serial vs. parallel**
**Parallelization strategies**

## Parallelization Concepts

**When performing task, some subtasks depend on one another, while others do not**
**Example: Preparing dinner**
**Salad prep independent of lasagna baking**
**Lasagna must be assembled before baking**
**Likewise, in solving scientific problems, some tasks independent of one another**

## Serial vs. Parallel

**Serial: tasks must be performed in sequence**
**Parallel: tasks can be performed independently in any order**

## Serial vs. Parallel: Example

**Example: Preparing dinner**
**Serial tasks: making sauce, assembling lasagna, baking lasagna; washing lettuce, cutting vegetables, assembling salad**
**Parallel tasks: making lasagna, making salad, setting table**

## Serial vs. Parallel: Example

**Could have several chefs, each performing one parallel task**
**This is concept behind parallel computing**

## Parallel Algorithm Design: PCAM

***P******artition:***** Decompose problem into fine-grained tasks to maximize potential parallelism**
***C******ommunication:***** Determine communication pattern among tasks**
***A******gglomeration:***** Combine into coarser-grained tasks, if necessary, to reduce communication requirements or other costs**
***M******apping:***** Assign tasks to processors, subject to tradeoff between communication cost and concurrency**

- (taken from *Heath: Parallel Numerical Algorithms*)

## Discussion: Jigsaw Puzzle*

**Suppose we want to do 5000 piece jigsaw puzzle**
**Time for one person to ****	****	****	****complete puzzle: *****n***** hours**
**How can we decrease wall ****	****	****	****time to completion?**

- * Thanks to Henry Neeman

## Discussion: Jigsaw Puzzle

**Add another person at the table**
**Effect on wall time**
**Communication**
**Resource contention**
**Add *****p***** people at the table**
**Effect on wall time**
**Communication**
**Resource contention**

## Discussion: Jigsaw Puzzle

**What about: *****p***** people,  *****p***** tables, *****5000/p***** pieces each?**
**What about: one person works on river, one works on sky, one works on mountain, etc.?**

## II. Supercomputer Architecture

**What is a supercomputer?**
**Conceptual overview of architecture**

- Cray (1976)

- IBM Blue Gene (2005)

- Architecture of IBM Blue Gene

## What Is a Supercomputer?

**“****The biggest, fastest computer right this minute.” -- Henry Neeman**
**Generally 100-10,000 times more powerful than PC**
**This field of study known as *****supercomputing,***** *****high-performance computing (HPC),***** or *****scientific computing***
**Scientists use really big computers to solve really hard problems**

## Architecture

**Two supercomputer construction paradigms**
**Build with specialized parts and custom design**
**E.g. Jaguar, Cray XT-3 at ORNL, 10th fastest supercomputer in the world**
**Build with regular computer parts connected together**
**E.g. Turing, XServe G5 at University of Illinois, 85th fastest supercomputer in the world**

- Jaguar

- Turing

## Cluster Architecture

**CPUs on racks, do computations (fast)**
**Communicate through myrinet connections (slow)**
**Want to write programs that divide computations evenly but minimize communication**
**How do we have communication in programs?**

## III. MPI

**Introduction to MPI**
**Parallel programming concepts**
**The Six Necessary MPI Commands**
**Example program**

## Introduction to MPI

**Stands for *****M*****essage *****P*****assing *****I*****nterface**
**Industry standard for parallel programming (200+ page document)**
**MPI implemented by many vendors; open source implementations available too**
**ChaMPIon-PRO, IBM, HP vendor implementations**
**MPICH, LAM-MPI, OpenMPI (open source)**
**MPI function library is used in writing C, C++, or Fortran programs in HPC**
**MPI-1 vs. MPI-2: MPI-2 has additional advanced functionality and C++ bindings, but everything learned today applies to both standards**

## Parallelization Concepts

**Two primary programming paradigms:**
**SPMD (single program, multiple data)**
**MPMD (multiple programs, multiple data)**
**MPI can be used for either paradigm**

## SPMD vs. MPMD

**SPMD: Write single program that will perform same operation on multiple sets of data**
**Multiple chefs baking many lasagnas**
**Rendering different frames of movie**
**MPMD: Write different programs to perform different operations on multiple sets of data**
**Multiple chefs preparing four-course dinner**
**Rendering different parts of movie frame**
**Can also write hybrid program in which some processes perform same task**

## The Six Necessary MPI Commands

**int MPI_Init(int *argc, char **argv)**
**int MPI_Finalize(void)**
**int MPI_Comm_size(MPI_Comm comm, int *size)**
**int MPI_Comm_rank(MPI_Comm comm, int *rank)**
**int MPI_Send(void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm)**
**int MPI_Recv(void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status)**

## Initiation and Termination

**MPI_Init(int *argc, char **argv)**** initiates MPI**
**Place in body of code after variable declarations and before any MPI commands**
**MPI_Finalize(void)**** shuts down MPI**
**Place near end of code, after last MPI command**

## Environmental Inquiry

**MPI_Comm_size(MPI_Comm comm, int *size)**** **
**Find out number of processes**
**Allows flexibility in number of processes used in program**
**MPI_Comm_rank(MPI_Comm comm, int *rank)**** **
**Find out identifier of current process**
**0 ******** ****rank**** ******** ****size****-1**

## Message Passing: Send

**MPI_Send(void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm)**
**Send message of length ****count**** bytes and datatype ****datatype**** contained in ****buf**** with tag ****tag**** to process number ****dest**** in communicator ****comm**
**E.g. ****MPI_Send(&x, 1, MPI_DOUBLE, manager, me, MPI_COMM_WORLD)**

## Message Passing: Receive

**MPI_Recv(void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status)**
**Receive message of length ****count**** bytes and datatype ****datatype**** with tag ****tag**** in buffer ****buf**** from process number ****source**** in communicator ****comm**** and record status ****status**
**E.g. ****MPI_Recv(&x, 1, MPI_DOUBLE, source, source, MPI_COMM_WORLD, &status)**

## Message Passing

**WARNING! Both standard send and receive functions are *****blocking***
**MPI_Recv**** returns only after receive buffer contains requested message**
**MPI_Send**** may or may not block until message received (usually blocks)**
**Must watch out for deadlock**

## Deadlocking Example (Always)

**#include <mpi.h>**
**#include <stdio.h>**
**int main(int argc, char **argv) {**
**    ****int me, np, q, sendto;**
**    ****MPI_Status status;**
**    ****MPI_Init(&argc, &argv);**
**    ****MPI_Comm_size(MPI_COMM_WORLD, &np);**
**    ****MPI_Comm_rank(MPI_COMM_WORLD, &me);**
**    ****if (np%2==1) return 0;**
**    ****if (me%2==1) {sendto = me-1;}**
**    ****else {sendto = me+1;}**
**    ****MPI_Recv(&q, 1, MPI_INT, sendto, sendto, MPI_COMM_WORLD, &status);**
**    ****MPI_Send(&me, 1, MPI_INT, sendto, me, MPI_COMM_WORLD);**
**    ****printf(“Sent %d to proc %d, received %d from proc %d\n”, me, **
**	****	****sendto, q, sendto);**
**    ****MPI_Finalize();**
**    ****return 0;**
**}**

## Deadlocking Example (Sometimes)

**#include <mpi.h>**
**#include <stdio.h>**
**int main(int argc, char **argv) {**
**    ****int me, np, q, sendto;**
**    ****MPI_Status status;**
**    ****MPI_Init(&argc, &argv);**
**    ****MPI_Comm_size(MPI_COMM_WORLD, &np);**
**    ****MPI_Comm_rank(MPI_COMM_WORLD, &me);**
**    ****if (np%2==1) return 0;**
**    ****if (me%2==1) {sendto = me-1;}**
**    ****else {sendto = me+1;}**
**    ****MPI_Send(&me, 1, MPI_INT, sendto, me, MPI_COMM_WORLD);**
**    ****MPI_Recv(&q, 1, MPI_INT, sendto, sendto, MPI_COMM_WORLD, &status);**
**    ****printf(“Sent %d to proc %d, received %d from proc %d\n”, me, **
**	****	****sendto, q, sendto);**
**    ****MPI_Finalize();**
**    ****return 0;**
**}**

## Deadlocking Example (Safe)

**#include <mpi.h>**
**#include <stdio.h>**
**int main(int argc, char **argv) {**
**    ****int me, np, q, sendto;**
**    ****MPI_Status status;**
**    ****MPI_Init(&argc, &argv);**
**    ****MPI_Comm_size(MPI_COMM_WORLD, &np);**
**    ****MPI_Comm_rank(MPI_COMM_WORLD, &me);**
**    ****if (np%2==1) return 0;**
**    ****if (me%2==1) {sendto = me-1;}**
**    ****else {sendto = me+1;}**
**    ****if (me%2 == 0) {**
**        ****MPI_Send(&me, 1, MPI_INT, sendto, me, MPI_COMM_WORLD);**
**        ****MPI_Recv(&q, 1, MPI_INT, sendto, sendto, MPI_COMM_WORLD, &status);**
**	****} else {**
**        ****MPI_Recv(&q, 1, MPI_INT, sendto, sendto, MPI_COMM_WORLD, &status);**
**        ****MPI_Send(&me, 1, MPI_INT, sendto, me, MPI_COMM_WORLD);**
**    ****}**
**    ****printf(“Sent %d to proc %d, received %d from proc %d\n”, me, sendto, q, ****	****	****sendto);**
**    ****MPI_Finalize();**
**    ****return 0;**
**}**

## Explanation: Always Deadlock Example

**Logically incorrect**
**Deadlock caused by blocking ****MPI_Recv****s**
**All processes wait for corresponding ****MPI_Send****s to begin, which never happens**

## Explanation: Sometimes Deadlock Example

**Logically correct**
**Deadlock could be caused by ****MPI_Send****s competing for buffer space**
**Unsafe because depends on system resources**
**Solutions:**
**Reorder sends and receives, like safe example, having evens send first and odds send second**
**Use non-blocking sends and receives or other advanced functions from MPI library (beyond scope of this tutorial)**

## IV. Debugging and Performance Evaluation 

**Common errors in parallel programs**
**Debugging tools**
**Overview of benchmarking and performance measurements**

## Common Errors

**Program hangs**
**Send has no corresponding receive (or vice versa)**
**Send/receive pair do not match in source/recipient or tag**
**Condition you believe should occur does not occur**
**Segmentation fault**
**Trying to access memory you are not allowed to access/ memory you should not have been allowed to access has been altered (e.g. array index out-of-bounds, uninitialized pointers, using non-pointer as pointer)**
**Trying to access a memory location in a way that is not allowed (e.g. overwrite a read-only location)**

## Debugging Tools

**Debugging parallel codes is particularly difficult**
**Problem: figuring out what happens on each node**
**Solutions:**
**Print statements, I/O redirection into files belonging to each node**
**Debuggers compatible with MPI**

## Print Statement Debugging Method

**Each processor dumps print statements to ****stdout**** or into individual output files, e.g. ****log.0001****, ****log.0002****, etc.**
**Advantage: easy to implement, independent of platform or available resources**
**Disadvantage: time-consuming, extraneous information in log files**

## MPI-Compatible Debuggers

**TotalView**
**Commercial product, easy-to-use GUI**
**Installed on production systems such as Crays, probably not installed on local machines**
**Free debuggers + mpirun**
**Use ****mpirun**** command and specify your favorite debugger, e.g. ****mpirun -dbg=ddd -np 4 ./myprog**
**This option available with MPICH and most other MPI implementations**
**Not as “pretty” as TotalView but it gets job done**

## Bibliography/Resources: Programming Concepts and Debugging

**Heath, Michael T. (2006) *****Notes for CS554: Parallel Numerical Algorithms,***** **_**[http://www.](http://www.cse.uiuc.edu/cs554/notes/index.html)**__**[cse](http://www.cse.uiuc.edu/cs554/notes/index.html)**__**[.](http://www.cse.uiuc.edu/cs554/notes/index.html)**__**[uiuc](http://www.cse.uiuc.edu/cs554/notes/index.html)**__**[.edu/cs554/notes/index.html](http://www.cse.uiuc.edu/cs554/notes/index.html)**_
**MPI Deadlock and Suggestions **_**[http://www.ncsa.uiuc.edu/UserInfo/Resources/Hardware/CommonDoc/MessPass/MPIDeadlock.html](http://www.ncsa.uiuc.edu/UserInfo/Resources/Hardware/CommonDoc/MessPass/MPIDeadlock.html)**_
**TotalView Tutorial **_**[http://www.](http://www.llnl.gov/computing/tutorials/totalview/)**__**[llnl](http://www.llnl.gov/computing/tutorials/totalview/)**__**[.](http://www.llnl.gov/computing/tutorials/totalview/)**__**[gov/computing/tutorials/totalview/](http://www.llnl.gov/computing/tutorials/totalview/)**_
**Etnus TotalView page **_**[http://www.](http://www.etnus.com/)**__**[etnus](http://www.etnus.com/)**__**[.com/](http://www.etnus.com/)**_

## Bibliography/Resources: MPI

**Snir, Marc, Steve W. Otto, Steven Huss-Lederman, David W. Walker, and Jack Dongarra. (1996) *****MPI:The Complete Reference.***** Cambridge, MA: MIT Press. (also available at **_**[http://www.netlib.org/utk/papers/mpi-book/mpi-book.html](http://www.netlib.org/utk/papers/mpi-book/mpi-book.html)**_**)**
**MPICH Documentation **_**[http://www-unix.mcs.anl.gov/mpi/mpich/](http://www-unix.mcs.anl.gov/mpi/mpich/)**_
**C, C++, and FORTRAN bindings for MPI-1.2***** ***_***[http://www.lam-mpi.org/tutorials/bindings/](http://www.lam-mpi.org/tutorials/bindings/)***_