Parallel Programming

These comprehensive notes cover the presentation slides based on An Introduction to Parallel Programming by Peter Pacheco:

Overview & Foundational Concepts

• Book Reference: An Introduction to Parallel Programming by Peter Pacheco (Elsevier Inc., 2010).

  
  

• Serial Hardware & Software: Standard computing involves input, execution of programs, and output, where the computer executes a single program at a time.

  
  

• Why Parallel Programming?: Running multiple independent instances of a serial program is generally not helpful (e.g., opening multiple instances of a game). The core objective of parallel programming is making a single application execution run faster.

  
  

Parallel Programming Strategies

• Task Parallelism: Partitioning different tasks required to solve a problem among available processing cores.

  
  

• Data Parallelism: Partitioning the problem's dataset among processing cores, with each core executing similar operations on its section of data.

  
  

• Analogy (Professor P & TAs grading 300 exams with 15 questions):

  
  
  

  • Data Parallelism: Each of the 3 TAs receives a subset of the data (e.g., 100 exams each) and grades all 15 questions.

    
    

  • Task Parallelism: Each TA is assigned specific questions across all exams (e.g., TA 1 grades Q1–5, TA 2 grades Q6–10, TA 3 grades Q11–15).

    
    

  • Partitioning Strategies: Can be split by number, workload, or specific task boundaries.

    
    

Core Coordination

Parallel execution requires cores to coordinate using three main mechanisms:

1. Communication: Sending partial results or data from one core to another.

   
   

2. Load Balancing: Distributing work evenly to ensure no single core becomes a bottleneck.

   
   

3. Synchronization: Coordinating execution speeds so faster cores do not progress too far ahead of others.

   
   

Memory Architectures & Models

1. Shared Memory Architecture

• System Layout: Multiple CPU cores access a single, shared address space over a memory bus. Compute nodes typically feature 1–2 CPUs with 10–14 cores each, utilizing local caches.

  
  

• Multi-Threading:

  
  
  

  • Threads exist within a process (1 process $\rightarrow$ multiple threads) and share the same address space.

    
    

  • Threads execute concurrently; if a shared resource is occupied, threads queue and wait.

    
    

  • Ideal performance is achieved by mapping each thread to a distinct, physical core.

    
    

  • Thread Lifecycle:

    
    
    

    • Forking: Master thread creates/starts new worker threads.

      
      

    • Joining: Termination and merging of worker threads back into the process.

      
      

2. Distributed Memory Architecture

• System Layout: Independent compute nodes, each containing its own local memory, linked together via a network interconnect.

  
  

• Inter-Process Communication: Processes cannot directly access each other's memory spaces and must communicate via explicitly passed messages (e.g., using MPI).

  
  

• Clusters: Commodity individual computers connected via a commodity network (e.g., Infiniband interconnect used in systems like Kamiak).

  
  

Single Program Models (Flynn's Taxonomy)

• Single Program (SP): Executing the same code base across all running threads or processes.

  
  

• SIMD (Single Instruction, Multiple Data): Every thread executes the exact same instruction at any clock cycle, but operates on different pieces of data.

  
  

• MIMD (Multiple Instruction, Multiple Data): Threads/processes independently execute different instructions on different data concurrently.

  
  

OpenMP Implementation (Shared Memory)

• Terminology: The group of threads executing inside a parallel block is called a team, consisting of one master thread and multiple worker threads.

  
  

• Compiler Guards: Protect OpenMP includes using macros in case the compiler lacks OpenMP support:

  
  
  

  C

  #ifdef _OPENMP
  # include <omp.h>
  #endif
  ```[cite: 1]
  

• Compilation:

  
  
  

  • Serial C code: gcc hello.c

    
    
    

    
    

  • OpenMP code: gcc -fopenmp hello.c

    
    
    

    
    

• Pragmas & Routines:

  
  
  

  • Parallel region declaration: #pragma omp parallel num_threads(thread_count)

    
    
    

    
    

  • Thread rank retrieval: omp_get_thread_num()

    
    
    

    
    

  • Total thread count retrieval: omp_get_num_threads()

    
    
    

    
    

Performance, Timing, & Scalability

• Timing Measurements: Can measure CPU time or wall-clock time between start and end checkpoints:

  
  
  

  • OpenMP timing function: omp_get_wtime()

    
    
    

    
    

  • MPI timing function: MPI_Wtime()

    
    
    

    
    

• Speedup & Theoretical Execution:

  
  
  

  • Speedup formula: $S = \frac{T_{\text{serial}}}{T_{\text{parallel}}}$

    
    
    

    
    

  • Theoretical ideal parallel runtime: $T_{\text{parallel}} = \frac{T_{\text{serial}}}{p}$ (where $p$ is the number of threads/cores).

    
    

  • Amdahl's Law: Demonstrates that overall speedup is limited by the sequential (non-parallelizable) portion of a program, causing speedup gains to plateau regardless of processor count.

    
    

• Reduction Operations:

  
  
  

  • Serial Reduction: Sequential chain of 7 operations across 1 thread.

    
    

  • Parallel Reduction: Tree-structured parallel combination of operations to reduce execution steps.