Human Computer Interaction (IT-803 (B)) - Unit 2 Short Notes

UNIT 2: BLOCKCHAIN TECHNOLOGY & PARALLEL COMPUTING

A. BLOCKCHAIN TECHNOLOGY

1. Cryptographic Foundations

Cryptographic Hash Functions

A deterministic algorithm that maps an arbitrary-length input (message) to a fixed-length output (hash/digest), designed to be collision-resistant and one-way.

Essential Properties:

Role in Blockchain: Forms the backbone of block linking (each block header contains previous block's hash), ensures data integrity, and is used in mining (PoW).

[!TIP] Exam often asks to list and explain properties. Use the table format for clarity.

Merkle Trees

A binary hash tree where leaves are hashes of individual transactions, and each non-leaf node is the hash of its two child nodes.

Structure & Construction:

1. Transactions in a block are hashed → Leaf Nodes.

2. Pairs of leaf hashes are concatenated and hashed → Next level.

3. Process repeats recursively until a single root hash (Merkle Root) is obtained.

4. Merkle Root is stored in the block header.

Importance for Blockchain:

• Efficiency & Scalability: Enables Merkle Proofs. A lightweight node can verify a specific transaction's inclusion by receiving only the transaction and a logarithmic (O(log n)) number of sibling hashes, not the entire block.

• Data Integrity: Any alteration to a single transaction changes its leaf hash, propagating up to alter the Merkle Root, breaking the chain.

• Simplified Payment Verification (SPV): Core to Bitcoin's light client protocol.

Usage in Transaction Verification:

[!TIP] Key point: Merkle Trees allow verification without full block download. Mention SPV in answers.

2. Blockchain Structure & Mining

Block Structure

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

Components:

• Block Header: Metadata critical for consensus and chain linking.

  • Version: Protocol version.

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

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

  • Timestamp: Block creation time.

  • Bits: Compact representation of the current target difficulty.

  • Nonce: 32-bit number miners vary to find a valid block hash.

• Transaction Counter: Number of transactions (VarInt).

• Transactions: List of all transactions (coinbase + regular). First transaction is the coinbase transaction (miner's reward).

Block Mining

The process of adding a new block to the blockchain by solving a computationally difficult puzzle.

Mining Process Steps (PoW):

1. Collect pending transactions from mempool.

2. Create block header with: prev_hash, merkle_root, timestamp, bits, and initial nonce=0.

3. Hash the block header (double SHA-256 in Bitcoin).

4. Check if hash(header) < target (defined by bits). If NO, increment nonce and repeat from step 3.

5. If YES, block is valid. Broadcast to network.

6. Other nodes verify: hash meets target, transactions valid, block size correct, etc.

7. Upon acceptance, miners start building on this new longest chain.

Types of Mining (Consensus Mechanisms):

Double-Spending Problem

• Definition: The risk that a single digital token/coin can be spent more than once due to the digital nature of assets and network latency.

• Significance: A fundamental issue for any digital cash system. Without a solution, trust in the currency collapses.

• Prevention in Blockchain:

  1. Global Consensus & Ordering: Transactions are ordered into a single, agreed-upon, immutable ledger (the blockchain). The first transaction in a block is considered valid; later conflicting ones are rejected.

  2. Confirmation Depth: A transaction is considered final only after being buried under k subsequent blocks (e.g., 6 confirmations in Bitcoin). An attacker would need to re-mine all k blocks to reverse a transaction (51% attack).

  3. Network Propagation: Transactions are gossiped quickly. Honest nodes reject conflicting transactions they see later.

[!TIP] Double-spending is prevented by consensus on transaction order. Link this to mining and block propagation.

3. Consensus Mechanisms

Proof of Work (PoW)

• HashCash (Adam Back, 1997): Original anti-spam mechanism. Sender must find a nonce such that Hash(nonce || message) has n leading zeros. Proves work was done.

• Bitcoin PoW: Adapts HashCash. Miners find nonce such that:

$$ \text{SHA256(SHA256(Block\_Header))} < \text{Target} $$

Target adjusts every 2016 blocks to maintain ~10 min block time.

• Attacks on PoW:

  • 51% Attack: If an attacker controls >50% of total hash power, they can:

    1. Double-spend their own coins (by creating a longer private fork).

    2. Censor transactions.

    3. Earn all block rewards (but not steal others' funds).

  • Monopoly Problem: Mining centralization due to economies of scale (ASICs, mining pools). Pools like Foundry USA, Antpool control significant hash power, contradicting decentralization ideal.

Proof of Elapsed Time (PoET)

• Algorithm: Uses Intel SGX (Software Guard Extensions) trusted execution environment (TEE).

  1. Each validator requests a random wait time from a ledger (a shared, signed data structure).

  2. SGX internally generates this wait time fairly and confidentially.

  3. Validator sleeps for its assigned time. The one with the shortest wait time wakes first and proposes the next block.

  4. Others verify the wait time was correctly generated (via SGX quote) and the block.

• Advantages: Low energy vs PoW, fair leader election without heavy computation.

• Limitation: Requires trusted hardware (Intel SGX), which is a centralization point.

Byzantine Fault Tolerance (BFT)

• Problem: Reaching consensus in a distributed system where some nodes may be faulty/malicious (Byzantine) and messages can be delayed.

• Lamport-Shostak-Pease (LSP) / Practical BFT (PBFT):

  1. Pre-Prepare: Leader (primary) proposes a block with sequence number n to all replicas.

  2. Prepare: Each replica, if block is valid, broadcasts Prepare(n, block_hash) to all others. It waits for 2f+1 Prepare messages (including its own) from distinct nodes.

  3. Commit: After 2f+1 Prepares, replica broadcasts Commit(n, block_hash). Waits for 2f+1 Commits.

  4. Execute: Upon 2f+1 Commits, block is committed and executed.

• Requirement: System must have 3f+1 total nodes to tolerate f Byzantine nodes. Used in permissioned/private blockchains (known identities).

Raft Algorithm

• Goal: Provide strong leader-based consensus for crash fault-tolerant (CFT) systems (no Byzantine nodes). Simpler than PBFT.

• Working Principles:

  • Roles: Leader, Follower, Candidate (during election).

  • Term: Arbitrary time period with a single leader. Each term begins with election.

  • Leader Election: If follower doesn't hear from leader within election timeout, becomes Candidate, votes for self, requests votes. Wins if gets majority votes.

  • Log Replication:

    1. Leader appends entry to its log, sends AppendEntries RPC to all Followers.

    2. Followers append entry and respond.

    3. Leader commits entry when replicated on majority. Notifies followers to commit.

• Key: Strong leader ensures simplicity and linearizable consistency. Used in etcd, Consul, Hyperledger Fabric (ordering service).

Consensus in Bitcoin (Detailed)

1. Transaction Propagation: User signs transaction, broadcasts to P2P network.

2. Mempool: Miners collect valid, unconfirmed transactions.

3. Block Creation: Miner assembles block (header + transactions). Sets nonce=0.

4. PoW Search: Miner repeatedly hashes header with different nonce until hash < target.

5. Block Propagation: Winning miner broadcasts block. Nodes verify:

   • Proof of Work (hash < target).

   • Block size, header fields.

   • All transactions (inputs unspent, signatures valid, no double-spends within block).

   • Merkle Root matches transactions.

   • Coinbase reward + fees correct.

6. Chain Selection: Nodes adopt the longest valid chain (most cumulative PoW). If two blocks found simultaneously, a temporary fork occurs. Miners work on the first block they receive; the fork resolves when one chain gets longer.

7. Finality: Probabilistic. After k confirmations (blocks on top), probability of reversal drops exponentially.

Permissioned Blockchain Consensus

For networks where participants are known/verified (e.g., enterprise consortiums). No need for Sybil resistance (PoW). Focus on performance & finality.

4. Smart Contracts

Bitcoin Script

• What: Bitcoin's stack-based, Forth-like, non-Turing-complete scripting language embedded in each transaction output (locking script) and input (unlocking script).

• Capabilities:

  • Simple conditional logic (OP_IF, OP_ELSE).

  • Multi-signature (OP_CHECKMULTISIG).

  • Timelocks (OP_CHECKLOCKTIMEVERIFY).

  • Hashlocks (OP_HASH160, OP_EQUAL).

• Limitations:

  • No loops → prevents infinite execution (intentional for security).

  • Limited opcodes (~200, many disabled).

  • No state between transactions (stateless).

  • Cannot access external data (oracle problem).

  • Result: Primarily used for payment channels (Lightning Network), escrow, multisig wallets. Not for complex dApps.

Ethereum Smart Contracts

• Writing Process:

  1. Write contract logic in Solidity (high-level, JS-like) or Vyper (Pythonic).

  2. Compile to EVM bytecode.

  3. Deploy via transaction to a specific address. Deployment cost = gas.

  4. Interact by sending transactions to contract address (costs gas).

• Execution Environment: Ethereum Virtual Machine (EVM). Each node runs EVM to execute contract code on every node in the network. State changes are recorded on-chain.

• Key Features: Turing-complete, persistent storage, can call other contracts, event emission.

Hyperledger Fabric Smart Contracts (Chaincode)

• Writing Process:

  1. Write chaincode (business logic) in Go, Java, or JavaScript.

  2. Chaincode interacts with ledger via GetState/PutState APIs.

  3. Package chaincode into a deployment spec.

  4. Install on endorsing peers.

  5. Instantiate/Approve on a channel (defines endorsement policy, init args).

• Deployment & Execution:

  • Execute: Client sends proposal to endorsing peers. Peers simulate, produce endorsement (signature + read-write set). Client collects sufficient endorsements, submits to ordering service.

  • Ordering: Ordering service (Raft, etc.) sequences transactions into blocks.

  • Validation & Commit: All peers validate block (endorsement policy, MVCC), then commit to ledger. Execute-Order-Validate paradigm.

• Key Difference from Ethereum: Chaincode does not run on all nodes. Only endorsing peers simulate. Ordering service is separate. Final validation/commit is done by all committing peers.

Essential Characteristics of Smart Contracts

[!TIP] Contrast Ethereum (global state, all nodes execute) vs Fabric (channel-based, execute-order-validate).

5. Blockchain Types & Design

Public vs Private/Permissioned Blockchains

Permissioned Blockchain Design Issues

• Membership Service Provider (MSP): How to issue, revoke, manage identities (X.509 certificates in Fabric).

• Privacy & Confidentiality: How to hide transaction details from non-participants? (Fabric: channels & private data collections).

• Consensus Choice: Trade-off between performance (Raft) and fault tolerance (PBFT).

• Governance: Who decides protocol upgrades? How are disputes resolved?

• Scalability vs Decentralization: Permissioned chains are more centralized for performance. How many nodes? Geographic distribution?

• Interoperability: How will this chain interact with other chains or legacy systems?

• Regulatory Compliance: KYC/AML integration, data residency (GDPR).

Hyperledger

• Overview: An open-source collaborative effort (hosted by Linux Foundation) to advance cross-industry blockchain technologies. Not a cryptocurrency. Focus on enterprise-grade, permissioned DLT.

• Projects: Fabric, Sawtooth, Indy (identity), Iroha (mobile), Burrow (EVM).

• Hyperledger Fabric Architecture:

  DiagramCANVAS: Three-layer diagram: 1) Application Layer (SDK, Apps). 2) Network Layer (Peers: Endorsing/Committing, Ordering Service). 3) Membership/Identity Layer (MSP, CA). Show channels as separate ledgers between subsets of peers.

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

  • Ordering Service: Solo (dev), Raft (production), Kafka (legacy). Orders transactions into blocks, broadcasts to peers. No consensus on transaction validity.

  • Channels: Private subnets of communication between specific peers/organizations. Each channel has its own ledger.

  • Chaincode (Smart Contracts): Business logic, runs in Docker containers on peers.

  • Membership Service Provider (MSP): Manages identities (certificates) for all entities (peers, users, orderers).

• Identities and Policies in Fabric:

  • Identities: X.509 digital certificates issued by a Certificate Authority (CA). Bind a public key to an organization/user.

  • Policies: Rules defined in channel configuration and chaincode.

    • Channel Policies: e.g., Admins policy (who can config channel), Readers/Writers (access).

    • Chaincode Policies: Endorsement Policy – specifies which peers (by org) must endorse a transaction for it to be valid. e.g., AND('Org1.peer', 'Org2.peer').

    • Lifecycle Policy: Who can approve chaincode definition for a channel.

6. Blockchain Platforms & Protocols

Bitcoin Network

• P2P Network Structure: Unstructured, flood-based gossip network. Nodes (full, lightweight) connect to ~8 random peers. No central server.

• Transaction Processing Flow:

  1. Creation: User creates transaction (inputs, outputs, signature).

  2. Broadcast: Sent to connected peers.

  3. Validation & Mempool: Each node validates (signature, UTXO set, fee). Valid tx enters mempool.

  4. Mining: Miners select tx from mempool, assemble candidate block, mine.

  5. Block Propagation: Winning miner broadcasts block. Nodes validate block & all tx again. If valid, remove conflicting tx from mempool, add block to chain.

  6. Confirmation: Recipient waits for confirmations (blocks on top).

Alternative Platforms

7. Blockchain Applications

Mortgage Process

• Traditional Workflow:

  1. Application & documentation (manual, paper-based).

  2. Credit check, income verification (multiple third parties).

  3. Property appraisal (ordered by lender).

  4. Title search (to ensure no liens).

  5. Underwriting (manual review).

  6. Closing (in-person, paper signatures, escrow).

  7. Recording with county (slow, days/weeks).

  • Problems: Slow (30-45 days), expensive (2-5% fees), opaque, fraud risk (title fraud), multiple copies of documents.

• Blockchain-Enabled Transformation:

  1. Immutable Digital Identities: Borrower, lender, agent, appraiser have verified digital IDs on-chain.

  2. Shared, Permissioned Ledger: All stakeholders (lender, title company, county recorder) on a permissioned chain (e.g., Hyperledger Fabric).

  3. Smart Contracts Automate Workflow:

     • Trigger appraisal request upon application.

     • Automatically release funds to seller upon verified conditions (inspection passed, title clear).

     • Execute escrow release.

  4. Tokenized Assets: Property title as a digital token (NFT-like). Transfer is instant and recorded on-chain.

  5. Benefits: Days vs weeks, reduced fraud, lower costs (disintermediate some parties), transparency, real-time status tracking.

Supply Chain Finance

• Traditional: Invoices are paper-based. SMEs wait 30-90 days for payment. Financing (factoring) is slow, requires credit checks, high interest.

• Blockchain Improvement:

  • Provenance Tracking: Each step (manufacturer → shipper → retailer) recorded on immutable ledger. All parties see same data.

  • Invoice Digitization: Invoice created as a digital asset on-chain (e.g., on Corda or Fabric).

  • Smart Contract Triggers: Upon verified delivery (IoT sensor data or digital signature from receiver), smart contract automatically:

    1. Releases payment from buyer's bank to seller (if pre-agreed).

    2. Or, if using financing: flags invoice as "eligible" for financier. Financier can instantly verify authenticity and purchase invoice at discount.

  • Benefits: Reduced DSO (Days Sales Outstanding), lower financing costs, reduced fraud (fake invoices), improved trust, automated reconciliation.

Cross-Border Payments

• Enterprise Application & Benefits:

  • Problem: Traditional (SWIFT) involves multiple correspondent banks, takes 2-5 days, high fees ($25-50 + FX spread), lack of transparency.

  • Blockchain Solution (e.g., RippleNet, JPM Coin):

    1. Sender's bank converts fiat to digital asset (XRP, stablecoin) on a permissioned ledger.

    2. Asset is sent directly to recipient's bank on the ledger (near-instant).

    3. Recipient's bank converts digital asset to local fiat.

  • Benefits:

    • Speed: Seconds to minutes vs days.

    • Cost: ~$0.0005 per transaction (Ripple) vs $25+.

    • Transparency: Track payment in real-time.

    • Finality: Irreversible settlement, no recalls.

    • Liquidity Management: Banks can hold digital asset instead of nostro accounts in multiple countries.

Identity Management

• Traditional: Centralized authorities (govt, Facebook, Google) control identity data. Users have no control, prone to breaches, fragmented.

• Blockchain-Based Identity (Self-Sovereign Identity - SSI):

  • Architecture:

    • User: Holds private keys in wallet (mobile). Identity is a set of Verifiable Credentials (VCs) issued by authorities (e.g., university degree, passport).

    • Issuer: Signs credential with private key, stores hash on-chain (e.g., Hyperledger Indy).

    • Verifier: Checks digital signature against on-chain public key (DID) to verify credential authenticity without contacting issuer.

    • Blockchain Role: Acts as decentralized public key infrastructure (DPKI), storing Decentralized Identifiers (DIDs) and credential schemas/revocation lists. No personal data on-chain.

  • Process: User presents VC to verifier (e.g., bar for age). Verifier checks cryptographic proof. User reveals only necessary data (zero-knowledge proofs possible).

  • Benefits: User control, privacy, reduced fraud, interoperability, no single point of failure.

B. PARALLEL COMPUTING

1. Fundamental Concepts & Terminologies

MIMD Multiprocessors vs Multiple Computer Systems/Networks

MIMD (Multiple Instruction, Multiple Data) multiprocessors are tightly-coupled systems where multiple processors share a common physical memory space and are managed by a single OS instance.

Distinguishing Characteristics:

1. Memory Sharing: MIMD has physically shared main memory (with caches). Networks of computers have distributed memory (each node has its own private memory); communication via message passing.

2. Communication Cost: In MIMD, accessing shared memory is fast (nanoseconds). In networks, message passing is slow (microseconds/milliseconds, network latency).

3. Coherency: MIMD requires hardware cache coherence protocols (snooping, directory) to keep caches consistent. Networks have no cache coherence issue (no shared memory).

4. Fault Isolation: In MIMD, a faulty processor can corrupt shared memory → system crash. In networks, node failure is isolated.

5. OS & Scheduling: MIMD has a single, global OS scheduler managing all processors/processes. Networks have independent OSes on each node; scheduling is local.

6. Tightly vs Loosely Coupled: MIMD is tightly-coupled (close proximity, fast interconnect like bus/mesh). Networks are loosely-coupled (geographically dispersed, slower network like Ethernet).

2. Performance & Speedup Analysis

Pipeline Performance: Proof of k-stage Speedup Limit

Claim: A k-stage linear pipeline can be at most k times faster than a non-pipelined processor.

Proof:

1. Let t = delay of one stage in a non-pipelined processor (which must complete all work sequentially).

2. In a k-stage pipeline, each stage is designed to take time t/k (ideally, stages are balanced).

3. Non-pipelined time for n instructions: T_serial = n * t.

4. Pipelined time for n instructions: First instruction takes k * (t/k) = t to fill pipeline. Subsequent n-1 instructions complete every t/k time (steady state). So:

$$ T_{pipeline} = t + (n-1) * \frac{t}{k} $$

5. Speedup (S):

$$ S = \frac{T_{serial}}{T_{pipeline}} = \frac{n \cdot t}{t + (n-1) \cdot \frac{t}{k}} = \frac{n}{1 + \frac{n-1}{k}} $$

6. As n → ∞ (large number of instructions), the term (n-1)/k dominates 1:

$$ \lim_{n \to \infty} S = \frac{n}{n/k} = k $$

7. Conclusion: Maximum speedup = k. Real speedup < k due to pipeline hazards (structural, data, control) causing stalls.

[!TIP] Exam Question: "Prove that a k-stage linear pipeline can be at most k times faster." Present the derivation step-by-step as above. Final answer: \boxed{k}.

Parallel System Metrics

3. Memory Systems & Cache Coherence

Cache Design Issues: Virtual vs Physical Addresses

Disadvantages of Caches Using Virtual Addresses:

1. Alias Problem: Same physical memory location can have multiple virtual addresses (from different processes). If cache indexed by virtual address, same data could be cached in multiple lines (aliases). On write, must invalidate all aliases → complex.

2. Cache Flush on Context Switch: Since virtual address spaces change, cache must be flushed (invalidated) on every process switch to avoid using stale data from previous process. High overhead.

3. OS Complexity: OS must manage cache coherency across address spaces (e.g., page coloring).

4. Physical Indexing Preferred: Modern CPUs use physically indexed, physically tagged (PIPT) caches to avoid aliasing. Or virtually indexed, physically tagged (VIPT) caches (if cache size < page size) to reduce tag comparison latency without aliasing.

Cache Architecture: Centralized vs Distributed Shared Caches

Cache Coherence Problem

Characterization: In a shared-memory multiprocessor with private caches, multiple cached copies of the same memory block can exist. When one processor writes to its cached copy, other cached copies become stale. The cache coherence problem is ensuring all processors see a consistent view of memory despite caches.

Coherence Methods:

1. Snooping-Based Protocols (Bus-Based Systems)

• Principle: All caches and memory controller are on a shared broadcast medium (bus). Each cache snoops (listens to) all bus transactions.

• Types:

  • Write-Invalidate: On write to a block, cache broadcasts Invalidate on bus. All other caches with that block invalidate their copy. Next read must fetch from memory/writer.

  • Write-Update/Write-Broadcast: On write, cache broadcasts new data on bus. All other caches update their copy. More bus traffic, but subsequent reads are fast.

• State Transition (MSI/MESI Protocol): Each cache line has a state:

  • Modified (M): Dirty, only in this cache.

  • Exclusive (E): Clean, only in this cache (can write without bus).

  • Shared (S): May be in other caches, clean.

  • Invalid (I): Not usable.

  • Transitions triggered by local read/write and bus snoop events (Read, Write, Invalidate).

• Advantage: Simple, no extra storage for directories.

• Disadvantage: Doesn't scale (bus saturation). Works for small systems (≤ 8-16 cores).

2. Directory-Based Protocols (Scalable Systems)

• Principle: Maintain a centralized or distributed directory that tracks, for each memory block, which caches have a copy and its state (shared/modified).

• Operation:

  1. Processor issues read/write to memory block.

  2. Directory is consulted first (like a cache for metadata).

  3. If write and block is shared elsewhere, directory sends Invalidate to all sharers before granting write permission.

  4. If read and block is modified elsewhere, directory forwards request to the cache holding the modified copy (cache-to-cache transfer).

• Advantage: Scales to many nodes (no broadcast). Traffic proportional to number of sharers, not total nodes.

• Disadvantage: Directory storage overhead (bit per cache line per node). Potential directory bottleneck (centralized directory). Complexity in distributed directories.

• Used in: Large NUMA machines, multi-chip modules, clusters.

4. Advanced Architectures

GPU Architecture

• Modern GPU Architectural Characteristics:

  • Many-Core: Hundreds to thousands of smaller, simpler scalar cores (e.g., NVIDIA CUDA cores, AMD stream processors) organized in Streaming Multiprocessors (SMs) / Compute Units (CUs).

  • SIMT (Single Instruction, Multiple Thread): Groups of threads (warps/wavefronts, typically 32/64 threads) execute the same instruction on different data. Divergence (if/else) causes serialization.

  • Massive Memory Bandwidth: Wide memory buses (e.g., 384-bit, 512-bit), high-speed GDDR6/HBM2e memory. Bandwidth > 1 TB/s.

  • High Throughput, Latency Hiding: Designed for throughput-oriented computing. Uses massive multithreading (thousands of concurrent threads) to hide memory latency. When one warp stalls, scheduler switches to another.

  • Specialized Units: Dedicated hardware for texture sampling, floating-point (FP32, FP64, Tensor cores for AI), integer, and now RT cores for ray tracing.

  • Memory Hierarchy: Per-SM shared memory/L1 cache, L2 cache shared across SMs, global memory (VRAM).

• Applications:

  • Graphics Rendering: Original purpose.

  • General-Purpose GPU (GPGPU) Computing: Scientific computing (CFD, molecular dynamics), machine learning (training/inference), cryptocurrency mining, video encoding, data analytics.

Transactional Memory (TM)

• Transaction (in databases): A sequence of operations that either commits (all changes permanent) or aborts/rolls back (no effect). ACID properties.

• Transactional Memory (TM): A concurrency control mechanism for shared-memory parallel programming (like a lock, but optimistic).

  • Idea: Group memory accesses into a transaction. System speculatively executes transaction. At commit, check for conflicts (another transaction wrote same location). If no conflict, commit; else abort and retry.

  • Types:

    • Hardware TM (HTM): CPU extensions (Intel TSX, IBM POWER) to track read/write sets in cache, detect conflicts in hardware. Fast, but limited by cache size/conflict complexity.

    • Software TM (STM): Library/runtime that instruments code to track accesses in software. Flexible, works on any hardware, but slower.

    • Hybrid TM: Combine HTM for common case, fall back to STM/locks for large/conflicting transactions.

  • Advantage over Locks: Avoids deadlocks, reduces contention (abort instead of block), simpler programming.

  • Disadvantage: Contention can cause livelock (constant aborts), performance unpredictable, not all operations can be in transactions (I/O, system calls).

Future System Architectures

• Architectural Characteristics:

  1. Heterogeneous Integration: CPU + GPU + FPGA + AI accelerators (TPU, NPU) on same package (e.g., AMD Ryzen with RDNA graphics, Intel Foveros).

  2. Chiplet-Based Design: Break large monolithic dies into smaller chiplets (CPU cores, I/O, memory controller) connected via high-speed interconnects (Infinity Fabric, UCIe). Improves yield, cost, flexibility.

  3. Near-Memory/In-Memory Computing: Reduce data movement by placing compute logic closer to or inside memory (HBM with logic die, processing-in-memory - PIM). Targets "memory wall".

  4. Domain-Specific Architectures (DSA): Optimized for specific workloads (AI, networking, storage). More efficient than general-purpose CPUs.

  5. Advanced Interconnects: Silicon photonics, 3D stacking (HBM, L4 cache), faster on-package networks (mesh, ring).

  6. Security-First: Hardware-enforced isolation (Intel SGX, AMD SEV, ARM TrustZone), speculative execution side-channel mitigations.

  7. Quantum-Classical Hybrid: Classical control processors integrated with quantum processing units (QPUs).

5. Parallel Programming Models

Four Categories of Parallelism

1. Bit-Level Parallelism: Increasing word size (8-bit → 64-bit) so processor does more work per instruction. (Less relevant now).

2. Instruction-Level Parallelism (ILP): Multiple instructions executed simultaneously within a single processor pipeline (superscalar, out-of-order execution, speculation). Exploited by compiler/CPU hardware.

3. Data Parallelism: Same operation performed simultaneously on multiple data elements. SIMD (Single Instruction, Multiple Data) vector instructions (SSE, AVX, NEON). Common in scientific computing, graphics, ML.

4. Task Parallelism (Thread-Level Parallelism - TLP): Different tasks (threads/processes) executed concurrently on different processors. May have different code. MIMD paradigm. Most common in multi-core programming (pthreads, OpenMP, MPI).

Steps to Design Parallel Programs

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

   • Task Parallelism: Identify independent tasks.

   • Data Parallelism: Partition data (domain decomposition).

2. Assignment: Assign tasks/data to processes/threads. Aim for load balancing (equal work per processor). Consider data locality.

3. Orchestration: Manage interactions between tasks.

   • Synchronization: Barriers, locks, semaphores to coordinate.

   • Communication: Message passing (MPI) or shared memory (locks, atomics).

   • Scheduling: Static (at compile-time) or dynamic (at runtime).

4. Mapping: Map logical processes/threads to physical processors/cores. Consider NUMA effects, cache affinity.

5. Performance Tuning: Identify bottlenecks (Amdahl's Law), reduce communication/synchronization overhead, improve locality.

Distributed-Memory Programming: MPI

• Message Passing Interface (MPI): A standardized, portable API for message-passing in distributed-memory systems (clusters, supercomputers).

• Key Concepts:

  • Communicator: Group of processes that can communicate (MPI_COMM_WORLD).

  • Rank: Unique ID of a process within a communicator (0 to size-1).

  • Send/Receive: Point-to-point communication.

    
    MPI_Send(buf, count, datatype, dest, tag, comm);
    
    MPI_Recv(buf, count, datatype, source, tag, comm, status);
    
    

  • Collective Operations: All processes in communicator participate.

    • MPI_Bcast (broadcast), MPI_Gather/MPI_Scatter, MPI_Reduce (sum, max), MPI_Barrier.

  • Non-blocking: MPI_Isend, MPI_Irecv allow computation/communication overlap.

• Programming Model: SPMD (Single Program, Multiple Data). All processes run same executable, but with different rank. They branch based on rank.

• Advantage: Explicit control, scalable, works on any network (Infiniband, Ethernet).

• Disadvantage: Programmer must manage all communication/synchronization explicitly (harder than shared memory).

Parallel Language Features

• I/O Handling:

  • Challenge: Multiple processes writing to same file → race conditions, interleaved output.

  • Solutions:

    1. Independent I/O: Each process writes to separate file (rank in filename).

    2. Collective I/O: Coordinated access (MPI-IO). Processes form groups, access file in large contiguous chunks. OS/parallel filesystem (Lustre, GPFS) optimizes.

    3. Shared File with Locks: Use file locking (advisory) but slow.

    4. Root-Write Pattern: Only root process gathers data (via MPI_Gather) and writes. Simple but root becomes bottleneck.

• Thread Management:

  • Thread: Lightweight unit of execution within a process, shares address space.

  • Creation/Joining: pthread_create, pthread_join (POSIX); std::thread (C++11); OpenMP #pragma omp parallel.

  • Thread Pool: Create fixed number of worker threads at start, assign tasks (work queues). Avoids creation overhead.

  • Fork-Join Model: Main thread spawns parallel region, waits (join) for threads to finish. Common in OpenMP.

  • Tasking: Higher-level abstraction (OpenMP tasks, Cilk, TBB). Runtime schedules tasks onto thread pool.

• Parallel Data Management:

  • Shared Memory: Use locks (mutex, spinlock), atomic operations (fetch_add, compare_and_swap), barriers.

  • Avoid False Sharing: When two threads on different cores modify variables that reside on same cache line, cache line bounces between cores → severe performance degradation. Solution: Pad/align data structures to cache line size (typically 64 bytes).

  • Reduction Variables: Special handling in OpenMP (reduction(+:sum)) to avoid race on accumulation.

  • Thread-Local Storage (TLS): Each thread has its own private copy of a variable (__thread in C, thread_local in C++).

• Fusing Map and Scan Operations:

  • Map: Apply function f to each element of a collection independently. Output[i] = f(Input[i]). Embarrassingly parallel.

  • Scan (Prefix Sum): For each index i, compute Output[i] = Input[0] + Input[1] + ... + Input[i]. Has data dependencies (sequential).

  • Fusing: Combining map and scan into a single pass to improve locality and reduce temporary storage.

    • Example: Compute Output[i] = f(Input[i]) + Output[i-1] in one loop instead of:

      1. Temp[i] = f(Input[i]) (map)

      2. Output[i] = Output[i-1] + Temp[i] (scan)

    • Parallel Scan Challenge: Inherently sequential. Requires parallel algorithms:

      • Reduce-Scan (Hillis-Steele): O(n log n) steps.

      • Blelloch Scan: Work-efficient O(n).

    • Fusing Benefit: If f is cheap, fusing map+scan may be faster than separate passes even with parallel scan, due to fewer memory accesses. Important in functional languages (MapReduce, Spark) and GPU programming.