Introduction to Parallel and Distributed Computing Lecture Notes
Course Overview and Learning Objectives
Course Information: Parallel and Distributed Computing (Subject Code: 23CST-401/23ITT-401).
Prepared By: Er. Priyanka (E16550), Master of Subject Coordinator, Unit 1.
Course Outcomes (CO):
CO 1 (BT2): Compare and differentiate various models and architectures of parallel and distributed computing.
CO 2 (BT2): Explain processor architectures and interconnection networks used in high-performance computing (HPC) systems.
CO 3 (BT3): Evaluate system performance using parallel computing metrics and scalability laws.
CO 4 (BT2): Explain synchronization, communication, and coordination techniques used in distributed systems.
CO 5 (BT4): Apply parallel and distributed computing concepts to real-world applications and case studies.
Learning Outcomes (Chandigarh University):
Explain the evolution, significance, and need for parallel computing in modern computing environments.
Describe the role of parallel computing in Artificial Intelligence (AI) and Machine Learning (ML) applications.
Analyse the use of parallel computing techniques in cloud computing and distributed platforms.
Evaluate the contribution of parallel computing to big data analytics and large-scale data processing.
Identify the importance of parallel computing in scientific simulations and high-performance computing systems.
Fundamental Concepts of Computing
Computing Definition: Computing is the process of using computer hardware and software to process data, solve problems, and manage information. It transforms raw data inputs into meaningful outputs through the execution of algorithmic instructions.
Core Characteristics of Computing:
Speed: Executes millions of complex algorithmic calculations per second.
Accuracy: Delivers error-free results when provided with correct data and instructions.
Storage: Holds vast amounts of data that can be retrieved instantly.
Automation: Performs repetitive tasks without human intervention once programmed.
Diligence: Works continuously without suffering from fatigue, boredom, or loss of focus.
Versatility: Switches easily between different tasks, ranging from playing video games to predicting weather.
Connectivity: Shares data across local networks and the global internet seamlessly.
Serial Computing vs. Parallel Computing
Serial Computing:
Definition: A computing model where a problem is divided into a sequence of instructions, and these instructions are executed sequentially by a single CPU.
Execution Model: Only one instruction is processed at any given time.
Characteristics:
One instruction executed at a time.
Single processor handles all work.
Slow for large-scale tasks.
Limited scalability.
Lower overall efficiency.
High latency for complex problems.
Data Dependencies: Essential for algorithms where step B relies completely on the outcome of step A.
Resource Load: Heavy strain on a single processor core, which can generate quick heat spikes at peak loads.
Parallel Computing:
Definition: An advanced computational technique in which multiple processors or cores execute different parts of a problem simultaneously. The workload is divided into smaller sub-tasks and processed concurrently to reduce execution time and improve system performance.
Four-Step Process (DDEC):
Divide: The problem is split into independent sub-tasks that can be processed in isolation.
Distribute: Sub-tasks are assigned to multiple processors or cores simultaneously.
Execute: All processors work on their assigned tasks at the same time.
Combine: Results from all processors are merged into a single final output.
Hardware Utilization: Maximizes modern multi-core architectures like AMD Ryzen or Intel Core processors.
Bottlenecks: Can suffer from communication overhead and synchronization delays if threads must wait for each other.
Key Types:
Data Parallelism: The same instruction is applied to different data blocks.
Task Parallelism: Different functions/tasks are running at once.
Evolution of Parallel Computing
1930s–1950s: Early Computing:
Alan Turing's Turing Machine (1936) and Von Neumann Architecture established stored-program computing.
Instructions were executed sequentially, which was slow and unsuitable for large scientific problems.
1950s–1960s: Parallel Beginnings:
Vector processors and multiprocessing systems emerged.
Architectures were developed for simultaneous data execution for complex engineering applications.
1970s–1990s: Supercomputing Era:
Introduction of SIMD (Single Instruction, Multiple Data) and MIMD (Multiple Instruction, Multiple Data) architectures.
Theoretical formalization: Leslie Lamport's Sequential Consistency Model (1978) and Valiant's BSP (Bulk Synchronous Parallel) Model (1990).
2000s: Multi-Core Revolution:
The end of Dennard Scaling forced manufacturers to integrate multiple cores per chip.
Parallel computing became standard in consumer electronics (laptops, smartphones).
2010–Present: GPU & AI Era:
Modern GPUs containing thousands of smaller cores for massive parallel operations.
GPUs power AI systems, cloud infrastructures, and the world's fastest supercomputers.
The Essentiality of Parallel Computing
Modern applications require extremely fast processing and handling of massive datasets across eight critical dimensions:
Faster Execution: Dividing large problems for simultaneous execution reduces time for computationally intensive tasks.
Massive Data Handling: Processes and analytics for huge data volumes generated every second.
AI & Machine Learning: Enormous computational power is needed to accelerate model training and logic inference.
Real-Time Applications: Essential for autonomous vehicles, online gaming, and medical imaging requiring immediate responses.
Scientific Simulations: Handles highly complex mathematical computations for weather forecasting and research.
Scalability: Systems scale easily by adding processors or nodes to improve performance and resource utilization.
Advantages and Limitations of Parallel Computing
Advantages:
Faster execution speed (tasks completed in a fraction of the time).
Efficient handling of large datasets (ideal for big data).
Better multitasking (multiple workloads run concurrently).
High scalability (increase capacity by adding processors).
Energy efficiency (multi-core designs reduce power per operation).
Limitations:
Complex programming and debugging (concurrent code is harder to write and test).
Synchronisation issues (coordinating processors introduces complexity).
Communication overhead (data exchange between processors consumes resources).
Expensive hardware infrastructure (multi-processor systems cost more).
Difficult load balancing (uneven work distribution reduces efficiency).
Distributed Computing
Definition: A model in which components of a software system are shared among multiple computers or nodes, spread across multiple locations, but run as one system to improve performance.
Mechanism: Systems on different networked computers communicate and coordinate by sending messages back and forth to achieve a defined task.
Common Functions:
Task distribution: A central algorithm divides a large task into smaller subtasks for assignment to nodes.
Parallel execution: Nodes independently execute assigned subtasks concurrently, enabling faster computation.
Communication: Nodes share resources and coordinate tasks through various network protocols.
Aggregation of results: Results are sent back to a central node or aggregator to produce the final output.
Fault tolerance: Designed to handle failures gracefully through redundancy, replication, and mechanisms for detecting/recovering from node failures.
Parallel vs. Distributed Computing Comparison
Memory:
Parallel: Shared memory among processors.
Distributed: Independent memory systems.
Communication:
Parallel: Processors communicate directly via shared memory.
Distributed: Communication occurs through a network.
Synchronization:
Parallel: High synchronization between tasks.
Distributed: Limited synchronization; often asynchronous.
Fault Tolerance:
Parallel: Typically less fault-tolerant.
Distributed: Designed for high fault tolerance and redundancy.
Examples:
Parallel: Multi-core processors, GPUs.
Distributed: Distributed databases, cloud platforms.
Real-World Applications in AI and Specialized Fields
Weather & Climate: Processing atmospheric datasets across regions for forecasting, hurricane tracking, and disaster management.
Robotics & Automation: Processing multiple sensor inputs simultaneously for path planning and object recognition.
Recommendation Systems: User interaction processing in parallel (Netflix, Amazon, YouTube).
NLP & Voice AI: Accelerating tokenization and speech recognition across massive text datasets.
Big Data Analytics: Processing petabytes of IoT and social media data across distributed clusters.
Cybersecurity: Real-time malware detection through simultaneous log analysis.
LLMs & Generative AI: Using data and tensor parallelism to train trillion-parameter models across thousands of GPUs.
Autonomous Vehicles: Real-time processing of camera, LiDAR, and radar streams.
Healthcare: Analysis of MRI/CT slices concurrently for diagnosis and drug discovery.
Finance: Parallel analysis of transactions for fraud detection and algorithmic trading.
Cloud-Based Parallel Computing
Definition: A model where multiple processors, VMs, or servers in a cloud environment work simultaneously using cloud infrastructure (virtual machines, containers, clusters).
Four-Step Parallel Data Flow:
Ingestion and Partitioning: Master node divides massive datasets into smaller uniform blocks.
Distribution: Data blocks are distributed across worker nodes and replicated for fault tolerance.
Parallel Processing: Each worker node processes data independently with minimal communication to improve throughput.
Aggregation: Intermediate results are sent to the master node and combined into a final output.
Case Examples:
Big Data: Hadoop and Spark splitting data across cloud nodes.
DevOps (CI/CD): Running hundreds of tests in isolated containers simultaneously.
Media Rendering: Cloud render farms processing animation frames concurrently.
Distributed Databases: Sharding database rows across servers for concurrent queries.
Parallel Computing in Big Data Analytics
Big Data Definition: Extremely large, diverse, complex datasets generated at high velocity (Social Media, IoT, Healthcare, Online Transactions, Scientific Applications).
Hadoop & MapReduce:
Hadoop: A framework for distributed storage and parallel processing.
MapReduce programming model:
Map Phase: Divides input into parts processed independently.
Reduce Phase: Combines results into a final output.
Advantages in Big Data: High throughput across multi-core clusters, scalability via commodity servers, and lower operational costs per gigabyte.
High-Performance Computing (HPC) and Scientific Simulations
Scientific Simulations: Using mathematical models to represent real-world phenomena (climate, biology, engineering). Parallel computing enables accuracy, reduces costs, and saves time by dividing large problems into concurrent tasks.
HPC components:
Compute Nodes: Servers with powerful CPUs/GPUs linked together.
High-Speed Interconnects: Networks for seamless data exchange between nodes.
Workload Manager: Software that queues and allocates jobs.
HPC Workflow:
Cluster Configuration: Nodes connected via high-speed network.
Task Parallelization: Work divided into independent tasks.
Data Distribution: Each node processes its portion in parallel.
Monitoring & Output: Software monitors performance; results are saved to parallel file systems.
Specialized Software:
VASP: Ab initio quantum mechanical simulations for materials science.
ANSYS Fluent: Computational fluid dynamics (CFD).
Gaussian: Electronic structure modeling in chemistry.
GROMACS: Molecular dynamics for biomolecular systems.
Future of HPC and Parallel Computing
Exascale Computing: Systems capable of performing over a quintillion () calculations per second.
AI Acceleration: Integration of ML frameworks with HPC workflows.
Quantum Integration: Hybrid architecture combining classical and quantum power.
Smart Autonomous Systems: Self-optimizing environments enabling autonomous scientific discovery.