0

I am trying to understand memory access patterns. My question is simple. Who decides the memory access pattern?

  • I decide the pattern for my program by giving as a parameter to gcc. Thus, I can set it according to my code.
  • My OS decides the memory access pattern. Thus, I can not change it for any of my programs.
  • My CPU decides what memory access pattern is used. Thus, any OS running on my PC uses the pattern.
Prihex
  • 342
  • 2
  • 11
  • Depends what you mean by memory pattern. CPU hardware has ability to handle physical memory access and virtual memory mapping to these physical pages. OS will allocate the physical pages and program the virtual memory page tables. When you malloc, you will get a linear virtual memory range with possibly scattered physical pages behind it. Generally HW is the how, OS is the what, app is simply a user of the what the OS provides – Chris Aug 29 '21 at 02:18
  • Whenever I causes CPU to access memory, I want to use Nearest neighbor memory access pattern because of my code implementation. Is it possible? Another approach is, before running my program, how can i know which pattern will be used? I am new to this, sorry if my questions are rubbish. – Prihex Aug 29 '21 at 02:43
  • It seems you are actually looking for algorithm, not related to the CPU/OS/Compile flag. You have to implement this as an algorithm using arrays for example I found this on SO: https://stackoverflow.com/questions/7862190/nearest-neighbor-operation-on-1d-array-elements You put data in array or arrays and you organize it in some structure that you understand, so you can walk the nearest neighbours. – Chris Aug 29 '21 at 03:02
  • 1
    Unless the data you access resides within a single page of memory, you're not guaranteed anything about the actual physical memory access pattern of your program since the OS can assign your virtual memory anywhere in physical memory. See [here](https://stackoverflow.com/q/68228499/13020139) – wxz Aug 29 '21 at 03:04

1 Answers1

2

Who decides the memory access pattern?

Mostly; the person who writes the code decides the memory access patterns by the choices they make.

For a silly example; if you decide to iterate through an array (like for(i = 0; i <= size; i++) { do_something(&my_array[i]); }) then you've caused a nice linear access pattern; and if you decide to iterate through a linked list instead (like while(current != NULL) { do_something(current); current = current->next; }) then you'll probably have a relatively erratic access pattern.

However; in some cases the compiler/linker may try to optimize the memory access patterns. This mostly only changes the fine details slightly (the exact order of individual reads/writes and not the overall pattern itself), but there are cases where a compiler can do more pronounced optimizations (primarily involving nested loops and arrays).

Note 1: It's likely that the result will be a "virtual memory access pattern". Underneath there will be a full memory hierarchy - the OS will control the mapping of virtual memory to physical memory (and handle things like swap space, etc); and then there will be multiple levels of caches and other "cache like things" built into the hardware. None of this matters. It complicates what is actually being accessed (which part of which cache, or which physical memory, or which part of swap space, or...) but accesses will still occur in the same order (and in the same pattern) regardless of what is actually being accessed.

Note 2: A typical program is rarely a simple/single algorithm. If a program (a web browser, a computer game, a compiler, ...) has hundreds of pieces then the program's access pattern will be some combination of the individual access patterns of each piece.

Brendan
  • 35,656
  • 2
  • 39
  • 66
  • I want to check if I understand you correctly. According to assembly code, CPU choses the proper memory access pattern and it can change any moment. For example; between 10-20 lines, linear access pattern is used, 60-80 lines, scatter pattern can be used. Am I correct? – Prihex Aug 29 '21 at 13:08
  • @Prihex: For software to work correctly the CPU has to do what it's told with strict guarantees. Those strict guarantees are flexible enough to allow the CPU to do some minor optimization of when some memory accesses are done, but it's never enough to change the overall access pattern in a meaningful way. If the assembly describes a linear access pattern, the CPU can't just ignore the code and go play some football. – Brendan Aug 29 '21 at 14:29
  • Well, the main access pattern is described by CPU architect. According to my code, it can change. For example 'mov bx, 2' then 'mov ax, [100]'. There is a memory operation in second one. Before that, setting bx as 2 will cause linear pattern for second operation. All that was an example. However, it is something like that? – Prihex Aug 29 '21 at 14:49
  • @Prihex: A single memory access isn't enough to establish a pattern. If you had `mov ax,[100]` then `mov [200],ax` then `mov bx,[300]`; the CPU would have no choice and must do these accesses in the order given (which happens to be a linear access pattern because that's what the code says). If you had `mov ax,[100]` then `mov bx,[200]` then `mov [300],ax`; the CPU would be allowed to do the first 2 loads in any order (but the last store must be last and CPU can't change that). – Brendan Aug 29 '21 at 15:04
  • @Prihex: Mostly; the memory ordering rules (especially for 80x86) are designed so that the CPU can only re-order memory accesses when it's very unlikely that it will cause a difference; which means that (except for a few rare special cases) you can assume the CPU will do memory accesses in the program's order (even if it might not in theory). – Brendan Aug 29 '21 at 15:12
  • "None of this matters." If the ultimate goal is performance, it does matter. – wxz Aug 29 '21 at 17:52
  • @wxz: If the ultimate goal is performance, assuming "memory access pattern is determined by the assembly" will give far better results than assuming "memory access pattern is entirely unknowable (because CPU can re-order a few measly reads between unmovable writes)". – Brendan Aug 29 '21 at 19:04