Memory access pattern - Revision history

David Eppstein: Barbara Chapman

2025-03-29T23:39:29Z

← Previous revision		Revision as of 23:39, 29 March 2025
Line 1:		Line 1:
	In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref name=":0">{{cite web \|title=Introduction to Data-Oriented Design \|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf \|url-status=dead \|archive-url=https://web.archive.org/web/20191116014412/http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf \|archive-date=2019-11-16}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book \|last1=Jeffers \|first1=James \|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231 \|title=Intel Xeon Phi Processor High Performance Programming: Knights Landing Edition \|last2=Reinders \|first2=James \|last3=Sodani \|first3=Avinash \|date=2016-05-31 \|publisher=Morgan Kaufmann \|isbn=9780128091951 \|edition=2nd}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{Cite book \|last1=Jana \|first1=Siddhartha \|last2=Schuchart \|first2=Joseph \|last3=Chapman \|first3=Barbara \|chapter=Analysis of Energy and Performance of PGAS-based Data Access Patterns \|date=2014-10-06 \|title=Proceedings of the 8th International Conference on Partitioned Global Address Space Programming Models \|chapter-url=https://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf \|series=PGAS '14 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=1–10 \|doi=10.1145/2676870.2676882 \|isbn=978-1-4503-3247-7}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{Cite book \|last1=Marandola \|first1=Jussara \|last2=Louise \|first2=Stéphane \|last3=Cudennec \|first3=Loïc \|last4=Acquaviva \|first4=Jean-Thomas \|last5=Bader \|first5=David \|chapter=Enhancing Cache Coherent Architectures with access patterns for embedded manycore systems \|date=2012-10-11 \|title=2012 International Symposium on System on Chip (SoC) \|chapter-url=https://inria.hal.science/hal-00741947v1 \|pages=1–7 \|language=en \|publisher=IEEE\|doi=10.1109/ISSoC.2012.6376369 \|isbn=978-1-4673-2896-8 \|url=https://hal.inria.fr/hal-00741947/file/SoC_2012.pdf }}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[Manycore processor\|manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>		In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref name=":0">{{cite web \|title=Introduction to Data-Oriented Design \|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf \|url-status=dead \|archive-url=https://web.archive.org/web/20191116014412/http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf \|archive-date=2019-11-16}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book \|last1=Jeffers \|first1=James \|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231 \|title=Intel Xeon Phi Processor High Performance Programming: Knights Landing Edition \|last2=Reinders \|first2=James \|last3=Sodani \|first3=Avinash \|date=2016-05-31 \|publisher=Morgan Kaufmann \|isbn=9780128091951 \|edition=2nd}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{Cite book \|last1=Jana \|first1=Siddhartha \|last2=Schuchart \|first2=Joseph \|last3=Chapman \|first3=Barbara\|author3-link=Barbara Chapman \|chapter=Analysis of Energy and Performance of PGAS-based Data Access Patterns \|date=2014-10-06 \|title=Proceedings of the 8th International Conference on Partitioned Global Address Space Programming Models \|chapter-url=https://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf \|series=PGAS '14 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=1–10 \|doi=10.1145/2676870.2676882 \|isbn=978-1-4503-3247-7}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{Cite book \|last1=Marandola \|first1=Jussara \|last2=Louise \|first2=Stéphane \|last3=Cudennec \|first3=Loïc \|last4=Acquaviva \|first4=Jean-Thomas \|last5=Bader \|first5=David \|chapter=Enhancing Cache Coherent Architectures with access patterns for embedded manycore systems \|date=2012-10-11 \|title=2012 International Symposium on System on Chip (SoC) \|chapter-url=https://inria.hal.science/hal-00741947v1 \|pages=1–7 \|language=en \|publisher=IEEE\|doi=10.1109/ISSoC.2012.6376369 \|isbn=978-1-4673-2896-8 \|url=https://hal.inria.fr/hal-00741947/file/SoC_2012.pdf }}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[Manycore processor\|manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>

	[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite book \|last1=Brown \|first1=Mary \|url=http://dl.acm.org/citation.cfm?id=838115 \|title=Memory Access Pattern Analysis \|last2=Jenevein \|first2=Roy M. \|last3=Ullah \|first3=Nasr \|date=29 November 1998 \|isbn=9780769504506 \|series=WWC '98: Proceedings of the Workload Characterization: Methodology and Case Studies \|publication-date=1998-11-29 \|page=105}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{Cite book \|last1=Ostadzadeh \|first1=S. Arash \|last2=Meeuws \|first2=Roel J. \|last3=Galuzzi \|first3=Carlo \|last4=Bertels \|first4=Koen \|chapter=QUAD – A Memory Access Pattern Analyser \|series=Lecture Notes in Computer Science \|date=2010 \|volume=5992 \|editor-last=Sirisuk \|editor-first=Phaophak \|editor2-last=Morgan \|editor2-first=Fearghal \|editor3-last=El-Ghazawi \|editor3-first=Tarek \|editor4-last=Amano \|editor4-first=Hideharu \|title=Reconfigurable Computing: Architectures, Tools and Applications \|chapter-url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf \|language=en \|location=Berlin, Heidelberg \|publisher=Springer \|pages=269–281 \|doi=10.1007/978-3-642-12133-3_25 \|isbn=978-3-642-12133-3}}</ref><ref>{{Cite book \|last1=Che \|first1=Shuai \|last2=Sheaffer \|first2=Jeremy W. \|last3=Skadron \|first3=Kevin \|chapter=Dymaxion: Optimizing memory access patterns for heterogeneous systems \|date=2011-11-12 \|title=Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis \|chapter-url=https://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf \|series=SC '11 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=1–11 \|doi=10.1145/2063384.2063401 \|isbn=978-1-4503-0771-0}}</ref><ref>{{Cite book \|last=Harrison \|first=Luddy \|chapter=Examination of a memory access classification scheme for pointer-intensive and numeric programs \|date=1996-01-01 \|title=Proceedings of the 10th international conference on Supercomputing - ICS '96 \|chapter-url=https://dl.acm.org/doi/10.1145/237578.237595 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=133–140 \|doi=10.1145/237578.237595 \|isbn=978-0-89791-803-9}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns.<ref>{{Cite book \|last1=Kim \|first1=Yooseong \|last2=Shrivastava \|first2=Aviral \|chapter=CuMAPz: A tool to analyze memory access patterns in CUDA \|date=2011-06-05 \|title=Proceedings of the 48th Design Automation Conference \|chapter-url=https://dl.acm.org/doi/10.1145/2024724.2024754 \|series=DAC '11 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=128–133 \|doi=10.1145/2024724.2024754 \|isbn=978-1-4503-0636-2}}</ref>		[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite book \|last1=Brown \|first1=Mary \|url=http://dl.acm.org/citation.cfm?id=838115 \|title=Memory Access Pattern Analysis \|last2=Jenevein \|first2=Roy M. \|last3=Ullah \|first3=Nasr \|date=29 November 1998 \|isbn=9780769504506 \|series=WWC '98: Proceedings of the Workload Characterization: Methodology and Case Studies \|publication-date=1998-11-29 \|page=105}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{Cite book \|last1=Ostadzadeh \|first1=S. Arash \|last2=Meeuws \|first2=Roel J. \|last3=Galuzzi \|first3=Carlo \|last4=Bertels \|first4=Koen \|chapter=QUAD – A Memory Access Pattern Analyser \|series=Lecture Notes in Computer Science \|date=2010 \|volume=5992 \|editor-last=Sirisuk \|editor-first=Phaophak \|editor2-last=Morgan \|editor2-first=Fearghal \|editor3-last=El-Ghazawi \|editor3-first=Tarek \|editor4-last=Amano \|editor4-first=Hideharu \|title=Reconfigurable Computing: Architectures, Tools and Applications \|chapter-url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf \|language=en \|location=Berlin, Heidelberg \|publisher=Springer \|pages=269–281 \|doi=10.1007/978-3-642-12133-3_25 \|isbn=978-3-642-12133-3}}</ref><ref>{{Cite book \|last1=Che \|first1=Shuai \|last2=Sheaffer \|first2=Jeremy W. \|last3=Skadron \|first3=Kevin \|chapter=Dymaxion: Optimizing memory access patterns for heterogeneous systems \|date=2011-11-12 \|title=Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis \|chapter-url=https://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf \|series=SC '11 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=1–11 \|doi=10.1145/2063384.2063401 \|isbn=978-1-4503-0771-0}}</ref><ref>{{Cite book \|last=Harrison \|first=Luddy \|chapter=Examination of a memory access classification scheme for pointer-intensive and numeric programs \|date=1996-01-01 \|title=Proceedings of the 10th international conference on Supercomputing - ICS '96 \|chapter-url=https://dl.acm.org/doi/10.1145/237578.237595 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=133–140 \|doi=10.1145/237578.237595 \|isbn=978-0-89791-803-9}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns.<ref>{{Cite book \|last1=Kim \|first1=Yooseong \|last2=Shrivastava \|first2=Aviral \|chapter=CuMAPz: A tool to analyze memory access patterns in CUDA \|date=2011-06-05 \|title=Proceedings of the 48th Design Automation Conference \|chapter-url=https://dl.acm.org/doi/10.1145/2024724.2024754 \|series=DAC '11 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=128–133 \|doi=10.1145/2024724.2024754 \|isbn=978-1-4503-0636-2}}</ref>

Rodw: Disambiguating links to Manycore (link changed to Manycore processor) using DisamAssist.

2025-02-25T08:06:50Z

Disambiguating links to Manycore (link changed to Manycore processor) using DisamAssist.

← Previous revision		Revision as of 08:06, 25 February 2025
Line 1:		Line 1:
	In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref name=":0">{{cite web \|title=Introduction to Data-Oriented Design \|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf \|url-status=dead \|archive-url=https://web.archive.org/web/20191116014412/http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf \|archive-date=2019-11-16}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book \|last1=Jeffers \|first1=James \|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231 \|title=Intel Xeon Phi Processor High Performance Programming: Knights Landing Edition \|last2=Reinders \|first2=James \|last3=Sodani \|first3=Avinash \|date=2016-05-31 \|publisher=Morgan Kaufmann \|isbn=9780128091951 \|edition=2nd}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{Cite book \|last1=Jana \|first1=Siddhartha \|last2=Schuchart \|first2=Joseph \|last3=Chapman \|first3=Barbara \|chapter=Analysis of Energy and Performance of PGAS-based Data Access Patterns \|date=2014-10-06 \|title=Proceedings of the 8th International Conference on Partitioned Global Address Space Programming Models \|chapter-url=https://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf \|series=PGAS '14 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=1–10 \|doi=10.1145/2676870.2676882 \|isbn=978-1-4503-3247-7}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{Cite book \|last1=Marandola \|first1=Jussara \|last2=Louise \|first2=Stéphane \|last3=Cudennec \|first3=Loïc \|last4=Acquaviva \|first4=Jean-Thomas \|last5=Bader \|first5=David \|chapter=Enhancing Cache Coherent Architectures with access patterns for embedded manycore systems \|date=2012-10-11 \|title=2012 International Symposium on System on Chip (SoC) \|chapter-url=https://inria.hal.science/hal-00741947v1 \|pages=1–7 \|language=en \|publisher=IEEE\|doi=10.1109/ISSoC.2012.6376369 \|isbn=978-1-4673-2896-8 \|url=https://hal.inria.fr/hal-00741947/file/SoC_2012.pdf }}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>		In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref name=":0">{{cite web \|title=Introduction to Data-Oriented Design \|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf \|url-status=dead \|archive-url=https://web.archive.org/web/20191116014412/http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf \|archive-date=2019-11-16}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book \|last1=Jeffers \|first1=James \|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231 \|title=Intel Xeon Phi Processor High Performance Programming: Knights Landing Edition \|last2=Reinders \|first2=James \|last3=Sodani \|first3=Avinash \|date=2016-05-31 \|publisher=Morgan Kaufmann \|isbn=9780128091951 \|edition=2nd}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{Cite book \|last1=Jana \|first1=Siddhartha \|last2=Schuchart \|first2=Joseph \|last3=Chapman \|first3=Barbara \|chapter=Analysis of Energy and Performance of PGAS-based Data Access Patterns \|date=2014-10-06 \|title=Proceedings of the 8th International Conference on Partitioned Global Address Space Programming Models \|chapter-url=https://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf \|series=PGAS '14 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=1–10 \|doi=10.1145/2676870.2676882 \|isbn=978-1-4503-3247-7}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{Cite book \|last1=Marandola \|first1=Jussara \|last2=Louise \|first2=Stéphane \|last3=Cudennec \|first3=Loïc \|last4=Acquaviva \|first4=Jean-Thomas \|last5=Bader \|first5=David \|chapter=Enhancing Cache Coherent Architectures with access patterns for embedded manycore systems \|date=2012-10-11 \|title=2012 International Symposium on System on Chip (SoC) \|chapter-url=https://inria.hal.science/hal-00741947v1 \|pages=1–7 \|language=en \|publisher=IEEE\|doi=10.1109/ISSoC.2012.6376369 \|isbn=978-1-4673-2896-8 \|url=https://hal.inria.fr/hal-00741947/file/SoC_2012.pdf }}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[Manycore processor\|manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>

	[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite book \|last1=Brown \|first1=Mary \|url=http://dl.acm.org/citation.cfm?id=838115 \|title=Memory Access Pattern Analysis \|last2=Jenevein \|first2=Roy M. \|last3=Ullah \|first3=Nasr \|date=29 November 1998 \|isbn=9780769504506 \|series=WWC '98: Proceedings of the Workload Characterization: Methodology and Case Studies \|publication-date=1998-11-29 \|page=105}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{Cite book \|last1=Ostadzadeh \|first1=S. Arash \|last2=Meeuws \|first2=Roel J. \|last3=Galuzzi \|first3=Carlo \|last4=Bertels \|first4=Koen \|chapter=QUAD – A Memory Access Pattern Analyser \|series=Lecture Notes in Computer Science \|date=2010 \|volume=5992 \|editor-last=Sirisuk \|editor-first=Phaophak \|editor2-last=Morgan \|editor2-first=Fearghal \|editor3-last=El-Ghazawi \|editor3-first=Tarek \|editor4-last=Amano \|editor4-first=Hideharu \|title=Reconfigurable Computing: Architectures, Tools and Applications \|chapter-url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf \|language=en \|location=Berlin, Heidelberg \|publisher=Springer \|pages=269–281 \|doi=10.1007/978-3-642-12133-3_25 \|isbn=978-3-642-12133-3}}</ref><ref>{{Cite book \|last1=Che \|first1=Shuai \|last2=Sheaffer \|first2=Jeremy W. \|last3=Skadron \|first3=Kevin \|chapter=Dymaxion: Optimizing memory access patterns for heterogeneous systems \|date=2011-11-12 \|title=Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis \|chapter-url=https://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf \|series=SC '11 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=1–11 \|doi=10.1145/2063384.2063401 \|isbn=978-1-4503-0771-0}}</ref><ref>{{Cite book \|last=Harrison \|first=Luddy \|chapter=Examination of a memory access classification scheme for pointer-intensive and numeric programs \|date=1996-01-01 \|title=Proceedings of the 10th international conference on Supercomputing - ICS '96 \|chapter-url=https://dl.acm.org/doi/10.1145/237578.237595 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=133–140 \|doi=10.1145/237578.237595 \|isbn=978-0-89791-803-9}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns.<ref>{{Cite book \|last1=Kim \|first1=Yooseong \|last2=Shrivastava \|first2=Aviral \|chapter=CuMAPz: A tool to analyze memory access patterns in CUDA \|date=2011-06-05 \|title=Proceedings of the 48th Design Automation Conference \|chapter-url=https://dl.acm.org/doi/10.1145/2024724.2024754 \|series=DAC '11 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=128–133 \|doi=10.1145/2024724.2024754 \|isbn=978-1-4503-0636-2}}</ref>		[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite book \|last1=Brown \|first1=Mary \|url=http://dl.acm.org/citation.cfm?id=838115 \|title=Memory Access Pattern Analysis \|last2=Jenevein \|first2=Roy M. \|last3=Ullah \|first3=Nasr \|date=29 November 1998 \|isbn=9780769504506 \|series=WWC '98: Proceedings of the Workload Characterization: Methodology and Case Studies \|publication-date=1998-11-29 \|page=105}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{Cite book \|last1=Ostadzadeh \|first1=S. Arash \|last2=Meeuws \|first2=Roel J. \|last3=Galuzzi \|first3=Carlo \|last4=Bertels \|first4=Koen \|chapter=QUAD – A Memory Access Pattern Analyser \|series=Lecture Notes in Computer Science \|date=2010 \|volume=5992 \|editor-last=Sirisuk \|editor-first=Phaophak \|editor2-last=Morgan \|editor2-first=Fearghal \|editor3-last=El-Ghazawi \|editor3-first=Tarek \|editor4-last=Amano \|editor4-first=Hideharu \|title=Reconfigurable Computing: Architectures, Tools and Applications \|chapter-url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf \|language=en \|location=Berlin, Heidelberg \|publisher=Springer \|pages=269–281 \|doi=10.1007/978-3-642-12133-3_25 \|isbn=978-3-642-12133-3}}</ref><ref>{{Cite book \|last1=Che \|first1=Shuai \|last2=Sheaffer \|first2=Jeremy W. \|last3=Skadron \|first3=Kevin \|chapter=Dymaxion: Optimizing memory access patterns for heterogeneous systems \|date=2011-11-12 \|title=Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis \|chapter-url=https://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf \|series=SC '11 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=1–11 \|doi=10.1145/2063384.2063401 \|isbn=978-1-4503-0771-0}}</ref><ref>{{Cite book \|last=Harrison \|first=Luddy \|chapter=Examination of a memory access classification scheme for pointer-intensive and numeric programs \|date=1996-01-01 \|title=Proceedings of the 10th international conference on Supercomputing - ICS '96 \|chapter-url=https://dl.acm.org/doi/10.1145/237578.237595 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=133–140 \|doi=10.1145/237578.237595 \|isbn=978-0-89791-803-9}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns.<ref>{{Cite book \|last1=Kim \|first1=Yooseong \|last2=Shrivastava \|first2=Aviral \|chapter=CuMAPz: A tool to analyze memory access patterns in CUDA \|date=2011-06-05 \|title=Proceedings of the 48th Design Automation Conference \|chapter-url=https://dl.acm.org/doi/10.1145/2024724.2024754 \|series=DAC '11 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=128–133 \|doi=10.1145/2024724.2024754 \|isbn=978-1-4503-0636-2}}</ref>

Citation bot: Alter: title, url, template type. URLs might have been anonymized. Add: publisher, chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 111/365

2024-11-23T19:47:30Z

Alter: title, url, template type. URLs might have been anonymized. Add: publisher, chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 111/365

← Previous revision		Revision as of 19:47, 23 November 2024
Line 1:		Line 1:
	In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref name=":0">{{cite web \|title=Introduction to Data-Oriented Design \|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf \|url-status=dead \|archive-url=https://web.archive.org/web/20191116014412/http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf \|archive-date=2019-11-16}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book \|last1=Jeffers \|first1=James \|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231 \|title=Intel Xeon Phi Processor High Performance Programming: Knights Landing Edition \|last2=Reinders \|first2=James \|last3=Sodani \|first3=Avinash \|date=2016-05-31 \|publisher=Morgan Kaufmann \|isbn=9780128091951 \|edition=2nd}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{Cite book \|last1=Jana \|first1=Siddhartha \|last2=Schuchart \|first2=Joseph \|last3=Chapman \|first3=Barbara \|chapter=Analysis of Energy and Performance of PGAS-based Data Access Patterns \|date=2014-10-06 \|title=Proceedings of the 8th International Conference on Partitioned Global Address Space Programming Models \|chapter-url=https://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf \|series=PGAS '14 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=1–10 \|doi=10.1145/2676870.2676882 \|isbn=978-1-4503-3247-7}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{Cite ~~journal~~ \|last1=Marandola \|first1=Jussara \|last2=Louise \|first2=Stéphane \|last3=Cudennec \|first3=Loïc \|last4=Acquaviva \|first4=Jean-Thomas \|last5=Bader \|first5=David \|date=2012-10-11 \|title=~~Enhancing~~ ~~Cache~~ ~~Coherent~~ ~~Architectures~~ ~~with~~ ~~Access~~ ~~Patterns~~ ~~for Embedded Manycore Systems~~ \|url=https://inria.hal.science/hal-00741947v1 ~~\|journal=International Symposium on System-on-Chip 2012~~ \|pages=1–7 \|language=en \|publisher=IEEE\|doi=10.1109/ISSoC.2012.6376369 \|isbn=978-1-4673-2896-8 }}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>		In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref name=":0">{{cite web \|title=Introduction to Data-Oriented Design \|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf \|url-status=dead \|archive-url=https://web.archive.org/web/20191116014412/http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf \|archive-date=2019-11-16}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book \|last1=Jeffers \|first1=James \|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231 \|title=Intel Xeon Phi Processor High Performance Programming: Knights Landing Edition \|last2=Reinders \|first2=James \|last3=Sodani \|first3=Avinash \|date=2016-05-31 \|publisher=Morgan Kaufmann \|isbn=9780128091951 \|edition=2nd}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{Cite book \|last1=Jana \|first1=Siddhartha \|last2=Schuchart \|first2=Joseph \|last3=Chapman \|first3=Barbara \|chapter=Analysis of Energy and Performance of PGAS-based Data Access Patterns \|date=2014-10-06 \|title=Proceedings of the 8th International Conference on Partitioned Global Address Space Programming Models \|chapter-url=https://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf \|series=PGAS '14 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=1–10 \|doi=10.1145/2676870.2676882 \|isbn=978-1-4503-3247-7}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{Cite book \|last1=Marandola \|first1=Jussara \|last2=Louise \|first2=Stéphane \|last3=Cudennec \|first3=Loïc \|last4=Acquaviva \|first4=Jean-Thomas \|last5=Bader \|first5=David \|chapter=Enhancing Cache Coherent Architectures with access patterns for embedded manycore systems \|date=2012-10-11 \|title=2012 International Symposium on System on Chip (SoC) \|chapter-url=https://inria.hal.science/hal-00741947v1 \|pages=1–7 \|language=en \|publisher=IEEE\|doi=10.1109/ISSoC.2012.6376369 \|isbn=978-1-4673-2896-8 \|url=https://hal.inria.fr/hal-00741947/file/SoC_2012.pdf }}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>

	[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite book \|last1=Brown \|first1=Mary \|url=http://dl.acm.org/citation.cfm?id=838115 \|title=Memory Access Pattern Analysis \|last2=Jenevein \|first2=Roy M. \|last3=Ullah \|first3=Nasr \|date=29 November 1998 \|isbn=9780769504506 \|series=WWC '98: Proceedings of the Workload Characterization: Methodology and Case Studies \|publication-date=1998-11-29 \|page=105}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{Cite book \|last1=Ostadzadeh \|first1=S. Arash \|last2=Meeuws \|first2=Roel J. \|last3=Galuzzi \|first3=Carlo \|last4=Bertels \|first4=Koen \|chapter=QUAD – A Memory Access Pattern Analyser \|series=Lecture Notes in Computer Science \|date=2010 \|volume=5992 \|editor-last=Sirisuk \|editor-first=Phaophak \|editor2-last=Morgan \|editor2-first=Fearghal \|editor3-last=El-Ghazawi \|editor3-first=Tarek \|editor4-last=Amano \|editor4-first=Hideharu \|title=Reconfigurable Computing: Architectures, Tools and Applications \|chapter-url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf \|language=en \|location=Berlin, Heidelberg \|publisher=Springer \|pages=269–281 \|doi=10.1007/978-3-642-12133-3_25 \|isbn=978-3-642-12133-3}}</ref><ref>{{Cite book \|last1=Che \|first1=Shuai \|last2=Sheaffer \|first2=Jeremy W. \|last3=Skadron \|first3=Kevin \|chapter=Dymaxion: Optimizing memory access patterns for heterogeneous systems \|date=2011-11-12 \|title=Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis \|chapter-url=https://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf \|series=SC '11 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=1–11 \|doi=10.1145/2063384.2063401 \|isbn=978-1-4503-0771-0}}</ref><ref>{{Cite book \|last=Harrison \|first=Luddy \|chapter=Examination of a memory access classification scheme for pointer-intensive and numeric programs \|date=1996-01-01 \|title=Proceedings of the 10th international conference on Supercomputing - ICS '96 \|chapter-url=https://dl.acm.org/doi/10.1145/237578.237595 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=133–140 \|doi=10.1145/237578.237595 \|isbn=978-0-89791-803-9}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns.<ref>{{Cite book \|last1=Kim \|first1=Yooseong \|last2=Shrivastava \|first2=Aviral \|chapter=CuMAPz: A tool to analyze memory access patterns in CUDA \|date=2011-06-05 \|title=Proceedings of the 48th Design Automation Conference \|chapter-url=https://dl.acm.org/doi/10.1145/2024724.2024754 \|series=DAC '11 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=128–133 \|doi=10.1145/2024724.2024754 \|isbn=978-1-4503-0636-2}}</ref>		[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite book \|last1=Brown \|first1=Mary \|url=http://dl.acm.org/citation.cfm?id=838115 \|title=Memory Access Pattern Analysis \|last2=Jenevein \|first2=Roy M. \|last3=Ullah \|first3=Nasr \|date=29 November 1998 \|isbn=9780769504506 \|series=WWC '98: Proceedings of the Workload Characterization: Methodology and Case Studies \|publication-date=1998-11-29 \|page=105}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{Cite book \|last1=Ostadzadeh \|first1=S. Arash \|last2=Meeuws \|first2=Roel J. \|last3=Galuzzi \|first3=Carlo \|last4=Bertels \|first4=Koen \|chapter=QUAD – A Memory Access Pattern Analyser \|series=Lecture Notes in Computer Science \|date=2010 \|volume=5992 \|editor-last=Sirisuk \|editor-first=Phaophak \|editor2-last=Morgan \|editor2-first=Fearghal \|editor3-last=El-Ghazawi \|editor3-first=Tarek \|editor4-last=Amano \|editor4-first=Hideharu \|title=Reconfigurable Computing: Architectures, Tools and Applications \|chapter-url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf \|language=en \|location=Berlin, Heidelberg \|publisher=Springer \|pages=269–281 \|doi=10.1007/978-3-642-12133-3_25 \|isbn=978-3-642-12133-3}}</ref><ref>{{Cite book \|last1=Che \|first1=Shuai \|last2=Sheaffer \|first2=Jeremy W. \|last3=Skadron \|first3=Kevin \|chapter=Dymaxion: Optimizing memory access patterns for heterogeneous systems \|date=2011-11-12 \|title=Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis \|chapter-url=https://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf \|series=SC '11 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=1–11 \|doi=10.1145/2063384.2063401 \|isbn=978-1-4503-0771-0}}</ref><ref>{{Cite book \|last=Harrison \|first=Luddy \|chapter=Examination of a memory access classification scheme for pointer-intensive and numeric programs \|date=1996-01-01 \|title=Proceedings of the 10th international conference on Supercomputing - ICS '96 \|chapter-url=https://dl.acm.org/doi/10.1145/237578.237595 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=133–140 \|doi=10.1145/237578.237595 \|isbn=978-0-89791-803-9}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns.<ref>{{Cite book \|last1=Kim \|first1=Yooseong \|last2=Shrivastava \|first2=Aviral \|chapter=CuMAPz: A tool to analyze memory access patterns in CUDA \|date=2011-06-05 \|title=Proceedings of the 48th Design Automation Conference \|chapter-url=https://dl.acm.org/doi/10.1145/2024724.2024754 \|series=DAC '11 \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=128–133 \|doi=10.1145/2024724.2024754 \|isbn=978-1-4503-0636-2}}</ref>
Line 13:		Line 13:

	=== Strided ===		=== Strided ===
	[[Stride (computing)\|Strided]] or simple 2D, 3D access patterns (e.g., stepping through [[multi-dimensional array]]s) are similarly easy to predict, and are found in implementations of [[linear algebra]] algorithms and [[image processing]]. [[Loop tiling]] is an effective approach.<ref>{{Cite book \|last1=Kennedy \|first1=Ken \|last2=McKinley \|first2=Kathryn S. \|chapter=Optimizing for parallelism and data locality \|date=1992-08-01 \|title=Proceedings of the 6th international conference on Supercomputing - ICS '92 \|chapter-url=https://www.cs.utexas.edu/~mckinley/papers/par-mem-ics-92.pdf \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=323–334 \|doi=10.1145/143369.143427 \|isbn=978-0-89791-485-7}}</ref> Some systems with [[Direct memory access\|DMA]] provided a strided mode for transferring data between subtile of larger [[2D array]]s and [[scratchpad memory]].<ref>{{Cite ~~journal~~ \|last1=Saidi \|first1=Selma \|last2=Tendulkar \|first2=P. \|last3=Lepley \|first3=Thierry \|last4=Maler \|first4=O. \|~~date=2012 \|title~~=Optimal 2D Data Partitioning for DMA Transfers on MPSoCs \|url=https://www-verimag.imag.fr/~maler/Papers/dma2dim.pdf ~~\|journal=2012 15th Euromicro Conference on Digital System Design~~ \|pages=584–591 \|language=en \|publisher=IEEE\|doi=10.1109/DSD.2012.99 \|isbn=978-0-7695-4798-5 }}</ref>		[[Stride (computing)\|Strided]] or simple 2D, 3D access patterns (e.g., stepping through [[multi-dimensional array]]s) are similarly easy to predict, and are found in implementations of [[linear algebra]] algorithms and [[image processing]]. [[Loop tiling]] is an effective approach.<ref>{{Cite book \|last1=Kennedy \|first1=Ken \|last2=McKinley \|first2=Kathryn S. \|chapter=Optimizing for parallelism and data locality \|date=1992-08-01 \|title=Proceedings of the 6th international conference on Supercomputing - ICS '92 \|chapter-url=https://www.cs.utexas.edu/~mckinley/papers/par-mem-ics-92.pdf \|location=New York, NY, USA \|publisher=Association for Computing Machinery \|pages=323–334 \|doi=10.1145/143369.143427 \|isbn=978-0-89791-485-7}}</ref> Some systems with [[Direct memory access\|DMA]] provided a strided mode for transferring data between subtile of larger [[2D array]]s and [[scratchpad memory]].<ref>{{Cite book \|last1=Saidi \|first1=Selma \|last2=Tendulkar \|first2=P. \|last3=Lepley \|first3=Thierry \|last4=Maler \|first4=O. \|chapter=Optimal 2D Data Partitioning for DMA Transfers on MPSoCs \|date=2012 \|title=2012 15th Euromicro Conference on Digital System Design \|chapter-url=https://www-verimag.imag.fr/~maler/Papers/dma2dim.pdf \|pages=584–591 \|language=en \|publisher=IEEE\|doi=10.1109/DSD.2012.99 \|isbn=978-0-7695-4798-5 }}</ref>

	=== Linear ===		=== Linear ===
Line 37:		Line 37:
	In a [[gather (vector addressing)\|gather]] memory access pattern, reads are randomly addressed or indexed, whilst the writes are sequential (or linear).<ref name="gpu gems2"/> An example is found in [[inverse texture mapping]], where data can be written out linearly across [[scan line]]s, whilst random access texture addresses are calculated per [[pixel]].		In a [[gather (vector addressing)\|gather]] memory access pattern, reads are randomly addressed or indexed, whilst the writes are sequential (or linear).<ref name="gpu gems2"/> An example is found in [[inverse texture mapping]], where data can be written out linearly across [[scan line]]s, whilst random access texture addresses are calculated per [[pixel]].

	Compared to scatter, the disadvantage is that caching (and bypassing latencies) is now essential for efficient reads of small elements, however it is easier to parallelise since the writes are guaranteed to not overlap. As such the gather approach is more common for [[gpgpu]] programming,<ref name="gpu gems"/> where the massive threading (enabled by parallelism) is used to hide read latencies.<ref name = "gpu gems">{{cite book\|title = GPU gems\|url=https://books.google.com/books?id=lGMzmbUhpiAC&q=scatter+memory+access+pattern&pg=PA51\|isbn = 9780123849892\|date = 2011-01-13}}deals with "scatter memory access patterns" and "gather memory access patterns" in the text</ref>		Compared to scatter, the disadvantage is that caching (and bypassing latencies) is now essential for efficient reads of small elements, however it is easier to parallelise since the writes are guaranteed to not overlap. As such the gather approach is more common for [[gpgpu]] programming,<ref name="gpu gems"/> where the massive threading (enabled by parallelism) is used to hide read latencies.<ref name = "gpu gems">{{cite book\|title = GPU gems\|url=https://books.google.com/books?id=lGMzmbUhpiAC&q=scatter+memory+access+pattern&pg=PA51\|isbn = 9780123849892\|date = 2011-01-13\| publisher=Elsevier }}deals with "scatter memory access patterns" and "gather memory access patterns" in the text</ref>

	=== Combined gather and scatter ===		=== Combined gather and scatter ===

Citation bot: Alter: title, template type, url. URLs might have been anonymized. Add: s2cid, page, volume, series, isbn, doi, pages, chapter-url, chapter, authors 1-1. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Software optimization | #UCB_Category 36/59

2024-11-03T01:32:34Z

Alter: title, template type, url. URLs might have been anonymized. Add: s2cid, page, volume, series, isbn, doi, pages, chapter-url, chapter, authors 1-1. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Software optimization | #UCB_Category 36/59

Show changes

Naruyoko: Improve inline citation

2024-11-02T04:35:52Z

Improve inline citation

Show changes

Maxeto0910: period after sentence

2023-04-08T15:46:43Z

period after sentence

← Previous revision		Revision as of 15:46, 8 April 2023
Line 6:		Line 6:

	== Examples ==		== Examples ==
	[[File:Random vs sequential access.svg\|thumb\|right\| ''Sequential'' and ''Linear'' patterns are incorrectly drawn as counterparts to each other by some publications; while real-world [[workloads]] contain almost innumerable patterns<ref>{{cite web\|author1=Chuck Paridon\|title=Storage Performance Benchmarking Guidelines - Part I: Workload Design\|url=http://www.snia.org/sites/default/files/PerformanceBenchmarking.Nov2010.pdf\|quote=In practice, IO access patterns are as numerous as the stars}}</ref>]]		[[File:Random vs sequential access.svg\|thumb\|right\| ''Sequential'' and ''Linear'' patterns are incorrectly drawn as counterparts to each other by some publications; while real-world [[workloads]] contain almost innumerable patterns.<ref>{{cite web\|author1=Chuck Paridon\|title=Storage Performance Benchmarking Guidelines - Part I: Workload Design\|url=http://www.snia.org/sites/default/files/PerformanceBenchmarking.Nov2010.pdf\|quote=In practice, IO access patterns are as numerous as the stars}}</ref>]]

	=== Sequential ===		=== Sequential ===

Tea2min: /* top */ Use existing redirect.

2022-01-05T06:04:39Z

top: Use existing redirect.

← Previous revision		Revision as of 06:04, 5 January 2022
Line 1:		Line 1:
	In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[~~Computer data storage\|~~secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref>{{cite web\|title = data oriented design\|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book\|title=xeon phi optimization\|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231\|isbn = 9780128091951\|last1 = Jeffers\|first1 = James\|last2 = Reinders\|first2 = James\|last3 = Sodani\|first3 = Avinash\|date = 2016-05-31}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{cite web\|title=Analysis of Energy and Performance of Code Transformations for PGAS-based Data Access Patterns\|url=http://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{cite web\|title=enhancing cache coherent architectures with memory access patterns for embedded many-core systems\|url=http://www.cc.gatech.edu/~bader/papers/EnhancingCache-SoC12.pdf}}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>		In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref>{{cite web\|title = data oriented design\|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book\|title=xeon phi optimization\|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231\|isbn = 9780128091951\|last1 = Jeffers\|first1 = James\|last2 = Reinders\|first2 = James\|last3 = Sodani\|first3 = Avinash\|date = 2016-05-31}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{cite web\|title=Analysis of Energy and Performance of Code Transformations for PGAS-based Data Access Patterns\|url=http://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{cite web\|title=enhancing cache coherent architectures with memory access patterns for embedded many-core systems\|url=http://www.cc.gatech.edu/~bader/papers/EnhancingCache-SoC12.pdf}}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>

	[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite book\|title=analysis of memory access patterns\|series = WWC '98\|date = 29 November 1998\|page = 105\|isbn = 9780769504506\|url=http://dl.acm.org/citation.cfm?id=838115}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{cite web\|title=QUAD a memory access pattern analyser\|url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf}}</ref><ref>{{cite web\|title=Dymaxion: Optimizing Memory Access Patterns for Heterogeneous Systems\|url=http://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf}}</ref><ref>{{cite journal\|title=evaluation of a memory access classification scheme for pointer intensive and numeric programs\|year=1996\|citeseerx=10.1.1.48.4163}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns<ref>{{cite book\|title=CuMAPz: a tool to analyze memory access patterns in CUDA\|series = Dac '11\|date = 5 June 2011\|pages = 128–133\|doi = 10.1145/2024724.2024754\|isbn = 9781450306362\|s2cid = 16065152\|url=http://dl.acm.org/citation.cfm?id=2024754}}</ref>		[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite book\|title=analysis of memory access patterns\|series = WWC '98\|date = 29 November 1998\|page = 105\|isbn = 9780769504506\|url=http://dl.acm.org/citation.cfm?id=838115}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{cite web\|title=QUAD a memory access pattern analyser\|url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf}}</ref><ref>{{cite web\|title=Dymaxion: Optimizing Memory Access Patterns for Heterogeneous Systems\|url=http://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf}}</ref><ref>{{cite journal\|title=evaluation of a memory access classification scheme for pointer intensive and numeric programs\|year=1996\|citeseerx=10.1.1.48.4163}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns<ref>{{cite book\|title=CuMAPz: a tool to analyze memory access patterns in CUDA\|series = Dac '11\|date = 5 June 2011\|pages = 128–133\|doi = 10.1145/2024724.2024754\|isbn = 9781450306362\|s2cid = 16065152\|url=http://dl.acm.org/citation.cfm?id=2024754}}</ref>

151.201.147.213 at 09:46, 4 January 2022

2022-01-04T09:46:11Z

← Previous revision		Revision as of 09:46, 4 January 2022
Line 1:		Line 1:
	In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[Computer data ~~storage#Secondary~~ storage\|secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref>{{cite web\|title = data oriented design\|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book\|title=xeon phi optimization\|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231\|isbn = 9780128091951\|last1 = Jeffers\|first1 = James\|last2 = Reinders\|first2 = James\|last3 = Sodani\|first3 = Avinash\|date = 2016-05-31}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{cite web\|title=Analysis of Energy and Performance of Code Transformations for PGAS-based Data Access Patterns\|url=http://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{cite web\|title=enhancing cache coherent architectures with memory access patterns for embedded many-core systems\|url=http://www.cc.gatech.edu/~bader/papers/EnhancingCache-SoC12.pdf}}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>		In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[Computer data storage\|secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref>{{cite web\|title = data oriented design\|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book\|title=xeon phi optimization\|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231\|isbn = 9780128091951\|last1 = Jeffers\|first1 = James\|last2 = Reinders\|first2 = James\|last3 = Sodani\|first3 = Avinash\|date = 2016-05-31}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{cite web\|title=Analysis of Energy and Performance of Code Transformations for PGAS-based Data Access Patterns\|url=http://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{cite web\|title=enhancing cache coherent architectures with memory access patterns for embedded many-core systems\|url=http://www.cc.gatech.edu/~bader/papers/EnhancingCache-SoC12.pdf}}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>

	[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite book\|title=analysis of memory access patterns\|series = WWC '98\|date = 29 November 1998\|page = 105\|isbn = 9780769504506\|url=http://dl.acm.org/citation.cfm?id=838115}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{cite web\|title=QUAD a memory access pattern analyser\|url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf}}</ref><ref>{{cite web\|title=Dymaxion: Optimizing Memory Access Patterns for Heterogeneous Systems\|url=http://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf}}</ref><ref>{{cite journal\|title=evaluation of a memory access classification scheme for pointer intensive and numeric programs\|year=1996\|citeseerx=10.1.1.48.4163}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns<ref>{{cite book\|title=CuMAPz: a tool to analyze memory access patterns in CUDA\|series = Dac '11\|date = 5 June 2011\|pages = 128–133\|doi = 10.1145/2024724.2024754\|isbn = 9781450306362\|s2cid = 16065152\|url=http://dl.acm.org/citation.cfm?id=2024754}}</ref>		[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite book\|title=analysis of memory access patterns\|series = WWC '98\|date = 29 November 1998\|page = 105\|isbn = 9780769504506\|url=http://dl.acm.org/citation.cfm?id=838115}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{cite web\|title=QUAD a memory access pattern analyser\|url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf}}</ref><ref>{{cite web\|title=Dymaxion: Optimizing Memory Access Patterns for Heterogeneous Systems\|url=http://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf}}</ref><ref>{{cite journal\|title=evaluation of a memory access classification scheme for pointer intensive and numeric programs\|year=1996\|citeseerx=10.1.1.48.4163}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns<ref>{{cite book\|title=CuMAPz: a tool to analyze memory access patterns in CUDA\|series = Dac '11\|date = 5 June 2011\|pages = 128–133\|doi = 10.1145/2024724.2024754\|isbn = 9781450306362\|s2cid = 16065152\|url=http://dl.acm.org/citation.cfm?id=2024754}}</ref>

Citation bot: Alter: template type. Add: website, s2cid, doi, pages, year, isbn, page, date, series. | Use this bot. Report bugs. | Suggested by Abductive | Category:Software optimization | #UCB_Category 39/61

2021-10-30T16:26:48Z

Alter: template type. Add: website, s2cid, doi, pages, year, isbn, page, date, series. | Use this bot. Report bugs. | Suggested by Abductive | Category:Software optimization | #UCB_Category 39/61

← Previous revision		Revision as of 16:26, 30 October 2021
Line 1:		Line 1:
	In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[Computer data storage#Secondary storage\|secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref>{{cite web\|title = data oriented design\|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book\|title=xeon phi optimization\|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231\|isbn = 9780128091951\|last1 = Jeffers\|first1 = James\|last2 = Reinders\|first2 = James\|last3 = Sodani\|first3 = Avinash\|date = 2016-05-31}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{cite web\|title=Analysis of Energy and Performance of Code Transformations for PGAS-based Data Access Patterns\|url=http://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{cite web\|title=enhancing cache coherent architectures with memory access patterns for embedded many-core systems\|url=http://www.cc.gatech.edu/~bader/papers/EnhancingCache-SoC12.pdf}}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>		In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[Computer data storage#Secondary storage\|secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref>{{cite web\|title = data oriented design\|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book\|title=xeon phi optimization\|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231\|isbn = 9780128091951\|last1 = Jeffers\|first1 = James\|last2 = Reinders\|first2 = James\|last3 = Sodani\|first3 = Avinash\|date = 2016-05-31}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{cite web\|title=Analysis of Energy and Performance of Code Transformations for PGAS-based Data Access Patterns\|url=http://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{cite web\|title=enhancing cache coherent architectures with memory access patterns for embedded many-core systems\|url=http://www.cc.gatech.edu/~bader/papers/EnhancingCache-SoC12.pdf}}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>

	[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite ~~web~~\|title=analysis of memory access patterns\|url=http://dl.acm.org/citation.cfm?id=838115}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{cite web\|title=QUAD a memory access pattern analyser\|url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf}}</ref><ref>{{cite web\|title=Dymaxion: Optimizing Memory Access Patterns for Heterogeneous Systems\|url=http://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf}}</ref><ref>{{cite journal\|title=evaluation of a memory access classification scheme for pointer intensive and numeric programs\|citeseerx=10.1.1.48.4163}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns<ref>{{cite ~~web~~\|title=CuMAPz: a tool to analyze memory access patterns in CUDA\|url=http://dl.acm.org/citation.cfm?id=2024754}}</ref>		[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite book\|title=analysis of memory access patterns\|series = WWC '98\|date = 29 November 1998\|page = 105\|isbn = 9780769504506\|url=http://dl.acm.org/citation.cfm?id=838115}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{cite web\|title=QUAD a memory access pattern analyser\|url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf}}</ref><ref>{{cite web\|title=Dymaxion: Optimizing Memory Access Patterns for Heterogeneous Systems\|url=http://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf}}</ref><ref>{{cite journal\|title=evaluation of a memory access classification scheme for pointer intensive and numeric programs\|year=1996\|citeseerx=10.1.1.48.4163}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns<ref>{{cite book\|title=CuMAPz: a tool to analyze memory access patterns in CUDA\|series = Dac '11\|date = 5 June 2011\|pages = 128–133\|doi = 10.1145/2024724.2024754\|isbn = 9781450306362\|s2cid = 16065152\|url=http://dl.acm.org/citation.cfm?id=2024754}}</ref>

	Memory access patterns also have implications for [[security (computing)\|security]],<ref>{{cite web\|title=Memory Access Pattern Protection for Resource-constrained Devices\|url=https://www.cardis.org/proceedings/cardis_2012/CARDIS2012_14.pdf}}</ref><ref>{{cite web\|title=understanding cache attacks\|url=https://www.rocq.inria.fr/secret/Anne.Canteaut/Publications/RR-5881.pdf}}</ref> which motivates some to try and disguise a program's activity for [[Privacy (computing)\|privacy]] reasons.<ref>{{cite web\|title=protecting data in the cloud\|url=https://news.mit.edu/2013/protecting-data-in-the-cloud-0702}}</ref><ref>{{cite web\|title=boosting-cloud-security-with----oblivious-ram\|url=http://www.information-age.com/technology/security/123457364/boosting-cloud-security-with----oblivious-ram---}}proposed RAM design avoiding memory-access-pattern vulnerabilities</ref>		Memory access patterns also have implications for [[security (computing)\|security]],<ref>{{cite web\|title=Memory Access Pattern Protection for Resource-constrained Devices\|url=https://www.cardis.org/proceedings/cardis_2012/CARDIS2012_14.pdf}}</ref><ref>{{cite web\|title=understanding cache attacks\|url=https://www.rocq.inria.fr/secret/Anne.Canteaut/Publications/RR-5881.pdf}}</ref> which motivates some to try and disguise a program's activity for [[Privacy (computing)\|privacy]] reasons.<ref>{{cite web\|title=protecting data in the cloud\|url=https://news.mit.edu/2013/protecting-data-in-the-cloud-0702}}</ref><ref>{{cite web\|title=boosting-cloud-security-with----oblivious-ram\|date=24 September 2013\|url=http://www.information-age.com/technology/security/123457364/boosting-cloud-security-with----oblivious-ram---}}proposed RAM design avoiding memory-access-pattern vulnerabilities</ref>

	== Examples ==		== Examples ==
Line 45:		Line 45:
	=== Random ===		=== Random ===
	{{main\|Random access}}		{{main\|Random access}}
	At the opposite extreme is a truly random memory access pattern. A few multiprocessor systems are specialised to deal with these.<ref>{{cite web\|title=Cray and HPCC: Benchmark Developments and Results from the Past Year\|url=https://cug.org/5-publications/proceedings_attendee_lists/2005CD/S05_Proceedings/pages/Authors/Wichmann/Wichmann_paper.pdf}}see global random access results for Cray X1. vector architecture for hiding latencies, not so sensitive to cache coherency</ref> The [[Partitioned 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).<ref name="PGAS programming">{{cite web\|title=partitioned global address space programming\|url=https://www.youtube.com/watch?v=NU4VfjISk2M}}covers cases where PGAS is a win, where data may not be already sorted, e.g., dealing with complex graphs - see "science across the irregularity spectrum".</ref> 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 [[Parallel computing\|parallelizing]].		At the opposite extreme is a truly random memory access pattern. A few multiprocessor systems are specialised to deal with these.<ref>{{cite web\|title=Cray and HPCC: Benchmark Developments and Results from the Past Year\|url=https://cug.org/5-publications/proceedings_attendee_lists/2005CD/S05_Proceedings/pages/Authors/Wichmann/Wichmann_paper.pdf}}see global random access results for Cray X1. vector architecture for hiding latencies, not so sensitive to cache coherency</ref> The [[Partitioned 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).<ref name="PGAS programming">{{cite web\|title=partitioned global address space programming\|website = [[YouTube]]\|url=https://www.youtube.com/watch?v=NU4VfjISk2M}}covers cases where PGAS is a win, where data may not be already sorted, e.g., dealing with complex graphs - see "science across the irregularity spectrum".</ref> 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 [[Parallel computing\|parallelizing]].

	== Approaches ==		== Approaches ==

Citation bot: Alter: url. URLs might have been internationalized/anonymized. Add: s2cid. | You can use this bot yourself. Report bugs here. | Suggested by AManWithNoPlan | All pages linked from cached copy of User:AManWithNoPlan/sandbox2 | via #UCB_webform_linked 1273/9606

2020-12-01T03:44:18Z

Alter: url. URLs might have been internationalized/anonymized. Add: s2cid. | You can use this bot yourself. Report bugs here. | Suggested by AManWithNoPlan | All pages linked from cached copy of User:AManWithNoPlan/sandbox2 | via #UCB_webform_linked 1273/9606

← Previous revision		Revision as of 03:44, 1 December 2020
Line 1:		Line 1:
	In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[Computer data storage#Secondary storage\|secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref>{{cite web\|title = data oriented design\|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book\|title=xeon phi optimization\|url=https://books.google.com/?id=DDpUCwAAQBAJ&~~pg=PA231&lpg=PA231&dq~~=scatter+memory+access+pattern~~#v=onepage~~&q=~~scatter%20memory%20access%20pattern&f=false~~\|isbn = 9780128091951\|last1 = Jeffers\|first1 = James\|last2 = Reinders\|first2 = James\|last3 = Sodani\|first3 = Avinash\|date = 2016-05-31}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{cite web\|title=Analysis of Energy and Performance of Code Transformations for PGAS-based Data Access Patterns\|url=http://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{cite web\|title=enhancing cache coherent architectures with memory access patterns for embedded many-core systems\|url=http://www.cc.gatech.edu/~bader/papers/EnhancingCache-SoC12.pdf}}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>		In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[Computer data storage#Secondary storage\|secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref>{{cite web\|title = data oriented design\|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book\|title=xeon phi optimization\|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231\|isbn = 9780128091951\|last1 = Jeffers\|first1 = James\|last2 = Reinders\|first2 = James\|last3 = Sodani\|first3 = Avinash\|date = 2016-05-31}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{cite web\|title=Analysis of Energy and Performance of Code Transformations for PGAS-based Data Access Patterns\|url=http://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{cite web\|title=enhancing cache coherent architectures with memory access patterns for embedded many-core systems\|url=http://www.cc.gatech.edu/~bader/papers/EnhancingCache-SoC12.pdf}}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>

	[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite web\|title=analysis of memory access patterns\|url=http://dl.acm.org/citation.cfm?id=838115}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{cite web\|title=QUAD a memory access pattern analyser\|url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf}}</ref><ref>{{cite web\|title=Dymaxion: Optimizing Memory Access Patterns for Heterogeneous Systems\|url=http://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf}}</ref><ref>{{cite journal\|title=evaluation of a memory access classification scheme for pointer intensive and numeric programs\|citeseerx=10.1.1.48.4163}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns<ref>{{cite web\|title=CuMAPz: a tool to analyze memory access patterns in CUDA\|url=http://dl.acm.org/citation.cfm?id=2024754}}</ref>		[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite web\|title=analysis of memory access patterns\|url=http://dl.acm.org/citation.cfm?id=838115}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{cite web\|title=QUAD a memory access pattern analyser\|url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf}}</ref><ref>{{cite web\|title=Dymaxion: Optimizing Memory Access Patterns for Heterogeneous Systems\|url=http://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf}}</ref><ref>{{cite journal\|title=evaluation of a memory access classification scheme for pointer intensive and numeric programs\|citeseerx=10.1.1.48.4163}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns<ref>{{cite web\|title=CuMAPz: a tool to analyze memory access patterns in CUDA\|url=http://dl.acm.org/citation.cfm?id=2024754}}</ref>

	Memory access patterns also have implications for [[security (computing)\|security]],<ref>{{cite web\|title=Memory Access Pattern Protection for Resource-constrained Devices\|url=https://www.cardis.org/proceedings/cardis_2012/CARDIS2012_14.pdf}}</ref><ref>{{cite web\|title=understanding cache attacks\|url=https://www.rocq.inria.fr/secret/Anne.Canteaut/Publications/RR-5881.pdf}}</ref> which motivates some to try and disguise a program's activity for [[Privacy (computing)\|privacy]] reasons.<ref>{{cite web\|title=protecting data in the cloud\|url=https://news.mit.edu/2013/protecting-data-in-the-cloud-0702}}</ref><ref>{{cite web\|title=boosting-cloud-security-with----oblivious-ram\|url=http://www.information-age.com/technology/security/123457364/boosting-cloud-security-with----oblivious-ram---}}proposed RAM design avoiding memory-access-pattern vulnerabilities</ref>		Memory access patterns also have implications for [[security (computing)\|security]],<ref>{{cite web\|title=Memory Access Pattern Protection for Resource-constrained Devices\|url=https://www.cardis.org/proceedings/cardis_2012/CARDIS2012_14.pdf}}</ref><ref>{{cite web\|title=understanding cache attacks\|url=https://www.rocq.inria.fr/secret/Anne.Canteaut/Publications/RR-5881.pdf}}</ref> which motivates some to try and disguise a program's activity for [[Privacy (computing)\|privacy]] reasons.<ref>{{cite web\|title=protecting data in the cloud\|url=https://news.mit.edu/2013/protecting-data-in-the-cloud-0702}}</ref><ref>{{cite web\|title=boosting-cloud-security-with----oblivious-ram\|url=http://www.information-age.com/technology/security/123457364/boosting-cloud-security-with----oblivious-ram---}}proposed RAM design avoiding memory-access-pattern vulnerabilities</ref>
Line 37:		Line 37:
	In a [[gather (vector addressing)\|gather]] memory access pattern, reads are randomly addressed or indexed, whilst the writes are sequential (or linear).<ref name="gpu gems2"/> An example is found in [[inverse texture mapping]], where data can be written out linearly across [[scan line]]s, whilst random access texture addresses are calculated per [[pixel]].		In a [[gather (vector addressing)\|gather]] memory access pattern, reads are randomly addressed or indexed, whilst the writes are sequential (or linear).<ref name="gpu gems2"/> An example is found in [[inverse texture mapping]], where data can be written out linearly across [[scan line]]s, whilst random access texture addresses are calculated per [[pixel]].

	Compared to scatter, the disadvantage is that caching (and bypassing latencies) is now essential for efficient reads of small elements, however it is easier to parallelise since the writes are guaranteed to not overlap. As such the gather approach is more common for [[gpgpu]] programming,<ref name="gpu gems"/> where the massive threading (enabled by parallelism) is used to hide read latencies.<ref name = "gpu gems">{{cite book\|title = GPU gems\|url=https://books.google.com/?id=lGMzmbUhpiAC&~~pg=PA51&lpg=PA51&dq~~=scatter+memory+access+pattern~~#v=onepage~~&q=~~scatter%20memory%20access%20pattern&f=false~~\|isbn = 9780123849892\|date = 2011-01-13}}deals with "scatter memory access patterns" and "gather memory access patterns" in the text</ref>		Compared to scatter, the disadvantage is that caching (and bypassing latencies) is now essential for efficient reads of small elements, however it is easier to parallelise since the writes are guaranteed to not overlap. As such the gather approach is more common for [[gpgpu]] programming,<ref name="gpu gems"/> where the massive threading (enabled by parallelism) is used to hide read latencies.<ref name = "gpu gems">{{cite book\|title = GPU gems\|url=https://books.google.com/books?id=lGMzmbUhpiAC&q=scatter+memory+access+pattern&pg=PA51\|isbn = 9780123849892\|date = 2011-01-13}}deals with "scatter memory access patterns" and "gather memory access patterns" in the text</ref>

	=== Combined gather and scatter ===		=== Combined gather and scatter ===

← Previous revision		Revision as of 03:44, 1 December 2020
Line 1:		Line 1:
	In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[Computer data storage#Secondary storage\|secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref>{{cite web\|title = data oriented design\|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book\|title=xeon phi optimization\|url=https://books.google.com/?id=DDpUCwAAQBAJ&~~pg=PA231&lpg=PA231&dq~~=scatter+memory+access+pattern~~#v=onepage~~&q=~~scatter%20memory%20access%20pattern&f=false~~\|isbn = 9780128091951\|last1 = Jeffers\|first1 = James\|last2 = Reinders\|first2 = James\|last3 = Sodani\|first3 = Avinash\|date = 2016-05-31}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{cite web\|title=Analysis of Energy and Performance of Code Transformations for PGAS-based Data Access Patterns\|url=http://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{cite web\|title=enhancing cache coherent architectures with memory access patterns for embedded many-core systems\|url=http://www.cc.gatech.edu/~bader/papers/EnhancingCache-SoC12.pdf}}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>		In [[computing]], a '''memory access pattern''' or '''IO access pattern''' is the pattern with which a system or program reads and writes [[Memory (computing)\|memory]] on [[Computer data storage#Secondary storage\|secondary storage]]<!--there no limit it levels (1 and 4 level could be used too), but we don't have sources yet -->. These patterns differ in the level of [[locality of reference]] and drastically affect [[Cache (computing)\|cache]] performance,<ref>{{cite web\|title = data oriented design\|url=http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf}}</ref> and also have implications for the approach to [[parallelism (computing)\|parallelism]]<ref>{{cite journal\|last1=Jang\|first1=Byunghyun\|last2=Schaa\|first2=Dana\|last3=Mistry\|first3=Perhaad\|last4=Kaeli\|first4=David\|name-list-style=amp\|date=2010-05-27\|title=Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures\|journal=IEEE Transactions on Parallel and Distributed Systems\|publisher=[[Institute of Electrical and Electronics Engineers\|IEEE]]\|location=New York\|volume=22\|issue=1\|pages=105–118\|eissn=1558-2183\|doi=10.1109/TPDS.2010.107\|s2cid=15997131\|issn=1045-9219\|id=NLM unique id 101212014}}</ref><ref>{{cite book\|title=xeon phi optimization\|url=https://books.google.com/books?id=DDpUCwAAQBAJ&q=scatter+memory+access+pattern&pg=PA231\|isbn = 9780128091951\|last1 = Jeffers\|first1 = James\|last2 = Reinders\|first2 = James\|last3 = Sodani\|first3 = Avinash\|date = 2016-05-31}}</ref> and distribution of workload in [[shared memory system]]s.<ref>{{cite web\|title=Analysis of Energy and Performance of Code Transformations for PGAS-based Data Access Patterns\|url=http://nic.uoregon.edu/pgas14/papers/pgas14_submission_17.pdf}}</ref> Further, [[cache coherency]] issues can affect [[multiprocessor]] performance,<ref>{{cite web\|title=enhancing cache coherent architectures with memory access patterns for embedded many-core systems\|url=http://www.cc.gatech.edu/~bader/papers/EnhancingCache-SoC12.pdf}}</ref> which means that certain memory access patterns place a ceiling on parallelism (which [[manycore]] approaches seek to break).<ref>{{cite web\|title=intel terascale\|url=https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf}}</ref>

	[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite web\|title=analysis of memory access patterns\|url=http://dl.acm.org/citation.cfm?id=838115}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{cite web\|title=QUAD a memory access pattern analyser\|url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf}}</ref><ref>{{cite web\|title=Dymaxion: Optimizing Memory Access Patterns for Heterogeneous Systems\|url=http://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf}}</ref><ref>{{cite journal\|title=evaluation of a memory access classification scheme for pointer intensive and numeric programs\|citeseerx=10.1.1.48.4163}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns<ref>{{cite web\|title=CuMAPz: a tool to analyze memory access patterns in CUDA\|url=http://dl.acm.org/citation.cfm?id=2024754}}</ref>		[[Computer memory]] is usually described as "[[random access memory\|random access]]", but traversals by software will still exhibit patterns that can be exploited for efficiency. Various tools exist to help system designers<ref>{{cite web\|title=analysis of memory access patterns\|url=http://dl.acm.org/citation.cfm?id=838115}}</ref> and programmers understand, analyse and improve the memory access pattern, including [[VTune]] and [[Intel Advisor\|Vectorization Advisor]],<ref>{{cite web\|title=QUAD a memory access pattern analyser\|url=http://ce-publications.et.tudelft.nl/publications/207_quad__a_memory_access_pattern_analyser.pdf}}</ref><ref>{{cite web\|title=Dymaxion: Optimizing Memory Access Patterns for Heterogeneous Systems\|url=http://www.cs.virginia.edu/~skadron/Papers/sc11_dymaxion_dist.pdf}}</ref><ref>{{cite journal\|title=evaluation of a memory access classification scheme for pointer intensive and numeric programs\|citeseerx=10.1.1.48.4163}}</ref><ref>{{cite book\|chapter=Online Memory Access Pattern Analysis on an Application Profiling Tool\|doi=10.1109/CANDAR.2014.86\|isbn=978-1-4799-4152-0\|title=2014 Second International Symposium on Computing and Networking\|year=2014\|last1=Matsubara\|first1=Yuki\|last2=Sato\|first2=Yukinori\|pages=602–604\|s2cid=16476418}}</ref><ref>{{cite web\|title=Putting Your Data and Code in Order: Data and layout\|url=https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2}}</ref> including tools to address [[GPU]] memory access patterns<ref>{{cite web\|title=CuMAPz: a tool to analyze memory access patterns in CUDA\|url=http://dl.acm.org/citation.cfm?id=2024754}}</ref>

	Memory access patterns also have implications for [[security (computing)\|security]],<ref>{{cite web\|title=Memory Access Pattern Protection for Resource-constrained Devices\|url=https://www.cardis.org/proceedings/cardis_2012/CARDIS2012_14.pdf}}</ref><ref>{{cite web\|title=understanding cache attacks\|url=https://www.rocq.inria.fr/secret/Anne.Canteaut/Publications/RR-5881.pdf}}</ref> which motivates some to try and disguise a program's activity for [[Privacy (computing)\|privacy]] reasons.<ref>{{cite web\|title=protecting data in the cloud\|url=https://news.mit.edu/2013/protecting-data-in-the-cloud-0702}}</ref><ref>{{cite web\|title=boosting-cloud-security-with----oblivious-ram\|url=http://www.information-age.com/technology/security/123457364/boosting-cloud-security-with----oblivious-ram---}}proposed RAM design avoiding memory-access-pattern vulnerabilities</ref>		Memory access patterns also have implications for [[security (computing)\|security]],<ref>{{cite web\|title=Memory Access Pattern Protection for Resource-constrained Devices\|url=https://www.cardis.org/proceedings/cardis_2012/CARDIS2012_14.pdf}}</ref><ref>{{cite web\|title=understanding cache attacks\|url=https://www.rocq.inria.fr/secret/Anne.Canteaut/Publications/RR-5881.pdf}}</ref> which motivates some to try and disguise a program's activity for [[Privacy (computing)\|privacy]] reasons.<ref>{{cite web\|title=protecting data in the cloud\|url=https://news.mit.edu/2013/protecting-data-in-the-cloud-0702}}</ref><ref>{{cite web\|title=boosting-cloud-security-with----oblivious-ram\|url=http://www.information-age.com/technology/security/123457364/boosting-cloud-security-with----oblivious-ram---}}proposed RAM design avoiding memory-access-pattern vulnerabilities</ref>
Line 37:		Line 37:
	In a [[gather (vector addressing)\|gather]] memory access pattern, reads are randomly addressed or indexed, whilst the writes are sequential (or linear).<ref name="gpu gems2"/> An example is found in [[inverse texture mapping]], where data can be written out linearly across [[scan line]]s, whilst random access texture addresses are calculated per [[pixel]].		In a [[gather (vector addressing)\|gather]] memory access pattern, reads are randomly addressed or indexed, whilst the writes are sequential (or linear).<ref name="gpu gems2"/> An example is found in [[inverse texture mapping]], where data can be written out linearly across [[scan line]]s, whilst random access texture addresses are calculated per [[pixel]].

	Compared to scatter, the disadvantage is that caching (and bypassing latencies) is now essential for efficient reads of small elements, however it is easier to parallelise since the writes are guaranteed to not overlap. As such the gather approach is more common for [[gpgpu]] programming,<ref name="gpu gems"/> where the massive threading (enabled by parallelism) is used to hide read latencies.<ref name = "gpu gems">{{cite book\|title = GPU gems\|url=https://books.google.com/?id=lGMzmbUhpiAC&~~pg=PA51&lpg=PA51&dq~~=scatter+memory+access+pattern~~#v=onepage~~&q=~~scatter%20memory%20access%20pattern&f=false~~\|isbn = 9780123849892\|date = 2011-01-13}}deals with "scatter memory access patterns" and "gather memory access patterns" in the text</ref>		Compared to scatter, the disadvantage is that caching (and bypassing latencies) is now essential for efficient reads of small elements, however it is easier to parallelise since the writes are guaranteed to not overlap. As such the gather approach is more common for [[gpgpu]] programming,<ref name="gpu gems"/> where the massive threading (enabled by parallelism) is used to hide read latencies.<ref name = "gpu gems">{{cite book\|title = GPU gems\|url=https://books.google.com/books?id=lGMzmbUhpiAC&q=scatter+memory+access+pattern&pg=PA51\|isbn = 9780123849892\|date = 2011-01-13}}deals with "scatter memory access patterns" and "gather memory access patterns" in the text</ref>

	=== Combined gather and scatter ===		=== Combined gather and scatter ===