Printing and Design (IT-803 (C)) - Unit 3 Short Notes

UNIT 3: BLOCKCHAIN TECHNOLOGY & PARALLEL COMPUTING

I. BLOCKCHAIN TECHNOLOGY

A. Cryptographic Foundations

1. Cryptographic Hash Functions

A cryptographic hash function is a deterministic algorithm that maps input data of any size to a fixed-size output (hash/digest). It is fundamental to blockchain integrity.

Essential Properties:

• Deterministic: Same input always produces same hash.

• Pre-image Resistance: Given a hash h, it is computationally infeasible to find any input x such that hash(x) = h.

• Second Pre-image Resistance: Given input x1, it is infeasible to find a different x2 such that hash(x1) = hash(x2).

• Collision Resistance: It is infeasible to find any two distinct inputs x1 and x2 such that hash(x1) = hash(x2).

• Avalanche Effect: A small change in input drastically changes the output hash.

Common Examples: SHA-256 (used in Bitcoin), SHA-3, Keccak-256 (used in Ethereum).

[!TIP] Exam Focus: Be prepared to define each property and explain why collision resistance is critical for blockchain security.

2. Public Key Cryptography (Asymmetric Cryptography)

Uses a pair of mathematically linked keys: a public key (shared openly) and a private key (kept secret).

Core Components & Principles:

• Key Generation: Algorithm creates the key pair.

• Encryption/Decryption: Data encrypted with a public key can only be decrypted by the corresponding private key (confidentiality).

• Digital Signatures: Data signed with a private key can be verified by anyone with the corresponding public key (authentication & non-repudiation).

  • Signing: Signature = Sign(Private_Key, Message)

  • Verification: Verify(Public_Key, Message, Signature) → True/False

• Key Exchange: Protocols (like Diffie-Hellman) to securely establish a shared secret.

In Blockchain: Used for creating wallet addresses (derived from public keys) and signing transactions to prove ownership.

3. Merkle Trees (Hash Trees)

A Merkle Tree is a binary tree structure where every leaf node is a hash of a data block (e.g., a transaction), and every non-leaf node is a hash of its child nodes' hashes.

Construction:

1. Hash each transaction (leaf node).

2. Pair up hashes and hash them together to create the next level.

3. Repeat until a single hash remains: the Merkle Root.

Importance in Blockchain:

• Data Integrity & Verification: The Merkle Root is stored in the block header. Any change to a transaction changes its hash, propagating up to alter the root, making tampering evident.

• Efficient Proof of Inclusion (Merkle Proof): To prove a transaction is in a block, only the log₂(N) hashes along the path from the transaction leaf to the root need to be provided (where N is number of transactions). This is far more efficient than downloading all transactions.

• Scalability: Enables Simplified Payment Verification (SPV) nodes to verify transactions without storing the entire blockchain.

[!TIP] Exam Focus: A very high-frequency question. Be ready to draw the tree structure and explain the proof-of-inclusion process step-by-step.

B. Blockchain Structure & Bitcoin Fundamentals

1. Block Structure

A block is a container for data. Its structure is hierarchical.

DiagramCANVAS: Draw a block with two main sections: a rectangular "Block Header" on top, and a list of "Transactions" below. The Block Header should contain labeled fields: Version, Previous Block Hash, Merkle Root, Timestamp, Difficulty Target, Nonce. Connect the Merkle Root field to the root of a small Merkle Tree drawn in the Transactions section.

Block Header (80 bytes in Bitcoin):

• Version: Software/protocol version.

• Previous Block Hash (Hash Pointer): 256-bit hash of the previous block's header. This creates the chain.

• Merkle Root: 256-bit hash of the root of the Merkle tree of all transactions in this block.

• Timestamp: Block creation time (in seconds since epoch).

• Difficulty Target (Bits): The proof-of-work difficulty threshold for this block.

• Nonce: A 32-bit number miners vary to find a valid proof-of-work.

Transactions List: A variable-length list of all transactions included in the block. The first is the coinbase transaction (reward for the miner).

2. Bitcoin P2P Network

A decentralized, peer-to-peer network where nodes (computers running Bitcoin software) communicate directly.

• Nodes: Full nodes (store entire blockchain, validate all transactions) and SPV nodes (store only headers).

• Transaction Propagation: A user broadcasts a signed transaction to its connected peers. Each peer validates it (signature, no double-spend) and, if valid, forwards it to its peers. This flooding protocol ensures rapid dissemination.

• Block Propagation: Miners, upon finding a valid block, broadcast it. Nodes validate the block (PoW, transactions, state) and, if valid, add it to their chain and propagate.

3. Transactions & Double Spending Problem

• Transaction: A transfer of value. It contains inputs (references to previous unspent outputs, UTXOs) and outputs (new UTXOs with amounts and locking scripts).

• Double Spending Problem: The risk of spending the same digital token (UTXO) more than once. In a digital file, copying is trivial.

Prevention Mechanisms:

1. Immutable Ledger: Once a transaction is confirmed in a block deeply buried in the chain, reversing it requires redoing the PoW for that block and all subsequent blocks, which is computationally infeasible.

2. Consensus & Confirmations: Nodes agree on the canonical chain (the longest valid chain). A transaction gets a "confirmation" for each subsequent block added on top of its block. 6 confirmations are considered secure against double-spend in Bitcoin.

3. Network Propagation: A double-spend attempt must outpace the propagation of the legitimate transaction to be included in a block first.

4. Bitcoin Script (Smart Contract Language)

A simple, stack-based, Turing-incomplete scripting language used to lock (encumber) and unlock (spend) transaction outputs.

• Purpose: Defines the conditions that must be met to spend a UTXO. Most common is Pay-to-Public-Key-Hash (P2PKH).

• Instruction Set: Includes operations like OP_DUP, OP_HASH160, OP_EQUALVERIFY, OP_CHECKSIG.

• Execution: When a transaction tries to spend an output, the locking script (from the output) and unlocking script (from the input) are concatenated and executed. If the final stack state is TRUE, the spend is authorized.

• Limitations:

  • No loops: Prevents infinite execution (Denial-of-Service).

  • Limited operations: No complex state or logic beyond basic cryptographic checks.

  • No native data storage: Cannot maintain complex state between transactions.

[!TIP] Exam Focus: Contrast Bitcoin Script's simplicity/limitations with Ethereum's Turing-complete Solidity.

C. Consensus Mechanisms

1. Proof of Work (PoW)

A consensus mechanism where miners compete to solve a computationally difficult but easily verifiable puzzle.

HashCash & Bitcoin PoW:

• Goal: Find a nonce such that: Hash(Block_Header) < Target

• The Target is a number representing difficulty. The hash must have a certain number of leading zeros.

• Miners brute-force the nonce. The first to find a valid hash "wins" the right to propose the next block and receives the block reward + transaction fees.

• Security: An attacker needs >50% of the total network hash power (51% attack) to consistently outpace honest miners.

Mining Process:

1. Collect pending transactions into a candidate block.

2. Build the block header (including Merkle root, previous hash).

3. Iterate the nonce (and extra nonce in coinbase) to find a hash below the target.

4. Broadcast the valid block to the network.

Types of Mining:

• Solo Mining: Individual miner.

• Pool Mining: Miners combine hash power; rewards split proportionally.

Attacks on PoW:

• 51% Attack: Attacker controls majority hash power. Can:

  • Double Spend: Send coins, wait for confirmation, then secretly mine a longer chain that excludes that transaction.

  • Censor Transactions: Refuse to include certain transactions.

  • Earn Rewards: Still receive block rewards on their chain.

• Monopoly Problem: Mining centralization due to economies of scale and specialized hardware (ASICs), leading to pool dominance.

2. Proof of Elapsed Time (PoET)

A lottery-based consensus algorithm for permissioned blockchains (like Hyperledger Sawtooth). It uses trusted execution environments (TEEs, e.g., Intel SGX).

Algorithm & Working:

1. Each validator requests a random wait time from its TEE.

2. The TEE (a secure enclave) confidentially generates a random wait time and signs it.

3. The validator with the shortest wait time is elected leader for the next block.

4. The leader proposes and commits the block.

5. Other validators verify the leader's TEE-signed wait time was valid and shortest.

Use Cases: Permissioned enterprise blockchains where participants are known and hardware-based trust is acceptable. More energy-efficient than PoW.

3. Raft Consensus Algorithm

A leader-based consensus algorithm for permissioned (crash-fault tolerant) systems. Prioritizes understandability and manageability.

Key Steps:

1. Leader Election: Nodes start as followers. If no leader heartbeat within timeout, a follower becomes a candidate, votes for itself, and requests votes. Candidate with majority votes becomes leader.

2. Log Replication: Leader accepts client requests, appends entry to its log, and replicates to followers via AppendEntries RPC. Once replicated on a majority, the entry is committed and applied to state machine. Leader notifies followers of commit.

3. Safety: Raft guarantees that if a log entry is committed in one term, it will appear in the logs of all future leaders (elected by majority).

Fault Tolerance: Can tolerate f crash failures in a cluster of 2f+1 nodes.

4. Byzantine Fault Tolerance (BFT)

Consensus in environments where nodes may fail arbitrarily (Byzantine failures: lying, crashing, arbitrary behavior).

Lamport-Shostak-Pease (LSB) Algorithm (The Oral Messages Algorithm):

• Scenario: A general must send a consistent attack/retreat order to n lieutenants, with up to t traitors (including possibly the general).

• Recursive Solution: The general sends his order to each lieutenant. Each lieutenant then acts as a "general" and forwards the received order to all other lieutenants (minus the sender). This recursion continues for t+1 levels.

• Majority Rule: After collecting all messages at level t+1, each lieutenant uses a majority function on the received values to decide.

• Requirement: Needs n > 3t to reach consensus in synchronous networks. For asynchronous, requires n > 3t and additional mechanisms (e.g., PBFT).

Distributed Consensus in Closed Environments: Used in permissioned blockchains (e.g., Hyperledger Fabric's ordering service can use BFT protocols like PBFT) where node identities are known and the system is designed to tolerate malicious (Byzantine) nodes.

[!TIP] Exam Focus: Contrast Raft (CFT, leader-based, permissioned) with BFT (handles malicious nodes, often more complex, e.g., PBFT). Know the n > 3t requirement.

5. Consensus in Bitcoin (Step-by-Step)

1. Transaction Broadcast: User signs and broadcasts transaction to P2P network.

2. Validation: Nodes validate (signature, UTXO existence, no double-spend). Valid transactions enter the mempool.

3. Block Creation: Miners select transactions from mempool, build a candidate block (with coinbase), and begin PoW on the block header.

4. PoW Competition: Miners iterate the nonce to find a hash below the current network difficulty target.

5. Block Propagation: Winning miner broadcasts the new block.

6. Block Validation: Other nodes verify: PoW is valid, all transactions in block are valid (and not double-spent), block timestamp is reasonable, block builds on the current tip of the longest valid chain.

7. Chain Selection: If valid, nodes add the block to their local chain. If two blocks are found simultaneously (temporary fork), nodes work on the first one received. The longest valid chain (with most cumulative PoW) is adopted as canonical. The other block's transactions return to the mempool.

8. Miner Role: Proposer of new blocks, enforcer of consensus rules, recipient of block reward. Incentivized by reward and fees.

6. Consensus Protocols for Permissioned Blockchains

Permissioned blockchains have known, vetted participants. Consensus is often faster and more efficient than PoW.

• Raft: (See section C.3 above). Leader-based, crash-fault tolerant. Simple, fast.

• PBFT (Practical BFT): State machine replication. Nodes communicate in rounds (pre-prepare, prepare, commit). Requires n > 3t. More message overhead than Raft but tolerates malicious nodes.

• SBFT (Simplified BFT): Optimized version of PBFT.

• Tendermint: BFT consensus with a rotating proposer. Used in Cosmos SDK.

• Avalanche Consensus: A family of protocols (Snowman, etc.) based on repeated random subsampling and metastability. Very high throughput, probabilistic finality.

D. Smart Contracts

1. Definition & Essential Characteristics

A smart contract is a self-executing program stored on a blockchain that automatically enforces the terms of an agreement when predefined conditions are met.

Essential Characteristics:

• Self-Executing: Runs automatically without intermediary.

• Immutable: Once deployed, code cannot be changed (unless upgradeability is built-in).

• Deterministic: Same inputs always produce same outputs on all nodes.

• Decentralized: Stored and executed across the network.

• Trustless: Parties do not need to trust each other, only the code and network.

• Stateful: Can store and modify state on the blockchain.

• Triggerable: Execution is triggered by transactions or events.

2. Smart Contracts on Bitcoin (Bitcoin Script)

• Process: Written in Bitcoin Script (stack-based, limited). The script logic (locking/unlocking scripts) is embedded directly in the transaction outputs.

• Limitations: Turing-incomplete, no loops, no complex state, no access to external data (oracles needed), very limited computational capability. Primarily used for simple payment conditions (multisig, timelocks).

3. Smart Contracts on Ethereum

• Writing Process:

  1. Write contract logic in Solidity (or Vyper, Yul).

  2. Compile Solidity to Ethereum Virtual Machine (EVM) bytecode.

  3. Deploy bytecode via a special transaction (no destination address). Deployment creates a contract address.

  4. Interact by sending transactions to the contract address with input data specifying the function to call.

• EVM: A Turing-complete, sandboxed, stack-based virtual machine. Every full node executes all contract code to reach consensus on state changes.

• Gas: Execution fee paid in ETH to prevent infinite loops and compensate for computation/storage.

4. Smart Contracts on Hyperledger Fabric

• Chaincode: The term for smart contracts in Fabric. Can be written in Go, Java, JavaScript.

• Writing & Deployment Process:

  1. Write chaincode (business logic) as a program.

  2. Package chaincode into a deployment spec.

  3. Install the chaincode package on endorsing peers.

  4. Instantiate (or upgrade) the chaincode on a channel, specifying the endorsement policy.

  5. Invoke chaincode functions via a transaction proposal sent to endorsing peers.

• Execution Model: Execute-Order-Validate architecture.

  • Execute: Endorsing peers simulate the transaction (using chaincode) to produce a read-write set and endorsement signature. No state change yet.

  • Order: Ordering service (e.g., Raft, BFT) sequences endorsed transactions into a block.

  • Validate: All peers validate the block. Each transaction is checked against its endorsement policy and the world state. Only valid transactions update the world state.

[!TIP] Exam Focus: Know the architectural difference: Ethereum (EVM on all nodes, global state) vs Fabric (chaincode on endorsing peers, channel-based private state, execute-order-validate).

E. Blockchain Platforms & Types

1. Public vs Private Blockchains

2. Permissioned Blockchains

Blockchains where participant identities are known and access is controlled by a central authority or consortium.

Design Issues:

• Identity Management & MSP: How to issue, revoke, and manage cryptographic identities (Membership Service Provider).

• Access Control: Defining who can read/write to the ledger/channels.

• Consensus Choice: Selecting an appropriate, efficient consensus algorithm (Raft, BFT) for known participants.

• Privacy & Confidentiality: Using channels, private data collections, or zero-knowledge proofs to hide transaction details from non-participants.

• Governance: Rules for network upgrades, membership changes, dispute resolution.

3. Hyperledger Fabric

A modular, permissioned blockchain framework for enterprise solutions.

Architecture:

DiagramCANVAS: Draw three main components: 1) Peers (Endorsing & Committing), 2) Ordering Service (Raft/BFT), 3) Client Application. Show a "Channel" connecting a subset of Peers and the Ordering Service. Label "Ledger" (World State + Blockchain) inside each Peer. Show flow: Client -> Proposal -> Endorsing Peers -> Ordering Service -> Block -> All Peers (Validate/Commit).

• Peers: Host the ledger and chaincode. Endorsing peers simulate transactions; committing peers validate and commit.

• Ordering Service: Orders endorsed transactions into blocks (does not process chaincode). Decoupled from peers.

• Channels: Private subnets of communication between specific peers and the ordering service. Ledger data is isolated per channel.

• Membership Service Provider (MSP): Manages identities (certificates from a CA) and defines who is a valid member of the network/channel.

Identities and Policies:

• Identities: X.509 digital certificates issued by a CA. Used for authentication and signing.

• Policies:

  • Endorsement Policy: Specifies which peers (by role or org) must endorse a transaction for it to be considered valid (e.g., AND('Org1.peer', 'Org2.peer')).

  • Validation Policy: (Usually same as endorsement). Checked during validation phase.

  • Channel Policies: For creating/updating channels.

  • Lifecycle Management Policy: For chaincode deployment.

Industry Use Cases:

• Supply Chain: Traceability of goods (food, pharmaceuticals), provenance verification.

• Finance: Trade finance, syndicated loans, KYC/AML sharing.

• Healthcare: Secure patient data sharing across providers, pharmaceutical track-and-trace.

• Insurance: Claims processing, parametric insurance.

4. Ripple and Corda

F. Blockchain Applications

1. Mortgage Process

• Traditional Process: Fragmented, paper-heavy. Involves borrower, lender, title company, appraiser, escrow, etc. Manual verification leads to delays (30-45 days), fraud risk, and high costs.

• Blockchain-Based Mortgage:

  • Shared, Immutable Ledger: All parties (borrower, lender, title, etc.) access a single source of truth for documents (loan application, appraisal, title deed, tax records).

  • Smart Contracts: Automate workflow. E.g., release funds to seller automatically upon verification of title transfer and signed closing documents.

  • Benefits: Dramatically reduced processing time (days), lower costs (eliminate intermediaries/reconciliation), enhanced security (tamper-proof records), improved transparency, reduced fraud.

2. Supply Chain Finance

• Improvements: Blockchain creates a verifiable, tamper-proof record of the entire supply chain (from raw material to consumer).

  • Transparency: All authorized participants (supplier, manufacturer, shipper, retailer) see the same real-time data on location, condition, ownership.

  • Efficiency: Automates processes (payments upon delivery verification via IoT/smart contracts), reduces paperwork and disputes.

  • Financing: Enables invoice financing based on verifiable, on-chain purchase orders and delivery receipts. Lenders can trust the data, offering better rates to SMEs.

  • Provenance: Combats counterfeiting by providing an immutable history of a product's journey.

3. Cross-Border Payments

• Enterprise Application: Banks and corporates use blockchain (e.g., RippleNet) for international money transfers.

• Challenges Solved:

  • Speed: Traditional SWIFT takes 2-5 days. Blockchain can settle in seconds/minutes.

  • Cost: Eliminates multiple intermediary banks and their fees. Lower FX costs.

  • Transparency & Tracking: Real-time tracking of payment status across the network.

  • Certainty: Pre-authorization of funds (using crypto assets like XRP as bridge currency) eliminates float and settlement risk.

4. Trade Finance

• Blockchain-Enabled Trade: Digitizes and automates the trade finance lifecycle (letters of credit, bills of lading, invoices).

• Documentation: All trade documents (LC, invoice, bill of lading, certificate of origin) are digitized and hashed onto the blockchain. Creates a single, shared version.

• Trust & Automation: Smart contracts automatically trigger payments when pre-agreed conditions (e.g., "Bill of Lading received and verified") are met by the on-chain data.

• Benefits: Reduces processing time from weeks to days/hours, lowers fraud (documents are tamper-proof), reduces administrative costs, improves liquidity for SMEs.

5. Identity Management Systems

• Decentralized Identity (DID): Users own and control their identity data, stored in a personal wallet, not in centralized databases.

• Self-Sovereign Identity (SSI): The ultimate form of DID. Individuals create their own identifiers, control which attributes (e.g., age, degree) are shared, and with whom.

• How it Works:

  1. Issuer (university, government) signs a credential (e.g., degree certificate) and gives it to the user.

  2. User stores signed credential in their digital wallet.

  3. When a verifier (employer) requests proof of degree, user presents a zero-knowledge proof (or selective disclosure) proving they have a valid credential from that issuer without revealing unnecessary data.

  4. Verifier checks the issuer's public key (on-chain) to validate the signature.

• Benefits: Privacy, user control, reduced identity theft, no single point of failure, portable identity across services.

II. PARALLEL COMPUTING

A. Fundamental Concepts & Distinctions

1. Parallelism vs Pipelining

• Parallelism: Simultaneous execution of multiple tasks or parts of a task on multiple processing units. Increases throughput by doing more work at the same time. (e.g., 4-core CPU running 4 threads).

• Pipelining: Overlapped execution of sequential tasks on a single processor by dividing it into stages. Increases throughput by finishing an instruction every cycle after pipeline fill. (e.g., 5-stage CPU pipeline: Fetch, Decode, Execute, Memory, Writeback). It is a form of temporal parallelism.

[!TIP] Exam Focus: Parallelism uses spatial resources (more units); pipelining uses temporal overlap on one unit.

2. Serial vs Parallel Processing

• Serial Processing: One instruction or task is executed completely before the next one begins. Single processor.

• Parallel Processing: Multiple instructions or tasks are executed concurrently on multiple processors/cores. Requires problem decomposition.

3. Control Flow Computers vs Data Flow Computers

4. Uniprocessor Systems vs Multiprocessor Systems

• Uniprocessor: Single CPU. Uses pipelining, superscalar execution, caching for performance. Limited by instruction-level parallelism (ILP).

• Multiprocessor (Parallel System): Two or more CPUs/cores sharing memory and/or I/O. Exploits thread-level parallelism (TLP) or process-level parallelism. Requires parallel programming models, synchronization, and deals with coherence.

B. Parallel Architectures

1. MIMD Multiprocessors

MIMD (Multiple Instruction, Multiple Data): Multiple independent processors, each executing its own instruction stream on its own data. Most common parallel architecture.

Characteristics distinguishing from multiple computer systems/networks:

1. Shared Memory (Typically): Processors communicate via shared global memory (UMA or NUMA), not just message passing. This enables faster communication but requires cache coherence.

2. Tightly Coupled: Processors are connected via a high-speed bus or interconnect (e.g., Intel UPI, AMD Infinity Fabric), with low latency and high bandwidth.

3. Single OS Image (Often): Runs a single instance of an OS that manages all processors and resources (SMP - Symmetric Multiprocessing). In clusters, each node runs its own OS.

4. Coherence Hardware: Hardware-based cache coherence protocols (snooping, directory) are essential to maintain a consistent view of shared memory.

5. Single System: Programmed as a single system (using threads, OpenMP), not as separate networked programs (using MPI).

2. Modern GPU Architecture

A GPU (Graphics Processing Unit) is a massively parallel processor designed for throughput-oriented workloads (graphics, AI, scientific computing).

Key Components:

• Streaming Multiprocessors (SMs) / Compute Units (CUs): The core building blocks. Each SM contains:

  • CUDA Cores / Stream Processors: Simple, integer/FP units.

  • Warp Schedulers: Issue instructions to groups of 32 threads (warps).

  • Registers: Per-thread register file (large).

  • Shared Memory / L1 Cache: Very fast, software-managed scratchpad memory shared by threads in a block.

  • Texture Units, RT Cores, Tensor Cores (specialized).

• Global Memory (DRAM): Large, high-bandwidth (HBM/GDDR), high-latency memory shared by all SMs.

• Memory Controllers & Interconnect: Manage access to global memory.

Execution Model (SIMT - Single Instruction, Multiple Threads):

• Threads are grouped into blocks, which are grouped into grids.

• Threads in a warp execute the same instruction simultaneously on different data (SIMD-like). Divergent branches (warps) cause serialization.

Applications:

• Graphics Rendering: Pixel/vertex shading.

• AI/ML Training & Inference: Matrix operations (Tensor Cores), neural networks.

• Scientific Computing: Molecular dynamics, climate modeling (data-parallel).

• Cryptocurrency Mining: Hash computations.

• Video Encoding/Decoding.

3. Architectural Characteristics of Future Systems

• Exascale: Systems capable of >10¹⁸ FLOPS. Challenges: power consumption, reliability, memory bandwidth wall.

• Heterogeneity: Integration of diverse compute elements (CPUs, GPUs, FPGAs, ASICs, AI accelerators) on a single package/chip (e.g., AMD APU, Intel Foveros).

• Memory Hierarchy: Deep, complex hierarchies. Focus on high-bandwidth memory (HBM, HMC) near processors, non-volatile memory (NVM) as persistent storage/memory, and memory-centric computing (processing-in-memory).

• Interconnect: Faster, more scalable networks (e.g., silicon photonics, 3D stacking).

• Energy Efficiency: Performance-per-watt is a primary design constraint.

• Resilience: Increased soft error rates require hardware/software resilience techniques.

C. Memory Systems & Cache Coherence

1. Cache Design Issues

Disadvantages of Virtual Address Caches:

• Alias Problem: Same physical memory location can have multiple virtual addresses (from different processes). If cache is indexed by virtual address, the same physical line could be cached in multiple places (incoherence).

• TLB Miss Penalty: On a TLB miss, the virtual-to-physical translation must be fetched from page table, stalling cache access.

• Protection & Consistency: Hardware must check permissions on every access, more complex with virtual addresses.

• Solution: Most modern systems use physically indexed, physically tagged (PIPT) caches. The virtual address is first translated by the TLB to a physical address, which is then used to index/tag the cache. This avoids aliases but adds TLB lookup latency. Some use virtually indexed, physically tagged (VIPT) caches to overlap translation and indexing.

2. Cache Architectures

• Centralized Shared Caches: A single, large cache (L3) shared by all processor cores. Simplifies coherence (single point), but can be a bottleneck and has higher access latency for distant cores.

• Distributed Shared Caches: Each core or cluster has its own local cache (L2/L3). The shared memory is distributed. Requires a coherence protocol to maintain consistency across these distributed caches. Lower average latency, but more complex coherence.

3. Cache Coherence Protocols

Ensures that multiple cached copies of the same memory block are kept consistent.

• Snooping-Based (Bus-Based Systems):

  • All caches monitor (snoop) a shared broadcast medium (bus).

  • On a read/write, the cache controller checks if it has a copy and takes action (invalidate, flush) based on the transaction.

  • Protocols: Write-Invalidate (MSI, MESI), Write-Update (Firefly).

  • Advantage: Simple, fast for small systems.

  • Disadvantage: Does not scale (bus saturation).

• Directory-Based (Scalable Systems):

  • A central or distributed directory tracks the state (shared, exclusive, etc.) and location (which caches have a copy) of each cache line.

  • On an access, the request is sent to the directory, which coordinates the necessary invalidations/updates.

  • Advantage: Scales to large processor counts (no broadcast storm).

  • Disadvantage: Higher latency for directory lookup, directory storage/access overhead.

4. Multicache Coherence Problem & Solutions

Problem: In a system with multiple private caches, a write by one processor to a cached location must be made visible to other caches that have a copy, to prevent stale reads.

Solutions & Protocols:

• Write-Through + Invalidate: Writes go to both cache and main memory. Other caches are invalidated via snoop/directory. Simple but high write traffic.

• Write-Back + Invalidate (Most Common): Writes only update the cache, marking it dirty. On a write, other caches' copies are invalidated. Dirty data is written back to memory when the line is evicted. Reduces memory traffic.

• Write-Update (Write-Through Broadcast): Writes update the local cache and broadcast the new data to all other caches that have a copy (update their data). No invalidates. Can reduce subsequent read misses but increases write traffic.

• State Transition Protocols: Define states for a cache line in each cache and the main memory.

  • MSI: Modified, Shared, Invalid.

  • MESI (most common): Modified, Exclusive, Shared, Invalid. Exclusive state (clean copy only in this cache) allows local writes without broadcast.

  • MOESI: Modified, Owner, Exclusive, Shared, Invalid. Owner state (dirty, shared) allows one cache to supply data to others without memory access (snoop response).

[!TIP] Exam Focus: Be able to draw the MESI state transition diagram and explain the meaning of each state and the actions (Read Miss, Write Hit, etc.) that cause transitions.

D. Parallel Programming Models

1. Four Categories of Parallelism

• Data Parallelism: Same operation applied to multiple data elements simultaneously. (e.g., vector addition, image processing). Best for SIMD/GPU.

• Task Parallelism: Different tasks (functions) executed concurrently on different data. (e.g., web server handling multiple requests). Best for MIMD CPUs.

• Pipeline Parallelism: Task broken into a sequence of stages, where different data items are processed concurrently at different stages. (e.g., CPU instruction pipeline, graphics rendering pipeline).

• Hybrid Parallelism: Combination of the above (e.g., task parallelism with data parallelism within tasks).

2. Steps to Design Parallel Programs

1. Decomposition: Break the problem into smaller, concurrent tasks (functional or data decomposition).

2. Mapping: Assign tasks to processing elements (threads, processes, cores). Consider load balancing and data locality.

3. Orchestration: Manage the interaction and synchronization between tasks (communication, coordination, ordering).

4. Execution: Run the parallel program on the target hardware.

5. Evaluation: Measure performance (speedup, efficiency), identify bottlenecks (Amdahl's Law), and optimize.

3. Distributed-Memory Programming with MPI

MPI (Message Passing Interface): Standard for programming distributed-memory systems (clusters, HPC).

• Point-to-Point Communication:

  • Blocking: MPI_Send, MPI_Recv. Send may block until receive posted (or buffer available). Simple but can cause deadlock if not ordered carefully.

  • Non-blocking: MPI_Isend, MPI_Irecv. Returns immediately. Requires MPI_Wait or MPI_Test to complete. Allows computation/communication overlap.

• Collective Communication: Involves a group of processes.

  • MPI_Bcast: Broadcast from root to all.

  • MPI_Scatter / MPI_Gather: Distribute/collect chunks of data from root.

  • MPI_Reduce / MPI_Allreduce: Apply operation (sum, max) and distribute result.

  • MPI_Barrier: Synchronize all processes in a communicator.

4. Thread Management

• Creation: pthread_create (POSIX), std::thread (C++11), thread pools.

• Synchronization Primitives:

  • Mutex/Lock: Mutual exclusion for critical sections.

  • Semaphore: Counting mechanism for resource access.

  • Condition Variable: Block threads until a condition is true.

  • Barrier: Wait for all threads to reach a point.

• Scheduling: OS kernel schedules threads onto cores. Can be preemptive or cooperative. Affinity (binding thread to core) can improve cache locality.

5. Parallel Data Management

• Distribution: How to partition data across memories/processors.

  • Block/Striped: Distribute contiguous chunks.

  • Cyclic: Distribute elements in round-robin.

  • Block-Cyclic: Hybrid.

• Replication: Copy data to multiple locations for faster read access or fault tolerance. Increases storage cost, requires coherence.

• Consistency: Ensuring all processors see a consistent view of shared data. Managed by hardware (cache coherence) or software (locks, barriers, memory models like C++11/Java memory model).

6. I/O Handling in Parallel Programming Languages

• Challenges:

  • Multiple Processes/Threads writing to same file: Need coordination (file locking, collective I/O) to avoid corruption/interleaving.

  • Performance: Many small I/O operations are slow. Need to aggregate requests.

  • Parallel File Systems: Required (e.g., Lustre, GPFS, HDFS) to provide high aggregate bandwidth to many nodes.

• Strategies:

  • Collective I/O: A subset of processes (e.g., rank 0) performs all I/O for the group, aggregating data from others.

  • Two-Phase I/O: First phase: data reshuffling to I/O aggregators. Second phase: aggregators write to file.

  • POSIX I/O with File Locking: Simple but poor performance.

  • MPI-IO: Part of MPI standard. Provides portable, high-performance I/O with features like collective buffering, non-contiguous access.

E. Performance & Optimization

1. Performance Metrics of Parallel Systems

• Speedup (S): S(p) = T(1) / T(p)

  • T(1): Execution time on 1 processor.

  • T(p): Execution time on p processors.

• Efficiency (E): E(p) = S(p) / p = T(1) / (p * T(p)). Measures fraction of time processors are usefully employed.

• Scalability: How speedup increases with p. Strong Scaling: Fixed problem size, increase p. Weak Scaling: Problem size increases proportionally with p.

• Cost: C(p) = p * T(p). Optimal if constant (linear speedup).

Amdahl's Law: S_max(p) = 1 / ( (1 - P) + P/p )

• P: Parallelizable fraction of the program.

• 1-P: Serial fraction.

• Limits speedup. Even with infinite processors, S_max(∞) = 1 / (1-P). To achieve high speedup, (1-P) must be near zero.

Gustafson's Law (Scaled Speedup): S'(p) = P + (1-P)/p

• Assumes problem size scales with p. More optimistic, argues speedup can be linear if parallel fraction dominates.

2. Pipeline Speedup Proof

Consider a k-stage linear pipeline.

• Non-pipelined (serial) time for n tasks: T_serial = n * t (where t is time per task/stage).

• Pipelined time: First task takes k*t to fill pipeline. Each subsequent task completes every t (cycle time = max stage delay). So, T_pipe = k*t + (n-1)*t = (k + n - 1) * t.

• Speedup: S = T_serial / T_pipe = (n * t) / ((k + n - 1) * t) = n / (k + n - 1)

• As n → ∞ (large number of tasks), S → n / n = 1? Wait, let's re-evaluate.

  • Actually, for large n, S ≈ n / n = 1? That's wrong. Let's derive properly.

  • S = n / (k + n - 1). Divide numerator and denominator by n: S = 1 / (k/n + 1 - 1/n).

  • As n → ∞, k/n → 0, 1/n → 0, so S → 1 / (0 + 1 - 0) = 1. This suggests speedup goes to 1, which is incorrect for pipelines.

  • Mistake: The non-pipelined time for n tasks is n * (k*t) if each task goes through all k stages serially? No, in a non-pipelined processor, each task still goes through k stages, but one after the other. So T_serial = n * (k * t_stage)? But in a pipelined processor, the cycle time t is determined by the slowest stage. Let t_i be delay of stage i. Then t = max(t_i). The non-pipelined time for one task is Σ t_i. Let T_task = Σ t_i.

  • Correct derivation:

    • Non-pipelined: T_serial = n * T_task = n * Σ t_i

    • Pipelined: Cycle time t = max(t_i). Time for n tasks: T_pipe = k*t + (n-1)*t = (k + n - 1)*t

    • Speedup: S = T_serial / T_pipe = (n * Σ t_i) / ((k + n - 1) * t)

    • For large n, S ≈ (n * Σ t_i) / (n * t) = (Σ t_i) / t

    • Since t = max(t_i), Σ t_i / t ≥ k (if all stages equal, Σ t_i = k*t, so S_max = k).

    • Therefore, the maximum possible speedup is k (when all stages are perfectly balanced, t_i = t for all i).

    • \boxed{S_{\text{max}} = k}

3. Transaction vs Transactional Memory

• Transaction (DBMS): A sequence of operations (read/write) on a database that is treated as a single logical unit. Properties: ACID (Atomicity, Consistency, Isolation, Durability). Managed by a DBMS.

• Transactional Memory (TM): A concurrency control mechanism for shared memory in parallel programming (like locks, but optimistic). A transaction is a block of code that executes speculatively on shared data. At commit, it checks for conflicts with other transactions. If conflict, aborts and retries.

  • Hardware TM (HTM): Supported by CPU (e.g., Intel TSX). Uses cache coherence to detect conflicts. Fast, but limited by cache size/conflict types.

  • Software TM (STM): Implemented in software libraries using versioning and locking. More flexible, slower.

  • Goal: Simplify parallel programming by avoiding explicit locks, reducing deadlocks.

4. Fusing Map and Scan Operations

• Map: Applies a function f to each element of a collection, producing a new collection of same size. [a,b,c] → [f(a), f(b), f(c)]. Independent operations.

• Scan (Prefix Sum): Produces a cumulative result. [a,b,c] → [a, a+b, a+b+c]. Sequentially dependent (each output depends on previous).

• Fusing: Combining map and scan into a single kernel/pass to avoid intermediate storage and improve data locality.

  • Example: Compute prefix sums of squares: scan(λ(x,y) x+y, map(λx x*x, A)).

  • Fused Implementation: In one pass, compute square and accumulate in one register. Reduces memory traffic (read/write array twice vs once). Crucial for GPU/vectorized performance.

  • Benefit: Lower memory bandwidth usage, better cache utilization, reduced latency.

[!TIP] Exam Focus: Know the definitions of map (independent) and scan (dependent prefix), and the performance benefit of fusing (reduced memory traffic).