## Distributed calculation of the Mandelbrot set # using MPD for parallel programming, and C for number crunching # # Gregg Townsend (gmt@Arizona.EDU) # Department of Computer Science # University of Arizona # October, 1988; February, 1982 # # Usage: a.out [-mp] [x [y [side [n]]] [host ...] # -m: generate mff(1) output and pipe into mff # -p: generate PostScript output # x,y: center of region to display # side: horizontal dimension of area displayed # n: maximum number of iterations (default 32, maximum 255) # host: list of host names on which to calculate (default: local host) # # Output is a greyscale image. # # See Computer Recreations, Scientific American, August, 1985 # # Interesting displays (some with references to the article) # -.7 0.0 2.6 the whole set (p.17) (THIS IS THE DEFAULT) # -.92 .265 .06 edge of the set (front cover) # -.73 .25 .05 another edge (near 18a) # .2649 .0034 .002 near cusp of cardioid # -.738 .208 .01 spiral arms just outside the edge # -.7375 .2085 .001 the eye at the center (like 19e) # -.234 .827 .01 mini-set in a filament (like 19f) # -1.579 .006 .025 a portion of the negative x axis # -1.57525 0 .0052 mini-set with 8 radiating arms # -.19 1.09 .08 the very top edge of the set # -.1 .958 .02 a fork near the top resource main () import remote external backend (string[*] path) external gethostname (res string[*] s, int namelen) external strchr (string[*] s, char c) returns ptr char p op outproc out op start (int m, config c) op hungry (int m) # defaults for command parameters const int DEFITER = 32 # default iteration limit const real DEFX = -0.7 # default x const real DEFY = 0.0 # default y const real DEFSIDE = 2.6 # default side # configuration parameters const int MAXREM = 64 # maximum number of remote machines const int AHEAD = 2 # number of anticipatory sends const int NAMLEN = 50 # max length of a machine name # the unit of distributed processing is a cell of CWIDTH by CHEIGHT pixels ########## NOTE: these numbers are for testing. Use 32, e.g., for real. ##### const int CWIDTH = 8 # cell width in pixels - must be even const int CHEIGHT = 8 # cell height # the total displayed area is NWIDE x NHIGH cells const int NWIDE = 9 # output width, in number of cells const int NHIGH = 9 # output height # other constants const int WIDTH = NWIDE * CWIDTH # total width, in pixels const int HEIGHT = NHIGH * CHEIGHT # total height const int DATALEN = CWIDTH * CHEIGHT # length of data for one cell # PostScript stuff bool PostScript = true # PostScript output flag const int PSHEIGHT = 792 # page height const int PSWIDTH = 612 # page width const int LLX = (PSWIDTH - WIDTH) / 2 # coords of LL corner of image const int LLY = (PSHEIGHT - HEIGHT) / 2 # coords of LL corner of image # other resource variables int nvm = 0 # number of virtual machines cap remote rcap[MAXREM] # caps for their resources string[NAMLEN] name[MAXREM] # their host names int tally[MAXREM] # number of cells computed by each # mapping from iteration count to greyscale char hex[0:255] = chars ( "3579BDEF89ABCDEF8899AABBCCDDEEFF888999AAABBBCCCDDDEEEFFF88889999" || "AAAABBBBCCCCDDDDEEEEFFFF888888999999AAAAAABBBBBBCCCCCCDDDDDDEEEE" || "EEFFFFFF88888888BBBBBBBBCCCCCCCCDDDDDDDDEEEEEEEEFFFFFFFF88888888" || "8999999999AAAAAAAAABBBBBBBBBCCCCCCCCCDDDDDDDDDEEEEEEEEEFFFFFFFFF") # start(m,c) - start up virtual machine m with configuration c proc start (m,c) { cap outproc o = out cap vm mcap tally[m] = 0 # zero the output counter locate(m,name[m]) # set hostname mcap = create vm() on m # create virtual machine if (mcap == null) { # check for success write(stderr,"can't create vm on",name[m]) stop } rcap[m] = create remote(m,o) on mcap # create remote server process send rcap[m].init(c) # initialize it if (nvm > 1) { write(stderr,"ready on",name[m]) # announce it } for [ j = 0 to AHEAD ] { send hungry(m) # give it an initial work queue } } # the dispatcher gives out work assignments upon request process dispatcher { int m for [ i = 0 to NWIDE-1 ] { # do columns from left to right for [ j = NHIGH-1 downto 0 ] { # do each column from top to bottom receive hungry(m) # get next request send rcap[m].docell(i,j) # send cell coordinates to machine } } while (true) { # gobble up and ignore extra requests receive hungry(m) } } # the output process receives iteration counts from the various machines, # translates them into mff form, and writes them to standard output process output { int i, j, m char d[DATALEN] # data buffer # receive all the cells of the image for [ n = 1 to NHIGH * NWIDE ] { receive out(m,i,j,d) # get a cell of data from machine m tally[m]++ # bump its counter hungry(m) # give it another cell to work on write (CWIDTH*i,CHEIGHT*j,CWIDTH,CHEIGHT,CWIDTH,CHEIGHT,4,"raster") # write header w/ cell size, locn, fmt int c = 0 for [ y = 1 to CHEIGHT ] { for [ x = 1 to CWIDTH ] { c++ writes (hex[int(d[c])]) # translate count to greyscale } write () # terminate scan line with newline } } # when all cells have been output, write statistics & terminate the program if (PostScript) { write("showpage") } if (nvm > 1) { for [ n = 1 to nvm ] { writes(stderr,name[n],": ",tally[n],"\n") } } stop } # overall initialization config c # set up record with configuration parameters c.cwidth = CWIDTH c.cheight = CHEIGHT c.nwide = NWIDE c.nhigh = NHIGH c.niter = DEFITER real xc = DEFX # region parameters real yc = DEFY real side = DEFSIDE string[NAMLEN] s # argument buffer int nna = 0 # number of numeric arguments seen so far for [ i = 1 to numargs() ] { # process arg list getarg(i,s) # get next arg if (strchr("-0.123456789",s[1]) ~= null) { if (s == "-p") { # "-p" sets PostScript mode PostScript = true } else if (s == "-m" ) { # "-m" sets mff mode PostScript = false } else { nna++ # process numeric value if (nna == 1) { getarg(i,xc) # 1st one is x value } else if (nna == 2 ) { getarg(i,yc) # 2nd one is y value } else if (nna == 3 ) { getarg(i,side) # 3rd one is side dimension } else if (nna == 4 ) { getarg(i,c.niter) # 4th one is iteration limit } else { nvm++ name[nvm] = s # must be a host number } } } else { nvm++ # nonnumeric args are just added to host list name[nvm] = s } } c.delta = side / (c.cwidth * c.nwide) c.xll = xc - (side / 2) c.yll = yc - c.delta * (c.nhigh * c.cheight / 2); if (c.niter > 255) { write(stderr,"sorry, can't handle over 255 iterations") stop } if (nvm == 0) { # if no hosts named, use self nvm = 1 gethostname(name[1],maxlength(name[1])) } hex[c.niter] = '0' # adjust count mapping to make max map to black if (PostScript) { # write header for PostScript output write("%!PS-Adobe-2.0 EPSF-1.2") write("%%BoundingBox",LLX,LLY,LLX+WIDTH,LLY+HEIGHT) write() write("/raster { ") write(" /f exch def /h exch def /w exch def /buf w string def") write(" /buf w string def") write(" gsave 4 2 roll translate scale") write(" w h f [w 0 0 h neg 0 h]") write(" {currentfile buf readhexstring pop} image grestore") write("} def") write() write(LLX,LLY,"translate") } else { backend("/usr/local/mff") # initialize graphics backend (pipe into mff) write ("1 metafile") # write metafile header and image dimensions write (WIDTH-1, HEIGHT-1, "128 128 128 init") } for [ i = 1 to nvm ] { # start a vm on each host (in parallel) send start(i,c) } end