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

UNIT 2: Parallel Computing

I. Fundamental Concepts and Classifications

A. Parallelism vs. Pipelining

Exam Tip: Parallelism = more workers; Pipelining = assembly line for one worker.

B. Serial vs. Parallel Processing

• Serial Processing:

  • Instructions executed one after another.

  • Single control unit manages execution sequence.

  • Model: SISD (Flynn's Taxonomy).

• Parallel Processing:

  • Multiple instructions executed concurrently.

  • Requires multiple ALUs/processors and coordination.

  • Models: SIMD, MISD, MIMD.

C. Control Flow vs. Data Flow Computers

D. Uniprocessor vs. Multiprocessor Systems

• Uniprocessor:

  • Single CPU; sequential execution.

  • Simple memory hierarchy (cache-main memory).

  • No coherence or synchronization issues.

• Multiprocessor:

  • Two or more CPUs sharing resources.

  • Memory organization critical (shared/distributed).

  • Faces cache coherence, synchronization, scalability challenges.

E. Categories of Parallelism (Flynn's Taxonomy)

Key: SIMD = same instruction on different data (data parallelism). MIMD = different instructions on different data (task/data parallelism).

II. Parallel Architectures

A. MIMD Multiprocessors

Distinguishing Characteristics from Networks/Clusters:

1. Tightly Coupled: Processors share physical memory (global address space).

2. Low Latency Communication: Via shared memory or fast interconnect (vs. network latency).

3. Single System Image: OS sees one system (vs. cluster's multiple nodes).

4. Uniform Memory Access (UMA) or NUMA: Memory access time may vary (NUMA) but is transparent to programmer.

Memory Organization:

• Shared Memory: All processors access single address space.

  • Centralized Shared: Single main memory (UMA).

  • Distributed Shared: Each node has local memory; global access via interconnect (NUMA).

• Interconnection Networks:

  • Bus: Simple, limited scalability (snooping coherence).

  • Crossbar: Non-blocking, expensive (O(n²) switches).

  • Multistage (e.g., Omega): Scalable, logarithmic hops.

  • Mesh/Torus: Used in massively parallel processors (MPP).

B. Pipelined Processors

Linear Pipeline Architecture (k-stage):

• Instruction execution divided into k sequential stages.

• Each stage works on different instruction simultaneously.

• Clock cycle per stage; throughput = 1 instruction/cycle (ideal).

Speedup Analysis:

Let:

• $$\displaystyle T_s $$ = Time for non-pipelined processor (k stages in series).

• $$\displaystyle T_p $$ = Time for pipelined processor.

• $$\displaystyle t_i $$ = Time for stage $i$; assume $$\displaystyle t_{max} = \max(t_1, ..., t_k) $$.

Without pipelining: $$\displaystyle T_s = \sum_{i=1}^{k} t_i $$

With pipelining (steady state): $$\displaystyle T_p = t_{max} $$ per instruction.

Maximum Speedup: $$\displaystyle S_{max} = \frac{T_s}{T_p} = \frac{\sum t_i}{t_{max}} \leq \frac{k \cdot t_{max}}{t_{max}} = k $$

\boxed{S_{max} \leq k}

Hazards:

• Structural: Resource conflict (two instructions need same unit).

• Data: Read-after-write (RAW), Write-after-read (WAR), Write-after-write (WAW).

• Control: Branch instructions cause pipeline flush.

Limitations: Imbalance in stage times, hazard penalties, non-ideal pipeline fill/drain.

C. GPU Architecture

Design Principles:

• SIMT (Single Instruction, Multiple Threads): Extension of SIMD; threads grouped in warps (e.g., 32 threads) execute same instruction on different data.

• Many-Core: Hundreds to thousands of scalar cores (e.g., NVIDIA CUDA cores).

• Throughput-Oriented: Optimized for high data-parallel workloads, not low-latency.

Memory Hierarchy:

1. Registers: Per-thread, fastest.

2. Shared Memory: On-chip, scratchpad for thread block (explicit management).

3. Global Memory: Off-chip DRAM, high latency, accessible by all threads.

4. Texture/Cache: Read-only, optimized for spatial locality.

Application Domains:

• Graphics: Rasterization, ray tracing.

• HPC: Scientific simulations (CFD, molecular dynamics).

• AI/ML: Matrix operations (DNN training/inference).

• Cryptocurrency: Hash computations.

D. Architectural Characteristics of Future Systems

Trends:

1. Heterogeneity: CPU + accelerators (GPU, FPGA, AI chips).

2. Memory-Centric Computing: Reduce data movement (processing-in-memory, HBM).

3. Energy Efficiency: Dark silicon limits; focus on performance-per-watt.

4. Chiplet Architecture: Modular dies connected via advanced packaging (e.g., AMD Infinity Fabric).

Challenges:

• Memory Wall: CPU speed >> memory speed; need cache hierarchies, prefetching.

• Communication Bottleneck: Interconnect bandwidth/latency limits scalability.

• Thermal/Power Limits: Dark silicon (inactive regions due to power density).

• Programming Complexity: Heterogeneous systems require complex programming models.

III. Memory Systems and Cache Coherence

A. Cache Design Considerations

Virtual vs. Physical Addressing:

• Virtual Cache: Tag uses virtual addresses.

  • Advantage: No TLB access on cache hit → faster.

  • Disadvantages:

    1. Aliasing Problem: Same physical line mapped to multiple virtual addresses → coherence issues.

    2. Synonym Problem: Different virtual addresses map to same physical line → inconsistent copies.

    3. Flush/Invalidate Complexity: On context switch, must flush entire cache or use address space identifiers (ASIDs).

• Physical Cache: Tag uses physical addresses.

  • Solves aliasing/synonym issues.

  • Requires TLB lookup before cache access (extra latency).

B. Shared Cache Architectures

C. The Multicache Coherence Problem

• Problem: Multiple caches hold copies of same memory block; writes by one processor must be propagated/observed by others to maintain single-writer/multiple-reader consistency.

• Protocol Strategies:

  • Invalidation: Write invalidates copies in other caches.

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

• Write Policy Impact:

  • Write-Through: Writes update cache and memory → easier coherence (memory always up-to-date).

  • Write-Back: Writes only to cache; memory updated on eviction → coherence harder; need dirty state tracking.

D. Snooping-Based Coherence Protocols

Bus-Based Snooping:

• All caches monitor (snoop) a shared bus for memory transactions.

• Write-Invalidate (e.g., MESI):

  • Write → invalidate other copies (transition to Exclusive/Modified).

  • Read → shared if others have copy.

• Write-Update (e.g., Firefly):

  • Write → broadcast new data to all caches (all stay Shared).

  • Less bus traffic for multiple readers, but more for single writer.

Scalability Limits:

• Bus Saturation: All snoop traffic on single bus → O(n) traffic, limits to ~16-32 cores.

• Broadcast Overhead: Invalidation/update messages to all caches.

E. Directory-Based Coherence Protocols

• Directory: Centralized or distributed data structure tracking which caches have a block.

• Centralized Directory: Single node maintains state for all blocks.

  • Scalability: Bottleneck at directory; memory overhead O(n) per block.

• Distributed Directory: Directory partitioned with memory (e.g., per memory module).

  • Scalability: Better; overhead distributed.

  • Complexity: Need message routing for coherence requests.

• Scalability: Suitable for large-scale (1000+ cores) where snooping fails.

IV. Parallel Programming Models and Languages

A. Distributed-Memory Programming with MPI

• Point-to-Point Communication:

  • Blocking: MPI_Send, MPI_Recv (wait for completion).

  • Non-blocking: MPI_Isend, MPI_Irecv (return immediately; later MPI_Wait).

• Collective Communication:

  • MPI_Bcast (broadcast), MPI_Reduce (sum/max), MPI_Allreduce, MPI_Scatter/Gather.

• Process Topology: MPI_Cart_create for virtual grid/process mapping.

• Virtual Processes: MPI_Comm_split to create subgroups.

B. Thread Management

• Thread Creation: pthread_create, OpenMP #pragma omp parallel.

• Synchronization:

  • Locks/Mutexes: Protect critical sections (pthread_mutex_lock).

  • Barriers: pthread_barrier_wait, #pragma omp barrier.

  • Condition Variables: For complex coordination.

• Thread Pools: Pre-created threads wait for tasks (reduce creation overhead).

• Work-Sharing (OpenMP): for, sections, single directives.

C. I/O Handling in Parallel Languages

• Challenges:

  • Contention: Many processes writing to same file system.

  • Consistency: Ensuring correct ordering/visibility.

• Models:

  • Independent I/O: Each process opens/writes own file → easy but poor aggregation.

  • Collective I/O (MPI-IO): MPI_File_write_all; two-phase I/O:

    1. Synchronization/Data Sieving: Processes aggregate requests.

    2. Single Writer: One process (or I/O node) performs actual disk I/O.

  • POSIX I/O with File Locking: Less scalable.

D. Parallel Data Management

• Data Distribution Strategies:

  • Block (Contiguous): Process $i$ gets elements $$\displaystyle [i \cdot \frac{n}{p}, (i+1) \cdot \frac{n}{p}) $$.

  • Cyclic: Process $i$ gets elements $i, i+p, i+2p, ...$ (good for load balance if uneven).

  • Block-Cyclic: Blocks of size $b$ distributed cyclically (common in ScaLAPACK).

• Load Balancing: Distribute work evenly; cyclic helps with irregular workloads.

• Data Locality: Place data on processor that uses it most (minimize communication).

E. Parallel Operations: Map, Scan, and Fusion

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

  
  // Parallel: for all i, B[i] = f(A[i])
  
  

• Scan (Prefix Sum): Compute all prefix sums: $$\displaystyle Y[i] = \sum_{j=0}^{i} X[j] $$.

  • Inclusive/Exclusive variants.

  • Parallel algorithms: Hillis-Steele, Blelloch (work-efficient).

• Fusion: Combine map + scan (or multiple maps) into single pass to reduce memory traffic and synchronization.

  • Example: map(f) + map(g) → map(f∘g).

F. Transactional Memory (TM)

• Concepts:

  • Atomicity: Transaction executes completely or not at all.

  • Isolation: Intermediate state invisible to other threads.

  • Commit/Abort: On conflict, transaction aborts and retries.

• vs. Database Transactions:

  • Scope: TM = in-memory; DB = persistent storage.

  • Duration: TM transactions short-lived (avoid aborts); DB transactions long-lived.

  • Isolation Levels: TM typically strict serializability; DB has read-committed, repeatable-read.

• Implementations:

  • Hardware TM (HTM): CPU extensions (Intel TSX, IBM Power).

  • Software TM (STM): Library-based; adds read/write logs.

  • Hybrid: HTM for small transactions, fallback to STM.

V. Performance and Program Design

A. Performance Metrics

• Speedup: $$\displaystyle S(p) = \frac{T_1}{T_p} $$ where $$\displaystyle T_1 $$ = sequential time, $$\displaystyle T_p $$ = parallel time with $p$ processors.

• Efficiency: $$\displaystyle E(p) = \frac{S(p)}{p} $$ (fraction of time processors are useful).

• Scalability: How $S(p)$ grows with $p$; strong scaling (fixed problem size), weak scaling (problem size ∝ $p$).

• Amdahl's Law:

  Let $f$ = sequential fraction, $(1-f)$ = parallelizable.

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

\boxed{S_{max} \leq \frac{1}{f}} (as $p \to \infty$)

Limitation: Assumes fixed problem size; often unrealistic.

• Gustafson's Law:

  Assume problem size scales with $p$: $$\displaystyle T_1 = f \cdot T_p + (1-f) \cdot p \cdot T_p $$.

$$ S(p) = p - f(p-1) $$

Key: For weak scaling, speedup can be linear if $f$ small.

B. Steps to Design Parallel Programs

1. Decomposition:

   • Task Decomposition: Identify independent tasks.

   • Data Decomposition: Partition data (block, cyclic).

   • Pipeline Decomposition: Stages process different data items.

2. Mapping: Assign tasks/data to processors (consider locality, load balance).

3. Orchestration:

   • Synchronization: Locks, barriers, fences.

   • Communication: Message passing (MPI), shared memory (threads).

4. Evaluation & Tuning:

   • Measure speedup, efficiency.

   • Identify bottlenecks (load imbalance, communication, synchronization).

   • Optimize: reduce communication, increase granularity, improve locality.

C. Transactional Memory Applications

• Concurrent Data Structures: Linked lists, hash tables, skip lists.

• Advantages over Locks:

  • Composition: Transactions compose; locks don't (lock ordering).

  • Deadlock-Free: No circular wait (abort instead of wait).

  • Simpler Code: No explicit lock management.

• Use Case: Fine-grained updates to shared structures where lock overhead high.

VI. Advanced Topics (Integrated)

A. Transactional Memory vs. Traditional Transactions

B. Future System Architectural Challenges

1. Memory Wall: CPU-Memory speed gap → cache hierarchies, prefetching, near-memory computing.

2. Power Constraints: Dark silicon (inactive regions); need heterogeneous and approximate computing.

3. Accelerator Integration: GPUs, FPGAs, AI chips → heterogeneous programming (CUDA, OpenCL, SYCL).

4. Communication Bottleneck: Interconnect bandwidth/latency → network-on-chip (NoC), 3D stacking.

5. Resilience: Soft errors in large systems → algorithmic resilience, checkpointing.

Exam Focus: Be prepared to prove pipeline speedup, compare coherence protocols, apply Amdahl/Gustafson, and contrast TM with DB transactions. Always link architecture to programming models (e.g., NUMA → data distribution in MPI).