Unit 4: Functional Data Parallelism
High-level Performance Concepts/Lessons
Sets: By abstracting away element order, it is easy to process
elements in parallel
Pure functions: Do not have side effects
·
Easier to reason about
Work/span: If this ratio does not improve, the parallelism of your
application is limited (Convex Hull example)
Map/Reduce pattern: Map a computation over a set, and then combine (reduce) the
results into an aggregated result
High-level Correctness Concepts/Lessons
Immutability: Don’t need to worry about stuff like data races!
Determinism: Parallel code should behave like sequential counterpart
Code-level Concepts/Lessons
Sample Learning Outcomes
·
Write parallel algorithms with F#, LINQ, and Accelerator
code, and be able to achieve speedup.
·
When naive
use of PLINQ, Accelerator, or F# does not result in expected speedups, be able
to analyze code and identify problems preventing speedups.
·
Be able to
use immutability and pure functions to write clear, race-free parallel code in
C#.
Assignment Ideas
Pick
a sequential program (Example: Olden benchmarks) and rewrite it in F#. Add
PLINQ and Array Accelerator code, to try to improve performance. Identify
performance bottlenecks, and potential future improvements.
Resources
Parallel Extensions Samples & Extras (http://code.msdn.microsoft.com/ParExtSamples):
·
LINQRayTracer
·
ParallelGrep
·
NQueens
·
ShakespeareanMonkeys
·
SpellChecker
·
Sudoko
·
VisualizePartitioning
Parallel Programming with Microsoft .NET
book (http://parallelpatterns.codeplex.com):
·
PLINQ in Chapter 2 (Parallel Loops)
·
MapReduce from Chapter 4 (Parallel Aggregation)
·
Recursion from Chapter 6 (Dynamic Task Parallelism)
·
Immutable types from Appendix A (Adapting
Object-Oriented Patterns)