Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Memory access pattern
open-in-new
<h2 id="examples">Examples</h2> <h3>Sequential</h3> <p class="note">Main article: <a href="/facts/Sequential_access/8NCL847H">Sequential access</a></p> <p>The simplest extreme is the <a href="/facts/Sequential_access/8NCL847H">sequential access</a> pattern, where data is read, processed, and written out with straightforward incremented/decremented addressing. These access patterns are highly amenable to <a href="/facts/Prefetching_(computing)/Gg0UkuqW">prefetching</a>. </p> <h3>Strided</h3> <p>Strided or simple 2D, 3D access patterns (e.g., stepping through <a href="/facts/Multi-dimensional_array/gHJJ3XPw">multi-dimensional arrays</a>) are similarly easy to predict, and are found in implementations of <a href="/facts/Linear_algebra/8VaB4VWk">linear algebra</a> algorithms and <a href="/facts/Image_processing/zenalNCf">image processing</a>. <a href="/facts/Loop_tiling/18lFS1CI">Loop tiling</a> is an effective approach.<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> Some systems with <a href="/facts/Direct_memory_access/DWuVgclV">DMA</a> provided a strided mode for transferring data between subtile of larger 2D arrays and <a href="/facts/Scratchpad_memory/qd5mHQul">scratchpad memory</a>.<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> </p> <h3>Linear</h3> <p>A linear access pattern is closely related to "strided", where a <a href="/facts/Memory_address/7EsUmbea">memory address</a> may be computed from a linear combination of some index. Stepping through indices sequentially with a linear pattern yields <a href="/facts/Stride_of_an_array/1Djh1kYY">strided access</a>. A linear access pattern for writes (with any access pattern for non-overlapping reads) may guarantee that an algorithm can be parallelised, which is exploited in systems supporting <a href="/facts/Compute_kernel/BxyI4vSf">compute kernels</a>. </p> <h3>Nearest neighbor</h3> <p>Nearest neighbor memory access patterns appear in simulation, and are related to sequential or strided patterns. An algorithm may traverse a data structure using information from the nearest neighbors of a data element (in one or more dimensions) to perform a calculation. These are common in physics simulations operating on grids.<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> Nearest neighbor can also refer to inter-node communication in a cluster; physics simulations which rely on such local access patterns can be parallelized with the data partitioned into cluster nodes, with purely nearest-neighbor communication between them, which may have advantages for latency and communication bandwidth. This use case maps well onto <a href="/facts/Torus_network_topology/vBDU15MN">torus network topology</a>.<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a> </p> <h3>2D spatially coherent</h3> <p>In <a href="/facts/3D_rendering/6SqukntK">3D rendering</a>, access patterns for <a href="/facts/Texture_mapping/9gDTsuXN">texture mapping</a> and <a href="/facts/Rasterization/QXfz5t7E">rasterization</a> of small primitives (with arbitrary distortions of complex surfaces) are far from linear, but can still exhibit spatial locality (e.g., in <a href="/facts/Screen_space/GfIomenN">screen space</a> or <a href="/facts/Texture_space/9gDTsuXN">texture space</a>). This can be turned into good <i>memory</i> locality via some combination of <a href="/facts/Morton_order/0QMjw8nF">morton order</a><a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a> and tiling for <a href="/facts/Texture_map/9gDTsuXN">texture maps</a> and <a href="/facts/Frame_buffer/kr8I4mm3">frame buffer</a> data (mapping spatial regions onto cache lines), or by sorting primitives via <a href="/facts/Tile_based_deferred_rendering/ts18ryzp">tile based deferred rendering</a>.<a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a> It can also be advantageous to store matrices in morton order in <a href="/facts/Linear_algebra_libraries/dfyHYAAm">linear algebra libraries</a>.<a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a> </p> <h3>Scatter</h3> <p>A <a href="/facts/Scatter_(vector_addressing)/NpmA08Aa">scatter</a> memory access pattern combines sequential reads with indexed/random addressing for writes.<a class="footnote-ref" id="fnref:25" href="#fn:25"><sup>25</sup></a> Compared to gather, It may place less load on a cache hierarchy since a <a href="/facts/Processing_element/Gg0UkuqW">processing element</a> may dispatch writes in a "fire and forget" manner (bypassing a cache altogether), whilst using predictable prefetching (or even DMA) for its source data. </p><p>However, it may be harder to parallelise since there is no guarantee the writes do not interact,<a class="footnote-ref" id="fnref:26" href="#fn:26"><sup>26</sup></a> and many systems are still designed assuming that a hardware cache will coalesce many small writes into larger ones. </p><p>In the past, <a href="/facts/Forward_texture_mapping/9gDTsuXN">forward texture mapping</a> attempted to handle the randomness with "writes", whilst sequentially reading source texture information. </p><p>The <a href="/facts/PlayStation_2/gbFBT7AX">PlayStation 2</a> console used conventional inverse texture mapping, but handled any scatter/gather processing "on-chip" using EDRAM, whilst 3D model (and a lot of texture data) from main memory was fed sequentially by DMA. This is why it lacked support for indexed primitives, and sometimes needed to manage textures "up front" in the <a href="/facts/Display_list/3tuIgqr0">display list</a>. </p> <h3>Gather</h3> <p>In a <a href="/facts/Gather_(vector_addressing)/NpmA08Aa">gather</a> memory access pattern, reads are randomly addressed or indexed, whilst the writes are sequential (or linear).<a class="footnote-ref" id="fnref:27" href="#fn:27"><sup>27</sup></a> An example is found in <a href="/facts/Inverse_texture_mapping/9gDTsuXN">inverse texture mapping</a>, where data can be written out linearly across <a href="/facts/Scan_line/3JEKoDRr">scan lines</a>, whilst random access texture addresses are calculated per <a href="/facts/Pixel/UzwBvXBV">pixel</a>. </p><p>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 <a href="/facts/Gpgpu/roBwsPY2">gpgpu</a> programming,<a class="footnote-ref" id="fnref:28" href="#fn:28"><sup>28</sup></a> where the massive threading (enabled by parallelism) is used to hide read latencies.<a class="footnote-ref" id="fnref:29" href="#fn:29"><sup>29</sup></a> </p> <h3>Combined gather and scatter</h3> <p>An algorithm may gather data from one source, perform some computation in local or on chip memory, and scatter results elsewhere. This is essentially the full operation of a <a href="/facts/GPU/PTK1RQVp">GPU</a> pipeline when performing <a href="/facts/3D_rendering/6SqukntK">3D rendering</a>- gathering indexed vertices and textures, and scattering shaded pixels in <a href="/facts/Screen_space/GfIomenN">screen space</a>. Rasterization of opaque primitives using a depth buffer is "commutative", allowing reordering, which facilitates parallel execution. In the general case synchronisation primitives would be needed. </p> <h3>Random</h3> <p class="note">Main article: <a href="/facts/Random_access/1cxrCk3r">Random access</a></p> <p>At the opposite extreme is a truly random memory access pattern. A few multiprocessor systems are specialised to deal with these.<a class="footnote-ref" id="fnref:30" href="#fn:30"><sup>30</sup></a> The <a href="/facts/Partitioned_global_address_space/wE3AwgJL">PGAS</a> approach may help by sorting operations by data on the fly (useful when the problem *is* figuring out the locality of unsorted data).<a class="footnote-ref" id="fnref:31" href="#fn:31"><sup>31</sup></a> Data structures which rely heavily on pointer chasing can often produce poor <a href="/facts/Locality_of_reference/fYFKDv5q">locality of reference</a>, 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 <a href="/facts/Parallel_computing/nQzcpzQt">parallelizing</a>. </p> <h2 id="approaches">Approaches</h2> <h3>Data-oriented design</h3> <p><a href="/facts/Data-oriented_design/mLBM7wYI">Data-oriented design</a> is an approach intended to maximise the locality of reference, by organising data according to how it is traversed in various stages of a program, contrasting with the more common <a href="/facts/Object_oriented/TxNMEcao">object oriented</a> approach (i.e., organising such that data layout explicitly mirrors the access pattern).<a class="footnote-ref" id="fnref:32" href="#fn:32"><sup>32</sup></a> </p> <h2 id="contrast-with-locality-of-reference">Contrast with locality of reference</h2> <p><a href="/facts/Locality_of_reference/fYFKDv5q">Locality of reference</a> refers to a property exhibited by memory access patterns. A programmer will change the memory access pattern (by reworking algorithms) to improve the locality of reference,<a class="footnote-ref" id="fnref:33" href="#fn:33"><sup>33</sup></a> and/or to increase potential for parallelism.<a class="footnote-ref" id="fnref:34" href="#fn:34"><sup>34</sup></a> A programmer or system designer may create frameworks or abstractions (e.g., <a href="/facts/Template_(C%2B%2B)/TXEqGy7R">C++ templates</a> or <a href="/facts/Higher-order_function/VjnjGbpt">higher-order functions</a>) that <a href="/facts/Encapsulation_(computer_programming)/kzDnbHPe">encapsulate</a> a specific memory access pattern.<a class="footnote-ref" id="fnref:35" href="#fn:35"><sup>35</sup></a><a class="footnote-ref" id="fnref:36" href="#fn:36"><sup>36</sup></a> </p><p>Different considerations for memory access patterns appear in parallelism beyond locality of reference, namely the separation of reads and writes. E.g.: even if the reads and writes are "perfectly" local, it can be impossible to parallelise due to <a href="/facts/Data_dependency/pkzwvqCf">dependencies</a>; separating the reads and writes into separate areas yields a different memory access pattern, maybe initially appear worse in pure locality terms, but desirable to leverage modern parallel hardware.<a class="footnote-ref" id="fnref:37" href="#fn:37"><sup>37</sup></a> </p><p>Locality of reference may also refer to individual variables (e.g., the ability of a <a href="/facts/Compiler/WNfCDFJe">compiler</a> to cache them in <a href="/facts/Processor_register/32RvbUdz">registers</a>), whilst the term memory access pattern only refers to data held in an indexable memory (especially <a href="/facts/Main_memory/wPHKFpdx">main memory</a>). </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Gather-scatter_(vector_addressing)/NpmA08Aa">Gather-scatter (vector addressing)</a></li> <li><a href="/facts/Locality_of_reference/fYFKDv5q">Locality of reference</a></li> <li><a href="/facts/Parallel_computing/nQzcpzQt">Parallel computing</a></li> <li><a href="/facts/Working_set/z7HKqFa5">Working set</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>"Introduction to Data-Oriented Design" (PDF). Archived from the original (PDF) on 2019-11-16. <a href="https://web.archive.org/web/20191116014412/http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf" target="_blank">https://web.archive.org/web/20191116014412/http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Jang, Byunghyun; Schaa, Dana; Mistry, Perhaad & Kaeli, David (2010-05-27). "Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures". IEEE Transactions on Parallel and Distributed Systems. 22 (1). New York: IEEE: 105–118. doi:10.1109/TPDS.2010.107. eISSN 1558-2183. ISSN 1045-9219. S2CID 15997131. NLM unique id 101212014. <a href="/wiki/Institute_of_Electrical_and_Electronics_Engineers" target="_blank">/wiki/Institute_of_Electrical_and_Electronics_Engineers</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Jeffers, James; Reinders, James; Sodani, Avinash (2016-05-31). Intel Xeon Phi Processor High Performance Programming: Knights Landing Edition (2nd ed.). Morgan Kaufmann. ISBN 9780128091951. <a href="9780128091951" target="_blank">9780128091951</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Jana, Siddhartha; Schuchart, Joseph; Chapman, Barbara (2014-10-06). "Analysis of Energy and Performance of PGAS-based Data Access Patterns" (PDF). Proceedings of the 8th International Conference on Partitioned Global Address Space Programming Models. PGAS '14. New York, NY, USA: Association for Computing Machinery. pp. 1–10. doi:10.1145/2676870.2676882. ISBN 978-1-4503-3247-7. <a href="978-1-4503-3247-7" target="_blank">978-1-4503-3247-7</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Marandola, Jussara; Louise, Stéphane; Cudennec, Loïc; Acquaviva, Jean-Thomas; Bader, David (2012-10-11). "Enhancing Cache Coherent Architectures with access patterns for embedded manycore systems". 2012 International Symposium on System on Chip (SoC) (PDF). IEEE. pp. 1–7. doi:10.1109/ISSoC.2012.6376369. ISBN 978-1-4673-2896-8. <a href="978-1-4673-2896-8" target="_blank">978-1-4673-2896-8</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>"intel terascale" (PDF). <a href="https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf" target="_blank">https://cseweb.ucsd.edu/classes/fa12/cse291-c/talks/SCC-80-core-cern.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Brown, Mary; Jenevein, Roy M.; Ullah, Nasr (29 November 1998). Memory Access Pattern Analysis. WWC '98: Proceedings of the Workload Characterization: Methodology and Case Studies (published 1998-11-29). p. 105. ISBN 9780769504506. <a href="9780769504506" target="_blank">9780769504506</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Ostadzadeh, S. Arash; Meeuws, Roel J.; Galuzzi, Carlo; Bertels, Koen (2010). "QUAD – A Memory Access Pattern Analyser" (PDF). In Sirisuk, Phaophak; Morgan, Fearghal; El-Ghazawi, Tarek; Amano, Hideharu (eds.). Reconfigurable Computing: Architectures, Tools and Applications. Lecture Notes in Computer Science. Vol. 5992. Berlin, Heidelberg: Springer. pp. 269–281. doi:10.1007/978-3-642-12133-3_25. ISBN 978-3-642-12133-3. <a href="978-3-642-12133-3" target="_blank">978-3-642-12133-3</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Che, Shuai; Sheaffer, Jeremy W.; Skadron, Kevin (2011-11-12). "Dymaxion: Optimizing memory access patterns for heterogeneous systems" (PDF). Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. SC '11. New York, NY, USA: Association for Computing Machinery. pp. 1–11. doi:10.1145/2063384.2063401. ISBN 978-1-4503-0771-0. <a href="978-1-4503-0771-0" target="_blank">978-1-4503-0771-0</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Harrison, Luddy (1996-01-01). "Examination of a memory access classification scheme for pointer-intensive and numeric programs". Proceedings of the 10th international conference on Supercomputing - ICS '96. New York, NY, USA: Association for Computing Machinery. pp. 133–140. doi:10.1145/237578.237595. ISBN 978-0-89791-803-9. <a href="978-0-89791-803-9" target="_blank">978-0-89791-803-9</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Matsubara, Yuki; Sato, Yukinori (2014). "Online Memory Access Pattern Analysis on an Application Profiling Tool". 2014 Second International Symposium on Computing and Networking. pp. 602–604. doi:10.1109/CANDAR.2014.86. ISBN 978-1-4799-4152-0. S2CID 16476418. <a href="978-1-4799-4152-0" target="_blank">978-1-4799-4152-0</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>"Putting Your Data and Code in Order: Data and layout". <a href="https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2" target="_blank">https://software.intel.com/en-us/articles/putting-your-data-and-code-in-order-data-and-layout-part-2</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Kim, Yooseong; Shrivastava, Aviral (2011-06-05). "CuMAPz: A tool to analyze memory access patterns in CUDA". Proceedings of the 48th Design Automation Conference. DAC '11. New York, NY, USA: Association for Computing Machinery. pp. 128–133. doi:10.1145/2024724.2024754. ISBN 978-1-4503-0636-2. <a href="978-1-4503-0636-2" target="_blank">978-1-4503-0636-2</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Kim, Yooseong; Shrivastava, Aviral (2011-06-05). "CuMAPz: A tool to analyze memory access patterns in CUDA". Proceedings of the 48th Design Automation Conference. DAC '11. New York, NY, USA: Association for Computing Machinery. pp. 128–133. doi:10.1145/2024724.2024754. ISBN 978-1-4503-0636-2. <a href="978-1-4503-0636-2" target="_blank">978-1-4503-0636-2</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Canteaut, Anne; Lauradoux, Cédric; Seznec, André (2006). Understanding cache attacks (report thesis). INRIA. ISSN 0249-6399. <a href="https://inria.hal.science/inria-00071387/en/" target="_blank">https://inria.hal.science/inria-00071387/en/</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Hardesty, Larry (2013-07-02). "Protecting data in the cloud". MIT News. <a href="https://news.mit.edu/2013/protecting-data-in-the-cloud-0702" target="_blank">https://news.mit.edu/2013/protecting-data-in-the-cloud-0702</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Rossi, Ben (2013-09-24). "Boosting cloud security with oblivious RAM". Information Age. <a href="https://www.information-age.com/boosting-cloud-security-with-oblivious-ram-28698/" target="_blank">https://www.information-age.com/boosting-cloud-security-with-oblivious-ram-28698/</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>Kennedy, Ken; McKinley, Kathryn S. (1992-08-01). "Optimizing for parallelism and data locality" (PDF). Proceedings of the 6th international conference on Supercomputing - ICS '92. New York, NY, USA: Association for Computing Machinery. pp. 323–334. doi:10.1145/143369.143427. ISBN 978-0-89791-485-7. <a href="978-0-89791-485-7" target="_blank">978-0-89791-485-7</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>Saidi, Selma; Tendulkar, P.; Lepley, Thierry; Maler, O. (2012). "Optimal 2D Data Partitioning for DMA Transfers on MPSoCs" (PDF). 2012 15th Euromicro Conference on Digital System Design. IEEE. pp. 584–591. doi:10.1109/DSD.2012.99. ISBN 978-0-7695-4798-5. <a href="978-0-7695-4798-5" target="_blank">978-0-7695-4798-5</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>CITRIS and the Banatao Institute (2013-09-05). Partitioned Global Address Space Programming - Kathy Yelick. Retrieved 2024-11-02 – via YouTube. 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". <a href="https://www.youtube.com/watch?v=NU4VfjISk2M" target="_blank">https://www.youtube.com/watch?v=NU4VfjISk2M</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>Weinberg, Jonathan; McCracken, Michael O.; Snavely, Allan; Strohmaier, Erich (12–18 November 2005). "Quantifying Locality in the Memory Access Patterns of HPC Applications" (PDF). ACM/IEEE SC 2005 Conference (SC'05). Seattle, WA, USA: IEEE. p. 50. doi:10.1109/SC.2005.59. ISBN 1-59593-061-2. Archived from the original (PDF) on 2016-08-03. mentions nearest neighbor access patterns in clusters <a href="1-59593-061-2" target="_blank">1-59593-061-2</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>Hakura, Ziyad S.; Gupta, Anoop (1997-05-01). "The design and analysis of a cache architecture for texture mapping" (PDF). Proceedings of the 24th annual international symposium on Computer architecture. ISCA '97. New York, NY, USA: Association for Computing Machinery. pp. 108–120. doi:10.1145/264107.264152. ISBN 978-0-89791-901-2. <a href="978-0-89791-901-2" target="_blank">978-0-89791-901-2</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Nocentino, Anthony E.; Rhodes, Philip J. (2010-04-15). "Optimizing memory access on GPUs using morton order indexing" (PDF). Proceedings of the 48th Annual Southeast Regional Conference. ACMSE '10. New York, NY, USA: Association for Computing Machinery. pp. 1–4. doi:10.1145/1900008.1900035. ISBN 978-1-4503-0064-3. Archived from the original (PDF) on 2022-12-08. <a href="978-1-4503-0064-3" target="_blank">978-1-4503-0064-3</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>Wise, David S.; Frens, Jeremy D. (1999). "Morton-order Matrices Deserve Compilers ' Support Technical Report 533". S2CID 17192354. {{cite journal}}: Cite journal requires |journal= (help) <a href="/wiki/S2CID_(identifier)" target="_blank">/wiki/S2CID_(identifier)</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> <li id="fn:25"><p>Harris, Mark (April 2005). "GPU Gems 2". 31.1.3 Stream Communication: Gather vs. Scatter. Archived from the original on 2016-06-14. Retrieved 2016-06-13. <a href="https://web.archive.org/web/20160614195224/http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter31.html" target="_blank">https://web.archive.org/web/20160614195224/http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter31.html</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></p></li> <li id="fn:26"><p>GPU gems. Elsevier. 2011-01-13. ISBN 9780123849892.deals with "scatter memory access patterns" and "gather memory access patterns" in the text <a href="9780123849892" target="_blank">9780123849892</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></p></li> <li id="fn:27"><p>Harris, Mark (April 2005). "GPU Gems 2". 31.1.3 Stream Communication: Gather vs. Scatter. Archived from the original on 2016-06-14. Retrieved 2016-06-13. <a href="https://web.archive.org/web/20160614195224/http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter31.html" target="_blank">https://web.archive.org/web/20160614195224/http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter31.html</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></p></li> <li id="fn:28"><p>GPU gems. Elsevier. 2011-01-13. ISBN 9780123849892.deals with "scatter memory access patterns" and "gather memory access patterns" in the text <a href="9780123849892" target="_blank">9780123849892</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></p></li> <li id="fn:29"><p>GPU gems. Elsevier. 2011-01-13. ISBN 9780123849892.deals with "scatter memory access patterns" and "gather memory access patterns" in the text <a href="9780123849892" target="_blank">9780123849892</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></p></li> <li id="fn:30"><p>Wichmann, Nathan (2005). Cray and HPCC : Benchmark Developments and Results from the Past Year (PDF). CUG 2005 Proceedings. see global random access results for Cray X1. vector architecture for hiding latencies, not so sensitive to cache coherency <a href="https://cug.org/5-publications/proceedings_attendee_lists/2005CD/S05_Proceedings/pages/Authors/Wichmann/Wichmann_paper.pdf" target="_blank">https://cug.org/5-publications/proceedings_attendee_lists/2005CD/S05_Proceedings/pages/Authors/Wichmann/Wichmann_paper.pdf</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></p></li> <li id="fn:31"><p>CITRIS and the Banatao Institute (2013-09-05). Partitioned Global Address Space Programming - Kathy Yelick. Retrieved 2024-11-02 – via YouTube. 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". <a href="https://www.youtube.com/watch?v=NU4VfjISk2M" target="_blank">https://www.youtube.com/watch?v=NU4VfjISk2M</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></p></li> <li id="fn:32"><p>"Introduction to Data-Oriented Design" (PDF). Archived from the original (PDF) on 2019-11-16. <a href="https://web.archive.org/web/20191116014412/http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf" target="_blank">https://web.archive.org/web/20191116014412/http://www.dice.se/wp-content/uploads/2014/12/Introduction_to_Data-Oriented_Design.pdf</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></p></li> <li id="fn:33"><p>"optimize-data-structures-and-memory-access-patterns-to-improve-data-locality". <a href="https://software.intel.com/en-us/articles/optimize-data-structures-and-memory-access-patterns-to-improve-data-locality" target="_blank">https://software.intel.com/en-us/articles/optimize-data-structures-and-memory-access-patterns-to-improve-data-locality</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></p></li> <li id="fn:34"><p>Harris, Mark (April 2005). "GPU Gems 2". 31.1.3 Stream Communication: Gather vs. Scatter. Archived from the original on 2016-06-14. Retrieved 2016-06-13. <a href="https://web.archive.org/web/20160614195224/http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter31.html" target="_blank">https://web.archive.org/web/20160614195224/http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter31.html</a> <a href="#fnref:34" class="footnote-back-ref">↩</a></p></li> <li id="fn:35"><p>"Template-based Memory Access Engine for Accelerators in SoCs" (PDF). <a href="http://www.cs.utah.edu/~zfang/asp_dac11.pdf" target="_blank">http://www.cs.utah.edu/~zfang/asp_dac11.pdf</a> <a href="#fnref:35" class="footnote-back-ref">↩</a></p></li> <li id="fn:36"><p>"Multi-Target Vectorization With MTPS C++ Generic Library" (PDF).a C++ template library for producing optimised memory access patterns <a href="http://www.metz.supelec.fr/metz/recherche/publis_pdf/Supelec753.pdf" target="_blank">http://www.metz.supelec.fr/metz/recherche/publis_pdf/Supelec753.pdf</a> <a href="#fnref:36" class="footnote-back-ref">↩</a></p></li> <li id="fn:37"><p>Harris, Mark (April 2005). "GPU Gems 2". 31.1.3 Stream Communication: Gather vs. Scatter. Archived from the original on 2016-06-14. Retrieved 2016-06-13. <a href="https://web.archive.org/web/20160614195224/http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter31.html" target="_blank">https://web.archive.org/web/20160614195224/http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter31.html</a> <a href="#fnref:37" class="footnote-back-ref">↩</a></p></li> </ol>