Message-Passing Computing ExamplesImage TransformationsPossible Static Image PartitioningsMessage Passing Image Shift Pseudocode Example (48, 10x640 strip partitions)Slide 5Image Transformation Performance AnalysisImage Computing Example: Mandelbrot SetSlide 8Mandelbrot Set: Sequential codeMandelbrot Set Using Static AssignmentDynamic Assignment - Work Pool/Processor FarmsMandelbrot Set Using Dynamic Work Pool AssignmentSlide 13Divide-and-ConquerDivide-and-Conquer Example Bucket SortSequential Bucket SortParallel Bucket SortParallel Version of Bucket SortPerformance of Message-Passing Bucket SortMore Detailed Performance Analysis of Parallel Bucket SortNumerical Integration Using RectanglesMore Accurate Numerical Integration Using RectanglesNumerical Integration Using The Trapezoidal MethodNumerical Integration Using The Trapezoidal Method: Static Assignment Message-PassingSlide 25Numerical Integration And Dynamic Assignment: Adaptive QuadratureAdaptive Quadrature ConstructionGravitational N-Body ProblemGravitational N-Body Problem: Barnes-Hut AlgorithmTwo-Dimensional Barnes-HutBarnes-Hut AlgorithmA Balanced Partitioning Approach: Orthogonal Recursive Bisection (ORB)Pipelined ComputationsSlide 34Slide 35Slide 36Pipeline Processing Where Information Passes To Next Stage Before End of ProcessPipelined AdditionPipelined Addition: AnalysisSlide 40Pipelined Insertion SortSlide 42Pipelined Insertion Sort ExamplePipelined Insertion Sort: AnalysisSlide 45Solving A Set of Upper-Triangular Linear EquationsSlide 47Slide 48Slide 49Solving A Set of Upper-Triangular Linear Equations: AnalysisOperation of Back-Substitution PipelineEECC756 - ShaabanEECC756 - Shaaban#1 lec # 7 Spring2000 3-30-99Message-Passing Message-Passing Computing ExamplesComputing 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 ComputationEECC756 - ShaabanEECC756 - Shaaban#2 lec # 7 Spring2000 3-30-99Image TransformationsImage TransformationsCommon Pixel-Level Image Transformations:•Shifting:–The coordinates of a two-dimensional object shifted by x in the x-direction and y in the y-dimension 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: –The coordinates of an object magnified by a factor Sx in the x direction and Sy in the y direction are given by: x' = xSxy' = ySy where Sx and Sy are greater than 1. The object is reduced in size if Sx and Sy are between 0 and 1. The magnification or reduction need not be the same in both x and y directions.• Rotation:–The coordinates of an object rotated through an angle about the origin of the coordinate system are given by: x' = x cos + y sin y' = - x sin + y cos •Clipping:–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 x1, y1, and the highest values of x, y are xh, yh, then: x1 x xhy1 y yh needs to be true for the point (x, y) to be displayed, otherwise (x, y) is not displayed.EECC756 - ShaabanEECC756 - Shaaban#3 lec # 7 Spring2000 3-30-99Possible Static Possible Static Image PartitioningsImage Partitionings• Image size: 640x480:• To be copied into array: map[ ][ ] from image file• To be processed by 48 Processes or Tasks80x80blocks10x640 stripsEECC756 - ShaabanEECC756 - Shaaban#4 lec # 7 Spring2000 3-30-99Message Passing Image Shift Pseudocode Message Passing Image Shift Pseudocode Example (48, 10x640 strip partitions)Example (48, 10x640 strip partitions)Master for (i = 0; i < 8; i++) /* for each 48 processes */ for (j = 0; j < 6; j++) { p = i*80; /* bit map starting coordinates */ q = j*80; for (i = 0; i < 80; i++) /* load coordinates into array x[], y[]*/ for (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 - ShaabanEECC756 - Shaaban#5 lec # 7 Spring2000 3-30-99Slave (process i)Slave (process i) recv(Pmaster, c[0] ... c[6400]); /* receive block of pixels to process */ for (i = 0; i < 6400; i += 2) { /* transform pixels */ c[i] = c[i] + delta_x ; /* 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 */Message Passing Image Shift Pseudocode Message Passing Image Shift Pseudocode Example (48, 10x640 strip partitions)Example (48, 10x640 strip partitions)EECC756 - ShaabanEECC756 - Shaaban#6 lec # 7 Spring2000 3-30-99Image Transformation Performance AnalysisImage 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
View Full Document