Memory optimization

Locality as the Core of Memory Optimization

Memory optimization in HPC focuses on how a program uses memory, not just how much memory it uses. On modern systems, the cost of moving data is often far larger than the cost of performing arithmetic. Good memory optimization improves locality, reduces data movement, and matches data layouts to access patterns.

Locality describes how your code reuses data in time and in space. Temporal locality means that once data is loaded, you use it again soon. Spatial locality means that if you load one location, you will also use neighboring locations soon. Memory optimizations aim to increase both forms of locality.

In performance terms, memory optimization is largely about organizing computations and data so that data lives as high as possible in the memory hierarchy and is moved as infrequently as possible. You can usually see the effect directly in performance measurements such as bandwidth usage, cache misses, and run time.

Working Set and Capacity Considerations

For any code section, the working set is the amount of data that must be actively present in fast memory (caches) at the same time for the computation to proceed efficiently. If the working set fits comfortably into cache, memory accesses are fast. If it exceeds cache capacity, you see frequent cache misses and slowdowns.

In practice, memory optimization often begins by estimating or measuring the working set size of hot loops and comparing it with typical cache sizes. For example, in a double precision 3D stencil, if you access several arrays over a neighborhood of points, the product of the grid slice size and the number of arrays tells you whether your loop over the slowest index will keep data in cache or repeatedly evict and reload it.

A simple rule is that for good performance a loop’s active data footprint should be significantly smaller than the size of the relevant cache level. If not, you need to restructure loops or data into smaller chunks that fit, which leads directly to tiling and blocking techniques.

Access Patterns and Stride

The specific order in which your code walks through memory is often as important as the total volume of data. A stride is the distance, in elements or bytes, between consecutive memory accesses in a loop. A stride of 1, which corresponds to walking linearly through contiguous memory, is usually best because it matches how hardware fetches memory in cache lines.

Suppose an array is stored in row-major order, as in C, where consecutive elements of a row are contiguous in memory. If you traverse it row by row, you get stride 1 accesses. If you traverse it column by column, you access one element from each row in turn and effectively skip many bytes between consecutive accesses. This large stride causes poor spatial locality and many extra cache line loads.

Memory optimization therefore includes choosing loop orders that give stride 1 access to the innermost loop and aligning data layouts with how arrays are traversed. This often means reorganizing loops, or in some languages choosing the storage order that matches the dominant access pattern.

Loop Transformations for Better Locality

One of the most powerful tools for memory optimization is loop transformation. Without changing the mathematical result, you adjust the order in which iterations are executed to improve data reuse and linear access.

Loop interchange swaps the nesting order of loops so that the innermost loop walks contiguous memory. For a 2D array, exchanging for i and for j can change performance dramatically, even though the number of operations stays the same.

Loop fusion merges two loops that traverse the same data so that each element is loaded once and used in multiple computations before being evicted from cache. The opposite transformation, loop fission or loop distribution, splits a loop into smaller loops if the combined working set is too large for cache, so that each new loop touches less data.

All of these transformations must preserve data dependencies and numerical correctness. In many HPC codes, however, the operations are structurally simple and amenable to such reordering, so these are among the first optimizations you apply when memory access patterns are poor.

Blocking and Tiling

Blocking, also called tiling, is a deliberate strategy to restrict the working set of a computation to a chunk that fits into a chosen cache level. Instead of operating on an entire large array in one sweep, you divide it into blocks and process one block at a time. You then fully exploit temporal reuse inside each block before moving on.

For a matrix multiplication with matrices of size $N \times N$ stored in row-major order, a naive triple loop might cause repeated cache misses for large $N$ because the inner loop may stride through memory in a way that does not fit cache. By introducing a block size $B$ and rewriting the loops so that you iterate over $B \times B$ tiles, you limit the active data to roughly $3 B^2$ elements. If $B$ is chosen so that $3 B^2 \cdot \text{sizeof(element)}$ is comfortably smaller than the target cache size, most accesses within a tile will hit in cache.

In higher dimensions or more complex stencils, the same idea applies. You define blocks over one or more indices, then reorganize loops so that all computations that touch a block are performed before moving on. Even when the optimal block size is not exactly known, using moderate blocks often yields very visible gains.

Data Layout and Structure Design

The way data structures are laid out in memory has a direct effect on access efficiency. Memory optimization frequently involves changing from one layout to another to match how data is used in hot kernels.

A very common choice is between array of structures and structure of arrays. In an array of structures, each element stores all fields together, for example positions and velocities of a particle together in memory. In a structure of arrays, you store all positions in one array and all velocities in another. If a hot loop uses only positions, the structure of arrays layout lets you stream through a single contiguous array and reduces bandwidth and cache pollution.

Another aspect is alignment. Modern compilers and hardware can load and store aligned data more efficiently and vector units often require or prefer aligned addresses. Allocating arrays with proper alignment boundaries and ensuring that the starting index of performance critical data respects these boundaries helps the compiler generate better code and reduces the number of memory transactions.

Padding is sometimes used to modify the effective size or shape of arrays so that stride patterns avoid pathological behaviors, such as cache conflict misses from different rows mapping to the same cache sets, or to prevent false sharing between threads by ensuring that frequently written elements occupy different cache lines.

Reducing Memory Footprint

Reducing how much memory your application uses can improve performance, not just capacity. A smaller memory footprint often means that more of your working set can stay in cache or at least in main memory, and it enables higher concurrency on shared systems because more processes and threads can fit without swapping.

Data precision is one important lever. Many codes default to double precision for safety, but for some parts of the computation single precision can be sufficient. If correctly applied and validated, this halves the memory required for those arrays and cuts the bandwidth cost in half as well. Mixed precision strategies that compute in lower precision but occasionally correct in higher precision are increasingly common in HPC.

Another lever is to remove unnecessary copies and temporary arrays. It is easy for high level code patterns to introduce extra allocations, for example by building intermediate arrays for expressions that could instead be computed in place. Each unnecessary temporary both increases memory usage and adds bandwidth traffic. Memory optimization means identifying these and replacing them with in-place updates or streaming computations where data is read once, processed, and written out without extra copies.

Compression and sparse representations also play a role when data is structured in a way that includes large regions of zeros or repeated patterns. By moving from dense to sparse or compressed formats where appropriate, you reduce both storage and the volume of memory traffic. The tradeoff is extra indexing and sometimes irregular access, so these options must be evaluated carefully in the context of performance measurements.

Temporal Locality and Reuse

Temporal locality focuses on reusing data while it is still in fast memory. Blocking and loop fusion directly exploit this, but you can also design algorithms that deliberately accumulate work around the same data region before moving on.

For example, in a simulation that repeatedly updates fields and computes derived quantities, you can organize the computation so that each grid cell is fully processed in one visit, rather than visiting the same cell multiple times in separate sweeps. Similarly, caching frequently used coefficients or parameters in small local arrays can avoid repeated fetches from larger, slower data structures.

In some cases, reorganizing the algorithm to increase temporal locality can lead to changes in the order of floating point operations and therefore in round-off behavior. When numerical sensitivity is high, you must balance memory and performance gains with reproducibility and accuracy requirements. Where acceptable, however, exploiting reuse often delivers significant performance improvements with minimal code complexity.

NUMA-aware Memory Placement

On modern multicore nodes with non uniform memory access, the physical location of allocated memory relative to the cores that use it has a large effect on access latency and bandwidth. Memory optimization at the node level must therefore take placement into account.

The simplest strategy is to align thread and process work with the memory that they use by following the first touch rule. Many operating systems place memory pages on the NUMA node of the core that first writes to them. If each parallel region initializes and then uses its own partition of an array, and if the threads are pinned to specific cores, this naturally keeps memory local.

If threads or processes frequently access memory that resides on a remote NUMA node, each access incurs extra latency and congestion on the interconnect between memory controllers. Tools that display NUMA distances and runtime libraries that allow explicit placement or migration of memory can help diagnose and correct these issues. Structured decomposition that assigns spatially contiguous data regions to specific threads or processes is usually the best defense.

Avoiding False Sharing

In shared memory programming, false sharing is a specific pattern of inefficient memory use that happens when different threads update different variables that happen to reside on the same cache line. Even if the variables are logically independent, the hardware has to maintain cache coherence at the granularity of whole lines. As one thread writes to its variable, it invalidates the line in the caches of other threads, which then have to reload it. This back and forth can severely degrade performance.

Memory optimization for shared memory includes arranging frequently written per-thread data so that each thread writes mainly to its own cache lines. One common practice is to introduce padding between per-thread elements to ensure each lies in a separate line. Another approach is to use separate arrays or structures for each thread, or to accumulate thread local results in registers and local variables before a single write to shared memory.

False sharing usually does not affect correctness, which makes it harder to spot. Performance profiling tools that show coherence traffic or cache miss breakdowns can help uncover it. Once identified, small changes in structure layout or index computation are often enough to eliminate it.

Memory Access Regularity and Prefetching

Hardware prefetchers attempt to predict future memory accesses and bring data into cache before it is needed. They are most effective when access patterns are regular and predictable, such as simple stride 1 or fixed stride loops. When your code has irregular or data dependent accesses, such as random index lookups or pointer chasing in linked structures, prefetchers are less effective and more memory latency reaches the core.

Memory optimization often includes making access patterns as regular as possible, for example by replacing pointer-based structures with flat arrays of indices, or by grouping indirect accesses into phases where they are more predictable. In some cases, software prefetch instructions provided by compilers or libraries can be used to explicitly request data ahead of time. These are advanced techniques and should be guided by profiling, since excessive or mis-timed prefetching can waste bandwidth.

Measuring and Iterating on Memory Optimizations

Memory optimization is not guesswork. Each change should be guided and validated by measurements that are sensitive to memory behavior. Typical measurements include achieved memory bandwidth, cache miss rates, cycles per instruction, and time spent in memory bound kernels.

A useful simple model is the roofline model, which relates performance to arithmetic intensity defined as the number of floating point operations per byte of data moved from memory. If code has low arithmetic intensity, it is likely memory bound. Effective memory optimization increases the arithmetic intensity by reducing bytes moved per operation, usually by improving reuse and locality.

Because memory hierarchies are complex and compilers apply their own optimizations, you should treat memory optimization as an iterative process. Start with clean and correct code, measure, identify the most memory bound regions, apply targeted changes such as loop transformations, blocking, or data layout adjustments, then measure again. Over time this converges to a design that respects the hardware’s memory behavior and delivers significantly better performance.