Unit_2_Parallel_and_Distributed_Computing

Loading views...

Unit 2: Parallel and Distributed Computing

2.1 Parallel vs. Distributed Computing

These two terms are often used interchangeably, but they have precise meanings.

Precise Definitions

Parallel Computing:

Computation is divided among multiple processors sharing the same memory. All processors are homogeneous (same type). They communicate via a single shared address space.

Distributed Computing:

Computation is broken into units and executed on different computing elements — which may be on separate nodes, different machines, or even different geographic locations. Elements may be heterogeneous (different hardware/software).

  PARALLEL COMPUTING                     DISTRIBUTED COMPUTING
  +----+  +----+  +----+                 +--------+      +--------+
  |CPU1|  |CPU2|  |CPU3|                 | Node A |      | Node B |
  +----+  +----+  +----+                 | London |      | Tokyo  |
     \       |       /                   +--------+      +--------+
      \      |      /                          \              /
    +------------------+                        \            /
    |  SHARED MEMORY   |                      [ INTERNET / NETWORK ]
    |  (single address |                           |          |
    |   space)         |                    +-------+      +-------+
    +------------------+                    |Node C |      |Node D |
                                            | Paris |      | NYC   |
  All CPUs read/write shared               +-------+      +-------+
  memory directly. Fast.
  Tightly coupled.                         Nodes communicate by
                                           MESSAGE PASSING over network.
                                           Loosely coupled. Scalable.

Feature	Parallel Computing	Distributed Computing
Memory	Shared (single address space)	Each node has its own memory
Coupling	Tightly coupled	Loosely coupled
Location	Same physical machine	Different machines/locations
Homogeneity	Usually homogeneous (same CPU)	Heterogeneous allowed
Communication	Shared memory read/write	Message passing over network
Speed	Very fast	Latency due to network
Scope	One server	Internet-scale possible
Examples	Multi-core CPU, GPU, SMP	Grid Computing, Cloud Computing

Key Rule: All parallel systems can be considered a subset of distributed systems. But not all distributed systems are parallel systems.

2.2 Why Parallel Computing? (Drivers)

The Physical Limits of Sequential CPUs

  1970: CPU clock speed = 1 MHz
  1990: CPU clock speed = 33 MHz
  2000: CPU clock speed = 1 GHz
  2004: CPU clock speed ≈ 3-4 GHz  <-- SATURATION POINT
  2024: CPU clock speed ≈ 3-6 GHz  <-- No significant increase in 20 years!

Why can't we just make CPUs faster?

Speed of Light Limit: Electrons in a wire can only travel so fast. Signals can't move faster than ~30 cm/nanosecond.
Thermodynamic Limit: Packing more transistors generates exponential heat. Intel's Prescott CPUs (2004) reached ~100°C — the practical thermal ceiling.
Instruction-Level Parallelism Ceiling: Techniques like superscalar, pipelining, out-of-order execution have diminishing returns.

Solution: Instead of making one CPU faster (vertical scaling), connect multiple CPUs (horizontal scaling).

Industries Requiring Parallel Computing

Industry	Problem Requiring Parallel Compute
Life Sciences	Protein folding, genome sequencing (billions of operations)
Aerospace	Computational fluid dynamics, wing simulations
Geophysics	Seismic data analysis, oil exploration
Climate Science	Global weather simulation models
Finance	Real-time risk analysis of millions of trades
AI/ML	Training neural networks (GPUs are parallel processors)

2.3 Elements of Parallel Computing

2.3.1 Parallel Processing Concepts

Parallel Processing: Multiple tasks (subtasks of a larger problem) are processed simultaneously on multiple processors.

Divide-and-Conquer Strategy:

  LARGE PROBLEM
        |
        | split into subtasks
        v
  [Subtask 1] [Subtask 2] [Subtask 3] [Subtask 4]
       |            |           |           |
    [CPU 1]      [CPU 2]    [CPU 3]     [CPU 4]
       |            |           |           |
       +------------+-----------+-----------+
                    |
                    v
              COMBINED RESULT

Parallel Programming: Writing programs that explicitly break work into concurrent units and distribute them across multiple processors.

2.3.2 Flynn's Taxonomy (1966)

Michael Flynn classified computer architectures based on the number of instruction streams and data streams:

                          DATA STREAMS
                      SINGLE        MULTIPLE
                   +----------+  +----------+
  INSTRUCTION  S  |   SISD   |  |   SIMD   |
  STREAMS      I  | (Classic  |  | (GPU,    |
               N  |  Uniproc) |  |  Vector) |
               G  +----------+  +----------+
               L  +----------+  +----------+
               E  |   MISD   |  |   MIMD   |
               M  | (Rare,   |  | (Multi-  |
               U  | Pipeline)|  |  core,   |
               L  |          |  |  Cluster)|
               T  +----------+  +----------+
               I
               P
               L
               E

Class	Full Name	Meaning	Example
SISD	Single Instruction, Single Data	Classic sequential CPU	Old single-core PCs
SIMD	Single Instruction, Multiple Data	Same instruction on many data points at once	GPU, Intel AVX, vector processors
MISD	Multiple Instruction, Single Data	Rare. Same data processed by different pipelines	Some fault-tolerant systems
MIMD	Multiple Instruction, Multiple Data	Each processor runs different instructions on different data	Modern multi-core, clusters, distributed systems

Cloud Computing systems are MIMD: each VM runs completely different software (different instruction streams) on different data.

2.4 Distributed Computing: Foundations

2.4.1 Definition (Tanenbaum et al.)

"A distributed system is a collection of independent computers that appears to its users as a single coherent system."

This definition has two critical parts:

Collection of INDEPENDENT computers — each node can fail independently; they have their own OS, CPU, memory.
Appears as a SINGLE coherent system — users see one unified interface, not multiple machines.

Second definition (Coulouris et al.) — focuses on communication:

"A distributed system is one in which components located at networked computers communicate and coordinate their actions only by passing messages."

Message Passing is the ONLY way nodes in a distributed system communicate. Unlike parallel computing (shared memory), there is no shared address space.

2.4.2 Key Properties of Distributed Systems

Property	Explanation
Heterogeneity	Nodes may have different OS, CPU, programming languages
Openness	Standard protocols allow new components to be added
Scalability	Can add more nodes without redesigning the system
Transparency	Hides the distribution from users (they see one system)
Concurrency	Multiple clients use the system simultaneously
Continuous Availability	System stays up even when some nodes fail
Independent Failures	One node can fail without bringing down the entire system

2.4.3 Layered View of a Distributed System

  +------------------------------------------+
  |           APPLICATIONS (SaaS)            |  <-- Email, social networks,
  |   Social Networks, Scientific Computing  |      scientific apps
  +------------------------------------------+
  |         MIDDLEWARE LAYER (PaaS)          |  <-- Hides heterogeneity.
  |  Frameworks for Cloud App Development    |      Provides uniform API.
  |  (MapReduce, REST APIs, RPC, MPI)        |      Enables distributed apps.
  +------------------------------------------+
  |       OPERATING SYSTEM LAYER             |  <-- Manages local resources.
  |  IPC primitives, process scheduling,     |      TCP/IP sockets, file I/O.
  |  file system, device drivers             |
  +------------------------------------------+
  |        HARDWARE LAYER (IaaS)             |  <-- Physical servers, network
  |  Networking, Parallel Hardware,          |      cables, switches, routers.
  |  Storage, CPU                            |
  +------------------------------------------+

In the context of Cloud Computing:

Hardware Layer = IaaS (e.g., AWS EC2 physical servers)
Middleware Layer = PaaS (e.g., Google App Engine runtime)
Applications Layer = SaaS (e.g., Gmail, Google Docs)

2.5 Software Architectural Styles

An architectural style defines a vocabulary of components and connectors and how they can be combined.

Component: A unit of software that encapsulates a function or feature. Examples: programs, objects, processes, pipes, filters.
Connector: A communication mechanism connecting components. Examples: method calls, network sockets, event buses, shared memory.

There are 5 categories of software architectural styles:

2.5.1 Data-Centered Architectures

Core idea: The data (shared data structure) is the center of the system. All components operate on this central data.

(a) Repository Style

  +-------------------+
  | CENTRAL REPOSITORY|  <-- One shared database/data store
  |  (data structure) |
  +-------------------+
     /    |    \    \
    v     v     v    v
  [C1]  [C2]  [C3] [C4]   <-- Independent components that read/write the repo

Components query the repository; when data changes, appropriate processes are triggered.
Example: A database-backed web application. The DB is the repository; web services are components.

(b) Blackboard Style

Three-part structure:

  +---------------------+
  |    BLACKBOARD       |  <-- Shared data structure (the "knowledge base")
  |  (Knowledge Base)   |      All agents share this.
  +---------------------+
         |  triggers
         v
     [CONTROL]            <-- Monitors blackboard. Decides which KS to activate.
         |  activates
         v
  [KS1] [KS2] [KS3]       <-- Knowledge Sources (intelligent agents)
  (update the blackboard when they have new information)

Knowledge Sources (KS): Agents that update the blackboard when they can contribute.
Blackboard: The shared knowledge base. Agents read it and write to it.
Control: Activates the right knowledge source based on the blackboard state.

Analogy: Like a group of experts around a physical blackboard. Each expert (KS) reads what others wrote, and adds their own knowledge when they can contribute something useful.

Applications: Speech recognition (each KS handles phonemes, words, grammar), signal processing, AI systems.

2.5.2 Data-Flow Architectures

Core idea: The availability of data triggers computation. Data flows through a pipeline of transformations.

(a) Batch-Sequential Style

  [Program 1] --> [Output File 1] --> [Program 2] --> [Output File 2] --> [Program 3]
  
  Each program:
  - Reads entire input
  - Processes it completely
  - Writes entire output
  - Then STOPS
  Next program starts only after previous one finishes completely.

Granularity: Coarse-grained (whole files, not streams).
Concurrency: None — strictly sequential.
Latency: High (must wait for each entire stage to complete).
Example: A scientific job that pre-filters data → runs simulation → post-processes results. Common in mainframe era.

(b) Pipe-and-Filter Style

  [Filter1] --pipe--> [Filter2] --pipe--> [Filter3] --pipe--> [Filter4]
  
  Data flows through pipes (FIFO buffers). Each filter:
  - Starts as soon as data arrives on its INPUT pipe
  - Processes data INCREMENTALLY
  - Outputs immediately to its OUTPUT pipe
  - Does NOT wait for the previous filter to finish!

Real Example — Unix Shell Pipes:

cat access.log | grep "ERROR" | awk '{print $5}' | sort | uniq -c
# Each | is a pipe. Each command is a filter. They all run concurrently!

Real Example — CPU Instruction Pipeline:

  Instruction 1: [FETCH] --> [DECODE] --> [EXECUTE] --> [WRITEBACK]
  Instruction 2:            [FETCH]  --> [DECODE]  --> [EXECUTE] --> [WRITEBACK]
  Instruction 3:                         [FETCH]  --> [DECODE]  --> [EXECUTE]
  
  All stages run at the same time on different instructions = pipelining.

Comparison: Batch-Sequential vs. Pipe-and-Filter

Feature	Batch-Sequential	Pipe-and-Filter
Granularity	Coarse-grained (whole files)	Fine-grained (streaming data)
Latency	High (wait for whole stage)	Low (incremental processing)
Concurrency	None	Possible (filters run in parallel)
Input style	External (disk files)	Localized (from previous pipe)
Interaction	Non-interactive	Interactive (awkward but possible)
Example	Scientific batch jobs	Unix pipes, CPU pipeline, compilers

2.5.3 Virtual Machine Architectures

Core idea: An abstract execution engine (virtual machine) simulates features not available in the real hardware/software. Programs run on top of this abstract engine.

(a) Rule-Based Style

  [Input Facts/Assertions]
          |
          v
  +---------------------+
  |  INFERENCE ENGINE   |  <-- Matches facts against rules
  |  (Rule Evaluator)   |
  +---------------------+
          |
          v
  [Rules/Predicates Knowledge Base]
          |
          v
  [Output: New facts or actions]

Programs are expressed as rules (IF condition THEN action).
The inference engine evaluates which rules fire given the input data.
Examples:

- Process Control: Monitor sensor data; fire alarm if temperature > 90°C.

- Network Intrusion Detection (NIDS): If packet matches pattern X → flag as intrusion.

- Expert Systems: Medical diagnosis systems.

(b) Interpreter Style

  +----------------------------+
  |   INTERPRETER ENGINE       |  <-- Reads and executes pseudo-code
  +----------------------------+
       |          |
       v          v
  [Pseudo-code]  [Engine State]  <-- Code to run + current state of engine
       |
       v
  [Program State]               <-- Current state of the program being run

The engine reads a pseudo-program line by line and executes it.
Examples: Python interpreter, Bash shell, JVM (before JIT), web browser JavaScript engine.
Advantage: Portability — same pseudo-code runs on any platform with the interpreter.
Disadvantage: Performance overhead — each instruction is decoded at runtime.

2.5.4 Call and Return Architectures

Core idea: Components are connected by method/function calls. One component invokes another and waits for a result.

(a) Top-Down Style (Main Program + Subroutines)

  main()
    |
    +-- computeTax()
    |       |
    |       +-- calculateIncome()
    |       +-- applyDeductions()
    |
    +-- generateReport()
    |       |
    |       +-- formatData()
    |       +-- writeFile()

Classic procedural/imperative programming (C, Pascal, FORTRAN).
Uses divide-and-conquer: break the problem into sub-procedures.
Connectors: Function calls (local) or RPC (Remote Procedure Call for across network).
Advantage: Intuitive, easy to understand.
Disadvantage: Hard to maintain in large systems. Tight coupling.

(b) Object-Oriented Style

  [Order Object]           [Customer Object]        [Payment Object]
  - orderId                - customerId             - paymentId
  - items[]                - name                   - amount
  - total                  - email                  - status
  + placeOrder()           + getAddress()           + processPayment()
  + cancelOrder()          + updateProfile()        + refund()
       |                        |                         |
       +-- calls getAddress() --+                         |
       +-- calls processPayment() -------------------------+

Data + Operations are encapsulated together in objects.
Objects hide their internal state (encapsulation) and expose only methods.
Advantages: Better decomposition, reusability, maintainability.
Disadvantages:

- An object must know the identity of another object to call it.

- Shared objects need careful design to ensure consistency.

(c) Layered Style

  +---------------------------+
  | Presentation Layer        |  <-- User interface (browser, mobile app)
  +---------------------------+
           | calls
  +---------------------------+
  | Business Logic Layer      |  <-- Application rules (e.g., "discount if loyal customer")
  +---------------------------+
           | calls
  +---------------------------+
  | Data Access Layer         |  <-- SQL queries, ORM (e.g., Hibernate)
  +---------------------------+
           | calls
  +---------------------------+
  | Database Layer            |  <-- MySQL, PostgreSQL, Oracle
  +---------------------------+

Each layer provides services to the layer above and uses services from the layer below.
Communication only between adjacent layers (Presentation cannot talk directly to Database).
Examples: OSI 7-layer network model, TCP/IP stack, modern web app architecture.
Advantages: Modular, replaceable layers (swap MySQL for MongoDB at the data layer).
Disadvantages: Cannot easily add extra layers without changing protocols between them.

2.5.5 Independent Component Architectures

Core idea: Components are independent processes with their own lifecycle. They interact through defined communication patterns.

(a) Communicating Processes Style

  [Process A]  <---IPC/Network--->  [Process B]
      |                                  |
      +---IPC/Network--->  [Process C]   |
                               |         |
                               +---------+

Components are independent processes (possibly on different machines).
They coordinate using IPC (Inter-Process Communication) facilities: sockets, pipes, message queues.
Sub-models:

- Client-Server: Asymmetric roles (see System Styles section).

- Peer-to-Peer: Symmetric roles (see System Styles section).

(b) Event Systems Style

  [Component A]  -- fires event "ORDER_PLACED" -->  [Event Bus]
                                                         |
                                              +-----------+-----------+
                                              v           v           v
                                        [Handler 1]  [Handler 2] [Handler 3]
                                        (Send email) (Update DB) (Log event)

Components are loosely coupled: they don't know who handles their events.
A component publishes an event; any number of handlers can subscribe and react.
Advantages:

- Open system: New handlers can be added without changing the event publisher's code.

- Loose coupling: Publisher doesn't know or care who handles the event.

- Components don't need to know each other's identity.

Disadvantages:

- Loss of control: Cannot predict at design time how many handlers will fire.

- Harder to reason about system behavior statically.

Examples: GUI frameworks (button click = event), Node.js EventEmitter, Apache Kafka, AWS SNS.

2.6 System Architectural Styles

System styles describe the physical deployment of components across machines.

2.6.1 Client-Server Architecture

Basic Model:

  [CLIENT 1] --request-->  +----------+
  [CLIENT 2] --request-->  |  SERVER  |  <-- Processes requests, returns responses
  [CLIENT 3] --request-->  +----------+
  [CLIENT N] --request-->
  
  Flow: Client sends REQUEST --> Server PROCESSES --> Server sends RESPONSE
  Communication is UNIDIRECTIONAL (client always initiates)

Three Logical Components (Tiers):

Presentation Tier: What the user sees (GUI, web browser).
Application Logic Tier: Business rules, processing.
Data Storage Tier: Database, file storage.

Client Models:

Model	Client does	Server does
Thin Client	Only presentation (display results)	All processing + data storage
Fat Client	Presentation + most application logic	Only data storage

Multi-Tier Architectures

Two-Tier Architecture:

  [CLIENT / Browser]  <--->  [SERVER (logic + database on same machine)]
  
  - Simple. Works for small systems.
  - Problem: Server becomes a bottleneck as users grow.
  - Cannot scale easily.

Three-Tier Architecture:

  [Browser / App]  <--->  [Application Server]  <--->  [Database Server]
    (Presentation)          (Business Logic)              (Data Storage)
    
  - Each tier can be scaled independently!
  - App server can be replicated (load balanced).
  - Database server can be clustered.
  - Example: Web browser + Tomcat server + MySQL database.

N-Tier Architecture:

  [Browser] <-> [Load Balancer] <-> [App Server Pool] <-> [Cache Layer] <-> [DB Cluster]
                                          |
                                    [External Services]
                                    (Payment, Maps, Email APIs)
  
  - Used in large-scale web apps (Google, Amazon, Facebook).
  - Each box can be independently scaled, replaced, or updated.

Limitations of Client-Server:

Centralized server = single point of failure.
Server can become bottleneck in many-to-one scenarios with millions of clients.
Not suitable for truly large-scale, decentralized systems.

2.6.2 Peer-to-Peer (P2P) Architecture

Core Idea: Every node (peer) is simultaneously a client AND a server. No central authority.

  Pure P2P Network:
  
  [Peer A] <---------> [Peer B]
      ^                    ^
      |                    |
      v                    v
  [Peer D] <---------> [Peer C]
  
  Each peer:
  - Downloads FROM other peers (acts as CLIENT)
  - Uploads TO other peers (acts as SERVER)
  - Stores part of the shared data

Advantages over Client-Server:

No single point of failure: System works even if many nodes go offline.
Massive scalability: Each new peer adds both demand AND supply (serves other peers).
No bottleneck: Load is distributed across all peers.

Disadvantages:

Complexity: Algorithms for finding content, handling failures, and maintaining consistency are much harder.
No central control: Hard to enforce policies, track usage, or guarantee data availability.

P2P Variants

① Pure P2P (Gnutella):

  All peers are identical. Content search = flood every neighbor with query.
  Problem: Massive network traffic (flooding doesn't scale well).

② Hybrid P2P with Supernodes (Skype, Kazaa):

  Regular peers
      |
  [SUPERNODE] <--> [SUPERNODE] <--> [SUPERNODE]
      |                |                 |
  Regular peers   Regular peers    Regular peers
  
  Supernodes: High-bandwidth peers that maintain index of their group.
  Regular peers: Connect to a supernode for content discovery.
  After discovery, transfer directly peer-to-peer.
  
  Benefit: Reduces flooding. More efficient search.
  Trade-off: Supernodes introduce partial centralization.

③ Structured P2P (BitTorrent):

  [Tracker Server] -- maintains list of peers sharing a file
       |
  [Peer A] <-chunk--> [Peer B] <-chunk--> [Peer C]
       ^                                       |
       +--------<---chunk---<-----------------+
  
  File is split into chunks. Different peers download different chunks.
  Then peers share chunks with each other (swarming).
  Faster than downloading from one server!

P2P Real-World Applications:

Application	P2P Model	Purpose
BitTorrent	Structured (tracker + peers)	File sharing
Gnutella	Pure P2P	File sharing (inefficient at scale)
Kazaa	Supernode P2P	File sharing
Skype	Supernode P2P	VoIP calling (pre-2012, now centralized)
Bitcoin	Pure P2P	Cryptocurrency/blockchain
IPFS	Structured P2P	Distributed web content delivery

2.7 Client-Server vs. Peer-to-Peer: Full Comparison

Feature	Client-Server	Peer-to-Peer
Roles	Separate: Client & Server	Same node = both client & server
Centralization	Centralized server	Fully distributed
Single Point of Failure	Yes (server)	No
Scalability	Limited (server bottleneck)	High (each peer helps)
Complexity	Simple to design	Complex algorithms needed
Data consistency	Easy (central server)	Hard (distributed consensus)
Examples	Web apps, email, FTP	BitTorrent, Gnutella, Bitcoin
Control	Easy to enforce policies	Difficult to control

2.8 Architectural Styles Summary Table

Style	Category	Core Components	Connectors	Cloud Relevance
Repository	Data-Centered	Shared DB + Clients	DB queries	SaaS databases (Google Drive)
Blackboard	Data-Centered	Blackboard, KSs, Control	Shared memory	AI systems, speech recognition
Batch-Sequential	Data-Flow	Programs in sequence	Files	HPC batch jobs, Hadoop jobs
Pipe-and-Filter	Data-Flow	Filters	Pipes (streams)	Unix pipelines, streaming analytics
Rule-Based	Virtual Machine	Inference Engine, Rules	Rule evaluation	NIDS, Expert Systems
Interpreter	Virtual Machine	Interpreter, Pseudo-code	Interpretation	JVM, Python runtime
Top-Down	Call & Return	Main + Subroutines	Function calls	Legacy applications
Object-Oriented	Call & Return	Objects	Method calls	Most modern software
Layered	Call & Return	Layers	Interfaces/Protocols	OSI model, web apps, OS kernel
Communicating Processes	Independent	Processes	IPC, Sockets	Distributed microservices
Event Systems	Independent	Components, Event Bus	Events/Callbacks	AWS SNS, Apache Kafka, GUI
Client-Server	System	Client, Server	Network protocol	Web applications, REST APIs
Peer-to-Peer	System	Peers (equal roles)	Network messages	BitTorrent, Bitcoin, Skype

Navigation

← Previous Next →