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

UNIT 4: Advanced Computing Technologies (Blockchain & Parallel Computing)

I. Blockchain Technology

A. Fundamental Concepts & Cryptography

Block Structure and Components

A block consists of a header and a body (list of transactions).

• Header: Contains metadata: Version, Previous Block Hash (link to chain), Merkle Root (hash of all transactions), Timestamp, Difficulty Target, Nonce.

• Body: Contains the transaction count and the transaction data itself.

[!TIP] The Merkle Root in the header allows efficient verification of any transaction without needing the entire block.

Cryptographic Hash Functions

A hash function $H$ maps input data of any size to a fixed-size output (hash/digest).

• Properties:

  1. Deterministic: Same input → same hash.

  2. Quick to Compute: Easy to compute $H(x)$.

  3. Pre-image Resistant: Given hash $h$, infeasible to find $x$ such that $$\displaystyle H(x)=h $$.

  4. Avalanche Effect: Tiny change in input drastically changes output.

  5. Collision Resistant: Infeasible to find two distinct inputs $x \neq y$ with $$\displaystyle H(x)=H(y) $$.

• Role in Blockchain: Links blocks (each block header includes previous block's hash), creates transaction identifiers, forms Merkle trees.

• Examples: SHA-256 (Bitcoin, Bitcoin Script), Keccak-256 (Ethereum).

Merkle Trees (Hash Trees)

A binary tree where each non-leaf node is the hash of its child nodes.

• Structure: Transactions are hashed → paired and hashed → results paired and hashed recursively until a single Merkle Root.

• Construction: Requires $n-1$ hash operations for $n$ transactions.

• Importance & Usage in Verification:

  • Enables Simple Payment Verification (SPV): A lightweight node can verify a transaction's inclusion by obtaining only the Merkle Path (hashes from the transaction leaf to the root) and the root from the block header, without downloading all transactions.

  • Provides data integrity: any change in a transaction changes all hashes up to the root.

  • Efficient and scalable proof of membership.

Public Key Cryptography (PKI) & Digital Signatures

• Basics: Uses a key pair: Private Key (secret) and Public Key (shared). Data encrypted with public key can only be decrypted by private key, and vice-versa for signatures.

• Digital Signature Process:

  1. Signing: Sender hashes the message, then encrypts the hash with their private key → signature.

  2. Verification: Receiver decrypts the signature with sender's public key to get the hash, hashes the received message independently, and compares the two hashes.

• Role in Blockchain: Provides authentication (proves ownership of funds/identity) and non-repudiation (sender cannot deny sending).

Double Spending Problem & Prevention

• Problem: The risk that a single digital token/coin is spent more than once because digital data can be copied.

• Prevention Mechanisms:

  1. Global Consensus: All nodes agree on a single, canonical history of transactions. Once a transaction is confirmed in a block deep enough in the chain (e.g., 6 confirmations in Bitcoin), it's practically irreversible.

  2. Timestamping & Chaining: Blocks are timestamped and cryptographically chained. Re-spending a confirmed transaction requires rewriting all subsequent blocks, which is computationally infeasible in PoW systems.

  3. Transaction Validation: Nodes validate every transaction: inputs must be unspent (UTXO model) or account balance sufficient (account model).

B. Blockchain Classifications & Design

Public vs Private Blockchains

Permissioned vs Permissionless

• Permissionless: No control over who can participate as a validator (miner/node). (e.g., Bitcoin).

• Permissioned: The network operator controls who can be a participant (node) and their roles (e.g., endorser, orderer in Fabric). This enables higher throughput and privacy.

Design Issues in Permissioned Blockchains

1. Access Control & Identity: Rigorous member enrollment and role definition (e.g., Fabric's Membership Service Provider - MSP).

2. Privacy & Confidentiality: Need to hide transaction details from non-participants. Solved via channels (Fabric) or confidential identities (Corda).

3. Scalability & Performance: Trade-off between decentralization, security, and scalability (the "blockchain trilemma"). Permissioned chains prioritize scalability via efficient consensus and limited nodes.

4. Consensus Choice: Must be efficient and final (no forks). Often BFT-style (PBFT) or leader-based (Raft).

C. Consensus Mechanisms

Proof of Work (PoW)

• Concept: Miners compete to solve a computationally difficult but easily verifiable puzzle (finding a nonce such that $$\displaystyle H(\text{block header}) < \text{target} $$).

• HashCash: Early PoW algorithm for spam prevention. Requires partial hash inversion.

• Bitcoin PoW: Uses double SHA-256. The puzzle difficulty adjusts to maintain ~10 min block time.

• Mining Process:

  1. Collect transactions, build candidate block.

  2. Compute block header hash with varying nonce.

  3. If hash < target → block found, broadcast.

  4. Other nodes verify and extend the chain.

• Attacks:

  • 51% Attack: If an entity controls >50% of hash power, they can double-spend and censor transactions (but not steal funds).

  • Selfish Mining: Miners withhold found blocks to gain unfair advantage, reducing chain fairness.

  • Monopoly Problem: Mining centralization in large pools/pools, defeating decentralization.

Proof of Stake (PoS) & Alternatives

• PoS: Validator chosen to create next block based on amount of stake (coins) locked as collateral and often other factors (coin age). No heavy computation. More energy-efficient. (Ethereum 2.0).

• Proof of Elapsed Time (PoET): Uses trusted execution environment (TEE, e.g., Intel SGX) to randomly wait for a random time. The node with the shortest wait time wins. Fair and low-cost, but requires hardware trust.

Byzantine Fault Tolerance (BFT)

• Goal: Achieve consensus in a system where some nodes may be malicious/faulty (Byzantine faults), assuming <1/3 of nodes are faulty.

• Lamport-Shostak-Pease (Oral Messages) Algorithm: A theoretical algorithm for synchronous systems with a known leader (General). Requires $$\displaystyle n > 3f $$ nodes to tolerate $f$ traitors. Uses recursive message passing.

• Practical BFT (PBFT): State machine replication for asynchronous systems. Operates in view with a primary (leader). Requires $n \geq 3f+1$. Phases: Pre-Prepare, Prepare, Commit. Efficient for small, known node sets (permissioned).

Raft Consensus Algorithm

• Goal: Provide understandable consensus for replicated state machines, tolerating non-Byzantine (crash) failures.

• Mechanism:

  1. Leader Election: Nodes start as followers. If no heartbeat from leader within timeout → become candidate, request votes. Wins if majority votes → becomes leader.

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

• Safety: Guarantees that if a log entry is committed in one term, it will appear in all future leaders' logs at the same index.

Consensus in Bitcoin (Nakamoto Consensus)

1. Network: P2P network of nodes (full nodes, miners).

2. Transaction Propagation: Nodes validate and broadcast new transactions.

3. Block Propagation: Miners collect transactions into candidate blocks, perform PoW. Upon finding a valid block, they broadcast it.

4. Chain Selection Rule: Nodes always adopt the longest valid chain (most cumulative PoW). This is the Nakamoto Consensus.

5. Finality: Probabilistic. Deeper a block, lower chance of reversal. ~6 confirmations considered final.

Consensus Protocols for Permissioned Blockchains

• BFT-based: PBFT, Tendermint (BFT-PoS), HotStuff. Provide immediate finality, efficient for small groups.

• Leader-based Crash Fault Tolerant (CFT): Raft, Paxos. Simple, fast, but tolerate only crashes, not malicious nodes.

• Sieve: Used in Hyperledger Fabric's ordering service (Raft by default).

Distributed Consensus in Closed Environments

• Theoretical Foundations: Assumes a known, fixed set of participants (closed group). Models: Synchronous (known bound on message delay) vs Asynchronous (no bound, FLP impossibility).

• Key Results:

  • FLP Impossibility: In an asynchronous system with even one faulty node, deterministic consensus is impossible.

  • Solutions: Use randomization (e.g., PBFT works in partially synchronous systems), or assume synchrony/some bounded delay.

  • Trade-offs: Between fault tolerance (Byzantine vs crash), performance, and complexity.

D. Smart Contracts

Definition & Characteristics

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

• Essential Characteristics:

  • Self-Executing: Runs automatically upon trigger.

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

  • Deterministic: Same input → same output on all nodes.

  • Trustless: Executes without needing a central authority.

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

• Execution Model: Nodes (miners/validators) execute the contract code as part of transaction processing. Execution requires gas/fee. All nodes must reach same final state.

Bitcoin Script

• Stack-based, Forth-like, non-Turing complete language.

• Smart Contract Language of Bitcoin: Used to lock/unlock UTXOs. Scripts define spending conditions (e.g., OP_CHECKSIG for single-sig, OP_CHECKMULTISIG for multisig).

• Limitations: No loops, limited opcodes → cannot express complex logic. Primarily for simple payment conditions.

Ethereum Smart Contracts

• Writing Process: Code written in Solidity (or Vyper) → compiled to EVM bytecode → deployed to an Ethereum address.

• Solidity: Statically typed, high-level language. Contracts have functions, state variables, events.

• Ethereum Virtual Machine (EVM): The runtime environment. Every full node runs EVM to execute contract bytecode. Gas mechanism prevents infinite loops/DoS.

• State Transition: Execution changes the global state (account balances, contract storage). Transaction cost = gas used * gas price.

Hyperledger Fabric Smart Contracts (Chaincode)

• Chaincode: The business logic of an application, written in Go, Java, or JavaScript.

• Writing Process:

  1. Define chaincode structure (init, Invoke).

  2. Init for initialization.

  3. Invoke routes transaction proposals to specific functions (e.g., createAsset, transferAsset).

  4. Chaincode interacts with world state (key-value database, e.g., CouchDB) via GetState/PutState.

• Execution Model: Execute-Order-Validate architecture. Endorsing peers simulate transaction (execute chaincode) and produce read-write set. Ordering service orders transactions. Committing peers validate endorsement policy and apply to world state.

Smart Contract Development Steps & Lifecycle

1. Design: Define logic, state variables, functions, events.

2. Code: Write in chosen language (Solidity, Go).

3. Test: Rigorous local/network testing (e.g., Truffle, Fabric test network).

4. Deploy: Compile to bytecode, send deployment transaction (paying gas).

5. Invoke: Users send transactions to call contract functions.

6. Monitor & Maintain: Track events, state changes. For upgradeable contracts, use proxy patterns (Ethereum) or chaincode upgrade process (Fabric).

[!TIP] Security is paramount. Common vulnerabilities: reentrancy (Ethereum), integer overflows/underflows, access control flaws.

E. Blockchain Platforms & Architectures

Bitcoin Architecture

• P2P Network: Decentralized network of full nodes (store full chain) and SPV clients.

• Transaction Propagation: Nodes validate and flood valid transactions (via inv/getdata messages).

• Block Propagation: Miners broadcast new blocks via inv; nodes fetch block with getdata.

• Mining:

  • Solo Mining: Individual miner.

  • Pool Mining: Miners combine hash power; pool operator distributes rewards proportionally to work (shares).

Ethereum Architecture

• Account Model: Two types: Externally Owned Accounts (EOA) (controlled by private key), Contract Accounts (controlled by code). Each has nonce, balance, storageRoot, codeHash.

• Gas: Unit of computation. Each EVM operation has a gas cost. Prevents spam and infinite loops. Gas Used * Gas Price = Transaction Fee.

• EVM: Turing-complete, stack-based VM. Isolated from network/FS.

• State Transition Function: $$\displaystyle \sigma_{t+1} = \Upsilon(\sigma_t, \tau) $$ where $\Upsilon$ is the state transition function applying transaction $\tau$ to state $$\displaystyle \sigma_t $$ to produce $$\displaystyle \sigma_{t+1} $$.

Hyperledger Fabric Architecture

• Peers: Host chaincode and ledger. Endorsing Peers simulate transactions. Committing Peers validate and commit.

• Orderers: Form the ordering service (consensus). Sequence transactions into blocks, deliver to peers.

• Channels: Private subnets. Ledger data and chaincode execution are isolated per channel. Provides confidentiality.

• MSP (Membership Service Provider): Manages identities (X.509 certificates) and access control for organizations/peers/orderers.

• Consensus Service: Pluggable (Raft, Kafka, BFT-SMaRt). Separated from transaction execution/validation.

Ripple and Corda

Cross-Platform Comparison (Bitcoin, Ethereum, Hyperledger, Ripple, Corda)

F. Applications & Industry Use Cases

Blockchain in Mortgage

• Traditional Process: Paper-heavy, multiple intermediaries (lenders, brokers, title companies, insurers), slow (30-60 days), prone to fraud, high costs.

• Blockchain-Based Process:

  • Digitized Assets: Property title, deeds, liens as digital tokens/NFTs on a permissioned blockchain.

  • Smart Contracts: Automate steps: release funds upon title transfer, trigger insurance, manage escrow.

  • Shared Ledger: All parties (lender, borrower, title, insurer) access a single, immutable source of truth. Reduces fraud, accelerates closing (to days), cuts costs.

  • Example: A consortium bank using Hyperledger Fabric for mortgage origination and servicing.

Supply Chain Finance Improvements

• Transparency: All participants (supplier, manufacturer, buyer, financier) see same immutable record of goods movement and invoices.

• Efficiency: Automates invoice verification and payment via smart contracts (e.g., upon IoT sensor confirmation of delivery). Reduces manual reconciliation.

• Traceability: End-to-end provenance. Enables invoice financing where financiers can trust the authenticity of invoices on-chain, lowering risk and interest rates for SMEs.

• Example: We.Trade (European banks on Fabric) for trade finance.

Cross-Border Payments (Enterprise Applications)

• Challenges: High fees (correspondent banking), slow (2-5 days), lack of transparency, currency conversion costs.

• Blockchain Solutions (e.g., RippleNet):

  • On-Demand Liquidity (ODL): Use XRP as bridge currency to avoid pre-funded Nostro accounts.

  • Real-Time Settlement: Payments settle in seconds.

  • Reduced Cost: Lower fees vs traditional SWIFT.

  • Transparency: Track payment end-to-end.

• Enterprise Adoption: Banks and corporates use private/permissioned versions (e.g., Ripple's xCurrent) for compliance.

Blockchain-Enabled Trade

• Documentation: Digitize trade documents (Letters of Credit, Bills of Lading, Invoices) as verifiable digital assets on a blockchain network (e.g., we.trade, Marco Polo).

• Automation: Smart contracts automatically trigger actions: release payment when Bill of Lading is uploaded and verified, transfer title upon payment.

• Trust: All parties trust the single source of truth. Reduces fraud, disputes, and processing time from weeks to hours.

• Example: A buyer's bank and seller's bank on a shared Fabric channel issue and confirm an LC.

Identity Management Systems (Self-Sovereign Identity - SSI)

• Concept: Individuals own and control their digital identity, not a central authority.

• Components:

  • Decentralized Identifiers (DIDs): Unique identifiers anchored on blockchain, resolvable to DID Documents (public keys, service endpoints).

  • Verifiable Credentials (VCs): Digitally signed claims (e.g., passport, degree) issued by an authority. Holder stores them in a digital wallet.

  • Verification: Relying party requests proof. Holder presents zero-knowledge proof or signed VC. Verifier checks issuer's DID and signature on-chain.

• Benefits: Privacy (minimal disclosure), user control, reduced identity theft, portable reputation.

• Example: Sovrin network, uPort.

Hyperledger Fabric Industry Use Cases

• Healthcare: Secure sharing of patient records among hospitals, labs, insurers with patient consent. (e.g., change healthcare).

• Finance: Trade finance (we.trade), syndicated loans, KYC/AML verification networks (e.g., Digital Trade Chain).

• Supply Chain: Food traceability (IBM Food Trust), provenance of luxury goods, pharmaceutical supply chain.

• Government: Land registry, digital credentials (academic degrees, birth certificates).

G. Security & Network Operations

Attacks on Proof of Work

• Selfish Mining: A miner withholds a found block instead of broadcasting it, continuing to mine on the previous tip. When the public chain catches up, the selfish miner releases their withheld block, causing a fork where their chain becomes longer, wasting public chain's work. Requires >33% hash power to be profitable.

• Block Withholding: A mining pool participant finds a valid block but does not submit it to the pool, reducing pool's revenue. Often a disgruntled miner attack.

• 51% Attack: As described earlier. Enables double-spending and censorship.

Bitcoin P2P Network Operation

1. Node Discovery: New node connects to DNS seeds to get list of IP addresses. Then connects to a few of them, and learns about more peers via addr messages.

2. Message Propagation: Messages (tx, block, addr, inv) are flooded using a gossip protocol. A node sends inv (inventory) to peers for new objects. If peer doesn't have it, they request with getdata.

3. Transaction Processing: Nodes validate incoming transactions (signature, UTXO existence, no double-spend). Valid transactions are added to mempool and relayed.

Block Mining Process (Including Types)

1. Transaction Selection: Miner selects transactions from mempool, prioritizing higher fee rates. Creates a candidate block.

2. Block Assembly: Builds block header (including Merkle root of selected txs, previous block hash, timestamp, difficulty, nonce). May include coinbase transaction (block reward).

3. Proof-of-Work (PoW): Repeatedly hashes the block header with different nonce values until $$\displaystyle H(\text{header}) < \text{target} $$. This is the mining process.

4. Block Propagation: Upon finding a valid nonce, miner broadcasts the block.

5. Other Mining Types:

   • Proof-of-Stake (PoS): Validator chosen based on stake. No computation race. "Minting" instead of mining.

   • Proof-of-Space/Time: Uses hard drive space (e.g., Chia).

   • Proof-of-Authority (PoA): Validators are pre-approved, identified authorities. Used in testnets/private chains.

II. Parallel Computing

A. Core Concepts & Classifications

Parallelism vs Pipelining

Serial vs Parallel Processing

• Serial Processing: Instructions executed one after another on a single processor. $$\displaystyle T_s = \text{number of instructions} \times \text{CPI} \times \text{cycle time} $$.

• Parallel Processing: Multiple instructions executed concurrently on multiple processors. $$\displaystyle T_p $$ is execution time on $p$ processors.

• Speedup: $$\displaystyle S = \frac{T_s}{T_p} $$. Theoretical max $S \leq p$ (linear speedup). Limited by sequential portion of code.

Control Flow Computers vs Data Flow Computers

Uniprocessor Systems vs Multiprocessor Systems

MIMD Multiprocessors vs Multiple Computer Systems/Networks

• MIMD (Multiple Instruction, Multiple Data): Multiple independent processors, each executing different instructions on different data. Can be shared memory or distributed memory.

• Distinguishing Characteristics from Networks:

  1. Tightly-Coupled: Processors share a common physical memory space (or have very fast interconnect).

  2. Low Latency: Communication latency is low (nanoseconds to microseconds), often via shared bus or crossbar.

  3. Single System Image: OS presents a unified system; processes can directly address memory of other processors (in shared memory).

  4. Synchronization Primitives: Hardware support (atomic instructions, locks) for fast synchronization.

  5. Goal: Reduce execution time of a single large problem.

• Multiple Computer Systems (Clusters): Loosely coupled, connected by network (Ethernet, InfiniBand). Each node has its own OS and memory. Communication via message passing (MPI). Higher latency, but scalable to thousands of nodes.

Four Categories of Parallelism

1. Bit-Level Parallelism (ILP): Increasing word size (e.g., 64-bit vs 32-bit) to process more bits per instruction.

2. Instruction-Level Parallelism (ILP): Executing multiple instructions simultaneously within a processor (pipelining, superscalar, out-of-order execution).

3. Data Parallelism: Same operation applied to multiple data elements simultaneously (SIMD, vector processors, GPU cores).

4. Task Parallelism (Functional Parallelism): Different tasks (threads/processes) executed concurrently on different processors. May have different code.

Steps to Design a Parallel Program

1. Decomposition: Break the problem into smaller tasks that can execute concurrently.

   • Task Decomposition: Identify independent tasks.

   • Data Decomposition: Partition data (block, cyclic) and assign tasks to partitions.

2. Mapping: Assign tasks to processors/threads. Goal: balance load, minimize communication.

3. Orchestration (Synchronization & Communication): Manage interactions: synchronization (barriers, locks), communication (message passing, shared memory).

4. Evaluation: Analyze performance (speedup, efficiency), scalability, and correctness. Use profiling tools.

B. Pipelining

Linear Pipeline: Speedup Proof

Assume a $k$-stage pipeline. Each stage takes $\tau$ time (for simplicity, stages are balanced).

• Non-pipelined (Serial) Execution: To execute $n$ instructions, time $$\displaystyle T_s = n \times k\tau $$.

• Pipelined Execution: First instruction takes $k\tau$ to complete. After that, one instruction completes every $\tau$ (steady state). Total time $$\displaystyle T_p = k\tau + (n-1)\tau = (k + n - 1)\tau $$.

• Speedup:

$$S = \frac{T_s}{T_p} = \frac{n k \tau}{(k + n - 1)\tau} = \frac{nk}{k + n - 1}$$

As $n \to \infty$ (large number of instructions):

$$S_{max} = \lim_{n \to \infty} \frac{nk}{k + n - 1} = k$$

Therefore, a $k$-stage pipeline can be **at most $k$ times faster** than a non-pipelined processor.

[!TIP] This is an ideal speedup. Real speedup is less due to pipeline hazards, unbalanced stages, and startup/drain overhead.

Pipeline Hazards and Optimization Techniques

• Hazards: Situations that prevent next instruction from executing in next cycle.

  1. Structural Hazard: Resource conflict (e.g., two instructions need same memory port). Fix: Duplicate resources, stall.

  2. Data Hazard: Dependency between instructions (RAW, WAR, WAW). Fixes:

     • Forwarding/Bypassing: Route result from EX/MEM stage directly to next instruction's ALU input.

     • Stall (Bubble): Insert no-op if forwarding not possible (e.g., load-use).

  3. Control Hazard: Caused by branches/jumps. Fixes:

     • Stall until branch resolved.

     • Branch Prediction: Predict taken/not-taken, speculatively execute.

     • Delayed Branch: Execute instruction(s) in branch delay slot (obsolete).

• Optimization: Deep pipelining (more stages), superscalar (multiple pipelines), out-of-order execution, speculative execution.

C. Memory Systems & Cache Coherence

Cache Design: Virtual Address vs Physical Address Caches

• Virtual Address Cache (VAC): Cache indexed and tagged with virtual addresses. No TLB access needed on access → faster.

• Disadvantages of VAC:

  1. Alias Problem: Same physical address may have multiple virtual addresses (different processes) → cache lines duplicated.

  2. Protection & Consistency: Virtual address protection bits must be checked on every access; OS page table changes complicate coherence.

  3. Context Switch Overhead: Must flush cache on process switch (unless using ASIDs).

• Physical Address Cache (PAC): Indexed/tagged with physical addresses. Requires TLB translation first → slower, but avoids aliasing, simpler coherence. Virtually Indexed, Physically Tagged (VIPT) is a common compromise.

Shared Memory Architectures: Centralized vs Distributed Shared Caches

Cache Coherence Problem: Definition & Root Causes

• Definition: Ensuring that multiple cached copies of the same memory block are kept consistent when one processor writes to it.

• Root Causes in Multicore Systems:

  1. Shared writable data: Multiple caches may hold a copy.

  2. Write-back caches: Writes update only the local cache, not memory immediately.

  3. No global monitoring: Each cache operates independently.

  • Result: After a write by CPU A, CPU B may read stale value from its cache.

Cache Coherence Protocols: Snooping-Based vs Directory-Based

Multicache Coherence: Problem & Coping Methods

• Problem: As above, maintaining a single-writer/multiple-reader invariant across distributed caches.

• Suggested Methods:

  1. Write-Invalidate (e.g., MESI Protocol): On a write, invalidate all other cached copies. Subsequent reads must fetch from memory/owner. State Transitions: Modified (M), Exclusive (E), Shared (S), Invalid (I).

  2. Write-Update (Write-Broadcast): On a write, broadcast the new data to all other caches holding a copy. Keeps all copies up-to-date. More bus traffic but read misses reduced.

  3. Directory-Based: As above. Directory maintains state per line (e.g., Shared, Exclusive, Modified). On write, directory sends invalidate/update requests only to relevant caches.

  4. Timestamp-Based: Use timestamps to order writes, resolve conflicts.

  5. Hardware Primitives: Atomic instructions (Test-And-Set, Compare-And-Swap) for synchronization, but not full coherence.

D. Parallel Architectures

Modern GPU Architecture & Applications

• Architecture:

  • Streaming Multiprocessors (SMs): GPU is built from many SMs. Each SM has:

    • CUDA Cores / Stream Processors: Simple, in-order ALUs for massive data-parallel work.

    • Warp Scheduler: Executes groups of 32 threads (warp) in SIMT (Single Instruction, Multiple Thread) fashion. All threads in warp execute same instruction on different data.

    • Memory Hierarchy: Registers (per thread), Shared Memory (on-chip, SM-wide, programmer-managed), L1/L2 caches, Global Memory (off-chip DRAM).

  • High Memory Bandwidth: Wide memory bus (e.g., 384-bit), GDDR6/HBM.

• Applications (GPGPU):

  • AI/ML Training: Matrix operations, neural network kernels.

  • Scientific Computing: CFD, molecular dynamics.

  • Rendering & Graphics: Ray tracing, rasterization.

  • Cryptocurrency Mining: Hash computations (historically).

  • Video Encoding/Decoding.

Architectural Characteristics of Future Systems

1. Heterogeneity: Integration of diverse compute elements: CPU cores, GPUs, FPGAs, AI accelerators (TPUs, NPUs) on a package/chip.

2. Memory-Centric Computing: Moving processing near memory to overcome memory wall. Technologies: Processing-in-Memory (PIM), Near-Data Processing, HBM with compute.

3. Interconnect Focus: High-bandwidth, low-latency interconnects: CXL (Compute Express Link) for cache-coherent memory pooling, NVLink, advanced network-on-chip (NoC).

4. Domain-Specific Architectures (DSA): Specialized hardware for specific workloads (AI, graph processing).

5. Scale-out vs Scale-up: More cores per chip (scale-up) and more chips per system (scale-out) via chiplets and advanced packaging.

MIMD System Architectures: Shared Memory vs Distributed Memory

E. Programming Models & Languages

Distributed-Memory Programming with MPI

• Model: Processes with private memory communicate via explicit messages.

• Point-to-Point Communication:

  • Blocking: MPI_Send, MPI_Recv. May block until buffer safe to reuse.

  • Non-blocking: MPI_Isend, MPI_Irecv + MPI_Wait. Allows overlap of communication/computation.

• Collective Communication: Involves group of processes.

  • MPI_Bcast (broadcast), MPI_Scatter/MPI_Gather (distribute/collect), MPI_Reduce (sum/max/etc.), MPI_Allreduce.

• Typical Pattern: Initialize (MPI_Init), get rank/size, perform computation/communication, finalize (MPI_Finalize).

Transactional Memory vs Transactions

Thread Management

• Creation: OS threads (pthread_create), language threads (Java Thread), thread pools.

• Scheduling: OS scheduler assigns runnable threads to CPU cores. Can be preemptive or cooperative. Affinity (binding to core) can improve cache locality.

• Synchronization: Primitives to coordinate access to shared data.

  • Locks/Mutexes: Mutual exclusion. Can cause deadlock.

  • Semaphores: Counting mechanism for resource pools.

  • Condition Variables: Wait/signal for state changes.

  • Barriers: Synchronize all threads at a point.

• Thread Pools: Pre-created worker threads waiting for tasks. Reduces creation/destruction overhead, controls concurrency level.

Parallel Data Management

• Distribution: How data is partitioned across processors/memory.

  • Block Distribution: Contiguous chunks.

  • Cyclic Distribution: Round-robin assignment.

  • Block-Cyclic: Hybrid.

• Partitioning: Goal: balance load, minimize communication (place communicating data together), maximize locality (spatial/temporal).

• Locality: Exploit temporal locality (reuse data soon) and spatial locality (access nearby data). Use data structures with good cache behavior (AoS vs SoA).

Fusing Map and Scan Operations

• Map: Applies a function $f$ independently to each element of a collection: $$\displaystyle [x_1, x_2, ..., x_n] \to [f(x_1), f(x_2), ..., f(x_n)] $$. Embarrassingly parallel.

• Scan (Prefix Sum): Computes all intermediate sums: $$\displaystyle [x_1, x_2, ..., x_n] \to [x_1, x_1+x_2, x_1+x_2+x_3, ...] $$. Requires dependencies.

• Fusing: Combining map and scan into a single pass over data to reduce memory traffic and improve locality.

  • Example: Compute prefix sums of squares: $$\displaystyle \text{scan}(x_i^2) $$. Can fuse square operation into scan kernel.

  • Use Case: Stream processing, GPU kernels where memory bandwidth is bottleneck.

I/O Handling in Parallel Programming Languages

• Challenges: Multiple processes/threads writing to same file → race conditions, inconsistent views. High overhead from many small I/O requests.

• Solutions:

  1. Collective I/O: Processes coordinate to issue large, contiguous requests (e.g., MPI-IO). Each process computes its file access pattern, an aggregator (or all) performs the actual I/O.

  2. Two-Phase I/O: Phase 1 (Aggregation): Processes with non-contiguous requests first move data to intermediate buffers (in memory) to form larger contiguous chunks. Phase 2 (Transfer): Buffered data written to file system. Reduces number of I/O requests.

  3. File Striping: Distribute file across multiple disks/OSTs (Lustre) to increase bandwidth.

  4. Libraries: MPI-IO, HDF5 (parallel), ADIOS.

F. Performance Evaluation

Performance Metrics for Parallel Systems

• Speedup ($S$): $$\displaystyle S = \frac{T_s}{T_p} $$. $$\displaystyle T_s $$ = serial time, $$\displaystyle T_p $$ = parallel time on $p$ processors.

• Efficiency ($E$): $$\displaystyle E = \frac{S}{p} = \frac{T_s}{p T_p} $$. Fraction of time processors are usefully employed.

• Scalability: How $S$ or $E$ changes with $p$. Strong scaling: Fixed problem size, increase $p$. Weak scaling: Problem size per processor fixed, increase $p$ and total size.

• Cost-Effectiveness: $$\displaystyle C = p \times T_p $$. Cost in processor-time. Goal: minimize $C$ for given problem.

Amdahl's Law and Gustafson's Law

• Amdahl's Law (Fixed Workload):

$$S_{max} = \frac{1}{(1 - f) + \frac{f}{p}}$$

where $f$ = fraction of code that is parallel. As $p \to \infty$, $$\displaystyle S_{max} \to \frac{1}{1-f} $$.

*   **Implication:** Speedup bounded by sequential portion. Even with infinite processors, max speedup is $1/(1-f)$. **Example:** If 90% parallel ($$\displaystyle f=0.9 $$), max speedup = 10.

> [!TIP] Amdahl's Law assumes **fixed problem size**. Often unrealistic as adding processors allows larger problems.

• Gustafson's Law (Scaled Workload):

$$S = p - (1 - f)(p - 1)$$

Here, $f$ is the parallel fraction of the **scaled problem** (problem size increases with $p$ to keep time constant).

*   **Reformulation:** $$\displaystyle T_s = (1-f)T_p + f p T_p $$. Assumes parallel part scales linearly with $p$.

*   **Implication:** If problem size scales, speedup can be nearly linear ($S \approx p$) because the sequential part $$\displaystyle T_s $$ becomes negligible relative to total scaled time $$\displaystyle T_p $$.

> [!TIP] Gustafson's Law is more realistic for many scientific applications where we solve larger problems with more resources.

\boxed{S_{max} = \frac{1}{(1 - f) + \frac{f}{p}}} \quad \text{(Amdahl's Law)}

\boxed{S = p - (1 - f)(p - 1)} \quad \text{(Gustafson's Law)}