Chapter 1: Introduction To Parallel Programming

Motivation

• Moore’s law
  • chip density hits the physical limit
  • single core performance hits the physical limit
  • multi-core system emerge
• Hardware price drops
  • CPU
  • Memory
  • Storage
  • Network devices
• In need of parallel program
  • It is challenging
    • Hard to translate sequential program to parallel program
    • Hard to debug parallel program
  • Catch up with the rapid development of parallel hardware

Terminology

• Concurrent
  • can be fake parallelism based on fast switching
  • e.g. Unix Time-sharing system
• Parallel
  • Tightly coupled
  • e.g. High performance computing cluster
  • e.g. Supercomputer
• Distributed
  • Loosely coupled
  • grid computation
  • e.g. crypto network

Fundamental strategies

• A.k.a parallelism patterns, type of parallelism
• Data parallelism
  • divide the data into chunks
  • each chunk is processed in parallel
• Task parallelism
  • divide the program into tasks
  • each task is executed in parallel
• Hybrid
  • combine data parallelism and task parallelism

Coordination

• Synchronization
  • lock
  • barrier
• Communication
  • message passing
  • shared memory
• Load balancing
  • static
  • dynamic

Parallel programming models

• Shared memory
  • OpenMP
  • Pthreads
• Message passing (distributed memory)
  • MPI
• Data parallel
  • OpenCL (FYI)
  • CUDA (FYI)
• Task parallel
  • OpenMP
• Hybrid
  • MPI + OpenMP
  • MPI + Pthreads