DOC PREVIEW
RIT EECC 756 - Message-Passing Computing Examples

This preview shows page 1-2-3-24-25-26-27-49-50-51 out of 51 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 51 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

RIT EECC 756 - Message-Passing Computing Examples

Documents in this Course
Load more
Download Message-Passing Computing Examples
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Message-Passing Computing Examples and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Message-Passing Computing Examples 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?