Calculaction of the Mandelbrot Set
Assignment
Source Files
Sample Image
Report
Programming Assignment #3
Authors: Ronald Blaschke and Eric Clark
Prof. Zimmerman Fall, 1999
We were assigned the dynamic task assignment with a single pixel
granularity
for our form of decomposition method. This means that the master will send
information for a single pixel to a slave. The slave then performs the
calculations and returns the information to the master.
The slave will then wait until the master sends the slave another
calculation
to perform or tells the slave to quit. If the slave is told to quit it
returns
the busy and idle times for the calculation of the utilization of the
slaves to
the master and then quits.
The message contents are as follows:
Master -> Slave Message 0 means sending calculation data
1 means send time data and quit
Slave -> Master Message 0: return maximum number of iterations
1: return time busy and time idle
The master will simply assign each slave a pixel. When all slaves are busy
he
waits for one slave to return a result, and then give him new work. If all
pixels are assigned the master just receives the missing results.
Then the master will tell all slaves to quit. Each slave will return it's
time
utilization and the master will display it on the screen.
We need to run a sequential test and a parallel test to calculate the
speedup. Both tests are included in this program and run one after the
other. The total time for each test is printed out.
Startup
=======
pa3_master <config_filename> <xmin> <xmax> <ymin> <ymax> <maxiter>
Example:
pa3_master hosts -2 2 -2 2 100
The master will spawn slave with the command
pa3_slave <maxiter>
Configuration File
==================
Any number of entries may be specified. Each entry is written
in one line. Possible entries are:
<N> DEFAULT
<N> HOST <hostname>
<N> ARCH <architecture>
N is the number of slaves to spawn, hostname or architecture
are as specified in PVM.
Example:
5 DEFAULT
10 HOST sigma.bgsu.edu
8 ARCH SGI6
Implementation Details
======================
On startup, before the tests start, a colormap is created in
the master to map a iteration value to a color. This map and
the received iteration value are then used to color the pixel.
All of the following messages have the PVM message id 0.
A message from the master to the slave looks like this
(int) msgtype
... other data.
A message from the slave to the master looks like this
... other data.
No msgtype is required because the master knows what
message he is expecting from the slave, ie there is
only 1 possible answer.
In Detail:
- Calculate Pixel
Master -> Slave
(int) 0
(float) real
(float) imag
The slave should then calculate the iteration count for the
complex number (real, imag) and send it back.
Master <- Slave
(int) iters
The master now may use this iteration count to draw the pixel,
corresponding to the complex number.
- Quit
Master -> Slave
(int) 1
The salve should then send the utilization statistics and die.
Master <- Slave
(long) idle_usec
(long) busy_usec
idle_usec is the time (in microseconds) the slave did nothing,
busy_used is the time (in microseconds) the slave calculated
the iteration value.
The master should then output the utilization of the slave.
Database
========
The master will use the following database:
tids
Contains slave number <-> slave task id
slaveStats
Contains slave number -> current status (idle, busy, dead)
idle ... waiting for job
busy ... calculating
dead ... non existant
slaveComp
Contains slave number -> job info (complex number & corresponding pixel)
slaveUtil
Contains slave number -> utilization statistic (idle & busy time, number
of calculated pixels)
colormap
Contains iteration value -> color
image
Contains the image (pixel position -> color)
The examples below show the speed up results of the various machines and
the various archatectures affects. Basically we should keep in mind that
these results are only an indication of the performance of these machines
since the amount of activity on these machines constantly varies. For the
most part the idea of reducing the granularity of the work to that of a
single pixel seems to make the communication time unreasonably large. Only
on sigma do you see any benefit be running multiple slaves. This benefit
would have to be weighted against the time spent making the process
parallel. It is also interesting to note the distribution of the number of
pixels calculated by the various slaves. This points to the possible
problem of using heterogenous composits rather than a single arch. machine.
I believe that it does not show that any one computer is faster than
another but instead which was better able to communicate with the master
machine running at that time.
You can see that the slaves spent the majority of time idle. This points
to a very poor utilization of the slaves. Which is the princple reason
that the speed up factor is so very bad.
EXAMPLE RUNS OF THE PROGRAM ON DIFFERENT PLATFORMS AND UNDER DIFFERENT
CONDITIONS.
sigma 26% cat hosts
5 HOST sigma.bgsu.edu
sigma 27% pa3_master hosts -2 2 -2 2 1000
Creating Mandelbrot Set image of size (1024,1024)
Sequential Code run
Creating image took 129923151 usecs, that are 8070 pix/sec
Parallel Code run
Spawning 5 slave(s) of type 1 on sigma.bgsu.edu
MANDELBROT SLAVE UTILIZATION
SLAVE HOST TIME IDLE TIME BUSY NUMBER OF PIXEL
CALCULATIONS
0 sigma.bgsu.edu 85069914 19049636 201375
1 sigma.bgsu.edu 83134219 20167967 220657
2 sigma.bgsu.edu 83321306 19671165 205213
3 sigma.bgsu.edu 86938044 18399247 199111
4 sigma.bgsu.edu 81574937 22147012 222220
Creating image took 110841788 usecs, that are 9460 pix/sec
sigma 28%
--------------------------------------------------------------------------
alpha 11% pa3_master hosts -2 2 -2 2 100
Creating Mandelbrot Set image of size (1024,1024)
Sequential Code run
Creating image took 58219230 usecs, that are 18010 pix/sec
Parallel Code run
Spawning 1 slave(s) of type 1 on sigma.bgsu.edu
Spawning 1 slave(s) of type 1 on alpha.bgsu.edu
Spawning 1 slave(s) of type 1 on sci-002.bgsu.edu
Spawning 1 slave(s) of type 1 on sci-004.bgsu.edu
MANDELBROT SLAVE UTILIZATION
SLAVE HOST TIME IDLE TIME BUSY NUMBER OF PIXEL
CALCULATIONS
0 sigma.bgsu.edu 590419787 377236 3627
1 alpha.bgsu.edu 526113405 51551164 1025518
2 sci-002.bgsu.edu 587780067 2510866 9413
3 sci-004.bgsu.edu 588016956 2392959 10018
Creating image took 591647551 usecs, that are 1772 pix/sec
----------------------------------------------------------------------------
---
sigma 15% pa3_master hosts -2 2 -2 2 100
Creating Mandelbrot Set image of size (1024,1024)
Sequential Code run
Creating image took 14158029 usecs, that are 74062 pix/sec
Parallel Code run
Spawning 1 slave(s) of type 1 on sigma.bgsu.edu
Spawning 1 slave(s) of type 1 on alpha.bgsu.edu
Spawning 1 slave(s) of type 1 on sci-002.bgsu.edu
Spawning 1 slave(s) of type 1 on sci-004.bgsu.edu
MANDELBROT SLAVE UTILIZATION
SLAVE HOST TIME IDLE TIME BUSY NUMBER OF PIXEL
CALCULATIONS
0 sigma.bgsu.edu 52185014 33568970 997645
1 alpha.bgsu.edu 100764042 56646 930
2 sci-002.bgsu.edu 94869701 5478991 24898
3 sci-004.bgsu.edu 95122690 5097751 25103
Creating image took 101542933 usecs, that are 10326 pix/sec
--
sigma 28% pa3_master hosts -2 2 -2 2 1000
Creating Mandelbrot Set image of size (1024,1024)
Sequential Code run
Creating image took 129770014 usecs, that are 8080 pix/sec
Parallel Code run
Spawning 1 slave(s) of type 1 on sigma.bgsu.edu
Spawning 1 slave(s) of type 1 on alpha.bgsu.edu
Spawning 1 slave(s) of type 1 on sci-002.bgsu.edu
Spawning 1 slave(s) of type 1 on sci-004.bgsu.edu
MANDELBROT SLAVE UTILIZATION
SLAVE HOST TIME IDLE TIME BUSY NUMBER OF PIXEL
CALCULATIONS
0 sigma.bgsu.edu 51148633 47160530 991930
1 alpha.bgsu.edu 113072251 133789 575
2 sci-002.bgsu.edu 104869922 7871641 27901
3 sci-004.bgsu.edu 104935487 7670005 28170
Creating image took 114217615 usecs, that are 9180 pix/sec
----------------------------------------------------------------------------
---
sci-002 4% pa3_master hosts -2 2 -2 2 100
Creating Mandelbrot Set image of size (1024,1024)
Sequential Code run
Creating image took 28616307 usecs, that are 21 pix/sec
Parallel Code run
Spawning 1 slave(s) of type 1 on sigma.bgsu.edu
Spawning 1 slave(s) of type 1 on alpha.bgsu.edu
Spawning 1 slave(s) of type 1 on sci-002.bgsu.edu
Spawning 1 slave(s) of type 1 on sci-004.bgsu.edu
MANDELBROT SLAVE UTILIZATION
SLAVE HOST TIME IDLE TIME BUSY NUMBER OF PIXEL
CALCULATIONS
0 sigma.bgsu.edu 1388666743 1062847 13399
1 alpha.bgsu.edu 1386222192 3469115 13176
2 sci-002.bgsu.edu 1072021026 296874433 704728
3 sci-004.bgsu.edu 1308380031 74238258 317273
Creating image took 1390533862 usecs, that are 0 pix/sec
============================================================================
===
sigma 15% pa3_master hosts -2 2 -2 2 100
Creating Mandelbrot Set image of size (1024,1024)
Sequential Code run
Creating image took 14158029 usecs, that are 74062 pix/sec
Parallel Code run
Spawning 1 slave(s) of type 1 on sigma.bgsu.edu
Spawning 1 slave(s) of type 1 on alpha.bgsu.edu
Spawning 1 slave(s) of type 1 on sci-002.bgsu.edu
Spawning 1 slave(s) of type 1 on sci-004.bgsu.edu
MANDELBROT SLAVE UTILIZATION
SLAVE HOST TIME IDLE TIME BUSY NUMBER OF PIXEL
CALCULATIONS
0 sigma.bgsu.edu 52185014 33568970 997645
1 alpha.bgsu.edu 100764042 56646 930
2 sci-002.bgsu.edu 94869701 5478991 24898
3 sci-004.bgsu.edu 95122690 5097751 25103
Creating image took 101542933 usecs, that are 10326 pix/sec
--
sigma 30% pa3_master hosts -2 2 -2 2 100
Creating Mandelbrot Set image of size (1024,1024)
Sequential Code run
Creating image took 14162767 usecs, that are 74037 pix/sec
Parallel Code run
Spawning 2 slave(s) of type 1 on sigma.bgsu.edu
Spawning 2 slave(s) of type 1 on alpha.bgsu.edu
Spawning 2 slave(s) of type 1 on sci-002.bgsu.edu
Spawning 2 slave(s) of type 1 on sci-004.bgsu.edu
MANDELBROT SLAVE UTILIZATION
SLAVE HOST TIME IDLE TIME BUSY NUMBER OF PIXEL
CALCULATIONS
0 sigma.bgsu.edu 38364416 22984065 506403
1 sigma.bgsu.edu 39123507 22011363 522679
2 alpha.bgsu.edu 69359111 127926 1796
3 alpha.bgsu.edu 69377701 75177 1713
4 sci-002.bgsu.edu 68375919 1041598 4081
5 sci-002.bgsu.edu 68347858 1028410 4079
6 sci-004.bgsu.edu 68372076 977049 3912
7 sci-004.bgsu.edu 68299124 1049462 3913
Creating image took 70040475 usecs, that are 14971 pix/sec
--
sigma 33% pa3_master hosts -2 2 -2 2 100
Creating Mandelbrot Set image of size (1024,1024)
Sequential Code run
Creating image took 14161619 usecs, that are 74043 pix/sec
Parallel Code run
Spawning 5 slave(s) of type 1 on sigma.bgsu.edu
Spawning 5 slave(s) of type 1 on alpha.bgsu.edu
Spawning 5 slave(s) of type 1 on sci-002.bgsu.edu
Spawning 5 slave(s) of type 1 on sci-004.bgsu.edu
MANDELBROT SLAVE UTILIZATION
SLAVE HOST TIME IDLE TIME BUSY NUMBER OF PIXEL
CALCULATIONS
0 sigma.bgsu.edu 88436892 17596879 225499
1 sigma.bgsu.edu 88176811 17744297 203856
2 sigma.bgsu.edu 90426405 17365784 199737
3 sigma.bgsu.edu 88242604 18387967 204231
4 sigma.bgsu.edu 88629128 18172284 208309
5 alpha.bgsu.edu 112416143 106423 440
6 alpha.bgsu.edu 112326241 132775 434
7 alpha.bgsu.edu 112311512 140651 426
8 alpha.bgsu.edu 112354484 100610 422
9 alpha.bgsu.edu 112294926 109322 441
10 sci-002.bgsu.edu 112310578 98522 474
11 sci-002.bgsu.edu 112298001 114183 474
12 sci-002.bgsu.edu 112338252 99412 474
13 sci-002.bgsu.edu 112326495 110951 473
14 sci-002.bgsu.edu 112336753 101458 473
15 sci-004.bgsu.edu 112241484 102613 483
16 sci-004.bgsu.edu 112182328 107695 483
17 sci-004.bgsu.edu 112260645 101839 483
18 sci-004.bgsu.edu 112211127 104265 482
19 sci-004.bgsu.edu 112218851 106211 482
Creating image took 113444478 usecs, that are 9243 pix/sec
--
sigma 59% pa3_master hosts -2 2 -2 2 100
Creating Mandelbrot Set image of size (1024,1024)
Sequential Code run
Creating image took 14106521 usecs, that are 74332 pix/sec
Parallel Code run
Spawning 10 slave(s) of type 1 on sigma.bgsu.edu
Spawning 5 slave(s) of type 1 on alpha.bgsu.edu
Spawning 5 slave(s) of type 1 on sci-002.bgsu.edu
Spawning 5 slave(s) of type 1 on sci-004.bgsu.edu
MANDELBROT SLAVE UTILIZATION
SLAVE HOST TIME IDLE TIME BUSY NUMBER OF PIXEL
CALCULATIONS
0 sigma.bgsu.edu 173219816 18039208 66800
1 sigma.bgsu.edu 153962676 31835876 165327
2 sigma.bgsu.edu 173743638 18100339 88090
3 sigma.bgsu.edu 168139200 22653313 116866
4 sigma.bgsu.edu 168316093 21993546 99076
5 sigma.bgsu.edu 171997314 20346548 116986
6 sigma.bgsu.edu 166926621 22903022 109127
7 sigma.bgsu.edu 166720616 22071165 118359
8 sigma.bgsu.edu 172680753 18276317 60220
9 sigma.bgsu.edu 167521943 21583468 101431
10 alpha.bgsu.edu 195161627 107418 394
11 alpha.bgsu.edu 195091231 151387 394
12 alpha.bgsu.edu 195047282 220722 396
13 alpha.bgsu.edu 195048329 182550 395
14 alpha.bgsu.edu 195008294 193341 392
15 sci-002.bgsu.edu 195044091 80320 435
16 sci-002.bgsu.edu 195058594 93941 434
17 sci-002.bgsu.edu 195034522 77472 434
18 sci-002.bgsu.edu 195048265 79056 434
19 sci-002.bgsu.edu 195023310 91362 434
20 sci-004.bgsu.edu 194873644 99409 431
21 sci-004.bgsu.edu 194909740 89285 431
22 sci-004.bgsu.edu 194906949 96509 430
23 sci-004.bgsu.edu 194906038 103853 430
24 sci-004.bgsu.edu 194914131 97990 430
Creating image took 196533946 usecs, that are 5335 pix/sec