PVM, Part I

An Introduction

For this assignment, we were to make an original program using Parallel Virtual Machine. First, a brief overview of PVM:

PVM works similarly to the individual processors in a supercomputer: one processor (the master, or in this case a whole computer, starts doing some computationally-intensive task. It splits up the task in some predetermined way, and sends each piece to more processors (the slaves, which can then work simultaneously and send the results back to the master program to be reassembled. Some possible methods are:

The master-slave method described above. A master program sends data to a bunch of slaves, who send their answers back.
The tree method. A program spawns itself on each of the machines, and each of the slaves spawn more slave, until a given depth is reached or the computers crash from having too many slaves. We usually try to avoid that, but it's happened before...
The relay/pipeline method. This works like an assembly line: each processor works on a specific task before sending their answers along to the next processor, then it continues is task on the next set of data, and so on.

Enough of that; on to:

The Program

The Chudnovsky brothers' claim to fame is all the many records they have set and broken for calculating pi, reaching totals in the billions of digits. The mathematician Srinivasa Ramanujan, among many other impressive accomplishments in his short life, came up with many quickly converging formulae for calculating pi, including one that adds approximately 8 correct digits per iteration. There exists a quartically converging algorithm - one that quadruples the number of digits - and a less efficient quintically converging algorithm for calculating digits of pi. Further more, within the last decade or so the "miraculous" Borwein-Bailey-Plouffe algorithm was discovered, giving to mathematicians not only another fast formula for pi but also an incredible algorithm for calculating specific hexadecimal digits of pi; using that, people have even calculated such trivia as the trillionth (yes, trillionth) binary digit of pi.

By now, you're probably thinking, Okay, okay, I get it. You used this amazing computing power to calculate pi. This is true, and I admit it proudly. So which amazingly rapid algorithm did you use, Gary? None of them. It's both a pain and a waste of memory to write classes to store numbers with even just thousands of digits, so I used doubles. Since doubles only store 14 or 15 digits, using a fast algorithm is useless. You can run that on one processor in virtually no time.

Enter Gregory's Formula. This is one of the more well-known formulae for calculating pi, but also one of the slowest. Since by simple trig we know that pi=4tan^-1(1), we use the series for arctangent to find that:

pi = 4/1 - 4/3 + 4/5 - 4/7 + 4/9 - ...

Now, how did I use this fact in my program? Well, I split up numbers into ten ranges (for ten slaves). I set an upper limit of 1,000,000,000, so each slave worked on 100 million numbers. Well, that's not quite true - from the formula we can see that the only denominators we care about are the even ones, so each slave only works on 50 million numbers for a grand total of 500 million iterations. Still, all these iterations don't do much for us. The program outputted 3.1415926516 as its final answer (after the 500 million iterations), when in fact pi is approximately 3.1415926536 (for a more exact value, click here - if you dare...). This is an accuracy of eight digits after the decimal point, which Ramanujan gave us with only one iteration. Still, it was a fun experiment and demonstration of the powers of PVM, as explained below.

The standard USACO estimation puts the number of "operations" a computer can perform per second at about 10 million ("operation" is in quotes because it is not a precise term - a function call does not count as an operation for this, for example, because it could take indefinitely long by itself). Here we are performing 500 million iterations for a total of 50 seconds. Throw in the extra operations to keep track of the alternating signs and other smaller operations and we are now on the order of 100 seconds for a lousy approximation of pi. Yet through the wonders of PVM I could split up the tasks among ten machines and run the program in under 10 seconds (this is where you, the fascinated reader, says "wow..."). Each program, given the First and Last values for each range, calculated the Partial Sum for that range and sent the values back to the master program, which compiled the data and spat it out to the screen. The output of a sample run appears below.

This program calculates pi by using the painfully slow Gregory's Formula:
  pi = 4atan(1)
It calculates half a billion iterations and still only gets 9 digits
right, but hey, if we're gonna use PVM we might as well do something slow.

First:  300000001, Last:   400000000; Partial Sum: 0.0000000017
First:  800000001, Last:   900000000; Partial Sum: 0.0000000003
First:  700000001, Last:   800000000; Partial Sum: 0.0000000004
First:  500000001, Last:   600000000; Partial Sum: 0.0000000007
First:  400000001, Last:   500000000; Partial Sum: 0.0000000010
First:  200000001, Last:   300000000; Partial Sum: 0.0000000033
First:  100000001, Last:   200000000; Partial Sum: 0.0000000100
First:          1, Last:   100000000; Partial Sum: 3.1415926336
First:  600000001, Last:   700000000; Partial Sum: 0.0000000005
First:  900000001, Last:  1000000000; Partial Sum: 0.0000000002

Pi is approximately 3.1415926516

Are you addicted to C code? Can you just not get enough of it? Do you feel empty with out those printf's? Or do you just want to see the code so you can grade it? Either way, I've got you covered:

mastapvm.c: The "masta" program, which divided the task into ten pieces and then sent them all to the ten slaves.
slavepvm.c: The slave program, which performed the iterations for Gregory's Formula over a certain range and sent the results back to the master program.

Appendix (sort of)

Yeah, yeah...I told you you'd get some pi, so here it is. The links here are to pages outside of my site, so be sure to have that Back button handy...

	My Supercomp front page.
	This page was created by Gary Sivek for 7th Period Supercomp.