# Presentation: 244993

## A Crash Course in Supercomputing: MPI Programming Project

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

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

## Outline

**Project description**
**Programming concepts**
**Parallelization strategies**
**Doing this project at ORNL**

## I. Project Description

**We want to compute ******
**One method: method of darts***
**Ratio of area of square to area of inscribed circle proportional to ******

****Disclaimer: this is a ***_***TERRIBLE***_*** way to compute ************.  Don’t even think about doing it this way except for the purposes of this project!***

## Method of Darts

**Imagine dartboard with circle of radius ***R ***inscribed in square**
**Area of circle**
**Area of square**
_**Area of circle **_
**   ****Area of square**

## Method of Darts

**So, ratio of areas proportional to ******
**How to find areas?**
**Suppose we threw darts (completely randomly) at dartboard**
**Could count number of darts landing in circle and total number of darts landing in square**
**Ratio of these numbers gives approximation to ratio of areas**
**Quality of approximation increases with number of darts**
****** ****= 4 ******** **_**# darts inside circle**_
**                    ****# darts thrown**

## Method of Darts

**Okay, Rebecca, but how in the world do we simulate this experiment on computer?**
**Decide on length ***R*
**Generate pairs of random numbers ***(x, y)*** s.t. ****	****	***-R ≤ x, y ≤ R*
**If ***(x, y)*** within circle (i.e. if ***(x**2**+y**2**) ≤ R**2***), add one to tally for inside circle**
**Lastly, find ratio**

## II. Programming Concepts

**Random numbers: in C language, function ****int rand(void)**** generates “pseudo-random integer in range 0 to ****RAND_MAX****”**
**RAND_MAX****: C-language constant denoting maximum random number generated; actual value varies with implementation**
**Divide “random” number by maximum random number to get a number between 0 and 1***

****Disclaimer: this is a ***_***TERRIBLE***_*** way to compute a pseudorandom number.  Don’t even think about doing it this way except for the purposes of this project!***

## Programming Concepts

**Type cast and coercion:**
**int a = rand(); double b = a/RAND_MAX;**
**b**** equals 0**
**int a = rand(); double b = ((double) a)/((double) RAND_MAX);**
**b**** equals correct value**
**Type conversion rules:**
**int/int ******** int**
**int/double ******** double**
**double/int ******** double**
**double/double ******** double**

## Programming Concepts

**Numbers generated by ****rand()**** not really random; same sequence every time**
**Change seed for random number generator with ****void srand(unsigned int seed)**
**Datatypes:**
**For a lot of darts, need larger datatype than ****int**** or risk overflow**
**On some computers (varies by platform):**

| Data Type | Range |
| --- | --- |
| int | -32,768 — +32,767 |
| long int | -2,147,483,648 — +2,147,483,648 |
| unsigned long int | 0 — +4,294,967,295 |

## III. Parallelization Strategies

**What tasks independent of each other?**
**What tasks must be performed sequentially?**
**Using PCAM parallel algorithm design strategy**

## Partition

***“******Decompose problem into fine-grained tasks to maximize potential parallelism”***
**Finest grained task: throw of one dart**
**Each throw independent of all others**
**If we had huge computer, could assign one throw to each processor**

## Communication

***“******Determine communication pattern among tasks”***
**Each processor throws dart(s) then sends results back to manager process**

## Agglomeration

***“******Combine into coarser-grained tasks, if necessary, to reduce communication requirements or other costs”***
**To get good value of ********, must use millions of darts**
**We don’t have millions of processors available**
**Furthermore, communication between manager and millions of worker processors would be very expensive**
**Solution: divide up number of dart throws evenly between processors, so each processor does a share of work**

## Mapping

***“******Assign tasks to processors, subject to tradeoff between communication cost and concurrency”***
**Assign role of “manager” to processor 0**
**Processor 0 will receive tallies from all the other processors, and will compute final value of ******
**Every processor, including manager, will perform equal share of dart throws**

## IV. Doing This Project at ORNL

**Today: on cheetah (4.5 TF IBM pSeries)**
**Later: using other resources**

## Connecting to Cheetah

**You need ssh client on your machine**
**Windows: download PuTTY: http://www.chiark.greenend.org.uk/~sgtatham/putty/**
**Mac: use terminal: Applications > Utilities > Terminal**
**Linux: open up a shell**
**Then, ssh to cheetah:**
**ssh hqi@cheetah.ccs.ornl.gov**
**Upon first login to new system, will be asked to accept authenticity of new machine (type ****yes****)**
**Enter your passcode: **
**(if not guest account) using your RSA SecurID, enter your PIN followed by 6-digit code shown on keyfob**
**(if guest account) enter passcode shown on whiteboard**

## Cheetah: Environment

**Cheetah consists of 27 p690 nodes, each with 32 1.3 GHz Power4 processors**
**Cheetah has IBM compilers, batch system, etc.**
**Compiler: ****mpcc**** (for C), ****mpCC**** (for C++)**
**Batch system: LoadLeveler**
**llsubmit myscript**** (submit ****myscript**** to queue)**
**llq**** (check status of current jobs)**
**llcancel *****<jobname>***** (cancel job *****<jobname>*****)**
**Parallel job launcher: ****poe**** (like ****mpirun**** or ****mpiexec**** on most systems)**

## Cheetah: Sample Script

**#@ shell = /bin/csh**
**#@ job_type = parallel**
**#@ network.MPI = csss,shared,US**
**#@ output = $(host).$(jobid).out**
**#@ error = $(host).$(jobid).err**
**#@ wall_clock_limit = 10:00**
**#@ tasks_per_node = 32****	*****(maximum is 32)***
**#@ node = 2****	*****(32 tasks x 2 nodes = 64 processors)***
**#@ queue**
**pwd**
**echo $LOADL_PROCESSOR_LIST**
**setenv MP_SHARED_MEMORY yes**
**poe myprog**

## Project Procedure

**Make directory for project, e.g. ****mkdir darts**
**Copy and paste skeleton code into main code file, e.g. ****main.cc**
**Write code, write makefile, edit/correct/improve code, compile final code, write job script, launch job!**

## Doing the Project Later

**Desktop machine:**
**Can install MPICH on any Linux box or Mac**
**Freely available from ****	****	****	****http://www-unix.mcs.anl.gov/mpi/**
**To install: need root access and gcc (or other) compiler suite**
**Machine “pretends” to have multiple processors**
**Suitable for code development, but not for production**
**Institutional Cluster: **
**oic.ornl.gov****: Check to see if your mentor can give you access to this machine**
**For more details on machine, see http://oic.ornl.gov/**

## Bibliography/Resources

**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)**_
**Kernighan, Brian W. and Dennis M. Ritchie.  *****The C Programming Language, 2nd ed.*****  Upper Saddle River, NJ: Prentice-Hall, 1988.**
**C: The float and double Data Types and the sizeof Operator **_**[http://www.iota-six.co.uk/c/b3_float_double_and_sizeof.asp](http://www.iota-six.co.uk/c/b3_float_double_and_sizeof.asp)**_
**C Data types http://www.phim.unibe.ch/comp_doc/c_manual/C/CONCEPT/data_types.html**
**Cheetah at NCCS http://info.nccs.gov/resources/other_resources/cheetah**

## Appendix: Better Ways to Compute 

**Look it up on the internet, e.g. http://oldweb.cecm.sfu.ca/projects/ISC/data/ pi.html**
**Compute using the BBP (Bailey-Borwein-Plouffe) formula**
**For less accurate computations, try your programming language’s constant, or quadrature or power series expansions**

## Appendix: Better Ways to Generate Pseudorandom Numbers

**For serial codes**
**Mersenne twister**
**GSL (Gnu Scientific Library), many generators available (including Mersenne twister) http://www.gnu.org/software/gsl/**
**For parallel codes**
**SPRNG, regarded as leading parallel pseudorandom number generator http://sprng.cs.fsu.edu/**
**PPRNG, Bill Cochran’s new parallel pseudorandom number generator, supposedly superior to SPRNG http://runge.cse.uiuc.edu/~wkcochra/pprng/**