Question

The goal is to desing parallel programs that are flexible, efficient and simple.

Step 0 : Start by profiling a serial program to identify bottlenecks

Step 1 : Are there for opportunities for parallism?

• Can tasks be perforemd in parallel?
  • Function calls
  • Loops
• Can data be split and operated on in parallel?
  • Decomposition of arrays along rows, columns, blocks
  • Decomposition of trees into sub-trees
• Is there a pipeline with a sequence of stages?
  • Data preprocesing and analysis
  • Graphics rendering

Step 2 : What is the nature of the parallelism?

• Linear
  • Embarassingly parallel programs
• Recursive
  • Adaptive partitioning methods

Step 3 : What is the granularity?

• 10s of jobs
• 1000s of jobs

Step 4 : Choose an algorihtm

• Organize by tasks
  • Task parallelism
  • Dvidie and conquer
• Organize by data
  • Geometric decomposition
  • Recursvie decomposition
• Organize by flow
  • Pipeline
  • Event-based processing

Step 5 : Map to program and data structures

• Program structures
  • Single program multiple data (SPMD)
  • Master/worker
  • Loop parallelism
  • Fork/join
• Data structures
  • Shared data
  • Shared queue
  • Distributed array

Step 6 : Map to parallel environment

• Multi-core shared memrory
  • Cython with OpenMP
  • multiprocessing
  • IPython.cluster
• Multi-computer
  • IPython.cluster
  • MPI
  • Hadoop / Spark
• GPU
  • CUDA
  • OpenCL

Step 7 : Execute, debug, tune in parallel environment