Parallel algorithm for calculating pi


Description of Problem

  1. Picture a circle with radius 1 centered at the origin.

  2. The circle sits inside a square whose corners are at (-1,-1), (-1,1), (1,1) and (1,-1).

  3. The area of the circle divided by the area of the square is pi/4. (pi * r * r/4*r *r )

  4. Think of this as a dartboard.

  5. The darts hit at x and y coordinates which are random numbers between -1 and 1.

  6. Darts must fall within the square, and may also fall within the circle.

  7. The program approximates the value of pi by dividing the number of darts that fall within the circle by the total darts thrown, and multiplying by four.


Psuedocode for serial execution:
darts =5000
circle_count = 0

do j = 1,darts
generate 2 random numbers between 0 and 1
xcoordinate = random1 ; ycoordinate = random2
if (xcoordinate, ycoordinate) inside circle
then circle_count = circle_count + 1
end do

PI = 4.0*circle_count/darts
Repeat this 500000 times and calculate the average value of pi.

Parallel Implementation

There are two ways to benefit from parallelism: you may run the same program in less time, or run a larger program in the same amount of time. This example takes the former approach.
The serial calculation of pi involves throwing 5000 darts for each of 500000 iterations, with the cumulative average reported at each iteration. For the parallel implementation, each task performs this process for a given number of iterations, reporting the the calculated pi to the master task , which calculates the cumulative average for 500000 iterations. The more tasks that participate, the more faster the calculation completes. The number iterations wil be equally divided among the tasks.

Psuedocode for parallel execution:

Each node executes this code for a specified number of times and writes the value of calculated pi into a file


darts =5000
circle_count = 0
do j = 1,darts
generate 2 random numbers between 0 and 1
xcoordinate = random1 ; ycoordinate = random2
if (xcoordinate, ycoordinate) inside circle
then circle_count = circle_count + 1
end do

PI = 4.0*circle_count/darts
Aggreagator function averages the pi values .
Source code
The source code for the example is available(in zipped format) here

Steps to install and run Vishwa ,are available in the UserGuide section of the Home page.Once you have Vishwa running on few nodes ,do the following steps to run this application on top of Vishwa:

1.Run the "automaticsplititng.c" (the you would have received in the downloaded folder) program and enter the number of splits to divide the input range into.This program will automatically generate the metafile or you with name "meta".

2.Your meta file will look as below.

5
1
rounds1.txt
rounds2.txt
rounds3.txt
rounds4.txt
rounds5.txt


3.Run ./user on any node and give ipadress of existing grid node Please enter the following details when asked for:

Enter the Path of the MetaData file name:
meta
Enter the Path of the Task file name:
piparallel.c
Enter the no of splits:
5
Enter the outputfilename:
result.txt
Enter the aggregate method file name:
aggregate.c

4.Run the program and view the results displayed on the screen after the completion of calculation.

Any further assistance regarding this please mailto:suneetha@cs.iitm.ernet.in