Parallel Computing (IT-803 (D)) - Unit 5 Short Notes

UNIT 5: Parallel Computing

1. Fundamental Concepts and Terminologies

1.1 Parallelism vs. Pipelining

[!TIP] Exam often asks to distinguish; focus on simultaneity (parallelism) vs overlap (pipelining).

1.2 Serial vs. Parallel Processing

• Serial Processing: Instructions executed one after another on a single processor.

$$ T_s = \text{Sum of all instruction execution times} $$

• Parallel Processing: Instructions executed concurrently on multiple processors.

$$ T_p = \text{Maximum time taken by any processor} + \text{communication overhead} $$

• Key Difference: Resource utilization—serial is sequential; parallel uses multiple resources simultaneously.

1.3 Control Flow vs. Data Flow Computers

1.4 Uniprocessor vs. Multiprocessor Systems

• Uniprocessor: Single CPU; executes one instruction stream at a time. Relies on pipelining, superscalar techniques for performance.

• Multiprocessor: Two or more CPUs sharing memory/IO. Supports true concurrent execution of multiple instruction streams.

• Distinction: Physical processors vs logical parallelism via pipelining/SIMD.

1.5 Flynn’s Taxonomy (Categories of Parallelism)

2. Parallel Architectures

2.1 MIMD Multiprocessors: Key Characteristics

Distinguish from multiple computer systems/networks:

1. Shared Memory: Processors share a global physical address space (UMA/NUMA).

2. Tight Coupling: Processors connected via high-speed bus or interconnect (e.g., Intel UPI, AMD Infinity Fabric).

3. Single OS Image: One operating system manages all processors (vs. networked systems with individual OS instances).

4. Low Communication Latency: Memory access latency is relatively uniform (UMA) or predictable (NUMA), unlike network latency in clusters.

2.2 Pipelining: Speedup Analysis and Proof

• Ideal Speedup for a k-stage linear pipeline:

$$ S_{ideal} = k $$

• Proof:

  • Non-pipelined execution of n tasks:

$$ T_s = n \times t_{task} \quad \text{(where } t_{task} \text{ is time per task)} $$

• Pipelined execution: First task takes k clock cycles; subsequent tasks take 1 cycle each.

$$ T_p = k + (n - 1) \times 1 \quad \text{(assuming 1 cycle per stage)} $$

• Speedup:

$$ S = \frac{T_s}{T_p} = \frac{n \times t_{task}}{k + (n - 1)} $$

• For large n and if $$\displaystyle t_{task} = k $$ cycles (each stage takes 1 cycle):

$$ S \approx \frac{n \times k}{n} = k $$

• Real-World Limiting Factors: Pipeline hazards (structural, data, control), imbalance in stage latencies.

[!TIP] Exam proof must show ideal case assumption (balanced stages, no hazards) and derive $S \leq k$.

2.3 Modern GPU Architecture: Design Principles & Applications

• Design Principles:

  • Massively Parallel: Thousands of small, efficient cores (e.g., NVIDIA CUDA cores).

  • SIMT (Single Instruction, Multiple Threads): Groups of threads (warps) execute same instruction on different data.

  • High Memory Bandwidth: Specialized memory (GDDR6, HBM) to feed many cores.

  • Hierarchical Organization: Streaming Multiprocessors (SMs) containing cores, shared memory, registers.

• Application Domains:

  • Graphics Rendering (primary).

  • Scientific Computing (CFD, molecular dynamics).

  • AI/ML Training & Inference (matrix operations).

  • Cryptocurrency Mining (hash computations).

2.4 Architectural Characteristics of Future High-Performance Systems

1. Heterogeneous Integration: CPUs + GPUs + accelerators (FPGAs, ASICs like TPUs) on package.

2. Memory-Centric Computing: Processing near memory (PIM) to reduce data movement.

3. Chiplet-Based Design: Modular dies connected via high-speed interconnects (e.g., AMD Infinity Fabric).

4. Advanced Interconnects: Silicon photonics, 3D stacking for bandwidth/density.

5. Exascale Focus: Energy efficiency (flops/watt) alongside raw performance.

3. Memory Systems and Cache Coherence

3.1 Caches Using Virtual Addresses: Disadvantages

1. Alias Problem: Same physical line may be cached at multiple virtual addresses → coherence issues.

2. Flush/Invalidate Overhead: Context switches require flushing entire TLB/cache or using ASIDs (complex).

3. Coherence Complexity: Virtual-to-physical mapping varies per process; maintaining coherence across processes is harder.

4. Security Risks: Potential for cache timing attacks (e.g., Spectre) due to shared virtual caches.

3.2 Shared Cache Organizations

3.3 Cache Coherence Protocols: Snooping vs. Directory-Based

3.4 Multicache Coherence Problem & Mitigation

• Problem: In systems with multiple caches, multiple copies of a memory block can exist. Writes by one processor must be made visible to others to maintain sequential consistency.

• Challenges: False sharing, write broadcast storms, latency.

• Mitigation Strategies:

  1. Snooping Protocols (MESI, MOESI): State machines per cache line.

  2. Directory Protocols: Track sharers to avoid unnecessary broadcasts.

  3. Write-Invalidate vs. Write-Update: Invalidate other copies vs. update all copies on write.

  4. Non-Blocking Caches: Allow hits during coherence misses.

  5. Hardware Prefetching: Reduce latency impact.

4. Parallel Programming Models and Languages

4.1 Designing Parallel Programs: Step-by-Step Methodology

1. Decomposition: Partition problem (task/data/functional).

2. Mapping: Assign tasks/data to processors (static/dynamic).

3. Orchestration: Manage communication, synchronization, load balancing.

4. Implementation: Choose model (MPI, OpenMP, CUDA) and code.

5. Evaluation: Test, profile, optimize (speedup, efficiency).

4.2 Distributed-Memory Programming with MPI

• Message Passing Interface (MPI): Standard library for message-passing in distributed memory.

• Key Concepts:

  • Communicator: Group of processes (e.g., MPI_COMM_WORLD).

  • Point-to-Point: MPI_Send, MPI_Recv (blocking/non-blocking).

  • Collective: MPI_Bcast, MPI_Reduce, MPI_Scatter/Gather.

  • Datatypes: Define custom data layouts.

  • Topologies: Virtual process arrangements (cartesian, graph).

• Typical Pattern: Initialize → Compute → Communicate → Reduce results.

4.3 Transactional Memory vs. Traditional Transactions

4.4 I/O Handling in Parallel Programming Languages

• Challenges: Consistency, ordering, performance bottlenecks, POSIX semantics in distributed FS.

• Strategies:

  1. Parallel I/O Libraries: MPI-IO (collective I/O, striping), HDF5, NetCDF.

  2. Two-Phase I/O: Aggregators merge requests from multiple processes.

  3. File System Support: Lustre, GPFS (parallel file systems).

  4. Consistency Models: Session semantics, MPI consistency guarantees.

4.5 Thread Management

• Creation: pthread_create, std::thread, OpenMP #pragma omp parallel.

• Synchronization:

  • Locks/Mutexes: Mutual exclusion (critical sections).

  • Barriers: pthread_barrier, omp barrier (wait for all threads).

  • Condition Variables: Wait/signal for state changes.

  • Atomic Operations: Lock-free synchronization (std::atomic).

• Scheduling:

  • Static: Threads assigned to processors at start (low overhead).

  • Dynamic: Work-stealing (e.g., OpenMP schedule(dynamic)), better load balance.

4.6 Parallel Data Management

• Distribution:

  • Block: Contiguous chunks to processors.

  • Cyclic: Round-robin assignment (good for load balance).

  • Block-Cyclic: Hybrid (e.g., ScaLAPACK).

• Partitioning: Decompose data structures (arrays, graphs) to minimize communication.

• Consistency:

  • Memory Models: Sequential consistency, weak consistency, release consistency.

  • Strategies: Barriers, locks, transactional memory.

5. Performance Evaluation

5.1 Key Performance Metrics

• Speedup ($S$):

$$ S = \frac{T_s}{T_p} $$

where $$\displaystyle T_s $$ = sequential time, $$\displaystyle T_p $$ = parallel time.

• Efficiency ($E$):

$$ E = \frac{S}{p} = \frac{T_s}{p \times T_p} $$

Measures resource utilization ($0 \leq E \leq 1$).

• Scalability:

  • Strong Scaling: Fix problem size, increase processors. Goal: $$\displaystyle T_p \propto 1/p $$.

  • Weak Scaling: Fix problem size per processor, increase total problem size. Goal: $$\displaystyle T_p $$ constant.

• Cost-Effectiveness:

$$ \text{Cost} = p \times T_p $$

Optimal when cost $$\displaystyle \approx T_s $$ (linear speedup).

• Isoefficiency Function: $f(p)$ relating problem size to processors to maintain fixed efficiency.

[!TIP] Remember Amdahl's Law ($$\displaystyle S \leq 1/(f_s + (1-f_s)/p) $$) limits speedup; Gustafson's Law argues for weak scaling.

6. Parallel Algorithms and Patterns

6.1 Map, Scan, and Fusion Operations

• Map: Apply function $f$ independently to each element.

$$ \text{output}[i] = f(\text{input}[i]) \quad \forall i $$

Embarrassingly parallel; no dependencies.

• Scan (Prefix Sum): Compute all prefix sums of an associative operator $\oplus$.

$$ \text{output}[i] = \text{input}[0] \oplus \text{input}[1] \oplus \dots \oplus \text{input}[i] $$

Example: Parallel prefix sum (Blelloch algorithm).

• Fusion (Loop Fusion): Combine multiple map/scan operations into one pass to reduce memory traffic and intermediate storage.

  Example: Fusing map(f) and map(g) into map(h) where $$\displaystyle h(x) = g(f(x)) $$.

[!TIP] Fusing Map and Scan optimizes by eliminating intermediate arrays—critical for memory-bound parallel codes.