design & implementation involves three aspects
methods for decomposing work into discrete units called tasks
ways of coordinating tasks as they run in parallel
scalable techniques for sharing data needed to perform tasks
Understanding Tasks
tasks are sequential operations
work together to perform larger operation
important to identify tasks at a level of granularity that results in efficient
use of hardware resources
too fine a granularity results in excess management overhead
too coarse a granularity can lose opportunities for parallelism leaving cores idle
tasks should be as large as possible and independent of each other
Coordinating Tasks
order of execution & degree of parallelism constrained by application's underlying
algorithms
how tasks are coordinated depends upon pattern used
Scalable Sharing of Data
race conditions can be catastrophic
synchronization by blocking serializes access to shared resources
such synchronization reduces parallelism
can degrade performance & be error-prone
number of techniques to share data without blocking including
immutable read-only data
limit reliance on shared variables
merge local versions of mutable state at appropriate checkpoints
important to incorporate design principles into the design process that limit the
need for synchronization
Design Approaches
best approach
understand problem or application as a whole
look for potential parallelism across entire application
prepare program for parallel execution
circular dependencies exist with techniques for decomposition, coordination &
scalable sharing
Patterns
Parallel Loop Pattern - parallel loops apply an independent operation to
multiple inputs simultaneously
Parallel Task Pattern - parallel tasks establish parallel control flow in
the style of fork and join
Parallel Aggregation Pattern - parallel aggregation introduces special steps
in the algorithm for merging partial results
Futures Pattern aka Task Graph Pattern - futures make data flow dependencies
between tasks explicit
Dynamic Task Parallelism Pattern - a divide-and-conquer approach, spawns
new tasks on demand
Pipelines Pattern - pipelines consist of components that are connected by
queues. all components run in parallel and the order of inputs is respected
Terminology Distinction
concurrency - goal is to prevent thread starvation
parallelism - maximize processor usage accross all available cores
Limits of Parallelism - Amdahl's Law
improvement provided by parallelsim limited by amount of sequential processing
maximum increase in speed limited to 1/total percentage of time for sequential processing
performance increase by adding cores is not linear
Tips
always try for the simplest approach
stay at highest possible level of abstraction & use constructs or a library
that does parallelism's heavy lifting
use inherent parallelism incorporated into web server or database
use API to encapsulate parallelism
consider overall architecture of application when thinking about how to parallelize
it
use patterns
restructuring algorithm for parallelism is more important than making low-level
improvements to code that was intended to run serially
don't share data among concurrent tasks unless absolutely necessary
low-level primitives such as threads and locks only as last resort, raise level
of abstraction from threads to tasks