New version page

MIT 6 189 - Design Patterns for Parallel Programming

This preview shows page 1-2-14-15-30-31 out of 31 pages.

View Full Document
View Full Document

End of preview. Want to read all 31 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

UntitledMIT 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 Lecture 6 Design Patterns for Parallel Programming I 16.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 20074 Common Steps to Creating a Parallel Program 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 Processes Parallel Processors computation program 26.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Decomposition (Amdahl’s Law) ● Identify concurrency and decide at what level to exploit it ● Break up computation into tasks to be divided among processes  Tasks may become available dynamically  Number of tasks may vary with time ● Enough tasks to keep processors busy  Number of tasks available at a time is upper bound on achievable speedup 3 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Assignment (Granularity) ● Specify mechanism to divide work among core  Balance work and reduce communication ● Structured approaches usually work well  Code inspection or understanding of application  Well-known design patterns ● As programmers, we worry about partitioning first  Independent of architecture or programming model  But complexity often affect decisions! 4 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Orchestration and Mapping (Locality) ● Computation and communication concurrency ● Preserve locality of data ● Schedule tasks to satisfy dependences early 5 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Parallel Programming by Pattern ● Provides a cookbook to systematically guide programmers  Decompose, Assign, Orchestrate, Map  Can lead to high quality solutions in some domains ● Provide common vocabulary to the programming community  Each pattern has a name, providing a vocabulary fordiscussing solutions ● Helps with software reusability, malleability, and modularity  Written in prescribed format to allow the reader to quickly understand the solution and its context ● Otherwise, too difficult for programmers, and software will notfully exploit parallel hardware 6 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007History ● Berkeley architecture professor Christopher Alexander ● In 1977, patterns for city planning, landscaping, and architecture in an attempt to capture principles for “living” design 7 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Example 167 (p. 783): 6ft Balcony Whenever you build a balcony, a porch, a gallery, or aterrace always make it at least six feet deep. If possible,recess at least a part of it into the building so that it is notcantilevered out and separated from the building by a simpleline, and enclose it partially.Therefore:six feet deepImage by MIT OpenCourseWare.8 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Patterns in Object-Oriented Programming ● Design Patterns: Elements of Reusable Object-Oriented Software (1995)  Gang of Four (GOF): Gamma, Helm, Johnson, Vlissides  Catalogue of patterns  Creation, structural, behavioral 9 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 tasks  Code and data structuring patterns ● Algorithm Structure ● Implementation Mechanisms  Map tasks to processes to  Low level mechanisms used exploit parallel architecture to write parallel programs Patterns for Parallel Programming. Mattson, Sanders, and Massingill (2005). 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 200710Here’s my algorithm. Where’s the concurrency? MPEG bit stream MPEG Decoder VLD macroblocks, motion vectors splitfrequency encodedmacroblocks differentially codedmotion vectors ZigZag IQuantization Motion Vector Decode Picture Reorder join IDCT motion vectors spatially encoded macroblocks recovered picture Saturation Repeat Motion Compensation Color Conversion Display 11 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Here’s my algorithm. Where’s the concurrency? MPEG bit stream MPEG Decoder VLD macroblocks, motion vectors splitfrequency encodedmacroblocks differentially codedmotion vectors spatially encoded macroblocks motion vectors IDCT IQuantization ZigZag Saturation Motion Vector Decode Repeat join Motion Compensation recovered picture Picture Reorder Color Conversion Display ● Task decomposition  Independent coarse-grained computation  Inherent to algorithm ● Sequence of statements (instructions) that operate together as a group  Corresponds to some logical part of program  Usually follows from the way programmer thinks about a problem 2 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 20071Here’s my algorithm. Where’s the concurrency? MPEG bit stream MPEG Decoder VLD macroblocks, motion vectors splitfrequency encodedmacroblocks differentially codedmotion vectors spatially encoded macroblocks motion vectors join IDCT IQuantization ZigZag Saturation Motion Vector Decode Repeat Motion Compensation recovered picture Picture Reorder Color Conversion Display ● Task decomposition  Parallelism in the application ● Data decomposition  Same computation is applied to small data chunks derived from large data set 13 6.189 IAP 2007 MIT Dr. Rodric Rabbah © Copyrights by IBM Corp. and by other(s) 2007Here’s my algorithm. Where’s the concurrency? MPEG bit stream MPEG Decoder VLD macroblocks, motion vectors splitfrequency encodedmacroblocks differentially


View Full Document
Loading Unlocking...
Login

Join to view Design Patterns for Parallel Programming 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 Design Patterns for Parallel Programming 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?