💻Parallel and Distributed Computing Unit 1 – Intro to Parallel & Distributed Computing

Key Concepts & Terminology

• Parallel computing involves simultaneous execution of multiple tasks or instructions on different processors or cores to solve a problem faster
• Distributed computing involves coordinating tasks across a network of interconnected computers to achieve a common goal
• Concurrency refers to the ability of a system to execute multiple tasks or processes simultaneously, which may or may not be truly parallel
• Scalability measures how well a system can handle increased workload or accommodate growth in terms of resources or users
• Speedup quantifies the performance improvement gained by using parallel or distributed computing compared to sequential execution
• Efficiency indicates how well the available resources are utilized in a parallel or distributed system
• Load balancing ensures even distribution of workload across available resources to optimize performance and resource utilization
• Synchronization mechanisms (locks, semaphores, barriers) coordinate access to shared resources and maintain data consistency in parallel and distributed systems

Parallel vs. Distributed Computing

• Parallel computing focuses on leveraging multiple processors or cores within a single system to solve a problem faster
  • Typically involves shared memory architectures where processors can access a common memory space
  • Suitable for tightly coupled tasks that require frequent communication and synchronization
• Distributed computing involves coordinating tasks across a network of interconnected computers, often geographically dispersed
  • Relies on message passing for communication between nodes in the distributed system
  • Suitable for loosely coupled tasks that can be divided into independent subtasks with minimal communication
• Parallel computing aims to reduce execution time by dividing a task into smaller subtasks executed simultaneously
• Distributed computing aims to solve problems that are too large or complex for a single system by distributing the workload across multiple nodes
• Hybrid approaches combine parallel and distributed computing, leveraging parallelism within each node and distribution across nodes

Hardware Architectures

• Shared memory architectures provide a common memory space accessible by all processors, enabling efficient communication and data sharing
  • Symmetric multiprocessing (SMP) systems have multiple identical processors connected to a shared memory bus
  • Non-uniform memory access (NUMA) systems have processors with local memory and interconnects for accessing remote memory
• Distributed memory architectures have separate memory spaces for each processor, requiring explicit communication via message passing
  • Clusters are composed of interconnected standalone computers (nodes) that work together as a unified computing resource
  • Grid computing involves coordinating geographically distributed resources (computers, storage, instruments) to solve large-scale problems
• Accelerators (GPUs, FPGAs) offer high-performance computing capabilities for specific tasks, often used in conjunction with CPUs
• Interconnection networks (buses, crossbars, meshes, hypercubes) enable communication between processors or nodes in parallel and distributed systems
• Storage hierarchies (caches, main memory, disk) impact performance and require careful management in parallel and distributed environments

Programming Models & Paradigms

• Shared memory programming models (OpenMP, Pthreads) provide abstractions for parallel execution on shared memory systems
  • Programmers use directives, libraries, or language extensions to express parallelism and synchronization
  • Suitable for fine-grained parallelism and tightly coupled tasks
• Message passing programming models (MPI) enable communication and coordination between processes in distributed memory systems
  • Programmers explicitly define data partitioning, communication, and synchronization using message passing primitives
  • Suitable for coarse-grained parallelism and loosely coupled tasks
• Partitioned global address space (PGAS) models (UPC, Co-Array Fortran) provide a shared memory abstraction over distributed memory systems
• Task-based programming models (Cilk, Intel TBB) focus on decomposing a problem into tasks and managing their dependencies and execution
• Dataflow programming models (Apache Spark, TensorFlow) express computations as a graph of data dependencies, enabling automatic parallelization and distribution
• Functional programming paradigms (Erlang, Scala) emphasize immutability and side-effect-free functions, facilitating parallelism and distribution

Performance Metrics & Scalability

• Execution time measures the total time taken to complete a parallel or distributed computation
• Speedup ($S(n) = T(1) / T(n)$) quantifies the performance improvement achieved by using $n$ processors compared to sequential execution
  • Linear speedup ($S(n) = n$) is the ideal case where doubling the number of processors halves the execution time
  • Sublinear speedup ($S(n) < n$) occurs when the performance improvement is less than the number of processors added
• Efficiency ($E(n) = S(n) / n$) indicates how well the available resources are utilized in a parallel or distributed system
• Scalability refers to a system's ability to handle increased workload or accommodate growth in terms of resources or users
  • Strong scaling involves fixing the problem size and increasing the number of processors to reduce execution time
  • Weak scaling involves increasing both the problem size and the number of processors to maintain constant execution time per processor
• Amdahl's Law ($S(n) = 1 / (1 - P + P/n)$) provides an upper bound on the speedup achievable based on the parallel fraction ($P$) of the workload
• Gustafson's Law ($S(n) = n - (1 - P)(n - 1)$) considers the case where the problem size scales with the number of processors

Challenges & Limitations

• Communication overhead arises from the need to exchange data and synchronize between parallel or distributed processes
  • Latency is the time delay in sending a message between processes or nodes
  • Bandwidth is the rate at which data can be transferred between processes or nodes
• Load imbalance occurs when the workload is not evenly distributed among available resources, leading to underutilization and performance degradation
• Synchronization overhead results from the need to coordinate access to shared resources and maintain data consistency
  • Locks, semaphores, and barriers are synchronization primitives that can introduce overhead and potential bottlenecks
• Fault tolerance and resilience become critical in large-scale parallel and distributed systems, as the likelihood of failures increases with scale
  • Checkpoint/restart mechanisms enable recovery from failures by periodically saving the system state and resuming from the last checkpoint
  • Replication and redundancy techniques introduce additional overhead but improve fault tolerance
• Debugging and testing parallel and distributed programs are more complex due to concurrency, nondeterminism, and the potential for race conditions
• Scalability limitations arise from factors such as Amdahl's Law, communication overhead, and resource contention, restricting the achievable speedup and efficiency

Real-World Applications

• Scientific simulations (climate modeling, molecular dynamics) leverage parallel and distributed computing to solve complex mathematical models
• Big data processing and analytics (Hadoop, Spark) use distributed computing to process and derive insights from massive datasets
• Machine learning and deep learning (TensorFlow, PyTorch) employ parallel and distributed techniques to train large-scale models on extensive datasets
• Cryptocurrency mining relies on distributed computing to solve complex mathematical problems and validate transactions on blockchain networks
• Rendering and animation in the entertainment industry (Pixar, DreamWorks) utilize parallel computing to generate high-quality visual effects and animations
• Financial modeling and risk analysis in the banking and finance sector leverage parallel computing for real-time decision-making and risk assessment
• Drug discovery and genomics research in the pharmaceutical industry use parallel and distributed computing for large-scale data analysis and simulations
• Internet of Things (IoT) and edge computing rely on distributed computing to process and analyze data from numerous connected devices

Future Trends & Developments

• Exascale computing aims to develop systems capable of performing at least one exaFLOPS ($10^{18}$ floating-point operations per second)
  • Requires advancements in hardware, software, and algorithms to overcome power, memory, and resilience challenges
• Quantum computing leverages quantum mechanical phenomena (superposition, entanglement) to solve certain problems exponentially faster than classical computers
  • Potential applications in cryptography, optimization, and simulation of quantum systems
• Neuromorphic computing draws inspiration from the human brain to develop energy-efficient and fault-tolerant computing systems
  • Aims to bridge the gap between the capabilities of biological neural networks and artificial neural networks
• Edge computing pushes computation and data storage closer to the sources of data (IoT devices, sensors) to reduce latency and bandwidth requirements
  • Enables real-time processing, improved privacy, and reduced dependence on cloud infrastructure
• Serverless computing abstracts away the underlying infrastructure, allowing developers to focus on writing and deploying code without managing servers
  • Provides automatic scaling, high availability, and cost efficiency for event-driven and microservices architectures
• Convergence of HPC, big data, and AI leads to the development of integrated systems and frameworks that combine the strengths of each domain
  • Enables data-driven scientific discovery, intelligent automation, and personalized services across various industries