Home
 

Calculaction of the Mandelbrot Set

Assignment

Source Files

global.h
Global definitions
image.h, image.c
Image generation
main.h, main.c
Master program
tim.c
Slave program

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