4003-532/4005-736 Parallel Computing II Module 2 Lecture Notes -- Hybrid SMP Cluster Programming Load Balancing Prof. Alan Kaminsky Rochester Institute of Technology -- Department of Computer Science Problem: The Mandelbrot Set In 1977 Benoit Mandelbrot published the first edition of The Fractal Geometry of Nature (W. H. Freeman and Company, 1985) in which he described a remarkable set that he called the μ-map   Now known as the Mandelbrot set, its image is perhaps the best-known fractal object ever discovered   Consider the following iteration, where (x,y) is a point in the plane and (ai,bi) is a sequence of points in the plane: a0 = 0 b0 = 0 ai+1 = ai2 - bi2 + x bi+1 = 2aibi + y For most points (x,y), the sequence (ai,bi) goes to infinity as i goes to infinity But for some points (x,y), the sequence (ai,bi) stays finite as i goes to infinity The Mandelbrot set is the set of all points (x,y) such that (ai,bi) stays finite as i goes to infinity   Practical considerations for computing the Mandelbrot set To determine if a certain point (x,y) is or is not in the Mandelbrot set, just start computing the (ai,bi) values If (ai,bi) ever becomes a distance > 2 from the origin, then (ai,bi) will just keep getting farther from the origin, so we can stop iterating and declare that c is not in the Mandelbrot set If (ai,bi) stays a distance <= 2 from the origin up to a certain maximum number of iterations maxiter, we will stop and declare that (x,y) is in the Mandelbrot set, even though we didn't continue iterating i to infinity We can save ourselves a time-consuming square root computation by testing ai2+bi2 > 4 instead of (ai2+bi2)1/2 > 2   Computing an image of the Mandelbrot set Each pixel corresponds to a point (x,y) If the point is in the Mandelbrot set, the pixel's color is black If the point is not in the Mandelbrot set, the pixel's hue depends on the value of i when ai2+bi2 became > 4 Hue = (i / maxiter)gamma The parameter gamma can be chosen to emphasize different aspects of the image   For further information, see Parallel Computing I Module 3 Lecture Notes Sequential Solution Package edu.rit.image Class ColorImage -- source code   Package edu.rit.color Class HSB -- source code   Package edu.rit.hyb.fractal Class MandelbrotSetSeq -- source code   Running time measurements   The whole shebang java edu.rit.hyb.fractal.MandelbrotSetSeq 400 400 -0.75 0 150 1000 0.4 fig01.png     A magnified view of one of the little blobs off the main blob java edu.rit.hyb.fractal.MandelbrotSetSeq 400 400 -0.55 0.6 9600 1000 0.6 fig02.png   Hybrid SMP Cluster Solution Package edu.rit.image Class ColorImage -- source code   Package edu.rit.color Class HSB -- source code   Package edu.rit.hyb.fractal Class MandelbrotSetHyb -- source code   Two levels of parallelization Whole image split into chunks (by rows) using the master-worker pattern Each process computes a chunk or chunks Within a process, chunk split into sub-chunks (by rows) using a parallel for loop Each thread computes a sub-chunk or sub-chunks   Load balancing is required at both levels of parallelization It is not clear what load balancing schedule to use at each level It is not clear whether both levels should use the same load balancing schedule   Load balancing schedule Process schedule: Determines how the image is divvied up into chunks among the processes Thread schedule: Determines how the chunks are divvied up into sub-chunks among the threads in each process Specified by separate command-line arguments   Three scheduling options Fixed scheduling Dynamic scheduling Guided scheduling   Running time measurements as determined by process schedule and thread schedule Kp = 1 process, Kt = 4 threads per process Kp = 2 processes, Kt = 4 threads per process Kp = 3 processes, Kt = 4 threads per process Parallel Computing II • 4003-532-70/4005-736-70 • Spring Quarter 2007 Course Page Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706 Home Page Copyright © 2007 Alan Kaminsky. All rights reserved. Last updated 21-Mar-2007. Please send comments to ark­@­cs.rit.edu.