EECC756 EECC756 --ShaabanShaaban#1 lec # 7 Spring2008 4-17-2008Basic Techniques of Parallel Programming Basic Techniques of Parallel Programming & Examples& Examples• Problems with a very large degree of (data) parallelism: (PP ch. 3)– Image Transformations: • Shifting, Rotation, Clipping etc.– Pixel-level Image Processing: (PP ch. 12)• Divide-and-conquer Problem Partitioning: (pp ch. 4)– Parallel Bucket Sort– Numerical Integration:• Trapezoidal method using static assignment. • Adaptive Quadrature using dynamic assignment.– Gravitational N-Body Problem: Barnes-Hut Algorithm.• Pipelined Computation (pp ch. 5)– Pipelined Addition– Pipelined Insertion Sort– Pipelined Solution of A Set of Upper-Triangular Linear EquationsParallel Programming (PP) book, Chapters 3-7, 12Data parallelism (DOP) scale well with size of problemTo improve throughputof a number of instancesof the same problemDivide problem is into smaller parallel problems of the same type as the larger problem then combine resultsFundamental or CommonEECC756 EECC756 --ShaabanShaaban#2 lec # 7 Spring2008 4-17-2008• Synchronous Iteration (Synchronous Parallelism) : (PP ch. 6)– Barriers:• Counter Barrier Implementation.• Tree Barrier Implementation.• Butterfly Connection Pattern Message-Passing Barrier.– Synchronous Iteration Program Example:• Iterative Solution of Linear Equations (Jacobi iteration)••Dynamic Load Balancing Dynamic Load Balancing (PP (PP chch. 7). 7)– Centralized Dynamic Load Balancing.––Decentralized Dynamic Load Balancing:Decentralized Dynamic Load Balancing:• Distributed Work Pool Using Divide And Conquer.• Distributed Work Pool With Local Queues In Slaves.• Termination Detection for Decentralized Dynamic Load Balancing.––Example: Shortest Path Problem (Moore’s Algorithm).Example: Shortest Path Problem (Moore’s Algorithm).Basic Techniques of Parallel Programming Basic Techniques of Parallel Programming & Examples& ExamplesSimilar to 2-d grid (ocean) example(lecture 4)For problems with unpredictablecomputations/tasksImplementations123EECC756 EECC756 --ShaabanShaaban#3 lec # 7 Spring2008 4-17-2008Problems with large degree of (data) parallelism:Example: Image TransformationsExample: Image 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 Sxin the x direction and Syin the y direction are given by:x' = xSxy' = ySywhere Sx and Syare greater than 1. The object is reduced in size if Sxand Syare 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≤ yhneeds to be true for the point (x, y) to be displayed, otherwise (x, y) is not displayed. Parallel Programming book, Chapter 3, Chapter 12 (pixel-based image processing)DOP = O(n2)Also low-level pixel-based image processingEECC756 EECC756 --ShaabanShaaban#4 lec # 7 Spring2008 4-17-2008Possible Static Image PartitioningsPossible Static Image Partitionings• Image size: 640x480:• To be copied into array:map[ ][ ] from image file• To be processed by 48 Processes or Tasks80x80blocks10x640strips (of image rows)Domain decomposition partitioning used(similar to 2-d grid ocean example)Block Assignment:Strip Assignment:pnnComputatio2=pnionCommunicat4=npCtoC×=−−4Communication = 2nComputation = n2/pc-to-c ratio = 2p/nX0X1X2X3X4X5X6X7X8Pixel-based image processing Example: Sharpening Filter-1 -1 -1-1 8 -1-1 -1 -1Sharpening Filter MaskUpdated X4= (8X4-X0–X1–X2–X3–X5 –X6–X7–X8)/9Weight or Filter coefficientMore on pixel-based image processingParallel Programming book, Chapters 12EECC756 EECC756 --ShaabanShaaban#5 lec # 7 Spring2008 4-17-2008Message Passing Image Shift Pseudocode Message Passing Image Shift Pseudocode Example (48, 10x640 strip partitions)Example (48, 10x640 strip partitions)Masterfor (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] ];}SendDataGetResultsUpdate coordinatesEECC756 EECC756 --ShaabanShaaban#6 lec # 7 Spring2008 4-17-2008Slave (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)Or other pixel-based computationMore on pixel-based image processingParallel Programming book, Chapters 12i.e Get pixel coordinates to work on from master processSend results to master processUpdate points(data parallel comp.)EECC756 EECC756 --ShaabanShaaban#7 lec # 7 Spring2008 4-17-2008Image Transformation Performance AnalysisImage Transformation Performance Analysis• Suppose each pixel requires one