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)