Memory access pattern: Difference between revisions

Revision as of 21:07, 11 June 2016

Revision as of 21:16, 11 June 2016

Line 8:

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 (mapping spatial regions onto cache lines), or by sorting primitives via [[tile based deferred rendering]].

=== Random ===

Line 19:

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

Sometimes reads and writes exhibit different access patterns. A series of random writes may scatter data ('pushing' to memory) without needing to pull in cache lines, producing data that is easier to access sequentially in a subsequent step.

Alternatively an algorithm may randomly 'gather' it's source data, whilst sequentially writing to it's destination (this foreknowledge can be exploited for parallelising ).