FazBrowse Wikipedia Viewer | Main Page |
Search Wikipedia:
|
Viewing: https://en.wikipedia.org/wiki/Memory_access_pattern

Memory access pattern

Contents
Approaches
    Data-oriented design
Contrast with locality of reference
See also
References

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

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 and programmers understand, analyse and improve the memory access pattern, including VTune and Vectorization Advisor, including tools to address GPU memory access patterns.

Memory access patterns also have implications for security, which motivates some to try to disguise a program's activity for privacy reasons.

At the opposite extreme is a truly random memory access pattern. A few multiprocessor systems are specialised to deal with these. 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). 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 prerequisite for parallelizing.

Approaches

edit

Data-oriented design

edit

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

Contrast with locality of reference

edit

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, and/or to increase potential for parallelism. 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.

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 dependencies; 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.

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

See also

edit

References

edit
    Jeffers, James; Reinders, James; Sodani, Avinash (2016-05-31). Intel Xeon Phi Processor High Performance Programming: Knights Landing Edition (2nd ed.). Morgan Kaufmann. ISBN 9780128091951.
  1. ↑ "intel terascale" (PDF).
  2. ↑ Che, Shuai; Sheaffer, Jeremy W.; Skadron, Kevin (2011-11-12). "Dymaxion: Optimizing memory access patterns for heterogeneous systems" (PDF). Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. SC '11. New York, NY, USA: Association for Computing Machinery. pp. 1–11. doi:10.1145/2063384.2063401. ISBN 978-1-4503-0771-0.
  3. ↑ "Putting Your Data and Code in Order: Data and layout".
  4. ↑ Rossi, Ben (2013-09-24). "Boosting cloud security with oblivious RAM". Information Age.
  5. ↑ Weinberg, Jonathan; McCracken, Michael O.; Snavely, Allan; Strohmaier, Erich (12–18 November 2005). "Quantifying Locality in the Memory Access Patterns of HPC Applications" ( (PDF)). ACM/IEEE SC 2005 Conference (SC'05). Seattle, WA, USA: IEEE. p. 50. doi:10.1109/SC.2005.59. ISBN 1-59593-061-2. Archived from the original on 2016-08-03. mentions nearest neighbor access patterns in clusters
  6. ↑ Harris, Mark (April 2005). "GPU Gems 2". 31.1.3 Stream Communication: Gather vs. Scatter. Archived from the original on 2016-06-14. Retrieved 2016-06-13.
  7. 1 2 3 "optimize-data-structures-and-memory-access-patterns-to-improve-data-locality".
  8. ↑
View original on Wikipedia | Back | FazBrowse Home