Memory access pattern: Difference between revisions

Revision as of 20:47, 11 June 2016

Revision as of 21:07, 11 June 2016

Line 1:

In [[computing]], a '''memory access pattern''' is the pattern over time and space with which a system ofor program accesses [[Memory (computing)|memory]]. These 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]] and distribution of workload 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.

== SequentialExamples ==

=== 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 ===

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