Distributed Systems Lecture Notes PDF

 Outline Flynn’s Taxonomy of computer architectures Distributed Systems categories Tightly coupled (Multiprocessor) Loosely Coupled (Multicomputer) 10/17/2024 Distributed Systems 2 Flynn’s Taxonomy of computer architectures  Flynn’s Taxono...

 Outline Flynn’s Taxonomy of computer architectures Distributed Systems categories Tightly coupled (Multiprocessor) Loosely Coupled (Multicomputer) 10/17/2024 Distributed Systems 2 Flynn’s Taxonomy of computer architectures  Flynn’s Taxonomy SISD Single Instruction/Single Data SIMD Single Instruction/Multiple Data MISD Multiple Instruction/Single Data MIMD Multiple Instruction/Multiple Data 10/17/2024 Distributed Systems 4  Single Instruction/Single Data Your desktop, before the spread of dual core CPUs PU – Processing Unit 10/17/2024 Distributed Systems 5  SIMD Processors that execute same instruction on multiple pieces of data NVIDIA GPUs 10/17/2024 Distributed Systems 6  SIMD Each core runs the same set of instructions on different data Example: NVIDIA: processes pixels of an image in parallel. Array Processor. 10/17/2024 Distributed Systems 7  MISD Example: Pipeline Architecture 10/17/2024 Distributed Systems 8  MIMD 10/17/2024 Distributed Systems 9  MIMD Shared Memory Distributed Memory Processors are all Each processor has its connected to a own individual memory location. "globally available" Each processor has no memory direct knowledge about Via either software or other processor's hardware means. memory. 10/17/2024 Distributed Systems 10  Summary for Flynn's taxonomy Item Proc. Inst. Data Parallelism Example Application M6800,M68000,i80 SISD 1 1 1 No Adding N numbers 86. Checking whether z MISD N N 1 Yes Pipeline is prime Super computers, Yes Adding matrices A SIMD N 1 N Array processors, ICL →synchronous and B (DAP). Yes Loosely coupled (multicomputer) MIMD N N N →Asynchronous Tightly coupled (multiprocessor) 10/17/2024 Distributed Systems 11 Distributed Systems categories  DS categories Based on Based on Based on Fault Based on Data Communication Resource Tolerance Distribution Method Management Mechanisms Message passing Centralized Replicated Passive vs. vs. vs. vs. shared memory decentralized partitioned data active replication Synchronous Consistency models vs. Load balancing Checkpointing and strategies (e.g., eventual rollback recovery asynchronous consistency, strong communication consistency) 10/17/2024 Distributed Systems 13 Distributed Computer Systems Hardware Software Tightly Loosely System Applications coupled coupled Web Bus Switch Bus OS applications Grid Single Crossbar Switch Non-OS computation Multiple M-stage 10/17/2024 Distributed Systems 14  To remember Bus Switched a single network bus, cable. there are individual wires from one machine to another and messages route along one of the outgoing wires. Sequential program Parallel program A sequence of operations A sequence of operations for the processor to follow for the processor to follow step by step. in parallel. 10/17/2024 Distributed Systems 15  H.W Point of view Point of view Tightly coupled Loosely coupled PE PE Connection n-processors on the n-computers same board connected together Delay Short Long Data rate High Low Usage parallel system works DS works on many on a single problem unrelated problems Communication Shared memory Messages 10/17/2024 Distributed Systems 16  Tightly coupled (Multiprocessor)  Bus-based multiprocessors SMP: Symmetric Multi-Processing All CPUs connected to one bus (backplane). One Shared memory (coherent). Limited to 64 processors. Disadvantages: One communication per clock pulse. One memory access at a time. With 4 or 5 processors connected to the bus it will be overloaded (1st problem). CPU A CPU B Device memory I/O Bus 10/17/2024 Distributed Systems 18  Bus-based multiprocessors Problem As the no of processors increase Dealing with bus overload Solution Add a high-speed cache memory between the processor and the bus to keep the most recent data. CPU does I/O to cache memory access main memory on cache miss CPU A CPU B Device memory cache cache I/O Bus 10/17/2024 Distributed Systems 19  Working with a cache The cache holds the most recently accessed words. All memory requests go through the cache. If the word requested is in the cache, the cache itself responds to the CPU, and no bus request is made Problem → Memory incoherency CPU A reads location 123 from memory CPU A CPU B Device 123 : 50 123 : 50 cache I/O Bus 10/17/2024 Distributed Systems 20  Working with a cache CPU A modifies location 123 CPU B reads location 123 from memory Get old value CPU A CPU B Device 123 : 50 123 : 70 123 : 50 I/O Memory not coherent! Bus 10/17/2024 Distributed Systems 21  Write-through cache Fix coherency problem by writing all values through bus to main memory CPU A modifies location 123 – write-through main memory is now coherent CPU B reads location 123 from memory loads into cache CPU A CPU B Device 123 : 70 123 : 70 123 : 70 I/O Bus 10/17/2024 Distributed Systems 22  Snoopy cache Add logic to each cache controller: monitor the bus Virtually all bus-based architectures use a snoopy cache CPU A CPU B Device 123 : 50 70 123 : 50 70 12345: 123 : 50 703 I/O write  0 Bus 10/17/2024 Distributed Systems 23  Switched multiprocessors Bus-based architecture does not scale to a large number of CPUs (8+) Divide memory into groups and connect chunks of memory to the processors with a crossbar switch memory memory memory memory CPU n2 CPU crosspoint CPU switches CPU 10/17/2024 Distributed Systems 24  Switched multiprocessors Disadvantages: No more than one CPU can access the same memory at the same time. Complexity. Low link utilization Crossbar switches are very expensive (problem) 10/17/2024 Distributed Systems 25  Omega network Reduce crosspoint switches by adding more switching stages CPU memory CPU memory CPU memory CPU memory 10/17/2024 Distributed Systems 26  Omega network with n CPUs and n memory modules: need log2n switching stages each with n/2 switches Total: (nlog2n)/2 switches.  Better than n2 but still a quite expensive  delay increases: ▪ 1024 CPU and memory chunks ▪ overhead of 10 switching stages to memory and 10 back. 10/17/2024 Distributed Systems 27  Example If a system of size 8*8 CPU and memory to be built using either Cross bar or Omega switch compare between both designs on the basis of: The required number of switching elements used. Number of switching stages. The cell delay in terms of switching element delay (T). Item Cross bar Omega number of switching elements N2 = 64 4* log2 8 = 12 Number of switching stages N=8 log2 8 = 3 Cell delay in terms of switching 8T T * log2 8 element delay T 10/17/2024 Distributed Systems 28  Loosely Coupled (Multicomputer) 10/17/2024 Distributed Systems 29  Bus-based multicomputer No shared memory Communication mechanism needed on bus Traffic much lower than memory access Need not use physical system bus ▪ Can use LAN (local area network) instead CPU CPU CPU CPU memory memory memory memory LAN LAN LAN LAN connector connector connector connector Interconnect 10/17/2024 Distributed Systems 30  Switched multicomputer Each computer has a direct access to another. CPU-to-CPU communication depends on the organization. Advantages Flexible and Expandable. Disadvantages Complex CPU CPU CPU CPU memory memory memory memory LAN LAN LAN LAN connector connector connector connector n-port switch 10/17/2024 Distributed Systems 31  Multicomputer Systems 2D-Grid Hypercube 10/17/2024 Distributed Systems 32 32 10/17/2024 Distributed Systems 33