#import "../utils/utils.typ": *

== Interlude: Memory, Caches, and Consistency Models

For a processor to perform well, it needs relatively fast access to memory.
Main memory technologies like _dynamic random access memory_ (DRAM) have high capacities and generally high bandwidths, which is good, but they also have high _latencies_; the time between requesting data and getting the data back.
Even though superscalar processors can finish more than one instruction per cycle, this is only in theory.

A good number of instructions within any given program are likely to be memory instructions.
Instructions are loaded from memory.
Because of this, the effective latency of memory accesses has a huge impact on processor performance.

=== Caches

To reduce latency in accessing main memory, the memory can be placed closer to the core, physically on the same chip.
However, this is costly and scales poorly for large capacities.
The compromise is to use _caches_ alongside main memory technologies like DRAM.

Caches, as a concept, show up everywhere in computing.
They are used to store temporary copies of frequently or recently used data in some sort of storage that is faster to access than the main storage.
The cached data must eventually be synchronised with the main storage, and changes must somehow be propagated to other copies, giving rise to one of the two hard problems in computer science @bib:two-hard-things.

Computer processor caches base themselves on this same idea.
Small low-latency memories are placed close to the core and are made to store copies of the data in main memory.
This works because applications exhibit _locality_ in memory requests.
Data that have been used previously are more likely to be re-used---called _temporal locality_.
Programs also exhibit _spatial locality_: data that lie close to previously used data are more likely to be requested in the future.
Computer processor caches exploit this by not only fetching the requested datum, but surrounding data as well.

Generally, caching is only employed for the address range that covers main memory as it is difficult or impossible to uphold any semblance of sanity while caching accesses with side-effects.

=== Cache Hierarchies

Caches are arranged in hierarchies, with the smallest, fastest caches placed closest to the core while the larger, slower caches are placed further away---sometimes on a different chip entirely.
If the processor requests data that cannot be found in the first level of cache, the data will be looked up in lower and lower levels until it is found, possibly all the way out in main memory.
The first level of cache is called the L1 cache, or level-1 cache.
Each consecutive level is simply numbered one higher than the last.
Modern processors have first-, second-, and third-level caches.
The last level of cache is appropriately named the last-level cache (LLC).
First-level caches are usually exclusive to a single core, but later cache levels are commonly shared between multiple cores in the system.

=== Split L1 Caches

All instructions have to be fetched from memory, and some instructions have to access memory.
These two sources of memory requests---instruction fetch and memory access---have very different patterns and behaviours:
The stream of requests generated by instruction fetch is very predictable and linear except for where branching occurs, often for one specific size, and is load-only.
The instruction fetching circuitry will never try to store an instruction to memory.

On the other hand, the stream of requests generated by memory instructions is going to hop back and forth between many different memory locations, may contain store instructions, and access many different sizes of data.

To avoid designing a cache that is good for both types of requests, the first-level cache is usually split into a first-level data cache (L1d), and a first-level instruction cache (L1i).
This allows implementers to focus on optimising each cache for specific needs.
The instruction cache can be optimised for loading consecutive instructions out at a high bandwidth.
The data cache can be optimised for accessing differently sized elements at different locations each cycle.

=== Cache Organisation

Caches are organised as a collection of _sets_.
When accessing the cache, bits from the address are used to select the specific set for the processor to look in.
These bits form the _index_.
The data of any given address can only be found within a specific set.
Each set is also split into one or more _blocks_ or _lines_.
We will refer to them as blocks.
Each block contains a number of bytes which are the data being accessed.
The lower 6 bits of the address are used to determine which specific bytes of the block are being accessed.
This is called the block _offset_.
The bits of an address that are not part of the index and offset are part of the _tag_.
Each block has a tag.

The number of blocks within sets is called the _associativity_.
With one block per set, the cache is a _direct-mapped_ cache (each datum has only one possible cache block it can be in).
With only one set and all blocks placed within it, the cache is _fully associative_ (each datum can be in any block in the cache).

Fully associative caches are expensive to implement as it requires comparing the address tag with the tag of every block in the cache.
Direct-mapped caches are simple to implement, but have problems with aliasing where multiple addresses with equal indices, but different tags, will cause each other to be pushed out of the cache to make space for themselves.
The compromise is an _n-way_ associative cache, where $n$ is the number of blocks within each set.
These caches can store up to $n$ blocks with equal indices but different tags at the same time without pushing any blocks out to make space.

When a request is made and the cache does not have the requested datum, the request is said to _miss_ in the cache.
The converse of a miss is a _hit_ in the cache.
When a miss occurs, the entire block that contains that datum is brought in along with surrounding data.
Using larger blocks reduces the amount of meta-data that must be stored per byte, although it requires fetching more data at a time when first missing.

=== Data Cache Prefetching

Naively, data are only brought into caches on-demand.
If no previous memory request has been made to any address within a block, a request to that block will always miss.
However, the access patterns of memory instructions are predictable.
For example: iterating over an array in a loop will generate requests for addresses that increment by some fixed amount.
Thus, if one such request starts by accessing the second-to-last byte in a block, then the last one, it is reasonable to assume that the next request will be for the first byte in the next block.
Using this information, the cache can begin loading the block before it is even known to be needed---called _prefetching_.

=== Consistency Models

ISA documents generally do not specify how a cache---or any other structures interacting with memory---should behave.
Whether a certain implementation is a valid one depends on the memory  model of the ISA.

Consistency models specify which effective orderings of memory accesses are valid in different scenarios.
Explaining the concept in full detail is too great an undertaking, so we have settled for a simple example with two cores: one executing two store instructions, and another executing two load instructions.

@lst:ordering-example shows instructions executed on two different cores.
$A$ and $B$ are values stored in memory.
These values are both set to 0 before execution starts.
A consistency model says which possible values Core 2 ($C_2$) can observe for $A$ and $B$, and what the value of one implies about the value of the other.

#figure(grid(columns: (auto, ) * 2, inset: 5pt, [
  ```
  // Core 1
  store A 1
  store B 1
  ```
], 
grid.vline(),
[
  ```
  // Core 2
  load B
  load A
  ```
]), 
  caption: [Two store instructions and two load instructions executing on different cores]
)<lst:ordering-example>

The most important thing to recognise about consistency models is that the _observed order_ of memory accesses not necessarily corresponds to the _program order_.
The program order is the order in which the instructions appear in the program during correct execution.

==== The Effect of Caching

With caching, what might happen is that both the store instructions from Core 1 ($C_1$) finish executing.
Then, when $C_2$ performs the load instructions, it uses the newly stored value for $B$, but uses a cached value for $A$, cached before the store instructions took place, possibly ending with the result $A = 0$, $B = 1$.

The order of memory operations would appear to be:
+ $C_2$ load $A$ (sees $A = 0$)
+ $C_1$ store $A$ 1
+ $C_1$ store $B$ 1
+ $C_2$ load $B$ (sees $B = 1$)

As can be seen here, the order of the load instructions has been swapped.
In the program, the load of $B$ went before the load of $A$, but in the observed ordering, they appear in a different order.

==== Different Consistency Models

The job of consistency models is to define which orderings are allowed in scenarios like the one above.
Consistency models can be divided into two groups: _weak_ and _strong_.
Strong models place more restrictions on the possible orderings, while weak models place few restrictions.
Strong models arguably "make more sense" and are likely to be a better fit for normal intuition.
However, strong models pose a challenge for computer engineers in feasibly implementing them.
There is no "best" model#footnote[Besides the venerable DEC Alpha, which has the coolest weak consistency model and allows some abhorrently unintuitive behaviours.], only tradeoffs for computer hardware engineers and computer programmers.

An example of a strong consistency model is the _total store order_ (TSO) which says that store instructions from the same core cannot be re-ordered, nor can load instructions.
Later load instructions in program order can go ahead of preceding store instructions as long as they don't alias (access the same address).

With TSO, the result above would be disallowed as the load of $A$ is seeing an older value of $A$ than the value loaded for $B$.
Note that even under TSO, though $C_1$ may complete the store instructions long before $C_2$ performs any load instructions, $C_2$ is still allowed to observe $A = 0, B = 0$ if it can still guarantee that the value of $A$ is as fresh as that of $B$.
A stronger ordering like this does give some useful guarantees, however, like $B = 1 ==> A = 1$.
Weak consistency models allow much more re-ordering.
The weakest possible consistency model only requires that a program executing on a single core behaves _as if_ it were executed fully in order.

With strong models, the processor implementation must provide certain guarantees for behaviour.
With weak models, more of that responsibility falls on the programmer.

Architectures with any strength model must still provide synchronisation primitives for programmers to properly express desired behaviour.
A _barrier_ or _fence_ is a normal synchronisation primitive.
A _full_ fence is an instruction that prevents any earlier memory operations from being observed after it and any later memory operations being observed before it.
