Memory access pattern: Difference between revisions

Revision as of 15:33, 13 June 2016

Revision as of 15:40, 13 June 2016

Line 29:

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

=== Combinations ===

==== random reads vs random writes ====

An algorithm may have inherently random and sequential components, and offer a choice of handling this through reads or writes, e.g. a sequential read combined with random writes (scatter), or random reads (gather) combined with sequential writes. These both have tradeoffs, e.g. scattered writes may bypass the need for [[caching]], as a [[processing element]] can dispatch the writes and move on without worrying about the latency. On the other hand, scattered writes may overlap, which makes parallelism harder. This consideration appears in GPGPU programming (where a GPU ). In the past, 'forward texture mapping' attempted to handle the randomness with 'writes', but the inverse approach is now more widespread.

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

==== random reads vs random writes ====

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

An task may have some inherent randomness, with alternative solutions where this is handled by random reads + sequential writes [[gather (vector addressing)|gather]] , or sequential reads plus random writes [[scatter (vector addressing)|scatter]]. The scatter approach may bypass the need for caching since a [[processing element]] may dispatch writes in a 'fire and forget' manner. However, it may be harder to parallelise since there is no guarantee the writes do not interact. As such the gather approach is more common for [[gpgpu]] programming.

Alternatively an algorithm may randomly [[gather (vector addressing)|gather]] it's source data, whilst sequentially writing to it's destination. This foreknowledge can be exploited for parallelising, and is usually preferable for [[GPU]] programming.

In the past, [[forward texture mapping]] attempted to handle the randomness with 'writes' (sequentially reading textures), but the inverse approach is now more widespread.