Modern Parallel Computer – Seeking Concurrency – Data Clustering

Modern Parallel Computer
Modern parallel computers are designed to perform multiple computations simultaneously by using multiple processors or cores. They aim to increase computational speed and efficiency by dividing tasks into smaller sub-tasks that can be executed concurrently4.

Seeking Concurrency
Concurrency means managing multiple tasks that can overlap in execution time, though not necessarily running simultaneously on a single-core CPU. It is about structuring programs so that multiple tasks make progress without waiting for others to finish, often through fast context switching or multi-threading1.

Data Clustering
Data clustering is a technique in data analysis where data points are grouped into clusters based on similarity. Parallel algorithms for clustering (such as parallel K-means) use multiple processors to speed up the clustering process by dividing the data and processing parts simultaneously, improving performance especially for big data2.

Programming Parallel Computers

Programming parallel computers involves writing software that can execute multiple operations simultaneously. This requires understanding parallel architectures and using appropriate programming models and tools to exploit hardware concurrency efficiently3.

Parallel Architectures

Parallel architectures define how multiple processors are organized and interact to perform computations.

• SIMD (Single Instruction, Multiple Data): One instruction operates on multiple data elements simultaneously, common in vector processing4.

• MIMD (Multiple Instruction, Multiple Data): Multiple processors execute different instructions on different data. This includes:

  • Shared-memory systems: All processors access a common memory.

  • Distributed-memory systems: Each processor has its own local memory4.

• SPMD (Single Program, Multiple Data): Multiple processors run the same program on different data sets, a common parallel programming model4.

Interconnection Networks

Interconnection networks connect processors and memory modules in parallel computers. They determine how processors communicate and share data, impacting performance and scalability. Examples include buses, crossbars, meshes, and hypercubes, each with trade-offs in speed, complexity, and cost4.

Processor Arrays

Processor arrays are arrangements of multiple processors in a regular geometric pattern (e.g., grids or meshes) where each processor communicates with its neighbors. This architecture is often used in SIMD systems and is suitable for tasks with spatial locality4.

Multiprocessors

Multiprocessors are systems with multiple processors sharing a common memory space (shared memory). They allow parallel execution of threads or processes, with communication via shared variables. They are classified by memory access patterns like UMA (Uniform Memory Access) and NUMA (Non-Uniform Memory Access)5.

Multicomputers

Multicomputers consist of multiple independent computers (nodes) connected by a network, each with its own local memory (distributed memory). Communication between nodes occurs via message passing. This architecture scales well but requires explicit communication management by the programmer45.

Flynn’s Taxonomy

Flynn’s Taxonomy classifies computer architectures based on instruction and data streams:

• SISD: Single Instruction, Single Data (traditional sequential computers).

• SIMD: Single Instruction, Multiple Data.

• MISD: Multiple Instruction, Single Data (rarely used).

• MIMD: Multiple Instruction, Multiple Data (common in multiprocessors and multicomputers)4.

Shared-memory Parallel Programming using OpenMP

OpenMP is a widely used API for shared-memory parallel programming. It allows programmers to write parallel code using compiler directives, pragmas, and runtime library routines, mainly in C, C++, and Fortran. OpenMP supports multi-threading on a single node with shared memory, making it easier to parallelize loops and sections of code without managing threads explicitly3.

• OpenMP is limited by the number of CPU cores on a node.

• It provides thread-safe constructs and simple ways to specify parallel regions.

• It is suitable for shared-memory architectures like SMP systems35.

Summary Table

Distributed Computing Overview

Distributed computing involves multiple computers (nodes) working together to solve problems as if they were a single system. These computers communicate by sending messages to coordinate tasks, share data, and ensure consistency.

Message Passing: Models, Events, and Types

• Message Passing is the fundamental communication method in distributed systems. Processes running on different machines send messages to each other to coordinate actions.

• Models define how messages are sent and received (e.g., synchronous or asynchronous communication).

• Events are occurrences in the system, like sending or receiving a message.

• Types of messages include:

  • Command: Request to change state.

  • Event: Notification that a state change happened.

  • Query: Request for information.

  • Reply: Response to a query.

Distributed Models

Distributed systems can be modeled in various ways depending on how processes interact and communicate, such as client-server, peer-to-peer, or message-passing models.

Time and Global States in Distributed Systems

Synchronizing Physical Clocks

• Each computer has its own clock, which may drift apart over time, making it hard to have a single global time.

• Synchronizing clocks is crucial for coordinating actions and maintaining consistency.

• Techniques like Network Time Protocol (NTP) help synchronize physical clocks, but perfect synchronization is impossible.

Logical Time and Logical Clocks

• To overcome clock synchronization issues, logical clocks track the order of events rather than real time.

• Lamport's Logical Clock assigns timestamps to events so that if one event happens before another, their timestamps reflect that order.

• This helps in understanding causality between events in a distributed system.

Coordination and Agreement

Distributed systems need to coordinate actions and agree on shared decisions despite failures or delays.

Distributed Mutual Exclusion

Mutual exclusion ensures that only one process accesses a critical shared resource at a time.

Suzuki–Kasami Algorithm (Token-based)

• Uses a token that circulates among processes.

• Only the process holding the token can enter the critical section.

• If a process wants to enter but doesn’t have the token, it broadcasts a request.

• The token holder sends the token to the requesting process if it is not using it.

• This reduces message complexity compared to other algorithms.

Example:

Imagine 3 processes: P1, P2, P3. P1 has the token initially.

• P2 wants to enter critical section but has no token, so it broadcasts a request.

• P1, holding the token and not in the critical section, sends the token to P2.

• P2 enters critical section.

• After finishing, P2 passes the token to the next requester or keeps it if no requests are pending.

Lamport’s Algorithm (Message-based)

• Processes send REQUEST messages with timestamps to all others when they want to enter the critical section.

• Other processes reply with REPLY messages.

• A process enters the critical section only after receiving replies from all others and if its request has the earliest timestamp.

• Ensures mutual exclusion without a token.

Election Algorithms

These algorithms select a coordinator (leader) among distributed processes.

Ring Algorithm

• Processes are arranged in a logical ring.

• A process initiating election sends its ID around the ring.

• Each process compares the received ID with its own and forwards the highest ID.

• Eventually, the highest ID circulates back to the initiator, which declares it the leader.

Example:

In a ring of processes with IDs 1, 2, 3, 4, 5:

• Process 1 starts election by sending ID=1 to process 2.

• Process 2 compares 1 with 2, forwards 2 to process 3.

• Process 3 compares 2 with 3, forwards 3 to process 4.

• Process 4 compares 3 with 4, forwards 4 to process 5.

• Process 5 compares 4 with 5, forwards 5 to process 1.

• Process 1 receives its own ID (5), so process 5 is elected leader.

Bully Algorithm

• Any process can start an election when it detects the coordinator has failed.

• The process sends election messages to all processes with higher IDs.

• If no higher ID responds, it becomes the coordinator.

• If a higher ID responds, that process takes over the election.

• The highest ID process eventually becomes the leader.

Example:

If process 4 detects failure of coordinator 6:

• Process 4 sends election messages to 5 and 6.

• 5 responds and starts its own election.

• 6 is down, so 5 becomes leader.

• If 7 (higher ID) is alive, it will respond and become leader eventually.

Consensus and Agreement

• Consensus means all non-faulty processes agree on a single value.

• Important for consistency in distributed systems.

• Byzantine Generals Problem illustrates difficulty in achieving consensus when some nodes may act maliciously or send conflicting information.

• Solutions require algorithms that tolerate faults and ensure agreement despite failures.

This explanation covers the fundamental concepts, models, and algorithms related to distributed computing in a clear and simple manner. If you want, I can also provide diagrams or pseudocode for any of these algorithms!

Distributed Transactions

Distributed transactions involve multiple database systems or resources participating in a single transaction. The key requirement is that all changes made by the transaction must be consistently reflected across all involved systems. This means the transaction must be atomic: either all changes are committed or all are rolled back, ensuring consistency and termination of the transaction across all nodes.

Nested Transactions

Nested transactions occur when a transaction starts within the scope of an already running transaction. They are structured in a tree-like hierarchy where the outermost transaction is the top-level, and inner transactions are sub-transactions. Each sub-transaction is atomic relative to its parent. Sub-transactions at the same level can run concurrently and can commit or abort independently, but the final commit of changes is only visible after the top-level transaction commits.

Nested transactions provide additional concurrency and robustness. For example, in a mail delivery system, sending to multiple recipients can be handled as nested sub-transactions that may succeed or fail independently without affecting the entire transaction immediately. When a parent transaction aborts, all its sub-transactions abort as well, but a sub-transaction abort does not necessarily force the parent to abort.

Locks in Distributed Transactions

Locks are mechanisms to ensure that only one process or node can modify a resource at a time in a distributed environment. Distributed locks prevent concurrent writes that could lead to inconsistent data states. They are crucial for coordinating access to shared resources like database rows, files, or external APIs. Without locks, multiple nodes could overwrite each other's changes, causing unpredictable system states.

Distributed locks act as a simple form of leader election, ensuring serialized access to critical resources, sacrificing some parallelism for data correctness.

Optimistic Concurrency Control (OCC)

Optimistic concurrency control is a non-locking concurrency method used in transactional systems. It assumes conflicts are rare and allows multiple transactions to proceed without locking resources. Before committing, each transaction validates that no other transaction has modified the data it has read.

If a conflict is detected during validation, the transaction is rolled back and can be retried. OCC is efficient in low-contention environments because it avoids the overhead of locking and waiting, but it can suffer performance degradation if conflicts are frequent.

The phases of OCC are:

• Begin: Mark the start time of the transaction.

• Modify: Read and tentatively write changes.

• Validate: Check for conflicts with other transactions.

• Commit/Rollback: Commit if no conflicts; otherwise, abort.

Timestamp Ordering

Timestamp ordering is a concurrency control technique where each transaction is assigned a unique timestamp indicating its start time. Data items maintain read and write timestamps to track the last transaction that read or wrote them.

Operations follow these rules:

• A transaction reading an object aborts if the object's write timestamp is newer (indicating a conflict).

• A transaction writing an object aborts if the object's read or write timestamp is newer than the transaction's timestamp.

This ensures transactions are serialized in timestamp order, preventing conflicts without locking.

Flat and Nested Distributed Transactions

• Flat Distributed Transactions: These have a single start and end point and execute sequentially across multiple servers. A coordinator manages the transaction, ensuring all participating servers commit or abort together.

• Nested Distributed Transactions: These allow sub-transactions within a top-level transaction, potentially running concurrently on different servers. Sub-transactions can commit or abort independently, adding concurrency and fault tolerance. The top-level transaction commits only after all sub-transactions have completed successfully.

Atomicity and Two-Phase Commit Protocol

Atomicity ensures a distributed transaction is indivisible: all participating nodes either commit or abort the transaction together.

The Two-Phase Commit (2PC) protocol ensures atomicity in distributed transactions through two phases:

1. Prepare Phase: The coordinator asks all participants if they can commit. Each participant votes "yes" or "no".

2. Commit Phase: If all vote "yes," the coordinator instructs all to commit; if any vote "no," it instructs all to abort.

This protocol guarantees consistency but can block if the coordinator fails.

Data Replication and Transactions with Replicated Data

Data replication involves maintaining copies of data across multiple nodes to improve availability and fault tolerance. However, transactions involving replicated data require coordination to maintain consistency across replicas.

Replication necessitates protocols to synchronize updates so that all replicas reflect the same committed state. Transactions with replicated data must handle potential conflicts and ensure atomicity and consistency despite the distributed nature of the replicas.

This comprehensive overview covers the essential concepts of distributed transactions, nested transactions, concurrency control mechanisms, timestamp ordering, transaction models, atomic commit protocols, and data replication challenges in distributed systems.