Lecture 3 Patterns For Parallel Programming I

2y ago
12 Views
2 Downloads
2.87 MB
65 Pages
Last View : 1m ago
Last Download : 2m ago
Upload by : Macey Ridenour
Transcription

Lecture 3!Patterns for !Parallel Programming I!John Cavazos!Dept of Computer & Information Sciences!University of Delaware!www.cis.udel.edu/ cavazos/cisc879!CISC 879 : Advanced Parallel Programming

Overview Parallelizing a sequential program Design Patterns for Parallel Programs Finding Concurrency Algorithmic Structure Supporting StructuresImplementation MechanismsCISC 879 : Advanced Parallel Programming

Parallelizing a Program1.2.3.Study sequential program Compile and profile What are the “hot” spots?Look for parallelism opportunities Decompose the data or code Decomposing data implicitly decomposes codeOrchestrate and map tasksCISC 879 : Advanced Parallel Programming

Parallelization Common Steps1. Studyproblemor code2. Look for parallelismopportunities3. Try to keep all coresbusy doing useful workSlide Source: Dr. Rabbah, IBM, MIT Course 6.189 IAP 2007CISC 879 : Advanced Parallel Programming

Parallelization Common Steps1. Studyproblemor code2. Look for parallelismopportunities3. Try to keep all coresbusy doing useful workSlide Source: Dr. Rabbah, IBM, MIT Course 6.189 IAP 2007CISC 879 : Advanced Parallel Programming

Parallelization Common Steps1. Studyproblemor code2. Look for parallelismopportunities3. Try to keep all coresbusy doing useful workSlide Source: Dr. Rabbah, IBM, MIT Course 6.189 IAP 2007CISC 879 : Advanced Parallel Programming

Parallelization Common Steps1. Studyproblemor code2. Look for parallelismopportunities3. Try to keep all coresbusy doing useful workSlide Source: Dr. Rabbah, IBM, MIT Course 6.189 IAP 2007CISC 879 : Advanced Parallel Programming

Decomposition Identify Concurrency Decide level to exploit Understand algorithm and datastructures! May require restructuring algorithm or anentirely new algorithmSlide Source: Dr. Rabbah, IBM, MIT Course 6.189 IAP 2007CISC 879 : Advanced Parallel Programming

Decomposition (cont’d) Break computation into tasks Divided among processesTasks may become available dynamicallyNumber of tasks can vary with timeWant enough tasks to keep processors busy.Slide Source: Dr. Rabbah, IBM, MIT Course 6.189 IAP 2007CISC 879 : Advanced Parallel Programming

Tasks to Processes Specify mechanism to divide workBalance of computationReduce communication andsynchronizationStructured approaches work well Code inspection and understandingalgorithmUsing design patterns (next lecture)Slide Source: Dr. Rabbah, IBM, MIT Course 6.189 IAP 2007CISC 879 : Advanced Parallel Programming

Granularity Ratio of computation and communication Fine-grain parallelism Tasks execute little comp. between comm. Easy to load balance If too fine, communication may take longerthan computationCoarse-grain parallelism Long computations between communicationHarder to load balance More opportunity for performance increase Which should we use?CISC 879 : Advanced Parallel Programming

Orchestration and Mapping Computation and communicationconcurrencySchedule task to satisfy dependencesPreserve locality of dataSlide Source: Dr. Rabbah, IBM, MIT Course 6.189 IAP 2007CISC 879 : Advanced Parallel Programming

Lecture 5: Overview Parallelizing a sequential ProgramDesign Patterns for Parallelization Finding ConcurrencyAlgorithmic StructureSupporting StructuresImplementation MechanismsCISC 879 : Advanced Parallel Programming

Patterns for Parallelization Parallelization is a difficult problem Hard to get everything to work correctly!Hard to fully exploit parallel hardwareOne Solution: Design PatternsCISC 879 : Advanced Parallel Programming

Design Patterns Cookbook for parallel programmers Can lead to high quality solutionsProvides a common vocabularySoftware reusability and modularityCISC 879 : Advanced Parallel Programming

Architecture Patterns Christopher Alexander Developed patterns forarchitecture Berkeley architecture professorCity planningLayout of windows in a roomAttempt to capture principles for“living” designsCISC 879 : Advanced Parallel Programming

Patterns for OOP Brought patterns to computerscienceDesign Patterns: Elements ofReusable Object-OrientedSoftware (1994) Gamma et al. (Gang of Four)Catalogue of “patterns”Not a finished solution!CISC 879 : Advanced Parallel Programming

Parallel Patterns Book Patterns for Parallel Programming. Mattson et al. (2005)Four Design Spaces Finding ConcurrencyAlgorithm Structure Supporting Structures Map tasks to processesCode and data structuring patternsImplementation Mechanisms Low-level mechanisms for writingprogramsCISC 879 : Advanced Parallel Programming

Finding Concurrency Expose concurrent task or dataDecomposition Dependency Analysis Task, Data, PipelineControl dependencesData dependencesDesign Evaluation Suitability for target platformDesign qualityCISC 879 : Advanced Parallel Programming

Decomposition Data (domain) decomposition Task (functional) decomposition Break data up independent unitsBreak problem into parallel tasksPipeline decompositionCISC 879 : Advanced Parallel Programming

Data Decomposition Also known as Domain DecompositionImplied by Task DecompositionWhich decomposition more natural to startwith, data or tasks?1) Decide how data is divided2) Decide how tasks should be performedSlide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Data Decomposition Data decomposition is good when: Main computation manipulating a largedata structureSimilar operations applied to diff. parts ofdata structure (e.g., SIMD)Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Common Data Decompositions Array-based computations Linked list data structures Decompose in a variety of ways, includingrows, columns, blocks (tiles)Break up into sub-listsRecursive-data structures Example: Parallel updates of large tree, bydecomposing into small treesCISC 879 : Advanced Parallel Programming

Data DecompositionFind the largest element of an arraySlide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Data DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Data DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Data DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Data DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Data DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Data DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Data DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Data DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Data DecompositionFind the largest element of an arrayCPU 0CPU 1CPU 2CPU 3Slide Decomposition Processing five data set (Step 5)CPU 0CPU 1CPU 2Data set 0Data set 1Data set 2Data set 3Data set 4Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Pipeline Decomposition Processing five data set (Step 6)CPU 0CPU 1CPU 2Data set 0Data set 1Data set 2Data set 3Data set 4Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Pipeline Decomposition Processing five data set (Step 7)CPU 0CPU 1CPU 2Data set 0Data set 1Data set 2Data set 3Data set 4Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Pipeline Decomposition Forces Flexibility Efficiency Deeper pipelines are betterStages of pipeline should not cause bottleneckSimplicity Manageable chunks of codeSlide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Dependency Analysis Control and Data DependencesDependence GraphGraph (nodes, edges)Data dependency graph (nodes variables)Control flow (nodes basic blocks)Call graph (nodes functions)Edge indicates possible control or data dependency Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Dependency Analysisfor (i 0; i 3; i )a[i] b[i] / 2.0;b[0]2b[1]2b[2]2///a[0]a[1]a[2]Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Dependency Analysisfor (i 0; i 3; i )a[i] b[i] / 2.0;b[0]2Domain e Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Dependency Analysisfor (i 1; i 4; i )a[i] a[i-1] * b[i];a[0]b[1]b[2]b[3]***a[1]a[2]a[3]Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Dependency Analysisfor (i 1; i 4; i )a[i] a[i-1] * b[i];a[0]b[1]No domain decompositionb[2]b[3]***a[1]a[2]a[3]Slide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Dependency Analysisa f(x, y, z);b g(w, x);t a b;c h(z);s t / c;wxyzgfhbact/sSlide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Dependency Analysisa f(x, y, z);b g(w, x);t a b;c h(z);s t / c;Taskdecompositionwith 3 CPUs.wxyzgfhbact/sSlide Source: Intel Software College, Intel Corp.CISC 879 : Advanced Parallel Programming

Evaluate Design Is the design good enough? YES - move to next phaseNO - re-evaluate previous patternsForces Suitability to target platform Design quality Should not depend on underlying architectureTrade-offs between simplicity, flexibility, and efficiencyPreparation for next phase Algorithm StructureCISC 879 : Advanced Parallel Programming

Read for Next Time Reengineering for Parallelism: An Entry Point forPLPP (Pattern Language for Parallel Programming)for Legacy Applications plop2005.pdfCISC 879 : Advanced Parallel Programming

CISC 879 : Advanced Parallel Programming Parallel Patterns Book Patterns for Parallel Programming. Mattson et al. (2005) Four Design Spaces Finding Concurrency Algorithm Structure Map tasks to processes Supporting Structures

Related Documents:

Introduction of Chemical Reaction Engineering Introduction about Chemical Engineering 0:31:15 0:31:09. Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18 Lecture 19 Lecture 20 Lecture 21 Lecture 22 Lecture 23 Lecture 24 Lecture 25 Lecture 26 Lecture 27 Lecture 28 Lecture

Bruksanvisning för bilstereo . Bruksanvisning for bilstereo . Instrukcja obsługi samochodowego odtwarzacza stereo . Operating Instructions for Car Stereo . 610-104 . SV . Bruksanvisning i original

10 tips och tricks för att lyckas med ert sap-projekt 20 SAPSANYTT 2/2015 De flesta projektledare känner säkert till Cobb’s paradox. Martin Cobb verkade som CIO för sekretariatet för Treasury Board of Canada 1995 då han ställde frågan

service i Norge och Finland drivs inom ramen för ett enskilt företag (NRK. 1 och Yleisradio), fin ns det i Sverige tre: Ett för tv (Sveriges Television , SVT ), ett för radio (Sveriges Radio , SR ) och ett för utbildnings program (Sveriges Utbildningsradio, UR, vilket till följd av sin begränsade storlek inte återfinns bland de 25 största

Hotell För hotell anges de tre klasserna A/B, C och D. Det betyder att den "normala" standarden C är acceptabel men att motiven för en högre standard är starka. Ljudklass C motsvarar de tidigare normkraven för hotell, ljudklass A/B motsvarar kraven för moderna hotell med hög standard och ljudklass D kan användas vid

LÄS NOGGRANT FÖLJANDE VILLKOR FÖR APPLE DEVELOPER PROGRAM LICENCE . Apple Developer Program License Agreement Syfte Du vill använda Apple-mjukvara (enligt definitionen nedan) för att utveckla en eller flera Applikationer (enligt definitionen nedan) för Apple-märkta produkter. . Applikationer som utvecklas för iOS-produkter, Apple .

Parallel Programming Design patterns and parallel patterns GrPPI architecture 10/105. GrPPI Introduction Design patterns and parallel patterns Software design There are two ways of constructing a softwa

Lecture 1: A Beginner's Guide Lecture 2: Introduction to Programming Lecture 3: Introduction to C, structure of C programming Lecture 4: Elements of C Lecture 5: Variables, Statements, Expressions Lecture 6: Input-Output in C Lecture 7: Formatted Input-Output Lecture 8: Operators Lecture 9: Operators continued