Distributed memory systems

Concept of Distributed Memory in HPC

In a distributed memory system, each compute node has its own private memory (RAM). No other node can directly read or write that memory. All data exchange between nodes happens explicitly via a network (e.g., Ethernet, InfiniBand).

This is in contrast to shared-memory systems, where multiple processing units see a single, unified memory address space.

Key characteristics:

• Each node has:
• One or more CPUs (and possibly GPUs)
• Local RAM
• Local storage (often)
• Nodes are connected via a high-speed interconnect
• There is no global memory visible to all nodes
• Data must be exchanged using explicit communication (e.g., MPI send/recv)

The cluster as a whole forms a distributed memory machine, even though each node might itself be a shared-memory system internally.

Address Space and Data Locality

In distributed memory systems, each process typically has its own address space on a specific node. An address in one process’s memory has no meaning to another process on another node.

Implications:

• No implicit sharing: You cannot pass a pointer from one process to another and expect it to be valid.
• Data locality becomes critical:
• Keep data on the node where it is needed most.
• Minimize remote communication over the network.
• Decomposition of data structures:
• Large arrays or grids are split into subdomains, each stored in the memory of a different node.
• Each process works primarily on its local piece.

A common mental model is: “One process per node (or per core) with its own private memory; processes collaborate by exchanging messages.”

Programming Models for Distributed Memory

The dominant programming model for distributed memory in HPC is message passing:

• MPI (Message Passing Interface):
• De facto standard for distributed-memory programming in HPC.
• Processes communicate explicitly via operations like MPI_Send, MPI_Recv, MPI_Bcast, MPI_Reduce, etc.
• Supports both point-to-point and collective communication.
• Supports communicators and groups for process organization.

While MPI can also be used on shared-memory machines, it is especially natural for distributed memory, since it mirrors the underlying hardware structure: independent processes + explicit messages over a network.

Other (less common) models that can target distributed memory systems:

• PGAS (Partitioned Global Address Space) languages (e.g., UPC, Coarray Fortran, Chapel) that provide a global view of data but internally use communication.
• Remote procedure call (RPC) or remote method invocation patterns in some high-level frameworks.

In practical cluster usage, most production distributed-memory applications rely primarily on MPI or MPI combined with node-level parallel models (e.g., MPI + OpenMP).

Data Decomposition and Domain Partitioning

Because memory is not shared across nodes, large problems must be partitioned:

• Domain decomposition:
• Common in PDE solvers, CFD, climate models, etc.
• A large spatial domain (e.g., a 3D grid) is partitioned into subdomains.
• Each process owns one or more subdomains and stores only its local data.
• Neighboring subdomains must exchange boundary information via messages.
• Data partitioning strategies:
• 1D, 2D, or 3D block decompositions of arrays.
• Block vs. block-cyclic distributions (e.g., in ScaLAPACK-style linear algebra).
• Graph or hypergraph partitioning for irregular problems (e.g., using tools such as METIS, ParMETIS, Scotch).

Partitioning goals:

• Balance the computational work across processes (load balancing).
• Minimize communication volume and frequency.
• Match the partition to the communication pattern of the algorithm.

These decompositions are explicitly designed with the underlying distributed memory in mind; good decompositions are essential for performance and scalability.

Communication Patterns and Overheads

Because communication is explicit and relatively expensive compared to local memory access, understanding communication patterns is central to distributed memory systems.

Common patterns:

• Point-to-point: Direct messages between pairs of processes.
• Example: neighbor exchanges in a domain decomposition (halo/ghost cell exchange).
• Collectives:
• Broadcast: one process sends the same data to many.
• Gather/Scatter: many processes send to/receive from a root.
• All-reduce: reduction (e.g., sum, max) of values from all processes, result made available to all.
• Global synchronization:
• Barriers or implicit synchronization in some collective operations.

Overhead considerations:

• Latency: Time to initiate a communication operation.
• Bandwidth: Amount of data that can be transferred per unit time.
• Message size: Small messages are latency-dominated; large messages are bandwidth-dominated.
• Network topology and contention: Interconnect design (e.g., fat-tree, dragonfly) and load can affect communication time.

In distributed memory applications, algorithms are often redesigned to:

• Reduce the total amount of communicated data.
• Reduce the number of messages.
• Overlap communication with computation where possible.

Scalability in Distributed Memory Systems

Distributed memory systems are the main path to scaling to very large core counts and problem sizes, because memory and compute are both scaled by adding more nodes.

Two scaling aspects:

• Strong scaling: Fix the overall problem size and increase the number of processes.
• Challenges: communication and synchronization overheads grow; eventually, extra processes spend more time communicating than computing.
• Weak scaling: Increase the problem size proportionally with the number of processes.
• Goal: keep the work per process constant.
• Communication often grows more slowly than computation, but still limits scalability.

Scalability challenges specific to distributed memory:

• Communication patterns that involve many-to-many exchanges can become bottlenecks.
• Global operations (e.g., all-reduce in iterative solvers) can become expensive at large scales.
• Load imbalance between processes can cause some nodes to wait for others.

Designing algorithms for distributed memory often focuses on minimizing or restructuring communication and using more scalable collective operations.

Memory Capacity and Problem Size

One key advantage of distributed memory systems is the ability to aggregate memory across many nodes.

• Each node has its own RAM; total effective memory is:
  $$\text{Total memory} \approx N_\text{nodes} \times \text{memory per node}$$
• Large-scale simulations and data analyses rely on this aggregated memory to store:
• Large meshes or grids
• Huge matrices
• Massive datasets

However, because memory is distributed:

• No single process can see or store the entire dataset in its own memory.
• Algorithms must be designed to work with local views of the data and explicit communication for nonlocal access.

This is a fundamental mindset shift from single-node or shared-memory programming.

Fault Tolerance and Reliability Considerations

As the number of nodes grows, the probability that something fails during a long run increases. Distributed memory systems must handle:

• Node failures (hardware faults, crashes).
• Network errors.
• Process failures.

Typical strategies (at the application and system level):

• Checkpoint/restart:
• Periodic saving of the distributed application state to a parallel filesystem.
• On failure, the job can restart from the last checkpoint instead of from the beginning.
• Resilient MPI and libraries:
• Some MPI implementations and frameworks provide mechanisms to tolerate process failures, though widespread use is still evolving.

Distributed memory architecture influences how checkpointing is implemented, since the global state is physically spread across many nodes and must be saved in a coordinated way.

When to Use Distributed Memory Systems

Distributed memory systems (i.e., HPC clusters with many nodes) are particularly suitable when:

• The problem size exceeds the memory of a single node.
• The required compute time on a single node would be too long.
• The application is designed with domain or data decomposition that can be partitioned across nodes.
• The workload can benefit from running on tens, hundreds, or thousands of nodes.

Typical application areas:

• Large-scale numerical simulations (weather/climate, astrophysics, fluid dynamics, structural mechanics).
• Large data analytics and machine learning training on massive datasets (often combined with accelerators).
• Large parameter sweeps or ensembles, where many similar tasks run in parallel across nodes.

Understanding the properties and constraints of distributed memory systems is foundational for designing scalable HPC codes and for making effective use of modern clusters.