Parallel & Distributed Computing Overview

Parallel Computing

  • Definition: Simultaneous use of multiple resources to solve computational problems by breaking tasks into discrete parts for concurrent execution.
  • Benefits:
    • Save time and money
    • Solve larger, complex problems
    • Provide concurrency
    • Maximize use of parallel hardware

Distributed Computing

  • Concept: Extends parallel computing by utilizing multiple independent computers connected via a network.
  • Characteristics: Focuses on loosely coupled, autonomous machines.
    • Client-Server Architecture: Clients request resources from centralized servers.
    • Peer-to-Peer Architecture: Nodes function as both clients and servers.
    • Cluster Computing: Connects multiple computers in one location for unified tasks.

Parallelism Types

  • Data Parallelism: Same operation on multiple data concurrently (e.g., image processing).
  • Task Parallelism: Different tasks executed simultaneously, which may be independent or dependent.

Flynn's Taxonomy

  • Classifies computer architectures based on instruction and data streams:
    • SISD: Single Instruction, Single Data
    • SIMD: Single Instruction, Multiple Data
    • MISD: Multiple Instruction, Single Data
    • MIMD: Multiple Instruction, Multiple Data

Performance Metrics

  • Amdahl's Law: Speedup determined by parallelizable portions of code (P).
  • Gustafson's Law: Emphasizes scalability with increasing problem sizes for multiple processors.
  • Scalability Types:
    • Strong Scaling: Fixed problem size, increased processors for speed.
    • Weak Scaling: Proportional problem size to processors.

Memory Architectures

  • Shared Memory: All processors access a common memory space.
    • SMP: Symmetric Multiprocessing
    • NUMA: Non-Uniform Memory Access, varying access times to different memory.
    • COMA: Cache-Only Memory Architecture, local memories act as caches.
  • Distributed Memory: Each processor has independent memory, requiring explicit communication.

Parallel Programming Models

  • Shared Memory: OpenMP, simplifies multi-core processor tasks.
  • Threads: CUDA, leverages GPU processing for massive parallelism.
  • Message Passing: MPI, communicates between distributed computers.

Fault Tolerance Strategies

  • Redundancy: Data replication across nodes for availability.
  • Error Detection: Heartbeat signals and periodic saving (checkpointing).
  • Recovery: Rollback to error-free states or forward recovery to continue operations.

Synchronization Techniques

  • Locking Mechanisms: Mutexes to prevent race conditions.
  • Barriers: Synchronize processes at a certain execution point.
  • Consensus Algorithms: Manage state consistency in distributed systems (e.g., Paxos).