Memory access pattern: Difference between revisions

Revision as of 20:13, 11 June 2016

Revision as of 20:46, 11 June 2016

Line 1:

In [[computing]], a '''memory access pattern''' is the pattern over time and space with which a system of program accesses [[Memory (computing)|memory]]. TheyThese patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)|cache]] performance, and also have implications for the approach to [[parallelism]] in shared memory systems. Computer memory is usually described as 'random access', but traversals by software will still exhibit patterns that can be exploited for efficiency.

== Sequential ==

At one extreme is the [[sequential access]] pattern , where data is read , processed, and written out in a straightforward incremental manner. As such these access patterns are highly amenable to [[prefetching]].

== Strided ==

Strided or simple 2D access patterns (e.g. stepping through [[multi-dimensional array]]s) are similarly easy to predict, and are found in implementations of [[linear algebra]] and [[image processing]]. [[Loop tiling]] is an effective approach.

== Spatially coherent ==

In [[3D rendering]], access patterns for [[texture mapping]] and [[rasterization]] of small primitives (with arbitrary distortions of complex surfaces) are often 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]] and [[Tiling (computer graphics)|tiling]] for [[texture map]]s and [[frame buffer]] data, or by sorting primitives via [[tile based deferred rendering]].

== Random ==

Data structures which rely heavily on [[pointer chasing]] can often produce poor locality of reference, although sorting can sometimes help.

At the opposite extreme is a truly random memory access pattern. A few multiprocessor systems are specialised to deal with these. The [[Partioned global address space|PGAS]] approach may help by sorting operations by data on the fly (useful when the problem *is* figuring out the locality of unsorted data).

Data structures which rely heavily on [[pointer chasing]] can often produce poor locality of reference, although sorting can sometimes help.

== Approaches ==

[[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.