UNIT 4: Parallel Computing

I. Fundamental Distinctions and Terminologies

A. Parallelism vs. Pipelining

[!TIP] Exam Focus: Parallelism uses multiple resources; pipelining uses one resource more efficiently.

B. Serial Processing vs. Parallel Processing

C. Control Flow Computers vs. Data Flow Computers

D. Uniprocessor Systems vs. Multiprocessor Systems

II. Parallel Architectures and Performance Analysis

A. MIMD Multiprocessors: Characteristics vs. Multiple Computer Systems/Networks

MIMD (Multiple Instruction, Multiple Data): Each processor executes independent instruction streams on independent data.

B. Pipeline Performance: Speedup Proof for k-Stage Linear Pipeline

Ideal Speedup (S): Maximum possible speedup = number of stages (k). Proof:

1. Non-pipelined (Serial) Execution Time for n tasks:

$$ T_s = n \times t_{task} $$

where $$\displaystyle t_{task} $$ is time to complete one task.

2. Pipelined Execution Time:

   • First task completes at $k \times \tau$ (where $\tau$ is clock cycle time per stage).

   • Subsequent tasks complete every $\tau$ cycles after the first.

   • Total time:

$$ T_p = k\tau + (n-1)\tau = (k + n - 1)\tau $$

3. Assume ideal case: $$\displaystyle t_{task} = k\tau $$ (each stage takes 1 cycle).

   Then:

$$ T_s = n \times k\tau $$

4. Speedup (S):

$$ S = \frac{T_s}{T_p} = \frac{n k \tau}{(k + n - 1)\tau} = \frac{nk}{k + n - 1} $$

5. As n → ∞ (large number of tasks):

$$ \lim_{n \to \infty} S = \frac{nk}{n} = k $$

**Hence, maximum speedup = k.**

[!CAUTION] Real-World Limitation: Actual speedup < k due to pipeline hazards (structural, data, control), imbalance in stage delays ($$\displaystyle \tau = \max(\tau_i) $$), and startup/drain overhead.

C. GPU Architecture and Applications

Architecture:

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

• Massively Parallel: Hundreds to thousands of small, efficient cores (Streaming Multiprocessors - SMs).

• Memory Hierarchy: High-bandwidth GDDR memory, shared memory per SM, registers per thread.

• Specialized Units: Texture units, tensor cores (for AI), RT cores (ray tracing).

Key Applications:

1. Graphics Rendering: Pixel/vertex shading.

2. Scientific Computing: Matrix operations, simulations (CFD, molecular dynamics).

3. Machine Learning/AI: Training & inference (CNNs, Transformers).

4. Cryptocurrency Mining: Hash computations.

5. Video Encoding/Decoding.

III. Memory Systems and Cache Coherence

A. Caches Using Virtual Addresses: Disadvantages

1. Synonym Problem: Different virtual addresses map to same physical address → multiple cache copies possible → coherence violation.

2. Homonym Problem: Same virtual address in different processes maps to different physical addresses → requires Address Space Identifier (ASID) tagging.

3. TLB Thrashing: Frequent TLB misses due to large working set of virtual pages.

4. Complex Coherence: Hardware must handle virtual-to-physical translation for coherence protocols.

[!TIP] Solution: Physically Indexed, Physically Tagged (PIPT) caches avoid synonym/homonym but add translation latency. Virtually Indexed, Physically Tagged (VIPT) is common compromise.

B. Shared Cache Organizations

C. Cache Coherence Protocols: Snooping-based vs. Directory-based

D. Multicache Coherence Problem and Solution Methods

Problem: In a system with multiple caches, a memory location cached in more than one cache may become inconsistent if one cache modifies it without others knowing.

Solution Methods:

1. Snooping Protocols (Bus-Based):

   • Write-Invalidate: Writer invalidates all other copies.

   • Write-Update (Write-Broadcast): Writer updates all other copies.

   • States: Modified (M), Exclusive (E), Shared (S), Invalid (I) - MESI protocol.

2. Directory-Based Protocols (Scalable):

   • Central/ distributed directory tracks state (Uncached, Shared, Modified) and list of sharers.

   • On read/write, consult directory to grant permission or invalidate/update.

3. Timestamp Ordering:

   • Assign timestamps to cache line accesses.

   • Enforce global order to detect inconsistencies.

IV. Parallel Programming Models and Design Methodology

A. Categories of Parallelism (Flynn's Taxonomy)

B. Steps to Design Parallel Programs

1. Problem Decomposition: Partition problem into concurrent tasks (data decomposition, functional decomposition).

2. Algorithm Selection: Choose appropriate parallel algorithm (e.g., divide-and-conquer, pipelining).

3. Mapping: Assign tasks to processes/threads/processors.

4. Scheduling & Load Balancing: Distribute work evenly, minimize idle time.

5. Synchronization & Communication: Identify points needing coordination (barriers, locks, messages).

6. Implementation: Choose programming model (MPI, OpenMP, CUDA).

7. Evaluation & Tuning: Measure performance (speedup, efficiency), identify bottlenecks (contention, imbalance), optimize.

C. Distributed-Memory Programming with MPI

MPI (Message Passing Interface): Standard for distributed-memory systems.

• Core Concept: Processes have private address spaces; communicate by explicit send() and receive().

• Key Routines:

  • MPI_Init(), MPI_Finalize(): Start/end.

  • MPI_Comm_size(), MPI_Comm_rank(): Get number of processes & ID.

  • Point-to-point: MPI_Send(), MPI_Recv().

  • Collective: MPI_Bcast(), MPI_Reduce(), MPI_Scatter(), MPI_Gather().

• Blocking vs. Non-blocking: MPI_Send/MPI_Recv (wait), MPI_Isend/MPI_Irecv (return immediately, use MPI_Wait).

• Topologies: Virtual process mappings (MPI_Cart_create).

D. I/O Handling in Parallel Programming Languages

Challenge: Multiple processes/threads accessing shared filesystems can cause contention, race conditions, and poor performance. Solutions:

1. Independent I/O: Each process opens/writes to its own file (simple, no coordination).

2. Shared File with Offsets: Use MPI_File_write_at to write at specific offsets.

3. Collective I/O: Processes cooperate to read/write a shared file efficiently (e.g., MPI_File_read_all). System can optimize (data sieving, two-phase I/O).

4. Parallel I/O Libraries: ROMIO (for MPI-IO), HDF5, NetCDF provide high-level, portable interfaces for structured data.

E. Thread Management

Thread: Lightweight unit of execution within a process (shares address space).

• Creation/Joining: pthread_create(), pthread_join() (POSIX); std::thread (C++11).

• Synchronization Primitives:

  • Mutex/Lock: pthread_mutex_lock() for mutual exclusion.

  • Condition Variable: pthread_cond_wait()/signal() for event-based sync.

  • Semaphore: Counting semaphore (sem_wait/post).

  • Barrier: pthread_barrier_wait() for phase synchronization.

• Thread Pools: Create fixed number of worker threads; assign tasks from queue (reduces creation overhead).

F. Parallel Data Management

Goal: Efficiently distribute, replicate, and maintain consistency of data across processing elements.

• Data Distribution: Block, cyclic, block-cyclic distribution for arrays.

• Replication: Read-only data can be replicated to all nodes (reduces communication).

• Consistency Models: Define rules for when a write becomes visible to others.

  • Strict Consistency: Immediate visibility (impractical).

  • Sequential Consistency: All processes see same order of operations.

  • Weak/Relaxed Consistency: Allows reordering; requires explicit synchronization to enforce order.

• Distributed Shared Memory (DSM): Software layer provides shared-memory abstraction on distributed-memory hardware (pages migrate/replicate).

G. Fusing Map and Scan Operations

• Map: Apply function f to each element of a collection independently. Output size = input size.

$$ \text{map}(f, [x_1, x_2, ..., x_n]) = [f(x_1), f(x_2), ..., f(x_n)] $$

• Scan (Prefix Sum): Compute all intermediate results of an associative operator ⊕.

$$ \text{scan}(\oplus, [x_1, x_2, x_3]) = [x_1, x_1 \oplus x_2, x_1 \oplus x_2 \oplus x_3] $$

• Fusing: Combine map and scan into a single pass to avoid intermediate array storage and extra traversal.

  • Example: Compute prefix sums of squares: scan(+, map(square, array)).

  • Benefit: Reduces memory traffic (O(n) reads/writes → O(1) per element), crucial for GPU/out-of-core.

V. Performance Evaluation

A. Performance Metrics for Parallel Systems

1. Speedup (S): Ratio of serial execution time to parallel time.

$$ S(p) = \frac{T_s}{T_p} $$

where `p` = number of processors.

2. Efficiency (E): How well processors are utilized.

$$ E(p) = \frac{S(p)}{p} = \frac{T_s}{p \cdot T_p} $$

Ideal: `E=1` (linear speedup). Real: `E < 1`.

3. Scalability: Ability to maintain efficiency as p increases. Isoefficiency: Function f(p) such that problem size W must grow to keep E constant.

4. Cost-Effectiveness: $$\displaystyle \text{Cost} = p \times T_p $$. Optimal solution minimizes cost for given problem.

5. Amdahl's Law: Max speedup limited by sequential fraction f.

$$ S_{max}(p) = \frac{1}{f + \frac{1-f}{p}} $$

6. Gustafson's Law: Speedup scales with problem size (assumes fixed time).

$$ S(p) = p - \alpha (p-1) $$

where α is non-parallelizable fraction of scaled problem.

VI. Advanced and Emerging Topics

A. Architectural Characteristics of Future Systems

1. Many-Core & Heterogeneous: Thousands of simple cores + specialized accelerators (GPUs, TPUs, FPGAs).

2. Memory-Centric/Processing-in-Memory (PIM): Compute near memory to overcome memory wall (bandwidth/energy bottleneck).

3. Chiplet-Based Design: Multiple smaller dies (chiplets) interconnected via high-density links (e.g., EMIB, UCIe) for better yield, cost, and integration.

4. Silicon Photonics Interconnects: Optical I/O for higher bandwidth, lower power, longer reach.

5. Approximate/Probabilistic Computing: Trade precision for energy/performance in error-tolerant applications (ML, signal processing).

6. Quantum-Classical Hybrid: Classical systems as controllers for quantum processors.

B. Transaction vs. Transactional Memory

[!TIP] Key Idea: Transactional Memory provides atomicity & isolation for memory operations, but not full ACID. Abort on conflict → retry.