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

UNIT 1: FUNDAMENTALS OF PARALLEL COMPUTING

I. INTRODUCTION & FUNDAMENTAL CONCEPTS

Core Distinctions & Terminology

• Parallelism vs. Pipelining:

  • Parallelism: Multiple tasks or data elements processed simultaneously by different resources.

  • Pipelining: A single task is broken into sequential stages; different stages of different tasks overlap in time. It is a form of temporal parallelism.

• Serial vs. Parallel Processing:

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

  • Parallel: Multiple instructions execute concurrently on multiple processors.

• Control Flow vs. Data Flow Computers:

  • Control Flow: Execution sequence determined by a program counter (von Neumann model). Instructions are fetched and executed based on control flow.

  • Data Flow: Execution triggered by availability of data. Instructions fire when their input operands are ready. No program counter.

• Uniprocessor vs. Multiprocessor Systems:

  • Uniprocessor: Single CPU, may use pipelining/instruction-level parallelism internally.

  • Multiprocessor: Multiple independent CPUs working together, requiring coordination (communication, synchronization, memory coherence).

Categories & Classifications of Parallelism

• Four Categories:

  1. Bit-level Parallelism: Parallelism within a word (e.g., 64-bit operations vs 32-bit).

  2. Instruction-level Parallelism (ILP): Multiple instructions executed in parallel within a single processor (pipelining, superscalar, VLIW).

  3. Data Parallelism: Same operation applied to multiple data elements simultaneously (SIMD, GPUs).

  4. Task Parallelism: Different tasks (threads/processes) execute concurrently (MIMD).

• Flynn's Taxonomy:

  | Taxonomy | Instruction Stream | Data Stream | Example | | :--- | :--- | :--- | :--- | | SISD | Single | Single | Traditional uniprocessor | | SIMD | Single | Multiple | Vector processors, GPUs (SIMT) | | MISD | Multiple | Single | Rare (e.g., some fault-tolerant systems) | | MIMD | Multiple | Multiple | Most multiprocessors, clusters, multicores |

MIMD Multiprocessors

• Key Characteristics (distinguishing from networked computers):

  1. Shared Physical Memory (in shared-memory variants) or fast, low-latency interconnect.

  2. Tight Coupling: Processors are integrated, often sharing a clock or memory bus.

  3. Coherent Memory Access: A single shared address space is maintained (requires cache coherence).

  4. Fine-grained Communication: Communication via shared memory is fast and frequent.

  5. Single Operating System Image: Often run a single OS instance across all processors (in SMP).

Pipelining Fundamentals

• k-stage Linear Pipeline Model: An instruction passes through k sequential stages (Fetch, Decode, Execute, etc.). Each stage takes one clock cycle.

• Theoretical Speedup Limit:

  • Ideal Case: Without any stalls, the pipeline achieves a throughput of one instruction per cycle after the first instruction fills the pipeline.

  • Speedup: $$\displaystyle S_{ideal}(k) = \frac{T_{serial}(k)}{T_{pipeline}(k)} = \frac{k \cdot t_{stage}}{(k + n - 1) \cdot t_{stage}} $$ for n instructions.

  • As n → ∞, $$\displaystyle S_{ideal}(k) \to k $$.

  • Proof of Limit: The maximum possible speedup is k because the pipeline's throughput is limited by its slowest stage. Even with perfect balancing, the clock period must be at least the delay of the slowest stage. Thus, the pipeline cannot be faster than k times a non-pipelined processor where each stage takes its actual time.

  \boxed{S_{max} \leq k}

• Pipeline Hazards & Limitations:

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

  • Data Hazards: Dependencies (RAW, WAR, WAW).

  • Control Hazards: Branches and jumps causing misprediction.

  • These hazards cause pipeline stalls, reducing actual speedup below k.

II. MEMORY SYSTEMS & CACHE COHERENCE

Cache Memory in Parallel Systems

• Disadvantages of Caches using Virtual Addresses:

  1. Synonym Problem: Different virtual addresses map to the same physical address. Caches may store multiple inconsistent copies.

  2. Homonym Problem: Same virtual address on different processors maps to different physical addresses (if address spaces not identical). Coherence protocols fail.

  3. TLB Shootdowns: When a page table entry changes, all processors' TLBs must be invalidated—expensive in multiprocessors.

  \boxed{\text{Virtual caches complicate coherence; physical caches are preferred in multiprocessors.}}

• Centralized vs. Distributed Shared Caches:

  | Feature | Centralized Shared Cache | Distributed Shared Cache | | :--- | :--- | :--- | | Location | Single cache (often L3) shared by all cores | Cache distributed (typically L2/L3) with each core or group | | Access Latency | Higher for remote cores (contention) | Lower for local cores, higher for remote | | Bandwidth | Limited by single cache port | Higher aggregate bandwidth | | Scalability | Poor (bottleneck) | Better, but coherence traffic increases | | Complexity | Simpler coherence (snooping on single bus) | More complex (directory or snooping across network) |

The Cache Coherence Problem

• Definition: Ensuring that multiple cached copies of the same memory block remain consistent when one cache modifies its copy.

• Causes: Write-back caches + shared data + multiple caches.

• Two Fundamental Policies:

  1. Write-Through with Invalidate: Write updates main memory and invalidates other caches' copies.

  2. Write-Back with Update (Write-Broadcast): Write updates main memory and broadcasts the new value to all other caches.

Snooping-Based Cache Coherence Protocols (Bus-based systems)

• Mechanism: All caches monitor (snoop) a shared broadcast medium (bus). On a write, the writer snoops to invalidate/update others.

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

  • Writer sends invalidate on bus.

  • Other caches snoop and invalidate their copy.

  • Future reads from those caches must fetch from memory/writer.

  • Advantage: Less bus traffic for writes after first invalidation.

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

  • Writer sends new data value on bus.

  • All caches snoop and update their copy.

  • Advantage: Subsequent reads hit locally.

  • Disadvantage: High bus traffic for repeated writes to same location.

• Implementation: States (Modified, Exclusive, Shared, Invalid - MESI) track block status.

Directory-Based Cache Coherence Protocols (Scalable for distributed memory)

• Mechanism: A directory (centralized or distributed) tracks which caches have a copy of each block.

• Centralized Directory:

  • Single directory (in memory or dedicated hardware) stores for each block: a bitmap or list of sharers + owner (if exclusive).

  • Advantage: Simple, single source of truth.

  • Disadvantage: Single point of bottleneck/contention.

• Distributed Directory:

  • Directory information is partitioned and distributed (often with the memory module owning the block).

  • Advantage: Scalable, no central bottleneck.

  • Disadvantage: More complex lookups, higher latency for remote directories.

• Tracking States: Typically tracks: Uncached, Shared (list of caches), Exclusive/Modified (one owner). On a write, directory sends invalidates/updates only to listed caches.

Comparison: Snooping vs. Directory-Based

III. PARALLEL PROGRAMMING MODELS & METHODOLOGIES

Design of Parallel Programs

• Essential Steps:

  1. Problem Decomposition: Partition problem into concurrent tasks.

  2. Algorithm Selection/Design: Choose/design parallel algorithms for tasks.

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

  4. Synchronization & Communication: Identify points needing coordination.

  5. Implementation & Tuning: Code, debug, optimize (load balance, locality).

  6. Evaluation: Measure performance (speedup, efficiency).

• Decomposition Strategies:

  • Task Decomposition (Functional): Split by subtasks (e.g., pipeline stages).

  • Data Decomposition (Domain): Split data, same operation on each part (e.g., array blocks).

  • Hybrid: Combine both.

Distributed-Memory Programming: Message Passing Interface (MPI)

• Core Concepts:

  • Communicator: Group of processes that can communicate (MPI_COMM_WORLD).

  • Point-to-Point: MPI_Send, MPI_Recv (blocking); MPI_Isend, MPI_Irecv (non-blocking).

  • Collective: All processes in communicator participate (MPI_Bcast, MPI_Reduce, MPI_Scatter, MPI_Gather).

• Blocking vs Non-blocking:

  • Blocking: Call returns only after operation complete (safe, may cause deadlock if ordering wrong).

  • Non-blocking: Returns immediately; operation proceeds in background. Use MPI_Wait/MPI_Test to complete. Enables overlap of computation and communication.

• Process Topology & Virtual Topologies:

  • Create logical grid/torus with MPI_Cart_create. Allows use of nearest-neighbor communication (MPI_Cart_shift) and easier algorithm mapping (e.g., stencil codes).

Shared-Memory Programming & Threads

• Thread Management:

  • Creation: pthread_create (POSIX), std::thread (C++11).

  • Joining: pthread_join to wait for thread completion.

  • Synchronization Primitives:

    • Mutex (Lock): Mutual exclusion for critical sections.

    • Semaphore: Counting for resource pools or producer-consumer.

    • Barrier: All threads wait until last arrives (pthread_barrier).

• Threading Models:

  | Model | User Threads → Kernel Threads | Pros | Cons | | :--- | :--- | :--- | :--- | | Many-to-One | Many → One | Fast user-level switch | No true parallelism; one thread blocks all | | One-to-One | One → One | True parallelism; blocking isolated | Overhead on creation/switch | | Many-to-Many | Many → Many | Balance; can block some without halting all | Complex scheduling |

Parallel Data Management

• Data Partitioning & Distribution:

  | Strategy | Description | Best For | | :--- | :--- | :--- | | Block (Contiguous) | Consecutive elements to a processor | Regular access, spatial locality | | Cyclic (Round-robin) | Distribute elements in round-robin | Load balancing if uneven work per element | | Block-Cyclic | Blocks of size b distributed cyclically | Balance locality & load balance (e.g., ScaLAPACK) |

• Data Locality & Affinity: Keep data close to the processor that uses it (NUMA-aware allocation, thread-core affinity).

• Load Balancing: Minimize idle time. Static (known work) vs Dynamic (work-stealing, task queues).

Parallel I/O Handling

• Challenges: Contention at shared disks/controllers, consistency, non-atomic file operations, large file access patterns.

• Approaches:

  • Independent I/O: Each process opens/writes its own file. Simple, but many files.

  • Collective I/O: Processes cooperate (e.g., one process reads large chunk, then distributes). Reduces contention.

  • Two-Phase I/O: Aggregation phase (processes send data to designated aggregators), I/O phase (aggregators perform actual I/O). Optimizes for file system striping.

Parallel Algorithmic Patterns

• Map Operation (Embarrassingly Parallel):

  • Apply a function f independently to each element of a collection.

  • No communication between tasks. Perfect speedup possible if work balanced.

  • Example: Image processing (filter each pixel).

• Scan Operation (Prefix Sum):

  • Given binary operator ⊕ (e.g., +), compute all prefixes: $$\displaystyle [x_0, x_0⊕x_1, x_0⊕x_1⊕x_2, ...] $$.

  • Algorithms: Hillis-Steele (parallel inclusive scan, $O(\log n)$ time, $O(n \log n)$ work), Blelloch (exclusive scan, work-efficient).

• Fusing Map and Scan:

  • Combine operations to reduce passes over data.

  • Example: Map-Scan: Apply f then scan. Can be done in one pass with careful algorithm design (e.g., segmented scan).

IV. PERFORMANCE EVALUATION & METRICS

Key Performance Metrics

• Speedup: $$\displaystyle S(p) = \frac{T(1)}{T(p)} $$

  • $T(1)$: Execution time on 1 processor.

  • $T(p)$: Execution time on p processors.

  • Linear Speedup: $$\displaystyle S(p) = p $$ (ideal).

• Efficiency: $$\displaystyle E(p) = \frac{S(p)}{p} = \frac{T(1)}{p \cdot T(p)} $$

  • Measures fraction of time processors are usefully employed.

• Scalability:

  • Strong Scaling: Fixed total problem size. How does $T(p)$ decrease as p increases? Goal: $T(p) \propto 1/p$.

  • Weak Scaling: Fixed problem size per processor (total size ∝ p). Goal: $T(p)$ remains constant.

Performance Analysis & Bottlenecks

• Amdahl's Law (Fixed Problem Size):

  \boxed{S(p) \leq \frac{1}{(1 - P) + \frac{P}{p}}}

  • P = fraction of code that is parallel.

  • Limitation: Speedup bounded by sequential portion $(1-P)$. Even with infinite processors, $$\displaystyle S_{max} = \frac{1}{1-P} $$.

  • Bottleneck: Sequential part dominates at large p.

• Gustafson's Law (Scaled Problem Size):

  \boxed{S(p) = p - (1 - P)(p - 1)}

  • Assumes problem size scales with p (more data on more processors).

  • Key Insight: If P is large, speedup can be nearly linear. Justifies using many processors for larger problems.

• Parallel Overhead: Time spent on non-computational work:

  • Communication: Message passing latency/bandwidth costs.

  • Synchronization: Barrier waits, lock contention.

  • Load Imbalance: Some processors finish early and idle.

  • Extra Computation: Algorithmic overhead (e.g., in scan).

• Cost Metric: Total Cost = $p \cdot T(p)$.

  • A parallel algorithm is cost-optimal if its total cost is asymptotically the same as the best sequential algorithm for the problem.

V. ARCHITECTURAL TRENDS & ADVANCED TOPICS

Modern GPU Architecture

• Architectural Characteristics:

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

  • Many-Cores: Hundreds to thousands of smaller, efficient cores (vs few large CPU cores).

  • Memory Hierarchy:

    • Global Memory: Large, high-latency DRAM (all threads access).

    • Shared Memory: On-chip, low-latency, programmer-managed scratchpad (per thread block).

    • Local Memory: Private to each thread (often spills to global).

    • Registers: Fastest, per thread.

  • Hardware Multithreading: Warps hide memory latency by switching to ready warps (zero-overhead context switch).

• Programming Models:

  • CUDA (NVIDIA): C++ extensions, kernels, thread hierarchy (grid, block, thread).

  • OpenCL: Open standard, heterogeneous (CPU/GPU/FPGA).

• Key Application Domains:

  • High-Performance Computing (HPC): Scientific simulations (climate, fluid dynamics).

  • Artificial Intelligence / Machine Learning: Dense matrix/tensor operations (training/inference).

  • Computer Graphics: Rasterization, ray tracing.

  • Data Analytics: Large-scale data processing (sorting, searching).

Transactional Memory

• Transaction (DB) vs. Transactional Memory (TM):

  • Database Transaction: Atomic, Consistent, Isolated, Durable (ACID) operations on disk-based data.

  • Transactional Memory: Provides atomicity and isolation for in-memory read/write operations, simplifying lock-based synchronization.

• Basic Idea: Group a sequence of memory accesses into a transaction. Transaction either commits (all writes visible atomically) or aborts (no effect). Provides atomicity & isolation without explicit locks.

• Hardware vs. Software TM:

  • HTM (Hardware TM): Uses CPU cache coherence protocol extensions (e.g., Intel TSX). Fast, but limited by cache size/conflicts.

  • STM (Software TM): Implemented in compiler/runtime using locks/versioning. Flexible (unbounded transactions), but higher overhead.

  \boxed{\text{TM Goal: Replace locks with atomic, composable transactions for shared data.}}

Architectural Characteristics of Future Systems

• Trends:

  • Dark Silicon: Power density limits prevent all transistors from being active simultaneously. Requires specialized accelerators.

  • 3D Stacking: Vertically stack memory/logic dies (e.g., HBM). Reduces memory wall, increases bandwidth.

  • Near-Memory / In-Memory Computing: Place compute near or inside memory (e.g., processing-in-memory - PIM) to reduce data movement.

• Heterogeneous Integration: Systems combining CPUs + GPUs + Domain-Specific Accelerators (e.g., AI TPUs, FPGAs) on package/board.

• Major Challenges:

  • Power & Energy: Cooling and power delivery are primary constraints.

  • Memory Wall: CPU-memory speed gap persists; requires architectural innovations (3D, PIM).

  • Reliability: Soft errors increase with smaller nodes; need resilience at system level.

[!TIP] Exam Focus Areas:

• Cache Coherence: Be ready to compare Snooping vs Directory (pros/cons, scalability). Know MESI states.

• MPI: Distinguish blocking/non-blocking, point-to-point/collective. Know MPI_Bcast/MPI_Reduce usage.

• Performance Laws: Amdahl vs Gustafson is a classic comparison. Know formulas and assumptions.

• GPU: SIMT, warp divergence penalty, memory hierarchy (global vs shared) are key.

• Pipeline Speedup Proof: Argue that clock period ≥ slowest stage time ⇒ max speedup = k.

• Design Steps: Memorize the 6-step process (Decomposition → Evaluation).