Memory access pattern

In computing, a memory access pattern or IO access patterns is the pattern with which a system or program reads and writes memory or secondary storage. These patterns differ in the level of locality of reference and drastically affect cache performance,^[1] and also have implications for the approach to parallelism ^{[2] [3]} and distribution of workload in shared memory systems. ^[4] Further, cache coherency issues can affect multiprocessor performance,^[5] which means that certain memory access patterns place a ceiling on parallelism (which manycore approaches seek to break ^[6] ).

Computer memory is usually described as 'random access', but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers ^[7] and programmers understand,analyse and improve the memory access pattern, e.g. VTune and others ,^{[8][9][10][11]} including tools to address GPU memory access patterns^[12]

Memory access patterns also have implications for security,^{[13] [14]} which motivates some to try and disguise a programs activity for privacy reasons.^{[15] [16]}

Examples

Sequential and Linear patterns are incorrectly drawn as counterparts to each other by some publications; while real-world workloads contain almost innumerable patterns^[17]

Sequential

The simplest extreme is the sequential access pattern, where data is read, processed, and written out with straightforward incremented/decremented addressing. These access patterns are highly amenable to prefetching.

Strided

Strided or simple 2D,3D access patterns (e.g. stepping through multi-dimensional arrays) are similarly easy to predict, and are found in implementations of linear algebra algorithms and image processing. Loop tiling is an effective approach. ^[18] Some systems with DMA provided a strided mode for transferring data between subtile of larger 2D arrays and scratchpad memory.^[19]

Linear

A linear access pattern is closely related to 'strided', where a memory address may be computed from a linear combination of some index. Stepping through indices sequentially with a linear pattern yields strided access. A linear access pattern for writes (with any access pattern for non overlapping reads) may guarantee that an algorithm can be parallelised, which is exploited in systems supporting compute kernels.

Nearest neighbour

Nearest neighbour memory access patterns appear in simulation, and are related to sequential/strided patterns. An algorithm may traverse a data structure using information from the nearest neighbours of a data element (in one or more dimensions) to perform a calculation. These are common in physics simulations operating on grids.^[20] Nearest neighbour can also refer to inter-node communication in a cluster; Physics simulations which rely on such local access patterns can be parallelized with the data partitioned into cluster nodes, with purely nearest-neighbour communication between them, which may have advantages for latency and communication bandwidth. This use case maps well onto torus network topology. ^[21]

2D Spatially coherent

In 3D rendering, access patterns for texture mapping and rasterization of small primitives (with arbitrary distortions of complex surfaces) are far from linear, but can still exhibit spatial locality (e.g. in screen space or texture space) . This can be turned into good memory locality via some combination of morton order ^[22] and tiling for texture maps and frame buffer data (mapping spatial regions onto cache lines), or by sorting primitives via tile based deferred rendering.^[23] It can also be advantageous to store matrices in morton order in linear algebra libraries. ^[24]

Scatter

A scatter memory access pattern combines sequential reads with indexed/random addressing for writes. ^[25] Compared to gather, It may place less load on a cache hierarchy since a processing element may dispatch writes in a 'fire and forget' manner (bypassing a cache altogether), whilst using predictable prefetching (or even DMA) for its source data.

However, it may be harder to parallelise since there is no guarantee the writes do not interact,^[26] and many systems are still designed assuming that a hardware cache will coalesce many small writes into larger ones.

In the past, forward texture mapping attempted to handle the randomness with 'writes', whilst sequentially reading source texture information.

The PlayStation 2 console used conventional inverse texture mapping, but handled any scatter/gather processing 'on-chip' using EDRAM, whilst 3D model (and a lot of texture data) from main memory was fed sequenatially by DMA. This is why it lacked of support for indexed primitives, and sometimes needed to manage textures 'up front' in the display list.

Gather

In a gather memory access pattern, reads are randomly addressed or indexed, whilst the writes are sequential (or linear). ^[25] An example is found in inverse texture mapping, where data can be written out linearly across scanlines, whilst random access texture addresses are calculated per pixel.

Compared to scatter, the disadvantage is that caching (and bypassing latencies) is now essential for efficient reads of small elements, however it is easier to parallelise since the writes are guaranteed to not overlap. As such the gather approach is more common for gpgpu programming,^[26] where the massive threading (enabled by parallelism) is used to hide read latencies. ^[26]

Combined gather and scatter

An algorithm may gather data from one source, perform some computation in local or on chip memory, and scatter results elsewhere. This is essentially the full operation of a GPU pipeline when performing 3D rendering- gathering indexed vertices and textures, and scattering shaded pixels in screen space. Rasterization of opaque primitives using a depth buffer is 'commutative', allowing reordering, which facilitates parallel execution. In the general case synchronisation primitives would be needed.

Random

At the opposite extreme is a truly random memory access pattern. A few multiprocessor systems are specialised to deal with these. ^[27] The PGAS approach may help by sorting operations by data on the fly (useful when the problem *is* figuring out the locality of unsorted data).^[20] Data structures which rely heavily on pointer chasing can often produce poor locality of reference, although sorting can sometimes help. Given a truly random memory access pattern, it may be possible to break it down (including scatter or gather stages, or other intermediate sorting) which may improve the locality overall; this is often a pre-requisite for parallelizing.

Approaches

Data oriented design

Data oriented design is an approach intended to maximise the locality of reference, by organising data according to how it is traversed in various stages of a program, contrasting with the more common object oriented approach (i.e. organising such that data layout explicitly mirrors the access pattern).^[28]

Contrast with locality of reference

Locality of reference refers to a property exhibited by memory access patterns. A programmer will change the memory access pattern (by reworking algorithms) to improve the locality of reference ,^[29] and to increase potential for parallelism.^[25] A programmer or system designer may create frameworks or abstractions (e.g. C++ templates or higher-order functions) that encapsulate a specific memory access pattern. ^{[30] [31]}

Different considerations for memory access patterns appear in parallelism beyond locality of reference, namely the separation of reads and writes. E.g.: even if the reads and writes are 'perfectly' local, it can be impossible to parallelise due to dependancies; separating the reads and writes into separate areas yields a different memory access pattern, maybe initially appear worse in pure locality terms, but desirable to leverage modern parallel hardware.^[25]

Locality of reference may also refer to individual variables (e.g. the ability of a compiler to cache them in registers), whist the term memory access pattern only refers to data held in an indexable memory (especially main memory).

See also

• Working set
• Gather-scatter (vector addressing)
• Parallel computing

References