Message Passing Computing Examples Problems with a very large degree of parallelism Image Transformations Shifting Rotation Clipping etc Mandelbrot Set Sequential static assignment dynamic work pool assignment Divide and conquer Problem Partitioning Parallel Bucket Sort Numerical Integration Trapezoidal method using static assignment Adaptive Quadrature using dynamic assignment Gravitational N Body Problem Barnes Hut Algorithm Pipelined Computation EECC756 Shaaban 1 lec 7 Spring2000 3 30 99 Image Transformations Common Pixel Level Image Transformations Shifting The coordinates of a two dimensional object shifted by x in the x direction and y in the ydimension are given by x x x y y y where x and y are the original and x and y are the new coordinates Scaling Rotation The coordinates of an object magnified by a factor S x in the x direction and Sy in the y direction are given by x xSx y ySy where Sx and Sy are greater than 1 The object is reduced in size if S x and Sy are between 0 and 1 The magnification or reduction need not be the same in both x and y directions The coordinates of an object rotated through an angle about the origin of the coordinate system are given by x x cos y sin Clipping y x sin y cos Deletes from the displayed picture those points outside a defined rectangular area If the lowest values of x y in the area to be display are x 1 y1 and the highest values of x y are xh yh then x1 x xh y1 y yh needs to be true for the point x y to be displayed otherwise x y is not displayed EECC756 Shaaban 2 lec 7 Spring2000 3 30 99 80x80 blocks Possible Static Image Partitionings 10x640 strips Image size 640x480 To be copied into array map from image file To be processed by 48 Processes or Tasks EECC756 Shaaban 3 lec 7 Spring2000 3 30 99 Message Passing Image Shift Pseudocode Example 48 10x640 strip partitions Master for i 0 for j 0 p q for y for i 8 i j 6 j i 80 j 80 i 0 i 80 i for each 48 processes bit map starting coordinates load coordinates into array x j 0 j 80 j x i p i y i q j z j 8 i process number send Pz x 0 y 0 x 1 y 1 x 6399 y 6399 send coords to slave for i 0 i 8 i for each 48 processes for j 0 j 6 j accept new coordinates z j 8 i process number recv Pz a 0 b 0 a 1 b 1 a 6399 b 6399 receive new coords for i 0 i 6400 i 2 update bit map map a i b i map x i y i EECC756 Shaaban 4 lec 7 Spring2000 3 30 99 Message Passing Image Shift Pseudocode Example 48 10x640 strip partitions Slave process i recv Pmaster c 0 c 6400 receive block of pixels to process for i 0 i 6400 i 2 c i c i delta x transform pixels shift in x direction c i 1 c i 1 delta y shift in y direction send Pmaster c 0 c 6399 send transformed pixels to master EECC756 Shaaban 5 lec 7 Spring2000 3 30 99 Image Transformation Performance Analysis Suppose each pixel requires one computational step and there are n x n pixels If the transformations are done sequentially there would be n x n steps so that ts n2 and a time complexity of O n2 Suppose we have p processors The parallel implementation column row or square rectangular divides the region into groups of n2 p pixels The parallel computation time is given by tcomp n2 p which has a time complexity of O n2 p Before the computation starts the bit map must be sent to the processes If sending each group cannot be overlapped in time essentially we need to broadcast all pixels which may be most efficiently done with a single bcast routine The individual processes have to send back the transformed coordinates of their group of pixels requiring individual send s or a gather routine Hence the communication time is tcomm O n2 So that the overall execution time is given by tp tcomp tcomm O n2 p O n2 EECC756 Shaaban 6 lec 7 Spring2000 3 30 99 Image Computing Example Mandelbrot Set Displaying the Mandelbrot set is another example of processing bit mapped image processing In this case the image is computed and the computation time is significant Required Computation The Mandelbrot set is a set of points in a complex plane that are quasi stable will increase and decrease but not exceed some limit when computed by iterating a function usually the function zn zn 1 2 c Where zn is the nth iteration of the complex number z a bi and z n 1 is the n 1 th value of z and c is a complex number giving the position of the point in the complex plane The initial value for z is zero The iterations are continued until the value of z is greater than 2 which indicates that z will eventually become infinite or the number of iterations exceeds some arbitrary limit EECC756 Shaaban 7 lec 7 Spring2000 3 30 99 Image Computing Example Mandelbrot Set The value of z is the length of the vector given by Zlength sqrt a2 b2 Computing the complex function z n z n 1 2 c is simplified by recognizing that if z a bi z2 a2 2abi bi 2 a2 b2 2abi or a real part of a2 b2 and an imaginary part of 2abi Hence if z real the real part of z and z imag is the imaginary part of z next iteration values can be produced from computing z realn z real n 1 2 z imag n 1 2 c real z imagn 2z real n 1 z imag n 1 c imag EECC756 Shaaban 8 lec 7 Spring2000 3 30 99 Mandelbrot Set Sequential code The code for iterating one point as a function that returns the number of iterations could be int cal pixel float c real float c imag int i max float z real z image z real next lengthsq max z real 0 z imag 0 i 0 number of iterations DO z real next z real z real z imag z imag c real z imag 2 z real z imag c imag z real z real next lengthsq z real z real z imag z imag i WHILE lengthsq 4 0 AND i max return i EECC756 Shaaban 9 lec 7 Spring2000 3 30 99 Mandelbrot Set Using Static Assignment Grouping by either square rectangular regions or by columns rows is suitable Each process needs to execute the procedure cal pixel after being given the coordinates of the pixels to compute Suppose we use the same grouping of 80 x 80 pixels and 48 processes the code might look like the following Master for i 0 i 8 i for j 0 j 6 …