CS621 Parallel and Distributed Computing Short Notes PDF

**CS621 Parallel and Distributed Computing Short Notes** **for Midterm Preparation** **Parallel Computing** Parallel computing is a type of computation in which many calculations or processes are carried out simultaneously. Large problems are divided into smaller ones, which are then solved concu...

**CS621 Parallel and Distributed Computing Short Notes** **for Midterm Preparation** **Parallel Computing** Parallel computing is a type of computation in which many calculations or processes are carried out simultaneously. Large problems are divided into smaller ones, which are then solved concurrently. The main characteristics of parallel computing include: - Multiple Processors - Concurrency - Performance Improvement Parallel computing can be implemented at various levels, from low-level hardware circuits to high-level algorithms. **Distributed Computing** Distributed computing involves multiple computers working together over a network to achieve a common goal. Each computer (node) in the network performs part of the overall task, and the results are combined to form the final output. Key features include: - Geographically Dispersed Systems - Autonomy - Resource Sharing Distributed computing systems often enhance fault tolerance, scalability, and resource utilization by leveraging the power of multiple interconnected machines. Examples include cloud computing, grid computing, and peer-to-peer networks. **History of computing:** **History of Computing: Key Eras** **1. Batch Processing Era (1950s - 1960s)** The batch processing era marked the beginning of modern computing, characterized by: Mainframes and Punch Cards: Computing tasks were executed in batches. Users submitted jobs (programs and data) on punch cards to operators. Sequential Processing: Jobs were processed one after another without user interaction during execution. High Utilization: Mainframes were expensive, so maximizing their use was crucial. **Significant Systems** - IBM 701 (1952): One of the first commercial mainframe computers. - IBM 1401 (1959): Widely used for business applications. **2. Time-Sharing Era (1960s - 1970s)** The time-sharing era introduced more interactive computing: - Multiple Users: Allowed multiple users to interact with the computer simultaneously by sharing CPU time. - Terminals: Users accessed the mainframe via terminals (keyboard and monitor) rather than punch cards. - Increased Accessibility: Made computing more accessible to organizations and educational institutions. **Important Systems:** - Compatible Time-Sharing System (CTSS, 1961): Developed at MIT, one of the first time-sharing systems. - Multics (1965): Influential time-sharing operating system that influenced the development of Unix. **3. Desktop Era (1980s - 1990s)** The desktop era saw the rise of personal computing: Personal Computers (PCs)\*\*: Computers became affordable and accessible for individual use. Graphical User Interface (GUI)\*\*: Made computers more user-friendly with visual interfaces. \- \*\*Software Revolution\*\*: Proliferation of software applications for business, education, and entertainment. **Key Milestones:** - Apple II (1977): Popularized personal computing. - IBM PC (1981): Set the standard for PC hardware and software compatibility. - Windows 95 (1995): Integrated GUI and significant networking capabilities, leading to widespread home and office use. **4. Network Era (1990s - Present)** The network era focuses on interconnected computing and the internet: - Internet and Web: The World Wide Web (introduced in 1990) revolutionized information sharing and communication. - Client-Server Architecture: Enabled distributed computing with clients (PCs) interacting with servers over networks. - Wireless and Mobile Computing: Smartphones, tablets, and wireless networks allowed ubiquitous access to information. - Cloud Computing: Delivery of computing services over the internet, providing scalable resources and services. - Significant Developments: - ARPANET (1969): Precursor to the internet. - Netscape Navigator (1994): Popular web browser that contributed to the web's growth. - Amazon Web Services (AWS, 2006): Pioneered cloud computing services. Each era represents a significant shift in how computing power was utilized, transforming from centralized, limited-access systems to pervasive, interconnected networks that empower users globally. **Difference Between Serial and Parallel Computing** **Serial Computing** - Execution: Tasks are executed one after another sequentially. - Processor: Uses a single processor. - Performance: Limited by the speed of the single processor. - Complexity: Simpler to implement and debug. **Parallel Computing** - Execution: Tasks are divided and executed simultaneously. - Processors: Utilizes multiple processors. - Performance: Can significantly increase speed and efficiency by performing many calculations at once. - Complexity: More complex due to the need for coordination and synchronization between processors. **Introduction to Parallel Computing** Parallel computing is a field of computer science that focuses on the simultaneous execution of multiple tasks to solve large and complex problems more efficiently. By dividing a problem into smaller subproblems and solving them concurrently, parallel computing can significantly reduce computation time and improve performance. **Key Concepts** **1. Parallelism:** - Task Parallelism: Different tasks are executed in parallel, often in a coordinated manner. Example: Different sections of a document being spell-checked simultaneously. - Data Parallelism: The same task is performed on different pieces of distributed data simultaneously. Example: Applying a filter to different parts of an image at the same time. **2. Architectures:** - Multi-core Processors: Single computing units with multiple processing cores. Each core can perform separate tasks simultaneously. - Distributed Systems: Multiple independent computers (nodes) connected via a network, working together to perform parallel computations. Examples include clusters, grids, and clouds. **3. Programming Models:** - Shared Memory: Multiple processors access the same memory space. Example: Threads in a multi-core CPU. - Distributed Memory: Each processor has its own local memory. Communication between processors is done through a network. Example: Message Passing Interface (MPI). **4. Synchronization:** - Coordination of parallel tasks is crucial to avoid conflicts and ensure correctness. Common methods include locks, semaphores, and barriers. **5. Scalability:** - The ability of a parallel system to handle increasing numbers of processors efficiently. Good scalability means performance improves proportionally with the addition of more processors. **Applications** **Parallel computing is used in a wide range of fields:** - Scientific Simulations: Weather forecasting, climate modeling, and astrophysics simulations. - Data Analysis: Big data processing, machine learning, and artificial intelligence. - Engineering: Computer-aided design (CAD), finite element analysis, and computational fluid dynamics. - Medical Research: Genome sequencing, protein folding, and medical imaging. **Benefits** - Speed: Drastically reduces computation time for large and complex problems. - Efficiency: Better utilization of resources by distributing tasks across multiple processors. - Capability: Enables the solution of problems that are too large or complex for a single processor to handle. **Challenges** - Complexity: Writing parallel programs can be more complex than writing serial ones due to the need for synchronization and communication. - Debugging: More difficult to debug due to the concurrent execution of tasks. - Overhead: Managing parallel tasks involves overhead that can sometimes diminish the performance gains. **Principles of Parallel Computing** **1. Decomposition:** - Task Decomposition: Breaking down a large problem into smaller tasks that can be executed simultaneously. - Data Decomposition: Dividing data into smaller chunks to be processed in parallel**.** **2. Concurrency:** - Performing multiple operations simultaneously to increase computational speed. **3. Communication:** - Inter-Process Communication (IPC): Mechanisms for processes to exchange information. - Message Passing: Sending and receiving messages between distributed systems. - Shared Memory: Multiple processors accessing the same memory space. **4. Synchronization:** Coordinating parallel tasks to ensure correct execution. This involves: - Locks: Prevent simultaneous access to resources. - Semaphores: Control access to shared resources. - Barriers: Ensure all tasks reach a certain point before continuing. **5. Scalability:** - The ability of a parallel system to efficiently utilize increasing numbers of processors. **6. Load Balancing:** - Evenly distributing work across all processors to avoid some processors being idle while others are overloaded. **7. Fault Tolerance:** - Ensuring the system can continue to operate correctly even if some components fail. **8. Granularity:** The size of the tasks into which a problem is decomposed: - Fine-Grained Parallelism: Smaller tasks with frequent communication. - Coarse-Grained Parallelism: Larger tasks with less frequent communication. Understanding and effectively applying these principles is crucial for developing efficient and robust parallel computing systems. **Why Use Parallel Computing?** **1. Increased Speed:** - Faster Computation: Parallel computing can significantly reduce the time required to complete large and complex tasks by dividing the work among multiple processors. **2. Efficiency:** - Better Resource Utilization: Utilizes the full potential of modern multi-core processors and distributed systems, leading to more efficient use of computational resources. **3. Scalability:** - Handling Larger Problems: Allows for the solving of problems that are too large or complex for a single processor by distributing the workload. **4. Cost-Effectiveness:** - Economies of Scale: Distributed computing can be more cost-effective by using multiple less expensive machines instead of one highly expensive supercomputer. **5. Real-Time Processing:** - Timely Results: Essential for applications requiring real-time data processing, such as weather forecasting, financial modeling, and real-time simulations. **6. Complex Simulations:** - Advanced Research: Enables detailed simulations and models in scientific research, engineering, and other fields that require high computational power. **Week \#2** **Introduction to Distributed Computing** Distributed computing involves multiple computers (nodes) working together over a network to achieve a common goal. Here\'s a brief overview: **1. Decentralized Architecture:** - Unlike traditional centralized computing, where a single powerful machine handles all tasks, distributed computing distributes tasks across multiple nodes. **2. Resource Sharing:** - Nodes share resources like processing power, memory, and data storage, making more efficient use of available resources. **3. Autonomy:** - Each node operates independently and can function without relying on a central controller. **4. Concurrency:** - Tasks can be executed concurrently across multiple nodes, improving overall system performance and responsiveness. **5. Fault Tolerance:** - Distributed systems are resilient to failures. If one node fails, the system can continue to operate by redistributing tasks to other available nodes. **6. Scalability:** - Distributed computing systems can easily scale up by adding more nodes, allowing them to handle increasing workloads or larger datasets. **7. Examples:** - Cloud Computing: Peer-to-Peer Networks - Distributed Databases: **Applications of Parallel and Distributed Computing** Parallel Computing: 1\. Scientific Simulations: - Weather forecasting, climate modeling, molecular dynamics simulations, and computational fluid dynamics rely on parallel computing for complex simulations. 2\. Data Analytics: - Big data processing, data mining, and machine learning algorithms benefit from parallel computing to analyze large datasets efficiently. 3\. Financial Modeling: - Parallel computing is used for risk analysis, option pricing, and portfolio optimization in financial markets. 4\. Computer Graphics and Rendering: - Rendering complex scenes in animation studios and creating realistic visual effects in movies often require parallel computing techniques. 5\. Genomics and Bioinformatics: - Analyzing genetic data, sequencing genomes, and simulating biological processes use parallel computing for faster analysis. **Distributed Computing:** **1. Cloud Computing:** - Services like Amazon Web Services (AWS), Microsoft Azure, and Google Cloud Platform provide distributed computing resources over the internet for storage, computation, and networking. 2**. Content Delivery Networks (CDNs):** - CDNs distribute web content across multiple servers globally, reducing latency and improving website performance. **3. Peer-to-Peer Networks:** - BitTorrent and other peer-to-peer networks distribute files across multiple nodes for faster downloads and decentralized file sharing. **4. Distributed Databases:** - Systems like Apache Cassandra, MongoDB, and Google Spanner distribute data across multiple nodes for improved scalability, fault tolerance, and performance. **5. Internet of Things (IoT:** - Distributed computing is essential for processing data from a vast number of IoT devices and sensors, enabling real-time analytics and decision-making. **6. Distributed Processing in Grid Computing:** - Grid computing distributes computational tasks across multiple nodes for scientific research, large-scale data processing, and high-performance computing. **Issues in Parallel and Distributed Computing** **1. Load Balancing:** - Distributing tasks evenly among processors or nodes to ensure efficient resource utilization and avoid bottlenecks. **2. Synchronization and Communication Overhead:** - Coordinating parallel tasks and managing communication between nodes can introduce overhead and reduce performance. **3. Scalability Challenges:** - Ensuring that distributed systems can scale up effectively to handle increasing workloads without sacrificing performance or reliability. **4. Fault Tolerance and Reliability:** - Dealing with node failures, network partitions, and other faults while maintaining system availability and data consistency. **5. Complexity of Programming Models:** - Developing and debugging parallel and distributed applications can be more challenging due to the complexities of synchronization, communication, and fault handling. **6. Data Management and Consistency:** - Ensuring data consistency and integrity across distributed systems, especially in scenarios where data is replicated across multiple nodes. **7. Security Concerns:** - Addressing security threats such as unauthorized access, data breaches, and denial-of-service attacks in distributed environments. **8. Scalability of Distributed Databases:** - Managing distributed databases at scale while ensuring data availability, consistency, and performance. **9. Network Latency and Bandwidth Limitations:** - Dealing with network delays and limited bandwidth, especially in wide-area distributed systems, can impact application performance and responsiveness. **10. Interoperability and Compatibility:** - Ensuring compatibility between different hardware and software platforms in heterogeneous distributed environments. Addressing these issues requires careful design, implementation, and management of parallel and distributed computing systems to achieve desired performance, reliability, and scalability. **Parallel and Distributed Computing Efforts** **1. Research and Development:** - Ongoing research efforts focus on improving algorithms, programming models, and system architectures to enhance the performance, scalability, and reliability of parallel and distributed computing systems. **2. Open Source Projects:** - Various open-source initiatives, such as Apache Hadoop, Spark, and Kubernetes, provide frameworks and tools for developing and managing parallel and distributed applications. **3. Industry Solutions:** - Leading technology companies invest in developing and deploying distributed computing solutions, such as cloud computing platforms (AWS, Azure, Google Cloud) and distributed databases (MongoDB, Cassandra). **4. Standardization Efforts:** - Standardization bodies like the IEEE and ISO work on defining standards for distributed computing, ensuring interoperability, compatibility, and security across different systems and platforms. **5. Education and Training:** - Academic institutions and training programs offer courses and certifications in parallel and distributed computing to equip professionals with the skills and knowledge needed to design, develop, and manage distributed systems effectively. **6. Collaborative Research Projects:** - Collaborative efforts between academia, industry, and government organizations focus on addressing challenges and advancing the state-of-the-art in parallel and distributed computing, particularly in areas like high-performance computing, big data analytics, and edge computing. **7. Community Engagement:** - Online communities, forums, and conferences provide platforms for researchers, developers, and practitioners to exchange ideas, share best practices, and collaborate on solving complex problems in parallel and distributed computing. Efforts in these areas contribute to the continuous advancement and innovation of parallel and distributed computing technologies, driving improvements in performance, scalability, and reliability across various domains and applications. **Week\#3** **1. Shared Memory (SharedMem):** - Shared memory is a type of parallel computing architecture where multiple processors share a common memory space. All processors can access the same memory locations directly, allowing for easy communication and synchronization between processes. **2. Distributed Memory (DistMem):** - Distributed memory is a parallel computing architecture where each processor has its own local memory, and communication between processors is done explicitly through message passing. Distributed memory systems are commonly used in clusters and distributed computing environments. **3. Flynn's classification of computer architectures (FlynnCCA):** - Flynn\'s taxonomy classifies computer architectures based on the number of instruction streams and data streams. It includes four categories: SISD, SIMD, MISD, and MIMD. **4. SISD (Single-Instruction Single-Data):** - SISD is a traditional computer architecture where a single processor executes a single instruction on a single piece of data at a time. This is the simplest and most common type of computer architecture. **5. SIMD (Single-Instruction Multi-Data):** - SIMD architecture consists of multiple processing units that execute the same instruction on multiple pieces of data simultaneously. This is commonly used in vector processing and multimedia applications. **6. MISD (Multiple-Instruction Single-Data):** - MISD architecture involves multiple processing units executing different instructions on the same piece of data. While theoretically possible, it is not commonly used in practice due to its complexity and limited applications. **7. MIMD (Multi-Instruction Multi-Data):** - MIMD architecture consists of multiple processing units executing different instructions on different pieces of data concurrently. This is the most flexible and widely used type of parallel computing architecture, commonly found in multi-core processors, clusters, and distributed systems. **8. SIMD-MIMD Comparison:** - SIMD and MIMD are two different types of parallel computing architectures with distinct characteristics. SIMD involves parallel processing of multiple data elements using the same instruction, while MIMD allows for independent execution of different instructions on different data. Each architecture has its own strengths and weaknesses, making them suitable for different types of applications. **Week \#4** **Introduction to Fault Tolerance** Fault tolerance is a critical aspect of distributed computing systems aimed at ensuring the system\'s continued operation even in the presence of faults or failures. Here are key concepts related to fault tolerance: **1. Faults:** - Faults refer to any deviation of a system from its correct behavior. These can include hardware failures, software bugs, communication errors, and other unexpected events. **2. Fault Tolerance:** - Fault tolerance is the ability of a system to continue operating properly in the presence of faults. It involves detecting, isolating, and recovering from faults to maintain system functionality and data integrity. **3. Process Resilience (ProcResilience):** - Process resilience refers to the ability of individual processes or components within a distributed system to withstand faults and continue functioning correctly. Techniques such as process monitoring, redundancy, and error recovery mechanisms contribute to process resilience. **4. Reliable Client-Server Communication (ReliableCSC):** - Reliable client-server communication ensures that messages exchanged between clients and servers in a distributed system are delivered correctly and in the intended order, even in the presence of network failures or message loss. **5. Reliable Group Communication (RelGroupComm):** - Reliable group communication extends the concept of reliable communication to groups of processes within a distributed system. It ensures that messages sent to a group of processes are reliably delivered to all group members despite failures or network partitions. **6. Distributed Commit (DistCommit):** - Distributed commit protocols ensure the consistency of distributed transactions by coordinating the commit or rollback of changes across multiple distributed components. These protocols help maintain data consistency and integrity in distributed databases and transactional systems. **7. Recovery:** - Recovery mechanisms are essential for restoring a system to a consistent and operational state after a fault or failure occurs. This may involve restarting failed processes, reconfiguring the system, restoring data from backups, or other recovery strategies. **Week \#5** **Introduction to Load Balancing (Intro-LB)** Load balancing is a fundamental concept in distributed computing, aimed at distributing computational tasks or network traffic across multiple resources to ensure optimal resource utilization, improve performance, and avoid overloading any single resource. Here\'s a brief overview: **1. Purpose:** - Load balancing aims to evenly distribute workloads across multiple servers, processors, or network links to prevent bottlenecks, minimize response times, and maximize throughput. **2. Benefits:** - Improved Performance: Evenly distributing tasks can reduce response times and improve system throughput. - Scalability: Load balancing allows systems to scale horizontally by adding more resources as demand increases. - Fault Tolerance: Distributing tasks across multiple resources enhances system resilience by reducing the impact of failures on overall system performance. - Efficient Resource Utilization: Load balancing ensures that resources are utilized optimally, avoiding underutilization or overloading of any single resource. **Mapping Techniques for Load Balancing (MapTech-LB)** Mapping techniques for load balancing involve strategies for assigning tasks or requests to resources in a distributed system. These techniques include: **1. Static Mapping for Load Balancing (StaticMap-LB):** - Static mapping involves pre-determining the assignment of tasks to resources based on factors such as resource capabilities, workload characteristics, and system topology. This mapping remains fixed unless manually reconfigured. **2. Schemes for Static Mapping (Schemes4StaticMap):** - Various schemes exist for static mapping, including round-robin, least-connections, and weighted round-robin, each with its own advantages and trade-offs in terms of fairness, efficiency, and complexity. **3. Schemes for Static Mapping-II (Schemes4StaticMapII):** - Additional schemes for static mapping may include hash-based mapping, where task assignment is determined by hashing task attributes or identifiers to select specific resources. **4. Dynamic Mapping for Load Balancing (DynamicMap-LB):** - Dynamic mapping adapts task assignment based on real-time changes in system conditions, such as resource availability, workload variations, or network conditions. This allows for more flexible and responsive load balancing. **5. Schemes for Dynamic Mapping:** - Dynamic mapping schemes may include load-based, feedback-based, or adaptive algorithms that continuously monitor system performance and adjust task assignment dynamically to optimize resource utilization and response times. **Week \#6** **Concurrency Control** Concurrency control is a critical aspect of database management systems (DBMS) that ensures transactions execute correctly and concurrently in a multi-user environment without interfering with each other. Here\'s an overview of key concepts related to concurrency control: **Basic Approaches to Achieving Concurrency (ConcApproaches)** **1. Locking:** - Transactions acquire locks on data items to prevent other transactions from accessing them concurrently. Common lock types include shared locks and exclusive locks. **2. Timestamp Ordering:** - Transactions are assigned timestamps, and the order of transactions is determined based on their timestamps. Conflicts are resolved by comparing timestamps. **3. Optimistic Concurrency Control:** - Transactions proceed without acquiring locks initially. Conflicts are detected and resolved at the time of transaction commit. **Models for Programming Concurrency (ConcProgModels)** **1. Thread-Based Concurrency:** - Concurrency is achieved by using multiple threads of execution within a single process. Threads share the same memory space but have their own execution context. **2. Event-Based Concurrency:** - Concurrency is achieved through event-driven programming, where tasks are executed in response to events or messages. This model is common in asynchronous programming. **Memory Hierarchies (MemHierarchies)** **1. Memory Levels:** - Memory hierarchies consist of different levels of memory with varying access speeds and capacities, including registers, cache memory, main memory (RAM), and secondary storage (disk). **2. Principle of Locality:** - Memory hierarchies exploit the principle of locality, where programs tend to access a small subset of data frequently (temporal locality) or access data that is nearby in memory (spatial locality). **Limitations of Memory System Performance (LimitationsOfMSP)** **1. Memory Latency:** - The time it takes to access data from memory can be a significant bottleneck in system performance, especially for large-scale data-intensive applications. **2. Memory Bandwidth:** - The rate at which data can be transferred between the memory and the processor affects overall system performance, particularly for memory-bound applications. **Improving Effective Memory Latency Using Caches (ImprEMLatency)** **1. Cache Memory:** - Cache memory is a small, fast memory located between the processor and main memory, designed to store frequently accessed data and instructions. **2. Cache Hierarchy:** - Modern processors have multiple levels of cache memory (L1, L2, L3) with varying sizes and access speeds, forming a cache hierarchy to reduce effective memory latency. **Effect of Memory Bandwidth** **1. Data Intensive Workloads:** - Workloads that require frequent memory accesses, such as scientific simulations, data analytics, and database applications, are heavily impacted by memory bandwidth limitations. **2. Memory-Bound Applications:** - Applications that are limited by memory bandwidth may not fully utilize the computational resources of a system, leading to underutilization of processing power.