close

Вход

Забыли?

вход по аккаунту

?

A Pattern Language for Parallel Programming

код для вставкиСкачать
A Pattern Language for
Parallel Programming
Beverly Sanders
University of Florida
Overview of talk
History of pattern languages
Motivation for a pattern language for
parallel programming
Pattern example: Reengineering for
Parallelism
Tour through the entire pattern language
via a programming example
History �60s and �70s
Berkeley architecture
professor Christopher
Alexander
253 patterns for city
planning, landscaping, and
architecture
Attempted to capture
principles for “living” design.
Example: Six Foot Balcony
Balconies less than six feet deep are hardly ever
used
Discussion of what makes a good balcony
Therefore: Whenever you build a balcony or a
porch, always make it at least six feet deep.
If possible, recess at least a part of it into the
building so that it is not cantilevered out and
separated from the building by a simple line,
and enclose it partially
A new approach to design
Not just a collection of patterns, but a
pattern language
– Patterns lead to other patterns
– Patterns are hierarchical and compositional
– Embodies design methodology and
vocabulary
Small impact on architectural practice
Patterns in Object-oriented
Programming
OOPSLA’87 Kent Beck and Ward Cunningham
1995 Design Patterns: Elements of Reusable
Object-Oriented Software
Gang of Four (GOF): Gamma, Helm, Johnson,
Vlissides,
– catalog of patterns
– Creation, structural, behavioral
PLoP Conferences
GOF Pattern Example
Behavioral Pattern: Visitor
– Separate the structure of an object collection
from the operations performed on that
collection.
– Example: Abstract syntax tree in a compiler
Multiple node types (declaration, command,
expression, etc.)
Action during traversal depends on both type of
node and compiler pass (type checking, code
generation)
Can add new functionality by implementing new
visitor without modifying AST code.
Impact of GOF book
Good solutions to frequently recurring
problems
New vocabulary
Pattern catalog
Significant influence on object-oriented
programming!
Design Pattern
High quality solution to frequently recurring
problem in some domain
Each pattern has a name, providing a
vocabulary for discussing the solutions
Written in prescribed format to allow the
reader to quickly understand the solution
and its context
A pattern format
Name
Also known as
Problem
Context
Forces
Solution
Examples and known uses
Related patterns
…
Pattern Language
Carefully structured collection of patterns
Structure embodies a design methodology
and leads user through the language so
that complex designs can be developed
using patterns
Provides domain specific advice to the
designer
Not a programming language
Parallel Programming
Parallel hardware becoming increasingly
mainstream and inexpensive
– Multicore CPUs in desktop PCs and servers
– Clusters
Software to fully exploit the hardware currently
rare (except specialized area of high
performance computing)
Can a pattern language providing guidance for
the entire development process make parallel
programming easier?
Structure of the pattern
language
– Reengineering for Parallelism pattern for
dealing with legacy sequential code
4 Design spaces
– Finding Concurrency
Help designer expose exploitable concurrency—
find high level task and data decomposition
– Algorithm Structure
Help designer map tasks to processes or threads
to best take advantage of the potential
concurrency
Structure of the pattern
language, continued
– Supporting Structures
Code structuring patterns
Distributed and thread-safe data structures
– Implementation Mechanisms
Low level mechanisms used to write parallel
programs
3 categories of mechanisms
– UE (process/thread) Management
– Synchronization
– Communication
Starting with legacy sequential
application?
Reengineering for Parallelism pattern
provides guidance to
– Manage the process
– Determine what to change
We’ll look at this as an example pattern
Reengineering for Parallelism
Problem:
How can existing applications be parallelized using PLPP to improve
performance by making use of parallel hardware?
Context:
We have legacy code that cannot be rewritten from scratch, need to
improve performance…
Forces:
– User base has expectations for behavior
– Existing application may not be fully understood
– Amdahl’s law pushes programmer to avoid sequential bottlenecks at
any cost, which may imply wholesale restructuring of the program
– Starting point is working code that embodies significant programming
work, bug fixes, and knowledge. Minimizing changes is desirable. It is
rarely feasible to make sweeping rewrites.
– Concurrency introduces new classes of errors that are hard to detect
and make software difficult to validate.
Solution:Preparation
Survey the landscape
– Pattern provides a list of questions to help assess
existing code
– Many are the same as in any reengineering project
– Is program numerically well-behaved?
Define the scope and get users’ buy-in
–
–
–
–
Required precision of results
Input range
Performance
Feasibility (back of envelope calculations)
Define a testing protocol
Solution: Continued
Identify hot spots—where is most of the time
spent?
– Look at code
– Use profiling tools
Parallelization
– Start with hot spots first
– As much as possible, make sequence of small
changes, each followed by testing
– Use PLPP patterns (pattern provides guidance)
Reengineering for Parallelism
Pattern, continued
Extended example
Discussion of related patterns
– Patterns for legacy code
– Patterns for parallel programming
Example: Molecular dynamics
Simulate motion in large molecular system
Example application: how protein
interacts with drug
Forces
– Bonded forces within a molecule
– Long-range forces between molecules
Not tractable N2
Use cutoff method—only consider forces from
neighbors that are “close enough”
Sequential Molecular dynamics
simulation
real atoms(3,N)
real force(3,N)
int neighbors(2,M)
loop over time steps
Compute bonded forces
Compute neighbors
Compute long-range forces
Update position …
end loop
Starting with legacy sequential
code?
If so start with the
Reengineering for Parallelism pattern
Next: Finding Concurrency Design Space
Finding Concurrency Design
Space
Decomposition Patterns
Dependency Analysis
Patterns
Design Evaluation
Finding Concurrency Design
Space
Decomposition Patterns
Task Decomposition
Dependency Analysis
Patterns
Design Evaluation
Data Decomposition
Molecular dynamics
decomposition
Each function is a loop over atoms
Suggests task decomposition with each
task corresponding to a loop iteration
(update of an atom)
– tasks for bonded forces
– tasks for long -range forces
– tasks to update positions
– tasks to compute neighbor list
Data shared between the tasks
Finding Concurrency Design
Space
Decomposition Patterns
Dependency Analysis
Group tasks
Patterns
Design Evaluation
Order tasks
Data Sharing
Molecular dynamics
dependency analysis
Neighbor list
Bonded forces
Long-range forces
Update position
next time step
Molecular dynamics
dependency analysis
Neighbor list
Bonded forces
neighbors
Long-range forces
atoms(3,N)
forces(3,N)
Read
Update position
Write
Accumulate
next time step
Finding Concurrency Design
Space
Decomposition Patterns
Dependency Analysis
Patterns
Suitability for target platform
Design Quality (flexibility, efficiency, simplicity)
Preparation for the next phase
Design Evaluation
Design evaluation for molecular
dynamics
Target architecture for example: distributed
memory cluster, message passing
Data sharing has enough special properties
(read only, accumulate, temporal constraints)
that we should be able to make it work in a
distributed memory environment.
Design seems OK, move to next design space
Algorithm structure design
space
Map tasks to Units of Execution (threads
or processes)
Target platform properties
– number of UEs
– communication between UEs
Major organizing principle
Organize by tasks?
Recursive?
no
Task
Parallelism
yes
Divide and Conquer
Organize by data?
Recursive?
no
Geometric
Decomposition
yes
Recursive Data
Organize by ordering?
yes
Regular?
no
Event-based
Coordination
Pipeline
Algorithm structure for
molecular dynamics
Organized by task
Task decomposition pattern
– Granularity: decide bonded forces not worth
parallelizing now.
– Load balancing: static OK, partition
iterations of original loop (over atoms) to UEs
– Termination: easy since number of UEs can
be determined in advance
Separable dependencies
Multiple tasks update force array
concurrently by adding to its value.
This type of update is called accumulation
Allows dependencies to be separated
from concurrent part of computation
– Each UE gets a local copy of data
– Updates local copy
– After local updates completed, reduce
(combine results using associative operator)
Supporting Structures Design
Space
A intermediate stage between algorithm
structures and implementation
mechanisms (Similar level to GOF)
Program structuring patterns
– SPMD, Fork/Join, Loop Parallelism,
Master/Worker
Data structures
– Shared queue, Distributed array, Shared data
Choose SPMD Pattern
Single program multiple data.
– Each UE executes exactly the same program
– Uses process ID to determine behavior
– Issues: replicate or partition data,
computation?
Replicate or partition data in MD?
– Replicate atoms, force.
– Partition neighbor list
Duplicate non-parallelized parts of
computation, or designate one process to
compute?
– Duplicate all computation except I/O.
Parallel Simulation
real atoms(3,N)
real force(3,N)
int neighbors(2,M)
myID = getProcessID
nprocs = getNumberProcesses
loop over time steps
Compute bonded forces //replicate computation
Compute neighbors
//only for atoms assigned to myID
Compute long range forces
globalSum(N,&forces)
//reduction to combine all force arrays
Update position …
end loop
if (myid == printID) printResults
Implementation Mechanisms
Describes low level mechanisms used to
write parallel programs
3 categories of mechanisms
– UE (process/thread) Management
– Synchronization
– Communication
Not in pattern format
We discuss OpenMP, MPI, and Java
Implement Simulation
For our target platform, MPI is the best
choice
Need to add standard code for initialization
and MPI specific reduction operator to
previous solution
Pattern languages evolve
A pattern language should not be
considered a static document:
– Evaluate and revise
– Extend with new patterns: new parallel
programming models, specific application
domains
– We added the Reengineering for Parallelism
pattern as a result of feedback from readers
For more information
Mattson, Sanders, and
Massingill. Patterns for
Parallel Programming.
Addison-Wesley Software
Patterns Series. 2005
Reengineering for
Parallelism, PLoP05
www.cise.ufl.edu/research/ParallelPatterns
Acknowledgements and
collaborators
The pattern language is joint work with:
– Tim Mattson, Intel
– Berna Massingill, Trinity University
Supported by NSF and Intel
Документ
Категория
Презентации
Просмотров
10
Размер файла
274 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа