# Presentation: 009401

## A Crash Course in Supercomputing: MPI Programming Project

**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

**Project description**
**Programming concepts**
**Parallelization strategies**

## I. Project Description

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

## 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**

## 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**

## 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](http://www.phim.unibe.ch/comp_doc/c_manual/C/CONCEPT/data_types.html)**_