UntitledUntitledMIT OpenCourseWare http://ocw.mit.edu 6.189 Multicore Programming Primer, January (IAP) 2007 Please use the following citation format: Rodric Rabbah, 6.189 Multicore Programming Primer, January (IAP) 2007. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (accessed MM DD, YYYY). License: Creative Commons Attribution-Noncommercial-Share Alike. Note: Please use the actual date you accessed this material in your citation. For more information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms6.189 IAP 2007 Lecture7 Design Patterns for Parallel Programming II 1 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Recap: Common Steps to Parallelization Partitioning P0 P1 P2 P3 p0 p1 p2 p3 p0 p1 p2 p3 d e c o m p o s i t i o n a s s i g n m e n t o r c h e s t r a t i o n m a p pi n g Sequential Tasks Execution Parallel Processorscomputation Units Program 2 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Recap: Decomposing for Concurrency MPEG Decoder MPEG bit stream join IDCT IQuantization split VLD macroblocks, motion vectors frequency encodedmacroblocks differentially codedmotion vectors motion vectors spatially encoded macroblocks ZigZag Saturation Motion Vector Decode Repeat ● Task decomposition  Parallelism in the application ● Data decomposition  Same computation many data ● Pipeline decomposition  Data assembly lines  Producer-consumer chains Motion Compensation recovered picture Picture Reorder Color Conversion Display 3 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Dependence Analysis ● Given two tasks how to determine if they can safely run in parallel? 4 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Bernstein’s Condition ● Ri: set of memory locations read (input) by task Ti ● Wj: set of memory locations written (output) by task Tj ● Two tasks T1 and T2 are parallel if  input to T1 is not part of output from T2  input to T2 is not part of output from T1  outputs from T1 and T2 do not overlap 5 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Example T1 a = x + y T2 b = x + z R1 = { x, y } W1 = { a } R2 = { x, z } W2 = { b } R1 IW2 =φ R2 IW1 =φ W1 IW2 =φ 6 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Patterns for Parallelizing Programs 4 Design Spaces Algorithm Expression Software Construction ● Finding Concurrency ● Supporting Structures  Expose concurrent  Code and data structuring tasks patterns ● Algorithm Structure ● Implementation Mechanisms  Map tasks to units of  Low level mechanisms used execution to exploit to write parallel programs parallel architecture Patterns for Parallel Programming. Mattson, Sanders, and Massingill (2005). 6.189 IAP 2007 MIT 7 Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Algorithm Structure Design Space ● Given a collection of concurrent tasks, what’s the next step? ● Map tasks to units of execution (e.g., threads) ● Important considerations  Magnitude of number of execution units platform will support  Cost of sharing information among execution units  Avoid tendency to over constrain the implementation – Work well on the intended platform – Flexible enough to easily adapt to different architectures 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 20078Major Organizing Principle ● How to determine the algorithm structure that represents the mapping of tasks to units of execution? ● Concurrency usually implies major organizing principle  Organize by tasks  Organize by data decomposition  Organize by flow of data 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 20079Organize by Tasks? Recursive? Task Parallelism yes no Divide and Conquer 0 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 20071Task Parallelism ● Ray tracing  Computation for each ray is a separate and independent ● Molecular dynamics  Non-bonded force calculations, some dependencies ● Common factors  Tasks are associated with iterations of a loop  Tasks largely known at the start of the computation  All tasks may not need to complete to arrive at a solution 11 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Divide and Conquer ● For recursive programs: divide and conquer  Subproblems may not be uniform  May require dynamic load balancing subproblem compute subproblem compute subproblem subproblem join split split subproblem compute subproblem compute subproblem subproblem join split problem join solution 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 200712Organize by Data? ● Operations on a central data structure  Arrays and linear data structures  Recursive data structures Recursive? Geometric Decomposition yes no Recursive Data 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 200713Geometric Decomposition simulator ● Gravitational body VEC3D acc[NUM_BODIES] = 0; for (i = 0; i < NUM_BODIES - 1; i++) { Calculate force for (j = i + 1; j < NUM_BODIES; j++) {// Displacement vectorbetween pairs of VEC3D d = pos[j] – pos[i];// Forcet = 1 / sqr(length(d));objects and update // Components of force along displacementaccelerations d = t * (d / length(d)); acc[i] += d * mass[j];acc[j] += -d * mass[i];}} pos vel pos 14 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Recursive Data ● Computation on a list, tree, or graph  Often appears the only way to solve a problem is to sequentially move through the data structure ● There are however opportunities to reshape the operations in a way that exposes concurrency 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 200715Recursive Data Example: Find the Root ● Given a forest of rooted directed trees, for each node, find the root of the tree containing the node  Parallel approach: for each node, find its successor’s successor, repeat until no changes – O(log n) vs. O(n) 4 3 2 1 6 5 7 4 3 2 1 6 5 7 4 3 2 1 6 5 7 Step 1 Step 2 Step 3 16 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp.