Memory consistency

Question 1

What is memory consistency?

Answer 1

A problem that occurs between different programs when you have multiple cores active.

A contract between the programmer and the hardware.

Is a set of rules that dictates how observable memory operations are performed. This means, that when you have designed a program, how does it translate to actual memory execution.

The programmer must be aware of this set of rules when creating programs.

Hardware designers must also follow these rules when designing out-of-order cores.

Consistency is NOT optional, and is not an optimisation feature.

Consistency models are NOT the same between different ISAs, meaning it is an inate part of the ISA and dictates how a program can e restructured during execution.

Question 2

What is the difference between cache coherence and memory consistency?

Answer 2

Memory consistency is a different multi-core problem, whereas coherence deals with making sure the memory has the correct value.

Consistency is NOT optional, and is not an optimisation feature.

Question 3

Who must follow the memory consistency rules?

Answer 3

Hardware designers when designing ooo cores

Programmers when creating programs

Question 4

Why is memory consistency needed?

Answer 4

Ensures we have synchronisation between programs executing in parallel. When programs are executing across cores, we do not know exactly when things are happening. Memory consistency helps avoiding problems such as race conditions.

Ensures ability to execute atomic operations.

Question 5

What would happen to programs if we did not have memory consistency?

Answer 5

Programs would suffer from race conditions more, and ambiguity.

Question 6

What is observability in memory systems?

Answer 6

When executing a program on a core in a multicore system, some memory operations will be visible to other threads.

Question 7

What memory operations are visable?

Answer 7

Shared cache line:
- readings from the cache line is visable

All writes are visible as it changes memory values. Even if it is not in a cache line that is shared.

Question 8

What difference in the goals of a SW and HW designer?

Answer 8

A SW designer wants to write programs that are correct and optimised. A typical optimisation is introducing parallelism, which comes with new problem areas.

A HW designer wants to execute memory operations when these are ready, but not necessarily in order (long latency, etc.). This means that memory operations might not execute in the program code order.

Question 9

What is memory order?

Answer 9

Order of executed observable memory operations in the actual core.

Question 10

What is program order?

Answer 10

Order of instructions as they appear in the machine code.

Defines the programmers intention for program execution/purpose. This means that if a programmer puts a load before a write, they expect the load to happen before the write.

Question 11

What limits the reordering of memory operations?

Answer 11

Consistency rules and ready instructions.

An instruction will execute when it is ready, if it is legal according to the consistency rules.

Question 12

What is the Sequential Consistency model (SC)

Answer 12

The baseline

Memory operations are performed in program order.

When having multiple processes, these are ordered in respect to each other - in some arbitrary order.
Within a program, all operations are executed in order. And all programs are ordered in regards to each other, in some arbitrary order.

No processes are performing memory operations at the same time.

Only one valid ordering (translation from program to execution order), when considering a single program/thread. And that is the program order.

Question 13

What is sequential consistency at a local level?

Answer 13

Every operation executes as ordered in the program code

Question 14

What is sequential consistency at a global level?

Answer 14

There are some ordering of processes in regards to each other

Question 15

How can you quickly define a memory consistency model?

Answer 15

The translation from program order to execution order.

Question 16

What are ordering rules?

Answer 16

When talking about consistency models, we have the 4 following rules:

Read followed by read
Read followed by write
Write followed by read
Write followed by write

Notation:
R0, R1: 0 - first operation, 1 - second operation
<p: Before in program order
<m: Before in memory order

Question 17

What are ordering rules for sequential consistency?

Answer 17

R0 <p R1 -> R0 <m R1
R0 <p W0 -> R0 <m W0
W0 <p R0 -> W0 <m R0
W0 <p W1 -> W0 <m W1

No reordering of execution. A rule says observable operations must happen in program order.

Question 18

Why is talking about SC important?

Answer 18

It is trivial ti implement
- all mem-ops are in program order
- all updates become fully visable before a value is read

Very intuitiv, it does what the programmer “expects” will happen

Very low performance - very limited when we can execute mem-ops. Not just when they are ready.

Question 19

When talking about consistency models, what are valid outcomes?

Answer 19

The possible outcomes of a program, based on the consistency model.

Question 20

What happens if we relax one or more of the rules, as they are defined in the SC model?

Answer 20

Reduces intuition of going from program to memory order. Can cause wrong outputs or race conditions.

Potentially improves performance. Introduces the ability to potentially issue operations earlier on (when ready).

Question 21

What is a Total Store Order (TSO) consistency model?

Answer 21

Relaxing the Write-Read rules. Maintains the store order.

W0 <p R0 -> W0 <m R0 # This does no longer need to apply

Allows for following reads to issue before preceding writes - assuming no dependence.

Question 22

What is a Partial Store Order (PSO) consistency model?

Answer 22

Relaxes both Write-Read, and Write-Write rules. No longer guarantee for writes happening in order.

W0 <p R0 -> W0 <m R0
W0 <p W1 -> W0 <m W1

Race conditions can occur here

Question 23

What is a Weak Ordering (WO) / Release Consistency (RC) consistency model?

Answer 23

Relaxes all of the rules. Give no guarantees of the execution ordering of memory operations.

Any ordering is legal, unless explicitly synchronised

There are multiple variations of WO, this is just the generic name

Question 24

What consistency model is most wide-spread in personal computers?

Answer 24

TSO and x86 ISA

Question 25

Why would we want to relax the Write-Read ordering?

Answer 25

Remove the W0 <p R0 -> W0 <m R0 rule

Allows reads to be issued, while writes to different addresses have not yet completed.

Effective way to hide write latency, as writes are not on the critical path. Reads are however, because they fetch new data into the system, whereas writes handles old data.

Note: If W0 <p W1 is still enforced, not all write latency can be hidden.

Question 26

Why would we want to relax Write-Write ordering?

Answer 26

Can hide more write latency as writes can be issued while writes to different addresses have not yet completed.

Question 27

What is the advantage of PSO?

Answer 27

Both write-read and write-write are relaxed

Can now empty stores from buffer in any order

Must still generate all older addresses to prevent issues with aliasing

Question 28

Why would we want to relax read-write and read-read?

Answer 28

Allows for even more MLP

These are most effective when other rules are also abolished

Question 29

What happens if we also relax read-write and read-read?

Answer 29

Explicit sunch is always necessary for coordinated program execution

Question 30

Why is a weaker consistency model better for hardware design?

Answer 30

Can have more MLP, but makes it difficult for the programmer

Question 31

What are memory barriers?

Answer 31

Special operations that enforce an ordering within the CPU

Serialises all memory instructions before and after the barrier

All mem-ops before the barrier completes before the barrier instruction complete. No mem-ops after the barrier are initiated before the barrier has completed

Question 32

What are some downsides with introducing barriers?

Answer 32

Force synchronisation - don’t have as liberal ordering as before, so less possible performance benefits (MLP).

They typically force FULL serialisation, which can result in the SC model

Question 33

What is Release Consistency (RC)?

Answer 33

Part of group of Weak Orderings (WOs)

Have more fine grained primitives. Can synchronise around specific operations - the acquire and release operations.

These operations are barriers that enforce specific ordering.

With release and acquire, we get a new, bigger set of rules.

Question 34

In RC what does Acquire do?

Answer 34

Getting permission from other processors for subsequent memory accesses

Previous memory accesses can be overlapped, but next memory access has to follow a release from somewhere else.

Question 35

In RC what does Release do?

Answer 35

Giving permission to other processors for previous memory accesses.

Subsequent memory accesses can be overlapped

Question 36

What is a trend in programming models, in regards to correctness?

Answer 36

The programming model guarantee correct execution for data-race free programs

However, if a program contains race conditions, there are no guarantees for execution. Meaning the programmer must implement explicit synchronisation themselves to achieve correctness.

Question 37

Why do we need synchronisation?

Answer 37

It is central in all kinds of parallelism
- synch access to resources
- order events from cooperating processes correctly
- used for shared memory programming

Question 38

How is synchronisation implemented in smaller multiprocessor systems?

Answer 38

Using uninterrupted instruction(s) atomically accessing a value

This requires special hardware support

Simplifies construction of OS / parallel applications

Question 39

What are the pros and cons of sequential consistency?

Answer 39

Pros:
- ensures program order and write atomicity
- intuitive and easy to use

Cons:
- No optimisations and bad performance

Question 40

What are the pros and cons of relaxed consistency?

Answer 40

Pros:
- Enables more optimisations and better performance
- Wide variety of models offers maximum flexibility

Cons:
- Does not ensure program order
- Added complexity for programmers and compilers

Question 41

What are atomic operations?

Answer 41

Special instructions that are used to guarantee execution semantics. This means that they differ from normal instructions by having this added guarantee about what is happening in the system.

Guarantee execution without interference from other programs.

Question 42

What are two examples of atomic operations?

Answer 42

Load-link / store-conditional

Atomic swap

Question 43

What is Load-link / Store-conditional

Answer 43

Used in a sequence: first LL then SC

If memory location accessed by LL is written to, SC fails

If contect switch between LL and SC, SC fails

Question 44

How is LL / SC implemented?

Answer 44

Using a special link register.

This register contains the address used in LL.

This is reset (to zero) if matching cache block is invalidated or if we get an interrupt.

SC checks if the link register contains the same address. If so, we have atomic execution of LL & SC

The store is conditional, on the link load not being messed with

Question 45

What is atomic exchange (swap)?

Answer 45

Swaps value in register for value in memory

If mem = 0, not locked
Mem = 1, locked

Sets the register to 1 -> means the processor wants the lock.
Then perform an exchange operation:
Exchange(register, mem)

If register ends up being 0 we have a success. Mem was 0 and is now 1.

If register ends up being 1 we failed. Mem was 1 and was locked. Still locked because mem is still 1.

The exchange must always be atomic.