f



calculating PI with a parallel algorithm

Hello all,

I have got the pseudo-code below that I would like to convert to c
language (or maybe java). The algorithm calculates Pi value. I am
somewhat
familiar with C language, but I am just starting to learn parallel
programming.
In this specific example, the idea seems to be simple: one must
subdivide the main loop into pieces that can be executed by
independent "tasks" (computers??).

Then, each "worker task"  executes a part of the loop a certain
number
of times, independently of the other worker tasks. One specific task
plays the role of "master task", which will collect and sum the
results of the worker tasks:

% descriptive algorithm:
1. Inscribe a circle inside a square
2. Generate random points inside the square
3. Determine the number of points that fell inside the circle
4. Let r be the number of points inside the circle divided by the
total number of points
5. Pi is approximately equal to 4*r
6. The more points are generated, the more is the precision in P
value


% pseudo-code (parallel):
1. npoints = 10000
2. circle_count = 0
3. p = number of tasks
4. num = npoints/p
5. find out if I am MASTER or WORKER
6. do j = 1,num
7. generate 2 random numbers between 0 and 1
8. xcoordinate = random1
9. ycoordinate = random2
10. if (xcoordinate, ycoordinate) inside circle then
circle_count = circle_count + 1
11. end do
12. if I am MASTER
13. receive from WORKERS their circle_counts
14. compute PI (use MASTER and WORKER calculations)
15. else if I am WORKER
16. send to MASTER circle_count
17. endif

My (understading) problem starts in the line 5 of the pseudo-code:
"5. find out if I am MASTER or WORKER"
How would I specificy a "worker"? Would that be another computer?
If yes, how can I access this remote computer in the calculations, in
C or JAVA?
If yes, it means that I have to have a LAN or something to perform
tests?
I have found that there are some libraries such as OMP or MPI that
could be used, but I'd like to know if there is a more "raw" way of
doing this first.

Any help would be much appreciated.

I thank you all in advance.

(I was advised for someone in comp.lang.c to post this question here
or some similar group, instead of in comp.lang.c).
0
epleite (73)
5/13/2008 7:10:19 PM
comp.parallel.mpi 1534 articles. 0 followers. kisitanggang (69) is leader. Post Follow

4 Replies
2693 Views

Similar Articles

[PageSpeed] 58

In article <20f2ce18-e8a8-4966-8003-9b69890a2a7d@d1g2000hsg.googlegroups.com>,
Prime Mover  <epleite@hotmail.com> wrote:

>I have got the pseudo-code below that I would like to convert to c
>language (or maybe java).

The problem and algorithm you describe are available with most MPI
implementations as an example program. Try googling "mpi pi".

>(I was advised for someone in comp.lang.c to post this question here
>or some similar group, instead of in comp.lang.c).

Rude, aren't they?

-- greg




0
lindahl
5/13/2008 7:22:23 PM
On May 13, 2:10 pm, Prime Mover <eple...@hotmail.com> wrote:
> Hello all,
>
> I have got the pseudo-code below that I would like to convert to c
> language (or maybe java). The algorithm calculates Pi value. I am
> somewhat
> familiar with C language, but I am just starting to learn parallel
> programming.
> In this specific example, the idea seems to be simple: one must
> subdivide the main loop into pieces that can be executed by
> independent "tasks" (computers??).
>
> Then, each "worker task"  executes a part of the loop a certain
> number
> of times, independently of the other worker tasks. One specific task
> plays the role of "master task", which will collect and sum the
> results of the worker tasks:
>
> % descriptive algorithm:
> 1. Inscribe a circle inside a square
> 2. Generate random points inside the square
> 3. Determine the number of points that fell inside the circle
> 4. Let r be the number of points inside the circle divided by the
> total number of points
> 5. Pi is approximately equal to 4*r
> 6. The more points are generated, the more is the precision in P
> value
>
> % pseudo-code (parallel):
> 1. npoints = 10000
> 2. circle_count = 0
> 3. p = number of tasks
> 4. num = npoints/p
> 5. find out if I am MASTER or WORKER
> 6. do j = 1,num
> 7. generate 2 random numbers between 0 and 1
> 8. xcoordinate = random1
> 9. ycoordinate = random2
> 10. if (xcoordinate, ycoordinate) inside circle then
> circle_count = circle_count + 1
> 11. end do
> 12. if I am MASTER
> 13. receive from WORKERS their circle_counts
> 14. compute PI (use MASTER and WORKER calculations)
> 15. else if I am WORKER
> 16. send to MASTER circle_count
> 17. endif
>
> My (understading) problem starts in the line 5 of the pseudo-code:
> "5. find out if I am MASTER or WORKER"
> How would I specificy a "worker"? Would that be another computer?
> If yes, how can I access this remote computer in the calculations, in
> C or JAVA?
> If yes, it means that I have to have a LAN or something to perform
> tests?
> I have found that there are some libraries such as OMP or MPI that
> could be used, but I'd like to know if there is a more "raw" way of
> doing this first.
>
> Any help would be much appreciated.
>
> I thank you all in advance.
>
> (I was advised for someone in comp.lang.c to post this question here
> or some similar group, instead of in comp.lang.c).

This problem is explained and solved in Section 3.8 of the book
_Using MPI. Portable parallel programming with the message-passing
interface_ 2nd edition, by Gropp, Lustk, and Skjellum.

HTH

Jomar
0
jomarbueyes
5/14/2008 5:58:55 PM
Here is the code to the third chapter of the book:
http://www-unix.mcs.anl.gov/mpi/usingmpi/examples/intermediate/main.htm
one of the example programs is the pi problem.
Gudny



0
gudny
5/17/2008 11:20:27 AM
On May 17, 1:20=A0pm, gudny <gud...@gmail.com> wrote:
> Here is the code to the third chapter of the book:http://www-unix.mcs.anl.=
gov/mpi/usingmpi/examples/intermediate/main.htm
> one of the example programs is the pi problem.
> Gudny

oh, sorry, exchange "intermediate" for "simplempi" in the link!
0
gudny
5/18/2008 9:52:45 AM
Reply: